一、写在前面

官方中文文档：https://redis.ac.cn/docs/latest/develop/data-types/probabilistic/cuckoo-filter/

布谷鸟过滤器是一种概率数据结构，用于检查元素是否存在于集合中

布谷鸟过滤器，就像布隆过滤器一样，是 Redis 开源版中的一种概率数据结构，它可以以非常快速且节省空间的方式检查元素是否存在于集合中，同时还支持删除操作，并在某些场景下表现优于布隆过滤器。

对比维度	布隆过滤器	布谷鸟过滤器
数据更新特性	仅支持插入和查询，删除需特殊变体（如计数布隆）	原生支持高效插入、查询和删除
空间效率	中等，误判率相同时空间占用比布谷鸟高约40%	高，相同误判率下空间利用率更高
适合数据类型	静态或低频更新数据	动态频繁更新数据
并发性能	哈希函数独立，适合硬件并行	需原子操作支持，但并发读写效率更高
典型误判影响	误判可能导致“漏查”（正常数据被误判不存在）	误判可能导致“错查”（不存在数据被误判存在）
硬件适配性	适合FPGA/ASIC加速（位运算简单）	适合CPU缓存优化（哈希表结构更紧凑）

二、使用

1、CF.RESERVE 创建布谷鸟过滤器

# 语法# capacity
#过滤器的预估容量。
#容量向上取整到下一个 2^n 数。
#过滤器很可能无法完全填充到其容量的 100%。如果您想避免扩展，请确保预留额外的容量。#BUCKETSIZE bucketsize
#每个桶中的项目数。
#较高的桶大小值可以提高填充率，但也会导致更高的错误率和稍微慢的性能。
#bucketsize 是一个介于 1 到 255 之间的整数。默认值为 2。# MAXITERATIONS maxiterations
#在声明过滤器已满并创建附加过滤器之前，在桶之间交换项目的尝试次数。
#较低的值有利于性能，较高的值有利于过滤器填充率。
#maxiterations 是一个介于 1 到 65535 之间的整数。默认值为 20。# EXPANSION expansion
#创建新过滤器时，其大小是当前过滤器大小乘以 expansion。
#expansion 是一个介于 0 到 32768 之间的整数。默认值为 1。
#扩展值向上取整到下一个 2^n 数。CF.RESERVE key capacity [BUCKETSIZE bucketsize]  [MAXITERATIONS maxiterations] [EXPANSION expansion]

创建一个空的 Cuckoo 过滤器，其中包含一个用于初始指定容量的子过滤器。

根据 Cuckoo 过滤器的行为，过滤器在达到 capacity 之前很可能声明自己已满；因此，填充率很可能永远无法达到 100%。通过使用更大的 bucketsize 可以提高填充率，但会以更高的错误率为代价。当过滤器自身声明 full 时，它将通过生成额外的子过滤器来进行自动扩展，但这会降低性能并增加错误率。新的子过滤器的大小等于前一个子过滤器的大小乘以 expansion。与桶大小一样，额外的子过滤器会线性地增加错误率。

使用桶大小为 1 时，最小的误报率约为 2/255 ≈ 0.78%。较大的桶会线性地增加错误率（例如，桶大小为 3 会导致 2.35% 的错误率），但可以提高过滤器的填充率。

maxiterations 指定了尝试为传入指纹找到插槽的次数。一旦过滤器满了，较高的 maxIterations 值将减慢插入速度。

在可能的情况下，会自动使用先前子过滤器中未使用的容量。过滤器最多可以增长 32 倍。

redis> CF.RESERVE cf 1000
OK
# 不允许重复创建
redis> CF.RESERVE cf 1000
(error) ERR item existsredis> CF.RESERVE cf_params 1000 BUCKETSIZE 8 MAXITERATIONS 20 EXPANSION 2
OK

2、CF.ADD 添加元素

Cuckoo 过滤器可以多次包含相同的元素，并将每次添加视为独立操作。使用 CF.ADDNX 仅在元素不存在时添加它。

# 语法
CF.ADD key item# 示例 可以重复添加
redis> CF.ADD cf item1
(integer) 1
redis> CF.ADD cf item1
(integer) 1

3、CF.ADDNX 不存在才添加

# 语法 如果元素不存在，则将项目添加到 Cuckoo 过滤器中。
CF.ADDNX key item

此命令类似于 CF.EXISTS 和 CF.ADD 命令的组合。如果元素已存在，则不会将元素添加到过滤器中。
注意
此命令比 CF.ADD 慢，因为它首先检查元素是否存在。
由于 CF.EXISTS 可能会产生误报，CF.ADDNX 可能不会添加某个元素（因为它被认为已经存在），这可能是错误的。

