觉得对你有益的小伙伴记住点个赞+关注

后续完好内容持续更新中

期望一起交流的欢迎发邮件至javalyhn@163.com

小伙伴们咱们好，今日介绍BloomFilter布隆过滤器。信任咱们对BloomFilter必定不陌生，可是或许仅仅知道姓名，并不知道原理并且没有动手去放到自己的项目中。

今日带咱们一套打通BloomFilter，如有补充，欢迎评论或者私信！！

1. 事例

现在有50亿个用户id，给你10万个用户id，怎么判别这10万个用户id是否存在于这50亿个中。

此时，或许你有两种处理方案

  1. 数据库查询：用数据库查询要想实现这么多数据快速查询有点困难
  2. 数据预存放到内存中：50亿*8字节大约40G，内存占用太大了

那咋实现呢？

2. 什么是BloomFilter

布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的。

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理
它实际上是一个很长的二进制数组+一系列随机hash算法映射函数，主要用于判别一个元素是否在调集中。

通常咱们会遇到许多要判别一个元素是否在某个调集中的事务场景，一般想到的是将调集中所有元素保存起来，然后通过比较确定。 链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。

可是随着调集中元素的增加，咱们需求的存储空间也会出现线性增长，终究到达瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n),O(logn),O(1)。这个时分，布隆过滤器（Bloom Filter）就应运而生。

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

一句话便是由一个初值都为0的bit数组和多个哈希函数构成，用来快速判别某一个数据是否存在。本质便是判别具体数据存不存在一个大的调集中。

布隆过滤器是一种类似set的数据结构，仅仅计算成果不太精确。

3. 在centos7下布隆过滤器2种装置方法

3.1 采用docker装置RedisBloom，推荐

Redis 在 4.0 之后有了插件功用（Module），能够运用外部的扩展功用， 能够运用 RedisBloom 作为 Redis 布隆过滤器插件。

docker run -p 6379:6379 –name=redis6379bloom -d redislabs/rebloom

docker exec -it redis6379bloom /bin/bash

redis-cli

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

3.2 编译装置

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

3.3 布隆过滤器常用操作指令

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

bf.reserve filter 0.01 100
bf.add filter v11
bf.exists filter v11
bf.exists filter v12
  1. bf.reserve key error_rate的值 initial_size 的值

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

error_rate：误判率

initial_size：数组初始巨细

  1. bf.add key 值
  2. bf.exists key 值
  3. bf.madd 一次增加多个元素
  4. bf.mexists 一次查询多个元素是否存在

4. BloomFilter特点

  1. 高效的刺进和查询，占用空间少，回来的成果是不确定性的
  2. 一个元素假如判别成果为存在的时分元素不必定存在，可是判别成果为不存在的时分则必定不存在
  3. 布隆过滤器能够增加元素，可是不能删去元素。由于删掉元素会导致误判率增加
  4. 误判只会产生在过滤器没有增加过的元素，关于增加过的元素不会产生误判

有，或许有

无，必定无，能够保证的是，假如布隆过滤器判别一个元素不在一个调集中，那这个元素必定不会在调集中

5. BloomFilter原理

5.1 Java中的传统hash

哈希函数的概念是：将任意巨细的输入数据转化成特定巨细的输出数据的函数，转化后的数据称为哈希值或哈希编码，也叫散列值

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

假如两个散列值是不相同的（依据同一函数）那么这两个散列值的原始输入也是不相同的。 这个特性是散列函数具有确定性的成果，具有这种性质的散列函数称为单向散列函数。

散列函数的输入和输出不是仅有对应联络的，假如两个散列值相同，两个输入值很或许是相同的，但也或许不同， 这种情况称为“散列磕碰（collision）”。

用 hash表存储大数据量时，空间功率仍是很低，当只要一个 hash 函数时，还很容易产生哈希磕碰。

5.2 Java中的哈希磕碰实例

事例一：

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

事例二：

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

5.3 初探布隆过滤器实现原理和数据结构

布隆过滤器(Bloom Filter) 是一种专门用来处理去重问题的高级数据结构。

实质便是一个大型位数组和几个不同的无偏hash函数(无偏表明散布均匀)。由一个初值都为零的bit数组和多个个哈希函数构成，用来快速判别某个数据是否存在。

可是跟 HyperLogLog(/post/719106…) 相同，它也相同有那么一点点不精确，也存在必定的误判概率。

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理
增加key时

运用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个方位， 每个hash函数都会得到一个不同的方位，将这几个方位都置1就完成了add操作。

查询key时

只需有其中一位是零就表明这个key不存在，但假如都是1，则不必定存在对应的key。

