大家好，我是一安，之前有介绍一篇《Redis缓存失效问题：缓存穿透-缓存雪崩-缓存击穿》，文中提到解决缓存穿透是通过null结果缓存，并加入短暂过期时间，这种其实有一个弊端，当用户量太大时，我们会缓存大量空数据，这也是今天要介绍的另一种方式布隆过滤器
介绍
布隆过滤器（Bloom Filter）是1970年由布隆提出的，是由位数组和多个哈希函数组成概率性数据结构，一个元素由多个状态值共同确定：位数组存储状态值，哈希函数计算状态值的位置
插入元素时，X,Y,Z分别由3个状态值共同确定元素是否存在，状态值的位置通过3个哈希函数分别计算
查询元素时，仍通过3个Hash函数得到对应的3个位，判断目标位置是否为1，若目标位置全为1则认为该元素在布隆过滤器内，否则认为该元素不存在
注意：如果判断这个key不存在，那么就一定不存在；如果key存在，那么有可能不存在
优点：空间效率和查询时间都比一般的算法要好
缺点：是有一定的误识别率和删除困难
应用场景
-
解决Redis缓存穿透问题（面试重点）
-
邮件过滤，使用布隆过滤器来做邮件黑名单过滤
-
浏览器检测钓鱼网站
演示
对于缓存穿透，相信大家看了上面的逻辑图，已经明白怎么处理了
下面就主要介绍一下布隆过滤器两种使用方式
内存布隆过滤器
1.引入依赖
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>30.1-jre</version>
</dependency>
2.测试验证
public static void main(String[] args) {
int size = 1000000;//预计要插入多少数据
double fpp = 0.001;//期望的误判率
BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
//插入数据
for (int i = 0; i < size; i++) {
bloomFilter.put(i);
}
int count = 0;
for (int i = 1000000; i < 2000000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "误判了");
}
}
System.out.println("总共的误判数:" + count);
}
1000735误判了
1000749误判了
1000925误判了
......
......
1989251误判了
1990375误判了
1990380误判了
1990743误判了
1991994误判了
1993323误判了
1994654误判了
1995990误判了
1996133误判了
1996793误判了
1997052误判了
总共的误判数:994
内存布隆过滤器不适合多节点集群环境下的应用共享，同时将数据保存在内存中系统重启也会导致数据丢
利用redis实现
1.引入依赖
<dependency>
<groupId>org.Springframework.boot</groupId>
<artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>
2.配置RedisTemplate
@Configuration
public class RedisConfig{
@Bean
public RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory factory) {
RedisTemplate<String, Object> redisTemplate = new RedisTemplate<>();
redisTemplate.setConnectionFactory(factory);
Jackson2JsonRedisSerializer jackson2JsonRedisSerializer = new Jackson2JsonRedisSerializer(Object.class);
ObjectMapper om = new ObjectMapper();
om.setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
om.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL);
jackson2JsonRedisSerializer.setObjectMapper(om);
//序列化设置 ，这样为了存储操作对象时正常显示的数据，也能正常存储和获取
redisTemplate.setKeySerializer(new StringRedisSerializer());
redisTemplate.setValueSerializer(jackson2JsonRedisSerializer);
redisTemplate.setHashKeySerializer(new StringRedisSerializer());
redisTemplate.setHashValueSerializer(jackson2JsonRedisSerializer);
return redisTemplate;
}
@Bean
public StringRedisTemplate stringRedisTemplate(RedisConnectionFactory factory) {
StringRedisTemplate stringRedisTemplate = new StringRedisTemplate();
stringRedisTemplate.setConnectionFactory(factory);
return stringRedisTemplate;
}
@Bean
public RedisTemplate<String, Serializable> limitRedisTemplate(LettuceConnectionFactory factory) {
RedisTemplate<String, Serializable> template = new RedisTemplate<String, Serializable>();
template.setKeySerializer(new StringRedisSerializer());
template.setValueSerializer(new GenericJackson2JsonRedisSerializer());
template.setConnectionFactory(factory);
return template;
}
/**
* 对hash类型的数据操作
*
* @param redisTemplate
* @return
*/
@Bean
public HashOperations<String, String, Object> hashOperations(RedisTemplate<String, Object> redisTemplate) {
return redisTemplate.opsForHash();
}
/**
* 对redis字符串类型数据操作
*
* @param redisTemplate
* @return
*/
@Bean
public ValueOperations<String, String> valueOperations(RedisTemplate<String, String> redisTemplate) {
return redisTemplate.opsForValue();
}
/**
* 对链表类型的数据操作
*
* @param redisTemplate
* @return
*/
@Bean
public ListOperations<String, Object> listOperations(RedisTemplate<String, Object> redisTemplate) {
return redisTemplate.opsForList();
}
/**
* 对无序集合类型的数据操作
*
* @param redisTemplate
* @return
*/
@Bean
public SetOperations<String, Object> setOperations(RedisTemplate<String, Object> redisTemplate) {
return redisTemplate.opsForSet();
}
/**
* 对有序集合类型的数据操作
*
* @param redisTemplate
* @return
*/
@Bean
public ZSetOperations<String, Object> zSetOperations(RedisTemplate<String, Object> redisTemplate) {
return redisTemplate.opsForZSet();
}
}
3.布隆过滤器工具类
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;
}
int sizeOfBitArray = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
return sizeOfBitArray;
}
/**
* 计算hash方法执行次数
*/
private int optimalNumOfHashFunctions(long n, long m) {
int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
return countOfHash;
}
}
@Component
public class BloomUtil {
private static int size = 1000000; //预计存放多少个key
private static double fpp = 0.001; //期望误判率, 千分之一
@Autowired
private RedisTemplate redisTemplate;
/**
* 初始化布隆过滤器，放入spring容器
* @return
*/
@Bean
public BloomFilterHelper<String> initBloomFilterHelper() {
return new BloomFilterHelper<>(
(Funnel<String>) (from, into) -> into.putString(from, Charsets.UTF_8).putString(from, Charsets.UTF_8),
size, fpp);
}
/**
* 根据给定的布隆过滤器添加值
* @param bloomFilterHelper
* @param key 布隆过滤器名称
* @param value 存入值
*/
public <T> void addByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
redisTemplate.opsForValue().setBit(key, i, true);
}
}
/**
* 根据给定的布隆过滤器判断值是否存在
* @param bloomFilterHelper
* @param key
* @param value
* @return
*/
public <T> boolean includeByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, 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;
}
}
4.测试代码
@Autowired
private BloomUtil bloomUtil;
@Autowired
private BloomFilterHelper bloomFilterHelper;
@GetMapping("/test1/{id}")
public String put(@PathVariable("id") Long id){
//id保存在布隆过滤器中
bloomUtil.addByBloomFilter(bloomFilterHelper,"bloomUser",id+"");
return "success";
}
@GetMapping("/test2/{id}")
public String get(@PathVariable("id") Long id){
//布隆过滤器中查询id是否存在
Boolean flag = bloomUtil.includeByBloomFilter(bloomFilterHelper,"bloomUser",id+"");
return flag.toString();
}
号外！号外！
如果这篇文章对你有所帮助，或者有所启发的话，帮忙点赞、在看、转发、收藏，你的支持就是我坚持下去的最大动力！
原文始发于微信公众号（一安未来）：面试官：如何通过布隆过滤器防止缓存穿透
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/44576.html
