Cuckoo Hashing的应用及性能优化

written by 钦诚，祯祺

Cuckoo Hashing 的引入

在indexlib的底层，需要一个高性能的Key/Value引擎来提供类似python Dict/ Java HashMap/ C++ unordered map（这些数据结构的性能不能接受）的支持。最基本的就是支持insert(key, value)和find(key)这两种操作。原本我们有Dense Hash Table和Chain Hash Table这两种数据结构，但是它们各自都有明显的缺点。

1. Dense Hash Table就是普通的用线性探查解决冲突的哈希表，如图所示。当插入F时，通过哈希函数将F映射到表中所指位置，发现该位置已存有D了，向后扫描探查，直到碰到一个空位，再将F插入。而查询一个G时，则需要从对应的位置开始向后找，直到找到G（命中），或找到空位（G不在表中）。这种结构对内存的利用不佳，如果想让哈希表尽量存满(k, v)对，那么插入/查询的性能将会严重下降。

   

2. Chain Hash Table是利用拉链法解决冲突的哈希表，它的特点是空间利用率比较高，除了顺序存下所有(k, v)对之外仅需要一个索引来记录链表头，但由于链表的空间不连续，导致查询性能一般。

   • 在我们实现的版本中，图中的A,H,P,J,B,M,Q,D,W存在一块连续的内存区域中，但它们的顺序不一定，我们将其称作链表区域。
   • 一种较简单的优化是在全部插入操作完成之后，重新整理链表区域，把同一条链上的结点归到连续的区域，即链表空间中严格按照A, H, P, J, B, M, Q, D, W的顺序存储。这样，查询时若要遍历链表，不需要“跳”着访问，而是访问连续的地址。
   • 但这个步骤本身花费不小（可能的额外空间、时间），并且由于索引区域和链表区域仍不连续，需要两次访存，其性能仍然存疑。

   

3. Cuckoo Hash Table是本次引入的数据结构，它用了两个哈希函数来解决冲突。Cuckoo查询操作的理论复杂度为最差O(1)，优于Dense的期望查询复杂度O(1)和Chain的O(1+α)，而Cuckoo的插入复杂度为均摊O(1)。我们引入Cuckoo是希望它在实际应用中，能够在较高的空间利用率下，仍然维持不错的查询性能。

   • Cuckoo利用两个哈希函数来实现最差O(1)的查询复杂度：
     对任意一个Key可求出两个哈希值，相当于映射到两个桶，如A被映射到1,4，说明它可以被存到1号或4号桶，而实际在1号桶。本图中，用箭头连接某个Key实际存入的桶和另一个对应的桶，如1--->4。
   • 当插入一个F时，如果对应的两个桶至少有一个为空，则将其插入到这个位置，否则任选一个桶，不妨设为A所在的1号桶。我们将其中原有的A = Key’/Value’踢出，将新的F存入。对于刚取出的A，它之所以存储在1号桶是因为用了两个哈希函数之一，那么我们用另外一个哈希函数，知道A对应的位置还有4号桶。若4号桶为空，则将A放入，整个过程就结束了。而事实上，4号桶中还存有B = Key’’/Value’’，那么把它们踢出并重复上面的操作。整个过程中进行踢出、填入操作的，形如“1->4-> … ->空位”这样的序列我们将其称为Cuckoo Kick路径。
   • 当查询一个F时，分别检查它的的哈希值对应的两个位置即可。

我们的Cuckoo哈希表的特性

1. 使用4路组相联

   不进行组相联的Cuckoo，只能达到50%左右的容积率，就会开始出现插不进去新的(k, v)对的情况。而如果用组相联，则可以大幅提高容积率。组相联即上图中的一个位置，变为现在的一组位置，它们对应同一个哈希值。我们使用的4路组相联，可以在性能无明显下降时达到超过90%的容积率。

   如果使用k路的组相联，那么一次查询就意味着最多要查2k个桶。因此如果使用更多的路数进行组相联，虽然可以进一步提高容积率，但同时会导致每一次查询操作时扫描过多的桶，导致读性能下降，不能接受。我们常见的使用场景是8bit key + 8bit value和 8bit key + 4bit value。对于第一种情况，4路组相联可以保证每次查的一个block在同一个cache line中，而即使是第二种，也最多跨两个cache line。相当于利用cache line内的访问，来减少组相联对读性能的影响。

