上一节我们学会了使用HyperLogLog 数据结构来进行估数，它非常有价值，可以解决 很多精确度不高的统计需求。
但是如果我们想知道某一个值是不是已经在HyperLogLog 结构里面了，它就无能为力 了，它只提供了pfadd 和pfcount 方法，没有提供pfcontains 这种方法.
讲个使用场景，比如我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的?
你会想到服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。问题是当用户量很大，每个用户看过的新闻又很多的情况下，这种方式，推荐系统的去重工作在性能上跟的上么?
实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行exists 查 询，当系统并发量很高时，数据库是很难扛住压力的。
你可能又想到了缓存，但是如此多的历史记录全部缓存起来，那得浪费多大存储空间啊?而且这个存储空间是随着时间线性增长，你撑得住一个月，你能撑得住几年么?但是不缓存的话，性能又跟不上，这该怎么办?
这时，布隆过滤器(Bloom Filter) 闪亮登场了，它就是专门用来解决这种去重问题的。 它在起到去重的同时，在空间上还能节省90% 以上，只是稍微有那么点不精确，也就是有 一定的误判概率。
布隆过滤器是什么?
布隆过滤器可以理解为一个不怎么精确的set 结构，当你使用它的contains 方法判断某 个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合 理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。
当布隆过滤器说某个值存在时，这个值可能不存在;当它说不存在时，那就肯定不存 在。打个比方，当它说不认识你时，肯定就不认识;当它说见过你时，可能根本就没见过面，不过因为你的脸跟它认识的人中某脸比较相似(某些熟脸的系数组合)，所以误判以前见过你。
套在上面的使用场景中，布隆过滤器能准确过滤掉那些已经看过的内容，那些没有看过 的新内容，它也会过滤掉极小一部分(误判)，但是绝大多数新内容它都能准确识别。这样就 可以完全保证推荐给用户的内容都是无重复的。
Redis 中的布隆过滤器
Redis 官方提供的布隆过滤器到了Redis 4.0 提供了插件功能之后才正式登场。布隆过滤 器作为一个插件加载到Redis Server 中，给Redis 供了强大的布隆去重功能。
下面我们来体验一下Redis 4.0 的布隆过滤器，为了省去繁琐安装过程，我们直接用Docker 吧。
如果上面三条指令执行没有问题，下面就可以体验布隆过滤器了。
布隆过滤器基本使用
布隆过滤器有二个基本指令，bf.add 添加元素，bf.exists 查询元素是否存在，它的用法 和set 集合的sadd 和sismember 差不多。注意bf.add 只能一次添加一个元素，如果想要 一次添加多个，就需要用到bf.madd 指令。同样如果需要一次查询多个元素是否存在，就需 要用到bf.mexists 指令。
似乎很准确啊，一个都没误判。下面我们用Python 脚本加入很多元素，看看加到第几 个元素的时候，布隆过滤器会出现误判：
Java 客户端Jedis-2.x 没有提供指令扩展机制，所以你无法直接使用Jedis 来访问Redis Module 提供的bf.xxx 指令。RedisLabs 提供了一个单独的包JReBloom，但是它是基 于Jedis-3.0，Jedis-3.0 这个包目前还没有进入release，没有进入maven 的中央仓库，需要 在Github 上下载。在使用上很不方便，如果怕麻烦，还可以使用lettuce，它是另一个Redis 的客户端，相比Jedis 而言，它很早就支持了指令扩展。
执行上面的代码后，你会张大了嘴巴发现居然没有输出，塞进去了100000 个元素，还
是没有误判，这是怎么回事?如果你不死心的话，可以将数字再加一个0 试试，你会发现依 然没有误判。
原因就在于布隆过滤器对于已经见过的元素肯定不会误判，它只会误判那些没见过的元 素。所以我们要稍微改一下上面的脚本，使用bf.exists 去查找没见过的元素，看看它是不是 以为自己见过了。
运行后，我们看到了输出是214，也就是到第214 的时候，它出现了误判。
那如何来测量误判率呢?我们先随机出一堆字符串，然后切分为2 组，将其中一组塞入布隆过滤器，然后再判断另外一组的字符串存在与否，取误判的个数和字符串总量一半的百 分比作为误判率。
Java版:
public class BloomTest {
private String chars; {
StringBuilder builder = new StringBuilder(); for (int i = 0; i < 26; i++) {
builder.append((char) ('a' + i)); }
chars = builder.toString(); }
private String randomString(int n) { StringBuilder builder = new StringBuilder(); for (int i = 0; i < n; i++) {
int idx = ThreadLocalRandom.current().nextInt(chars.length());
builder.append(chars.charAt(idx)); }
return builder.toString(); }
private List<String> randomUsers(int n) { List<String> users = new ArrayList<>(); for (int i = 0; i < 100000; i++) {
users.add(randomString(64)); }
return users; }
public static void main(String[] args) {
BloomTest bloomer = new BloomTest();
List<String> users = bloomer.randomUsers(100000);
List<String> usersTrain = users.subList(0, users.size() / 2); List<String> usersTest = users.subList(users.size() / 2, users.size());
total users 100000 all trained
628 50000
可以看到误判率大约1% 多点。你也许会问这个误判率还是有点高啊，有没有办法降低 一点?答案是有的。
我们上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次add 的时候自 动创建。Redis 其实还供了自定义参数的布隆过滤器，需要我们在add 之前使用bf.reserve 指令显式创建。如果对应的key 已经存在，bf.reserve 会报错。bf.reserve 有三个参数，分别是key, error_rate 和initial_size。错误率越低，需要的空间越大。initial_size 参数表示预计放 入的元素数量，当实际数量超出这个数值时，误判率会上升。
所以需要提
前设置一个较大的数值避免超出导致误判率升高。如果不使用bf.reserve，默 认的error_rate 是0.01，默认的initial_size 是100。
接下来我们使用bf.reserve 改造一下上面的脚本:
运行一下，等待约1 分钟，输出如下:
total users 100000
all trained
6 50000
我们看到了误判率大约0.012%，比预计的0.1% 低很多，不过布隆的概率是有误差 的，只要不比预计误判率高太多，都是正常现象。
注意事项
布隆过滤器的initial_size 估计的过大，会浪费存储空间，估计的过小，就会影响准确 率，用户在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避 免实际元素可能会意外高出估计值很多。
布隆过滤器的error_rate 越小，需要的存储空间就越大，对于不需要过于精确的场合，error_rate 设置稍大一点也无伤大雅。比如在新闻去重上而言，误判率高一点只会让小部分文 章不能让合适的人看到，文章的整体阅读量不会因为这点误判率就带来巨大的改变。
布隆过滤器的原理
学会了布隆过滤器的使用，下面有必要把原理解释一下，不然读者还会继续蒙在鼓里。
每个布隆过滤器对应到Redis 的数据结构里面就是一个大型的位数组和几个不一样的无 偏hash 函数。所谓无偏就是能够把元素的hash 值算得比较均匀。
向布隆过滤器中添加key 时，会使用多个hash 函数对key 进行hash 算得一个整数索 引值然后对位数组长度进行取模运算得到一个位置，每个hash 函数都会算得一个不同的位 置。再把位数组的这几个位置都置为1 就完成了add 操作。
向布隆过滤器询问key 是否存在时，跟add 一样，也会把hash 的几个位置都算出 来，看看位数组中这几个位置是否都位1，只要有一个位为0，那么说明布隆过滤器中这个key 不存在。如果都是1，这并不能说明这个key 就一定存在，只是极有可能存在，因为这 些位被置为1 可能是因为其它的key 存在所致。如果这个位数组比较稀疏，这个概率就会很大，如果这个位数组比较拥挤，这个概率就会降低。具体的概率计算公式比较复杂，感兴 趣可以阅读扩展阅读，非常烧脑，不建议读者细看。
使用时不要让实际元素远大于初始化大小，当实际元素开始超出初始化大小时，应该对 布隆过滤器进行重建，重新分配一个size 更大的过滤器，再将所有的历史元素批量add 进 去(这就要求我们在其它的存储器中记录所有的历史元素)。因为error_rate 不会因为数量超 出就急剧增加，这就给我们重建过滤器提供了较为宽松的时间。
空间占用估计
布隆过滤器的空间占用有一个简单的计算公式，但是推导比较繁琐，这里就省去推导过
程了，直接引出计算公式
布隆过滤器有两个参数，第一个是预计元素的数量n，第二个是错误率f。公式根据这 两个输入得到两个输出，第一个输出是位数组的长度l，也就是需要的存储空间大小(bit)， 第二个输出是hash 函数的最佳数量k。hash 函数的数量也会直接影响到错误率，最佳的数 量会有最低的错误率。
从公式中可以看出
1、位数组相对越长(l/n)，错误率f 越低，这个和直观上理解是一致的
2、位数组相对越长(l/n)，hash 函数需要的最佳数量也越多，影响计算效率
3、当一个元素平均需要 1个字节 (8bit)的指纹空间时 (l/n=8)，错误率大约为 2%
4、错误率为 10%，一个元素需要的平均指纹空间为 4.792个 bit，大约为 5bit
5、错误率为 1%，一个元素需要的平均指纹空间为 9.585个 bit，大约为 10bit
6、错误率为 0.1%，一个元素需要的平均指纹空间为 14.377个 bit，大约为 15bit
你也许会想，如果一个元素需要占据15 个bit，那相对set 集合的空间优势是不是就 没有那么明显了?这里需要明确的是，set 中会存储每个元素的内容，而布隆过滤器仅仅存 储元素的指纹。元素的内容大小就是字符串的长度，它一般会有多个字节，甚至是几十个上 百个字节，每个元素本身还需要一个指针被set 集合来引用，这个指针又会占去4 个字节 或8 个字节，取决于系统是32bit 还是64bit。而指纹空间只有接近2 个字节，所以布隆 过滤器的空间优势还是非常明显的。
如果读者觉得公式计算起来太麻烦，也没有关系，有很多现成的网站已经支持计算空间 占用的功能了，我们只要把参数输进去，就可以直接看到结果，比如布隆计算器。
实际元素超出时，误判率会怎样变化
当实际元素超出预计元素时，错误率会有多大变化，它会急剧上升么，还是平缓地上
升，这就需要另外一个公式，引入参数t 表示实际元素和预计元素的倍数t
当t 增大时，错误率，f 也会跟着增大，分别选择错误率为10%,1%,0.1% 的k 值，画
出它的曲线进行直观观察。
从这个图中可以看出曲线还是比较陡峭的
1、错误率为10% 时，倍数比为2 时，错误率就会升至接近40%，这个就比较危险了
2、错误率为1% 时，倍数比为2 时，错误率升至15%，也挺可怕的
3、错误率为0.1%，倍数比为2 时，错误率升至5%，也比较悬了
用不上 Redis4.0 怎么办?
Redis 4.0 之前也有第三方的布隆过滤器lib 使用，只不过在实现上使用redis 的位图来 实现的，性能上也要差不少。比如一次exists 查询会涉及到多次getbit 操作，网络开销相比 而言会高出不少。另外在实现上这些第三方lib 也不尽完美，比如pyrebloom 库就不支持重 连和重试，在使用时需要对它做一层封装后才能在生产环境中使用。
1、Python Redis Bloom Filter 2、Java Redis Bloom Filter
布隆过滤器的其它应用
在爬虫系统中，我们需要对URL 进行去重，已经爬过的网页就可以不用爬了。但是URL 太多了，几千万几个亿，如果用一个集合装下这些URL 地址那是非常浪费空间的。这 时候就可以考虑使用布隆过滤器。它可以大幅降低去重存储消耗，只不过也会使得爬虫系统 错过少量的页面。
布隆过滤器在NoSQL 数据库领域使用非常广泛，我们平时用到的HBase、Cassandra 还有LevelDB、RocksDB 内部都有布隆过滤器结构，布隆过滤器可以显著降低数据库的IO 请求数量。当用户来查询某个row 时，可以先通过内存中的布隆过滤器过滤掉大量不存在的row 请求，然后再去磁盘进行查询。
邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，因为用了这个过滤器，所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中，这个就是误判所致，概率很低。
扩展阅读
布隆过滤器的原理涉及到较为复杂的数学知识，感兴趣可以阅读下面的链接文章继续深入了解内部原理:布隆过滤器。
同样，如果你是个数学学渣，那建议你谨慎观看，要注意保护好自己的24K钛合金狗眼，避免闪瞎。
网友评论