redis专题06 布隆过滤器

文章目录

1. 1. 布隆过滤器是什么?
2. 2. redis中布隆过滤器基本使用
   1. 2.1. 环境准备
3. 3. 布隆过滤器实现原理
4. 4. 占用空间估计
5. 5. 应用场景
6. 6. 总结

灰常方便用redis的HyperLogLog来进行数值估数, 可以解决很多精确度不高的统计需求。

但是如果想知道某一个值是不是已经在HyperLogLog结构里面了，它就无能为力了，它只提供了pfadd, pfcount和pfmerge等方法，没有提供pfcontains这样类似的方法。

讲个使用场景，比如我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？

你会想到服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。问题是当用户量很大，每个用户看过的新闻又很多的情况下，这种方式，推荐系统的去重工作在性能上跟的上么？

实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行exists查询，当系统并发量很高时，数据库是很难扛住压力的。

你可能又想到了缓存，但是如此多的历史记录全部缓存起来，那得浪费多大存储空间啊？而且这个存储空间是随着时间线性增长，你撑得住一个月，你能撑得住几年么？但是不缓存的话，性能又跟不上，这该怎么办？

这时，布隆过滤器(Bloom Filter)闪亮登场了，它就是专门用来解决这种去重问题的。它在起到去重的同时，在空间上还能节省 90%`以上，只是稍微有那么点不精确，也就是有一定的误判概率。

数据量小时， 可以用redis提供的集合set去重;

当数据量很大，且没有很严格的精度要求时， 就可以用redis提供的布隆过滤器来去重，而且还能极大的节省空间, 所以在存储空间上相比set集合优势十分明显;

布隆过滤器是什么?

布隆过滤器可以理解为一个不怎么精确的set结构，当你使用它的contains方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。

当布隆过滤器说某个值存在时，这个值可能不存在；
当它说不存在时，那就肯定不存在。打个比方，当它说不认识你时，肯定就不认识；当它说见过你时，可能根本就没见过面，不过因为你的脸跟它认识的人中某脸比较相似 (某些熟脸的系数组合)，所以误判以前见过你。

套在上面的使用场景中，布隆过滤器能准确过滤掉那些已经看过的内容，那些没有看过的新内容，它也会过滤掉极小一部分 (误判)，但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。

redis中布隆过滤器基本使用

环境准备

redis官方提供的布隆过滤器到了redis4.0提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到Redis Server中，给Redis提供了强大的布隆去重功能。

➜  02 docker exec -it myredis redis-cli --version
redis-cli 4.0.11
➜  02 docker pull redislabs/rebloom
➜  02 docker run -itd --name redisbloom -p6378:6379 redislabs/rebloom
➜  02 docker exec -it redisbloom redis-cli
127.0.0.1:6379>

布隆过滤器有二个基本指令，bf.add添加元素，bf.exists查询元素是否存在，它的用法和set集合的sadd和 sismember差不多。注意bf.add只能一次添加一个元素，如果想要一次添加多个，就需要用到bf.madd指令。同样如果需要一次查询多个元素是否存在，就需要用到bf.mexists指令。

127.0.0.1:6379> bf.add visitor user1
(integer) 1

# 添加的元素如果原来不存在 则返回1， 否则返回0
127.0.0.1:6379> bf.add visitor user1
(integer) 0

# bf.madd 返回值为数组
127.0.0.1:6379> bf.madd visitor user2 user3
1) (integer) 1
2) (integer) 1

# bf.exists 如果存在返回1， 否则返回0;
127.0.0.1:6379> bf.exists visitor user1
(integer) 1

#bf.mexists 返回一个数组， 1表示存在， 0表示不存在;
127.0.0.1:6379> bf.mexists visitor user1 user2 user3
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379>

布隆过滤器判断元素是否存在时，存在一定的误差， 可以通过调节布隆过滤器参数来降低误差值， 在没有设置误差参数值时，redis会启用布隆过滤器的默认参数，它在第一次add的时候自动创建。用户可以在add之前使用bf.reserve指令显式自定义布隆过滤器参数值。如果对应的key已经存在，bf.reserve会报错。bf.reserve有三个参数，分别是key, error_rate和initial_size。错误率越低，需要的空间越大。initial_size参数表示预计放入的元素数量，当实际数量超出这个数值时，误判率会上升。所以需要提前设置一个较大的数值避免超出导致误判率升高。

默认的error_rate是0.01，默认的initial_size是100。

布隆过滤器的initial_size估计的过大，会浪费存储空间，估计的过小，就会影响准确率，用户在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出估计值很多。

布隆过滤器的error_rate越小，需要的存储空间就越大，对于不需要过于精确的场合，error_rate设置稍大一点也无伤大雅。比如在新闻去重上而言，误判率高一点只会让小部分文章不能让合适的人看到，文章的整体阅读量不会因为这点误判率就带来巨大的改变。

布隆过滤器实现原理

每个布隆过滤器对应到redis的数据结构里面就是一个大型的位数组和几个不一样的无偏hash函数。

无偏就是能够把元素的hash值算得比较均匀。

向布隆过滤器中添加key时，会使用多个hash函数对key进行hash算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置。再把位数组的这几个位置都置为1就完成了add操作。

       key1     key2
       /  |    /  \
      /   |   /    \
     /    |  /      \
0 0 1 0 0 1  1 0 0 0 1 0 0 0

向布隆过滤器询问key是否存在时，跟add一样，也会把hash的几个位置都算出来，看看位数组中这几个位置是否都为1，只要有一个位为0，那么说明布隆过滤器中这个key不存在。如果都是1，这并不能说明这个key就一定存在，只是极有可能存在，因为这些位被置为1可能是因为其它的key存在所致。如果这个位数组比较稀疏，判断正确的概率就会很大，如果这个位数组比较拥挤，判断正确的概率就会降低。

使用时不要让实际元素远大于初始化大小，当实际元素开始超出初始化大小时，应该对布隆过滤器进行重建，重新分配一个size更大的过滤器，再将所有的历史元素批量add进去 (这就要求我们在其它的存储器中记录所有的历史元素)。因为error_rate不会因为数量超出就急剧增加，这就给我们重建过滤器提供了较为宽松的时间。

占用空间估计

布隆过滤器有两个参数，第一个是预计元素的数量n，第二个是错误率f。公式根据这两个输入得到两个输出，第一个输出是位数组的长度l，也就是需要的存储空间大小(bit)，第二个输出是hash函数的最佳数量k。hash函数的数量也会直接影响到错误率，最佳的数量会有最低的错误率。布隆过滤器的空间占用有一个简单的计算公式，

k=0.7*(l/n)  # 约等于
f=0.6185^(l/n)  # ^ 表示次方计算，也就是 math.pow

从公式中可以看出

位数组相对越长(l/n)，错误率f越低，这个和直观上理解是一致的
位数组相对越长(l/n)，hash函数需要的最佳数量也越多，影响计算效率 当一个元素平均需要1个字节(8bit)的指纹空间时(l/n=8)，错误率大约为2%`

