Go语言实现布谷鸟过滤器的方法_Golang

转载请声明出处哦~，本篇文章发布于luozhiyun的博客： https://www.luozhiyun.com/archives/453

介绍

在我们工作中，如果遇到如网页 url 去重、垃圾邮件识别、大集合中重复元素的判断一般想到的是将集合中所有元素保存起来，然后通过比较确定。如果通过性能最好的hash表来进行判断，那么随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。

所以很多时候会选择使用布隆过滤器来做这件事。布隆过滤器通过一个固定大小的二进制向量或者位图（bitmap），然后通过映射函数来将存储到 bitmap 中的键值进行映射大大减少了空间成本，布隆过滤器存储空间和插入/查询时间都是常数 o(k)。但是随着存入的元素数量增加，布隆过滤器误算率会随之增加，并且也不能删除元素。

想要体验布隆过滤器的插入步骤的可以看看这里： https://www.jasondavies.com/bloomfilter/

于是布谷鸟过滤器(cuckoo filter)华丽降世了。在论文《cuckoo filter: practically better than bloom》中直接说到布隆过滤器的缺点：

a limitation of standard bloom filters is that one cannot remove existing items without rebuilding the entire filter.

论文中也提到了布谷鸟过滤器4大优点：

it supports adding and removing items dynamically;
it provides higher lookup performance than traditional bloom filters, even when close to full (e.g., 95% space utilized);
it is easier to implement than alternatives such as the quotient filter; and
it uses less space than bloom filters in many practical applications, if the target false positive rate is less than 3%.

翻译如下：

支持动态的新增和删除元素；
提供了比传统布隆过滤器更高的查找性能，即使在接近满的情况下（比如空间利用率达到 95% 的时候）；
更容易实现；
如果要求错误率小于3%，那么在许多实际应用中，它比布隆过滤器占用的空间更小

实现原理

简单工作原理

可以简单的把布谷鸟过滤器里面有两个 hash 表t1、t2，两个 hash 表对应两个 hash 函数h1、h2。

具体的插入步骤如下：

当一个不存在的元素插入的时候，会先根据 h1 计算出其在 t1 表的位置，如果该位置为空则可以放进去。
如果该位置不为空，则根据 h2 计算出其在 t2 表的位置，如果该位置为空则可以放进去。
如果t1 表和 t2 表的位置元素都不为空，那么就随机的选择一个 hash 表将其元素踢出。
被踢出的元素会循环的去找自己的另一个位置，如果被暂了也会随机选择一个将其踢出，被踢出的元素又会循环找位置；
如果出现循环踢出导致放不进元素的情况，那么会设置一个阈值，超出了某个阈值，就认为这个 hash 表已经几乎满了，这时候就需要对它进行扩容，重新放置所有元素。

下面举一个例子来说明：

Go语言实现布谷鸟过滤器的方法

如果想要插入一个元素z到过滤器里：

首先会将z进行 hash 计算，发现 t1 和 t2 对应的槽位1和槽位2都已经被占了；
随机将 t1 中的槽位1中的元素 x 踢出，x 的 t2 对应的槽位4已经被元素 3 占了；
将 t2 中的槽位4中的元素 3 踢出，元素 3 在 hash 计算之后发现 t1 的槽位6是空的，那么将元素3放入到 t1 的槽位6中。

当 z 插入完毕之后如下：

Go语言实现布谷鸟过滤器的方法

布谷鸟过滤器

布谷鸟过滤器和上面的实现原理结构是差不多的，不同的是上面的数组结构会存储整个元素，而布谷鸟过滤器中只会存储元素的几个 bit ，称作指纹信息。这里是牺牲了数据的精确性换取了空间效率。

上面的实现方案中，hash 表中每个槽位只能存放一个元素，空间利用率只有50%，而在布谷鸟过滤器中每个槽位可以存放多个元素，从一维变成了二维。论文中表示：

with k = 2 hash functions, the load factor α is 50% when the bucket size b = 1 (i.e., the hash table is directly mapped), but increases to 84%, 95% or 98% respectively using bucket size b = 2, 4 or 8.

也就是当有两个 hash 函数的时候，使用一维数组空间利用率只有50%，当每个槽位可以存放2，4，8个元素的时候，空间利用率就会飙升到 84%，95%，98%。

如下图，表示的是一个二维数组，每个槽位可以存放 4 个元素，和上面的实现有所不同的是，没有采用两个数组来存放，而是只用了一个：

Go语言实现布谷鸟过滤器的方法

说完了数据结构的改变，下面再说说位置计算的改变。

