[大数据]基于Redis位图BitMap的布隆过滤器(附源码)

Redis的 bitmap 支持2^32大小，内存最大512MB，误判率万分之一 ，差不多可以放下2亿左右的数据，性能高，空间占用率极小，省去了大量无效的数据库连接。可用于实现用户签到、用户日活、在线状态、布隆过滤器等。

本文主要讲解基于Redis的 Bitmap (位图) 实现布隆过滤器，可用于防止缓存穿透等场景。

1.主要涉及知识点

• jedis连接池
• pipeline redis管道技术，也叫流水线
• 位图bitMap

2.布隆过滤器代码实现

注：这里仅列出了部分核心代码实现，详见文末源码链接

/**
 * 基于Redis - BitMap实现的布隆过滤器
 *
 * @author 程序员小强
 */
public class RedisBitMapBloomFilter {

    private static final Logger LOGGER = LoggerFactory.getLogger(RedisBitMapBloomFilter.class);

    /**
     * 公共key前缀
     */
    private static final String BF_KEY_PREFIX = "bf:";

    /**
     * jedis连接池
     */
    private JedisPool jedisPool;

    /**
     * bit数组长度
     */
    private long bitmapLength;

    /**
     * Hash 函数个数
     */
    private int hashFunctionNum;

    /**
     * redis Key
     */
    private String key;

    /**
     * 失效时间
     */
    private int expireSecond;


    /**
     * 构造 布隆过滤器
     *
     * @param key            redis key
     * @param expireSecond   过期时间（秒）
     * @param maxElementSize 预估元素数量
     * @param fpp            可接受的最大误差率：示例0.01
     * @param jedisPool      Jedis连接池
     */
    public RedisBitMapBloomFilter(String key, int expireSecond, int maxElementSize, double fpp, JedisPool jedisPool) {
        this.jedisPool = jedisPool;
        this.key = key;
        this.expireSecond = expireSecond;
        //计算bit数组长度
        bitmapLength = (int) (-maxElementSize * Math.log(fpp) / (Math.log(2) * Math.log(2)));
        //计算hash函数个数
        hashFunctionNum = Math.max(1, (int) Math.round((double) bitmapLength / maxElementSize * Math.log(2)));
    }

    /**
     * 构造 布隆过滤器
     *
     * @param maxElementSize 预估元素数量
     * @param fpp            可接受的最大误差率：示例0.01
     * @param jedisPool      Jedis连接池
     */
    public RedisBitMapBloomFilter(int maxElementSize, double fpp, JedisPool jedisPool) {
        this.jedisPool = jedisPool;
        //计算bit数组长度
        bitmapLength = (int) (-maxElementSize * Math.log(fpp) / (Math.log(2) * Math.log(2)));
        //计算hash函数个数
        hashFunctionNum = Math.max(1, (int) Math.round((double) bitmapLength / maxElementSize * Math.log(2)));
    }

    /**
     * 插入元素
     *
     * @param element 元素值
     */
    public void put(Object element) {
        this.put(this.key, element, this.expireSecond);
    }

    /**
     * 检查元素在集合中是否（可能）存在
     *
     * @param element 元素值
     */
    public boolean contains(Object element) {
        return this.contains(this.key, element);
    }

    /**
     * 插入元素
     *
     * @param key          原始Redis键，会自动加上'bf:'前缀
     * @param element      元素值，默认 toString后存储
     * @param expireSecond 过期时间（秒）
     */
    public void put(String key, Object element, int expireSecond) {
        if (key == null || element == null) {
            throw new RedisBloomFilterException("key or element  is not null");
        }

        Jedis jedis = null;
        String redisBitKey = BF_KEY_PREFIX.concat(key);
        try {
            //获得连接
            jedis = jedisPool.getResource();
            //获得redis管道
            Pipeline pipeline = jedis.pipelined();
            for (long index : getBitIndices(element.toString())) {
                pipeline.setbit(redisBitKey, index, true);
            }
            pipeline.syncAndReturnAll();
            //刷新过期时间
            jedis.expire(redisBitKey, expireSecond);
        } catch (JedisException ex) {
            LOGGER.error("[ RedisBloomFilter ] >> put exception >>  messages:{}", ex.getMessage(), ex);
            throw new RedisBloomFilterException("[ RedisBloomFilter ] >> put exception " + ex.getMessage());
        } finally {
            if (jedis != null) {
                if (jedis.isConnected()) {
                    jedis.close();
                }
            }
        }
    }

