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

