怎么實現(xiàn)一個更全面的Golang版本的布谷鳥過濾器

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

布谷鳥過濾器

布谷鳥過濾器在網(wǎng)絡(luò)上已經(jīng)有很多的介紹文章了，這里不再做過多的介紹，只提一下要點，用于引出下面的內(nèi)容

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

什么是布谷鳥過濾器？

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

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

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

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

同樣都是存儲哈希值，本質(zhì)上都是存儲多位哈希，為什么布谷鳥過濾器更優(yōu)？

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

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

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

優(yōu)點有了，缺點呢？相比于布隆過濾器

• 布谷鳥過濾器采用一種備用候選桶的方案，候選桶與首選桶可以通過位置和存儲值互相異或得出，這種對應(yīng)關(guān)系要求桶的大小必須是 2 的指數(shù)倍

• 布隆過濾器插入時計算好哈希直接寫入位即可，而布谷鳥過濾器在計算后可能會出現(xiàn)當前位置上已經(jīng)存儲了指紋，這時候就需要將已存儲的項踢到候選桶，隨著桶越來越滿，產(chǎn)生沖突的可能性越來越大，插入耗時越來越高，因此其插入性能相比布隆過濾器很差

• 插入重復元素：布隆過濾器在插入重復元素時并沒有影響，只是對已存在的位再置一遍。而布谷鳥過濾器對已存在的值會做踢出操作，因此重復元素的插入存在上限

• 布谷鳥過濾器的刪除并不完美：有上述重復插入的限制，刪除時也會出現(xiàn)相關(guān)的問題：刪除僅在相同哈希值被插入一次時是完美的，如果元素沒有插入便進行刪除，可能會出現(xiàn)誤刪除，這和假陽性率的原因相同；如果元素插入了多次，那么每次刪除僅會刪除一個值，你需要知道元素插入了多少次才能刪除干凈，或者循環(huán)運行刪除直到刪除失敗為止

優(yōu)缺點都列出來了，我們再來總結(jié)一下。對于這種集合隸屬測試問題，大部分情景都是讀多寫少的，而重復插入并沒有什么意義，布谷鳥過濾器的刪除雖然不完美但總好過沒有，同時還有更優(yōu)的查詢和存儲效率，應(yīng)該說在絕大多數(shù)情況下其都是一個性價比更高的選擇。

實戰(zhàn)指南

細節(jié)實現(xiàn)

先說一下布谷鳥過濾器中的概念，過濾器是由很多桶組成的，每個桶存儲插入項經(jīng)過哈希計算后的值，該值只會存儲固定位數(shù)。

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

每一個桶會存儲多個指紋，這受制于桶的大小，不同的指紋可能映射到同一個桶中。桶越大，空間利用率越高，但同時每次查詢掃描同一桶中指紋數(shù)越多，因此產(chǎn)生假陽性的概率越高，此時就需要提高存儲的指紋位數(shù)，用以降低沖突率，維持假陽性率。

在論文中提到了實現(xiàn)布谷鳥過濾器所需的幾個參數(shù)，主要是

• 哈希函數(shù)個數(shù)（k）：哈希個數(shù)，取 2 就足夠

• 桶大?。╞）：每個桶存儲多少個指紋

• 指紋大小（f）：每個指紋存儲鍵的哈希值的多少位

詳細閱讀論文，在第五章中作者依靠試驗數(shù)據(jù)告訴了我們?nèi)绾芜x擇最合適的構(gòu)建參數(shù)，我們可以得到如下結(jié)論

• 過濾器無法 100% 填滿，存在最大負載因子 α，那么均攤到每個項上的存儲占用空間就是 f/α

• 當保持過濾器總大小不變時，桶越大負載因子越高，即空間利用率越高，但每個桶存儲的指紋越多，查詢時可能發(fā)生沖突的概率也越高，為了維持假陽性率不變，桶越大，就需要越大的指紋

根據(jù)上述的理論依據(jù)，得出的相關(guān)實驗數(shù)據(jù)有：

• 使用 k=2 個哈希函數(shù)時，當桶大小 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)]/α$

• 實驗數(shù)據(jù)表明，當 r>0.002 時。每桶有兩個條目比每桶使用四個條目產(chǎn)生的結(jié)果略好；當 r 減小到 0.00001<r≤0.002 時，每個桶四個條目可以最小化空間

• 如果使用半排序桶，可以對每一個存儲項減少 1bit 的存儲空間，但其僅作用于 b=4 的過濾器

這樣一來我們便可以確定如何選擇參數(shù)來構(gòu)建我們的布谷鳥過濾器了：

首先哈希函數(shù)我們使用兩個就足夠了，這可以達到足夠的空間利用率。根據(jù)我們需要的假陽性率，我們可以確定使用多大的桶大小，當然 b 的選擇并不絕對，即使 r>0.002，你也可以使用 b=4 來啟用半排序桶。之后我們可以根據(jù) b 來計算為了達到目標假陽性率，我們需要的 f 的大小，這樣所有的過濾器參數(shù)就確定了。

將上面的結(jié)論與布隆過濾器的每項 $1.44log_2(1/r)$ 對比，可以發(fā)現(xiàn)啟用半排序時，當 r<0.03 左右，布谷鳥過濾器空間更小，若不啟用半排序，則退化到 r<0.003 左右。

一些進階解釋

哈希算法的優(yōu)化

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

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

半排序的本質(zhì)是對每個指紋取其四位，該四位可以表示為一個十六進制，對于 b 個指紋的四位存儲就可以表示為 b 個 16 進制數(shù)，將其所有可能按順序排列后，可以通過索引其位置來找到對應(yīng)的排列，從而獲取實際的存儲值。

我們可以通過以下函數(shù)計算所有的情況種類數(shù)

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 位，這樣節(jié)省了 4 位，即對每一個指紋節(jié)省了一位。

可以發(fā)現(xiàn)，在 b 為 2 時是否啟用半排序需要存儲的位數(shù)相同，沒有意義。如果 b 太大則需要存儲的索引也會急劇擴張，會在查詢性能上有很大的損耗，因此 b=4 是一個性價比最高的選擇。

此外編碼存儲四位指紋的選擇是因為其剛好可以用一個十六進制表示，利于存儲

使用半排序時的參數(shù)選擇

使用半排序時，應(yīng)保證 $ceil(b(f-1)/8)<ceil(bf/8)$，否則是否使用半排序占用的空間是一樣大的

過濾器大小選擇

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

Golang 實現(xiàn)

這部分主要是 Golang 庫相關(guān)

在翻閱了 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ù)組，按位存儲指紋

• 支持二進制序列化

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