基于Redis的BloomFilter实现

phodal 发布于2019-08-16 13:58 / 653人阅读

摘要：再来看怎么结合一起使用根据给定的布隆过滤器添加值不能为空根据给定的布隆过滤器判断值是否存在不能为空很简单，只有两个方法，往里面添加元素，检查元素是否在里面这里的客户端使用的是封装的，可以在我的项目中查看完整的使用代码。

前言

最近在研究布隆过滤器（如果不了解什么是布隆过滤器的，推荐看这篇如何判断一个元素在亿级数据中是否存在？了解），发现Guava提供了封装好的类，但是只能单机使用，一般现在的应用都是部署在分布式系统的，所以想找个可以在分布式系统下使用的布隆过滤器，找了半天只找到一个基于redis开发的模块项目ReBloom，但是这个是需要额外安装的，而且文档里只说了怎么在docker下运行，没研究过docker所以放弃了。后来找到一篇博客讲怎么利用布隆过滤器统计消息未读数的（博客地址不记得了，是一位淘宝同学写的），博客最后放了一份整合redis和bloomFilter的代码demo，详见BloomFilter.java，看了下实现比较简单，但是使用方式不是我想要的，所以参考着自己整理了一份。

BloomFilterHelper

package com.doodl6.springmvc.service.cache.redis;

import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;

public class BloomFilterHelper {

    private int numHashFunctions;

    private int bitSize;

    private Funnel funnel;

    public BloomFilterHelper(Funnel funnel, int expectedInsertions, double fpp) {
        Preconditions.checkArgument(funnel != null, "funnel不能为空");
        this.funnel = funnel;
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }

    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)));
    }
}

BloomFilterHelper是实现功能的关键，包含了计算bitmap的核心算法，其实大部分代码都是来源于Guava库里面的BloomFilterStrategies类，但是因为这个类是专门为Guava的BloomFilter类使用的，所以没有对外暴露一些重要的算法逻辑。

再来看怎么结合redis一起使用BloomFilterHelper

RedisService

package com.doodl6.springmvc.service.cache.redis;

import com.google.common.base.Preconditions;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;

import javax.annotation.Resource;
import java.util.Collection;
import java.util.Map;
import java.util.concurrent.TimeUnit;

@Service
public class RedisService {

    @Resource
    private RedisTemplate redisTemplate;

    /**
     * 根据给定的布隆过滤器添加值
     */
    public  void addByBloomFilter(BloomFilterHelper 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);
        }
    }

    /**
     * 根据给定的布隆过滤器判断值是否存在
     */
    public  boolean includeByBloomFilter(BloomFilterHelper 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;
    }
}

RedisService很简单，只有两个方法

addByBloomFilter，往redis里面添加元素

includeByBloomFilter，检查元素是否在redis bloomFilter里面

这里redis的客户端使用的是spring-data-redis封装的，可以在我的项目SpringMVC-Project中查看完整的使用代码。

云内存存储UMem Redis 基于webrtc的电话回声消除的研究与实现基于webrtc的视频会议系统的设计与实现基于防火墙技术的校园网络安全设计与实现基于webrtc实现对讲

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72665.html

基于Redis的BloomFilter实现

摘要：再来看怎么结合一起使用根据给定的布隆过滤器添加值不能为空根据给定的布隆过滤器判断值是否存在不能为空很简单，只有两个方法，往里面添加元素，检查元素是否在里面这里的客户端使用的是封装的，可以在我的项目中查看完整的使用代码。前言最近在研究布隆过滤器（如果不了解什么是布隆过滤器的，推荐看这篇如何判断一个元素在亿级数据中是否存在？了解），发现Guava提供了封装好的类，但是只能单机使用，一般...

kun_jian 2019-07-24 16:05 评论0 收藏0
[轮子系列]Google Guava之BloomFilter源码分析及基于Redis的重构

摘要：方法，即表示自动扩容，这个函数名是从中搬过来的。自动扩容最后，也是最重要的，其中用了布隆过滤器中计算型数组长度的方法，得到之后使用命令初始化一个全部为的位数组。本文源地址：http://www.fullstackyang.com/...，转发请注明该地址或segmentfault地址，谢谢！一、背景知识在网上已经有很多关于布隆过滤器的介绍了，这里就不再赘述，下面简单地提炼几个要点...

xiangchaobin 2019-08-15 13:25 评论0 收藏0
【数据库】Redis集群篇

摘要：类似代码实现如下从缓存中获取数据缓存为空从存储中获取如果存储数据为空，需要设置一个过期时间秒缓存非空布隆过滤器拦截就类似于一个，用于快速判某个元素是否存在于集合中，其典型的应用场景就是快速判断一个是否存在于某容器，不存在就直接返回。欢迎关注公众号：【爱编码】如果有需要后台回复2019赠送1T的学习资料哦！！ showImg(https://upload-images.jianshu....

raoyi 2019-07-24 16:22 评论0 收藏0
Redis缓存穿透问题及解决方案

摘要：方案二布隆过滤器拦截布隆过滤器介绍概念布隆过滤器英语是年由布隆提出的。这就是布隆过滤器的基本思想。防缓存穿透的布隆过滤器判断是否为合法非法则不允许继续查库从缓存中获取数据缓存为空从数据库中获取缓存空对象参考书籍开发与运维上周在工作中遇到了一个问题场景，即查询商品的配件信息时（商品：配件为1：N的关系），如若商品并未配置配件信息，则查数据库为空，且不会加入缓存，这就会导致，下次在查询同...

AlanKeene 2019-08-16 13:57 评论0 收藏0
Redis缓存穿透问题及解决方案

摘要：方案二布隆过滤器拦截布隆过滤器介绍概念布隆过滤器英语是年由布隆提出的。这就是布隆过滤器的基本思想。防缓存穿透的布隆过滤器判断是否为合法非法则不允许继续查库从缓存中获取数据缓存为空从数据库中获取缓存空对象参考书籍开发与运维上周在工作中遇到了一个问题场景，即查询商品的配件信息时（商品：配件为1：N的关系），如若商品并未配置配件信息，则查数据库为空，且不会加入缓存，这就会导致，下次在查询同...

Anonymous1 2019-07-24 16:02 评论0 收藏0