错误率为10%，一个元素需要的平均指纹空间为4.792个bit，大约为5bit
错误率为1%，一个元素需要的平均指纹空间为9.585个bit，大约为10bit
错误率为0.1%，一个元素需要的平均指纹空间为14.377个 bit，大约为15bit

你也许会想，如果一个元素需要占据15个bit，那相对set集合的空间优势是不是就没有那么明显了？

这里需要明确的是，set中会存储每个元素的内容，而布隆过滤器仅仅存储元素的指纹。元素的内容大小就是字符串的长度，它一般会有多个字节，甚至是几十个上百个字节，每个元素本身还需要一个指针被set集合来引用，这个指针又会占去4个字节或8个字节，取决于系统是 32bit 还是 64bit。而指纹空间只有接近2个字节，所以布隆过滤器的空间优势还是非常明显的。

当实际元素超出预计元素时，错误率会有多大变化，它会急剧上升么，还是平缓地上升，这就需要另外一个公式，引入参数t表示实际元素和预计元素的倍数t

f=(1-0.5^t)^k  # 极限近似，k 是 hash 函数的最佳数量

当t增大时，错误率，f也会跟着增大，分别选择错误率为10%,1%,0.1%的k值，实验得知

错误率为10%时，倍数比为2时，错误率就会升至接近40%，这个就比较危险了
错误率为1%时，倍数比为2时，错误率升至15%，也挺可怕的
错误率为0.1%，倍数比为2时，错误率升至5%，也比较悬了

应用场景

在爬虫系统中，我们需要对URL进行去重，已经爬过的网页就可以不用爬了。但是URL太多了，几千万几个亿，如果用一个集合装下这些URL地址那是非常浪费空间的。这时候就可以考虑使用布隆过滤器。它可以大幅降低去重存储消耗，只不过也会使得爬虫系统错过少量的页面。

布隆过滤器在NoSQL数据库领域使用非常广泛，我们平时用到的HBase、Cassandra还有LevelDB、RocksDB内部都有布隆过滤器结构，布隆过滤器可以显著降低数据库的IO请求数量。当用户来查询某个row时，可以先通过内存中的布隆过滤器过滤掉大量不存在的row请求，然后再去磁盘进行查询。

邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，因为用了这个过滤器，所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中，这个就是误判所致，概率很低。

总结

• 布隆过滤（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。本文引入了其基本原理，并给出实例分析;
• 它的优点是空间效率和查询时间都远远超过一般的算法，布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

• 缺点是有一定的误识别率（假正例False positives，即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例False negatives，如果某个元素确实没有在该集合中，那么Bloom Filter 是不会报告该元素存在于集合中的，所以不会漏报）。

• 目前我们知道布隆过滤器可以支持add和isExist操作，那么delete操作可以么，很难实现， 如位数组中的bit位 被两个值共同覆盖的话，一旦你删除其中一个值而将其置位0，那么下次判断另一个值是否存在的话，会直接返回false，而实际上你并没有删除它。如何解决这个问题，答案是计数删除。但是计数删除需要存储一个数值，而不是原先的bit位，会增大占用的内存大小。这样的话，增加一个值就是将对应索引槽上存储的值加一，删除则是减一，判断是否存在则是看值是否大于0。