RedisBloom插件：使Redis支持布隆和布谷鸟过滤器

缓存和数据处理的效率一直是大伙关注的重点。今天咱就来聊聊RedisBloom这个插件，它能让Redis支持布隆过滤器（Bloom Filter）和布谷鸟过滤器（Cuckoo Filter），在很多场景下都超有用，像处理缓存穿透、URL映射，还有黑名单管理这些。

一、布隆过滤器的原理剖析

布隆过滤器是1970年由Burton Howard Bloom提出的一种概率型数据结构，主要用来快速判断一个元素是不是可能在某个集合里。这玩意儿空间效率超高，查询速度也快，不过它有个小毛病，就是存在一定的误判率，而且不支持删除操作。

1.1 数据结构组成

布隆过滤器主要由两部分构成：

一个长长的二进制向量，刚开始里面所有的位都是0。这就好比是一个超级大的数组，每个位置只能存0或者1 。
一系列随机映射函数，一般是k个独立的哈希函数。这些函数就像一个个“小助手”，能把元素映射到二进制向量的不同位置上。

1.2 工作原理详解

添加元素：当要往布隆过滤器里添加一个元素时，就用这k个哈希函数对这个元素一顿“操作”，生成k个哈希值。然后把这些哈希值和二进制向量的长度取模，得到k个索引位置。最后把二进制向量里对应的这k个位置都改成1。
查询元素：查询的时候也用同样的k个哈希函数处理查询元素，得到k个哈希值，再检查二进制向量里对应的k个位置。要是有一个位置是0 ，那就说明这个元素肯定不在集合里；要是所有位置都是1，只能说这个元素可能在集合里，因为存在误判的情况。
误判率：误判率和二进制向量的大小（m）、哈希函数的数量（k），还有集合里元素的数量（n）关系可大了，公式是 [ P = (1 – e^{-kn/m})^k ] 。咱们可以通过调整m和k的值，在空间效率和误判率之间找到一个平衡点。

1.3 优点与不足分析

优点：它的空间效率真的很高，和存储完整的数据集相比，占用的内存那是少得可怜。查询速度也快，只需要计算哈希函数，然后检查二进制向量就行，时间复杂度是O(k) 。
不足：误判这个问题确实有点头疼，有可能把不在集合里的元素误判成在集合里，但它不会把在集合里的元素漏判。而且它不支持删除操作，因为多个元素可能共用相同的位，删一个元素可能会影响到其他元素。另外，它只能判断元素存不存在，没办法统计元素出现的次数。

二、布隆过滤器在Redis中的集成应用

Redis本身是不直接支持布隆过滤器的，不过借助RedisBloom这个插件就能实现这个功能。RedisBloom是个独立的模块，一般需要手动编译，然后加载到Redis里。

2.1 安装RedisBloom

在Linux系统下，安装RedisBloom按下面这些步骤来：

# 从GitHub下载RedisBloom的源码 git clone https://github.com/RedisBloom/RedisBloom.git cd RedisBloom # 编译源码 make # 把编译好的模块加载到Redis里 redis-server --loadmodule /path/to/redisbloom.so

2.2 RedisBloom提供的常用命令

BF.ADD key item：往布隆过滤器里添加单个元素。
BF.MADD key item1 item2 ...：一次添加多个元素到布隆过滤器。
BF.EXISTS key item：检查某个元素是否存在于布隆过滤器中。
BF.MEXISTS key item1 item2 ...：批量检查多个元素是否存在。
BF.RESERVE key error_rate capacity ：创建一个指定误判率和容量的布隆过滤器。

2.3 代码示例（Java与Jedis实现）

下面是用Java和Jedis操作Redis布隆过滤器的示例代码：

