文章目录布隆过滤器是什么布隆过滤器能干什么布隆过滤器原理hash冲突布隆过滤器使用添加坑位判断是否存在布隆过滤器使用场景解决缓存穿透的问题和redis结合bitmap使用黑名单校验识别垃圾邮件案例布隆过滤器优缺点布隆过滤器是什么布隆过滤器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 */ComponentSlf4jpublicclassBloomFilterInit{ResourceprivateRedisTemplateredisTemplate;PostConstruct//初始化白名单数据,暂时注释省的后台打印publicvoidinit(){//1 白名单客户加载到布隆过滤器Stringkeycustomer:12;//2 计算hashValue,由于存在计算出来负数的可能我们取绝对值inthashValueMath.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;ComponentSlf4jpublicclassCheckUtils{ResourceprivateRedisTemplateredisTemplate;publicbooleancheckWithBloomFilter(StringcheckItem,Stringkey){inthashValueMath.abs(key.hashCode());longindex(long)(hashValue%Math.pow(2,32));booleanexistOKredisTemplate.opsForValue().getBit(checkItem,index);log.info(---key:key 对应坑位下标index: index 是否存在existOK);returnexistOK;}}分割线publicCustomerfindById(IntegercustomerId){Customercustomernull;//缓存key的名称StringkeyCACHA_KEY_CUSTOMERcustomerId;//布隆过滤器check无是绝对无有是可能有//if(!checkUtils.checkWithBloomFilter(whitelistCustomer,key)){log.info(白名单无此顾客不可以访问: key);returnnull;}////1 查询rediscustomer(Customer)redisTemplate.opsForValue().get(key);//redis无进一步查询mysqlif(customernull){//2 从mysql查出来customercustomercustomerMapper.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算出来散列值是666checkWithBloomFilter会获取whitelistCustomer这个key的地666比特位的值饭后返回true或false。如果是黑名单用户我们已经添加布隆过滤器的缓存中了肯定能在缓存中查到所以就直接拒绝后续流程这样就可以有效过滤到一些我们不愿意的访问。以上就是一个简单的布隆过滤器的实现。布隆过滤器优缺点优点缺点不能删除元素。因为删掉元素会导致误判率增加因为hash冲突同一个位置可能存的东西是多个共有的你删除一个元素的同时可能也把其它的删除了。存在误判不能精准过滤。有是可能有无是肯定无。