Redis 命令及数据类型 -- CF(Cuckoo Filter)

发表于 2025-12-22 更新于 2026-01-06 分类于技术， redis

阅读次数：本文字数： 2.9k 阅读时长 ≈ 10 分钟

摘要

本文介绍 Redis 扩展模型 RedisBloom 中的 Cuckoo Filter 数据类型
本文基于redis-7.4.7，springboot-3.5.8
Redis官网：https://redis.io/
Redis 命令文档：https://redis.io/docs/latest/commands/
RedisBloom 的安装参见 Redis 扩展模块 -- RedisBloom 的安装方法
示例代码：GitHub

Cuckoo Filter（布谷鸟过滤器）

Cuckoo Filter 是 Bloom Filter 的改进版，支持动态添加和删除元素，仍能提供比布隆过滤器更高的查询性能。
维基百科对 Cuckoo Filter 的描述
在高 QPS 查询场景下，Cuckoo Filter 通常优于 Bloom Filter。
优点：低误判率 + 高负载率，基于相同的集合和误报率，Cuckoo Filter通常占用空间更少。相对的，算法实现也就更复杂。
缺点：与Bloom Filter一样，有可能将一个不在集合中的元素错误的判断成在集合中
Bloom Filter 的误报率通过调整位数组的大小和哈希函数数量来控制，而 Cuckoo Filter 的误报率受指纹大小和桶大小控制。

布谷哈希算法

百度百科对布谷哈希算法的描述]
算法使用两个不同哈希函数计算对应 key 的位置。
- 1. 当两个哈希任意位置为空，则随机选择一个位置插入
- 1. 当两个哈希有位置为空时，则插入到空位置
- 1. 当两个哈希位置均不为空时，随机选择一个位置插入并踢出原key，原key会再次经过计算获得新的位置，转至1执行，反复直到成功或者达到最大迭代次数。

Cuckoo Filter 的实现原理

布谷过滤器是在布谷哈希算法的算法基础上扩充来的，但是它所提供的概念不是表，而是提供了多个数据桶(Bucket)
每一个数据桶都是个一维数组，每个数组的保存内容为条目(Entry)，每一个条目里面可以保存一个指纹数据(指纹数据就是原始数据经过哈希计算得到的一个n位的数据标记)，除了指纹数据之外，还会同时得出一个保存位置P1标记。
当两个数据计算得到的指纹数据相同时，就会发生冲突，冲突操作的解决思路是使用布谷哈希算法，简单说就是新的数据会将原有数据踢出，而被踢出的数据会被重新计算得到新的指纹数据和保存位置标记。
布谷过滤器里面需要进行各种数据的踢出操作，这个踢出的方式就是使用P1标志位和指纹数据进行异或计算得出来的P2标志位，按照同样的思路(前提:一直都有冲突操作)一直计算新的P2位，直到冲突解决或者达到最大迭代次数，就会失败。
指纹数据里面包含有唯一性，所以可以实现数据的删除，当然，不同的数据计算是有可能得到相同指纹的，那么一旦删除数据之后，有可能造成数据的"假删除"，所以布谷过滤器本身也是存在有误差的。
Cuckoo Filter 中的 BUSKETSIZE
- BUSKETSIZE，表示每个桶(Busket)中存放的元素个数，即桶大小。
- Cuckoo Filter的数组里存的不是位，而是桶(busket)，每个桶里可以存放多个数据。
- 同一个桶中存放的数据越多，空间利用率更高，相应的误判率也就越高，性能也更慢。
- Redis的CuckooFilter实现中，BUSKETSIZE应该是一个在1到255之间的整数，默认的 BUSKETSIZE 是 2。
- 桶(Busket)中并不实际保存数据本身，而是保存数据的指纹(fingerprint)。指纹越小，HASH冲突造成误判的几率就越小。这个参数的调整比较复杂，Redis的CuckooFilter中不支持调整这个参数。

CF 命令说明

对应Redis命令： CF.xxx

