redis8.0新特性之布谷鳥過濾器(Cuckoo Filter)的使用
一、寫在前面
官方中文文檔：https://redis.ac.cn/docs/latest/develop/data-types/probabilistic/cuckoo-filter/
布谷鳥過濾器是一種概率數(shù)據(jù)結構，用于檢查元素是否存在于集合中
布谷鳥過濾器，就像布隆過濾器一樣，是 Redis 開源版中的一種概率數(shù)據(jù)結構，它可以以非?？焖偾夜?jié)省空間的方式檢查元素是否存在于集合中，同時還支持刪除操作，并在某些場景下表現(xiàn)優(yōu)于布隆過濾器。
| 對比維度 | 布隆過濾器 | 布谷鳥過濾器 |
|---|---|---|
| 數(shù)據(jù)更新特性 | 僅支持插入和查詢，刪除需特殊變體（如計數(shù)布?。?/td> | 原生支持高效插入、查詢和刪除 |
| 空間效率 | 中等，誤判率相同時空間占用比布谷鳥高約40% | 高，相同誤判率下空間利用率更高 |
| 適合數(shù)據(jù)類型 | 靜態(tài)或低頻更新數(shù)據(jù) | 動態(tài)頻繁更新數(shù)據(jù) |
| 并發(fā)性能 | 哈希函數(shù)獨立，適合硬件并行 | 需原子操作支持，但并發(fā)讀寫效率更高 |
| 典型誤判影響 | 誤判可能導致“漏查”（正常數(shù)據(jù)被誤判不存在） | 誤判可能導致“錯查”（不存在數(shù)據(jù)被誤判存在） |
| 硬件適配性 | 適合FPGA/ASIC加速（位運算簡單） | 適合CPU緩存優(yōu)化（哈希表結構更緊湊） |
二、使用
1、CF.RESERVE 創(chuàng)建布谷鳥過濾器
# 語法 # capacity #過濾器的預估容量。 #容量向上取整到下一個 2^n 數(shù)。 #過濾器很可能無法完全填充到其容量的 100%。如果您想避免擴展，請確保預留額外的容量。 #BUCKETSIZE bucketsize #每個桶中的項目數(shù)。 #較高的桶大小值可以提高填充率，但也會導致更高的錯誤率和稍微慢的性能。 #bucketsize 是一個介于 1 到 255 之間的整數(shù)。默認值為 2。 # MAXITERATIONS maxiterations #在聲明過濾器已滿并創(chuàng)建附加過濾器之前，在桶之間交換項目的嘗試次數(shù)。 #較低的值有利于性能，較高的值有利于過濾器填充率。 #maxiterations 是一個介于 1 到 65535 之間的整數(shù)。默認值為 20。 # EXPANSION expansion #創(chuàng)建新過濾器時，其大小是當前過濾器大小乘以 expansion。 #expansion 是一個介于 0 到 32768 之間的整數(shù)。默認值為 1。 #擴展值向上取整到下一個 2^n 數(shù)。 CF.RESERVE key capacity [BUCKETSIZE bucketsize] [MAXITERATIONS maxiterations] [EXPANSION expansion]
創(chuàng)建一個空的 Cuckoo 過濾器，其中包含一個用于初始指定容量的子過濾器。
根據(jù) Cuckoo 過濾器的行為，過濾器在達到 capacity 之前很可能聲明自己已滿；因此，填充率很可能永遠無法達到 100%。通過使用更大的 bucketsize 可以提高填充率，但會以更高的錯誤率為代價。當過濾器自身聲明 full 時，它將通過生成額外的子過濾器來進行自動擴展，但這會降低性能并增加錯誤率。新的子過濾器的大小等于前一個子過濾器的大小乘以 expansion。與桶大小一樣，額外的子過濾器會線性地增加錯誤率。
使用桶大小為 1 時，最小的誤報率約為 2/255 ≈ 0.78%。較大的桶會線性地增加錯誤率（例如，桶大小為 3 會導致 2.35% 的錯誤率），但可以提高過濾器的填充率。
maxiterations 指定了嘗試為傳入指紋找到插槽的次數(shù)。一旦過濾器滿了，較高的 maxIterations 值將減慢插入速度。
在可能的情況下，會自動使用先前子過濾器中未使用的容量。過濾器最多可以增長 32 倍。
redis> CF.RESERVE cf 1000 OK # 不允許重復創(chuàng)建 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 可能會產(chǎn)生誤報，CF.ADDNX 可能不會添加某個元素（因為它被認為已經(jīng)存在），這可能是錯誤的。
redis> CF.ADDNX cf item (integer) 1 # 不能重復添加 redis> CF.ADDNX cf item (integer) 0
4、CF.COUNT 判斷元素添加次數(shù)
# 語法 返回給定項被添加到布谷鳥過濾器中的次數(shù)的估計值。 CF.COUNT key item
返回值為整數(shù)，其中正值是 item 被添加到過濾器中的次數(shù)的估計值。可能存在高估，但不會低估。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 判斷元素是否存在
# 語法，返回值為整數(shù)，其中 1 表示 item !很可能!已經(jīng)添加到過濾器中，而 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 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 創(chuàng)建并添加元素
向布谷鳥過濾器（cuckoo filter）中添加一個或多個元素，如果過濾器尚不存在，可以指定自定義容量進行創(chuàng)建。
# 語法 # 如果 key 不存在，則會創(chuàng)建一個新的布谷鳥過濾器。 #CAPACITY capacity #如果過濾器尚不存在，則指定新過濾器的期望容量。 #如果過濾器已存在，則忽略此參數(shù)。 #如果過濾器尚不存在且未指定此參數(shù)，則會以模塊級別的默認容量（即 1024）創(chuàng)建過濾器。 # NOCREATE #如果指定此選項，則在過濾器不存在時阻止自動創(chuàng)建（將返回錯誤）。 #此選項與 CAPACITY 互斥。 CF.INSERT key [CAPACITY capacity] [NOCREATE] ITEMS item [item ...]
# 創(chuàng)建并添加元素 redis> CF.INSERT cf CAPACITY 1000 ITEMS item1 item2 1) (integer) 1 2) (integer) 1 # NOCREATE 不創(chuàng)建 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 不存在則添加
如果元素之前不存在，則向布谷鳥過濾器添加一個或多個項目；如果過濾器尚不存在，則可以指定自定義容量來創(chuàng)建過濾器。
此命令類似于 CF.ADDNX，但可以添加多個項目并指定容量。
# 語法 #CAPACITY capacity #指定新過濾器的期望容量，如果此過濾器尚不存在。 #如果過濾器已存在，則此參數(shù)將被忽略。 #如果過濾器尚不存在且未指定此參數(shù)，則使用模塊級別的默認容量 1024 創(chuàng)建過濾器。 #NOCREATE #如果指定此項，則在過濾器不存在時阻止自動創(chuàng)建過濾器（此時會返回錯誤）。 #此選項與 CAPACITY 互斥。 CF.INSERTNX key [CAPACITY capacity] [NOCREATE] ITEMS item [item ...]
# 創(chuàng)建過濾器并添加 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 不會創(chuàng)建過濾器 redis> CF.INSERTNX cf_new CAPACITY 1000 NOCREATE ITEMS item1 item2 (error) ERR not found
11、CF.SCANDUMP 保存過濾器
開始對布谷鳥過濾器進行增量保存。
此命令對于無法容納于DUMP和RESTORE模式的大型布谷鳥過濾器非常有用。
首次調用此命令時，iter的值應為 0。
此命令返回連續(xù)的(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 中添加。
每個布谷鳥過濾器桶中的條目數(shù)。
類型：整數(shù)
有效范圍：[1 … 255]
默認值：2
2、cf-initial-size
在 v8.0.0 中添加。
布谷鳥過濾器的初始容量。
類型：整數(shù)
有效范圍：[2*cf-bucket-size .. 1048576]
默認值：1024
3、cf-expansion-factor
在 v8.0.0 中添加。
布谷鳥過濾器的擴展因子。
類型：整數(shù)
有效范圍：[0 … 32768]
默認值：1
4、cf-max-expansions
布谷鳥過濾器的最大擴展次數(shù)。
類型：整數(shù)
有效范圍：[1 … 65535]
默認值：32
5、cf-max-iterations
在 v8.0.0 中添加
布谷鳥過濾器的最大迭代次數(shù)。
類型：整數(shù)
有效范圍：[1 … 65535]
默認值：20
四、其他
1、關于布谷鳥過濾器刪除操作引發(fā)的思考
刪除不存在的元素是否會導致其他元素被刪除，取決于指紋沖突情況。布谷鳥過濾器的刪除邏輯基于元素的指紋（fingerprint），而非完整元素值，因此存在以下風險：
- 指紋沖突的影響
若元素A和元素B的指紋相同（哈希沖突），當刪除不存在的元素A時，系統(tǒng)會根據(jù)哈希函數(shù)找到對應位置，若該位置存儲的是元素B的指紋，則會誤刪元素B。- 示例：元素A（值為"apple"）和元素B（值為"banana"）的指紋均為0x123。若用戶嘗試刪除A（實際不存在），過濾器會在哈希位置查找指紋0x123，若B的指紋存儲在此處，則B會被錯誤刪除。
- 刪除的前提條件
布谷鳥過濾器的刪除操作需要確保元素確實存在，否則可能因指紋沖突導致誤刪。與布隆過濾器不同，布谷鳥過濾器支持刪除，但依賴于準確的指紋匹配。
所以，布谷鳥過濾器雖然支持操作，但是仍然有一定的錯誤率，反而不支持刪除操作的布隆過濾器還算比較精準了（刪除時需要額外維護一個刪除列表，如果存在的話需要額外判斷刪除列表中有沒有）。
到此這篇關于redis8.0新特性之布谷鳥過濾器(Cuckoo Filter)的使用的文章就介紹到這了,更多相關redis8 布谷鳥過濾器內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
Redis實現(xiàn)主從復制方式(Master&Slave)
這篇文章主要介紹了Redis實現(xiàn)主從復制方式(Master&Slave)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
這篇文章主要介紹了Redis服務之高可用組件sentinel,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-08-08
Redis提供了一些機制來保護敏感數(shù)據(jù)和限制對Redis服務器的訪問,本文主要介紹了Redis權限和訪問控制的實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下2023-12-12
本文主要介紹了redis list類型命令的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-07-07
這篇文章主要介紹了Spring Boot 項目集成Redis的方式，本文通過實例代碼給大家介紹的非常詳細，需要的朋友參考下吧,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了redis緩存與數(shù)據(jù)庫一致性的問題及解決，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
這篇文章主要介紹了Redis的KEYS 命令千萬不能亂用,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-07-07
文章介紹了兩種方法來檢查Redis鎖的狀態(tài)：使用GET命令查看鎖的值和使用EXISTS命令檢查鎖的存在性,這兩種方法都是通過連接到Redis服務器并執(zhí)行相應的命令來實現(xiàn)的,GET命令用于獲取指定鍵的值,而EXISTS命令用于檢查指定鍵是否存在2025-01-01
這篇文章主要介紹了Redis未授權訪問漏洞復現(xiàn)與利用,介紹了redis未授權訪問漏洞的基本概念及漏洞的危害，本文給大家介紹的非常詳細，需要的朋友可以參考下2022-01-01
這篇文章主要介紹了使用Redis實現(xiàn)用戶積分排行榜的教程,包括一個用PHP腳本進行操作的例子,需要的朋友可以參考下2015-04-04