Cuckoo Filter & Bloom Filter 比较

Presentation on theme: "Cuckoo Filter & Bloom Filter 比较"— Presentation transcript:

1 Cuckoo Filter & Bloom Filter 比较

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

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

4 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)） 散列函数相互之间没有关系，方便由硬件并行实现 布隆过滤器不需要存储元素本身，适合保密场合

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

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

7 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取出做这种操作。

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

9 算法 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的准确度依赖于指纹的可信赖性。 删除操作本质上就是查找，查出指纹删了就可以。

10 操作对比 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

11 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 // 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，对每一位都做散列操作，保证了随机性的优秀。

12 实际测试数据 表结构：10000x4x8*8 单次插入允许碰撞：10 填充数据：1000-40000[2000] 测试数据：0-50000
插入错误，插入成功，碰撞， 正确， 错误 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 0, , , , 3, , , , 32, 36968, , , 468, 39532, , , 表结构：10000x4x8*8 单次插入允许碰撞：10 填充数据： [2000] 测试数据： 1.2% | | % 87.5% 注意观察特殊颜色的数据，可以发现这种条件下的插入失败为1.2%，错误识别为1.2% 插入失败的频率可以用碰撞约束才调整。可以看出，即使在当前的条件下，数据接近90%的时候，过滤器的性能还是很优秀的，这也符合论文中所描述的。 错误识别，分为把正确的认为错的，也可以是把错的当成对的，不过从危害性上，后者危害可能更大，前者只是会降低部分性能。 对于错误识别率，很容易发现这几乎是超长的指纹所致，超长的指纹让本已经接近充满的表都并不会错认数据。

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

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

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

16 存储

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

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

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

20 Over