基本概念

布谷鳥過濾器 是一種節(jié)省內(nèi)存空間的概率數(shù)據(jù)結(jié)構(gòu)，基于 布谷鳥哈希算法 實現(xiàn)的過濾器，和 布隆過濾器 一樣，用于檢測指定元素是否存在于某個集合中，返回結(jié)果語義是 “元素一定不存在” 或 “有較大可能存在”。

和布隆過濾器比較

優(yōu)點

• 布谷鳥過濾器支持刪除元素，布隆過濾器不支持

• 高負載因子場景下，布谷鳥過濾器查詢效率更高

• 對于存儲數(shù)據(jù)量較大且期望誤判率較低 (小于 3%) 的場景下，布谷鳥過濾器存儲空間開銷更低

• 布谷鳥過濾器比布隆過濾器更容易實現(xiàn)

缺點

• 布谷鳥過濾器采用一種備用候選桶的方案，候選桶與首選桶可以通過 位置 + 值指紋的哈希 通過 異或計算 得出，這種對應(yīng)關(guān)系要求桶的大小必須是 2 的指數(shù)倍數(shù) (如 4, 8, 16, 32...)

• 布隆過濾器插入時計算好哈希直接寫入位即可，而布谷鳥過濾器在計算后可能會出現(xiàn)對應(yīng)位置上已經(jīng)存儲了指紋，這時就需要將已存儲的值踢出到候選桶，碰撞概率和插入耗時隨著表元素增多而增大，因此其插入性能低于布隆過濾器

• 布隆過濾器插入重復(fù)元素時沒有影響 (可以重復(fù)插入)，而布谷鳥過濾器對已存在的值會執(zhí)行 踢出 操作，因此重復(fù)元素的插入存在上限

• 布谷鳥過濾器的刪除并不完美，刪除操作在相同哈希值僅被插入一次時是完美的，如果元素沒有插入就進行刪除，可能會出現(xiàn)誤刪除 (刪除了相同哈希值的其他元素)， 如果元素插入了多次，但是每次刪除操作只刪除一個值，那么就需要知道元素插入了多少次才能徹底刪除，或者循環(huán)刪除直到失敗為止

PS: 如果只需要保證 一定不存在 語義，那么刪除時不論是否存在重復(fù)元素，直接刪除即可。

布谷鳥哈希算法描述

• 使用兩個哈希函數(shù) H1, H2 和兩個哈希表 T1, T2

• 插入元素 x

• 計算 x 的兩個哈希值 idx1 = H1(x), idx2 = H2(x)

• 如果 T1[idx1], T2[idx2] 有一個為空，插入 x, 兩者都為空，隨便選一個插入 x

• 如果 T1[idx1], T2[idx2] 都不為空，則隨便選擇其中一個 (設(shè)為 y) 將其踢出，插入 x

• 重復(fù)上述過程，插入元素 y

• 如果插入時，踢出次數(shù)過多，則說明哈希表滿了，進行擴容 (ReHash)，擴容完成后再次插入

• 查詢元素 x

• 讀取 T1[idx1], T2[idx2] 的值，和 x 比較

圖(a) 算法過程描述:

• 插入元素 x

• 將對應(yīng)桶的元素 y 踢出

• 將元素 y 插入到桶 z

• 將對應(yīng)桶的元素 z 踢出

• 將元素 z 插入到其他桶中

圖(b) 算法過程描述:

• 插入元素 x

• 插入失敗，因為桶已經(jīng)滿了

• 觸發(fā)擴容

偽代碼

按照算法描述，翻譯成偽代碼如下 (不考慮并發(fā)情況):

不同的版本

一個哈希桶

如圖所示，在未發(fā)生哈希碰撞之前，哈希桶的利用率只有 50%。

四路哈希桶

如圖所示是一個改進的哈希桶，每個桶有 4 個槽位，當哈希函數(shù)映射到同一個桶時，其它 3 個槽位如果有空位，那么就不會有元素被踢出，降低了碰撞概率。

布谷鳥過濾器

布谷鳥過濾器 對 布谷鳥哈希算法 進行了如下優(yōu)化改進:

• 使用多路哈希桶提高桶的利用率

• 只存儲 key 的指紋以減少內(nèi)存使用

通過異或計算尋找新桶

異或計算性質(zhì): 三個值中的任意兩個值進行異或計算，都可以得出第三個值。

示例代碼: 數(shù)字 1, 2, 3 執(zhí)行異或計算