我们在上面简单实现的位置计算公式是这样做的：

而布谷鸟过滤器计算位置公式可以在论文中看到是这样：

我们可以看到在计算位置 i2 的时候是通过 i1 和元素 x 对应的指纹信息取异或计算出来。指纹信息在上面已经解释过了，是元素 x 的几个 bit ，牺牲了一定精度，但是换取了空间。

那么这里为什么需要用到异或呢？因为这样可以用到异或的自反性： a ⊕ b ⊕ b = a ，这样就不需要知道当前的位置是 i1 还是 i2，只需要将当前的位置和 hash(f) 进行异或计算就可以得到另一个位置。

这里有个细节需要注意的是，计算 i2 的时候是需要先将元素 x 的 fingerprint 进行 hash ，然后才取异或，论文也说明了：

if the alternate location were calculated by “i⊕fingerprint” without hashing the fingerprint, the items kicked out from nearby buckets would land close to each other in the table, if the size of the fingerprint is small compared to the table size.

如果直接进行异或处理，那么很可能 i1 和 i2 的位置相隔很近，尤其是在比较小的 hash 表中，这样无形之中增加了碰撞的概率。

除此之外还有一个约束条件是布谷鸟过滤器强制数组的长度必须是 2 的指数，所以在布谷鸟过滤器中不需要对数组的长度取模，取而代之的是取 hash 值的最后 n 位。

如一个布谷鸟过滤器中数组的长度2^8即256，那么取 hash 值的最后 n 位即： hash & 255 这样就可以得到最终的位置信息。如下最后得到位置信息是 23 ：

Go语言实现布谷鸟过滤器的方法

代码实现

数据结构

在这里我们假定一个指纹 fingerprint 占用的字节数是 1byte ，每个位置有 4 个座位。

初始化

这个 init 函数会缓存初始化两个全局变量 althash 和 masks。因为 fingerprint 长度是 1byte ，所以在初始化 althash 的时候使用一个 256 大小的数组取缓存对应的 hash 信息，避免每次都需要重新计算；masks 是用来取 hash 值的最后 n 位，稍后会用到。

我们会使用一个 newfilter 函数，通过传入过滤器可容纳大小来获取过滤器 filter：

newfilter 函数会通过 getnextpow2 将 capacity 调整到 2 的指数倍，如果传入的 capacity 是 9 ，那么调用 getnextpow2 后会返回 16；然后计算好 buckets 数组长度，实例化 filter 返回；bucketpow 返回的是二进制中以 0 结尾的个数，因为 capacity 是 2 的指数倍，所以 bucketpow 是 capacity 二进制的位数减 1。

插入元素

getindexandfingerprint 函数会获取 data 的指纹 fingerprint，以及位置 i1；
然后调用 insert 插入到 filter 的 buckets 数组中，如果 buckets 数组中对应的槽位 i1 的 4 个元素已经满了，那么尝试获取位置 i2 ，并将元素尝试插入到 buckets 数组中对应的槽位 i2 中；
对应的槽位 i2 也满了，那么调用 reinsert 方法随机获取槽位 i1、i2 中的某个位置进行抢占，然后将老元素踢出并循环重复插入。

下面看看 getindexandfingerprint 是如何获取 fingerprint 以及槽位 i1：

getindexandfingerprint 中对 data 进行 hash 完后会对其结果取模获取指纹信息，然后再取 hash 值的高 32 位进行取与，获取槽位 i1。masks 在初始化的时候已经看过了， masks[bucketpow] 获取的二进制结果全是 1 ，用来取 hash 的低位的值。

假如初始化传入的 capacity 是1024，那么计算到 bucketpow 是 8，对应取到 masks[8] = (1 << 8) - 1 结果是 255 ，二进制是 1111，1111 ，和 hash 的高 32 取与得到最后 buckets 中的槽位 i1 ：

Go语言实现布谷鸟过滤器的方法

getaltindex 中获取槽位是通过使用 althash 来获取指纹信息的 hash 值，然后取异或后返回槽位值。需要注意的是，这里由于异或的特性，所以传入的不管是槽位 i1，还是槽位 i2 都可以返回对应的另一个槽位。

下面看看循环踢出插入 reinsert：

这里会最大循环 500 次获取槽位信息。因为每个槽位最多可以存放 4 个元素，所以使用 rand 随机从 4 个位置中取一个元素踢出，然后将当次循环的元素插入，再获取被踢出元素的另一个槽位信息，再调用 insert 进行插入。

Go语言实现布谷鸟过滤器的方法