浅谈MatrixOne如何用Go语言设计与实现高性能哈希表

# 目录 - [MatrixOne数据库是什么?](#MatrixOne数据库是什么?) - [哈希表数据结构基础](#哈希表数据结构基础) - [哈希表基本设计与对性能的影响](#哈希表基本设计与对性能的影响) - [碰撞处理](#碰撞处理) - [链地址法](#链地址法) - [开放寻址法](#开放寻址法) - [Max load factor](#max-load-factor) - [Growth factor](#growth-factor) - [空闲桶探测方法](#空闲桶探测方法) - [一些常见的哈希表实现](#一些常见的哈希表实现) - [C++ std::unordered_map/boost::unordered_map](#c-stdunordered_mapboostunordered_map) - [go map](#go-map) - [swisstable](#swisstable) - [ClickHouse的哈希表实现](#clickhouse的哈希表实现) - [高效哈希表的设计与实现](#高效哈希表的设计与实现) - [基本设计与参数选择](#基本设计与参数选择) - [哈希函数](#哈希函数) - [特殊优化](#特殊优化) - [具体实现代码](#具体实现代码) - [性能测试](#性能测试) - [测试环境](#测试环境) - [测试内容](#测试内容) - [整数key结果](#整数key结果) - [字符串key结果](#字符串key结果) - [总结](#总结) # 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 # 哈希表数据结构基础 哈希表（Hashtable）是一种非常基础的数据结构，对于数据库的分组聚合和Join查询的性能至关重要。以如下的分组聚合为例(备注，图引自参考文献[1])： `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实现的哈希表的设计选择与工程优化，最后是性能测试结果。 我们预设读者已经对文中提到哈希表相关的概念有所了解，主要讨论其对性能的影响，不做详细科普。如果对基本概念并不了解，请从其他来源获取相关知识，例如[维基百科](https://en.wikipedia.org/wiki/Hash_table)。 # 哈希表基本设计与对性能的影响 ## 碰撞处理 不同的key经哈希函数映射到同一个桶，称作哈希碰撞。各种实现中最常见的碰撞处理机制是链地址法（chaining）和开放寻址法（open-addressing）。 ### 链地址法 在哈希表中，每个桶存储一个链表，把相同哈希值的不同元素放在链表中。这是C++标准容器通常采用的方式。 优点： * 实现最简单直观 * 空间浪费较少 ### 开放寻址法 若插入时发生碰撞，从碰撞发生的那个哈希桶开始，按照一定的次序，找出一个空闲的桶。 优点： * 每次插入或查找操作只有一次指针跳转，对CPU缓存更友好 * 所有数据存放在一块连续内存中，内存碎片更少 当max load factor较大时，性能不如链地址法。然而当我们主动牺牲内存，选择较小的max load factor时（例如0.5），形势就发生逆转，开放寻址法反而性能更好。因为这时哈希碰撞的概率大大减小，缓存友好的优势得以凸显。 值得注意的是，C++标准容器实现不采用开放寻址法是由C++标准决定，而非根据性能考量（详细可见这个[boost文档](https://www.boost.org/doc/libs/1_78_0/doc/html/unordered/rationale.html#unordered.rationale.data_structure)）。 ## Max load factor 对链地址法哈希表，指平均每个桶所含元素个数上限。 对开放寻址法哈希表，指已填充的桶个数占总的桶个数的最大比值。 max load factor越小，哈希碰撞的概率越小，同时浪费的空间也越多。 ## Growth factor 指当已填充的桶达到max load factor限定的上限，哈希表需要rehash时，内存扩张的倍数。growth factor越大，哈希表rehash的次数越少，但是内存浪费越多。 ## 空闲桶探测方法 在开放寻址法中，若哈希函数返回的桶已经被其他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) + c₁i + c₂i² mod |T|。其中c₂不能为0，否则退化成线性探测。 * 双重哈希（double hashing）：使用两个不同哈希函数，依次探测H(k, i) = (H₁(k) + i * H₂(k)) mod |T|。 线性探测法对比其他方法，平均需要探测的桶数量最多。但是线性探测法访问内存总是顺序连续访问，最为缓存友好。因此，在冲突概率不大的时候（max load factor较小），线性探测法是最快的方式。 其他还有一些更精巧的探测方法，例如cuckoo hashing，hopscotch hashing，robin hood hashing（文章开头给的维基百科页面里都有介绍）。然而它们都是为max load factor较大（0.6以上）的情形设计的。在max load factor = 0.5的时候，实际测试中性能都不如最原始最直接的线性探测。 # 一些常见的哈希表实现 ## C++ std::unordered_map/boost::unordered_map 基于上面提到的原因，处理碰撞使用链地址法。默认max load factor = 1，growth factor = 2。设计简单，不用多说。 ## go map 通过阅读golang库的代码得知，golang内置的map采用链地址法。 ## swisstable 来自于Google推出的[abseil库](https://abseil.io/blog/20180927-swisstables)，是一款性能十分优秀的针对通用场景的哈希表实现。碰撞处理方式使用开放寻址，地址探测方法是在分块内部做平方探测。[parallel-hashmap](https://github.com/greg7mdp/parallel-hashmap)，以及rust语言标准库的哈希表实现，都是基于swisstable。更多信息可参考[此处](https://zhuanlan.zhihu.com/p/277732297)。 ## ClickHouse的哈希表实现 采用开放寻址，线性探测。max load factor为0.5，growth factor在桶数量小于2^24时为4，否则为2。 针对key为字符串的情形，ClickHouse还有专门的根据字符串长度自适应的哈希表实现，具体参见[论文](https://www.researchgate.net/publication/339879042_SAHA_A_String_Adaptive_Hash_Table_for_Analytical_Databases)，这里不展开。 # 高效哈希表的设计与实现 MatrixOne是使用go语言开发的数据库，市面上的知名哈希表实现我们都无缘直接使用，而在初始的实现中，我们采用了go语言自带的map，结果高基数的分组(比如多属性分组很容易做到高基数)性能相比ClickHouse差距会接近一个数量级，低基数也慢不少，所以我们必须实现自己的版本。 ## 基本设计与参数选择 ClickHouse的哈希表在自带的benchmark中表现出了最高的性能，因此借鉴其具体实现成为十分自然的选择。我们照搬了ClickHouse的如下设计： * 开放寻址 * 线性探测 * max load factor = 0.5，growth factor = 4 * 整数哈希函数基于CRC32指令 具体原因前面已经提到，当max load factor不大时，开放寻址法要优于链地制法，同时线性探测法又优于其他的探测方法。 并做了如下修改（优化）： * 字符串哈希函数基于AESENC指令 * 插入、查找、扩张时批量计算哈希函数 * 扩张时直接遍历旧表插入新表 * ClickHouse是先把旧表整体memcpy到新表中，再遍历调整位置。没找到如此设计的原因，但是经测试性能不如我们的方式。 ## 哈希函数 哈希函数的作用是将任意的key映射到哈希表的一个地址，是哈希表插入和查找过程的第一步。数据库场景中使用的哈希函数，应该满足： * 速度尽量快 * 打散得尽量均匀（避免聚集），这样使得碰撞概率尽量小，若哈希表做分区的话也可保证分得均匀 * 不需要考虑密码学安全性 在ClickHouse的实现中，主要使用现代CPU（amd64或者arm64）自带的CRC32指令来实现哈希函数。 ```c++ 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等一系列没有使用特殊指令的“普通”哈希函数。 我们的整数哈希函数也使用同样的方法实现。 ```go 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](https://github.com/mengzhuo/nabhash)，[meowhash](https://github.com/cmuratori/meow_hash)，[aHash](https://github.com/tkaitchuck/aHash)。我们自己的实现在[这里（amd64）](https://github.com/matrixorigin/matrixone/blob/6c57eceb783fefbc3b62c8c896918e33928921e4/pkg/container/hashtable/hash_amd64.s#L176)和[这里（arm64）](https://github.com/matrixorigin/matrixone/blob/6c57eceb783fefbc3b62c8c896918e33928921e4/pkg/container/hashtable/hash_arm64.s#L178)。 ## 特殊优化 我们针对字符串key，使用了一种非常规的设计：不在哈希表中保存原始的key，而是存两个不同的基于AESENC指令的哈希函数，其中一个64位的结果当作哈希值，另一个128位的结果当作“key”。192位再加上64位的value，每个桶宽度正好是32字节，可完全与CPU的cacheline对齐。在碰撞处理中，不比较原始key，而是比较这192位的数据。不同的字符串两个哈希值同时碰撞的概率极低，在AP系统中可以忽略不计。这样做的优势是把变长字符串比较变成了定长的3个64位整数比较，而且还省掉一次指针跳转开销，大大加速碰撞检测的过程。 代码片段： ```go 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 # 性能测试 ## 测试环境 * CPU：AMD Ryzen 9 5900X * 内存：DDR4-3200 32GB * 操作系统：Manjaro 21.2 * 内核版本：5.16.11 * 数据：ClickHouse提供的一亿行Yandex.Metrica数据集 ## 测试内容 每个测试都是顺序插入一亿条记录，再以相同顺序查找一亿条记录。过程类似如下代码所展示： ```c++ ... // 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）。 | 属性 | ParamPrice | CounterID | RegionID | FUniqID | UserID | URLHash | RefererHash | WatchID | | - | - | - | - | - | - | - | - | - | | 基数 | 1109 | 6506 | 9040 | 15112668 | 17630976 | 20714865 | 21598756 | 99997493 | | ClickHouse HashMap | 67 / 46 | 175 / 147 | 154 / 141 | 1235 / 873 | 1651 / 893 | 2051 / 1027 | 1945 / 1033 | 5389 / 2040 | | [google::dense_hash_map][1] | 767 / 758 | 273 / 262 | 261 / 260 | 1861 / 1071 | 1909 / 1020 | 2134 / 1158 | 2203 / 1156 | 6181 / 2365 | | [absl::flat_hash_map][2] | 227 / 223 | 236 / 230 | 230 / 231 | 1544 / 1263 | 1685 / 1354 | 2092 / 1504 | 1987 / 1521 | 6278 / 3166 | | std::unordered_map | 298 / 301 | 323 / 356 | 443 / 443 | 4740 / 2277 | 4966 / 2459 | 5473 / 3058 | 5536 / 2849 | 24832 / 6348 | | [tsl::hopscotch_map][3] | 166 / 162 | 376 / 250 | 167 / 167 | 2151 / 920 | 2225 / 1006 | 3055 / 1278 | 2830 / 1246 | 9473 / 3170 | | [tsl::robin_map][4] | 247 / 281 | 240 / 225 | 276 / 254 | 1641 / 1152 | 2052 / 1132 | 2445 / 1320 | 2371 / 1295 | 7409 / 2651 | | [tsl::sparse_map][5] | 425 / 405 | 550 / 419 | 441 / 415 | 3090 / 1906 | 3773 / 2232 | 4712 / 2760 | 4508 / 2605 | 18342 / 7025 | | go map | 361 / 433 | 537 / 482 | 461 / 460 | 3039 / 1712 | 3186 / 1818 | 4527 / 2571 | 4175 / 2411 | 15774 / 6027 | | MatrixOne Int64HashMap | 190 / 182 | 190 / 191 | 191 / 191 | 1112 / 759 | 1160 / 793 | 1445 / 907 | 1400 / 922 | 3205 / 1613 [1]: <https://github.com/sparsehash/sparsehash> [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> 可以看出当基数非常小的时候，ClickHouse实现最快。在基数较大时，MatrixOrigin的实现最快，且基数越大领先得越多。 ## 字符串key结果 | 属性 | OriginalURL | Title | URL | Referer | | - | - | - | - | - | | 基数 | 8510123 | 9425718 | 18342035 | 19720815 | | ClickHouse StringHashMap | 2840 / 1685 | 3873 / 2844 | 5726 / 3713 | 4751 / 2987 | | ClickHouse HashMapWithSavedHash | 2628 / 1708 | 3508 / 2905 | 5332 / 3679 | 4458 / 2963 | | ClickHouse HashMap | 3931 / 1570 | 4203 / 2573 | 7137 / 3282 | 6159 / 2644 | | go map | 5402 / 2440 | 9515 / 4564 | 12881 / 5741 | 10750 / 4624 | | MatrixOne StringHashMap | 1743 / 1228 | 2434 / 1829 | 2520 / 1811 | 2563 / 1955 | 结果与整数key类似，基数越大我们的实现领先越多。 # 总结 以上性能测试结果已经大大超出了我们最初的预期。我们从移植ClickHouse自带哈希表出发，预计由于语言差异，最终能达到C++原版70~80%的性能。随着反复的迭代优化，以及不断尝试改变ClickHouse原本的一些设计，最终在哈希表的插入和查找性能上竟然超越了C++版本。 这说明哪怕是一些非常基础的通常被认为早已研究透了的数据结构，通过针对特定应用场景仔细的设计和部分使用汇编加速，也可让go实现的版本在性能上一点不输C/C++/rust版本。这也为我们坚持用go语言开发高性能数据库提供了更多信心。 # 参考文献 1. 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 # MatrixOne社区 对MatrixOne有兴趣的话可以关注矩阵起源公众号或者加入MatrixOne社群。  微信公众号 矩阵起源  MatrixOne社区群 技术交流