布谷鳥過濾器 為了節(jié)省內(nèi)存，保存的是 x 的指紋信息，而非源值，那么當某個元素 x 被踢出時，需要找一個新桶 h2(x)，如何在不損失 x 的指紋信息的情況下，計算新桶 (候選桶) 并存儲呢？

布谷鳥過濾器 采用了巧妙的算法: 將桶 h1(x) 和 x 的指紋信息哈希值 hash( finger(x) ) 進行 異或計算 得出新的桶，這樣當新桶的值后面被踢出時， 可以通過 異或計算 反轉(zhuǎn)得到 x 的指紋信息。

對于元素 x, 計算兩個哈希值:

h1(x) = hash(x), h2(x) = h1(x) ⊕ hash(x’s fingerprint)

踢出桶上的元素時 (不管該桶是 h1(x) 還是 h2(x))，直接使用該桶的索引 index 和存儲在桶中的指紋信息計算備用桶 j

j = i ⊕ hash(fingerprint)

均衡分配

此外，指紋與桶進行 異或計算 之前會進行哈希，從而在表中均衡分配。如果備用位使用 i ⊕ hash(fingerprint) 計算時不將指紋進行哈希，且指紋的大小與表的大小相比很小，那么踢出的元素最終會落在鄰近的桶。

例如使用 8 位指紋，踢出的元素將被放置到離桶 i 最多 256 (2^8) 的桶，因為 異或計算 將改變桶索引的低 8 位，而高位不會改變。 哈希指紋可以確保這些元素可以重新定位到哈希表的不同的桶中，達到均衡分配，減少哈希碰撞并提高表的利用率。

空間優(yōu)化

較大的桶可以提高表的利用率，使用 2 個哈希函數(shù)，桶大小為 1 時，負載因子為 50% (上面提到的第一種布谷鳥哈希算法版本)， 但是當使用桶大小 2, 4, 8 時，負載因子分別會增加到 84%, 95%, 98%。

實驗數(shù)據(jù)表明，當誤判率 r > 0.002 時，每個桶使用 2 個槽位比 4 個槽位效果更好，當 r 為到 0.00001 < r ≤ 0.002 時，每個桶 4 個槽位可以最小化空間。

半排序桶

半排序的本質(zhì)是: 對每個指紋取 4 位，該 4 位可以表示為一個 16 進制，對于 b 個指紋的 4 位存儲就可以表示為 b 個 16 進制，進行 重復(fù)組合計算 后， 可以通過索引其位置來找到對應(yīng)的指紋 (也就是某個組合值)。

假設(shè)每個桶包含 b = 4 個指紋，每個指紋 f = 4 bit，一個未壓縮的桶占 4 x 4 = 16 bit。但是如果我們對每個 4 位指紋進行排序（空項被視為存儲值為 "0" 的指紋)， 那么共有 3876 個重復(fù)組合值。如果我們預(yù)先計算并將 3876 個值存儲在一個額外的表中 (表中每個位置表示一個指紋組合)，并將桶替換為預(yù)先計算好的表， 那么桶可以用 12 bit 表示整個表 (2 ^ 12 = 4096 > 3876)，而不是 16 bit 表示桶，這樣算下來，平均每個指紋可以節(jié)省 1 bit。

3876 是怎樣計算出來的？

其中 n 表示被選擇的東西個數(shù)， r 表示選擇個數(shù)，(順序可以重復(fù))。

根據(jù)數(shù)學公式，我們可以編寫如下代碼:

在上面的代碼中，計算了在 16 bit 中 4 bit 指紋的重復(fù)組合數(shù)量。

開源庫

有了前文的理論基礎(chǔ)后，接下來一起探索下具體的代碼實現(xiàn)。筆者選擇開源的 linvon/cuckoo-filter 作為研究 布谷鳥過濾器 代碼實現(xiàn)，版本為 v0.4.0。

這個庫的優(yōu)點

這里直接引用庫作者的原文:

在翻閱了 Github 上 cuckoofilter 的 golang 實現(xiàn)后，發(fā)現(xiàn)已有的實現(xiàn)都存在一些缺點:

• 絕大部分的庫都是固定 b 和 f 的，即假陽性率也是固定的，適應(yīng)性不好

• 所有的庫 f 都是以字節(jié)為單位的，只能以 8 的倍數(shù)來調(diào)整，不方便調(diào)整假陽性率

• 所有的庫都沒有實現(xiàn)半排序桶，相比于布隆過濾器的優(yōu)勢大打折扣

因為作者的場景需要更優(yōu)的空間和自定的假陽性率，因此移植了原論文的 C++ 實現(xiàn)，并做了一些優(yōu)化，主要包括:

