Redis 過濾請(qǐng)求絕技 — 布隆過濾器與布谷鳥過濾器

點(diǎn)擊上方藍(lán)色字體，選擇“設(shè)為星標(biāo)”

大家都知道,在計(jì)算機(jī)中,IO一直是一個(gè)瓶頸,很多框架以及技術(shù)甚至硬件都是為了降低IO操作而生,今天聊一聊過濾器,先說一個(gè)場景:

我們業(yè)務(wù)后端涉及數(shù)據(jù)庫,當(dāng)請(qǐng)求消息查詢某些信息時(shí),可能先檢查緩存中是否有相關(guān)信息,有的話返回,如果沒有的話可能就要去數(shù)據(jù)庫里面查詢,這時(shí)候有一個(gè)問題,如果很多請(qǐng)求是在請(qǐng)求數(shù)據(jù)庫根本不存在的數(shù)據(jù),那么數(shù)據(jù)庫就要頻繁響應(yīng)這種不必要的IO查詢,如果再多一些,數(shù)據(jù)庫大多數(shù)IO都在響應(yīng)這種毫無意義的請(qǐng)求操作,那么如何將這些請(qǐng)求阻擋在外呢?過濾器由此誕生:

布隆過濾器

布隆過濾器(Bloom Filter)大概的思路就是,當(dāng)你請(qǐng)求的信息來的時(shí)候,先檢查一下你查詢的數(shù)據(jù)我這有沒有,有的話將請(qǐng)求壓給數(shù)據(jù)庫,沒有的話直接返回,是如何做到的呢?

如圖,一個(gè)bitmap用于記錄,bitmap原始數(shù)值全都是0,當(dāng)一個(gè)數(shù)據(jù)存進(jìn)來的時(shí)候,用三個(gè)Hash函數(shù)分別計(jì)算三次Hash值,并且將bitmap對(duì)應(yīng)的位置設(shè)置為1,上圖中,bitmap 的1,3,6位置被標(biāo)記為1,這時(shí)候如果一個(gè)數(shù)據(jù)請(qǐng)求過來,依然用之前的三個(gè)Hash函數(shù)計(jì)算Hash值,如果是同一個(gè)數(shù)據(jù)的話,勢必依舊是映射到1,3,6位,那么就可以判斷這個(gè)數(shù)據(jù)之前存儲(chǔ)過,如果新的數(shù)據(jù)映射的三個(gè)位置,有一個(gè)匹配不上,假如映射到1,3,7位,由于7位是0,也就是這個(gè)數(shù)據(jù)之前并沒有加入進(jìn)數(shù)據(jù)庫,所以直接返回。

布隆過濾器的問題

上面這種方式,應(yīng)該你已經(jīng)發(fā)現(xiàn)了,布隆過濾器存在一些問題:

第一方面,布隆過濾器可能誤判:

假如有這么一個(gè)情景,放入數(shù)據(jù)包1時(shí),將bitmap的1,3,6位設(shè)置為了1,放入數(shù)據(jù)包2時(shí)將bitmap的3,6,7位設(shè)置為了1,此時(shí)一個(gè)并沒有存過的數(shù)據(jù)包請(qǐng)求3,做三次哈希之后,對(duì)應(yīng)的bitmap位點(diǎn)分別是1,6,7,這個(gè)數(shù)據(jù)之前并沒有存進(jìn)去過,但是由于數(shù)據(jù)包1和2存入時(shí)將對(duì)應(yīng)的點(diǎn)設(shè)置為了1,所以請(qǐng)求3也會(huì)壓倒數(shù)據(jù)庫上,這種情況,會(huì)隨著存入的數(shù)據(jù)增加而增加。

第二方面,布隆過濾器沒法刪除數(shù)據(jù),刪除數(shù)據(jù)存在以下兩種困境:

一是,由于有誤判的可能,并不確定數(shù)據(jù)是否存在數(shù)據(jù)庫里,例如數(shù)據(jù)包3。

二是,當(dāng)你刪除某一個(gè)數(shù)據(jù)包對(duì)應(yīng)位圖上的標(biāo)志后,可能影響其他的數(shù)據(jù)包,例如上面例子中,如果刪除數(shù)據(jù)包1,也就意味著會(huì)將bitmap1,3,6位設(shè)置為0,此時(shí)數(shù)據(jù)包2來請(qǐng)求時(shí),會(huì)顯示不存在,因?yàn)?,6兩位已經(jīng)被設(shè)置為0。

布隆過濾器增強(qiáng)版

