白话布隆过滤器BloomFilter

原创后端技术指南针后端研究所

通过本文将了解到以下内容：

查找问题的一般思路
布隆过滤器的基本原理
布隆过滤器的典型应用
布隆过滤器的工程实现

场景说明：

本文阐述的场景均为普通单机服务器、并非分布式大数据平台，因为在大数据平台下问题就是另外一种考虑方式了，因此本文只描述贫穷落后一穷二白的场景，俨然有种60年代先辈们在戈壁攻克原子弹的感觉。

1.查找问题的一般思路

查找问题是出现频率极高的问题，来看一道面试题：

给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件所有共同的URL。
某知名公司面试题

一般思路：

面对一般的问题，根据不同的数据规模，转换为计算机问题之后就落地到实际的数据结构：

线性结构：数组、链表、
容器结构：集合、Map、HashTable
树形结构：AVL、RBTree、BTree

但是上述的结构都是将待查找数据直接存储，如果是大数据量，这样虽然保证了准确性但是空间消耗会非常大，实际是不可行的。

苛求条件下的思路：

把待查数据进行信息无缺失地压缩

这句话的意思就是：对于公民可以使用身份证来独立唯一表示此个体，而无需太多诸如性别、出生日期、出生地、履历等描述，这种转换就相当于在信息无缺失的情况下，使用更少的特征来表示。

还有一个例子就是：文言文往往篇幅很短，翻译为白话文可能很长，所以文言文就可以认为是白话文的信息无缺失压缩。

这种做法可以实现使用更少的信息量表达更多的含义，对存储很有利。

借助于存储容器来存储辅助信息

这句话是说：比如高考之后的每个省份的一分一档表，每个分数段代表一个存储空间，假如要知道0-750分中每个分数段有多少人，那么只需要计数即可，因为在对应分数段的考生就是对应的分数，换句话说600分段的存储的值都是600分，无需单独记录绝对值，借用下标即可，也就是需要设计存储容器来自动带有相关信息。

2.布隆过滤器的基本原理

前面那道问题就可以使用布隆过滤器解决。

布隆过滤器的定义

布隆过滤器Bloom Filter是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
维基百科-BloomFilter

布隆过滤器横向对比

如果想判断一个元素是不是在一个集合里，一般是将集合中所有元素保存起来，然后通过比较确定。链表、树、哈希表等数据结构都是这种思路。但是集合元素的增加需要的存储空间越大，检索速度也越慢。
维基百科

布隆过滤器的基本原理

布隆过滤器本质上是bitmap位数组的扩展，位数组的应用也非常多，比如在IO复用工具Select中就使用三个FD_SET来存储Socket文件描述符的值，简单说一下位数组的原理：

假如现在有0-31范围的20个不重复数字，如何判断16是否在其中呢？

一种做法是建立个数组就算是int8 单字节的数组，也需要8*32=256位空间，之后去遍历这个数组查看是否有16.

另外一种做法使用一个int32的变量，这个变量占4个字节32bit，可以用bit0表示数字0，bit1表示数字1,.....bit30表示30，因此我们实现了使用4字节空间完成了之前32字节的工作，空间使用是之前的1/8，非常可观。

一图胜千言灵魂画手上线了：

如图所示在bit数组中如果对于bit是1表示存在对应的值，为0则不存在。

布隆过滤器的两大组件

一定大小的BitAarry位阵列(具体大小和存储规模有关)
N个优秀的哈希函数(N的个数和存储规模和容忍误判率有关)

两个组件的功能也非常明确，位阵列就是存储对应位的值是0/1的二进制向量，哈希函数的作用是将原始输入经过数学运算转换为一个数字值，哈希函数是加密和安全的基础，也是数学的伟大体现，感兴趣可以进一步学习其基本原理。

对应最开始提到的信息无损压缩其实就是哈希函数的作用，就像我们每个人可以用一个学号、工号、身份证号来代替一样，哈希函数也实现了原始输入的数字化。

布隆过滤器和哈希冲突

哈希冲突虽然概率很低，但是在大规模数据场景下还是会出现的，而且冲突率和哈希函数本身有很大关系，因此在设计布隆过滤器时要选择性能优良的哈希函数来降低哈希冲突。

举个栗子：

