如何實現一個更全面的Golang版本的布穀鳥過濾器

#                            

下面由go語言教學專欄為大家介紹我實現了一個更全面的Golang 版本的布穀鳥過濾器，希望對需要的朋友有所幫助！

「判斷一個值是否在一個巨大的集合當中」（下文中統稱為集合隸屬測試），是一種常見的資料處理問題。在以往的經驗中，如果允許一定的假陽性率，那麼布隆過濾器是首選，而如今我們有了更好的選擇：布穀鳥過濾器。
最近的業務需要用到過濾器，搜尋了一下發現我們的場景下布穀鳥過濾器性價比更高，要好於布隆過濾器。
為了確定最終的技術選型，我去讀了一下原論文，後來確定要用布穀鳥過濾器時發現幾乎沒有golang 的全面實現，當前在GitHub 上的幾個高stars 實現都存在一些缺陷，並沒有最大化空間利用率，因此自己參照原論文以及論文的原C 實現，移植並優化了一版Golang 的庫，細節內容都在下文中。
程式碼地址在這裡，歡迎star 、使用、貢獻、debug： github.com/linvon/cuckoo-filter

布穀鳥過濾器

布穀鳥過濾器在網路上已經有很多的介紹文章了，這裡不再做過多的介紹，只提一下要點，用於引出下面的內容

如果想要知道更多的細節，可以參考原始論文，或查看我的中文翻譯版本

什麼是布穀鳥過濾器？

是一種基於布穀鳥哈系演算法實現的過濾器，本質上是儲存了存儲項哈希值的布穀鳥哈希表。

如果你了解布隆過濾器，你應該知道布隆過濾器原理是採用多種哈希方法，將存儲項的不同哈希映射到位數組上，查詢時通過對這些位進行檢查來判斷是否存在。

而布穀鳥過濾器是對存儲項做哈希，將其哈希值取一定位數存儲在數組中，查詢時通過判斷相等位數的哈希是否在數組中來判斷是否存在。

為什麼選擇布穀鳥濾鏡？

同樣都是儲存雜湊值，本質上都是儲存多位元哈希，為什麼布穀鳥過濾器比較優？

• 一是由於布穀鳥雜湊表更加緊湊，因此可以更加節省空間。

• 二是因為在查詢時，布隆過濾器要採用多種哈希函數進行多次哈希，而布穀鳥過濾器只需一次哈希，因此查詢效率很高

• 三是布穀鳥過濾器支援刪除，而布隆過濾器不支援刪除

##優點有了，缺點呢？相較於布隆過濾器

布穀鳥過濾器採用備用候選桶的方案，候選桶與首選桶可以透過位置和儲存值互相異或得出，這種對應關係要求桶的大小必須是2 的指數倍
• 布隆過濾器插入時計算好哈希直接寫入位即可，而布穀鳥過濾器在計算後可能會出現當前位置上已經存儲了指紋，這時候就需要將已儲存的項踢到候選桶，隨著桶子越來越滿，產生衝突的可能性越來越大，插入耗時越來越高，因此其插入性能相比布隆過濾器很差
• 插入重複元素：布隆過濾器在插入重複元素時並沒有影響，只是對已存在的位元再置一遍。而布穀鳥過濾器對已存在的值會做踢出操作，因此重複元素的插入存在上限
• 布穀鳥過濾器的刪除並不完美：有上述重複插入的限制，刪除時也會出現相關的問題：刪除僅在相同哈希值被插入一次時是完美的，如果元素沒有插入便進行刪除，可能會出現誤刪除，這和假陽性率的原因相同；如果元素插入了多次，那麼每次刪除只會刪除一個值，你需要知道元素插入了多少次才能刪除乾淨，或者循環運行刪除直到刪除失敗為止

優缺點都列出來了，我們再來總結一下。對於這種集合隸屬測試問題，大部分情景都是讀多寫少的，而重複插入並沒有什麼意義，布穀鳥過濾器的刪除雖然不完美但總好過沒有，同時還有更優的查詢和存儲效率，應該說在絕大多數情況下其都是性價比更高的選擇。

實戰指南

細節實作

#先說一下布穀鳥濾鏡中的概念，濾鏡是由許多桶組成的，每個桶儲存插入項經過雜湊計算後的值，該值只會儲存固定位數。

過濾器中有 n 個桶，桶的數量是根據要儲存的項目的數量計算得來的。透過雜湊演算法我們可以計算出一個項應該儲存在哪個桶中，此外每增加一個雜湊演算法，就可以對一個項產生一個候選桶，當重複插入時，會把目前儲存的項踢到候選桶中去。理論上哈希演算法越多，空間利用率越高，但實際測試使用 k=2 個哈希函數就可以達到 98% 的利用率了。

每一個桶會儲存多個指紋，這受制於桶的大小，不同的指紋可能會對應到同一個桶中。桶越大，空間利用率越高，但同時每次查詢掃描同一桶中指紋數越多，因此產生假陽性的機率越高，此時就需要提高儲存的指紋位數，用以降低衝突率，維持假陽性率。

在論文中提到了實作布穀鳥濾波器所需的幾個參數，主要是

• #雜湊函數個數（k）：哈希個數，取2就足夠
• 桶大小（b）：每個桶儲存多少個指紋
• 指紋大小（f）：每個指紋儲存鍵的雜湊值的多少位

