十、Redis之布隆过滤器

布隆过滤器是什么？

布隆过滤器（Bloom Filter）：由一个初值都为零的bit数组和多个哈希函数构成，是一种用来快速判断“某个数据是否可能存在”的数据结构。它的特点是：

占用内存非常小 查询速度非常快 判断“肯定不存在”非常准确 判断“可能存在”时，有一定概率出错

一句话概括：布隆过滤器说不存在，就一定不存在；说存在，只是可能存在。

布隆过滤器的组成

布隆过滤器主要由两部分组成：

一个二进制数组 多个哈希函数

例如有一个长度为 10 的二进制数组：

下标：0 1 2 3 4 5 6 7 8 9 值： 0 0 0 0 0 0 0 0 0 0 数组中的每个位置只能是： 0：没有被标记 1：已经被标记

布隆过滤器是一种类似set的数据结构，只是统计结果在巨量数据下有点小瑕疵，不够完美。

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。
它实际上是一个很长的二进制数组(00000000)+ 一系列随机hash算法映射函数，主要用于判断一个元素是否在集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、哈希表等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n),O(logn),O(1)。这个时候，布隆过滤器（Bloom Filter）就应运而生。

布隆过滤器能干什么？

高效地插入和查询，占用空间少，但是返回的结果是不确定性+不够完美

布隆过滤器是一个二进制数组 + 一系列哈希函数组成。要知道在集合类只要用哈希函数基本上都会遇到哈希冲突，这会导致某些key冲突占用同一个坑位，比如三个key都占用上图5号坑位那么一个坑位的值表示三个key存在或不存在，所以会有瑕疵。

重点：

• 判断“可能存在”时，有一定概率出错
  比如5号坑位现在值是1，那么三个key中有几个存在？存在的是哪一个或者是那几个？没办法确定。
• 判断“肯定不存在”非常准确
  判断不存在，那么肯定就不存在
• 布隆过滤器可以添加元素，但是不能删除元素，由于涉及hashcode判断依据，删掉元素会导致误判率增加。

布隆过滤器原理

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

查询某个变量的时候我们只要看看这些点是不是都是1，就可以大概率知道集合中有没有它了。

如果这些点，有任何一个为零则被查询变量一定不在。
如果都是1，则被查询变量很可能存在。

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。（见上图3号坑两个对象都1），这也是为什么不能删除的原因（明明想要删除obj1，但是顺带也会把obj2误删掉）

正是基于布隆过滤器的快速检测特性，我们可以在把数据写入数据库时，使用布隆过滤器做个标记。当缓存缺失后，应用查询数据库时，可以通过查询布隆过滤器快速判断数据是否存在。如果不存在，就不用再去数据库中查询了。这样一来，即使发生缓存穿透了，大量请求只会查询Redis和布隆过滤器，而不会积压到数据库，也就不会影响数据库的正常运行。布隆过滤器可以使用Redis实现，本身就能承担较大的并发访问压力。

hash冲突

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

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

散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“散列碰撞（collision）”。

用hash表存储大数据量时，空间效率还是很低，当只有一个hash函数时，还很容易发生哈希碰撞。

布隆过滤器使用

添加坑位

当我们向布隆过滤器中添加数据时，为了尽量地址不冲突，会使用多个hash函数对key进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置。再把位数组的这几个位置都置为1就完成了add操作。

例如，我们添加一个字符串wmyskxz，对字符串进行多次hash(key)→ 取模运行 → 得到坑位1、3、5。

判断是否存在

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

只要有一个位为零，那么说明布隆过滤器中这个 key 不存在；
如果这几个位置全都是 1，那么说明极有可能存在；
因为这些位置的 1 可能是因为其他的 key 存在导致的，也就是前面说过的 hash 冲突。。。。。

就比如我们在 add 了字符串wmyskxz数据之后，很明显下面 1/3/5 这几个位置的 1 是因为第一次添加的wmyskxz而导致的；此时我们查询一个没添加过的不存在的字符串inexistent-key，它有可能计算后坑位也是 1/3/5，这就是误判了……笔记见最下面

使用时最好不要让实际元素数量远大于初始化数量，一次给够避免扩容，当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add进行。

布隆过滤器使用场景

解决缓存穿透的问题，和redis结合bitmap使用

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

可以使用布隆过滤器解决缓存穿透的问题
把已存在数据的 key 存在布隆过滤器中，相当于 Redis 前面挡着一个能量护照。当有新的请求时，先到布隆过滤器中查询是否存在：

• 如果布隆过滤器中不存在该条数据则直接返回；
• 如果布隆过滤器中已存在，才去查询缓存 Redis，如果 Redis 里没查询到则再查询 MySQL 数据库。

