Cuckoo Filter & Bloom Filter 比较

过滤器应用场景举例 本地恶意URL库 Stored in Filter 这是一个好url 拦截莆田系医院网站http://www.bjfhfk.net/?yy1?yiyuan?bdjjpc13?yiyuan 远程服务器 鉴别“http://www.bjfhfk.net/?yy1?yiyuan?bdjjpc13?yiyuan ” 这是一个好url Probably Yes! Lookup(“http://www.bjfhfk.net/?yy1?yiyuan?bdjjpc13?yiyuan”) 命中！Dangerous… No! Delete（“”） 演示命中url库、以及删除单个url的过程 本地恶意URL库 Stored in Filter

过滤器的用途 Is item x in set Y 构建大型缓存 拼写检查 数据库系统 网络爬虫-URL去重复 过滤器解决的是“判别x是否在集合y中”的问题，它的使用场景可以概括为用于构建大型缓存。 无论是做拼写检查、数据库缓存还是爬虫的的url去重复，都是做这样的事情。 我们所谓的过滤器，本质上是改进的hash表，相对于最基本的散列，它做到了更高效和更低的碰撞

Bloom Filter的原理 K-散列 时空优势：布隆过滤器存储空间和插入/查询时间都是常数（ O(k) O(k)） 很长时间以来，布隆过滤器是一种十分流行的过滤算法。 它的原理很简单，简而言之就是存在一个表，和K个不同的hash函数。 插入一个item的时候，会对这个item做K个hash，之后把表中对应的K个hash位全部置为true，注意，这个时候并不考虑这K个位置原来的值。 在查找一个item的时候，同样对item做K个hash，只有这K个位置全部为true，才会认为表中存在这个item。 它的优势很明显，时空优势、保密等 时空优势：布隆过滤器存储空间和插入/查询时间都是常数（ O(k) O(k)） 散列函数相互之间没有关系，方便由硬件并行实现 布隆过滤器不需要存储元素本身，适合保密场合

随着存入的元素数量增加，误算率随之增加。 删除元素。 Bloom Filter的劣势 随着存入的元素数量增加，误算率随之增加。 删除元素。 当然它的问题也很明显，一个是误算率，另一个就是不能删除。删除一个item绝对不可以把K个位置全部置为false，因为这会使命中这七个位置任何一个的item全部会识别为不存在。实际上改进布隆过滤器使之可以删除是很麻烦的。最常见的思路是每个位置都存一个uint，插入时增1，删除时减1，不过这也有问题，因为并不确定要删的元素就一定已经存在于表中。有一种叫做d-left bloom的改进过滤器似乎解决了这个问题，但是它又过于笨拙。 误算率更易理解，随着数据的增多，空位越少，就越容易把一个不存在于表中的数据判定为存在。在表满的时候，更是会把所有的数据均判定为存在于表中。 正式因为它的这些风险，我们才会选择使用cuckoo

误算率稳定，整体远低于Bloom Filter 使用Cuckoo Filter的原因 删除方便 误算率稳定，整体远低于Bloom Filter Cuckoo的核心优势就是两个，删除方便，甚至比插入还要方便；误算率稳定而且远低于布隆，当然，任何hash避免碰撞都是理论上不可能的，不过优化的cuckoo filter在3%的错误率的情况下，使用的空间似乎远小于bloom filter

Cuckoo Filter方法： 选位： bucket1 = hash1(x) bucket2 = bucket1⊕hash1 (FP(x)) 占位【杜鹃】： alternate(x) = current(x) ⊕ hash(FP(x)) ……（有限递归） Cuckoo的意思是杜鹃，它的来源就是杜鹃下蛋的原理。杜鹃下蛋的故事十万个为什么里面讲过的，就是它把蛋下在人家的窝里，把人家的蛋搞掉。Cuckoo filter也类似，每个item选两个位置，判断这两个位置是否为空，如果有一个为空，就放在这个位置上，如果都不为空，就选一个位置，取出这上面的item，放自己，然后在把这个取出的item放到那个item自己的另一个位置上，当然那个位置也会可能不为空，那个时候再把对应位置上的item取出做这种操作。