1. 使用BFS寻找Cuckoo Kick路径

   我们遇到冲突时，先不急着将Key/Value踢出，而是使用广度优先搜索，从A和B分别开始找一条完整的Cuckoo Kick路径，每一步都将组相联的4个桶一起加入BFS队列，这样可以保证找到的路径是最短的一条。找到之后，先把路径上最后一个Key/Value移到空位，形成新的空位，再把倒数第二个Key/Value移到空位，以此类推。
   

2. 支持增加哈希函数：

   在容积率达到较高（如90%）以后，如果希望再插入新的(k, v)对，那么插入过程中BFS寻找的Cuckoo Kick路径将会越来越长（见性能测试部分），插入性能将会快速下降。
   
   因此，我们在插入失败时，选择添加一个哈希函数（从2个变为3个，再不行变为4个，5个…，这意味着每个key对应的block从2个变成更多），让BFS搜索树从二叉树变成多叉树，使得找到一条Cuckoo Kick路径更加容易，在损失一些读性能的前提下，提高了容积率。
   

名词定义

• 我们的哈希表将key, value对完整地存下来，简称为(k, v)对
• 将哈希表中用来存储(k, v)对的位置称为桶（bucket），因此表体就是桶的数组
• 容积率(occupancy) = 已存有(k, v)对的桶数/总桶数，相当于空间利用率/load factor
• insert/插入/写，表示将一个(k, v)对插入哈希表
• find/查询/读/lookup，表示在哈希表中查询key对应的value
• 命中/查询成功/positive lookup，表示find函数在哈希表中成功找到了所查的key
• 不命中/查不到/negative lookup，表示find函数发现key不在哈希表中
• QPS(query per second或reqs per second) = 平均每秒完成的insert或find操作的次数
• Cuckoo的组相联意味着每4个桶对应同一个哈希值，这4个桶称为一个块（block）
• 一张Dense哈希表包括：表头（header）+ 表体（bucket的数组）
• 一张Cuckoo哈希表包括：表头（header）+ 表体（block的数组）+ 辅助数据结构（临时，仅插入时使用，不需要存下来）

参考资料

• Cuckoo Hashing for Undergraduates, Rasmus Pagh
• MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing, NSDI’13
• Algorithmic Improvements for Fast Concurrent Cuckoo Hashing, eurosys’14
• https://brilliant.org/wiki/cuckoo-filter/
• https://en.wikipedia.org/wiki/Cuckoo_hashing
• http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/05/linear-probing.html

Cuckoo Hashing性能测试

容积率

经过测试，在桶数较多的前提下（>10000），使用纯随机数据并且不使用增加哈希函数的功能，在插入性能明显下降之前可以达到92%左右的容积率，不考虑性能的因素，在第一次有key插入失败之前可以达到98%的容积率。

使用增加哈希函数的功能一起测试，一般可以达到100%的容积率，在1000000个桶的哈希表上进行容积率测试，结果如下表：

插入性能

由于Cuckoo Hash Table的特性，在容积率较低时，一次插入扫描的桶数、代码逻辑的复杂程度都高于Dense，导致只能获得2000000左右的QPS。而随着容积率的上升，越来越多的插入操作需要通过找Cuckoo Kick路径来获得一个空桶，而这个路径的长度也相应增长，其占用的时间、空间资源大幅上升。因此，整体的插入性能应该是比不上Dense和Chain的。

向一个有100,000,000个桶的Cuckoo Hash Table中不断插入key，它花费总时间的趋势如图所示。在容积率达到85%之前，插入时间基本是一条直线，说明没有明显的性能变化。而在约92%-93%之后，插入性能开始发生急剧下降。

总体来说，Cuckoo的插入性能是远逊与Dense Hash Table的，虽然Dense的性能在高容积率时也会快速下降，但容积率直到90%时插入性能仍远高于Cuckoo。

查询性能

