3.5*　过滤

在点对点P2P网络中，由于没有中心控制，一方面区块或交易在网络上自由传输，那么，传过来的数据我这里有没有？若已有，则没有必要重复接受；该数据我转发过没有？若已转发，则没有必要重复转发。为了避免反复传输和接收相同的数据，点对点网络中各节点都应设置过滤器。另一方面别人问你“有没有这个K的V”或“V在内存中还是在磁盘上”等等，也需要一个判断算法。

由此，抽象出的问题是：判断元素x在不在一个集合S中。

如果要判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较来确定。链表、树、哈希表（又叫哈希表，Hash Table）等数据结构都是这种思路。

但在数据量比较大的情况下，我们需要一个时间和空间消耗都比较小的数据结构和算法。Bloom Filter就是一种解决方案。

3.5.1　降低一点儿标准

设网络节点接收网络传来的数据存于本地数据库，需要判断新传来的数据X需不需要保存下来，即需要一个过滤算法“判断元素x在不在一个集合S中”，这个算法返回的结果一定为如下两者之一：

（1）算法说：x“在”一个集合S中；

（2）算法说：x“不在”一个集合S中。

借用医学检验的说法，上述对应为检验结果：

（1）x呈阳性；

（2）x呈阴性。

如果检验绝对正确，则如下命题成立：

x在一个集合S中的充分必要条件是x呈阳性。等价命题为：x不在一个集合S中的充分必要条件是x呈阴性。

逻辑学告诉我们，它可转化为两个命题：

（1）若x呈阳性，则x在一个集合S中；

（2）若x呈阴性，则x不在一个集合S中。

显然，很难有检验手段同时满足上述命题，所以我们退而求其次，即考虑弱化它们。从医学检验的需求来看，首先，必须保证“有此病，则检验必呈阳性”，即若x在一个集合S中，则x呈阳性。改为其逆否命题即为（2），也就是说：我们必须保证（2）成立，那降低要求的重担就落在（1）上了，将（1）改为“若x呈阳性，则x很可能在一个集合S中”。

也就是允许（1）有一定的误判率，即平时说的呈假阳性。

综上，我们可以稍微降低对检验的要求，即要求检验满足：

（1）允许少量的假阳性，即允许“若x呈阳性，则x在一个集合S中”有误报率；

（2）不允许有假阴性，即“若x呈阴性，则x不在一个集合S中”不漏判，即百分百准确。

将检验改为针对算法，则对应的说法为：

A．算法说“在”，极大可能“在”，即“极少”误报；

B．算法说“不在”，一定“不在”。

3.5.2　一个算法

我们先找到一个满足条件B的过滤算法。

设集合S中有|S|个元素，选取一个k，做初始值为0的k个格子，格子有编号0到k-1，|S|远远大于k。

对S中的每个元素y，按k的模映射到格子中，即i=y%k，对编号为i的格子将其值由0改为1，若已为1则保持不变。这就相当于把S中的元素y作为子弹，向一块划分为k个格子的板子扫射，瞄准规则为i=y%k，若编号为i的格子被打穿，则格子的值为1。

对需要判断的元素x，也计算j=x%k。算法就是看编号为j的格子的情况：

（1）若编号为j的格子未被子弹打穿，则格子的值仍为0——算法说“不在”，则可以肯定x不在S中，因为x对应的格子没有被S中的元素击中，即算法说“不在”，一定“不在”。满足条件B的要求。

（2）若编号为j的格子被子弹打穿，则格子的值为1——算法说“在”，则x可能是S的元素，还有可能是这种情况：x变换的结果与S中元素变换结果“撞车”，如变换结果“撞车”13%10=3%10，即算法说“在”，不一定“在”。不一定满足A的“极少”误报的要求。

综上，这个算法满足前述降低标准的要求。

3.5.3　对算法的优化

切换个视角：将上述带孔的板子视为一个筛子，用它来筛x，若x没有掉下去，算法说“不在”，则x不在S中（满足B的要求）。

A中要求“极少”误报，如何实现“极少”？

板子是用S中的元素打孔的，从孔中掉下去的x，算法给出的检验结果是“在”。

模具有很大的压缩性，如S={21，33，23}，k=10时，对S中的元素按10求模得到的筛子为，打孔了的格子标记为1，板子上有两个孔。

显然，x=61不在S中，但x从孔中掉下去了，因为61%10=1，对应于编号为1的格子。所以，从孔中掉下去的x既可能为S中的元素（如21），也可能不是S中的元素（如61）。

可再做一个筛子，如取k=6，筛子为，则61%6=1说明61不会被这个筛子漏下去。

也就是说，通过多加筛子，层层筛选，能掉下去的元素就会越来越少，“最终掉下来的x，在一个集合S中”的误报率很小，如图3.3所示。

在我们的生活中也有这方面的例子：体检发现某指标为阳性，怎么办？一是再对该指标进行复检，这是怀疑检测的技术；二是再对其他相关指标进行检验，这才是再加一层筛子。

