Redis之_层峦叠嶂_布隆过滤器
前言
Github：https://github.com/HealerJean
1、引入
上一节我们学会了使用
HyperLogLog数据结构来进行估数，它非常有价值，可以解决 很多精确度不高的统计需求。但是如果我们想知道某一个值是不是已经在
HyperLogLog结构里面了，它就无能为力 了，它只提供了pfadd和pfcount方法，没有提供pfcontains这种方法。
问题1：我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的?
答案：你会想到服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。
问题2：问题是当用户量很大，每个用户看过的新闻又很多的情况下，这种方式，推荐系统的去重工作在性能上跟的上么?
答案：实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行 exists 查 询，当系统并发量很高时，数据库是很难扛住压力的。
问题3：不使用数据库，那使用什么呢？
答案：你可能又想到了缓存，但是如此多的历史记录全部缓存起来，那得浪费多大存储空间啊?而且这个存储空间是随着时间线性增长，你撑得住一个月，你能撑得住几年么? 但是不缓存的话，性能又跟不上，这该怎么办 ?
问题4：缓存都扛不住，那还能用啥呢？
这时，布隆过滤器 (Bloom Filter) 闪亮登场了，它就是专门用来解决这种去重问题的。
问题5：为什么用布隆过滤器呢？
答案： 它在起到去重的同时，在空间上还能节省 90% 以上，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。
问题6：布隆过滤器有什么缺点呢？
答案：只是稍有那么点不精确，也就是有 一定的误判概率
2、布隆过滤器是什么？
布隆过滤器可以理解为一个不怎么精确的
set结构，当你使用它的contains方法判断某 个对象是否存在时，它可能会误判。1、但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率
2、当布隆过滤器说某个值存在时，这个值可能不存在，当它说不存在时，那就肯定不存在。
套在上面的使用场景中，布隆过滤器能准确过滤掉那些已经看过的内容，那些没有看过 的新内容，它也会过滤掉极小一部分 (误判)，但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。
3、Redis 中的布隆过滤器
Redis官方提供的布隆过滤器到了Redis 4.0提供了插件功能之后才正式登场。布隆过滤 器作为一个插件加载到Redis Server中，给Redis提供了强大的布隆去重功能。(我这里没有进行安装，所以就看着文档过一下吧，以后有需要再回来看)
| 命令 | 说明 |
|---|---|
bf.add |
添加元素 |
bf.madd |
批量添加元素 |
bf.exists |
查询元素是否存在 |
bf.mexists |
批量查询元素是否存在 |
3.1、默认的布隆过滤器
在我们第一次
add的时候自 动创建默认参数的布隆过滤器默 认的
error_rate是0.01，默认的initial_size是100。
127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2
(integer) 1
127.0.0.1:6379> bf.exists codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0
127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
3.2、自定义的布隆过滤器
Redis其实还提供了自定义参数的布隆过滤器，需要我们在add之前使用bf.reserve指令显式创建。如果对应的key已经存在，bf.reserve会报错。bf.reserve有三个参数，分别⬤
key⬤
error_rate：错误率越低，需要的空间越大。⬤
initial_size参数表示预计放入的元素数量，当实际数量超出这个数值时，误判率会上升，所以需要提前设置一个较大的数值避免超出导致误判率升高。
3.3、注意事项
⬤ 布隆过滤器的 initial_size 估计的过大，会浪费存储空间，估计的过小，就会影响准确率，用户在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出估计值很多。
⬤ 布隆过滤器的 error_rate 越小，需要的存储空间就越大，对于不需要过于精确的场合， error_rate 设置稍大一点也无伤大雅。（比如在新闻去重上而言，误判率高一点只会让小部分文章不能让合适的人看到，文章的整体阅读量不会因为这点误判率就带来巨大的改变）
4、布隆过滤器的原理
每个布隆过滤器对应到
Redis的数据结构里面就是一个大型的位数组和几个不一样的无偏hash函数。所谓无偏就是能够把元素的hash值算得比较均匀。
4.1、add：添加元素
向布隆过滤器中添加
key时，会使用多个hash函数对key进行hash算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置。再把位数组的这几个位置都置为1就完成了add操作。
4.2、exists：校验元素是否存在
向布隆过滤器询问
key是否存在时，跟add一样，也会把hash的几个位置都算出 来，看看位数组中这几个位置是否都位11、只要有一个位为
0，那么说明布隆过滤器中这个key不存在。2、如果都是
1，这并不能说明这个key就一定存在，只是极有可能存在，因为这 些位被置为1可能是因为其它的key存在所致。如果这个位数组比较稀疏，这个概率就会很大，如果这个位数组比较拥挤，这个概率就会降低。具体的概率计算公式比较复杂，感兴 趣可以阅读扩展阅读，非常烧脑，不建议读者细看。
4.3、实际元素超出初始化大小怎么办？
使用时不要让实际元素远大于初始化大小，由于
error_rate不会因为数量超出就急剧增加（看下面的图表），这就给我们重建过滤器提供了较为宽松的时间，所以当实际元素开始超出初始化大小时，应该对布隆过滤器进行重建，重新分配一个size更大的过滤器，再将所有的历史元素批量add进去注意： 这就要求我们在其它的存储器中记录所有的历史元素，所以尽量一开始就尽量想好多大合适
4.4、空间占用估计
布隆过滤器的空间占用有一个简单的计算公式，但是推导比较繁琐，这里就省去推导过程了，直接引出计算公式
布隆过滤器有两个参数，第一个是预计元素的数量
n，第二个是错误率f。公式根据这 两个输入得到两个输出，第一个输出是位数组的长度L，也就是需要的存储空间大小(bit)， 第二个输出是hash函数的最佳数量k。hash函数的数量也会直接影响到错误率，最佳的数量会有最低的错误率。
| 输入 | 说明 |
|---|---|
n |
预计元素的数量 n |
f |
错误率 f |
| 输出 | 说明 |
|---|---|
L |
位数组的长度 L，也就是需要的存储空间大小 (bit) |
k |
hash 函数的最佳数量 k |
k = 0.7*(1/n) # 约等于
f = 0.6185^(L/n) #表示次方计算，也就是 math.pow
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
4.4.1、总结
问题：你也许会想，如果一个元素需要占据 15 个 bit，那相对 set 集合的空间优势是不是就 没有那么明显了?
答案：这里需要明确的是，set 中会存储每个元素的内容，而布隆过滤器仅仅存储元素的指纹。
1、元素的内容大小就是字符串的长度，它一般会有多个字节，甚至是几十个上 百个字节
2、每个元素本身还需要一个指针被 set 集合来引用，这个指针又会占去 4 个字节 或 8 个字节，取决于系统是 32bit 还是 64bit。而指纹空间只有接近 2 个字节，所以布隆过滤器的空间优势还是非常明显的。
问题：计算太麻烦了，有没有一个计算的工具呢？
https://krisives.github.io/bloom-calculator/
4.4.2、实际元素超出时，误判率会怎样变化
当实际元素超出预计元素时，错误率会有多大变化，它会急剧上升么，还是平缓地上升，这就需要另外一个公式，引入参数
t表示实际元素和预计元素的倍数
f = (1-0.5^t) ^ k # 极限近似，k 是 hash 函数的最佳数量
当 t 增大时，错误率，f 也会跟着增大，分别选择错误率为 10% ,1%, 0.1% 的 k 值，画出它的曲线进行直观观察。
从这个图中可以看出曲线还是比较陡峭的
1、错误率为 10% 时，倍数比为 2 时，错误率就会升至接近 40%，这个就比较危险了
2、错误率为 1% 时，倍数比为 2 时，错误率升至 15%，也挺可怕的
3、错误率为 0.1%，倍数比为 2 时，错误率升至 5%，也比较悬了
5、布隆过滤器的场景
1、邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，因为用了这个过滤器，所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中，这个就是误判所致，概率很低
2、布隆过滤器可以显著降低数据库的 IO 请求数量。当用户来查询某个 row 时，可以先通过内存中的布隆过滤器过滤掉大量不存在的 row 请求，然后再去磁盘进行查询。
6、其他布隆过滤器
6.1、com.google.guava
<dependencies>
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>
</dependencies>
public class BloomFilterTest {
private static final int capacity = 1000000;
private static final int key = 999998;
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), capacity);
static {
for (int i = 0; i < capacity; i++) {
bloomFilter.put(i);
}
}
public static void main(String[] args) {
/*返回计算机最精确的时间，单位微妙*/
long start = System.nanoTime();
if (bloomFilter.mightContain(key)) {
System.out.println("成功过滤到" + key);
}
long end = System.nanoTime();
System.out.println("布隆过滤器消耗时间:" + (end - start));
int sum = 0;
for (int i = capacity + 20000; i < capacity + 30000; i++) {
if (bloomFilter.mightContain(i)) {
sum = sum + 1;
}
}
System.out.println("错判率为:" + sum);
}
}
// 成功过滤到999998
// 布隆过滤器消耗时间:215518
// 错判率为:318
//可以看到，100w个数据中只消耗了约0.2毫秒就匹配到了key，速度足够快。然后模拟了1w个不存在于布隆过滤器中的key，匹配错误率为318/10000，也就是说，出错率大概为3%，跟踪下BloomFilter的源码发现默认的容错率就是0.03：
public static <T> BloomFilter<T> create(Funnel<T> funnel, int expectedInsertions /* n */) {
return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}
