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

MatrixOne数据库是什么?
哈希表数据结构根底
哈希表根本设计与对性能的影响
- 碰撞解决
  - 链地址法
  - 凋谢寻址法
- Max load factor
- Growth factor
- 闲暇桶探测办法
一些常见的哈希表实现
- C++ std::unordered_map/boost::unordered_map
- go map
- swisstable
- ClickHouse的哈希表实现
高效哈希表的设计与实现
- 根本设计与参数抉择
- 哈希函数
- 非凡优化
- 具体实现代码
性能测试
- 测试环境
- 测试内容
- 整数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/matrixorig…

哈希表数据结构根底

哈希表（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实现的哈希表的设计抉择与工程优化，最初是性能测试后果。

咱们预设读者曾经对文中提到哈希表相干的概念有所理解，次要探讨其对性能的影响，不做具体科普。如果对基本概念并不理解，请从其余起源获取相干常识，例如维基百科。

哈希表根本设计与对性能的影响

碰撞解决

不同的key经哈希函数映射到同一个桶，称作哈希碰撞。各种实现中最常见的碰撞解决机制是链地址法（chaining）和凋谢寻址法（open-addressing）。

链地址法

在哈希表中，每个桶存储一个链表，把雷同哈希值的不同元素放在链表中。这是C++规范容器通常采纳的形式。

长处：

实现最简略直观
空间节约较少

凋谢寻址法

若插入时产生碰撞，从碰撞产生的那个哈希桶开始，依照肯定的秩序，找出一个闲暇的桶。

长处：

每次插入或查找操作只有一次指针跳转，对CPU缓存更敌对
所有数据寄存在一块间断内存中，内存碎片更少

当max load factor较大时，性能不如链地址法。然而当咱们被动就义内存，抉择较小的max load factor时（例如0.5），局势就产生逆转，凋谢寻址法反而性能更好。因为这时哈希碰撞的概率大大减小，缓存敌对的劣势得以凸显。

值得注意的是，C++规范容器实现不采纳凋谢寻址法是由C++规范决定，而非依据性能考量（具体可见这个boost文档）。

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库，是一款性能非常优良的针对通用场景的哈希表实现。碰撞解决形式应用凋谢寻址，地址探测办法是在分块外部做平方探测。parallel-hashmap，以及rust语言规范库的哈希表实现，都是基于swisstable。更多信息可参考此处。

ClickHouse的哈希表实现

采纳凋谢寻址，线性探测。max load factor为0.5，growth factor在桶数量小于2^24时为4，否则为2。

针对key为字符串的情景，ClickHouse还有专门的依据字符串长度自适应的哈希表实现，具体参见论文，这里不开展。

高效哈希表的设计与实现

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指令来实现哈希函数。

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/matrixorig…

性能测试

测试环境

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）。

属性	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	767 / 758	273 / 262	261 / 260	1861 / 1071	1909 / 1020	2134 / 1158	2203 / 1156	6181 / 2365
absl::flat_hash_map	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	166 / 162	376 / 250	167 / 167	2151 / 920	2225 / 1006	3055 / 1278	2830 / 1246	9473 / 3170
tsl::robin_map	247 / 281	240 / 225	276 / 254	1641 / 1152	2052 / 1132	2445 / 1320	2371 / 1295	7409 / 2651
tsl::sparse_map	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

能够看出当基数十分小的时候，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语言开发高性能数据库提供了更多信念。

参考文献

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社区群技术交换