这些知识点你会吗？redis的分布式布隆过滤器含答案解析

2023-01-07 12:16:35

问题

老顾先来举个常会问到的面试题：现有50亿个电话号码，现有10万个电话号码，如何要快速准确的判断这些电话号码是否已经存在？

上面的问题可以细化一下，也就是50亿个电话号码在数据库中，现在要快速、准确的判断提供的10万个电话号码是否存在。

我们小伙伴们是否脑子中会有以下方案：

实际项目中也会遇到类似的问题，如垃圾邮件过滤、网络爬虫重复url检测等，本质就是判断数据存不存在一个大的集合中。

那如何去解决呢？这就是我们今天老顾要介绍的布隆过滤器方案，我们继续往下看。

#布隆过滤器

布隆过滤器是一种类似set的数据结构，只是不太准确，当判断元素是否存在时返回结果存在但真实不一定存在；当返回不存在时肯定是不存在，所以判断去重时有一定的误判概率。

当然，误判只会发生在过滤器没有添加过的元素，对于添加过的元素不会发生误判。

特点：高效地插入和查询，占用空间少，返回的结果是不确定性的。

#布隆过滤器原理

这个是由柏顿.布隆在1970年提出，用很小的空间，解决上述的类似问题。

实现原理就是我们需要一个很长的二进制数组（也叫向量）；在添加数据时，使用多个hash函数对key进行hash运算得到一个索引值（即二进制数组的索引值）

上图中，下面是很长的二进制数组，第二层就是多个hash函数，再上面就是数据。

上图中，每个数据经过多个hash函数计算，得到索引值，并把二进制数组对应的索引值那边设置为1，我们发现经过三次hash，就会在三个索引的地方设置为1，也就是代表此数据存在。

#布隆过滤器误差

空间占用

布隆过滤器的空间占用有一个简单的计算公式，但推导比较繁琐。布隆过滤器有两个参数，预计元素数量n，错误率f，公式得到两个输出，位数组长度L（即存储空间大小bit），hash函数的最佳数量k。

k = 0.7*(1/n)
f = 0.6185^(L/n)

实际元素超出时

以上小伙伴们只要知道会存在误差就行了，不需要强求是怎么计算的。

#Redis布隆过滤器的基本使用

在Redis中，布隆过滤器有两个基本命令，分别是：

bf.add：添加元素到布隆过滤器中，类似于集合的sadd命令，不过bf.add命令只能一次添加一个元素，如果想一次添加多个元素，可以使用bf.madd命令。
bf.exists：判断某个元素是否在过滤器中，类似于集合的sismember命令，不过bf.exists命令只能一次查询一个元素，如果想一次查询多个元素，可以使用bf.mexists命令。

#布隆过滤器的高级使用

上面的例子中使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次使用 bf.add 命令时自动创建的。Redis还提供了自定义参数的布隆过滤器，想要尽量减少布隆过滤器的误判，就要设置合理的参数。

在使用 bf.add 命令添加元素之前，使用bf.reserve 命令创建一个自定义的布隆过滤器。bf.reserve命令有三个参数，分别是：

key：键
error_rate：期望错误率，期望错误率越低，需要的空间就越大。
capacity：初始容量，当实际元素的数量超过这个初始化容量时，误判率上升。

比如：

如果对应的key已经存在时，在执行bf.reserve命令就会报错。如果不使用bf.reserve命令创建，而是使用Redis自动创建的布隆过滤器，默认的error_rate是 0.01，capacity是 100。

布隆过滤器的error_rate 越小，需要的存储空间就越大，对于不需要过于精确的场景，error_rate设置稍大一点也可以。布隆过滤器的capacity设置的过大，会浪费存储空间，设置的过小，就会影响准确率，所以在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。总之，error_rate和capacity都需要设置一个合适的数值。

#布隆过滤器的应用

解决缓存穿透的问题

一般情况下，**先查询缓存是否有该条数据，缓存中没有时，再查询数据库。**当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透。缓存穿透带来的问题是，当有大量请求查询数据库不存在的数据时，就会给数据库带来压力，甚至会拖垮数据库。

可以使用布隆过滤器解决缓存穿透的问题，把已存在数据的key存在布隆过滤器中。当有新的请求时，先到布隆过滤器中查询是否存在，如果不存在该条数据直接返回；如果存在该条数据再查询缓存查询数据库。

黑名单校验

发现存在黑名单中的，就执行特定操作。比如：识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中，再收到邮件时，判断邮件地址是否在布隆过滤器中即可。

#总结

今天老顾带着大家了解了redis布隆过滤器的原理以及应用场景；希望能给小伙伴带来帮助，谢谢！！