    /**
     * 检查元素在集合中是否（可能）存在
     *
     * @param key     原始Redis键，会自动加上'bf:'前缀
     * @param element 元素值
     */
    public boolean contains(String key, Object element) {
        if (key == null || element == null) {
            throw new RuntimeException("键值均不能为空");
        }
        boolean result;
        Jedis jedis = null;
        String redisBitKey = BF_KEY_PREFIX.concat(key);
        try {
            //获得连接
            jedis = jedisPool.getResource();
            //获得redis管道
            Pipeline pipeline = jedis.pipelined();
            for (long index : getBitIndices(element.toString())) {
                pipeline.getbit(redisBitKey, index);
            }
            result = !pipeline.syncAndReturnAll().contains(false);
        } catch (JedisException ex) {
            LOGGER.error("[ RedisBloomFilter ] >> contains exception >>  messages:{}", ex.getMessage(), ex);
            throw new RedisBloomFilterException("[ RedisBloomFilter ] >> contains exception " + ex.getMessage());
        } finally {
            if (jedis != null) {
                if (jedis.isConnected()) {
                    jedis.close();
                }
            }
        }
        return result;
    }

    /**
     * 计算一个元素值哈希后映射到Bitmap的哪些bit上
     *
     * @param element 元素值
     * @return bit下标的数组
     */
    private long[] getBitIndices(String element) {
        long hash64 = Hashing.murmur3_128()
                .hashObject(element, Funnels.stringFunnel(Charset.forName("UTF-8")))
                .asLong();
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);

        long[] offset = new long[hashFunctionNum];
        for (int i = 1; i <= hashFunctionNum; i++) {
            int nextHash = hash1 + i * hash2;
            if (nextHash < 0) {
                nextHash = ~nextHash;
            }
            offset[i - 1] = nextHash % bitmapLength;
        }

        return offset;
    }

    public long getBitmapLength() {
        return bitmapLength;
    }

    public int getHashFunctionNum() {
        return hashFunctionNum;
    }
}

3.使用与测试Demo

/**
 * @author 程序员小强
 */
public class RedisBloomFilterTest {

    /**
     * 预估元素数量
     */
    private static final int MAX_ELEMENT_SIZE = 10000 * 120;

    /**
     * 误差率
     */
    private static final double FPP = 0.001;

    /**
     * 过期时间-秒
     */
    private static final int EXPIRE_SECOND = 60 * 60 * 24;

    private static final String REDIS_KEY = "my_test_bloom_filter";

    private static RedisBitMapBloomFilter redisBloomFilter;

    @BeforeClass
    public static void beforeClass() throws Exception {
        JedisPool jedisPool = new JedisPool(new JedisPoolConfig(), "127.0.0.1", 6379, 1000, "123456", 0);
        redisBloomFilter = new RedisBitMapBloomFilter(REDIS_KEY, EXPIRE_SECOND, MAX_ELEMENT_SIZE, FPP, jedisPool);
        System.out.println("Hash 函数个数 : " + redisBloomFilter.getHashFunctionNum());
        System.out.println("bit数组长度 : " + redisBloomFilter.getBitmapLength());
    }

    @Test
    public void testPut() {
        redisBloomFilter.put(1001);
        redisBloomFilter.put(1002);
        redisBloomFilter.put(1003);
        redisBloomFilter.put(1004);
        redisBloomFilter.put(1005);
    }

    @Test
    public void testContains() throws Exception {
        System.out.println(redisBloomFilter.contains(1001));
        System.out.println(redisBloomFilter.contains(1002));
        System.out.println(redisBloomFilter.contains(1003));
        System.out.println(redisBloomFilter.contains(1006));
    }

}   

先执行testPut存储数据后执行t estContains 输出内容如下

Hash 函数个数 : 10
bit数组长度 : 17253105
true
true
true
true

4.源码地址

https://github.com/xqiangme/spring-boot-example/tree/master/spring-boot-redis-bloomFilter