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

引子

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