注意 指纹：log b/n 链表习惯挂桶，提升过滤器效率（不挂桶的效率最大只有50%，论文上介绍挂桶效率可达到95%，取决于数据结构设计） 链表挂桶，桶本身可以做简单排序，能提升命中效率 桶的长度不宜过大，那样把过多处理放在了桶的遍历上 当然，一般编程的时会对这种操作做一个限制，不会无限制的允许这种递归。另外，就好像第三个图这样，大部分时候也会对hash表进行挂桶操作，这样结合有限递归的限制，会降低出错率。 不过挂桶不宜过多，否则hash表本身的性能就降低了。 在改进版的cuckoo filter中对桶会做semi-sorting，能够降低空间消耗，这个后面会说一下。 刚刚说cuckoo filter存储item，在每个位置上，都会存储一个指纹，根据论文中的数据，指纹长度最合适为log b/n 以上，b为hash表长度，n为挂桶数量。关于这个地方后面我补充了详细的测试数据。

算法 Algorithm 2: Lookup(x) f = fingerprint(x); i 1 = hash(x); Algorithm 1: Insert(x) f = fingerprint(x); i 1 = hash(x); i 2 = i 1 ⊕ hash(f); if bucket[i 1 ] or bucket[i 2 ] has an empty entry then add f to that bucket; return Done; // must relocate existing items; i = randomly pick i 1 or i 2 ; 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]; // Hashtable is considered full; return Failure; Algorithm 2: Lookup(x) f = fingerprint(x); i 1 = hash(x); i 2 = i 1 ⊕ hash(f); if bucket[i 1 ] or bucket[i 2 ] has f then return True; return False; Algorithm 3: Delete(x) remove a copy of f from this bucket; 这是cuckoo的增删查的算法。 增加算法的核心也就是这几个hash函数的运用。一个用于选位，另一个用于生成指纹，实际上这也是hash本身的用途，就是选位和指纹加密。可以看到，我标红的地方，信息指纹hash非常重要，这个hash函数一会可以看一眼代码，我用的那个方案类似于rabin的原理。Rabin指纹是密码学里面特别常用的加密。它也叫随机多项式算法，特点是计算效率高，随机性好，换句话说就是重复率低，很多模式识别也会用。Max这个参数是指有限递归的容忍度，就是递归选位最多选多少次。 Lookup是查找的算法，相对简单，就是看一下item对应的两个位置上有没有对应的指纹就可以，lookup的准确度依赖于指纹的可信赖性。 删除操作本质上就是查找，查出指纹删了就可以。

操作对比 Insert O ( 1 ) Delete O（1） Lookup O ( 1 ) Capacity x bucket x fingersize & maxRetries K & Capacity 我们可以尝试对比下，实际上效率没有数量级的差别，都是O(1)。 对于这样两个大小的表，相对于复杂度的算计，访问位置数量区间更加直观。可以看出，对于插入和查找操作，布隆都是访问K个位置，儿对于插入，cuckoo一般在2bucket个位置访问即可，最差情况要访问2+maxRetries x bucket个位置。 对于删除和查找，只需要在2xbucket个位置中查找即可。 bloom cuckoo 综合 Insert K (2-[2+maxRetries]) x bucket O(1) Delete cannot 2 x bucket Lookup