命令	功能说明	是否创建 Filter	关键参数含义	返回值	示例	使用要点 / 备注
CF.RESERVE	显式创建 Cuckoo Filter	是	`capacity`：容量(必填) `BUCKETSIZE`：每个桶里最多能放多少个 fingerprint（指纹），默认 2(大多数情况下的最优解) `MAXITERATIONS`：重排次数，越大成功率越高 `EXPANSION`：扩容倍数，默认 1（不扩容）	OK	`CF.RESERVE user:cf 100000`	✅ 生产推荐支持删除与计数
CF.ADD	添加一个元素，不去重	是（不存在则创建）	`item`：元素	OK	`CF.ADD user:cf user_1`	若满可能失败
CF.ADDNX	元素不存在时才添加，去重	是（不存在则创建）	`item`	`1` 新增 `0` 已存在	`CF.ADDNX user:cf user_1`	幂等写入首选
CF.INSERT	批量插入	是（不存在则创建）	`ITEMS`：元素列表	OK	`CF.INSERT user:cf ITEMS u1 u2`	默认配置
CF.INSERTNX	批量插入（不存在才加）	是	`ITEMS`	`0/1` 列表	`CF.INSERTNX user:cf ITEMS u1 u2`	幂等 + 批量
CF.EXISTS	判断单个元素是否存在	否	`item`	`1` 可能存在 `0` 不存在	`CF.EXISTS user:cf user_1`	仍有误判
CF.MEXISTS	批量判断是否存在	否	`item...`	`0/1` 列表	`CF.MEXISTS user:cf u1 u9`	高并发推荐
CF.COUNT	返回元素出现次数	否	`item`	整数	`CF.COUNT user:cf user_1`	⭐ Bloom 没有的能力
CF.DEL	删除一个元素	否	`item`	`1` 删除成功 `0` 不存在	`CF.DEL user:cf user_1`	⭐ Bloom 不支持
CF.INFO	查看 Filter 元信息	否	无	KV 列表	`CF.INFO user:cf`	运维分析
CF.SCANDUMP	分块导出 Filter	否	`iterator`	`iterator + data`	`CF.SCANDUMP user:cf 0`	迁移 / 备份
CF.LOADCHUNK	从 dump 恢复 Filter	是	`iterator + data`	OK	`CF.LOADCHUNK user:cf 1 "xxx"`	与 SCANDUMP 配合

Bloom vs Cuckoo

维度	Bloom Filter	Cuckoo Filter
查询复杂度	O(k)（k 个哈希函数）	O(1)（2–4 次 bucket 访问）
插入复杂度	O(k)	平均 O(1)，最坏可能触发重排
删除支持	❌ 原生不支持	✅ 原生支持
误判率（False Positive）	可配置，稳定	可配置，通常更低
漏判（False Negative）	❌ 理论上不会	❌ 理论上不会
空间利用率	高（但受 k 影响）	通常更高（特别是低误判率）
扩容成本	高（需重建）	中等（支持扩展策略）
实现复杂度	低	较高

RedisBloom Cuckoo Filter 不支持设置 误判率，通常容量越大，误判率越低。

CF 命令示例

# 创建 Cuckoo Filter
## 容量1000，这个是必填参数。后面几个都是可选参数。
## BUSKETSIZE越大，空间利用率更高，但是误判率也更高，性能更差，默认2
## MAXITARATIONS越小，性能越好。如果设置越大，空间利用率就越好。默认20
## EXPANSION 是指空间扩容的比例。默认1，不扩容
127.0.0.1:6379> CF.RESERVE user:cf 1000 BUCKETSIZE 2 MAXITERATIONS 500 EXPANSION 2
OK
# 添加元素
127.0.0.1:6379> CF.ADD user:cf user_1
(integer) 1
127.0.0.1:6379> CF.ADD user:cf user_2
(integer) 1
# 可以重复添加元素
127.0.0.1:6379> CF.ADD user:cf user_1
(integer) 1
# 返回元素出现次数
127.0.0.1:6379> CF.COUNT user:cf user_1
(integer) 2
# 判断元素是否存在
127.0.0.1:6379> CF.EXISTS user:cf user_1
(integer) 1
# 批量判断元素是否存在
127.0.0.1:6379> CF.MEXISTS user:cf user_1 user_2 user_100
1) (integer) 1
2) (integer) 1
3) (integer) 0
# 删除元素，一次只删除一个
127.0.0.1:6379> CF.DEL user:cf user_1
(integer) 1
# 因为user_1有两个，所以才是还是能查询出 user_1
127.0.0.1:6379> CF.COUNT user:cf user_1
(integer) 1
# 再次删除
127.0.0.1:6379> CF.DEL user:cf user_1
(integer) 1
# 同名元素已全部删除，查询不到
127.0.0.1:6379> CF.COUNT user:cf user_1
(integer) 0

