Go语言实现布谷鸟过滤器的方法
转载请声明出处哦~，本篇文章发布于luozhiyun的博客：https://www.luozhiyun.com/archives/453
介绍
在我们工作中，如果遇到如网页URL去重、垃圾邮件识别、大集合中重复元素的判断一般想到的是将集合中所有元素保存起来，然后通过比较确定。如果通过性能最好的Hash表来进行判断，那么随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。
所以很多时候会选择使用布隆过滤器来做这件事。布隆过滤器通过一个固定大小的二进制向量或者位图（bitmap），然后通过映射函数来将存储到bitmap中的键值进行映射大大减少了空间成本，布隆过滤器存储空间和插入/查询时间都是常数O(K)。但是随着存入的元素数量增加，布隆过滤器误算率会随之增加，并且也不能删除元素。
想要体验布隆过滤器的插入步骤的可以看看这里：https://www.jasondavies.com/bloomfilter/
于是布谷鸟过滤器(Cuckoofilter)华丽降世了。在论文《CuckooFilter:PracticallyBetterThanBloom》中直接说到布隆过滤器的缺点：
AlimitationofstandardBloomfiltersisthatonecannotremoveexistingitemswithoutrebuildingtheentirefilter.
论文中也提到了布谷鸟过滤器4大优点：
- Itsupportsaddingandremovingitemsdynamically;
- ItprovideshigherlookupperformancethantraditionalBloomfilters,evenwhenclosetofull(e.g.,95%spaceutilized);
- Itiseasiertoimplementthanalternativessuchasthequotientfilter;and
- ItuseslessspacethanBloomfiltersinmanypracticalapplications,ifthetargetfalsepositiverateislessthan3%.
翻译如下：
- 支持动态的新增和删除元素；
- 提供了比传统布隆过滤器更高的查找性能，即使在接近满的情况下（比如空间利用率达到95%的时候）；
- 更容易实现；
- 如果要求错误率小于3%，那么在许多实际应用中，它比布隆过滤器占用的空间更小
实现原理
简单工作原理
可以简单的把布谷鸟过滤器里面有两个hash表T1、T2，两个hash表对应两个hash函数H1、H2。
具体的插入步骤如下：
- 当一个不存在的元素插入的时候，会先根据H1计算出其在T1表的位置，如果该位置为空则可以放进去。
- 如果该位置不为空，则根据H2计算出其在T2表的位置，如果该位置为空则可以放进去。
- 如果T1表和T2表的位置元素都不为空，那么就随机的选择一个hash表将其元素踢出。
- 被踢出的元素会循环的去找自己的另一个位置，如果被暂了也会随机选择一个将其踢出，被踢出的元素又会循环找位置；
- 如果出现循环踢出导致放不进元素的情况，那么会设置一个阈值，超出了某个阈值，就认为这个hash表已经几乎满了，这时候就需要对它进行扩容，重新放置所有元素。
下面举一个例子来说明：
如果想要插入一个元素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插入完毕之后如下：
布谷鸟过滤器
布谷鸟过滤器和上面的实现原理结构是差不多的，不同的是上面的数组结构会存储整个元素，而布谷鸟过滤器中只会存储元素的几个bit，称作指纹信息。这里是牺牲了数据的精确性换取了空间效率。
上面的实现方案中，hash表中每个槽位只能存放一个元素，空间利用率只有50%，而在布谷鸟过滤器中每个槽位可以存放多个元素，从一维变成了二维。论文中表示：
Withk=2hashfunctions,theloadfactorαis50%whenthebucketsizeb=1(i.e.,thehashtableisdirectlymapped),butincreasesto84%,95%or98%respectivelyusingbucketsizeb=2,4or8.
也就是当有两个hash函数的时候，使用一维数组空间利用率只有50%，当每个槽位可以存放2，4，8个元素的时候，空间利用率就会飙升到84%，95%，98%。
如下图，表示的是一个二维数组，每个槽位可以存放4个元素，和上面的实现有所不同的是，没有采用两个数组来存放，而是只用了一个：
说完了数据结构的改变，下面再说说位置计算的改变。
我们在上面简单实现的位置计算公式是这样做的：
p1=hash1(x)%数组长度 p2=hash2(x)%数组长度
而布谷鸟过滤器计算位置公式可以在论文中看到是这样：
f=fingerprint(x); i1=hash(x); i2=i1⊕hash(f);
我们可以看到在计算位置i2的时候是通过i1和元素X对应的指纹信息取异或计算出来。指纹信息在上面已经解释过了，是元素X的几个bit，牺牲了一定精度，但是换取了空间。
那么这里为什么需要用到异或呢？因为这样可以用到异或的自反性：A⊕B⊕B=A，这样就不需要知道当前的位置是i1还是i2，只需要将当前的位置和hash(f)进行异或计算就可以得到另一个位置。
这里有个细节需要注意的是，计算i2的时候是需要先将元素X的fingerprint进行hash，然后才取异或，论文也说明了：
Ifthealternatelocationwerecalculatedby“i⊕fingerprint”withouthashingthefingerprint,theitemskickedoutfromnearbybucketswouldlandclosetoeachotherinthetable,ifthesizeofthefingerprintissmallcomparedtothetablesize.
如果直接进行异或处理，那么很可能i1和i2的位置相隔很近，尤其是在比较小的hash表中，这样无形之中增加了碰撞的概率。
除此之外还有一个约束条件是布谷鸟过滤器强制数组的长度必须是2的指数，所以在布谷鸟过滤器中不需要对数组的长度取模，取而代之的是取hash值的最后n位。
如一个布谷鸟过滤器中数组的长度2^8即256，那么取hash值的最后n位即：hash&255这样就可以得到最终的位置信息。如下最后得到位置信息是23：
代码实现
数据结构
constbucketSize=4
typefingerprintbyte
//二维数组，大小是4
typebucket[bucketSize]fingerprint
typeFilterstruct{
//一维数组
buckets[]bucket
//Filter中已插入的元素
countuint
//数组buckets长度中对应二进制包含0的个数
bucketPowuint
}
在这里我们假定一个指纹fingerprint占用的字节数是1byte，每个位置有4个座位。
初始化
var(
altHash=[256]uint{}
masks=[65]uint{}
)
funcinit(){
fori:=0;i<256;i++{
//用于缓存256个fingerprint的hash信息
altHash[i]=(uint(metro.Hash64([]byte{byte(i)},1337)))
}
fori:=uint(0);i<=64;i++{
//取hash值的最后n位
masks[i]=(1<
这个init函数会缓存初始化两个全局变量altHash和masks。因为fingerprint长度是1byte，所以在初始化altHash的时候使用一个256大小的数组取缓存对应的hash信息，避免每次都需要重新计算；masks是用来取hash值的最后n位，稍后会用到。
我们会使用一个NewFilter函数，通过传入过滤器可容纳大小来获取过滤器Filter：
funcNewFilter(capacityuint)*Filter{
//计算buckets数组大小
capacity=getNextPow2(uint64(capacity))/bucketSize
ifcapacity==0{
capacity=1
}
buckets:=make([]bucket,capacity)
return&Filter{
buckets:buckets,
count:0,
//获取buckets数组大小的二进制中以0结尾的个数
bucketPow:uint(bits.TrailingZeros(capacity)),
}
}
NewFilter函数会通过getNextPow2将capacity调整到2的指数倍，如果传入的capacity是9，那么调用getNextPow2后会返回16；然后计算好buckets数组长度，实例化Filter返回；bucketPow返回的是二进制中以0结尾的个数，因为capacity是2的指数倍，所以bucketPow是capacity二进制的位数减1。
插入元素
func(cf*Filter)Insert(data[]byte)bool{
//获取data的fingerprint以及位置i1
i1,fp:=getIndexAndFingerprint(data,cf.bucketPow)
//将fingerprint插入到Filter的buckets数组中
ifcf.insert(fp,i1){
returntrue
}
//获取位置i2
i2:=getAltIndex(fp,i1,cf.bucketPow)
//将fingerprint插入到Filter的buckets数组中
ifcf.insert(fp,i2){
returntrue
}
//插入失败，那么进行循环插入踢出元素
returncf.reinsert(fp,randi(i1,i2))
}
func(cf*Filter)insert(fpfingerprint,iuint)bool{
//获取buckets中的槽位进行插入
ifcf.buckets[i].insert(fp){
//Filter中元素个数+1
cf.count++
returntrue
}
returnfalse
}
func(b*bucket)insert(fpfingerprint)bool{
//遍历槽位的4个元素，如果为空则插入
fori,tfp:=rangeb{
iftfp==nullFp{
b[i]=fp
returntrue
}
}
returnfalse
}
- getIndexAndFingerprint函数会获取data的指纹fingerprint，以及位置i1；
- 然后调用insert插入到Filter的buckets数组中，如果buckets数组中对应的槽位i1的4个元素已经满了，那么尝试获取位置i2，并将元素尝试插入到buckets数组中对应的槽位i2中；
- 对应的槽位i2也满了，那么调用reinsert方法随机获取槽位i1、i2中的某个位置进行抢占，然后将老元素踢出并循环重复插入。
下面看看getIndexAndFingerprint是如何获取fingerprint以及槽位i1：
funcgetIndexAndFingerprint(data[]byte,bucketPowuint)(uint,fingerprint){
//将data进行hash
hash:=metro.Hash64(data,1337)
//取hash的指纹信息
fp:=getFingerprint(hash)
//取hash高32位，对hash的高32位进行取与获取槽位i1
i1:=uint(hash>>32)&masks[bucketPow]
returni1,fingerprint(fp)
}
//取hash的指纹信息
funcgetFingerprint(hashuint64)byte{
fp:=byte(hash%255+1)
returnfp
}
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：
funcgetAltIndex(fpfingerprint,iuint,bucketPowuint)uint{
mask:=masks[bucketPow]
hash:=altHash[fp]&mask
returni^hash
}
getAltIndex中获取槽位是通过使用altHash来获取指纹信息的hash值，然后取异或后返回槽位值。需要注意的是，这里由于异或的特性，所以传入的不管是槽位i1，还是槽位i2都可以返回对应的另一个槽位。
下面看看循环踢出插入reinsert：
constmaxCuckooCount=500
func(cf*Filter)reinsert(fpfingerprint,iuint)bool{
//默认循环500次
fork:=0;k
这里会最大循环500次获取槽位信息。因为每个槽位最多可以存放4个元素，所以使用rand随机从4个位置中取一个元素踢出，然后将当次循环的元素插入，再获取被踢出元素的另一个槽位信息，再调用insert进行插入。
上图展示了元素X在插入到hash表的时候，hash两次发现对应的槽位0和3都已经满了，那么随机抢占了槽位3其中一个元素，被抢占的元素重新hash之后插入到槽位5的第三个位置上。
查询数据
查询数据的时候，就是看看对应的位置上有没有对应的指纹信息：
func(cf*Filter)Lookup(data[]byte)bool{
//获取槽位i1以及指纹信息
i1,fp:=getIndexAndFingerprint(data,cf.bucketPow)
//遍历槽位中4个位置，查看有没有相同元素
ifcf.buckets[i1].getFingerprintIndex(fp)>-1{
returntrue
}
//获取另一个槽位i2
i2:=getAltIndex(fp,i1,cf.bucketPow)
//遍历槽位i2中4个位置，查看有没有相同元素
returncf.buckets[i2].getFingerprintIndex(fp)>-1
}
func(b*bucket)getFingerprintIndex(fpfingerprint)int{
fori,tfp:=rangeb{
iftfp==fp{
returni
}
}
return-1
}
删除数据
删除数据的时候，也只是抹掉该槽位上的指纹信息：
func(cf*Filter)Delete(data[]byte)bool{
//获取槽位i1以及指纹信息
i1,fp:=getIndexAndFingerprint(data,cf.bucketPow)
//尝试删除指纹信息
ifcf.delete(fp,i1){
returntrue
}
//获取槽位i2
i2:=getAltIndex(fp,i1,cf.bucketPow)
//尝试删除指纹信息
returncf.delete(fp,i2)
}
func(cf*Filter)delete(fpfingerprint,iuint)bool{
//遍历槽位4个元素，尝试删除指纹信息
ifcf.buckets[i].delete(fp){
ifcf.count>0{
cf.count--
}
returntrue
}
returnfalse
}
func(b*bucket)delete(fpfingerprint)bool{
fori,tfp:=rangeb{
//指纹信息相同，将此槽位置空
iftfp==fp{
b[i]=nullFp
returntrue
}
}
returnfalse
}
缺点
实现完布谷鸟过滤器后，我们不妨想一下，如果布谷鸟过滤器对同一个元素进行多次连续的插入会怎样？
那么这个元素会霸占两个槽位上的所有位置，最后在插入第9个相同元素的时候，会一直循环挤兑，直到最大循环次数，然后返回一个false：
如果插入之前做一次检查能不能解决问题呢？这样确实不会出现循环挤兑的情况，但是会出现一定概率的误判情况。
由上面的实现我们可以知道，在每个位置里设置的指纹信息是1byte，256种可能，如果两个元素的hash位置相同，指纹相同，那么这个插入检查会认为它们是相等的导致认为元素已存在。
事实上，我们可以通过调整指纹信息的保存量来降低误判情况，如在上面的实现中，指纹信息是1byte保存8位信息误判概率是0.03，当指纹信息增加到2bytes保存16位信息误判概率会降低至0.0001。
Reference
CuckooFilter:PracticallyBetterThanBloomhttps://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
CuckooHashingVisualizationhttp://www.lkozma.net/cuckoo_hashing_visualization/
CuckooFilterhttps://github.com/seiflotfy/cuckoofilter
到此这篇关于Go语言实现布谷鸟过滤器的方法的文章就介绍到这了,更多相关Go布谷鸟过滤器内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。