考虑到我们引入Cuckoo 时，就是希望其能在较高的容积率下保持不错的查询性能，以在离线场景能节省空间，因此可以接受稍差一些的插入性能。所以，插入性能暂不在后面进一步讨论的范围内（即使插入也可以类似地使用Cuckoo性能优化这一节的方法来进行优化），而将关注点转移到查询性能上。

我们预期的查询性能是Dense在容积率较低时肯定性能出色，而随着容积率上升到70%-80%，每次查询遍历的桶数将快速上升，导致查询时间成比例的上升；Cuckoo预计的性能将不怎么受到容积率的影响，随着容积率的上升，查询性能只会缓慢下降；因此，在一定的容积率（如70%）时，其性能将会超过Dense，并逐渐将其甩开。

但是，实测的查询性能却并不理想，虽然前两个估计基本满足了，但是Cuckoo性能超过Dense的容积率节点却非常靠后，具体数据展示在Cuckoo、Dense、Chain性能对比。

其它性能测试

除以上的常规测试之外，还对Cache Line对齐、存储在第二个哈希函数对应位置占比等进行了测试（哈希表包含100,000,000个桶，里面装了90,000,000组(k, v)对），结论主要有以下几点：

• Cache Line如果不对齐，将导致10%-12%的性能下降。
• 查询全部命中时，只有23%的命中了第二个哈希函数对应的位置。
• 直接改为不查第二个哈希函数（只遍历第一个哈希函数对应的block，没有查到就退出），性能为原本的5倍。
• 8路组相联的性能较4路差很多，5路组相联较4路也有下降。

Cuckoo、Dense、Chain性能对比

在进行对比测试之前，已经初步优化了Cuckoo的代码，包括做了一些循环展开、条件判断的顺序调整、优化代码逻辑等等。为了保证Cuckoo与Dense、Chain格式尽量在公平的条件下进行对比测试，控制实验条件如下：

• 尽量为表体使用同样大小的内存，因此，Cuckoo和Dense表中包含的桶数是相同的，均为100,000,000。在建表时，Cuckoo会多用一些额外的辅助结构，它们占用了一定内存，但这部分最终是不用存下来的。
• 容积率统一设置为90%，即插入过程在插入90,000,000个(k, v)对后结束，之后开始测试查询性能。由于Chain不存在容积率的概念，我们仍按照保持内存大小一致的原则，用90,000,000个桶存下所有插入的(k, v)对（存多条链），剩下10,000,000个桶的空间作为索引（存链表头）。
• Key和Value各占用8个字节，Cuckoo Hash Table还满足表体的首字节地址为64的倍数，以确保Cache Line对齐（即一个Block对应一个Cache Line）。
• 采用一组实际的user_id数据进行测试。

测试结果如下图所示，横轴为哈希表的容积率，纵轴为查询操作的QPS。可以看出，在绝大部分key不命中的场景，反而是Chain哈希具有较好的性能，这是因为Chain每次查询访问的空间连续，且它不需要判断桶是否为empty，少一次比较操作，效率相对较高。而Cuckoo和Dense对于每个桶的检查是完全一致的，我们原本认为性能的差异应当对应于每次查询平均遍历的桶数/Cache Miss次数的差异。

在图示查询不命中的实测数据中，如果我们对Cuckoo和Dense这两种闭链哈希进行对比的话，仅在较低的容积率50%时，Dense的查询性能比Cuckoo好；在容积率为60%及以上，Cuckoo的性能就超过了使用线性探查的Dense；在容积率达到90%以后，Dense的性能已经退化到无法使用的地步。

这一结果基本符合我们的预期：Dense Hash Table随着越来越多的key的插入桶数组，空桶位越来越少，并且，key不命中的场景是需要遍历所有连续存有(k, v)对的桶（它们会跨越多个Cache Line，有多次Cache Miss），直到找到一个空桶，才能确定这个key确实不存在；而Cuckoo在大多数情况只有一次Cache Miss（扫第一个哈希函数对应的block），偶尔会有两次Cache Miss（扫第一个和第二个哈希函数对应的两个block），因此在容积率达到一定时，性能将会超过Dense。

