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

13-03-12 banq
              

用于并发读密集型的乐观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
<p>

更多理解可见英文原文。

              

2
banq
2013-03-12 16:34

在dual CPU Xeon L5640 (2.27GHz, 6 cores each)千万级数据测试结果:

C代码已经在GitHub上

Java实现在这里,当它有两个缺点:小于50%的表使用量;对于读操作使用了mutex。