# 元素不存在时才添加，幂等
127.0.0.1:6379> CF.ADDNX user:cf user_2
(integer) 0
127.0.0.1:6379> CF.ADDNX user:cf user_3
(integer) 1

# 查看 Filter 元信息
127.0.0.1:6379> CF.INFO user:cf
 1) Size                      # 当前 Cuckoo Filter 实际占用的内存大小（字节）
 2) (integer) 1080
 3) Number of buckets         # 当前过滤器中 bucket（桶）的总数量，Size = Number of buckets * Bucket size(默认为2)
 4) (integer) 512
 5) Number of filters         # 内部 子 Cuckoo Filter 的数量
 6) (integer) 1
 7) Number of items inserted  # 成功插入的元素总数（近似）
 8) (integer) 2
 9) Number of items deleted   # 已删除元素的累计次数
10) (integer) 2
11) Bucket size               # 每个 bucket 可容纳的 fingerprint 数，默认为 2
12) (integer) 2
13) Expansion rate            # 过滤器自动扩容倍率，默认为1，0 或 1 表示不扩容（满则失败）
14) (integer) 2
15) Max iterations            # Cuckoo Kick-out 的最大重排次数，值越大，插入成功率越高，但写入延迟可能上升
16) (integer) 500

# 批量添加，key不存在则创建
127.0.0.1:6379> CF.INSERT order:cf CAPACITY 100 ITEMS order1 order2
1) (integer) 1
2) (integer) 1
# 幂等，元素不存在时才添加
127.0.0.1:6379> CF.INSERTNX order:cf CAPACITY 100 ITEMS order1 order2 order100
1) (integer) 0
2) (integer) 0
3) (integer) 1

# 查看类型
127.0.0.1:6379> type order:cf
MBbloomCF

SpringBoot 集成

SpringBoot 的 RedisTemplate 中没有提供对RedisBloom的封装，需要自己封装，我这里封装了一个简易的RedisCuckooFilterTool

package com.example.redisbloom;

/**
 * 基于 RedisBloom 插件的 CuckooFilter 实现
 * https://github.com/RedisBloom/RedisBloom/releases
 */

import lombok.extern.slf4j.Slf4j;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.data.redis.core.script.DefaultRedisScript;
import org.springframework.stereotype.Component;

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

@Component
@Slf4j
public class RedisCuckooFilterTool {

    private final StringRedisTemplate redisTemplate;

    public RedisCuckooFilterTool(StringRedisTemplate redisTemplate) {
        this.redisTemplate = redisTemplate;
    }

    /**
     * 初始化 Cuckoo Filter
     * <p>
     * 不能重复创建
     *
     * @param key      Filter 名称
     * @param capacity 预计容量
     */
    public boolean reserve(String key, long capacity) {
        String script = "return redis.call('CF.RESERVE', KEYS[1], " + capacity + ")";
        try{
            redisTemplate.execute(
                    new DefaultRedisScript<>(script, String.class),
                    Collections.singletonList(key)
            );
            return true;
        } catch (Exception e) {
            log.error("RedisCuckooFilterTool reserve error:",e);
            return false;
        }

    }

    /**
     * 初始化 Cuckoo Filter（高级参数）
     *
     * 不能重复创建
     *
     * @param key           Filter 名称
     * @param capacity      预计容量
     * @param bucketSize    每个桶里最多能放多少个 fingerprint（指纹），默认 2(大多数情况下的最优解)
     * @param maxIterations 重排次数，越大成功率越高
     * @param expansion     扩容倍数，默认 1（不扩容）
     */
    public boolean reserve(String key, long capacity, int bucketSize, int maxIterations, int expansion) {

        String script = String.format(
                "return redis.call('CF.RESERVE', KEYS[1], %d, " +
                        "'BUCKETSIZE', %d, 'MAXITERATIONS', %d, 'EXPANSION', %d)",
                capacity, bucketSize, maxIterations, expansion
        );

        try{
            redisTemplate.execute(
                    new DefaultRedisScript<>(script, String.class),
                    Collections.singletonList(key)
            );
            return true;
        } catch (Exception e) {
            log.error("RedisCuckooFilterTool reserve error:",e);
            return false;
        }
    }

    /**
     * 添加元素（不去重）
     */
    public boolean add(String key, String value) {
        String script = "return redis.call('CF.ADD', KEYS[1], ARGV[1])";
        final Boolean execute = redisTemplate.execute(
                new DefaultRedisScript<>(script, Boolean.class),
                Collections.singletonList(key),
                value
        );
        return Boolean.TRUE.equals(execute);
    }

