本篇文章为你整理了Redis实现布隆过滤器解析（redisson布隆过滤器）的详细内容，包含有redistemplate 布隆过滤器 redisson布隆过滤器 redis bitmap 布隆过滤 java布隆过滤器解决redis缓存穿透 Redis实现布隆过滤器解析，希望能帮助你了解 Redis实现布隆过滤器解析。
介绍了布隆过滤器的原理，结合分析guava框架如何实现JVM层面的布隆过滤器，参照guava编写Redis实现的分布式布隆过滤器
【1】概念说明
1）布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
【2】设计思想
1）BF是由一个长度为m比特的位数组（bit array）与k个哈希函数（hash function）组成的数据结构。位数组均初始化为0，所有哈希函数都可以分别把输入数据尽量均匀地散列。
2）当要插入一个元素时，将其数据分别输入k个哈希函数，产生k个哈希值。以哈希值作为位数组中的下标，将所有k个对应的比特置为1。
3）当要查询（即判断是否存在）一个元素时，同样将其数据输入哈希函数，然后检查对应的k个比特。如果有任意一个比特为0，表明该元素一定不在集合中。如果所有比特均为1，表明该集合有（较大的）可能性在集合中。为什么不是一定在集合中呢？因为一个比特被置为1有可能会受到其他元素的影响，这就是所谓“假阳性”（false positive）。相对地，“假阴性”（false negative）在BF中是绝不会出现的。
【3】图示
【4】优缺点
1）优点
1.不需要存储数据本身，只用比特表示，因此空间占用相对于传统方式有巨大的优势，并且能够保密数据；
2.时间效率也较高，插入和查询的时间复杂度均为O(k)；
3.哈希函数之间相互独立，可以在硬件指令层面并行计算。
2）缺点
1.存在假阳性的概率，不适用于任何要求100%准确率的情境；
2.只能插入和查询元素，不能删除元素，这与产生假阳性的原因是相同的。我们可以简单地想到通过计数（即将一个比特扩展为计数值）来记录元素数，但仍然无法保证删除的元素一定在集合中。（因此只能进行重建）
guava框架如何实现布隆过滤器
【1】引入依赖
dependency
groupId com.google.guava /groupId
artifactId guava /artifactId
version 28.0-jre /version
/dependency
【2】简单使用
//布隆过滤器-数字指纹存储在当前jvm当中
public class LocalBloomFilter {
private static final BloomFilter String bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8),1000000,0.01);
* 谷歌guava布隆过滤器
* @param id
* @return
public static boolean match(String id){
return bloomFilter.mightContain(id);
public static void put(Long id){
bloomFilter.put(id+"");
}
【3】源码分析（由上面的三个主要方法看起，create方法，mightContain方法，put方法）
1）create方法深入分析
@VisibleForTesting
static T BloomFilter T create(Funnel ? super T funnel, long expectedInsertions, double fpp, Strategy strategy) {
//检测序列化器
checkNotNull(funnel);
//检测存储容量
checkArgument(expectedInsertions = 0, "Expected insertions (%s) must be = 0", expectedInsertions);
//容错率应该在0-1之前
checkArgument(fpp 0.0, "False positive probability (%s) must be 0.0", fpp);
checkArgument(fpp 1.0, "False positive probability (%s) must be 1.0", fpp);
//检测策略
checkNotNull(strategy);
if (expectedInsertions == 0) {
expectedInsertions = 1;
// 这里numBits即底下LockFreeBitArray位数组的长度，可以看到计算方式就是外部传入的期待数和容错率
long numBits = optimalNumOfBits(expectedInsertions, fpp);
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
try {
return new BloomFilter T (new BitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException e) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
private BloomFilter(BitArray bits, int numHashFunctions, Funnel ? super T funnel, Strategy strategy) {
//检测hash函数个数应该在0-255之间
checkArgument(numHashFunctions 0, "numHashFunctions (%s) must be 0", numHashFunctions);
checkArgument(numHashFunctions = 255, "numHashFunctions (%s) must be = 255", numHashFunctions);
this.bits = checkNotNull(bits);
this.numHashFunctions = numHashFunctions;
this.funnel = checkNotNull(funnel);
this.strategy = checkNotNull(strategy);
static int optimalNumOfHashFunctions(long n, long m) {
// (m / n) * log(2), but avoid truncation due to division!
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
2）mightContain方法深入分析
public boolean mightContain(T object) {
return strategy.mightContain(object, funnel, numHashFunctions, bits);
public T boolean mightContain(T object, Funnel ? super T funnel, int numHashFunctions, BloomFilterStrategies.BitArray bits) {
long bitSize = bits.bitSize();
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
int hash1 = (int)hash64;
int hash2 = (int)(hash64 32);
for(int i = 1; i = numHashFunctions; ++i) {
int combinedHash = hash1 + i * hash2;
if (combinedHash 0) {
combinedHash = ~combinedHash;
if (!bits.get((long)combinedHash % bitSize)) {
return false;
return true;
}
3）put方法深入分析
@CanIgnoreReturnValue
public boolean put(T object) {
return strategy.put(object, funnel, numHashFunctions, bits);
//策略实现填入bits
public T boolean put(T object, Funnel ? super T funnel, int numHashFunctions, BloomFilterStrategies.BitArray bits) {
long bitSize = bits.bitSize();
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
int hash1 = (int)hash64;
int hash2 = (int)(hash64 32);
boolean bitsChanged = false;
for(int i = 1; i = numHashFunctions; ++i) {
int combinedHash = hash1 + i * hash2;
if (combinedHash 0) {
combinedHash = ~combinedHash;
bitsChanged = bits.set((long)combinedHash % bitSize);
return bitsChanged;
}
采用Redis实现布隆过滤器
【1】抽出guava框架中部分核心逻辑方法形成工具类
/**
* 算法过程：
* 1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数
* 2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
* 3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
* 4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
* @description: 布隆过滤器，摘录自Google-guava包
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];
//有点类似于hashmap中采用高32位与低32位相与获得hash值
long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 32);
//采用对低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数组长度
* Math.log(2) = 0.6931471805599453;（取0.693147来用）
* (Math.log(2) * Math.log(2)) = 0.48045237;
* 假设传入n为1,000,000 , p为0.01;
* Math.log(0.01) = -4.605170185988091;
* 则返回值为9,585,071 ,即差不多是预设容量的10倍
* 要知道 1MB = 1024KB , 1KB = 1024B ,1B=8bit。
* 也就是对一百万数据预计花费的内存为1.143MB的内存
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)));
}
【2】构建Redis实现布隆过滤器的服务类
public class BloomRedisService {
private RedisTemplate String, Object redisTemplate;
private BloomFilterHelper bloomFilterHelper;
public void setBloomFilterHelper(BloomFilterHelper bloomFilterHelper) {
this.bloomFilterHelper = bloomFilterHelper;
public void setRedisTemplate(RedisTemplate String, Object redisTemplate) {
this.redisTemplate = redisTemplate;
* 根据给定的布隆过滤器添加值
* 这里可以考虑LUA脚本进行优化，减少传输次数
* 如 eval "redis.call(setbit,KEYS[1],ARGV[1],1) redis.call(setbit,KEYS[1],ARGV[2],1) " 1 mybool 243 5143
* 但是又需要衡量操作的时间，与如果次数很多导致的传输的数据量很大容易阻塞问题
public T 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 T 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;
}
【3】编辑配置类
@Slf4j
@Configuration
public class BloomFilterConfig implements InitializingBean{
@Autowired
private PmsProductService productService;
@Autowired
private RedisTemplate template;
@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);
// 布隆过滤器bean注入
@Bean
public BloomRedisService bloomRedisService(){
BloomRedisService bloomRedisService = new BloomRedisService();
bloomRedisService.setBloomFilterHelper(initBloomFilterHelper());
bloomRedisService.setRedisTemplate(template);
return bloomRedisService;
@Override
public void afterPropertiesSet() throws Exception {
List Long list = productService.getAllProductId();
log.info("加载产品到布隆过滤器当中,size:{}",list.size());
if(!CollectionUtils.isEmpty(list)){
list.stream().forEach(item- {
//LocalBloomFilter.put(item);
bloomRedisService().addByBloomFilter(RedisKeyPrefixConst.PRODUCT_REDIS_BLOOM_FILTER,item+"");
}
【4】构建布隆过滤器的拦截器
//拦截器，所有需要查看商品详情的请求必须先过布隆过滤器
@Slf4j
public class BloomFilterInterceptor implements HandlerInterceptor {
@Autowired
private BloomRedisService bloomRedisService;
@Override
public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception {
String currentUrl = request.getRequestURI();
PathMatcher matcher = new AntPathMatcher();
//解析出pathvariable
Map String, String pathVariable = matcher.extractUriTemplateVariables("/pms/productInfo/{id}", currentUrl);
//布隆过滤器存储在redis中
if(bloomRedisService.includeByBloomFilter(RedisKeyPrefixConst.PRODUCT_REDIS_BLOOM_FILTER,pathVariable.get("id"))){
return true;
* 不在布隆过滤器当中，直接返回验证失败
* 设置响应头
response.setHeader("Content-Type","application/json");
response.setCharacterEncoding("UTF-8");
String result = new ObjectMapper().writeValueAsString(CommonResult.validateFailed("产品不存在!"));
response.getWriter().print(result);
return false;
}
【5】将拦截器注册进SpringMVC中
@Configuration
public class IntercepterConfiguration implements WebMvcConfigurer {
@Override
public void addInterceptors(InterceptorRegistry registry) {
//注册拦截器
registry.addInterceptor(authInterceptorHandler())
.addPathPatterns("/pms/productInfo/**");
@Bean
public BloomFilterInterceptor authInterceptorHandler(){
return new BloomFilterInterceptor();
}
以上就是Redis实现布隆过滤器解析（redisson布隆过滤器）的详细内容，想要了解更多 Redis实现布隆过滤器解析的内容，请持续关注盛行IT软件开发工作室。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。