Bloom Filter 的后继者？布谷鸟哈希与布谷鸟过滤器

引子

之前我们聊过 LevelDB 中的布隆过滤器，它利用一组哈希函数和一块内存可以表示一个数据集，并支持对集合中数据条目的有无进行快速查询。它虽有一定误报率，但是只使用相当小的内存，因此在特定场景下特别好用。不过它有一个显著的缺陷——不支持删除。本文我们介绍一种新的数据结构：布谷鸟过滤器，在紧凑的使用内存同时，支持删除。本着刨根问底的精神，我们从最基础的哈希说起。

哈希的本质是从一个较大空间映射到一个较小的空间，因此在插入数据足够多之后，根据鸽巢原理，一定会存在位置冲突。常见的哈希表（Hash Table 或者字典，dictionary）会通过链表、开放地址探测等方式来处理冲突。单桶多函数的布谷鸟哈希，便是开放地址法处理冲突的一种哈希表，只不过有冲突后，不是通过线性寻找新的位置，而是通过额外哈希函数来寻找。

作者：木鸟杂记 https://www.qtmuniao.com/2021/12/07/cuckoo-hash-and-cuckoo-filter, 转载请注明出处

原理

布谷鸟哈希最早是Rasmus Pagh 和 Flemming Friche Rodler 在 2001 年一次会议上公开的[1]。其基本思想为：

1. 使用两个哈希函数 h1(x) 、 h2(x) 和两个哈希桶 T1、T2 。
2. 插入元素 x：
   1. 如果 T1[h1(x)] 、T2[h2(x)] 有一个为空，则插入；两者都空，随便选一个插入。
   2. 如果 T1[h1(x)] 、T2[h2(x)] 都满，则随便选择其中一个（设为 y ），将其踢出，插入 x。
   3. 重复上述过程，插入元素 y。
   4. 如果插入时，踢出次数过多，则说明哈希桶满了。则进行扩容、ReHash 后，再次插入。
3. 查询元素 x：
   1. 读取 T1[h1(x)] 、T2[h2(x)] 和 x 比对即可

cuckoo hash insert example

布谷鸟（Cuckoo），即大杜鹃，喜欢在别的鸟窝里产蛋。布谷鸟幼鸟出生后，会将其他蛋踢出，借巢长大。布谷鸟哈希的关键设计正在于“踢出”（kicks out）这个动作，该设计和名字都堪称神来之笔。

变种

布谷鸟哈希可以有很多变种，比如：

1. 使用两个哈希函数和一个哈希桶。
2. 使用两个哈希函数和四路哈希桶。

cuckoo hash variant

可以证明，后者的桶的利用率会更高，感兴趣可以去看原论文[3]查看论证过程。

应用

cmu 大学的 Bin Fan 等人，在 2014 年发表了一篇名为：Cuckoo Filter: Practically Better Than Bloom [3] 的论文，基本思想是将布谷鸟哈希（key-value queries）的思想应用于集合（set membership）方向，可以替代工程中常用的 Bloom Filter，有以下优势：

1. 支持删除元素
2. 更高的查询效率，尤其在高负载因子时
3. 相比其他支持删除的 Filter 更容易实现
4. 如果期望误报率在 3% 以下，所用空间比 Bloom Filter 少

为了达到以上效果，Cuckoo Filter 对原 Cuckoo Hash 做了如下改变：

1. 为了提高桶的利用率，使用多路哈希桶。
2. 为了减少内存的使用，只存储 key 指纹。

此外，当某个值 x 被踢出时，需要找到另外一个位置。Cuckoo Hash 是通过额外哈希函数作用于 x 计算而出：h2(x)。但在 Cuckoo Filter 中为了节省内存，保存的是定长的指纹 finger(x)而非原值 x。当 x 被踢出时，如何找到其另外一个位置？直观的，我有两种想法：

方法一：通过 h2(finger(x)) 计算出另外一个位置。但这样在计算第二个位置时，相当于将原数据空间强行压缩到了指纹空间，会损失很多信息，加大碰撞概率。

方法二：在值中记下另外一个位置， pair(finger, the other position)，但这样空间占用会大大增加。

Cuckoo Filter 用了一个巧妙地做法，将位置（h1(x)）和对应值的哈希（hash(finger(x))）进行异或得到另外一个位置。我们知道，异或运算满足性质：三值中的任意两值异或都能得到第三值。在另一个位置 x 被踢出时，也能通过同样的方法得到原位置，如下图所示。

xor position and val

为什么不直接和finger(x)进行异或计算另外位置呢？因为 finger(x) 一般位数比较少，比如 8 bit。如果按照这种方法，从物理意义上理解，即是在原位置±2^8 = 256 的范围内找到另一个位置，因为异或只会改变低 8 bit 的值。这个范围太小了，不利于均衡散列。

另外有两点需要注意。一是不借助额外信息， Cuckoo Filter 是不能扩容的，因为我们已经丢失了原值 x，则无法计算扩容后新的位置 hash(x)。当然，如果保存有相应的 key 集合，也可以扩容后，将原来的 key 集合重新插入一遍。二是，如果两个不同值 x 和 y，恰巧满足 hash(x) == hash(y) && finger(x) == finger(y) 则会出现假阳性。理解假阳性，我们可以从哈希的本质出发。如开篇所述，哈希本质是从大空间映射到小空间，则小空间中一定会出现碰撞，出现碰撞的两个原值一个存在，便会让人以为另一个也存在。回到 Cuckoo Filter 上，如果 x 和 y 都存在于 Cuckoo Filter 中，删除 x 或者 y 时，删除两个相同 finger 中的任何一个即可。

实现

布谷鸟过滤器的实现很简单， 论文中也给出了伪代码，贴在这里。

插入 Insert(x)

f = fingerprint(x);
i1 = hash(x);
i2 = i1 ⊕ hash(f);
if bucket[i1] or bucket[i2] has an empty entry then
 add f to that bucket;
 return Done;

// must relocate existing items;
i = randomly pick i1 or i2;
for n = 0; n < MaxNumKicks; n++ do
 randomly select an entry e from bucket[i];
 swap f and the fingerprint stored in entry e;
 i = i ⊕ hash(f);
 if bucket[i] has an empty entry then
  add f to bucket[i];
  return Done;

// Hashtable is considered full;
return Failure;

查找 Lookup(x)

f = fingerprint(x);
i1 = hash(x);
i2 = i1 ⊕ hash(f);
if bucket[i1] or bucket[i2] has f then
 return True;
return False;

删除 Delete(x)

f = fingerprint(x);
i1 = hash(x);
i2 = i1 ⊕ hash(f);
if bucket[i1] or bucket[i2] has f then
 remove a copy of f from this bucket;
 return True;
return False;

参考

布谷鸟哈希和布谷鸟过滤器

1. 布谷鸟哈希：https://www.itu.dk/people/pagh/papers/cuckoo-jour.pdf
2. 布谷鸟哈希维基百科：https://en.wikipedia.org/wiki/Cuckoo_hashing#cite_note-Cuckoo-1
3. 布谷鸟过滤器 Cuckoo Filter: Practically Better Than Bloom https://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf
4. 布谷鸟过滤器实现：[https://coolshell.cn/articles/17225.html]