redis> CF.ADDNX cf item
(integer) 1
# 不能重复添加
redis> CF.ADDNX cf item
(integer) 0

4、CF.COUNT 判断元素添加次数

# 语法 返回给定项被添加到布谷鸟过滤器中的次数的估计值。
CF.COUNT key item

返回值为整数，其中正值是 item 被添加到过滤器中的次数的估计值。可能存在高估，但不会低估。0 表示 key 不存在或 item 未被添加到过滤器中。

redis> CF.INSERT cf ITEMS item1 item2 item2
1) (integer) 1
2) (integer) 1
3) (integer) 1
redis> CF.COUNT cf item1
(integer) 1
redis> CF.COUNT cf item2
(integer) 2

5、CF.DEL 删除一次元素

# 语法
CF.DEL key item

从过滤器中删除一个项目一次。

如果该项目只存在一次，它将从过滤器中移除。如果该项目被添加了多次，它仍然会存在。

注意！删除一个不在过滤器中的项目可能会误删其他项目，导致漏报。

redis> CF.INSERT cf ITEMS item1 item2 item2
1) (integer) 1
2) (integer) 1
3) (integer) 1
redis> CF.DEL cf item1
(integer) 1
redis> CF.DEL cf item1
(integer) 0
redis> CF.DEL cf item2
(integer) 1
redis> CF.DEL cf item2
(integer) 1
redis> CF.DEL cf item2
(integer) 0

6、CF.EXISTS 判断元素是否存在

# 语法，返回值为整数，其中 1 表示 item !很可能!已经添加到过滤器中，而 0 表示 key 不存在或 item 未添加到过滤器中。
CF.EXISTS key item# 示例
redis> CF.ADD cf item1
(integer) 1
redis> CF.EXISTS cf item1
(integer) 1
redis> CF.EXISTS cf item2
(integer) 0

7、CF.MEXISTS 批量判断元素是否存在

# 语法
CF.MEXISTS key item [item ...]# 示例
redis> CF.INSERT cf ITEMS item1 item2
1) (integer) 1
2) (integer) 1
redis> CF.MEXISTS cf item1 item2 item3
1) (integer) 1
2) (integer) 1
3) (integer) 0

8、CF.INFO 查看布谷鸟过滤器信息

# 语法
CF.INFO key# 示例
redis> CF.INFO cf1) Size2) (integer) 10803) Number of buckets4) (integer) 5125) Number of filter6) (integer) 17) Number of items inserted8) (integer) 09) Number of items deleted
10) (integer) 0
11) Bucket size
12) (integer) 2
13) Expansion rate
14) (integer) 1
15) Max iteration
16) (integer) 20

9、CF.INSERT 创建并添加元素

向布谷鸟过滤器（cuckoo filter）中添加一个或多个元素，如果过滤器尚不存在，可以指定自定义容量进行创建。

# 语法# 如果 key 不存在，则会创建一个新的布谷鸟过滤器。#CAPACITY capacity
#如果过滤器尚不存在，则指定新过滤器的期望容量。
#如果过滤器已存在，则忽略此参数。
#如果过滤器尚不存在且未指定此参数，则会以模块级别的默认容量（即 1024）创建过滤器。# NOCREATE
#如果指定此选项，则在过滤器不存在时阻止自动创建（将返回错误）。
#此选项与 CAPACITY 互斥。CF.INSERT key [CAPACITY capacity] [NOCREATE] ITEMS item [item ...]

# 创建并添加元素
redis> CF.INSERT cf CAPACITY 1000 ITEMS item1 item2 
1) (integer) 1
2) (integer) 1# NOCREATE 不创建
redis> CF.INSERT cf1 CAPACITY 1000 NOCREATE ITEMS item1 item2 
(error) ERR not found# 指定容量
redis> CF.RESERVE cf2 2 BUCKETSIZE 1 EXPANSION 0
OK
redis> CF.INSERT cf2 ITEMS 1 1 1 1
1) (integer) 1
2) (integer) 1
3) (integer) -1
4) (integer) -1

10、CF.INSERTNX 不存在则添加

如果元素之前不存在，则向布谷鸟过滤器添加一个或多个项目；如果过滤器尚不存在，则可以指定自定义容量来创建过滤器。

此命令类似于 CF.ADDNX，但可以添加多个项目并指定容量。

# 语法#CAPACITY capacity
#指定新过滤器的期望容量，如果此过滤器尚不存在。
#如果过滤器已存在，则此参数将被忽略。
#如果过滤器尚不存在且未指定此参数，则使用模块级别的默认容量 1024 创建过滤器。#NOCREATE
#如果指定此项，则在过滤器不存在时阻止自动创建过滤器（此时会返回错误）。
#此选项与 CAPACITY 互斥。CF.INSERTNX key [CAPACITY capacity] [NOCREATE] ITEMS item [item ...]