詳細閱讀論文，在第五章中作者依靠試驗數據告訴了我們如何選擇最合適的構建參數，我們可以得到如下結論

• 過濾器無法100% 填滿，存在最大負載因子α，那麼均攤到每個項目上的儲存佔用空間就是f/α
• 當保持過濾器總大小不變時，桶越大負載因子越高，即空間利用率越高，但每個桶儲存的指紋越多，查詢時可能發生衝突的機率也越高，為了維持假陽性率不變，桶越大，就需要越大的指紋

##根據上述的理論依據，所得的相關實驗數據有：

使用k=2 個雜湊函數時，當桶大小b=1（即直接映射雜湊表）時，負載因子α 為50%，但使用桶大小b=2、4 或8 時則分別會增加到84%、95% 和98%
• 為了保證假陽性率r，需要保證$2b/2 ^f\leq r$ ，則指紋f 大小約為$f ≥ log_2(2b/r)=log_2(1/r) log_2(2b)$ ，那每個項的均攤成本即為$C ≤ [log_2( 1/r) log_2(2b)]/α$
• 實驗數據表明，當r>0.002 時。每桶有兩個條目比每桶使用四個條目產生的結果略好；當r 減小到0.00001
如果使用半排序桶，可以對每一個存儲項減少1bit 的存儲空間，但其僅作用於b=4 的過濾器

這樣一來我們便可以確定如何選擇參數來建立我們的布穀鳥過濾器了：

首先哈希函數我們使用兩個就足夠了，這可以達到足夠的空間利用率。根據我們需要的假陽性率，我們可以確定使用多大的桶大小，當然 b 的選擇並不絕對，即使 r>0.002，你也可以使用 b=4 來啟用半排序桶。之後我們可以根據 b 來計算為了達到目標假陽性率，我們需要的 f 的大小，這樣所有的濾波參數就確定了。 將上面的結論與布隆過濾器的每項$1.44log_2(1/r)$ 對比，可以發現啟用半排序時，當r<0.03 左右，布穀鳥過濾器空間更小，若不啟用半排序，則退化到r<0.003 左右。

一些進階解釋

#雜湊演算法的最佳化

雖然我們指定了需要兩個雜湊演算法，但實際實作上我們使用一個雜湊演算法就足夠了，因為在論文中提到了一種備選桶計算方法，第二個雜湊值可以由第一個雜湊值與該位置儲存的指紋異或計算得來。如果你在擔心我們還需要分別計算指紋的哈希和位置的哈希，我們可以只用一種演算法製作 64 位元的哈希，高 32 位元用於計算位置，低 32 位元用於計算指紋。

為什麼半排序桶只能用在 b=4 的情況？

半排序的本質是對每個指紋取其四位，該四位可以表示為一個十六進制，對於b 個指紋的四位存儲就可以表示為b 個16進制數，將其所有可能按順序排列後，可以透過索引其位置來找到對應的排列，從而取得實際的儲存值。

我們可以透過以下函數計算所有的情況種類數

func getNum(base, k, b, f int, cnt *int) {
    for i := base; i < 1<> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    n |= n >> 32
    n++
    return uint(n)}func getNumOfKindAndBit(b, f int) {
    cnt := 0
    getNum(0, 0, b, f, &cnt)
    fmt.Printf("Num of kinds: %v, Num of needed bits: %v\n", cnt, math.Log2(float64(getNextPow2(uint64(cnt)))))}在b=4 時，總共有3786 種排列，小於4096，也就是用12 位元即可儲存所有的排列索引，而如果直接存放所有指紋，則需要4X4=16 位，這樣節省了4 位，即對每一個指紋節省了一位。 

可以發現，在 b 為 2 時是否啟用半排序需要儲存的位數相同，沒有意義。如果 b 太大則需要儲存的索引也會急劇擴張，會在查詢效能上有很大的損耗，因此 b=4 是一個性價比最高的選擇。 
此外編碼儲存四位指紋的選擇是因為其剛好可以用一個十六進位表示，利於儲存
使用半排序時的參數選擇
 
#使用半排序時，應保證$ceil(b(f-1)/8)f/8)$，否則是否使用半排序佔用的空間是一樣大的

濾鏡大小選擇
濾鏡的桶總大小一定是2 的指數倍，因此在設定濾鏡大小時，盡量滿足$size/α ~=(<) 2^n$，size 即為想要一個過濾器儲存的資料量，必要時應選擇小一點的過濾器，使用多個過濾器達到目標效果

Golang 實作
這部分主要是Golang 函式庫相關
在翻閱了Github 上cuckoofilter 的golang 實作後，發現已有的實作都存在一些缺點：

絕大部分的函式庫都是固定b 和f 的，即假陽性率也是固定的，適應性不好
所有的庫f 都是以位元組為單位的，只能以8 的倍數來調整，不方便調整假陽性率
所有的庫都沒有實現半排序桶，相比於布隆過濾器的優勢大打折扣

因為自己的場景需要更優的空間和自定的假陽性率，因此移植了原論文的C 實現，並做了一些優化，主要包括

##支持調節參數


支援半排序桶


壓縮空間到緊湊的位元組，按位元儲存指紋


支援二進位序列化

#
以上是如何實現一個更全面的Golang版本的布穀鳥過濾器的詳細內容。更多資訊請關注PHP中文網其他相關文章！