MatrixOne Intelligence 开服在即，点击浅谈 MatrixOne如何用Go 语言高性能哈希表的设计与实现
“
作者简介 PROFILE
龙冉
矩阵起源高级研发工程师
目录
1. MatrixOne数据库是什么?
2. 哈希表数据结构基础
3. 哈希表基本设计与对性能的影响
3.1 链地址法
3.2 开放寻址法
3.3 碰撞处理
3.4 Max load factor
3.5 Growth factor
3.6 空闲桶探测方法
4. 一些常见的哈希表实现
4.1 C++ std::unordered_map/
boost::unordered_map
4.2 go map
4.3 swisstable
4.4 ClickHouse的哈希表实现
5. 高效哈希表的设计与实现
5.1 基本设计与参数选择
5.2 哈希函数
5.3 特殊优化
5.4 具体实现代码
6. 性能测试
6.1 测试环境
6.2 测试内容
6.3 整数key结果
6.4 字符串key结果
7. 总结
01 MatrixOne数据库是什么?
Github地址：https://github.com/matrixorigin/matrixone
02 哈希表数据结构基础
SELECT col, count(*) FROM table GROUP BY col
它包含两个处理阶段：第1阶段是使用数据源的数据建立一个哈希表。哈希表中的每条记录都与一个计数器有关。如果记录是新插入的，相关的计数器被设置为1；否则，计数器被递增。第二阶段是将哈希表中的记录集合成一种可用于进一步查询处理的格式。
对于Join查询而言，以如下SQL为例：
SELECT A.left_col, B.right_col FROM A JOIN B USING (key_col)
它同样也有两个阶段：第一阶段是使用Join语句右侧表的数据建立一个哈希表，第二阶段是从左侧表中读取数据，并快速探测刚刚建立的哈希表。构建阶段与上面的分组实现类似，但每个哈希表的槽位都存储了对右边列的引用。
由此可见，哈希表对于数据库的SQL基础能力起着很关键的作用 ，本文讨论哈希表的基本设计与对性能的影响，比较各种常见哈希表实现，然后介绍我们为MatrixOne实现的哈希表的设计选择与工程优化，最后是性能测试结果。
我们预设读者已经对文中提到哈希表相关的概念有所了解，主要讨论其对性能的影响，不做详细科普。如果对基本概念并不了解，请从其他来源获取相关知识，例如维基百科。
03
哈希表基本设计与对性能的影响
03
哈希表基本设计与对性能的影响
>> 碰撞处理
不同的key经哈希函数映射到同一个桶，称作哈希碰撞。各种实现中最常见的碰撞处理机制是链地址法（chaining）和开放寻址法（open-addressing）。
>> 链地址法
在哈希表中，每个桶存储一个链表，把相同哈希值的不同元素放在链表中。这是C++标准容器通常采用的方式。
优点：
实现最简单直观 空间浪费较少
>> 开放寻址法
若插入时发生碰撞，从碰撞发生的那个哈希桶开始，按照一定的次序，找出一个空闲的桶。
优点：
每次插入或查找操作只有一次指针跳转，对CPU缓存更友好 所有数据存放在一块连续内存中，内存碎片更少
当max load factor较大时，性能不如链地址法。然而当我们主动牺牲内存，选择较小的max load factor时（例如0.5），形势就发生逆转，开放寻址法反而性能更好。因为这时哈希碰撞的概率大大减小，缓存友好的优势得以凸显。
值得注意的是，C++标准容器实现不采用开放寻址法是由C++标准决定，而非根据性能考量（详细可见这个boost文档）。
>> Max load factor
>> Growth factor
>> 空闲桶探测方法
在开放寻址法中，若哈希函数返回的桶已经被其他key占据，需要通过预设规则去临近的桶中寻找空闲桶。最常见有以下方法（假设一共|T|个桶，哈希函数为H(k)）：
线性探测（linear probing）：对i = 0, 1, 2...，依次探测第H(k, i) = H(k) + ci mod |T|个桶。 平方探测（quadratic probing）：对i = 0, 1, 2...，依次探测H(k, i) = H(k) + c1i + c2i2 mod |T|。其中c2不能为0，否则退化成线性探测。 双重哈希（double hashing）：使用两个不同哈希函数，依次探测H(k, i) = (H1(k) + i * H2(k)) mod |T|。
线性探测法对比其他方法，平均需要探测的桶数量最多。但是线性探测法访问内存总是顺序连续访问，最为缓存友好。因此，在冲突概率不大的时候（max load factor较小），线性探测法是最快的方式。
其他还有一些更精巧的探测方法，例如cuckoo hashing，hopscotch hashing，robin hood hashing（文章开头给的维基百科页面里都有介绍）。然而它们都是为max load factor较大（0.6以上）的情形设计的。在max load factor = 0.5的时候，实际测试中性能都不如最原始最直接的线性探测。
04 一些常见的哈希表实现
>> go map
通过阅读golang库的代码得知，golang内置的map采用链地址法。
>> swisstable
>> ClickHouse的哈希表实现
05 高效哈希表的设计与实现
>> 基本设计与参数选择
ClickHouse的哈希表在自带的benchmark中表现出了最高的性能，因此借鉴其具体实现成为十分自然的选择。我们照搬了ClickHouse的如下设计：
开放寻址 线性探测 max load factor = 0.5，growth factor = 4 整数哈希函数基于CRC32指令
具体原因前面已经提到，当max load factor不大时，开放寻址法要优于链地制法，同时线性探测法又优于其他的探测方法。
并做了如下修改（优化）：
字符串哈希函数基于AESENC指令 插入、查找、扩张时批量计算哈希函数 扩张时直接遍历旧表插入新表 ClickHouse是先把旧表整体memcpy到新表中，再遍历调整位置。没找到如此设计的原因，但是经测试性能不如我们的方式。
>> 哈希函数
哈希函数的作用是将任意的key映射到哈希表的一个地址，是哈希表插入和查找过程的第一步。数据库场景中使用的哈希函数，应该满足：
速度尽量快 打散得尽量均匀（避免聚集），这样使得碰撞概率尽量小，若哈希表做分区的话也可保证分得均匀 不需要考虑密码学安全性
在ClickHouse的实现中，主要使用现代CPU（amd64或者arm64）自带的CRC32指令来实现哈希函数。
inline DB::UInt64 intHashCRC32(DB::UInt64 x)
{
#ifdef __SSE4_2__
return _mm_crc32_u64(-1ULL, x);
#elif defined(__aarch64__) && defined(__ARM_FEATURE_CRC32)
return __crc32cd(-1U, x);
#else
/// On other platforms we do not have CRC32. NOTE This can be confusing.
return intHash64(x);
#endif
}
经实测，打散效果非常不错，而且每个64位整数只需一条CPU指令，已经达到理论极限，速度远超xxhash， Murmur3等一系列没有使用特殊指令的“普通”哈希函数。
我们的整数哈希函数也使用同样的方法实现。
TEXT ·Crc32Int64Hash(SB), NOSPLIT, $0-16
MOVQ $-1, SI
CRC32Q data+0(FP), SI
MOVQ SI, 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位整数比较，而且还省掉一次指针跳转开销，大大加速碰撞检测的过程。
代码片段：
type StringHashMapCell struct {
HashState [3]uint64
Mapped uint64
}
...
func (ht *StringHashMap) findCell(state *[3]uint64) *StringHashMapCell {
mask := ht.cellCnt - 1
idx := state[0] & mask
for {
cell := &ht.cells[idx]
if cell.Mapped == 0 || cell.HashState == *state {
return cell
}
idx = (idx + 1) & mask
}
return nil
}
>> 具体实现代码
https://github.com/matrixorigin/matrixone/tree/main/pkg/container/hashtable
06 性能测试
CPU：AMD Ryzen 9 5900X 内存：DDR4-3200 32GB 操作系统：Manjaro 21.2 内核版本：5.16.11 数据：ClickHouse提供的一亿行Yandex.Metrica数据集
>> 测试内容
每个测试都是顺序插入一亿条记录，再以相同顺序查找一亿条记录。过程类似如下代码所展示：
...
// Insert
for (auto k : data) {
hash_map.emplace(k, hash_map.size() + 1);
}
...
// Find
size_t sum = 0;
for (auto k : data) {
sum += hash_map[k]
}
...
>> 整数key结果
下表中记录了一些哈希表实现对Yandex.Metrica数据集不同属性insert/find所用的时间，单位毫秒（ms）。
[2] https://github.com/abseil/abseil-cpp/tree/master/absl/container
[3] https://github.com/Tessil/hopscotch-map
[4] https://github.com/Tessil/robin-map
[5] https://github.com/Tessil/sparse-map
>> 字符串key结果
结果与整数key类似，基数越大我们的实现领先越多。
07 总结
以上性能测试结果已经大大超出了我们最初的预期。我们从移植ClickHouse自带哈希表出发，预计由于语言差异，最终能达到C++原版70~80%的性能。随着反复的迭代优化，以及不断尝试改变ClickHouse原本的一些设计，最终在哈希表的插入和查找性能上竟然超越了C++版本。
这说明哪怕是一些非常基础的通常被认为早已研究透了的数据结构，通过针对特定应用场景仔细的设计和部分使用汇编加速，也可让go实现的版本在性能上一点不输C/C++/rust版本。这也为我们坚持用go语言开发高性能数据库提供了更多信心。
08 参考文献
Tianqi Zheng, Zhibin Zhang, and Xueqi Cheng. 2020. SAHA: A String Adaptive Hash Table for Analytical Databases. Applied Sciences 10, 6 (2020). https: //doi.org/10.3390/app10061915