什么是布隆过滤器

布隆过滤器（Bloom Filter）是由Howard Bloom在1970年提出的一种比较巧妙的概率型数据结构，它可以告诉你某种东西一定不存在或者可能存在。当布隆过滤器说，某种东西存在时，这种东西可能不存在；当布隆过滤器说，某种东西不存在时，那么这种东西一定不存在。

布隆过滤器相对于Set、Map 等数据结构来说，它可以更高效地插入和查询，并且占用空间更少，它也有缺点，就是判断某种东西是否存在时，可能会被误判。但是只要参数设置的合理，它的精确度也可以控制的相对精确，只会有小小的误判概率。

redis中的布隆过滤器

之前的布隆过滤器可以使用Redis中的位图操作实现，直到Redis4.0版本提供了插件功能，Redis官方提供的布隆过滤器才正式登场。布隆过滤器作为一个插件加载到Redis Server中，就会给Redis提供了强大的布隆去重功能。

插件的安装

1.进入redis官网，选择modules模块，找到redisBloom， 点击进入github中，找到…gz；复制下载地址

2.进入服务器进行下载

进入一个目录，执行： wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz

3.解压编译

tar -zxvf v1.1.1.tar.gz

解压完的目录

进入目录RedisBloom-1.1.1执行make命令进行编译

这时候会看到该目录出现一个rebloom.so

打开redis的配置文件，导入rebloom.so

loadmodule /usr/local/software/redis/RedisBloom-1.1.1/rebloom.so

注意： /usr/local/software/redis/RedisBloom-1.1.1/rebloom.so是绝对路劲

重启redis, bf的命令就出现了

布隆过滤器的基本使用

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

• bf.add：添加单个元素到布隆过滤器中
• bf.madd: 添加多个元素到布隆过滤器中
• bf.exists：判断单个元素是否在过滤器中
• bf.mexists: 判断多个元素是否在过滤器中
  

布隆过滤器的高级使用

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

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

设置K2的参数

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

布隆过滤器的原理简介

数据结构

布隆过滤器是一个BIT数组，本质上是一个数据，所以可以根据下标快速找数据

哈希映射

1、布隆需要记录见过的数据，这里的记录需要通过hash函数对数据进行hash操作，得到数组下标并存储在BIT 数组里记为1。这样的记录一个数据只占用1BIT空间

2、判断是否存在时：给布隆过滤器一个数据，进行hash得到下标，从BIT数组里取数据如果是1 则说明数据存在，如果是0 说明不存在

精确度

hash算法存在碰撞的可能，所以不同的数据可能hash为一个下标数据，故为了提高精确度就需要 使用多个hash 算法标记一个数据，和增大BIT数组的大小
也是因为如此，布隆过滤器判断为【数据存在】 可能数据并不存在，但是如果判断为【数据不存在】那么数据就一定是不存在的

** baidu字样到布隆过滤器中，用了三个不同的hash函数 3BIT 判断一个数据，BIT数组大小为8**
哈希函数返回 1、4、7

我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话， 4 位置发生了hash碰撞

布隆过滤器只能插入数据判断是否存在，不能删除，而且只能保证【不存在】判断绝对准确

布隆过滤器的应用

解决缓存穿透的问题

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

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

黑名单校验

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