迅闻网
让更多人看到你

浅谈 Go 语言高性能哈希表的规划与完成

MatrixOne数据库是什么?
MatrixOne是一个新一代超交融异构数据库,致力于打造单一架构处理TP、AP、流核算等多种负载的极简大数据引擎。MatrixOne由Go言语所开发,并已于2021年10月开源,目前现已release到0.3版本。在MatrixOne已发布的功能陈述中,与业界抢先的OLAP数据库Clickhouse相比也不落劣势。作为一款Go言语完成的数据库,居然能够与C++完成的顶级OLAP数据库功能媲美,这其间就涉及到了许多方面的优化,包括高功能哈希表的完成,本文就将详细说明MatrixOne是如何用Go完成高功能哈希表的。
Github地址:https://github.com/matrixorigin/matrixone
2
哈希表数据结构根底
哈希表(Hashtable)是一种十分根底的数据结构,关于数据库的分组聚合和Join查询的功能至关重要。以如下的分组聚合为例(补白,图引自参阅文献1):
SELECTcol,count(*)FROMtableGROUPBYcol
groupby
它包括两个处理阶段:第1阶段是运用数据源的数据树立一个哈希表。哈希表中的每条记载都与一个计数器有关。假如记载是新刺进的,相关的计数器被设置为1;否则,计数器被递增。第二阶段是将哈希表中的记载集组成一种可用于进一步查询处理的格局。
关于Join查询而言,以如下SQL为例:
SELECTA.left_col,B.right_colFROMAJOINBUSING(key_col)
join
它相同也有两个阶段:第一阶段是运用Join句子右侧表的数据树立一个哈希表,第二阶段是从左侧表中读取数据,并快速勘探刚刚树立的哈希表。构建阶段与上面的分组完成相似,但每个哈希表的槽位都存储了对右边列的引证。
由此可见,哈希表关于数据库的SQL根底能力起着很要害的作用,本文评论哈希表的根本规划与对功能的影响,比较各种常见哈希表完成,然后介绍咱们为MatrixOne完成的哈希表的规划挑选与工程优化,最后是功能测验成果。
咱们预设读者现已对文中说到哈希表相关的概念有所了解,主要评论其对功能的影响,不做详细科普。假如对根本概念并不了解,请从其他来历获取相关知识,例如维基百科。
3
哈希表根本规划与对功能的影响
磕碰处理
不同的key经哈希函数映射到同一个桶,称作哈希磕碰。各种完成中最常见的磕碰处理机制是链地址法(chaining)和敞开寻址法(open-addressing)。
链地址法
在哈希表中,每个桶存储一个链表,把相同哈希值的不同元素放在链表中。这是C++规范容器一般选用的办法。
优点:
完成最简略直观
空间糟蹋较少
敞开寻址法
若刺进时产生磕碰,从磕碰产生的那个哈希桶开始,按照一定的次序,找出一个闲暇的桶。
优点:
每次刺进或查找操作只有一次指针跳转,对CPU缓存更友爱
一切数据存放在一块接连内存中,内存碎片更少
当maxloadfactor较大时,功能不如链地址法。可是当咱们主动牺牲内存,挑选较小的maxloadfactor时(例如0.5),形势就产生逆转,敞开寻址法反而功能更好。因为这时哈希磕碰的概率大大减小,缓存友爱的优势得以凸显。
值得注意的是,C++规范容器完成不选用敞开寻址法是由C++规范决定,而非依据功能考量(详细可见这个boost文档)。
Maxloadfactor
对链地址法哈希表,指均匀每个桶所含元素个数上限。
对敞开寻址法哈希表,指已填充的桶个数占总的桶个数的最大比值。
maxloadfactor越小,哈希磕碰的概率越小,一起糟蹋的空间也越多。
Growthfactor
指当已填充的桶到达maxloadfactor限制的上限,哈希表需求rehash时,内存扩张的倍数。growthfactor越大,哈希表rehash的次数越少,可是内存糟蹋越多。
闲暇桶勘探办法
在敞开寻址法中,若哈希函数返回的桶现已被其他key占据,需求经过预设规矩去接近的桶中寻觅闲暇桶。最常见有以下办法(假定总共|T|个桶,哈希函数为H(k)):
线性勘探(linearprobing):对i=0,1,2…,顺次勘探第H(k,i)=H(k)+cimod|T|个桶。
平方勘探(quadraticprobing):对i=0,1,2…,顺次勘探H(k,i)=H(k)+c1i+c2i2mod|T|。其间c2不能为0,否则退化成线性勘探。
双重哈希(doublehashing):运用两个不同哈希函数,顺次勘探H(k,i)=(H1(k)+i*H2(k))mod|T|。
线性勘探法比照其他办法,均匀需求勘探的桶数量最多。可是线性勘探法访问内存总是次序接连访问,最为缓存友爱。因而,在抵触概率不大的时分(maxloadfactor较小),线性勘探法是最快的办法。
其他还有一些更精巧的勘探办法,例如cuckoohashing,hopscotchhashing,robinhoodhashing(文章开头给的维基百科页面里都有介绍)。可是它们都是为maxloadfactor较大(0.6以上)的景象规划的。在maxloadfactor=0.5的时分,实践测验中功能都不如最原始最直接的线性勘探。

 

