一篇文章读懂布隆过滤器

你接到一个新的开发需求，需要你为用户注册服务设计一个用户名检查的API接口, 这个接口会根据用户输入的用户名与系统中所有账号的用户名进行匹配检查，如果用户名已经存在，则会提示用户该名称已被使用,无法进行注册，如果名称未被占用，则返回允许注册。这个需求是不是听上去很简单，实现上我们有以下的几种方案：

        方案一：每次注册验证的时候直接去数据库执行SQL, 检查是否存在相同用户名。

        方案二：导出一份用户名列表到缓存（定期或者使用消息队列），每次单独的查询缓存完成检查

我们先来看下前两种方案存在有哪些问题：

        方案一：最简单，除了原数据库存储外，不需要外部的数据存储服务，但是每次查询进行全表扫描，特别是涉及到注册用户较多，分库分表设的情况下，资源开销可不是一般的大，查询效率肯定也不会太好。

        方案二：内存数据查询效率比第一种要好一些，但是需要额外维护一套缓存服务，运维成本也不小，另外数据存储服务在数据量较大的情况下占用的内存开销也会较大。

其实比较简单的方式是通过一个布隆过滤器来完成校验，这种方式具有维护简单，占用资源少，查询效率高的优势，至于如何实现，以及它是否也是一个完美的解决方式呢，等我们讲完了大家就明白了。通过阅读这篇文章，你可以：

      1. 自己实现一个布隆过滤器，完成数据验证

      2. 了解布隆过滤器的优点和缺陷。

      3. 掌握一些典型的布隆过滤器的使用场景

1. 什么是布隆过滤器？

我们先从维基百科给出的布隆过滤器的解释：

布隆过滤器是一个内存使用效率较高的概率数据结构，由Burton Howard Bloom在1970年提出，被用于测试是一个元素是否是一个集合中的成员。该数据结构在验证中存在假阳性的错误，但不会产生假阴性结果。在验证的时候只会返回两个结果：肯定不存在和可能存在的结果。

其中上面的说的假阳性，指本身可能不存在集合中，但是检查会产生验证存在的结果；假阴性则是本身应该存在集合中，但是检查产生验证不存在的结果。验证的结果返回不存在，那元素肯定是不在集合中，而验证如果返回可能存在的话，则有一定概率元素本身不存在集合中。因此实践中可能就需要知道到底这样的错误概率有多大， 一般1%以内的概率可以满足大部分的需求，但是如果可能概率只有50%,那就失去了验证的意义了。

2. 从哈希表到布隆过滤器

那可能有人会问，如果我定期把数据存储到一个哈希表中，是不是也可以呢？答案是肯定的，不仅可以，而且验证可实现100%的准确性应答，比起布隆过滤器的概率设计来说看上去更完美一些，但是为何布隆过滤器仍被用于很多现实的系统设计中呢，它存在的意义在哪呢？

我们先看一下哈希表的设计，这里使用的是链式实现的哈希表，元素通过哈希函数映射到一个大小为N数组上，通过数组指向的一个链表来存储元素，如果多个元素映射到相同的位置，则使用链表将多个元素串连起来，查询的时候通过定位以及遍历链表检查是否存在。

针对哈希表我们的存储成本其实很昂贵的，除了需要存储Key元素外 每个链表还需要维护节点指针的开销，另外本身N个元素也需要维护大量的指针来实现链表的跳转。假设我们存储100万的用户账户邮件地址，邮件地址的平均长度为20个字节,每个指针占用8个字节，考虑表负载大约1/2的情况下，(2*1000000 + 2*1000000)*8 + 1000000*（20） =  52MB，当然这只是粗略的计算,实际程序可能占用的更多，如果我们现在的用户1000万呢， 1个亿呢，内存占用将直线上升。

另外我们考虑一个相似的场景，爬虫URL监测，通过一个系统来监测URL是否已经被爬取过，如果是的话直接跳到下一个待监测URL任务，这个需求下URL规模往往是巨大的，动辄都是上亿的URL爬取，我们如果还是使用哈希表的话， 则基本上内存访问是不用考虑了。一个URL按照100字节计算，一个亿的URL仅数据存储就会占用=10^9 *100 = 100GB!!!，这还不包含其他指针和数据的开销, 如果使用类似于磁盘哈希表的结构处理，那访问速度肯定不会太快。

或者我们可以改进一下Hash表的结构，去掉后面的链表呢？这时候我们的Hash表只包含了前面的数据表结构。删除链表后我们如何通过这个结构来确定元素是否在集合中呢？很简单，举个例子，假如我们现在有几个Key需要写入：

1. 对Key进行Hash计算，比如Hash(Key)=1 那我们就设置第1个位置为1

2. 对Key2进行Hash计算，比如Hash(Key2)=5 那我们就设置第5个位置为1

3. 依次按照上面的方式不断更新表格，直到完成所有元素输入。

4. 验证的时候，假如输入的是Key3, 同样计算Hash(Key3)=3 由于第3个位置为0 则我们知道之前并没有元素的Hash值等于3，因此返回验证失败，元素肯定不在集合中。

5. 假如输入的是Key4, 同样计算Hash(Key4)=1 由于第1个位置为1 则我们知道之前有元素的Hash值等于1，因此返回验证成功，元素可能存在集合。

