redis8.0新特性之布谷鸟过滤器(Cuckoo Filter)的使用

目录

• 一、写在前面
• 二、使用
• 1、CF.RESERVE 创建布谷鸟过滤器
• 2、CF.ADD 添加元素
• 3、CF.ADDNX 不存在才添加
• 4、CF.COUNT 判断元素添加次数
• 5、CF.DEL 删除一次元素
• 6、CF.EXISTS 判断元素是否存在
• 7、CF.MEXISTS 批量判断元素是否存在AYasno
• 8、CF.INFO 查看布谷鸟过滤器信息
• 9、CF.INSERT 创建并添加元素
• 10、CF.INSERTNX 不存在则添加
• 11、CF.SCANDUMP 保存过滤器
• 12、CF.LOADCHUNK 恢复保存的过滤器
• 三、默认值
• 1、cf-bucket-size
• 2、cf-initial-size
• 3、cf-expansion-factor
• 4、cf-max-expansions
• 5、cf-max-iterations
• 四、其他
• 1、关于布谷鸟过滤器删除操作引发的思考

一、写在前面

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

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

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

二、使用

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

# 语法

# capacity
#过滤器的预估容量。
#容量向上取整到下一个 2^n 数。
#过滤器很可能无法完全填充到其容量的 100%。如果您想避免扩展，请确保预留额外的容量。

#androidBUCKETSIZE 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 exists

redis> 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.IpythonNSERT 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 cf
 1) Size
 2) (integer) 1080
 3) Number of buckets
 4) (integer) 512
 5) Number of filter
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 0
 9) 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 [http://www.devze.comitem ...]

# 创建过滤器并添加
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:
        break
    else:
        chunks.append([iter, data])

# Load it back
for chunk in chunks:
    iter, data = chunk
    CF.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. 删除的前提条件

   布谷鸟过滤器的删除操作需要确保元素确实存在，否则可能因指纹冲突导致误删。与布隆过滤器不同，布谷鸟过滤器支持删除，但依赖于准确的指纹匹配。

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

到此这篇关于redis8.0新特性之布谷鸟过滤器(Cuckoo Filter)的使用的文章就介绍到这了,更多相关redis8 布谷鸟过滤器内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！