Cuckoo Filter code func rabinFingerprintFunc(value []byte, fingerprintSize uint) Fingerprint { windowsize := 8 mod := 255 prime := 71 pow := int(math.Pow(float64(prime), float64(windowsize))) % mod prntfngr:= make([]byte, fingerprintSize) for j, _ := range prntfngr { rollhash := 149 // 1001 0101 outbyte := 0 for i, v := range value { // rollhash = (rollhash * PRIME + inbyte - outbyte * POW) % MODULUS // Include j so that each iteration is different rollhash = (rollhash*prime + int(v) + j*prime - outbyte*pow) % mod if i > windowsize { outbyte = int(v) } prntfngr[j] = byte(rollhash) return prntfngr 然后，看一眼刚刚介绍的rabin指纹，它的特点是有个窗口，做滚动hash，对每一位都做散列操作，保证了随机性的优秀。

实际测试数据 表结构：10000x4x8*8 单次插入允许碰撞：10 填充数据：1000-40000[2000] 测试数据：0-50000 插入错误，插入成功，碰撞， 正确， 错误 0, 1000, 0, 1000, 0 0, 3000, 0, 3000, 7 0, 5000, 0, 5000, 10 0, 7000, 0, 7000, 11 0, 9000, 0, 9000, 6 0, 11000, 0, 11000, 15 0, 13000, 0, 13000, 44 0, 15000, 0, 15000, 81 0, 17000, 0, 17000, 119 0, 19000, 0, 19000, 153 0, 21000, 2, 20998, 185 0, 23000, 18, 22982, 198 0, 25000, 26, 24974, 215 0, 27000, 49, 26952, 217 0, 29000, 92, 28908, 237 0, 31000, 359, 30645, 241 0, 33000, 1009, 32022, 222 3, 34997, 2585, 32554, 227 32, 36968, 5224, 32259, 233 468, 39532, 15848, 27252, 240 表结构：10000x4x8*8 单次插入允许碰撞：10 填充数据：1000-40000[2000] 测试数据：0-50000 1.2% | | 2.4% 87.5% 注意观察特殊颜色的数据，可以发现这种条件下的插入失败为1.2%，错误识别为1.2% 插入失败的频率可以用碰撞约束才调整。可以看出，即使在当前的条件下，数据接近90%的时候，过滤器的性能还是很优秀的，这也符合论文中所描述的。 错误识别，分为把正确的认为错的，也可以是把错的当成对的，不过从危害性上，后者危害可能更大，前者只是会降低部分性能。 对于错误识别率，很容易发现这几乎是超长的指纹所致，超长的指纹让本已经接近充满的表都并不会错认数据。

指纹长度为log n/b时错误率最低 表结构：4096x2x[1-10] 单次插入允许碰撞：2 填充数据：8000 测试数据：0-40000 插入错误，插入成功，碰撞， 正确， 错误 780, 7220, 8248, 3521, 313 579, 7421, 6299, 4457, 11 626, 7374, 6535, 4333, 14 560, 7440, 6195, 4564, 24 531, 7469, 5936, 4689, 17 568, 7432, 6303, 4491, 8 577, 7423, 6285, 4525, 11 556, 7444, 6087, 4587, 12 539, 7461, 6021, 4656, 11 552, 7448, 6148, 4563, 17 表结构：4096x2x[1-10] 单次插入允许碰撞：2 填充数据：8000 测试数据：0-40000 关于log n/b这个公式，我进行了较为详细的测试。可以看这个表，这个表只有错误识别列是值得关注的，正确率同样很低，但是并不值得过分关注，识别正确率低的原因在于允许碰撞次数太少，很多填充准确的值被布谷鸟最终踢掉了，这又不在插入错误的统计。 按照这张表，最合适的指纹长度为log4096/2,大概是10-11之间，可以看到除了第一组的错误率超高之外，下面的全都降低了数量级。 大概是一个byte是八位，2个byte就远大于11了。所以后面指纹增长的效果接近于没有。 最开始踩了一个坑，就是错误的把bit当做byte计算，犯了常识性错误。

上面那组数据我自己看着都不信啊 插入错误，插入成功，碰撞 1726320, 8273680, 0 1081929, 8918071, 0 1726320, 8273680, 0 1081929, 8918071, 0 1049358, 8950642, 0 1045286, 8954714, 0 1058844, 8941156, 0 1046334, 8953666, 0 表结构：4096*4096x1x[1-6] 单次插入允许碰撞：0 填充数据：10000000 当然，上面那组数据太不明显，又因为我的程序里面指纹长度都是byte约束而很难做bit长度的约束，所以我只能扩大数据量和表长 对于这样一个表，我做了一个单元测试。并且强制约束禁止碰撞，并不挂桶，这样也许结果更明显。 这个时候理论上最佳的指纹长度应该是log4096*4096，也就是24位，折算成byte，应该在三位以上 这时我们对比插入成功和插入失败，也是大概在这个地方，性能停滞了，所以基本符合理论。

指纹长度-成功率趋势图 in theory n: hash table size, b: bucket size see more analysis in paper 看到网上有这样一张图，它的数据5bit为是奇点。

存储

Lookup-MOPS 这是几种过滤器的性能对比，MOPS：MIllion Operation Per Second 中文全称：每秒百万次运算。 所以这个数据肯定是越大越好了。 所以看出cuckoo的性能应该是最佳。 Semi sort是改造的cuckoo filter，会对桶内数据排序，目的是压缩节约空间，所以性能会降低很多，我也没觉得这样压缩有什么特别大的意义，8亿数据才节约1G内存。 Blocked bloom不命中的效率高是因为它本身相当于中间又加了一层缓存，或者说索引。 包括其他几种bloom的变种，从本身算法看，都有点画蛇添足，反而举例bloom的轻量越来越远。

布隆过滤器&&酷壳过滤器 时空优势 保密性 散列函数 删除元素 误算率

不同过滤器比较[未测试] Bloom blocked Bloom counting Bloom d-left counting Bloom quotient cuckoo

Over zhangpenghao@360.cn 2016.8.4