import redis.clients.jedis.Jedis; public class BloomFilterExample { public static void main(String[] args) { // 连接本地的Redis服务，端口号是6379 Jedis jedis = new Jedis("localhost", 6379); // 创建一个布隆过滤器，设置误判率为0.01，预期能容纳10000个元素 jedis.sendCommand(() -> "BF.RESERVE".getBytes(), "mybloom", "0.01", "10000"); // 往布隆过滤器里添加元素 jedis.sendCommand(() -> "BF.ADD".getBytes(), "mybloom", "apple"); jedis.sendCommand(() -> "BF.ADD".getBytes(), "mybloom", "banana"); // 检查元素是否存在 Long existsApple = (Long) jedis.sendCommand(() -> "BF.EXISTS".getBytes(), "mybloom", "apple"); Long existsOrange = (Long) jedis.sendCommand(() -> "BF.EXISTS".getBytes(), "mybloom", "orange"); // 输出检查结果 System.out.println("apple exists: " + (existsApple == 1)); System.out.println("orange exists: " + (existsOrange == 1)); // 关闭Jedis连接 jedis.close(); } }

2.4 RedisBloom源码分析

RedisBloom的核心代码在bloom.c文件里，下面简单说下部分关键逻辑：

初始化布隆过滤器：

BloomFilter *bf = createBloomFilter(error_rate, capacity); bf->bits = calloc(size, sizeof(uint8_t)); // 分配二进制向量空间 bf->hashes = k; // 设置哈希函数的数量

添加元素：

void bloomAdd(BloomFilter *bf, const char *item) { for (int i = 0; i < bf->hashes; i++) { // 使用MurmurHash计算哈希值 uint64_t hash = murmurhash(item, i); // 计算在二进制向量中的索引位置 uint64_t idx = hash % bf->size; // 将对应位置设置为1 setBit(bf->bits, idx); } }

查询元素：

int bloomCheck(BloomFilter *bf, const char *item) { for (int i = 0; i < bf->hashes; i++) { uint64_t hash = murmurhash(item, i); uint64_t idx = hash % bf->size; // 只要有一个位为0，就说明元素不在集合中 if (!getBit(bf->bits, idx)) return 0; } // 所有位都是1，说明元素可能存在 return 1; }

完整的源码可以去RedisBloom的GitHub仓库查看。

三、布谷鸟过滤器的应用解析

布隆过滤器虽然好用，但它不能删除元素这个缺点，在有些场景下就不太行了。这时候，布谷鸟过滤器就派上用场了。

3.1 布谷鸟过滤器的优势

支持删除操作：它不像布隆过滤器那样，而是通过存储指纹（fingerprint），可以安全地删除元素。
空间效率更高：在低误判率的情况下，布谷鸟过滤器比布隆过滤器更节省空间。
查询效率依然高效：查询复杂度是O(1)，速度杠杠的。

3.2 布谷鸟过滤器原理介绍

数据结构：布谷鸟过滤器是由多个桶（bucket）组成的哈希表，每个桶能存好几个指纹。每个元素通过两个哈希函数能映射到两个候选桶。
添加元素：计算元素的两个哈希值，找到对应的两个候选桶。要是有一个桶有空位，就把元素的指纹存进去；要是两个桶都满了，就随机踢出一个已有元素，然后把被踢出的元素重新插入。
删除元素：在两个候选桶里找元素的指纹，找到了就直接删除。
查询元素：检查两个候选桶里有没有匹配的指纹。

3.3 Redis中的布谷鸟过滤器实现

RedisBloom也支持布谷鸟过滤器，提供了下面这些命令：

CF.ADD key item：添加元素。
CF.DEL key item：删除元素。
CF.EXISTS key item：检查元素是否存在。
CF.RESERVE key capacity：创建指定容量的布谷鸟过滤器。

3.4 示例代码（Jedis实现）

import redis.clients.jedis.Jedis; public class CuckooFilterExample { public static void main(String[] args) { // 连接Redis服务 Jedis jedis = new Jedis("localhost", 6379); // 创建一个容量为10000的布谷鸟过滤器 jedis.sendCommand(() -> "CF.RESERVE".getBytes(), "mycuckoo", "10000"); // 添加元素 jedis.sendCommand(() -> "CF.ADD".getBytes(), "mycuckoo", "apple"); // 检查元素是否存在 Long existsApple = (Long) jedis.sendCommand(() -> "CF.EXISTS".getBytes(), "mycuckoo", "apple"); System.out.println("apple exists: " + (existsApple == 1)); // 删除元素 jedis.sendCommand(() -> "CF.DEL".getBytes(), "mycuckoo", "apple"); // 再次检查元素是否存在 existsApple = (Long) jedis.sendCommand(() -> "CF.EXISTS".getBytes(), "mycuckoo", "apple"); System.out.println("apple exists after delete: " + (existsApple == 1)); // 关闭Jedis连接 jedis.close(); } }

3.5 RedisBloom中布谷鸟过滤器源码解读

布谷鸟过滤器的源码在cuckoo.c文件里，核心逻辑如下：

插入元素：

int cuckooInsert(CuckooFilter *cf, const char *item) { // 计算第一个哈希值 uint64_t h1 = hash1(item); // 计算第二个哈希值 uint64_t h2 = hash2(item); // 获取元素的指纹 uint8_t fingerprint = getFingerprint(item); // 尝试插入到第一个候选桶或第二个候选桶 if (insertToBucket(cf, h1, fingerprint) || insertToBucket(cf, h2, fingerprint)) { return 1; // 插入成功 } // 触发“布谷鸟”策略，递归插入 return relocate(cf, h1, h2, fingerprint); }

删除元素：

int cuckooDelete(CuckooFilter *cf, const char *item) { // 计算两个哈希值 uint64_t h1 = hash1(item); uint64_t h2 = hash2(item); // 获取元素的指纹 uint8_t fingerprint = getFingerprint(item); // 尝试从第一个候选桶或第二个候选桶删除 if (removeFromBucket(cf, h1, fingerprint) || removeFromBucket(cf, h2, fingerprint)) { return 1; // 删除成功 } return 0; }