Go
4
一些常见的哈希表完成
C++std::unordered_map/boost::unordered_map
依据上面说到的原因,处理磕碰运用链地址法。默认maxloadfactor=1,growthfactor=2。规划简略,不必多说。
gomap
经过阅览golang库的代码得知,golang内置的map选用链地址法。
swisstable
来自于Google推出的abseil库,是一款功能十分优异的针对通用场景的哈希表完成。磕碰处理办法运用敞开寻址,地址勘探办法是在分块内部做平方勘探。parallel-hashmap,以及rust言语规范库的哈希表完成,都是依据swisstable。更多信息可参阅此处。
ClickHouse的哈希表完成
选用敞开寻址,线性勘探。maxloadfactor为0.5,growthfactor在桶数量小于2^24时为4,否则为2。
针对key为字符串的景象,ClickHouse还有专门的依据字符串长度自习惯的哈希表完成,详细参见论文,这儿不展开。
5
高效哈希表的规划与完成
MatrixOne是运用go言语开发的数据库,市面上的知名哈希表完成咱们都无缘直接运用,而在初始的完成中,咱们选用了go言语自带的map,成果高基数的分组(比如多特点分组很容易做到高基数)功能相比ClickHouse差距会接近一个数量级,低基数也慢不少,所以咱们有必要完成自己的版本。
根本规划与参数挑选
ClickHouse的哈希表在自带的benchmark中表现出了最高的功能,因而借鉴其详细完成成为十分天然的挑选。咱们照搬了ClickHouse的如下规划:
敞开寻址
线性勘探
maxloadfactor=0.5,growthfactor=4
整数哈希函数依据CRC32指令
详细原因前面现已说到,当maxloadfactor不大时,敞开寻址法要优于链地制法,一起线性勘探法又优于其他的勘探办法。
并做了如下修改(优化):
字符串哈希函数依据AESENC指令
刺进、查找、扩张时批量核算哈希函数
扩张时直接遍历旧表刺进新表
ClickHouse是先把旧表全体memcpy到新表中,再遍历调整位置。没找到如此规划的原因,可是经测验功能不如咱们的办法。
哈希函数
哈希函数的作用是将恣意的key映射到哈希表的一个地址,是哈希表刺进和查找进程的第一步。数据库场景中运用的哈希函数,应该满足:
速度尽量快
打散得尽量均匀(避免聚集),这样使得磕碰概率尽量小,若哈希表做分区的话也可保证分得均匀
不需求考虑密码学安全性
在ClickHouse的完成中,主要运用现代CPU(amd64或者arm64)自带的CRC32指令来完成哈希函数。
inlineDB::UInt64intHashCRC32(DB::UInt64x){#ifdef__SSE4_2__return_mm_crc32_u64(-1ULL,x);#elifdefined(__aarch64__)&&defined(__ARM_FEATURE_CRC32)return__crc32cd(-1U,x);#else///OnotherplatformswedonothaveCRC32.NOTEThiscanbeconfusing.returnintHash64(x);#endif}
经实测,打散作用十分不错,并且每个64位整数只需一条CPU指令,现已到达理论极限,速度远超xxhash,Murmur3等一系列没有运用特殊指令的“普通”哈希函数。
咱们的整数哈希函数也运用相同的办法完成。
TEXT·Crc32Int64Hash(SB),NOSPLIT,$0-16MOVQ$-1,SI
CRC32Qdata+0(FP),SI
MOVQSI,ret+8(FP)
RET
值得注意的是,go言语不具有C/C++/rust的intrinsics函数库,因而要运用某些特殊的指令,只能用go汇编自己完成。并且go汇编函数目前无法内联,因而为了最大化功能,需求把核算哈希函数的进程做成批量化。这点将在后续的文章中详细介绍。
包括CRC32指令的SSE4.2最早见于2008年发布的Nehalem架构CPU。因而咱们假定用户的CPU都支撑这一指令,毕竟更老的设备用来跑AP数据库似乎不太合适了。
关于字符串类型的哈希函数,ClickHouse依然经过CRC32指令完成。咱们经过调研,挑选依据AESENC指令来完成。AESENC包括在AES-NI指令集中,由Intel于2010年发布的Westmere架构中首次引入,单条指令执行AES加密进程中的一个round。AESENC均匀一条指令处理128位数据,比CRC32更快,并且供给128位成果,习惯更多应用场景(比照CRC32只有32位)。在实测中依据AESENC的哈希函数打散作用相同优异。网络上依据AESENC指令完成的哈希函数现已有不少,例如nabhash,meowhash,aHash。咱们自己的完成在这儿(amd64)和这儿(arm64)。
特殊优化
咱们针对字符串key,运用了一种十分规的规划:不在哈希表中保存原始的key,而是存两个不同的依据AESENC指令的哈希函数,其间一个64位的成果当作哈希值,另一个128位的成果当作“key”。192位再加上64位的value,每个桶宽度正好是32字节,可彻底与CPU的cacheline对齐。在磕碰处理中,不比较原始key,而是比较这192位的数据。不同的字符串两个哈希值一起磕碰的概率极低,在AP体系中能够忽略不计。这样做的优势是把变长字符串比较变成了定长的3个64位整数比较,并且还省掉一次指针跳转开销,大大加快磕碰检测的进程。
代码片段:
typeStringHashMapCellstruct{
HashState[3]uint64Mappeduint64}
…func(ht*StringHashMap)findCell(state*[3]uint64)*StringHashMapCell{
mask:=ht.cellCnt-1idx:=state[0]&mask
for{
cell:=&ht.cells[idx]
ifcell.Mapped==0||cell.HashState==*state{
returncell
}
idx=(idx+1)&mask
}
returnnil}
详细完成代码
https://github.com/matrixorigin/matrixone/tree/main/pkg/container/hashtable
6
功能测验
测验环境
CPU:AMDRyzen95900X
内存:DDR4-320032GB
操作体系:Manjaro21.2
内核版本:5.16.11
数据:ClickHouse供给的一亿行Yandex.Metrica数据集
测验内容
每个测验都是次序刺进一亿条记载,再以相同次序查找一亿条记载。进程相似如下代码所展现:
…//Insertfor(autok:data){
hash_map.emplace(k,hash_map.size()+1);
}
…//Findsize_tsum=0;for(autok:data){
sum+=hash_map[k]
}

