论文阅读笔记: Algorithmic Improvements for Fast Concurrent Cuckoo Hashing

Posted by CodingCat on January 20, 2015

这是一篇发表在EuroSys 2014的论文, 和上一篇(/blog/2015/01/19/mem3c_notes/) 阅读笔记来自于同一个组,都是CMU的david anderson的学生发的,同样也是和Intel合作,同样也是提出了一种高效的并发Cuckoo Hashing的实现。

基于上一篇的基础,这一篇就不再过多的阐述哈希表和Cuckcoo Hashing的基础知识了。这篇所做的工作其实是对他们发表在NSDI 2013的MemC3的改进: 在上一篇论文中我们提到,MemC3通过一个全局锁使得在任意时刻,哈希表都只能对唯一的writer服务从而避免了写写状态下的死锁。

这篇论文做的就是提供了一种新的cuckoo Hashing的实现能够支持多writer, 既没有死锁,又能保证较大的吞吐量。

并发哈希的实现及优化方法

细粒度锁优化

要实现一个支持并发的哈希表,最常见的方法就是锁, 锁的关键之处就是要安全,高效。这对于锁的使用其实是很有挑战性的。比如在MemC3中,只要开始写表就申请一把锁,于是将整个写操作顺序化,带来了不必要的性能开销。为了优化MemC3中粗粒度的锁使用方法,这篇论文提出的第一个优化思路就是,只有在找到了一个能够插入新元素的slot的情况下才去申请锁,这样就已经在一定程度上允许了一定的并发度(寻找cuckoo hashing path的并发). 如以下算法所示:

这个算法确实细化了锁的粒度,但是带来了一定的复杂度,这个复杂度就在于,当一个线程在不断寻找自己的cuckoo hashing path的时候,另一个线程可能修改了path上某个bucket的某个slot, 所以在第11行会有一个validate_execute,就是检查当前找到的path上是不是有被修改过的脏数据。

以上的优化方法是说减小锁的使用粒度. 那么另一个层次上的优化就是如何使得数据中的元素,尽量不去共享同一把锁。这其实就是concurrentHashMap和synchronized hashmap的区别了

本文采用的策略也很简单。给一个锁的列表,仅仅部分的bucket共享同一把锁。获得锁的顺序由bucket number决定,从而避免死锁。

缩小数据结构体积

在上述的细粒度锁优化中,能够导致validate execute返回false的就是两个写操作的cuckoo hashing path出现了交叠。换个角度说,path越长,交叠的可能性越大。因此,为了减少写操作的冲突,我们就要尽量的缩短找到的cuckoo hashing path。

这个问题其实非常好解决。跳出当前的问题,回到基本的算法题上,给你一颗二叉树,如何从根节点最快的找到离根节点最近的叶子节点 => 广度优先搜索 (BFS) 啊

那和cuckoo hashing有什么联系呢. 回顾一下标准的Cuckoo Hashing的做法: 从一个被占用的slot 去找在某一个bucket中的空slot, 直到找到为止,这是一个典型的深度优先搜索算法 (DFS), 但是从一个slot 出发到达一个空slot的路径是远远不止一条的,如下图所示

7F07BB82-13D4-42C4-869A-F25A2AF87EC6

我们讲每一个bucket当成一个节点,每一个slot当成一个边,空slot当成叶子节点。于是这个问题就转换到一个经典的并且是简单的算法问题了。

基于这种BFS的优化,因为我们已知了每一个Bucket和其他Bucket的联系关系,我们在查找cuckoo hashing path的时候还可以预取多个子节点(有关系的邻居bucket), 而不需要多次访存

提高哈希桶的组相关

这其实是MemC3里没有讨论的一点,在Cuckoo Hashing的结构中,每一个哈希桶到底该多大。假设哈希桶的长度是B,那么当B过大时,查找一个元素需要遍历2B个slot,同时写操作时为了查找元素是否已存在也会涉及同样的开销。但是合适的B值可以使得写吞吐量上升,原因是因为每一个哈希桶的体积减小,只要遍历较少的哈希桶就能够知道是否可以完整插入。这是一个简单的tradeoff, 主要还是系统调优找到合适的参数。

其他

这篇论文的另一部分是将本身的算法和Intel的硬件事务内存做比较,并且优化了lock elision的机制 (lock elision是说你在访问事务性内存失败的情况下,系统自动回退到普通的锁操作)。这部分其实是本文的败笔,整个文章被这部分内容搞的非常凌乱。应该是先写自己在事务性内存上的两次尝试,最后导出自己的方法。当然,如果那么写以现在的篇幅看可能事务性内存过长。这部分我就不细说了。

这两篇阅读笔记主要就是介绍了最近两年cuckoo hashing实现上的一些进步。下个月可能在这上面做一些工作。