对于哈希函数fuc(唱歌都很棒)，有四个输入分别是大白、周杰伦、张学友、岩崎良美，哈希函数计算结果分别是：Yes/Yes/Yes/Yes。

可以看到如果以yes/no作为结果的话，我和周杰伦他们仨产生了哈希冲突，因此这个哈希函数并不优秀。水平有限关于哈希函数和碰撞的数学原理就不再展开了。

多个哈希：

即使很优秀的哈希函数仍然存在冲突，那么如何降低冲突率呢？很明显多用几个哈希函数！

假如Hash1冲突率万分之一，Hash2万分之一，同时Hash1和Hash2冲突的概率就是亿分之一了，但是实际中为了将数据都存储在bitarray中，由于取模运算的存在，冲突率会比理论值高。

这种思想也并不新鲜，远在春秋战国时期，就有先例：

(侵权请告之删除)

上图是兵符，当两个兵符合在一起才可以调度千军万马，跟单个哈希冲突率高就使用多个是一个道理。

布隆过滤器的具体使用

假如现在有三个哈希函数分别为h1,h2,h3,同时有三个输入x,y,z。三个输入分别通过h1-h3进行哈希计算出对应整数之后，对bitarray的长度进行取模运算，获取对应下标再进行置1，这样运算三次就形成了如图的bitmap结构：

布隆过滤器检索时，使用相同的哈希函数进行计算出对应的bit位置，只要看这些位置的值，如果这些位置有任何一个0，则被检元素一定不在；如果都是1，则被检元素可能存在。

一句话概率就是有0一定不存在、全1不一定存在。

布隆过滤器和误判率

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的bit位被多次映射且置1。

这种情况也造成了布隆过滤器的删除问题，因为冲突的存在无法确定有多少输入映射到这个bit位了，当然这是个优化方向。

布隆过滤器存在一定的误判，主要因素包括：

哈希函数本身的冲突率
bitarray位数组的大小

这个其实很明显，如果位数组很小，哈希函数再优秀也会产生误判，因此在工程设计中需要首先设定误判率和数据规模再确定哈希函数个数和位数组大小。

上述过程再用一张图来表示：

布隆过滤器的优缺点

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。布隆过滤器可以表示全集，其它任何数据结构都不能；
维基百科--布隆的优点

误算率是其中之一，随着存入的元素数量增加，误算率随之增加，但是如果元素数量太少，则使用散列表足够。另外一般情况下不能从布隆过滤器中删除元素。
维基百科--布隆的缺点

3.布隆过滤器的典型应用

布隆在海量数据查询中以优异的空间效率和低误判率有非常广泛的应用，其中包括但不限于：

检查单词拼写正确性
检测海量名单嫌疑人
垃圾邮件过滤
搜索爬虫URL去重
缓存穿透过滤

4.布隆过滤器的工程实现

位数组和哈希函数个数的计算

理论要迁移到实际工程还是需要做一些调研的，从上面的理论部分可以知道，要设计一个误判率低的布隆过滤器最关键的是要确定两个因素：

bitarray位数组的大小m
哈希函数的个数k

感兴趣的可以查询相关推导过程，这里直接给出网上较为认可的工程值：

其中fpp是误判率比如0.0001，n是预估要存储的数据元素个数。

多个哈希函数的优化

使用多个哈希函数确实可以降低冲突，但是多个哈希函数也会造成计算时间的增加，因此哈希函数的个数是个折中值，但是在2008年哈佛的一篇论文指出可以使用2个哈希函数来模拟多个哈希函数：

这篇论文涉及大量的数学推导，我很自觉地知难而退了，大神可以看看，作为一个结论可以在工程实践中用一下。

工程组件

Google的Guava类库提供了简洁的接口，只要设置误判率和数据规模即可完成，Redis新版本中也有bitmap类型，也可以实现布隆，当然不借助于这些组件，也可以自己来实现，在此就不展开了，后续有机会可以聊一聊。

5.参考资料

https://www.jianshu.com/p/af6c63822da8
https://juejin.im/post/5c9b61576fb9a070f653557d
https://segmentfault.com/a/1190000015482091
https://www.kancloud.cn/kancloud/the-art-of-programming/41619
https://segmentfault.com/a/1190000012620152
https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf

继续滑动看下一个