两次访存 · 踢出链 · 相变 0.5

cuckoo hashing：只给两处候选

前面几种方案的查找代价都是负载因子的函数——链地址法是 $\alpha$ ，开放寻址是 $1/(1-\alpha)$ 那一族，Swiss table 是扫过的组数。cuckoo hashing 换了个约束方向：给每个 key 只留两处候选。它要么在第一处，要么在第二处，没有第三种可能。

于是查找的代价被钉死了：最多两次访存，与表有多满无关。这个确定性对尾延迟敏感的系统很值钱，MemC3 把它用进 memcached 正是为此。代价全部转移到了插入那一侧。

1 · 占了就把原住户踢走

插入时先看第一处候选。空着就放进去，结束。被占了，就把新 key 放进去、把原住户踢出来，再送它去它的另一处候选；那里若也被占，接着踢。

定义 1.1（cuckoo 插入） 两个独立散列 $h_1, h_2$ 。插入 $k$ 时置 $x \gets k$ 、 $i \gets 1$ ，循环：把 $x$ 写进表 $i$ 的 $h_i(x)$ 号槽；若该槽原本为空则结束，否则把被换出的 key 记为新的 $x$ 、 $i$ 换成另一张表，继续。循环次数超过上限则判定成环，插入失败。

名字取自 cuckoo 的巢寄生行为——把别人的蛋推出巢外，自己占据。

图 1-1 · 两张各 11 槽的表逐个装入 key。格下数字是本次踢出链的第几步，蓝框是查找时检查的两个候选槽。可逐个插入，也可点击任一 key 观察查找恒为两次访存。

查找与删除都因此变得极简单：算两个下标，看这两个槽，完事。删除甚至不需要墓碑——每个 key 的位置由它自己的两个散列值唯一确定，删掉它不会影响任何其他 key 的可达性。这是 cuckoo hashing 相对开放寻址的一项干净优势。

2 · 0.5 是一堵墙

插入失败怎么办？直觉的答案是「多踢几次」。实测表明这个方向几乎无效。

图 2-1 · 踢出预算从 4 提到 500 时能装到的最高负载，虚线是理论相变点 0.5。下方另有装填过程中平均踢出次数随负载的变化。可改每表槽数。

每表 512 槽（共 1024 槽）的实测：

maxKicks	装入	负载因子
4	226	0.221
8	386	0.377
16	515	0.503
32	515	0.503
64	534	0.521
500	534	0.521

预算从 16 提到 500 涨了三十倍，负载只从 0.503 挪到 0.521。这不是调参没调好，是一堵理论的墙。

把 key 看作边、槽位看作顶点，每个 key 连接它的两个候选槽——插入全部成功等价于这张图的每条边都能定向到一个专属顶点，也就是每个连通分量里边数不超过顶点数。随机图论的经典结果是：当边数与顶点数之比越过 $1/2$ 时，随机图几乎必然出现含两个以上环的分量，此时抽屉原理下无解。0.5 是相变点，不是工程上限。图 1-1 里插入失败时表内往往还剩不少空槽，说明装不下与「有没有地方」无关，只与候选位置的锁死结构有关。

踢出的代价分布也值得看：median 是 1（即绝大多数插入根本不踢），p99 是 12，最长 34。前一半插入的平均踢出次数是 1.31，后一半 2.48。代价高度集中在逼近相变点的最后那一段。

3 · 把墙推高的三种改法

0.5 太低，实用实现都会改。三条路各自动一个参数。

加候选数。用 $d$ 个散列而非 2 个，相变点随 $d$ 上升： $d = 3$ 约 0.918， $d = 4$ 约 0.977。代价是查找从两次访存变成 $d$ 次。

加桶容量。每个候选位置不只装一个 key，而是一个能装 $b$ 个 key 的桶（一个 cache line 正好装几个）。 $d = 2$ 、 $b = 4$ 的相变点约 0.98，而查找仍是两次访存——只是每次带回一整个 cache line。这条路性价比最高，MemC3 与 cuckoo filter 都走它。

加一个小暂存区。留一个能装几个 key 的 stash，踢出成环时把当前那个 key 丢进 stash。stash 只有常数大小，查找时线性扫一遍即可。它能显著降低「因为一个倒霉的环就要重建整张表」的概率。

4 · 并发读为什么反而容易

cuckoo hashing 有一个不显眼的性质：踢出过程只搬动 key，从不改变任何 key 的候选集合。这让并发读取的设计变得简单——读者只需要检查两个固定的槽位。

麻烦在于搬动的瞬间：一个 key 从表 0 的槽 $a$ 搬到表 1 的槽 $b$ ，若读者恰好在「已从 $a$ 移走、尚未写入 $b$ 」这一刻查两个槽，会得到「不存在」这个错误答案。MemC3 的解法是给每个 key 配一个版本号计数器，写者搬动前后各加一次（奇数表示正在改），读者读完两个槽后校验版本号没变过——这就是乐观并发控制里的 optimistic lock striping。

更彻底的做法是先探路再搬：插入时不立即写，而是先在「候选槽」的图上搜出一条通向空槽的完整踢出路径，然后从路径末端往回搬。这样每一步都是「把 key 搬进一个确认为空的槽」，任何时刻每个 key 都恰好存在于某一处，读者不会看到空窗。代价是要先做一次广度优先搜索。

5 · 参考文献

Pagh, R., & Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2), 122–144.
Fan, B., Andersen, D. G., & Kaminsky, M. (2013). MemC3: compact and concurrent MemCache with dumber caching and smarter hashing. NSDI 2013, 371–384.
Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014). Cuckoo filter: practically better than Bloom. CoNEXT 2014, 75–88.
Dietzfelbinger, M., & Weidling, C. (2007). Balanced allocation and dictionaries with tightly packed constant size bins. Theoretical Computer Science, 380(1–2), 47–68.