布隆过滤器(解决redis缓存穿透步骤之一)
)
布隆过滤器详解1、是什么布隆过滤器Bloom Filter一个很长的二进制位数组 N 个哈希函数用来快速判断某个元素一定不存在 / 可能存在。✅特点判断不存在100% 准确判断存在有误判概率可能把不在的元素判定为存在不能删除元素普通布隆只能新增、查询不存储原始数据只存 hash 映射后的 bit 位内存占用极小2、工作原理初始化长度为 m 的 bit 数组全部置 0添加元素元素经过k个不同哈希函数算出 k 个下标把数组对应下标全部置为1。同一个位置多次置 1还是 1。查询元素是否存在对元素执行同样 k 个 hash拿到 k 个下标只要有任意一位是 0→ 元素一定不存在全部都是 1→ 元素可能存在存在误判误判来源不同元素 hash 刚好落在同一批 bit 位上。❌不能删除如果把某个 bit 置 0会影响其他共用这个 bit 的元素。如果需要删除使用计数布隆过滤器bit 数组改成计数器数组。3、核心参数mbit 数组长度越大误判率越低内存越大n预期存放元素数量k哈希函数个数误判率 p业务上可以接受的错误概率经验公式 最佳哈希函数数量k (m/n)*ln2m 越大、n 越小误判率越低。4、Java/Redis 实际使用场景场景 1缓存穿透最经典面试大量请求查询数据库不存在的数据直接打穿 Redis 打到 DB。方案把所有有效 key 放入布隆过滤器。 请求过来先过布隆返回不存在 → 直接返回不查 redis、不查 DB返回可能存在 → 再查缓存、数据库注意布隆过滤器有误判不会 100% 拦截。场景 2黑名单、垃圾过滤黑名单手机号、url判断是否在黑名单。场景 3去重比如爬虫判断 url 是否已经爬过大数据量去重。❗不能做精确判断存在、需要删除元素的业务。5、Redis 布隆过滤器Redis4.0 以后提供插件RedisBloom# 添加 BF.ADD bloom_user 10001 # 查询 BF.EXISTS bloom_user 10001Redis 布隆也不支持删除。实例 1Redis 布隆过滤器解决缓存穿透伪业务代码Java前提Redis 安装 RedisBloom 模块命令BF.ADD、BF.EXISTS业务商品查询项目启动预热把数据库全部合法商品 id 加载进布隆过滤器// 项目启动把所有商品id存入布隆 ListLong allGoodsId goodsMapper.selectAllGoodsId(); for (Long id : allGoodsId) { // BF.ADD bloom:goods 1001 redisTemplate.opsForValue().execute((RedisCallbackObject) conn - { conn.bfAdd(bloom:goods, id.toString().getBytes()); return null; }); }查询商品完整流程public Goods getGoodsById(Long goodsId){ //①第一步布隆过滤器判断 Boolean mayExist (Boolean)redisTemplate.opsForValue().execute(conn-{ return conn.bfExists(bloom:goods,goodsId.toString().getBytes()); }); //布隆返回false一定不存在直接返回不走redis、不走DB if(Boolean.FALSE.equals(mayExist)){ return null; } //②布隆说可能存在查询Redis缓存 String cacheJson redisTemplate.opsForValue().get(goods:goodsId); if(cacheJson ! null){ return JSONUtil.toBean(cacheJson,Goods.class); } //③redis未命中查询数据库 Goods goods goodsMapper.selectById(goodsId); if(goods ! null){ //写入redis缓存 redisTemplate.opsForValue().set(goods:goodsId,JSONUtil.toJsonStr(goods),30, TimeUnit.MINUTES); } return goods; }业务注意新增商品需要同步调用BF.ADD把新 id 加入布隆 ⚠️删除商品普通布隆无法删除会产生脏数据。实例2Guava 布隆过滤器Java 本地dependency groupIdcom.google.guava/groupId artifactIdguava/artifactId version32.1.3-jre/version /dependency// 预期元素10万误判率0.01 BloomFilterString bloomFilter BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8),100000,0.01); bloomFilter.put(zhangsan); boolean exist bloomFilter.mightContain(zhangsan);Guava 布隆是本地内存多实例环境无法共享适合单机分布式必须用 RedisBloom。6、高频面试考点为什么布隆过滤器不能删除一个 bit 位会被多个元素共享把 bit 置 0会把其他元素标记成不存在。 解决计数布隆过滤器每个位置存计数器删除计数器减一。为什么会误判哈希冲突不同元素映射到同一组 bit。不会漏判只会误判。 不存在一定是真的不存在存在不一定真的存在。缓存穿透使用布隆过滤器有什么缺点1有一定误判率 2元素新增后布隆要同步 3数据大量删除普通布隆无法处理 4Redis 布隆需要安装插件Guava 本地实例之间数据不互通。布隆过滤器、BitMap 区别BitMap一个元素对应一个 bit无误差但是需要知道元素最大值适合 id 连续场景。布隆过滤器k 个 hash 映射多个 bit有误差不需要知道元素范围适合字符串、不规则 id。7、对比小结表格特性布隆过滤器BitMap误差存在误判无误差存储原始值不存储不存储删除普通版本不支持支持适用数据字符串、离散 id连续数字 id内存极小取决于最大值
