揭秘布谷鸟过滤器：一场数据过滤中的“鸠占鹊巢”大戏！

       大家好，我是石头~

       前面我发了一篇关于缓存系统三大痛点的文章《一文读懂缓存击穿、穿透与雪崩，破局之道何在？》，里面有提到用布谷鸟过滤器来解决缓存穿透的问题。今日，我将继续深化探讨，为大家揭开布谷鸟过滤器的神秘面纱。

1、布谷鸟过滤器的诞生背景

       布谷鸟过滤器，这个名称听起来似乎与数据过滤关联不大，实则源于它的工作机制类似于布谷鸟将蛋下在其他鸟类巢穴中的行为。

       在计算机科学领域，布谷鸟过滤器作为一种空间效率极高的概率型数据结构，专为大规模数据去重和查找问题设计，是布隆过滤器的优秀替代者。

2、布谷鸟过滤器的组成

       在了解布谷鸟过滤器的实现原理之前，我们先了解下布谷鸟过滤器的组成。

       如上图所示，布谷鸟过滤器由三部分组成：哈希表、存储在哈希表中的指纹和两个并不独立的哈希函数（h1和h2）。

哈希表

       布谷鸟过滤器的布谷鸟哈希表的基本单位称为条目， 每个条目存储一个指纹。

       哈希表由一个桶数组组成，其中一个桶可以有多个条目（比如上图中有四个条目）。而每个桶中有四个指纹位置，意味着一次哈希计算后布谷鸟有四个“巢“可用，而且四个巢是连续位置，可以更好的利用cpu高速缓存。也就是说每个桶的大小是4*8bits。

指纹

       我们在使用布谷鸟过滤器的时候，并不需要存储具体的信息，因为整个过滤器的作用只是证明当前元素是否可能存在，因此我们需要把可以证明这个元素的关键信息放进去就可以了，这个关键信息我们称之为指纹。

       指纹是使用一个哈希函数生成的n位比特位，n的具体大小由所能接受的误判率来设置。

哈希函数

       这两个哈希函数，是布谷鸟过滤器用来计算元素存储的桶位置的。每个待插入的元素，都会通过这两个哈希元素计算出2个候选桶位置。

3、布谷鸟过滤器实现原理

       了解了布谷鸟过滤器的组成之后，我们就可以接着了解下它的实现原理。

       如上图，(a)和(b)是布谷鸟过滤器的插入过程。

插入

       上图是一布谷鸟过滤器计算桶位置过程，当一个元素x要插入到布谷鸟过滤器时，布谷鸟过滤器会先使用fingerprint函数计算出指纹fp，接着用hash算法对计算式第一个桶位置p1，并用p1和指纹通过第3个公式计算出第2个桶位置p2。

       接下来，我们要开始执行插入动作，这里会遇到三种情况：

• p1桶和p2桶都有空余空间：将指纹fp随机插入一个桶

• p1桶和p2桶只有一个桶有空余空间：将指纹fp插入有空余空间的桶中

• p1桶和p2桶都没有空余空间：此时将触发布谷鸟过滤器的“踢巢”操作（将现有桶内一个元素的指纹移出，并根据此时桶位置和该元素指纹计算出该指纹的另外一个桶位置。若此时这个桶的位置也满了，则继续“踢巢”，直到找到一个可供新元素插入的空桶为止。）

查找

       布谷鸟过滤器的查找过程很简单，给定一个项x，算法首先根据上述插入公式，计算x的指纹和两个候选桶。然后读取这两个桶：如果两个桶中的任何现有指纹匹配，则布谷鸟过滤器返回true，否则过滤器返回false。此时，只要不发生桶溢出，就可以确保没有假阴性。

删除

       删除的过程也很简单，检查给定项的两个候选桶；如果任何桶中的指纹匹配，则从该桶中删除匹配指纹的一份副本。

4、布谷鸟过滤器的不足

存在误删的可能行

       若是不同元素根据函数计算出来的指纹和桶位置相同，则可能出现误删。

插入复杂度比较高

       随着插入元素的增多，触发“踢巢”的可能性越高，复杂度会越来越高。

存储空间的大小必须为2的指数

       这个限制让空间效率打了折扣。

同一个元素最多插入kb次

       k指哈希函数的个数，b指的桶中能装指纹的个数也可以说是桶的尺寸大小。如果布谷鸟过滤器支持删除，则必须存储同一项的多个副本。 插入同一项kb+1次将导致插入失败。 这类似于计数布隆过滤器，其中重复插入会导致计数器溢出。

5、总结

       以上为本次分析的内容，欢迎大家评论区留言讨论~

MORE | 更多精彩文章

• JWT重放漏洞如何攻防？你的系统安全吗？
• JWT vs Session：到底哪个才是你的菜？
• JWT：你真的了解它吗？
• 别再这么写POST请求了~
• H5推送，为什么都用WebSocket？
  关注公众号：石头聊技术，解锁更多Java干货文章。