整数key成果
下表中记载了一些哈希表完成对Yandex.Metrica数据集不同特点insert/find所用的时间,单位毫秒(ms)。
特点ParamPriceCounterIDRegionIDFUniqIDUserIDURLHashRefererHashWatchID
基数1109650690401511266817630976207148652159875699997493
ClickHouseHashMap67/46175/147154/1411235/8731651/8932051/10271945/10335389/2040
google::dense_hash_map767/758273/262261/2601861/10711909/10202134/11582203/11566181/2365
absl::flat_hash_map227/223236/230230/2311544/12631685/13542092/15041987/15216278/3166
std::unordered_map298/301323/356443/4434740/22774966/24595473/30585536/284924832/6348
tsl::hopscotch_map166/162376/250167/1672151/9202225/10063055/12782830/12469473/3170
tsl::robin_map247/281240/225276/2541641/11522052/11322445/13202371/12957409/2651
tsl::sparse_map425/405550/419441/4153090/19063773/22324712/27604508/260518342/7025
gomap361/433537/482461/4603039/17123186/18184527/25714175/241115774/6027
MatrixOneInt64HashMap190/182190/191191/1911112/7591160/7931445/9071400/9223205/1613
能够看出当基数十分小的时分,ClickHouse完成最快。在基数较大时,MatrixOrigin的完成最快,且基数越大抢先得越多。
字符串key成果
特点OriginalURLTitleURLReferer
基数851012394257181834203519720815
ClickHouseStringHashMap2840/16853873/28445726/37134751/2987
ClickHouseHashMapWithSavedHash2628/17083508/29055332/36794458/2963
ClickHouseHashMap3931/15704203/25737137/32826159/2644
gomap5402/24409515/456412881/574110750/4624
MatrixOneStringHashMap1743/12282434/18292520/18112563/1955
成果与整数key相似,基数越大咱们的完成抢先越多。
7
总结
以上功能测验成果现已大大超出了咱们最初的预期。咱们从移植ClickHouse自带哈希表动身,预计因为言语差异,终究能到达C++原版70~80%的功能。跟着反复的迭代优化,以及不断尝试改动ClickHouse本来的一些规划,终究在哈希表的刺进和查找功能上居然超越了C++版本。
这说明哪怕是一些十分根底的一般被以为早已研讨透了的数据结构,经过针对特定应用场景细心的规划和部分运用汇编加快,也可让go完成的版本在功能上一点不输C/C++/rust版本。这也为咱们坚持用go言语开发高功能数据库供给了更多信心。

未经允许不得转载:迅闻网 » 浅谈 Go 语言高性能哈希表的规划与完成
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

迅闻网-让更多人看到你

登录/注册返回首页