失眠网 > 基于Redis位图BitMap的布隆过滤器(附源码)

基于Redis位图BitMap的布隆过滤器(附源码)

时间：2024-04-09 22:33:15

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 jedisPoolJedis连接池*/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 jedisPoolJedis连接池*/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;@BeforeClasspublic 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());}@Testpublic void testPut() {redisBloomFilter.put(1001);redisBloomFilter.put(1002);redisBloomFilter.put(1003);redisBloomFilter.put(1004);redisBloomFilter.put(1005);}@Testpublic 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 函数个数 : 10bit数组长度 : 17253105truetruetruetrue