结论：

有，是或许有

无，是肯定无

5.4 进一步探究

当有变量被参加调集时，通过N个映射函数将这个变量映射成位图中的N个点， 把它们置为 1（假定有两个变量都通过 3 个映射函数）。

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

查询某个变量的时分咱们只需看看这些点是不是都是 1， 就能够大概率知道调集中有没有它了。

假如这些点，有任何一个为零则被查询变量必定不在，

假如都是 1，则被查询变量很或许存在，

为什么说是或许存在，而不是必定存在呢？那是由于映射函数自身便是散列函数，散列函数是会有磕碰的。

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

5.5 布隆过滤器三步骤

  1. 初始化

布隆过滤器本质上是由长度为 m 的位向量或位列表（仅包括 0 或 1 位值的列表）组成，开始所有的值均设置为 0。

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

  1. 增加

当咱们向布隆过滤器中增加数据时，为了尽量地址不抵触，会运用多个 hash 函数对 key 进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个方位，每个 hash 函数都会算得一个不同的方位。

再把位数组的这几个方位都置为 1 就完成了 add 操作。

例如，咱们增加一个字符串wmyskxz

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

  1. 判别是否存在

向布隆过滤器查询某个key是否存在时，先把这个 key 通过相同的多个 hash 函数进行运算，检查对应的方位是否都为 1，

只需有一个位为 0，那么说明布隆过滤器中这个 key 不存在；

假如这几个方位全都是 1，那么说明极有或许存在；

由于这些方位的 1 或许是由于其他的 key 存在导致的，也便是前面说过的hash抵触。

就比方咱们在 add 了字符串wmyskxz数据之后，很明显下面1/3/5 这几个方位的 1 是由于第一次增加的 wmyskxz 而导致的； 此时咱们查询一个没增加过的不存在的字符串inexistent-key，它有或许计算后坑位也是1/3/5 ，这便是误判了……

Redis高级（五）、彻底掌握BloomFilter的安装+操作+原理

5.6 关于BloomFilter的误判率，为什么不要删去？

布隆过滤器的误判是指多个输入通过哈希之后在相同的bit方位1了，这样就无法判别究竟是哪个输入产生的， 因而误判的本源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删去问题，由于布隆过滤器的每一个 bit 并不是独占的，很有或许多个元素同享了某一位。

假如咱们直接删去这一位的话，会影响其他的元素。

5.7 BloomFilter小总结

  1. 存在则很或许存在，不存在则必定不存在。
  2. 运用时最好不要让实际元素数量远大于初始化数量
  3. 当实际元素数量超越初始化数量时，应该对布隆过滤器进行重建， 重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进行

6. BloomFilter优缺点

长处：高效的刺进和删去，占用空间很少

缺点：

  1. 不能删去元素，由于删去元素会导致误判率增大，由于hash抵触，bit数组中同一个方位存放的数据或许是多个key进行hash计算后共有的
  2. 存在误判：不同的数据或许出来相同的值

7. 布谷鸟过滤器

为了处理布隆过滤器不能删去元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》

作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。比较布谷鸟过滤器而言布隆过滤器有以下缺乏： 查询功能弱、空间利用功率低、不支持反向操作（删去）以及不支持计数。

8. 实战

  • 数据库避免穿库。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 运用BloomFilter来削减不存在的行或列的磁盘查找。避免代价昂扬的磁盘查找会大大进步数据库查询操作的功能。
  • 事务场景中判别用户是否阅读过某视频或文章，比方抖音或头条，当然会导致必定的误判，但不会让用户看到重复的内容。
  • 缓存宕机、缓存击穿场景，一般判别用户是否在缓存中，假如在则直接回来成果，不在则查询db，假如来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时分能够用布隆过滤器当缓存的索引，只要在布隆过滤器中，才去查询缓存，假如没查询到，则穿透到db。假如不在布隆器中，则直接回来。
  • WEB拦截器，假如相同恳求则拦截，避免重复被攻击。用户第一次恳求，将恳求参数放入布隆过滤器中，当第二次恳求时，先判别恳求参数是否被布隆过滤器射中。能够进步缓存射中率。Squid 网页署理缓存服务器在 cache digests 中就运用了布隆过滤器。Google Chrome阅读器运用了布隆过滤器加速安全阅读服务
  • Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
  • SPIN 模型检测器也运用布隆过滤器在大规模验证问题时盯梢可达状况空间。

由于BloomFilter最常用的地方适用于处理缓存穿透，因而实战内容放到缓存穿透篇叙述。

以上便是BloomFilter的内容啦，感谢小伙伴的观看，有任何建议都能够联络我！！