黑名单校验，识别垃圾邮件

发现存在黑名单中的，就执行特定操作。比如：识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。

假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中，在收到邮件时，判断邮件地址是否在布隆过滤器中即可。

案例

布隆过滤器：根据代码逻辑+redis缓存实现，简单实现核心代码如下：

importch.qos.logback.classic.util.StatusViaSLF4JLoggerFactory;importlombok.extern.slf4j.Slf4j;importorg.apache.ibatis.transaction.managed.ManagedTransaction;importorg.springframework.data.redis.core.RedisTemplate;importorg.springframework.stereotype.Component;importjavax.annotation.PostConstruct;importjavax.annotation.Resource;/** * 布隆过滤器白名单初始化工具类，一开始就设置一部分数据为白名单所有， * 白名单业务默认规定：布隆过滤器有，redis是极大可能有。 * 白名单：whitelistCustomer */@Component@Slf4jpublicclassBloomFilterInit{@ResourceprivateRedisTemplateredisTemplate;@PostConstruct//初始化白名单数据,暂时注释省的后台打印publicvoidinit(){//1 白名单客户加载到布隆过滤器Stringkey="customer:12";//2 计算hashValue,由于存在计算出来负数的可能，我们取绝对值inthashValue=Math.abs(key.hashCode());//3 通过hashValue和2的32次方后取余，获得对应的下标坑位longindex=(long)(hashValue%Math.pow(2,32));log.info(key+" 二进制bit数组的位置，index:{}",index);//4 设置redis里面的bitmap对应类型白名单：whitelistCustomer的坑位，将该值设置为1redisTemplate.opsForValue().setBit("whitelistCustomer",index,true);}}

上面的和的核心思想是，先将初始化数据的key通过hashcode方法得到散列值，然后取散列值的绝对值得到布隆过滤器的bit数组的位置，然后存到的key为：whitelistCustomer的的缓存中，比如此时bit位是666，那么此时比特位666的值是1。

importlombok.extern.slf4j.Slf4j;importorg.springframework.data.redis.core.RedisTemplate;importorg.springframework.stereotype.Component;importjavax.annotation.Resource;@Component@Slf4jpublicclassCheckUtils{@ResourceprivateRedisTemplateredisTemplate;publicbooleancheckWithBloomFilter(StringcheckItem,Stringkey){inthashValue=Math.abs(key.hashCode());longindex=(long)(hashValue%Math.pow(2,32));booleanexistOK=redisTemplate.opsForValue().getBit(checkItem,index);log.info("--->key:"+key+" 对应坑位下标index: "+index+" 是否存在："+existOK);returnexistOK;}}===============================================分割线===============================================publicCustomerfindById(IntegercustomerId){Customercustomer=null;//缓存key的名称Stringkey=CACHA_KEY_CUSTOMER+customerId;//布隆过滤器check，无是绝对无，有是可能有//===============================================if(!checkUtils.checkWithBloomFilter("whitelistCustomer",key)){log.info("白名单无此顾客，不可以访问: "+key);returnnull;}//===============================================//1 查询rediscustomer=(Customer)redisTemplate.opsForValue().get(key);//redis无，进一步查询mysqlif(customer==null){//2 从mysql查出来customercustomer=customerMapper.selectByPrimaryKey(customerId);// mysql有，redis无if(customer!=null){//3 把mysql捞到的数据写入redis，方便下次查询能redis命中。redisTemplate.opsForValue().set(key,customer);}}returncustomer;}

findById是一个普通的service层的普通查询方法，当获得查询参数id后，直接拼接redis的key，然后传递给checkWithBloomFilter。

checkWithBloomFilter获取到key后调用hashcod方法获取散列值去redis的中查询，如果查询到了，返回ture否则返回false。然后findById根据true或false在决定直接响应结束，还是查缓存或者是数据库。
比如此刻传递过来的key经过hashCode算出来散列值是666，checkWithBloomFilter会获取whitelistCustomer这个key的地666比特位的值，饭后返回true或false。

如果是黑名单用户我们已经添加布隆过滤器的缓存中了，肯定能在缓存中查到，所以就直接拒绝后续流程，这样就可以有效过滤到一些我们不愿意的访问。

以上就是一个简单的布隆过滤器的实现。

布隆过滤器优缺点

• 优点
• 缺点
  1. 不能删除元素。
     因为删掉元素会导致误判率增加，因为hash冲突同一个位置可能存的东西是多个共有的，你删除一个元素的同时可能也把其它的删除了。
  2. 存在误判，不能精准过滤。有是可能有，无是肯定无。