Redis应用⌚️——过滤器与限流

布隆过滤器

比如新闻客户端，在推送新的新闻时，要过滤掉已经看过这条新闻的用户。那用什么方法来过滤呢，你可能会想到缓存一个集合，但是当用户量很大的时候，所有用户的阅读历史集合将是一个非常庞大的数据。

如果你们没有为用户提供“足迹”这样的需求的话，上面所说的功能就可以利用布隆过滤器来实现。

布隆过滤器用来判断一个值是否不存在，但是不能完全准确的判断这个值是否一定存在，也就是会有误差，但是我们可以通过参数控制这个误差的概率。可以理解为一个不怎么精确的set结构，过滤时相当于contains方法。

在Java中，Guava里面提供了布隆过滤器的实现。

Redis中也提供了布隆过滤器的实现，在Redis 4.0后提供了布隆过滤器作为插件加入到Redis Server中。

使用bf.add bf.exists指令进行基础操作。

使用bf.madd``bf.mexists进行批量操作。

使用bf.reserve有三个参数key error_rate initial_size。

error_rate越低，所需的空间越大。

initial_size注意，要尽量设置的准确，一旦元素数量超过initial_size，误判率将会大幅度上升。

底层是使用一个大的数组和几个无偏hash函数来实现的，所谓无偏就是可能把hash值算得比较均匀。

当执行add时，使用几个hash函数分别算出来结果，每个结果对应一个位置，然后将数组这几个位置上的值都设成1。

当执行exists时，同样将传入的value通过上面的hash函数进行计算，在结果对应的几个位置上判断，如果各位上都是1，即证明这个值存在。

注意，证明值存在是会有误判的，因为存在可能两个不同的value，通过hash计算出来的结果是完全一致的。

所以只能保证value一定不存在，不能完全保证这个value存在。

当这个数组越大的时候，存储也越稀疏，判断的准确性就会更高，但是占用的空间也会更大。