本文简要阐述libcuckoo项目的两篇论文基础。如有错漏之处，欢迎指出一起讨论交流。

论文1

《MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing》
这篇论文主要讲了在多线程模式下如何提升cuckoo hash table的吞吐。

问题

传统hash表在并发效率上并不高，使用链表解决哈希冲突效率低，使用分shard的模式并不能提升热点负载。

改进一：Tag-based Lookup/Insert

kv不存储在hash表中，hash表的每个slot只存储 对这个key的 tag 和真实存储这个key的指针。如此一次可读取单个bucket内的所有slot信息，对cache line也十分友好。

查找过程优先比较tag，tag命中后再全比较key。
同时提供了 主bucket id和备 bucket id的函数公式计算，可通过tag加其中一个主bucket id推算出备bucket id。方便查找移动合适的bucket。

改进二：Concurrent Cuckoo Hashing

通过DFS算法找到key 迁移bucket的路线图，查找过程非互斥，找到之后再尝试从最后的key开始往前挪动，挪动的过程才是互斥的行为。可以查找多条路径，找到最优的路径移动bucket。

每个bucket有对应的一个原子版本号，对应这个bucket下的所有slot，本质上是lock striping。虽然粒度粗了，但是和每个slot都有版本号相比，减少了内存消耗。
在此基础上实现了乐观锁，每个insert之前先对版本号+1，完成之后再对版本号+1。每个读操作之前先读取版本号，如果是奇数，说明有insert正在进行，放弃重试。如果是偶数，再读取之后再重新获取一下版本号，如果版本号已经发生了改变，放弃重新获取。

改进三：Clock LRU

传统的LRU算法会使用双向链表来实现，通过移动链表来计算出最近访问的key。这种方法空间利用率低。
使用一个环形的bit数据结构来替换双向链表。每个bit代表了slot的位置，当有insert/update发生时，这个slot的bit被置为1。有个独立的evict扫描器，从环形bit开始扫描，遇到为1的置为0，继续向前扫描，遇到0的则将对应的slot的数据设置为需要淘汰。淘汰的过程中也使用上述的乐观锁，与insert/update一致，避免脏读。

论文2

《Algorithmic Improvements for Fast Concurrent Cuckoo Hashing》
这篇论文是基于上一篇论文提出的进一步优化提高吞吐量。其中关于HTM部分的优化本文略过。

改进一：BFS

将DFS 路径查找改成BFS，尽量找到最短的路径。

论文测试出最适合的单个bucket最适合的slot个数是8，
论文在读和写吞吐的平衡中找到最合适的桶深度为8，8个slot会超过一个cache line，论文认为可一次读取两个cache line，经实践是最优配置。

改进二：Fine-grained Locking

论文1中当需要挪动bucket时，对路径图中key的bucket都提前加上了锁，锁的力度太大。同时读的时候如果发生更改，每次都需要重试，很容易发生了活锁。
由此论文2提出更细粒度的锁，使用spinlock替换版本号实现lock-striped。对于cuckoo hash来说，无论如何移动bucket，最终数据的操作粒度在主备bucket之中操作，所以在lookup/insert过程中，都细粒度到只是对两个bucket的操作，每次都是获取两个bucket的锁。

结束语

云数据库Redis版（ApsaraDB for Redis）是一种稳定可靠、性能卓越、可弹性伸缩的数据库服务。基于飞天分布式系统和全SSD盘高性能存储，支持主备版和集群版两套高可用架构。提供了全套的容灾切换、故障迁移、在线扩容、性能优化的数据库解决方案。欢迎各位购买使用：阿里云redis