用于并发读密集型的乐观Cuckoo(布谷鸟) Hashing

用于并发读密集型的乐观Cuckoo(布谷鸟) Hashing：Optimistic Cuckoo Hashing for concurrent, read-intensive applications一文探索的是针对高并发读，只有一个线程写的应用场景下，如何最大限度提高诸如memcached之类缓存的吞吐量。

作者介绍了他们使用了一个新的哈希算法，适合多个读，单个写并发，称为Cuckoo布谷鸟 hashing。因为是主要面向读操作，所以称之为乐观的(相对于悲观锁而言)。在其中引入了SILT ("partial-key cuckoo hashing")新的方法：当新的数据插入时如何移动其中数据，这样它同时支持很高吞吐量的读操作，同时允许一个线程以很高频率和速度不断更新哈希中的数据(测试: 2M updates/second ).

优点：
1. 快速并发读高吞吐量Fast concurrent read throughput (no mutex required)

2.拿得出手的写吞吐量 write throughput (each update requires acquiring a mutex)

3.非常高的内存效率，尤其对于小的key/value pairs
可预测和快速的读取性能：每读正好有两个内存引用references.

缺陷:
1.哈希表大小不能动态变化，如果满了，得摧毁旧的创建新的更大的，将旧的再导入新的。
2.对于写操作很多(write-heavy (>50%) workloads. )的应用会比较慢

相对于传统的Linear Probing 和Chaining算法，布谷鸟算法非常类似布谷鸟叫声，叫两声。布谷鸟算法的数据结构是假定一个槽slot里有几个bucket桶，有两个key：2,4表示(k=2 slots, b=4 buckets)。

当搜索一个布谷鸟哈希时，将在两个槽中寻找，s1 = h1(key), s2=h2(key)，看看这两个槽中是否有要找的数据，如没有返回失败。


find(key):
   foreach slot s in (s1, s2):
      foreach bucket b in s:
          if b.key == key:
              return true, b.value
   return false, nil

更多理解可见英文原文。