為了解決上面布隆過濾器的問題,出現(xiàn)了一個(gè)增強(qiáng)版的布隆過濾器(Counting Bloom Filter),這個(gè)過濾器的思路是將布隆過濾器的bitmap更換成數(shù)組,當(dāng)數(shù)組某位置被映射一次時(shí)就+1,當(dāng)刪除時(shí)就-1,這樣就避免了普通布隆過濾器刪除數(shù)據(jù)后需要重新計(jì)算其余數(shù)據(jù)包Hash的問題,但是依舊沒法避免誤判。

布谷鳥過濾器

查詢性能弱是因?yàn)椴悸∵^濾器需要使用多個(gè) hash 函數(shù)探測位圖中多個(gè)不同的位點(diǎn)，這些位點(diǎn)在內(nèi)存上跨度很大，會(huì)導(dǎo)致 CPU 緩存行命中率低。

空間效率低是因?yàn)樵谙嗤恼`判率下，布谷鳥過濾器的空間利用率要明顯高于布隆，空間上大概能節(jié)省 40% 多。不過布隆過濾器并沒有要求位圖的長度必須是 2 的指數(shù)，而布谷鳥過濾器必須有這個(gè)要求。從這一點(diǎn)出發(fā)，似乎布隆過濾器的空間伸縮性更強(qiáng)一些。

不支持反向刪除操作這個(gè)問題著實(shí)是擊中了布隆過濾器的軟肋。在一個(gè)動(dòng)態(tài)的系統(tǒng)里面元素總是不斷的來也是不斷的走。布隆過濾器就好比是印跡，來過來就會(huì)有痕跡，就算走了也無法清理干凈。比如你的系統(tǒng)里本來只留下 1kw 個(gè)元素，但是整體上來過了上億的流水元素，布隆過濾器很無奈，它會(huì)將這些流失的元素的印跡也會(huì)永遠(yuǎn)存放在那里。隨著時(shí)間的流失，這個(gè)過濾器會(huì)越來越擁擠，直到有一天你發(fā)現(xiàn)它的誤判率太高了，不得不進(jìn)行重建。

布谷鳥過濾器在論文里聲稱自己解決了這個(gè)問題，它可以有效支持反向刪除操作。而且將它作為一個(gè)重要的賣點(diǎn)，誘惑你們放棄布隆過濾器改用布谷鳥過濾器。

為啥要取名布谷鳥呢?

有個(gè)成語，「鳩占鵲巢」,布谷鳥也是,布谷鳥從來不自己筑巢。它將自己的蛋產(chǎn)在別人的巢里，讓別人來幫忙孵化。待小布谷鳥破殼而出之后，因?yàn)椴脊萨B的體型相對(duì)較大，它又將養(yǎng)母的其它孩子（還是蛋）從巢里擠走 —— 從高空摔下夭折了。

布谷鳥哈希

最簡單的布谷鳥哈希結(jié)構(gòu)是一維數(shù)組結(jié)構(gòu)，會(huì)有兩個(gè) hash 算法將新來的元素映射到數(shù)組的兩個(gè)位置。如果兩個(gè)位置中有一個(gè)位置為空，那么就可以將元素直接放進(jìn)去。但是如果這兩個(gè)位置都滿了，它就不得不「鳩占鵲巢」，隨機(jī)踢走一個(gè)，然后自己霸占了這個(gè)位置。

p1 = hash1(x) % l
p2 = hash2(x) % l
復(fù)制代碼

不同于布谷鳥的是，布谷鳥哈希算法會(huì)幫這些受害者（被擠走的蛋）尋找其它的窩。因?yàn)槊恳粋€(gè)元素都可以放在兩個(gè)位置，只要任意一個(gè)有空位置，就可以塞進(jìn)去。所以這個(gè)傷心的被擠走的蛋會(huì)看看自己的另一個(gè)位置有沒有空，如果空了，自己挪過去也就皆大歡喜了。但是如果這個(gè)位置也被別人占了呢？好，那么它會(huì)再來一次「鳩占鵲巢」，將受害者的角色轉(zhuǎn)嫁給別人。然后這個(gè)新的受害者還會(huì)重復(fù)這個(gè)過程直到所有的蛋都找到了自己的巢為止。

布谷鳥哈希的問題

還會(huì)有另一個(gè)問題，那就是可能會(huì)存在擠兌循環(huán)。比如兩個(gè)不同的元素，hash 之后的兩個(gè)位置正好相同，這時(shí)候它們一人一個(gè)位置沒有問題。但是這時(shí)候來了第三個(gè)元素，它 hash 之后的位置也和它們一樣，很明顯，這時(shí)候會(huì)出現(xiàn)擠兌的循環(huán)。不過讓三個(gè)不同的元素經(jīng)過兩次 hash 后位置還一樣，這樣的概率并不是很高，除非你的 hash 算法太挫了。

布谷鳥哈希算法對(duì)待這種擠兌循環(huán)的態(tài)度就是認(rèn)為數(shù)組太擁擠了，需要擴(kuò)容（實(shí)際上并不是這樣）。

優(yōu)化

上面的布谷鳥哈希算法的平均空間利用率并不高，大概只有 50%。到了這個(gè)百分比，就會(huì)很快出現(xiàn)連續(xù)擠兌次數(shù)超出閾值。這樣的哈希算法價(jià)值并不明顯，所以需要對(duì)它進(jìn)行改良。

改良的方案之一是增加 hash 函數(shù)，讓每個(gè)元素不止有兩個(gè)巢，而是三個(gè)巢、四個(gè)巢。這樣可以大大降低碰撞的概率，將空間利用率提高到 95%左右。

另一個(gè)改良方案是在數(shù)組的每個(gè)位置上掛上多個(gè)座位，這樣即使兩個(gè)元素被 hash 在了同一個(gè)位置，也不必立即「鳩占鵲巢」，因?yàn)檫@里有多個(gè)座位，你可以隨意坐一個(gè)。除非這多個(gè)座位都被占了，才需要進(jìn)行擠兌。很明顯這也會(huì)顯著降低擠兌次數(shù)。這種方案的空間利用率只有 85%左右，但是查詢效率會(huì)很高，同一個(gè)位置上的多個(gè)座位在內(nèi)存空間上是連續(xù)的，可以有效利用 CPU 高速緩存。

所以更加高效的方案是將上面的兩個(gè)改良方案融合起來，比如使用 4 個(gè) hash 函數(shù)，每個(gè)位置上放 2 個(gè)座位。這樣既可以得到時(shí)間效率，又可以得到空間效率。這樣的組合甚至可以將空間利用率提到高 99%，這是非常了不起的空間效率。

布谷鳥過濾器

首先布谷鳥過濾器還是只會(huì)選用兩個(gè) hash 函數(shù)，但是每個(gè)位置可以放置多個(gè)座位。這兩個(gè) hash 函數(shù)選擇的比較特殊，因?yàn)檫^濾器中只能存儲(chǔ)指紋信息。當(dāng)這個(gè)位置上的指紋被擠兌之后，它需要計(jì)算出另一個(gè)對(duì)偶位置。而計(jì)算這個(gè)對(duì)偶位置是需要元素本身的，我們來回憶一下前面的哈希位置計(jì)算公式。

fp = fingerprint(x)
p1 = hash1(x) % l
p2 = hash2(x) % l

我們知道了 p1 和 x 的指紋，是沒辦法直接計(jì)算出 p2 的。

特殊的 hash 函數(shù)

布谷鳥過濾器巧妙的地方就在于設(shè)計(jì)了一個(gè)獨(dú)特的 hash 函數(shù)，使得可以根據(jù) p1 和 元素指紋 直接計(jì)算出 p2，而不需要完整的 x 元素。

fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)  // 異或

從上面的公式中可以看出，當(dāng)我們知道 fp 和 p1，就可以直接算出 p2。同樣如果我們知道 p2 和 fp，也可以直接算出 p1 —— 對(duì)偶性。

p1 = p2 ^ hash(fp)

所以我們根本不需要知道當(dāng)前的位置是 p1 還是 p2，只需要將當(dāng)前的位置和 hash(fp) 進(jìn)行異或計(jì)算就可以得到對(duì)偶位置。而且只需要確保 hash(fp) != 0 就可以確保 p1 != p2，如此就不會(huì)出現(xiàn)自己踢自己導(dǎo)致死循環(huán)的問題。

也許你會(huì)問為什么這里的 hash 函數(shù)不需要對(duì)數(shù)組的長度取模呢？實(shí)際上是需要的，但是布谷鳥過濾器強(qiáng)制數(shù)組的長度必須是 2 的指數(shù)，所以對(duì)數(shù)組的長度取模等價(jià)于取 hash 值的最后 n 位。在進(jìn)行異或運(yùn)算時(shí)，忽略掉低 n 位 之外的其它位就行。將計(jì)算出來的位置 p 保留低 n 位就是最終的對(duì)偶位置。

后臺(tái)回復(fù)?學(xué)習(xí)資料?領(lǐng)取學(xué)習(xí)視頻