然而，在全部命中的场景，Cuckoo的表现则不尽如人意，从横轴（容积率）来看，Dense的性能一路领先，直到达到90%的容积率时，性能才被Cuckoo反超，可以说离我们的期望有较大的差距。因为按照我们最初的想法（上一段中的预期），即使是命中的场景，只要容积率达到60%-70%，Dense也应该比Cuckoo扫描更多的桶，从而QPS比Cuckoo低。可是，实测数据却说明Dense的性能直到90%才被超过，这个差异将在Cuckoo性能分析与优化一节进行分析。

另一方面，插入完成后进行过链表区域整理的Chain哈希的查询性能则基本处于Cuckoo和Dense两者之间，考虑到在不命中时其性能领先，在容积率处于70%-90%之间时Chain也不失为一种解决方案。

Cuckoo 性能分析与优化

性能差异分析

首先回顾一下我们的预期：Cuckoo和Dense对于每个桶的检查是完全一致的，它们之间性能的差异应当在每次查询平均遍历的桶数/Cache Line数上。由于Dense就是普通的线性探查哈希，在容积率较高时，一个key实际存储的位置，相较于这个key通过哈希函数求出来的桶，往往需要探查较长的距离，也就是和Cuckoo相比（一次查询最多遍历8个桶）要遍历更多的桶。

考虑到实测结果，特别是key全部命中的情况，不符合我们的预期。于是我们统计了Cuckoo和Dense每次查询平均遍历的桶数，以判断以下假设的正确性：在较高的容积率时，Dense会比Cuckoo遍历更多的桶，这些桶跨越更多的Cache Lines。

上表展示的是每次查询平均扫描的桶数，可以看出，在Key查不到的情况下，Dense每次需要遍历的桶数远超Cuckoo需要遍历的桶数，因此性能不如Cuckoo也是合理的。但是，它们之间性能的实际差距远没有遍历的桶数的差距那么大。

而在Key全部命中的情况下，由于数据比较随机，Dense的散列效果并不差，在容积率为80%时平均遍历的桶数仅略多于Cuckoo，在90%时则超过较多，约为Cuckoo的1.7倍。然而，实测性能告诉我们容积率在80%甚至85%时，Dense的性能还领先于Cuckoo，90%时也只是略差于Cuckoo。综上所述，我们之前认为的“性能和遍历的桶数/Cache Miss次数成反比”这一断言存在一定的问题，我们需要找到其中隐藏的其他因素的影响。

一种可能的解释是Dense的空间局部性较好，每次查询操作都是由给定的key求出哈希值，再从哈希值对应的桶开始，向后连续遍历一些桶，直到找到这个key或者碰到一个空桶。即使这些桶跨越了较多的Cache Line，CPU还是能较好地进行分支预测、预取到缓存等操作。Cuckoo虽然做了Cache Line对齐，且每次查询最多会访问两个block，即两个Cache Line的数据，但这两个行之间没有任何联系，进行访存的时候CPU没有优化的余地，且还比Dense多了一次取模运算。考虑其它性能测试b)c)提到的，仅23%的操作访问了第二个哈希函数对应的行（占总操作的23/123），却导致了超过50%的性能差异，可见Cuckoo访问“第二行”的开销是相当大的。因此，在80%左右的容积率下，虽然Dense访问的桶数略多于Cuckoo，但它凭借优良的空间局部性挽回了不少性能；而Cuckoo被少数“需要访问第二个哈希函数的查询操作”中的第二次取模、第二次访存所拖累，所以性能不如Dense。

为了验证这种解释，我们使用Intel VTune抓取CPU数据，我们发现Cuckoo的查询函数中，有一条cmp汇编指令的平均CPI（Clockticks per Instructions）非常高，而这句指令前面是哈希函数（包括取模获取桶号）以及访存，并且访存指令依赖于取模的结果、cmp指令依赖于访存的结果，这一系列操作加起来可能占用数百个时钟周期。虽然上述指令的CPI并没有异常，但可以推测VTune是把这一系列指令的时钟周期算在了cmp指令上。

通过进一步查询资料以及和intel工程师的合作，基本可以确认瓶颈就是在取模、访存操作上（和Dense的差距也就在于Cuckoo可能用到的第二个哈希函数对应的取模、访存），而且我们使用的64位取模指令花费的时间可以达到32位取模的数倍。由于这几句汇编指令前后还存在数据依赖，更导致流水线几乎停顿，并且在这期间，超标量处理器的多个发射指令的port也只有一个能被使用。

