在之前的一篇文章中，我们已经深入理解了布隆过滤器的基本原理，并且了解到它在缓存系统中有较多的应用。Redis 提供的 Bitmap 正好能够作为布隆过滤器所需要的位数组的基础，本文先简要介绍 Bitmap，然后给出基于它的布隆过滤器实现。

Bitmap 在 Redis 中并不是一个单独的数据类型，而是由字符串类型（Redis 内部称 Simple Dynamic String，SDS）之上定义的与比特相关的操作实现的，此时 SDS 就被当做位数组了。下面是在 redis-cli 中使用 getbit 和 setbit 指令的操作示例。

字符串”meow”的二进制表示：01101101 01100101 01101111 01110111

es1:19000> set bitmap_cat “meow”
OK

最低位下标为0。取得第3位的比特（0）

es1:19000> getbit bitmap_cat 3
(integer) 0

取得第23位的比特（1）

es1:19000> getbit bitmap_cat 23
(integer) 1

将第7位设为0

es1:19000> setbit bitmap_cat 7 0
(integer) 1

将第14位设为1

es1:19000> setbit bitmap_cat 14 1
(integer) 0

修改过后的字符串变成了”lgow”

es1:19000> get bitmap_cat
“lgow”
Redis 的 Bitmap 是自动扩容的，亦即 get/set 到高位时，就会主动填充 0。此外，还有 bitcount 指令用于计算特定字节范围内 1 的个数，bitop 指令用来执行位运算（支持 and、or、xor 和 not）。相应的用法可以查询 Redis 官方文档等。

下面我们基于 Redis（Codis）实现布隆过滤器 RedisBloomFilter。根据之前讲解布隆过滤器的文章，要初始化一个布隆过滤器的话，需要两个参数：预估的元素数量，以及可接受的最大误差（即假阳性率）。另外，我们也需要传入 Jodis 的连接池实例 JedisResourcePool，以方便在 Redis 上操作。RedisBloomFilter 类的成员和构造方法如下所示。

  1. public class RedisBloomFilter {
  2. private static final Logger LOGGER = Logger.getLogger(RedisBloomFilter.class);
  3. private static final String BF_KEY_PREFIX = "bf:";
  4. private int numApproxElements;
  5. private double fpp;
  6. private int numHashFunctions;
  7. private int bitmapLength;
  9. private JedisResourcePool jedisResourcePool;
  11. /**
  12.  * 构造布隆过滤器。注意：在同一业务场景下，三个参数务必相同
  13.  *
  14.  * @param numApproxElements 预估元素数量
  15.  * @param fpp               可接受的最大误差（假阳性率）
  16.  * @param jedisResourcePool Codis专用的Jedis连接池
  17.  */
  18. public RedisBloomFilter(int numApproxElements, double fpp, JedisResourcePool jedisResourcePool) {
  19.     this.numApproxElements = numApproxElements;
  20.     this.fpp = fpp;
  21.     this.jedisResourcePool = jedisResourcePool;
  23.     bitmapLength = (int) (-numApproxElements * Math.log(fpp) / (Math.log(2) * Math.log(2)));
  24.     numHashFunctions = Math.max(1, (int) Math.round((double) bitmapLength / numApproxElements * Math.log(2)));
  25. }
  27. /**
  28.  * 取得自动计算的最优哈希函数个数
  29.  */
  30. public int getNumHashFunctions() {
  31.     return numHashFunctions;
  32. }
  34. /**
  35.  * 取得自动计算的最优Bitmap长度
  36.  */
  37. public int getBitmapLength() {
  38.     return bitmapLength;
  39. }
  41. // 以下都是方法
  42. }


为了区分出布隆过滤器对应的 Key，在原始 Key 的前面都加上 “bf:” 前缀。Bitmap 长度 bitmapLength 和哈希函数个数 numHashFunctions 则利用 Guava 版实现中的方法来计算。

然后，我们需要计算一个元素被 k 个哈希函数散列后，对应到 Bitmap 的哪些比特上。这里仍然借鉴了 Guava 的 BloomFilterStrategies 实现，采用 MurmurHash 和双重哈希进行散列。为了应用简单，假设所有元素固定为字符串类型，不用泛型。

  1. /**
  2.  * 计算一个元素值哈希后映射到Bitmap的哪些bit上
  3.  *
  4.  * @param element 元素值
  5.  * @return bit下标的数组
  6.  */
  7. private long[] getBitIndices(String element) {
  8.     long[] indices = new long[numHashFunctions];
  10.     byte[] bytes = Hashing.murmur3_128()
  11.         .hashObject(element, Funnels.stringFunnel(Charset.forName("UTF-8")))
  12.         .asBytes();
  14.     long hash1 = Longs.fromBytes(
  15.         bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]
  16.     );
  17.     long hash2 = Longs.fromBytes(
  18.         bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]
  19.     );
  21.     long combinedHash = hash1;
  22.     for (int i = 0; i < numHashFunctions; i++) {
  23.         indices[i] = (combinedHash & Long.MAX_VALUE) % bitmapLength;
  24.         combinedHash += hash2;
  25.     }
  27.     return indices;
  28. }