优化后，算法满足前述A的“极少”误报的要求。

上述多层筛子在使用时，可以“贴在一起”，形成一个筛子。

元素从筛子中“筛下去”、“呈阳性”和“在集合S中”是同一个意思，只是站在不同角度进行表述。

3.5.4　布隆过滤器

上述多个筛子的大小可能不一样，如何使得筛子的大小一样呢？

现有多块大小一样的板子，每个板子有k个格子，将它们做成多块大小一样但不同的筛子。做筛子的方法还是用k取模，要做不同的筛子，那还得从“子弹”的角度去思考：对集合中的元素进行不同的“变换”，得到不同批次的“子弹”，就可以做出不同的筛子。

对“变换”的要求就是变换后能“代表”原来的元素，此处请回忆“指纹”的知识。

Hash函数能满足这一要求。选取m个Hash函数：。

对S中的每个元素y，先用作用后再按k的模映射到格子中，即i=h1(y)%k时，对编号为i的格子将其值由0改为1，若已为1则保持不变，形成第一个筛子。

对如法炮制，就得到了m个筛子。这里要重新定义元素x“筛下去”的含义，它是指：分别能从这m个筛子中“筛下去”。若有一个被第i个筛子挡住，则元素x就没有被“筛下去”，说明x不在集合S中。

更进一步，将这m个筛子的孔全部集中到一个筛子上，再用这个新筛子去筛元素x的，若都能“筛下去”，则称x能“筛下去”。显然，新筛子比原来任何一个筛子的孔都多，故稍提高了x“筛下去”的可能性，即稍增加了些“假阳性”，但换来的好处是：只需要一个筛子，节省了空间。这个新筛子就是布隆过滤器（Bloom Filter）。

另外，按给定A中的误报率要求（通常是万分之几），以及元素数据量评估，就可能确定Hash函数个数m及筛子大小k，公式略。

3.5.5　布隆过滤器效率优化

上述布隆过滤器算法对集合S中的元素需要计算m次Hash值，而Hash值的计算是需要耗费大量机器时间的，因此有人提出一个技巧，可以用2个哈希函数来模拟m个哈希函数，即

进一步地：

（1）该公式可以看作每次累加，即。

（2）而与又可以用一个Hash函数值的左半部分和右半部分来分别模拟。

这样就将m个Hash函数的计算转化为了一个Hash函数的计算，大大提升了效率。

例如，Guava中布隆过滤器算法的实现是对元素通过MurmurHash3计算16字节的Hash值，将得到的Hash值取高8个字节，以及低8个字节分别作为与。

3.5.6　缺点及应对

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法。它之所以能做到在时间和空间上的高效率，是因为牺牲了判断的准确率和删除的便利性。

（1）存在误判。它是单向误判的，即B不会误判，A有很小的误判，故在一般情况下是没有问题的，如重复去取数据。但有时可能是不能容忍的，如S为黑名单，“在黑名单中”的误报是不能容忍的，因为不能误伤，这时就不能用这个方法了，或者将不能伤害的加入“白名单”。

（2）删除困难。能从集合S中删除一个元素，但能将筛子中由这个元素产生的孔填上吗？不能。例如，在前面的例子中，S={21,33,23}，取k=6，筛子为，当删除33时，就不能将它对应的孔填上，即不能把编号为3的孔的值从1改为0，因为，该孔也是另一个元素21打的孔。程序员很容易处理这种情况，当多个元素打同一个孔时，将打孔标志改为格子被打孔计数器，删除一个元素，对应的格子的被打次数减1，当减到0时，该孔相当于被填上了，这就是所谓的计数布隆过滤器（Counting Bloom Filter）。

3.5.7　应用举例

布隆过滤器的特点是：

• 算法说“在”，极大可能“在”，即“极少”误报；

• 算法说“不在”，一定“不在”。

由此，我们可以找到适合的应用，举例如下。

（1）Google著名的分布式数据库BigTable及HBase都使用布隆过滤器来查找不存在的行或列，以减少磁盘查找的I/O次数。

（2）文档存储检查系统也采用布隆过滤器来检测是不是先前存储的数据。

（3）Google Chrome浏览器使用布隆过滤器加速安全浏览服务。

（4）垃圾邮件地址的过滤。

（5）爬虫工具中URL地址的去重。

（6）解决缓存穿透问题：指查询一个一定不存在的数据，先查缓冲有没有，再查存储层有没有，这将导致这些不存在的数据每次请求都要到存储层去查询，失去了缓存的意义。当流量较大，特别是被攻击时，出现一直请求访问数据库的情况，很容易导致服务器“挂掉”。采用布隆过滤器，将存储层所有数据映射到一个足够大的BitMap中，即依前述原理，建一个叠加筛子，使不存在的数据被这个BitMap拦截，这时查询机制从“先查缓冲，再查存储层”改为“先查缓冲，再过滤，再查存储层”，从而避免了对底层存储系统的查询压力。

（7）区块链中的应用，后面章节将会涉及。