取模与预取优化

最终，我们应用了两个优化：

1. 经过测试，发现仅将64位取模语句直接修改为32位取模就可以获得15%的性能提升。但在特定场景下的总桶数的确是可能超过4G的，因此考虑下述两种解决方案：

   • a) 将一个大表拆成多个桶数不超过4G的小表

   这就需要将key的值分段进行索引，一段索引到表，一段索引到个桶。这样就存在潜在的问题：一个是不同小表的容积率可能不会均衡；一个是可能需要两次取模。

   • b) 在桶数较少时，使用32位取模，桶数较多时仍维持64位取模

   这种修改比较容易实现，也足以优化大多数场景。可是，这就需要我们加入对桶数的条件判断，既可以每次取模时判断，也可以在建表前判断，并用函数指针确定每次调用的时64位模还是32位模。后者虽然不需要做多次判断，但是函数指针的存在导致代码不能内联，实测的性能是：

   32位取模>每次条件判断使用哪种>函数指针>64位取模。

2. 在应用了1.b)的优化后，减少了取模运算消耗的时间，可以利用这一点再对访存操作再进行优化。我们尝试加入了prefetch预取，即在读取第一个哈希函数对应的block之前，计算第二个哈希函数对应的block号，并利用__builtin_prefetch()语句显式的预取第二行的内容到Cache。经过多轮实验，最终确定的（在高容积率下）性能最优的执行顺序如下:

   1. 计算哈希、取模，得到第1个block的位置
   2. 预取第1个block
   3. 计算哈希、取模，得到第2个block的位置
   4. 预取第2个block
   5. 查询第1个block
   6. 查询第2个block

本实验依然在“100,000,000个桶，90,000,000个(k, v)对”的条件下进行，可以看出32位取模对性能有约15%的影响，预取在这一基础上，又对总性能有约20%的提升。图中prefetch1是仅预取第2个block的另一种写法，prefetch2对应上述的执行顺序。由于低容积率下绝大多数时候不需要遍历第二个block，这种方式实际上是略微牺牲了低容积率下的性能的。但是，对于高容积率的情况，不命中时有约74%的会查到第2个block，因此性能有大幅提高。命中时虽然仅有23%的查询会访问第二个block，但是基于以下几点原因，性能同样得到了提高。

• 优化之前，我们已知23%的操作访问了第2个block，却占用了总时间的50%。
• 应用32位取模后，多余的取模操作造成的负面影响已经被大幅减小。
• 现代CPU都是超标量、流水线、多核处理器，以开发机的Intel Haswell处理器为例，它的每个核心中都有6个可以同时发射指令的port（6条超标量流水线），Skylake则有8个，每个核心中有一个scheduler决定将指令发射到哪个端口，优化前，VTune数据显示我们对port的利用不佳，大多数时候都只能用到其中1个port。优化后，预取操作虽然属于访存操作，需要花费较多的时钟周期，但它只需要占用6个中的1个支持内存load的port（并非6个port都支持内存load的操作）。这就意味着，在进行预取的同时，其余的port上仍然可以进行计算、比较等指令，比如，预取第1个block和计算第2个哈希可以在不同port上并行，预取第2个block和查询第1个block也应当可以并行。

总结

在应用了这两项优化之后，重新进行Cuckoo和Dense的性能对比，可以明显地看到Cuckoo性能的提升，我们的优化有不错的效果。现在基本可以认为，在80%的容积率时，Cuckoo的整体查询性能已经超过了Dense。（不命中的场景QPS达到了Dense的两倍，命中时以约5%的差距稍稍落后于Dense。）

几点以后需要注意的地方：

1. Intel Vtune的数据，未必会将CPI的统计与汇编指令一一对应，在我们的测试中，会将连续几条的累积（包括取模、访存）计在一条cmp指令上。
2. 64位取模和32位取模的耗时的巨大差异需要留意，最好使用32位取模，条件允许的情况下将除数设为2的幂，用位运算进行取模。
3. 对一些有规律，并且计算、访存交替进行的操作，可以通过预取来提升性能，让访存和计算并行起来。