江苏龙网

  1. 首页 > 人文 > >

那些年向前冲 大厂二面：Redis的分布式布隆过滤器是什么原理？

欢迎关注头条号：老顾聊技术
精品原创技术分享 ， 知识的组装工
问题老顾先来举个常会问到的面试题：现有50亿个电话号码 ， 现有10万个电话号码 ， 如何要快速准确的判断这些电话号码是否已经存在？
上面的问题可以细化一下 ， 也就是50亿个电话号码在数据库中 ， 现在要快速、准确的判断提供的10万个电话号码是否存在 。
我们小伙伴们是否脑子中会有以下方案：
1、通过数据库查询：实现快速有点难 。 2、数据预放到内存集合中：50亿*8字节大约40G ， 内存太大了 。实际项目中也会遇到类似的问题 ， 如垃圾邮件过滤、网络爬虫重复url检测等 ， 本质就是判断数据存不存在一个大的集合中 。
那如何去解决呢？这就是我们今天老顾要介绍的布隆过滤器方案 ， 我们继续往下看 。
布隆过滤器布隆过滤器是一种类似set的数据结构 ， 只是不太准确 ， 当判断元素是否存在时返回结果存在但真实不一定存在；当返回不存在时肯定是不存在 ， 所以判断去重时有一定的误判概率 。
当然 ， 误判只会发生在过滤器没有添加过的元素 ， 对于添加过的元素不会发生误判 。
特点：高效地插入和查询 ， 占用空间少 ， 返回的结果是不确定性的 。
布隆过滤器原理这个是由柏顿.布隆在1970年提出 ， 用很小的空间 ， 解决上述的类似问题 。
实现原理就是我们需要一个很长的二进制数组（也叫向量）；在添加数据时 ， 使用多个hash函数对key进行hash运算得到一个索引值（即二进制数组的索引值）
布隆过滤器误差空间占用布隆过滤器的空间占用有一个简单的计算公式 ， 但推导比较繁琐 。 布隆过滤器有两个参数 ， 预计元素数量n ， 错误率f ， 公式得到两个输出 ， 位数组长度L（即存储空间大小bit） ， hash函数的最佳数量k 。
k=0.7*(1/n)
f=0.6185^(L/n)
1、位数组相对长度越长 ， 错误率越低；2、位数组相对长度越长 ， 需要的hash函数越多；3、当一个元素平均需要一个字节（8bit）的指纹空间时（L/n=8) ， 错误率大约为2% 。 实际元素超出时f=(1-0.5^t)^k#t为实际元素与预计元素的倍数1、当错误率为10%时 ， 倍数比为2时 ， 错误率接近40%；2、当错误率为1% ， 倍数比为2时 ， 错误率15%；3、当错误率为0.1% ， 倍数为2时 ， 错误率5%以上小伙伴们只要知道会存在误差就行了 ， 不需要强求是怎么计算的
Redis布隆过滤器的基本使用在Redis中 ， 布隆过滤器有两个基本命令 ， 分别是：
bf.add：添加元素到布隆过滤器中 ， 类似于集合的sadd命令 ， 不过bf.add命令只能一次添加一个元素 ， 如果想一次添加多个元素 ， 可以使用bf.madd命令 。 bf.exists：判断某个元素是否在过滤器中 ， 类似于集合的sismember命令 ， 不过bf.exists命令只能一次查询一个元素 ， 如果想一次查询多个元素 ， 可以使用bf.mexists命令 。 >bf.addone-more-filterfans1(integer)1>bf.addone-more-filterfans2(integer)1>bf.existsone-more-filterfans3(integer)1>bf.existsone-more-filterfans4(integer)0>bf.maddone-more-filterfans4fans5fans61)(integer)12)(integer)13)(integer)1>bf.mexistsone-more-filterfans4fans5fans6fans71)(integer)12)(integer)13)(integer)1布隆过滤器的高级使用上面的例子中使用的布隆过滤器只是默认参数的布隆过滤器 ， 它在我们第一次使用bf.add命令时自动创建的 。 Redis还提供了自定义参数的布隆过滤器 ， 想要尽量减少布隆过滤器的误判 ， 就要设置合理的参数 。


推荐阅读


上一篇：美国|美国卫生部长访台，释放战略转变信号？

下一篇：ZAKER生活 并不是盐，若你爱吃，再多降压药也没用，高血压的“祸首”发现了