两个键值的哈希值相同，则我们说过滤器发生了碰撞，这种碰撞是在预期范围内，我们后面有对应的解决方式。现在我们只需要知道的是对于发生了碰撞的情况，将导致一定的误报率发生，Hash(k1) = Hash(k2), 那我们在验证的阶段，我们无法确定到底是K1是集合中的元素，还是K2是集合中的元素。

3. 设计布隆过滤器

为了解决上面的碰撞问题，或者更精确的说是缓解该问题，在实践中我们一般采用多Hash函数的方式，这又分为两类，

第一类：多Hash函数映射到多Hash表.示意图如下面所示，通过计算每个哈希函数的值，将其更新到每个哈希表，验证阶段，重新计算每个哈希函数值，假如有一个值在其对应的表中不为1则返回验证元素不在集合的结果。如果都为1，则可能存在集合中。 

第二种：多Hash函数使用单一Hash表，如下图所示，规模上差不多与上面的累加在一起相同， 这种情况下只需要管理一个Hash表即可，所以实现上更简单一些。

对于布隆过滤器，选择多大的负载比例以及多少个哈希函数都有较为系统的科学计算，保证在一定的配置下，错误率能够达到最低。这里仅仅给出结论，感兴趣的可以参考维基百科相关介绍页面：(https://en.wikipedia.org/wiki/Bloom_filter)，毕竟我们只是为了更好的应用过滤器。

对于固定的m/n的话， 最佳的哈希函数选择为：

其中m=表中bit位的数量， n代表插入的元素个数，当m/n=10的时候我们需要的k元素数量为7，也就是7个哈希函数才能实现一个比较低的错误率。另外一种偷懒的方式，可以通过一个在线的布隆计算器来查询我们需要的的配置：https://hur.st/bloomfilter/  

在上面的网站上我们只需要输入预估插入的元素个数，比如我们输入1百万个元素，设置对应的容错率，这里我们设置为1%也就是允许出现1%的错误率，得到的哈希函数个数为K=7，也就是需要设置7个Hash函数，设置的比特位容量约为10倍的存储数量，即使这样我们也就只使用1M左右的空间。

这就是布隆过滤器存在的主要意义，提供在极端数据量下仍旧保持可用的一种集合判断方案。假如你不知道有这些优雅的解决方案，那在选择解决方案的时候就可能会陷入直觉陷阱，往往得到的结果即无法满足预期的效果，又可能会占用太多的服务资源，这也是为什么我推荐大家多去学习和掌握一些数据结构和算法的目的。

4. 程序实现

关于布隆过滤器的实现，由于篇幅有限，我会省略很多的细节，这些细节在生产环境中可能依赖于不同的使用场景而不同。举个简单的例子，假如对于插入的元素数量未知，那是否需要考虑可扩展性问题，又如何更高效的实现数据的迁移。

以下代码为Golang语言编写实现，其他语言逻辑处理基本相似。首先我们来定义一个数据结构

这里为了简单起见，使用了布尔类型来代替比特（1个字节vs1个比特），正常情况下应该设计为比特结构，只是比特位操作上还需要进行一些与或操作，不太直观。创建数据结构的两个参数分别是预估的容量size以及代表需要需要多少哈希函数的参数k。如果插入元素数量可以估计的话，可以利用上面给出的参考网站获取设置参数。

另外，程序中使用的哈希算法是murmur3算法，这是一种非密码学哈希算法（易于遭受HashDOS攻击），但实现上比较简单，性能也很高，主要用于一些查询和定位服务中使用， 比如memcached, redis, hive等在某些组件实现上都有采用这种高效的哈希算法。

数据结构方法有两个核心方法分别是：

AddItem：”增加“元素到集合中， 这里的增加并非真正的将元素放入列表这样的操作，只是设置对应的bitset位操作。

Verify ：验证元素是否属于集合，当元素不存在元素的时候，返回false, 但是当元素返回true的时候，仍旧有可能没有存在集合中，其错误率与设置k,size的参数有关系

核心代码就是这么简单，非常具有可操作性，可以根据需要进行扩展实现。

5. 其他使用场景参考

另外一些典型的生产环境中使用布隆过滤器的实例，列举如下：

1. 一些交友软件，每次抓取一批推荐给用户前端，利用一个布隆过滤器来完成记录，每次检查是否已被推荐过

2. 视频网站，使用布隆过滤器来检查推荐的视频内容是否已经被推荐过。

3. 缓存优化，一般缓存使用LRU策略，只要最近使用过，就会被缓存起来，但是这样可能导致生僻资源占用缓存带宽的问题，可以通过前置一个布隆过滤器来完成二次检查，只有出现两次的才进行缓存

4. 流处理中元素的计数，可以估计存在多少独立的元素被处理过。

5. HBase使用布隆过滤器来避免一些无效的硬盘读取操作

6. 恶意域名监测，是否属于恶意域名

7. 爬虫系统设计，已经处理过的页面检查

这些应用场景，借助于布隆过滤器都可以极大的减少内存或者硬盘操作的执行时间，提升系统的处理容量，特别是大规模用户访问和使用的情况下，提供生产可用的一种解决方案。对于布隆过滤器的介绍就是这些，大家如果感兴趣的话可以扫描下面的二维码订阅我的公众号，我会在后续的文章中介绍更多实用又高效的数据结构和算法与大家分享。

感谢大家阅读,如果大家对与算法感兴趣，还可以订阅下面的微信公众号，第一时间接收我发布的更新。