关键词：
目录
一. 布隆过滤简基础
- 首先了解一个需求: 现有50亿个电话号码,如何快速准确的判断这些电话号码已经存在(这个问题的关键是大数据量,快速,判断是否存在)不管数据库还是redis,不管什么数据类型50亿都占用内存太大
- 布隆过滤器解释: 实际是一个很长的二进制数组+一系列随机hash算法映射函数,主要用于判断一个元素是否存在某个集合中(简单理解为:由一个初始值都为0的bit数组和多个哈希函数构成用来快速判断某个数据是否存在,类似于set的数据结构,只是统计结果不太准确)
- 布隆过滤器的特点
1)高效的插入和查询,占用空间少,返回结果不确定
2)一个元素如果判断结果为存在实际该元素可能不存在,如果判断该结果不存在则一定不存在
3)布隆过滤器可以添加元素,但是不能删除元素,因为删除元素会导致误判率的增加
4)误判只会发生才过滤器没有添加过的元素,对于添加过的元素不会发生误判
- 误判的原因,假设一个数据aaaa计算到的hash值是"1111",但是hash是可能重复的,布隆过滤器中已经存储了数据bbbb的hash值"1111",这时候通过hash值判断aaaa是否存在,返回true,时间存储的"1111"对应的数据是bbbb
- 布隆过滤器使用场景: 解决缓存穿透问题,黑名单校验
二. 布隆过滤器原理
-
复习java中的hash函数: 将任意大小的数据通过hash算法转换为特定大小的hash编码,也叫散列,可能存在冲突,也就是两个hash值不同实际数据一定不同,两个hash相同,实际数据可能不相同 使用hash表存大量数据时,空间效率低,并且当只有一个hash函数时,很容易发生hash碰撞
-
上面提到过布隆过滤器是一个很长的初始值都为0的,二进制数组+一系列随机hash算法映射函,类似于set的数据结构,统计结果不太准确(在统计存在时)
-
添加key时: 使用多个hash函数,对key进行hash运算得到一个整数索引,然后与位数组长度进行取模运算拿到位置,每个hash函数都会得到不同的位置,将这几个位置设置为1,完成了一次add操作
-
查询key时,只要通过key进行hash运算拿到整数索引后与位数组长度进行取模运算,拿到位数组的位置,只要一次位数组中指定的位置值为0,就说明key不存在
-
解释为什么判断存在的可能不存在,假设在判断一个key是经过hash运算,与位数组长度取模运算获取到位置后判断该位置上是1,这个1可能是对别的key进行标记的
-
解释为什么不能删除,删除会造成误判率增加的原因: 看上图,添加obj1与obj2两个数据,假设需要通过三次hash运算获取到了三个位置obj1对应1,3,12, obj2对应3, 8, 13,会发现obj1与obj2同时都用到了3位置,假设我要删除obj1,将索引为1,3,12位置上的1设置为0,当查询obj2是否存在时走到3位置上会发现在删除obj1时已经设置为0了,实际存在的却返回不存在,发生误判
-
基于布隆过滤器的快速检测特性,我们可以在做数据库写入是,使用布隆过滤器做标记,当缓存缺失后,查询数据库前(或存储数据库–>redis成功后再使用布隆过滤器进行标记)先通过查询布隆过滤器判断是否存在,如果不存在则直接返回不需要操作数据库
-
优化布隆过滤器出现了布谷鸟过滤器, 相比布谷鸟过滤器,布隆过滤器查询性能低,空间利用率低,不支持删除以及计数操作
三. redis 缓存穿透
- 什么是缓存穿透: 查询数据,先查询redis,后查询mysql,都查询不到的记录,请求每次都会打到数据库导致数据库压力暴增,数据库宕机
- 解决方案:
1)空对象缓存: 假设查询到redis没有,数据库也没有的数据时,存储一个空或一个缺省值到redis,后续再去查询这个为空的key,就会走redis(但是恶意攻击使用大量不同数据库redis同时都不存在的key查询不能解决,并且防止出现这种情况在向redis中存储空对象时要设置过期时间,防止redis中存储大量为空的key)
2)bloomfilter过滤器: 在存储数据是,除了存储redis与数据库,在布隆过滤器中再存储一份进行标记,后续查询时走布隆过滤器判断这个key是否不存在或存在,如果不存在直接return
Google 布隆过滤器Guava解决缓存穿透
- 创建项目工程
- 项目中引入 Guava 依赖
<!--guava-->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>
- Guava helloWorld 重点关注几个API
1)BloomFilter 对象的创建,指定当前过滤器能存储多少个元素,误判率
3)BloomFilter put(元素) 方法, 将元素数据存入过滤器中,实际存储的并不是元素本身(具体了解布隆过滤器原理)
2)BloomFilter mightContain(元素) 方法, 判断元素是否存在
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class Test
public void bloomFilter()
//1.创建布隆过滤器对象
//create方法中的Funnels 与 100 表示创建一个位数组可以容纳100个数据的过滤器,误判率是0.03
BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), 100, 0.03d);
//BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), 100000, 0.03d);
//2.判断指定元素是否存在 mightContain(元素)
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
//3.将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
- 实际开发中Guava 布隆过滤器应用流程
1)需要使用布隆过滤器的模块估算该模块大概会存多少个key,确定布隆过滤器存放数据大小
2)项目启动时,插入对应该功能模块数据时同步将数据key存入布隆过滤器
3)编写过滤器,请求查询时拦截过滤查询过滤器是否不存在,如果不存在直接return
4)插入对应功能模块数据时插入数据库,插入redis,对应的key插入布隆过滤器
- 注意误判问题,判断一个元素在过滤器中不存在,则一定不存在,判断一个元素在过滤器中存在,也可能不存在,误判率0.03的误判率
- 查看创建 BloomFilter对象create()源码发现在Guava过滤器中底层默认指定使用了5个hash函数,默认的误判率为0.03
- 在上面的示例代码中我们创建BloomFilter指定了误判率,需要注意,可以手动指定,但是误判率越低,性能越低,误判率越小,位数组长度越大,hash此处越多
- 注意点: Guava 是单机版
Redis 布隆过滤器解决缓存穿透(推荐)
- 使用流程
1)项目中引入redisson依赖
2)配置redissonClient注意是单机模式还是集群模式
3)通过redissonClient构造redis 布隆过滤器
4)初始化布隆过滤器,设置存放数据量,误判率
5)存储数据到mysql,redis后在redis中做存储标识将key存入布隆过滤器
6)查询时判断过滤器中如果不存在,直接return
- 项目中添加相关依赖
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.13.4</version>
</dependency>
- redissonClient 集群模式配置示例
/**
* 单机版
* @return
*/
@Bean
public Redisson redisson()
Config config = new Config();
config.useSingleServer().setAddress("redis://47.100.63.107:16379").setDatabase(0);
return (Redisson) Redisson.create(config);
/**
* 集群版
* @return
*/
@Bean
public RedissonClient getRedisson()
//redi集群地址
String cluster="10.10.1.1:7000,10.10.1.1:7001,10.10.1.1:7002,10.10.1.1:7003,10.10.1.1:7004,10.10.1.1:7005";
String[] nodes = cluster.split(",");
//redisson版本是3.5，集群的ip前面要加上“redis://”，不然会报错，3.2版本可不加
for (int i = 0; i < nodes.length; i++)
nodes[i] = "redis://" + nodes[i];
Config config = new Config();
//SentinelServersConfig serverConfig = config.useSentinelServers()
//useSentinelServers() 与 useClusterServers() 前者要指定masterName
//调用 setMasterName("masterName")
config.useClusterServers() //这是用的集群server
.addNodeAddress(nodes)
.setScanInterval(2000) //设置集群状态扫描时间
.setPassword("password")
.setTimeout(3000)
.setMasterConnectionPoolSize(8)
.setSlaveConnectionPoolSize(8)
.setSlaveConnectionMinimumIdleSize(1)
.setMasterConnectionMinimumIdleSize(1);;
RedissonClient redisson = Redisson.create(config);
//可通过打印redisson.getConfig().toJSON().toString()来检测是否配置成功
return redisson;
- redis布隆过滤器helloWorld
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RBucket;
import org.redisson.api.RedissonClient;
import org.redisson.client.codec.StringCodec;
import org.redisson.config.Config;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.RedisTemplate;
import java.util.concurrent.TimeUnit;
/**
* redis 布隆过滤器 helloWorld 此处以单机redis示例
*/
public class RedissonBloomFilterDemo
@Autowired
private RedisTemplate redisTemplate;
public void redissonBloomFilterHelloWorld()
//1.获取redisClient 连接redis服务器
Config config = new Config();
config.useSingleServer().setAddress("redis://192.168.111.147:6379").setDatabase(0);
RedissonClient redissonClient = Redisson.create(config);
//2.通过redisson构造rBloomFilter,"phoneListBloomFilter" 固定
RBloomFilter rBloomFilter = redissonClient.getBloomFilter("phoneListBloomFilter",new StringCodec());
//3.初始化布隆过滤器,指定过滤器中存储数据量为1000000,误判率为0.03
rBloomFilter.tryInit(1000000,0.03d);
//4.使用示例
//4.1向redis中添加kv键值对,"new StringCodec()"是指定编码格式
redissonClient.getBucket("key1",new StringCodec()).set("valu1");
//等同于
redisTemplate.opsForValue().set("key1","valu1");
//4.2
redissonClient.getBucket("key1", new StringCodec());
//等同于
redisTemplate.opsForValue().get("key1");
//4.3向过滤器中添加一个元素key
rBloomFilter.add("key1");
//4.4 判断指定元素在过滤器中是否存在,存在返回true
boolean b = rBloomFilter.contains("key1");
//4.5释放client连接
redissonClient.shutdown()
redis 安装布隆过滤器插件
- 上面演示了redis版本的布隆过滤器使用,但是redis上需要安装布隆过滤器的插件
四. 模拟Guava编码通过redis实现布隆过滤器
- 引入Guava依赖
- 模拟Guava实现布隆过滤器逻辑编码实现,底层基础运算逻辑不变,只是把原Guava通过内存存储数据,修改为通过redis存储数据
import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;
public class BloomFilterHelper<T>
private int numHashFunctions;
private int bitSize;
private Funnel<T> funnel;
public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp)
Preconditions.checkArgument(funnel != null, "funnel不能为空");
this.funnel = funnel;
// 计算bit数组长度
bitSize = optimalNumOfBits(expectedInsertions, fpp);
// 计算hash方法执行次数
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
public int[] murmurHashOffset(T value)
int[] offset = new int[numHashFunctions];
long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++)
int nextHash = hash1 + i * hash2;
if (nextHash < 0)
nextHash = ~nextHash;
offset[i - 1] = nextHash % bitSize;
return offset;
/**
* 计算bit数组长度
*/
private int optimalNumOfBits(long n, double p)
if (p == 0)
// 设定最小期望长度
p = Double.MIN_VALUE;
return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
/**
* 计算hash方法执行次数
*/
private int optimalNumOfHashFunctions(long n, long m)
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
import com.google.common.base.Preconditions;
import org.springframework.data.redis.core.RedisTemplate;
public class BloomRedisService<T>
private RedisTemplate<String, String> redisTemplate;
private BloomFilterHelper<T> bloomFilterHelper;
public void setBloomFilterHelper(BloomFilterHelper<T> bloomFilterHelper)
this.bloomFilterHelper = bloomFilterHelper;
public void setRedisTemplate(RedisTemplate<String, String> redisTemplate)
this.redisTemplate = redisTemplate;
/**
* 根据给定的布隆过滤器添加值
*/
public void addByBloomFilter(String key, T value)
Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset)
redisTemplate.opsForValue().setBit(key, i, true);
/**
* 根据给定的布隆过滤器判断值是否存在
*/
public boolean includeByBloomFilter(String key, T value)
Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset)
if (!redisTemplate.opsForValue().getBit(key, i))
return false;
return true;
- 配置
import com.google.common.base.Charsets;
import com.google.common.hash.Funnel;
import com.single.mall.service.IUserBusinessService;
import com.single.mall.service.impl.BloomFilterHelper;
import com.single.mall.service.impl.BloomRedisService;
import org.springframework.beans.factory.InitializingBean;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.util.CollectionUtils;
import java.util.Arrays;
import java.util.List;
@Configuration
public class BloomFilterConfiguration implements InitializingBean
@Autowired
private RedisTemplate redisTemplate;
@Autowired
private IUserBusinessService userBusinessService;
/**
* 将模拟Guava自定义实现布隆过滤器底层BloomFilterHelper注入容器
* @return
*/
@Bean
public BloomFilterHelper<String> initBloomFilterHelper()
return new BloomFilterHelper<>((Funnel<String>) (from, into) -> into.putString(from, Charsets.UTF_8)
.putString(from, Charsets.UTF_8), 1000000, 0.01);
/**
* 将通过redis自定义实现的布隆过滤器BloomRedisService bean注入
*
* @return
*/
@Bean
public BloomRedisService<String> bloomRedisService()
BloomRedisService<String> bloomRedisService = new BloomRedisService<>();
bloomRedisService.setBloomFilterHelper(this.initBloomFilterHelper());
bloomRedisService.setRedisTemplate(redisTemplate);
redis的缓存穿透缓存雪崩缓存击穿问题的概念与解决办法(代码片段)
...穿透1.1什么是缓存穿透？1.2怎么解决1.3BloomFilter布隆过滤器1.3.1BloomFilter的原理1.3.2BloomFilter的优缺点1.3.3GuavaBloomFilter1.3.4RedisBloomFilter2缓存雪崩3缓存击穿4缓存预热5防止Redis宕机1缓存穿 查看详情
redis12_缓存雪崩缓存穿透基于布隆过滤器解决缓存穿透的问题缓存击穿基于缓存击穿工作实际案例(代码片段)
文章目录①.缓存雪崩②.缓存穿透③.在centos7下布隆过滤器2种安装方式④.缓存击穿⑤.高并发的淘宝聚划算案例落地①.缓存雪崩①.问题的产生:缓存雪崩是指缓存数据大批量到过期时间,而查询数据量巨大,引起数据库压力过大甚至... 查看详情
redis12_缓存雪崩缓存穿透基于布隆过滤器解决缓存穿透的问题缓存击穿基于缓存击穿工作实际案例(代码片段)
文章目录①.缓存雪崩②.缓存穿透③.在centos7下布隆过滤器2种安装方式④.缓存击穿⑤.高并发的淘宝聚划算案例落地①.缓存雪崩①.问题的产生:缓存雪崩是指缓存数据大批量到过期时间,而查询数据量巨大,引起数据库压力过大甚至... 查看详情
redis08_缓存雪崩缓存穿透基于布隆过滤器解决缓存穿透的问题缓存击穿基于缓存击穿工作实际案例(代码片段)
文章目录①.缓存雪崩②.缓存穿透③.在centos7下布隆过滤器2种安装方式④.缓存击穿⑤.高并发的淘宝聚划算案例落地①.缓存雪崩①.问题的产生:缓存雪崩是指缓存数据大批量到过期时间,而查询数据量巨大,引起数据库压力过大甚至... 查看详情
redis缓存雪崩缓存穿透缓存击穿
...分布式锁缓存穿透解决方案过滤非法查询缓存空对象布隆过滤器布隆过滤器的新增布隆过滤器的查询布隆过滤器的删除布隆过滤器解决缓存穿透布隆过滤器的特点缓存击穿解决方案设置热点Key永不过期使用Redis的分布式锁Redis缓... 查看详情
布隆过滤器底层原理(代码片段)
什么是布隆过滤器是一个叫做布隆的小伙子发明出来的，底层使用bitmap（二进制位）实现，向bitmap中标记为1，表示这个元素已查询过，下次来查询的时候就不要再去数据库查了；这里涉及到了一个问题... 查看详情
redis缓存穿透击穿雪崩预热更新降级(代码片段)
...：提前过滤掉不合法的请求，可以使用Redis中布隆过滤器； 布隆过滤器设计思想：布隆过滤器由一个长度为m比特的位数组（bitarray）与k个哈希函数 查看详情
高级数据结构----跳跃表布隆过滤器一致性哈希雪花算法(代码片段)
...跃表与其它结构相比1.4使用场景1.5Redis中的跳跃表2、布隆过滤器(BloomFilter)2.1什么是布隆过滤器2.2原理2.3场景(Redis缓存穿透)3、一致性哈希3.1普通哈希3.2一致性哈希算法3.2.1基本原理3.2.2优点3.2.3hash环的偏斜3 查看详情
什么是布隆过滤器？如何解决高并发缓存穿透问题？(代码片段)
...流量，要注意缓存穿透问题吗!!! 本文会介绍布隆过滤器，空间换时间，以较低的内存空间、高效解决这个问题。1、性能不够，缓存来凑现在的年轻人都喜欢网购，没事就逛逛淘宝，剁剁手，买些自... 查看详情
什么是缓存穿透缓存雪崩及解决缓存穿透雪崩解决方案实现(代码片段)
(目录)1、缓存穿透问题的解决思路缓存穿透：常见的解决方案有两种：缓存空对象布隆过滤缓存空对象思路分析：布隆过滤：①编码解决商品查询的缓存穿透问题：核心思路如下：在原来的逻辑中：现在的逻辑中：代码：/***查... 查看详情
防缓存穿透利器-隆过滤器(bloomfilter)(代码片段)
防缓存穿透利器-布隆滤器(BloomFilter)一、布隆过滤器原理如果想要判断一个元素是不是在一个集合中存在，一般的想法是将所有元素保存起来，然后再拿着这个元素在集合中一个一个进行比对。但是随着集合中元素的增... 查看详情
浅谈布隆过滤器(代码片段)
不知道从什么时候开始，本来默默无闻的布隆过滤器一下子名声大燥，仿佛身在互联网，做着开发的，无人不知，无人不晓，哪怕对技术不是很关心的小伙伴也听过它的名号。我也花了不少时间去研究布隆过滤器，看了不少博客... 查看详情
redis问题(代码片段)
...合规范的key2、缓存空值，设置较短过期时间3、布隆过滤器，存储所有可能访问的key，不存在的key直接被过滤缓存击穿某一个热点key，缓存过期瞬间 查看详情
redis的缓存问题之缓存穿透缓存雪崩缓存击穿(代码片段)
目录一、什么是缓存穿透？二、常见的解决方案有两种：1、缓存空对象2、布隆过滤综上所述三、编码解决商品查询的缓存穿透问题四、缓存雪崩问题及解决思路1、什么是缓存雪崩？五、缓存击穿问题及解决思路 1、... 查看详情
redis——缓存穿透缓存击穿缓存雪崩
...也会导致这一段时间内的数据不一致问题。2）使用布隆过滤器简单地说就是在缓存前面加了一个过滤器，查询一个数据时布隆过滤器中存在才继续查询缓存，否则直接返回空值。注意，布隆过滤器可能误判（不存在的肯定不存... 查看详情
redis系列之什么是布隆过滤器？(代码片段)
Redis系列之什么是布隆过滤器？1、前言前面的学习，我们知道了Redis的很多应用场景，但是最常见的还是缓存，“性能不够，缓存来凑”，在一些高并发的场景合理的使用缓存，还是可以减缓系统压力... 查看详情
redis系列之什么是布隆过滤器？(代码片段)
Redis系列之什么是布隆过滤器？1、前言前面的学习，我们知道了Redis的很多应用场景，但是最常见的还是缓存，“性能不够，缓存来凑”，在一些高并发的场景合理的使用缓存，还是可以减缓系统压力... 查看详情
redis布隆过滤器原理安装使用(代码片段)
1布隆过滤器介绍Hash、Set、String的BitMap等可以实现判断元素是否存在的功能，但这些实现方式要么随着元素增多会占用大量内存（Hash、Set），要么无法动态伸缩和保持误判率不变（BitMap）。因此，我们... 查看详情