一、寫在前面

官方中文文檔：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. 刪除的前提條件
   布谷鳥過濾器的刪除操作需要確保元素確實存在，否則可能因指紋沖突導致誤刪。與布隆過濾器不同，布谷鳥過濾器支持刪除，但依賴于準確的指紋匹配。

所以，布谷鳥過濾器雖然支持操作，但是仍然有一定的錯誤率，反而不支持刪除操作的布隆過濾器還算比較精準了（刪除時需要額外維護一個刪除列表，如果存在的話需要額外判斷刪除列表中有沒有）。