木鸟杂记

分布式系统，数据库，存储

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

发表于 更新于 分类于 ，

引子

哈希的本质是从一个较大空间映射到一个较小的空间，因此在插入数据足够多之后，根据鸽巢原理，一定会存在位置冲突。常见的哈希表（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-insert.png

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

变种

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

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

cuckoo-hash.png

可以证明，后者的桶的利用率会更高，感兴趣可以去看原论文[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-val.png

为什么不直接和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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)

1
2
3
4
5
6
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)

1
2
3
4
5
6
7
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]

我是青藤木鸟，一个喜欢摄影、专注大规模数据系统的程序员，欢迎关注我的公众号：“木鸟杂记”，有更多的分布式系统、存储和数据库相关的文章，欢迎关注。 关注公众号后，回复“资料”可以获取我总结一份分布式数据库学习资料。 回复“优惠券”可以获取我的大规模数据系统付费专栏《系统日知录》的八折优惠券。

我们还有相关的分布式系统和数据库的群，可以添加我的微信号：qtmuniao，我拉你入群。加我时记得备注：“分布式系统群”。 另外，如果你不想加群，还有一个分布式系统和数据库的论坛（点这里），欢迎来玩耍。

wx-distributed-system-s.jpg