    /**
     * 添加元素（仅当不存在时）
     *
     * @return true 表示成功插入，false 表示已存在
     */
    public boolean addNx(String key, String value) {
        String script = "return redis.call('CF.ADDNX', KEYS[1], ARGV[1])";
        final Boolean execute = redisTemplate.execute(
                new DefaultRedisScript<>(script, Boolean.class),
                Collections.singletonList(key),
                value
        );
        return Boolean.TRUE.equals(execute);
    }

    /**
     * 判断元素是否存在
     */
    public boolean exists(String key, String value) {
        String script = "return redis.call('CF.EXISTS', KEYS[1], ARGV[1])";
        final Boolean execute = redisTemplate.execute(
                new DefaultRedisScript<>(script, Boolean.class),
                Collections.singletonList(key),
                value
        );
        return Boolean.TRUE.equals(execute);
    }

    /**
     * 批量判断是否存在
     * @return 每个元素对应的结果，1 表示存在，0 表示不存在
     */
    public List<Long> mexists(String key, String... items) {
        String script = "return redis.call('CF.MEXISTS', KEYS[1], unpack(ARGV))";
        if (items == null || items.length == 0) {
            return Collections.emptyList();
        }

        return redisTemplate.execute(
                new DefaultRedisScript<>(script, List.class),
                Collections.singletonList(key),
                items
        );
    }

    /**
     * 返回元素出现次数（近似）
     */
    public Long count(String key, String value) {
        String script = "return redis.call('CF.COUNT', KEYS[1], ARGV[1])";
        return redisTemplate.execute(
                new DefaultRedisScript<>(script, Long.class),
                Collections.singletonList(key),
                value
        );
    }

    /**
     * 删除元素
     *
     * @return true 删除成功，false 表示不存在
     */
    public boolean delete(String key, String value) {
        String script = "return redis.call('CF.DEL', KEYS[1], ARGV[1])";

        final Long execute = redisTemplate.execute(
                new DefaultRedisScript<>(script, Long.class),
                Collections.singletonList(key),
                value
        );
        return Boolean.TRUE.equals(execute);
    }

    /**
     * 批量插入，不去重
     * @return 每个元素对应插入结果，1 插入成功，0 插入失败
     */
    public List<Long> insert(String key, String... items) {
        String script = "return redis.call('CF.INSERT', KEYS[1], 'ITEMS', unpack(ARGV))";
        if (items == null || items.length == 0) {
            return Collections.emptyList();
        }
        return redisTemplate.execute(
                new DefaultRedisScript<>(script, List.class),
                Collections.singletonList(key),
                items
        );
    }

    /**
     * 批量插入，去重
     * @return 每个元素对应插入结果，1 插入成功，0 插入失败
     */
    public List<Boolean> insertNx(String key, String... items) {
        String script = "return redis.call('CF.INSERTNX', KEYS[1], 'ITEMS', unpack(ARGV))";
        if (items == null || items.length == 0) {
            return Collections.emptyList();
        }
        return redisTemplate.execute(
                new DefaultRedisScript<>(script, List.class),
                Collections.singletonList(key),
                items
        );
    }

    /**
     * 获取 Cuckoo Filter 元信息
     */
    public Map<String, Long> info(String key) {
        String script = "return redis.call('CF.INFO', KEYS[1])";
        List<Object> result = redisTemplate.execute(
                new DefaultRedisScript<>(script, List.class),
                Collections.singletonList(key)
        );

        if (result == null || result.isEmpty()) {
            return Collections.emptyMap();
        }

        Map<String, Long> infoMap = new LinkedHashMap<>();
        for (int i = 0; i < result.size(); i += 2) {
            String field = toString(result.get(i));
            Long value = (Long) result.get(i + 1);
            infoMap.put(field, value);
        }

        return infoMap;
    }

    /**
     * 字节数组转字符串
     * info 返回的 List
     * [
     * byte[]("Size"),                  Long(1080),
     * byte[]("Number of buckets"),     Long(512),
     * byte[]("Number of filters"),     Long(1),
     * ...
     * ]
     */
    private String toString(Object obj) {
        if (obj instanceof byte[]) {
            return new String((byte[]) obj);
        }
        return String.valueOf(obj);
    }
}