杀手锏SwissTable

杀手锏SwissTable

0.导语

最近在研究HashJoin的性能，发现SwissTable的性能真牛逼，对于原生的哈希表采用STL的unordered_multimap，其性能一般，为了加速这个查找，Arrow提供了SwissJoin，其实现原理为SwissTable，但是其细节部分还是有很多不一样的地方，本节先来个开篇，以经典的abseil库的代码为例，先聊聊abseil库里面的SwissTable原理。

SwissTable在性能上远超于std::unordered_map的哈希表。

通常哈希表会面临几个问题，其中最重要的便是哈希碰撞。

比较经典的算法有：拉链法、线性探测法。

• 拉链法

像std::unordered_map的哈希表采用拉链法实现，对于CPU 需要读写内存地址，会检测缓存是否存在，由于链表的随机访问性质，会导致缓存查询失败，性能会骤降。

• 线性探测法

对于拉链法缓存问题，我们可以使用线性探测法解决，对cache来说比较友好。由于是顺序访问元素，当这些连续的内存正好是cache line的一部分时，省下了CPU指令周期，但是当元素越来越多，连续的序列也会变长，查询缓存失败率也会加大。

因此，我们需要解决几个问题：

• CPU cache比内存快n倍，如何有效利用cache来加速哈希表的查找？
• 如何解决hash冲突？

为了解决这些问题，于是有了缓存友好、内存与CPU效率比较高的SwissTable。

1.abseil SwissTable

SwissTable的伪代码：

int8_t* ctrl_;
char* slots_;

SwissTable划分为control byte结构与slots结构，如下图所示：

对于每个key的hash值，拆分成两部分：

H1: hash最左边57位，找到第几个group。

H2: hash最右边7位，

假设每个group有16个slot，同时有16个控制字节。

控制字节Carol byte为8位，有三个状态：

• 空

10000000

• 删除

11111110

• 在使用

当有数据时，ctro byte长这个样子：00010100，最高位为0。

• 哨兵

只是个dummy

当执行查询时，先通过h1计算出对应group的起始位置，然后扫描当前group中的控制字节(通过h2)，搜索出对应的slot。

其中根据group的其实位置扫描key是否存在这一步骤，如果进行“线性探测”可就太慢了。

于是SwissTable怎么做了？

一组的控制字节为 128 位，可以放入 L1 的cache line，像SSE2这类的指令，可以直接使用128位快速搜索出对应的slot。

所以可以一次比较一整个group的control bytes信息，从而确定这个key在不在当前group中，如下图所示，一次可以比较16个值。如果当前group没有找到，继续查找下一个group。当然涉及的好的话，一次可以通过simd算n个group。

插入过程：

• 查找到目标的key，如果存在，更新目标key，完毕。
• 当前hash值可以计算出哪个group，这个group如果满了，就下一个group找空位，然后插入对应slot。

当然插入过程还涉及扩容操作。

本节简单讲解了SwissTable的原理，下一节详细讲讲Arrow的SwissTable。