Cuckoo Filter详解

Contents
  1. BloomFilter的缺陷
  2. Cuckoo Filter
    1. Cuckoo Hash Tables
    2. Cuckoo Filter算法
      1. 插入
      2. 查找
      3. 删除
  3. 总结

对于海量数据处理业务,我们通常需要一个索引数据结构,用来帮助查询,快速判断数据记录是否存在,这种数据结构通常又叫过滤器(filter)。考虑这样一个场景,上网的时候需要在浏览器上输入URL,这时浏览器需要去判断这是否一个恶意的网站,它将对本地缓存的成千上万的URL索引进行过滤,如果不存在,就放行,如果(可能)存在,则向远程服务端发起验证请求,并回馈客户端给出警告。

BloomFilter的缺陷

时下一个非常流行的哈希索引结构就是bloom filter,它类似于bitmap这样的hashset,所以空间利用率很高。其独特的地方在于它使用多个哈希函数来避免哈希碰撞,如图所示(来源wikipedia),bit数组初始化为全0,插入x时,x被3个哈希函数分别映射到3个不同的bit位上并置1,查询x时,只有被这3个函数映射到的bit位全部是1才能说明x可能存在,但凡至少出现一个0表示x肯定不存在。

bloomFilterWorkflow

但是,bloom filter的这种位图模式带来两个问题:一个是误报(false positives),在查询时能提供“一定不存在”,但只能提供“可能存在”,因为存在其它元素被映射到部分相同bit位上,导致该位置1,那么一个不存在的元素可能会被误报成存在;另一个是漏报(false nagatives),同样道理,如果删除了某个元素,导致该映射bit位被置0,那么本来存在的元素会被漏报成不存在。由于后者问题严重得多,所以bloom filter必须确保“definitely no”从而容忍“probably yes”,不允许元素的删除。

关于元素删除的问题,一个改良方案是对bloom filter引入计数(Counting Bloom filters),但这样一来,原来每个bit空间就要扩张成一个计数值,空间效率上又降低了。

Cuckoo Filter

为了解决这一问题,本文引入了一种新的哈希算法 —— cuckoo filter,它既可以确保该元素存在的必然性,又可以在不违背此前提下删除任意元素,仅仅比bitmap牺牲了微量空间效率。

Cuckoo Hash Tables

我们先来看看cuckoo hashing有什么特点,它的哈希函数是成对的(具体的实现可以根据需求设计),每一个元素都是两个,分别映射到两个位置,一个是记录的位置,另一个是备用位置。这个备用位置是处理碰撞时用的,这就要说到cuckoo这个名词的典故了,中文名叫布谷鸟,这种鸟有一种即狡猾又贪婪的习性,它不肯自己筑巢,而是把蛋下到别的鸟巢里,而且它的幼鸟又会比别的鸟早出生,布谷幼鸟天生有一种残忍的动作,幼鸟会拼命把未出生的其它鸟蛋挤出窝巢,今后以便独享“养父母”的食物。借助生物学上这一典故,cuckoo hashing处理碰撞的方法,就是把原来占用位置的这个元素踢走,不过被踢出去的元素还要比鸟蛋幸运,因为它还有一个备用位置可以安置,如果备用位置上还有人,再把它踢走,如此往复。直到被踢的次数达到一个上限,才确认哈希表已满,并执行rehash操作。

cuckooPreview

我们不禁要问发生哈希碰撞之前的空间利用率是多少呢?不幸地告诉你,一维数组的哈希表上跟其它哈希函数没什么区别,也就50%而已。但如果是二维的呢?

一个改进的哈希表如下图所示,每个桶(bucket)有4路槽位(slot)。当哈希函数映射到同一个bucket中,在其它三路slot未被填满之前,是不会有元素被踢的,这大大缓冲了碰撞的几率。笔者自己的简单实现上测过,采用二维哈希表(4路slot)大约80%的占用率(CMU论文数据据说达到90%以上,应该是扩大了slot关联数目所致)。

cuckooHashing

如上图所示,(a) 表示插入元素x之前已经存在的元素a, b, c。通过计算x的两个可用位置分别被a, b占用了,随机选择一个位置,也就是元素a存放的位置。然后元素a被迁移到它的备用位置,也就是元素c现在的位置。类似的c再做迁移。(c) 表示Cuckoo Hash的一种实现,每个bucket有四个slot。对于 (a) 的情形,则直接把x插入到元素a或b所在的bucket的空的slot里面即可。

Cuckoo Filter是Cuckoo Hash的一种更节省空间的变体,它在bucket中存放的不是元素本身,而是 fingerprint(x) 值,也是类似于一种哈希值。

Cuckoo Filter算法

Cuckoo Hash Table的基本单元叫做entry,每个entry存储一个fingerprint。Hash Table由多个bucket组成,每个bucket有多个entry。

插入

假设对于x的两个可用位置为i1, i2。当出现x需要迁移的时候,我们怎么得到它的另一个位置呢?因为bucket里面存放的是f = fingerprint值,所以i1,i2不能简单的通过两个哈希函数计算得到。这里使用异或运算达到i1,i2可以互相转化的目的。具体算法如下:

cuckooFilterInsert

另外在我们为元素再分配地址(下面简称reallocate)的时候,如果一直找不到空闲的位置(比如x, y 的两个可用位置i1, i2完全相同),或者可以找到但是需要的时间出于性能方面的考虑不能忍受,这个时候就需要我们做一个限制,比如设置一个最大的reallocate的次数。

查找

查找很简单,但是需要注意的是存在误判的。

cuckooFilterLookUp

删除

删除也是删除的元素fingerprint值,存在误删的情况。

cuckooFilterDelete

总结

Cuckoo Filter的优点是不言而喻的:

  • 支持动态的插入、删除操作
  • 整个数据结构接近满的时候,Cuckoo Filter具有更佳的查找性能(95%的空间利用率)
  • 容易实现
  • False Positive Rate比Bloom Filter更小,并且具有更高的空间利用率

同其他的filter比较:

filterType

但Cuckoo Filter还是有一些缺点:

  • 由于进行XOR运算,使得Filter的个数必须为2的整数次幂
  • 储存fingerprint在filter内当做特征值,虽然有一定好处,但是也存在碰撞机会而造成false positive