# 创建过滤器并添加
redis> CF.INSERTNX cf CAPACITY 1000 ITEMS item1 item2 
1) (integer) 1
2) (integer) 1
# 不允许重复添加元素
redis> CF.INSERTNX cf CAPACITY 1000 ITEMS item1 item2 item3
1) (integer) 0
2) (integer) 0
3) (integer) 1
# NOCREATE 不会创建过滤器
redis> CF.INSERTNX cf_new CAPACITY 1000 NOCREATE ITEMS item1 item2 
(error) ERR not found

11、CF.SCANDUMP 保存过滤器

开始对布谷鸟过滤器进行增量保存。

此命令对于无法容纳于DUMP和RESTORE模式的大型布谷鸟过滤器非常有用。

首次调用此命令时，iter的值应为 0。

此命令返回连续的(iter, data)对，直到(0, NULL)表示完成。

# 语法
CF.SCANDUMP key iterator

redis> CF.RESERVE cf 8
OK
redis> CF.ADD cf item1
(integer) 1
redis> CF.SCANDUMP cf 0
1) (integer) 1
2) "\x01\x00\x00\x00\x00\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x02\x00\x14\x00\x01\x008\x9a\xe0\xd8\xc3\x7f\x00\x00"
redis> CF.SCANDUMP cf 1
1) (integer) 9
2) "\x00\x00\x00\x00\a\x00\x00\x00"
redis> CF.SCANDUMP cf 9
1) (integer) 0
2) (nil)
redis> DEL bf
(integer) 1
redis> CF.LOADCHUNK cf 1 "\x01\x00\x00\x00\x00\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x02\x00\x14\x00\x01\x008\x9a\xe0\xd8\xc3\x7f\x00\x00"
OK
redis> CF.LOADCHUNK cf 9 "\x00\x00\x00\x00\a\x00\x00\x00"
OK
redis> CF.EXISTS cf item1
(integer) 1

# python代码
chunks = []
iter = 0
while True:iter, data = CF.SCANDUMP(key, iter)if iter == 0:breakelse:chunks.append([iter, data])# Load it back
for chunk in chunks:iter, data = chunkCF.LOADCHUNK(key, iter, data)

12、CF.LOADCHUNK 恢复保存的过滤器

# 语法
CF.LOADCHUNK key iterator data

三、默认值

1、cf-bucket-size

在 v8.0.0 中添加。

每个布谷鸟过滤器桶中的条目数。

类型：整数

有效范围：[1 … 255]

默认值：2

2、cf-initial-size

在 v8.0.0 中添加。

布谷鸟过滤器的初始容量。

类型：整数

有效范围：[2*cf-bucket-size .. 1048576]

默认值：1024

3、cf-expansion-factor

在 v8.0.0 中添加。

布谷鸟过滤器的扩展因子。

类型：整数

有效范围：[0 … 32768]

默认值：1

4、cf-max-expansions

布谷鸟过滤器的最大扩展次数。

类型：整数

有效范围：[1 … 65535]

默认值：32

5、cf-max-iterations

在 v8.0.0 中添加

布谷鸟过滤器的最大迭代次数。

类型：整数

有效范围：[1 … 65535]

默认值：20

四、其他

1、关于布谷鸟过滤器删除操作引发的思考

删除不存在的元素是否会导致其他元素被删除，取决于指纹冲突情况。布谷鸟过滤器的删除逻辑基于元素的指纹（fingerprint），而非完整元素值，因此存在以下风险：

1. 指纹冲突的影响
   若元素A和元素B的指纹相同（哈希冲突），当删除不存在的元素A时，系统会根据哈希函数找到对应位置，若该位置存储的是元素B的指纹，则会误删元素B。
   • 示例：元素A（值为"apple"）和元素B（值为"banana"）的指纹均为0x123。若用户尝试删除A（实际不存在），过滤器会在哈希位置查找指纹0x123，若B的指纹存储在此处，则B会被错误删除。
2. 删除的前提条件
   布谷鸟过滤器的删除操作需要确保元素确实存在，否则可能因指纹冲突导致误删。与布隆过滤器不同，布谷鸟过滤器支持删除，但依赖于准确的指纹匹配。

所以，布谷鸟过滤器虽然支持操作，但是仍然有一定的错误率，反而不支持删除操作的布隆过滤器还算比较精准了（删除时需要额外维护一个删除列表，如果存在的话需要额外判断删除列表中有没有）。