怎么實(shí)現(xiàn)一個(gè)更全面的Golang版本的布谷鳥過濾器-創(chuàng)新互聯(lián)

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

成都創(chuàng)新互聯(lián)公司是一家以網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)、品牌設(shè)計(jì)、軟件運(yùn)維、營銷推廣、小程序App開發(fā)等移動(dòng)開發(fā)為一體互聯(lián)網(wǎng)公司。已累計(jì)為三輪攪拌車等眾行業(yè)中小客戶提供優(yōu)質(zhì)的互聯(lián)網(wǎng)建站和軟件開發(fā)服務(wù)。

布谷鳥過濾器

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

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

什么是布谷鳥過濾器？

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

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

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

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

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

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

  • 二是因?yàn)樵诓樵儠r(shí)，布隆過濾器要采用多種哈希函數(shù)進(jìn)行多次哈希，而布谷鳥過濾器只需一次哈希，因此查詢效率很高

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

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

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

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

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

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

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

實(shí)戰(zhàn)指南

細(xì)節(jié)實(shí)現(xiàn)

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

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

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

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

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

  • 桶大?。╞）：每個(gè)桶存儲(chǔ)多少個(gè)指紋

  • 指紋大小（f）：每個(gè)指紋存儲(chǔ)鍵的哈希值的多少位

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

  • 過濾器無法 100% 填滿，存在較大負(fù)載因子 α，那么均攤到每個(gè)項(xiàng)上的存儲(chǔ)占用空間就是 f/α

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

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

  • 使用 k=2 個(gè)哈希函數(shù)時(shí)，當(dāng)桶大小 b=1（即直接映射哈希表）時(shí)，負(fù)載因子 α 為 50%，但使用桶大小 b=2、4 或 8 時(shí)則分別會(huì)增加到 84%、95% 和 98%

  • 為了保證假陽性率 r，需要保證 $2b/2^f\leq r$ ，那么指紋 f 大小約為 $f ≥ log_2(2b/r)=log_2(1/r) + log_2(2b)$ ，那每個(gè)項(xiàng)的均攤成本即為 $C ≤ [log_2(1/r) + log_2(2b)]/α$

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

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

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

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

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

一些進(jìn)階解釋

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

雖然我們指定了需要兩個(gè)哈希算法，但實(shí)際實(shí)現(xiàn)上我們使用一個(gè)哈希算法就足夠了，因?yàn)樵谡撐闹刑岬搅艘环N備選桶計(jì)算方法，第二個(gè)哈希值可以由第一個(gè)哈希值與該位置存儲(chǔ)的指紋異或計(jì)算得來。如果你在擔(dān)心我們還需要分別計(jì)算指紋的哈希和位置的哈希，我們可以只用一種算法制作 64 位的哈希，高 32 位用于計(jì)算位置，低 32 位用于計(jì)算指紋。

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

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

我們可以通過以下函數(shù)計(jì)算所有的情況種類數(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 時(shí)，總共有 3786 種排列，小于 4096，即用 12 位即可存儲(chǔ)所有的排列索引，而如果直接存儲(chǔ)所有指紋，則需要 4X4=16 位，這樣節(jié)省了 4 位，即對每一個(gè)指紋節(jié)省了一位。

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

此外編碼存儲(chǔ)四位指紋的選擇是因?yàn)槠鋭偤每梢杂靡粋€(gè)十六進(jìn)制表示，利于存儲(chǔ)

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

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

過濾器大小選擇

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

Golang 實(shí)現(xiàn)

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

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

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

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

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

因?yàn)樽约旱膱鼍靶枰鼉?yōu)的空間和自定的假陽性率，因此移植了原論文的 C++ 實(shí)現(xiàn)，并做了一些優(yōu)化，主要包括

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

  • 支持半排序桶

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

  • 支持二進(jìn)制序列化

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

文章題目：怎么實(shí)現(xiàn)一個(gè)更全面的Golang版本的布谷鳥過濾器-創(chuàng)新互聯(lián)
文章位置：http://muchs.cn/article14/egcge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、企業(yè)網(wǎng)站制作、關(guān)鍵詞優(yōu)化、域名注冊、云服務(wù)器、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

成都做網(wǎng)站