• 支持調(diào)節(jié)參數(shù)

• 支持半排序桶

• 壓縮空間到緊湊的位數(shù)組，按位存儲指紋

• 支持二進制序列化

示例

源碼解析

接口

linvon/cuckoo-filter 實現(xiàn)了 普通單表 和空間優(yōu)化的 基于半排序桶的壓縮表，將兩者的通用部分抽象為 table 接口，通過運行時的 工廠方法 可以在初始化時根據(jù)不同的參數(shù)生成不同的過濾器。

過濾器數(shù)據(jù)結(jié)構(gòu)

victimCache 結(jié)構(gòu)體表示過濾器執(zhí)行 Add 操作時被 踢出 的元素對象。

Filter 結(jié)構(gòu)體表示 過濾器 對象，非常簡潔，只有三個字段: 被踢出元素, 元素數(shù)量, 底層用于存儲的表實例。

初始化過濾器

添加元素

Add 方法添加一個元素到表中，返回是否添加成功。

查找元素

Contain 方法檢測給定元素是否存在于表中。

計算元素數(shù)量

Size 方法計算表內(nèi)當前存儲的元素數(shù)量，如果 被踢出元素 一直沒有找到可用的桶，元素數(shù)量 + 1。

計算負載因子

LoadFactor 方法計算當前表的 負載因子, 計算公式為:

表內(nèi)當前元素數(shù)量 / 表內(nèi)可存儲元素數(shù)量

重置過濾器

Reset 方法會重置過濾器，相當于重新初始化。

計算誤判率

FalsePositiveRate 方法計算 過濾器 的 誤判率，需要注意的是，該方法會調(diào)用 Reset 方法重置 過濾器。

哈希算法

從 go.mod 文件定義中可以看到，linvon/cuckoo-filter 使用的哈希算法是 MetroHash。

MetroHash 是一個哈希函數(shù)算法，可用于計算輸入數(shù)據(jù)的 64 位 和 128 位哈希值，支持增量式哈希計算，具有較高的性能和較低的碰撞率概率。

此外，在計算 候選桶 的索引時，也用到了 Murmur2 算法。

省略部分

普通單表 和 壓縮表 的底層表存儲實現(xiàn)，由于時間關(guān)系不再展開分析，感興趣的讀者可以自行閱讀源代碼。

調(diào)用關(guān)系圖

小結(jié)

本文概括了 布谷鳥過濾器 的算法描述，并對比了其和 布隆過濾器 的主要差異。在代碼實現(xiàn)方面，筆者選擇了開源的 linvon/cuckoo-filter[1], 著重分析了庫的接口設(shè)計和主要 API 方法實現(xiàn)。最后順帶提一下，如果讀者決定使用 linvon/cuckoo-filter 到項目中，需要注意的是: 庫內(nèi)部并沒有做 并發(fā)限制，使用 Add, Contain 等方法時可能會遇到常見的 并發(fā)競態(tài) 問題，這就要求調(diào)用方在使用時需要做好相應(yīng)的并發(fā)處理。

Reference

• Cuckoo Filter: Practically Better Than Bloom[2]

• Cuckoo filter[3]

• 布谷鳥哈希和布谷鳥過濾器[4]

• 布谷鳥過濾器實戰(zhàn)對比與調(diào)參指南[5]

• 布谷鳥過濾器：實際上優(yōu)于布隆過濾器[6]

• linvon/cuckoo-filter[7]

• Cuckoo Hashing Visualization[8]

• List of hash functions[9]

鏈接

[1]

linvon/cuckoo-filter: https://github.com/linvon/cuckoo-filter

[2]

Cuckoo Filter: Practically Better Than Bloom: http://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf

[3]

Cuckoo filter: https://en.wikipedia.org/wiki/Cuckoo_filter

[4]

布谷鳥哈希和布谷鳥過濾器: https://www.qtmuniao.com/2021/12/07/cuckoo-hash-and-cuckoo-filter/

[5]

布谷鳥過濾器實戰(zhàn)對比與調(diào)參指南: http://www.linvon.cn/posts/cuckoo_guide/

[6]

布谷鳥過濾器：實際上優(yōu)于布隆過濾器: http://www.linvon.cn/posts/cuckoo/

[7]

linvon/cuckoo-filter: https://github.com/linvon/cuckoo-filter

[8]

Cuckoo Hashing Visualization: http://www.lkozma.net/cuckoo_hashing_visualization/

[9]

List of hash functions: https://en.wikipedia.org/wiki/List_of_hash_functions