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

文
章
目
录

• 一、布隆过滤器的原理剖析
• 1.1 数据结构组成
• 1.2 工作原理详解
• 1.3 优点与不足分析
• 二、布隆过滤器在Redis中的集成应用
• 2.1 安装RedisBloom
• 2.2 RedisBloom提供的常用命令
• 2.3 代码示例（Java与Jedis实现）
• 2.4 RedisBloom源码分析
• 三、布谷鸟过滤器的应用解析
• 3.1 布谷鸟过滤器的优势
• 3.2 布谷鸟过滤器原理介绍
• 3.3 Redis中的布谷鸟过滤器实现
• 3.4 示例代码（Jedis实现）
• 3.5 RedisBloom中布谷鸟过滤器源码解读
• 四、总结与对比

缓存和数据处理的效率一直是大伙关注的重点。今天咱就来聊聊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;
}

四、总结与对比

• 布隆过滤器：适合那些不需要删除元素的场景，像缓存穿透、URL去重这些。它空间效率高，就是误判问题没法避免，而且不支持删除操作。
• 布谷鸟过滤器：在需要动态添加和删除元素的场景里就很合适，比如黑名单管理。它支持删除，误判率也更低，就是实现起来比布隆过滤器稍微复杂点。

在Redis里，这两种过滤器都是通过RedisBloom模块来实现的，源码都是开放的，方便大伙扩展。具体选哪种过滤器，还得看实际的业务需求。要是删除操作不是必须的，布隆过滤器就挺简单高效；要是集合里的数据需要动态调整，那布谷鸟过滤器无疑是更好的选择。