然后我们就可以通过 Jedis 的 setbit () 和 getbit () 方法来实现向布隆过滤器中插入元素与查询元素是否存在的逻辑了。一个元素会对应多个比特，为了提高效率，流水线就派上用场了。另外，setbit 指令不会重置对应 Key 的过期时间戳。

  1. /**
  2.  * 插入元素
  3.  *
  4.  * @param key       原始Redis键，会自动加上'bf:'前缀
  5.  * @param element   元素值，字符串类型
  6.  * @param expireSec 过期时间（秒）
  7.  */
  8. public void insert(String key, String element, int expireSec) {
  9.     if (key == null || element == null) {
  10.         throw new RuntimeException("键值均不能为空");
  11.     }
  12.     String actualKey = BF_KEY_PREFIX.concat(key);
  14.     try (Jedis jedis = jedisResourcePool.getResource()) {
  15.         try (Pipeline pipeline = jedis.pipelined()) {
  16.             for (long index : getBitIndices(element)) {
  17.                 pipeline.setbit(actualKey, index, true);
  18.             }
  19.             pipeline.syncAndReturnAll();
  20.         } catch (IOException ex) {
  21.             LOGGER.error("pipeline.close()发生IOException", ex);
  22.         }
  23.         jedis.expire(actualKey, expireSec);
  24.     }
  25. }
  27. /**
  28.  * 检查元素在集合中是否（可能）存在
  29.  *
  30.  * @param key     原始Redis键，会自动加上'bf:'前缀
  31.  * @param element 元素值，字符串类型
  32.  */
  33. public boolean mayExist(String key, String element) {
  34.     if (key == null || element == null) {
  35.         throw new RuntimeException("键值均不能为空");
  36.     }
  37.     String actualKey = BF_KEY_PREFIX.concat(key);
  38.     boolean result = false;
  40.     try (Jedis jedis = jedisResourcePool.getResource()) {
  41.         try (Pipeline pipeline = jedis.pipelined()) {
  42.             for (long index : getBitIndices(element)) {
  43.                 pipeline.getbit(actualKey, index);
  44.             }
  45.             result = !pipeline.syncAndReturnAll().contains(false);
  46.         } catch (IOException ex) {
  47.             LOGGER.error("pipeline.close()发生IOException", ex);
  48.         }
  49.     }
  51.     return result;
  52. }

完毕，写个简单的单元测试吧。假设现在用布隆过滤器来存储已读帖子的 ID，Key 中包含用户 ID 和时间。每天预估的每用户最大阅读量是 3000 篇，最大误差 3%。

  1. public class RedisBloomFilterTest {
  2. private static final int NUM_APPROX_ELEMENTS = 3000;
  3. private static final double FPP = 0.03;
  4. private static final int DAY_SEC = 60  60  24;
  5. private static JedisResourcePool jedisResourcePool;
  6. private static RedisBloomFilter redisBloomFilter;
  8. @BeforeClass
  9. public static void beforeClass() throws Exception {
  10.     jedisResourcePool = RoundRobinJedisPool.create()
  11.         .curatorClient("10.10.99.130:2181,10.10.99.132:2181,10.10.99.133:2181,10.10.99.124:2181,10.10.99.125:2181,", 10000)
  12.         .zkProxyDir("/jodis/bd-redis")
  13.         .build();
  14.     redisBloomFilter = new RedisBloomFilter(NUM_APPROX_ELEMENTS, FPP, jedisResourcePool);
  15.     System.out.println("numHashFunctions: " + redisBloomFilter.getNumHashFunctions());
  16.     System.out.println("bitmapLength: " + redisBloomFilter.getBitmapLength());
  17. }
  19. @AfterClass
  20. public static void afterClass() throws Exception {
  21.     jedisResourcePool.close();
  22. }
  24. @Test
  25. public void testInsert() throws Exception {
  26.     redisBloomFilter.insert("topic_read:8839540:20190609", "76930242", DAY_SEC);
  27.     redisBloomFilter.insert("topic_read:8839540:20190609", "76930243", DAY_SEC);
  28.     redisBloomFilter.insert("topic_read:8839540:20190609", "76930244", DAY_SEC);
  29.     redisBloomFilter.insert("topic_read:8839540:20190609", "76930245", DAY_SEC);
  30.     redisBloomFilter.insert("topic_read:8839540:20190609", "76930246", DAY_SEC);
  31. }
  33. @Test
  34. public void testMayExist() throws Exception {
  35.     System.out.println(redisBloomFilter.mayExist("topic_read:8839540:20190609", "76930242"));
  36.     System.out.println(redisBloomFilter.mayExist("topic_read:8839540:20190609", "76930244"));
  37.     System.out.println(redisBloomFilter.mayExist("topic_read:8839540:20190609", "76930246"));
  38.     System.out.println(redisBloomFilter.mayExist("topic_read:8839540:20190609", "76930248"));
  39. }
  40. }


观察输出。

numHashFunctions: 5
bitmapLength: 21895
true
true
true
false
13 人点赞
Redis

作者：LittleMagic
链接：https://www.jianshu.com/p/c2defe549b40
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。