怎么實現一個更全面的Golang版本的布谷鳥過濾器

這篇文章給大家分享的是有關怎么實現一個更全面的Golang版本的布谷鳥過濾器的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

布谷鳥過濾器

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

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

什么是布谷鳥過濾器？

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

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

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

為什么選擇布谷鳥過濾器？

同樣都是存儲哈希值，本質上都是存儲多位哈希，為什么布谷鳥過濾器更優？

• 一是由于布谷鳥哈希表更加緊湊，因此可以更加節省空間。

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

• 三是布谷鳥過濾器支持刪除，而布隆過濾器不支持刪除

優點有了，缺點呢？相比于布隆過濾器

• 布谷鳥過濾器采用一種備用候選桶的方案，候選桶與首選桶可以通過位置和存儲值互相異或得出，這種對應關系要求桶的大小必須是 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<r≤0.002 時，每個桶四個條目可以最小化空間

• 如果使用半排序桶，可以對每一個存儲項減少 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<<f; i++ {
        if k+1 < b {
            getNum(i, k+1, b, f, cnt)
        } else {
            *cnt++
        }
    }}func getNextPow2(n uint64) uint {
    n--
    n |= n >> 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)<ceil(bf/8)$，否則是否使用半排序占用的空間是一樣大的

過濾器大小選擇

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

Golang 實現

這部分主要是 Golang 庫相關

在翻閱了 Github 上 cuckoofilter 的 golang 實現后，發現已有的實現都存在一些缺點：

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

• 所有的庫 f 都是以字節為單位的，只能以 8 的倍數來調整，不方便調整假陽性率

• 所有的庫都沒有實現半排序桶，相比于布隆過濾器的優勢大打折扣

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

• 支持調節參數

• 支持半排序桶

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

• 支持二進制序列化

感謝各位的閱讀！關于“怎么實現一個更全面的Golang版本的布谷鳥過濾器”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！