Redis 之布隆過濾器與布穀鳥過濾器

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

我們業務後端涉及數據庫, 當請求消息查詢某些信息時, 可能先檢查緩存中是否有相關信息, 有的話返回, 如果沒有的話可能就要去數據庫裏面查詢, 這時候有一個問題, 如果很多請求是在請求數據庫根本不存在的數據, 那麼數據庫就要頻繁響應這種不必要的 IO 查詢, 如果再多一些, 數據庫大多數 IO 都在響應這種毫無意義的請求操作, 那麼如何將這些請求阻擋在外呢? 過濾器由此誕生:

布隆過濾器

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

如圖, 一個 bitmap 用於記錄, bitmap 原始數值全都是 0, 當一個數據存進來的時候, 用三個 Hash 函數分別計算三次 Hash 值, 並且將 bitmap 對應的位置設置爲 1, 上圖中, bitmap 的 1,3,6 位置被標記爲 1, 這時候如果一個數據請求過來, 依然用之前的三個 Hash 函數計算 Hash 值, 如果是同一個數據的話, 勢必依舊是映射到 1,3,6 位, 那麼就可以判斷這個數據之前存儲過, 如果新的數據映射的三個位置, 有一個匹配不上, 假如映射到 1,3,7 位, 由於 7 位是 0, 也就是這個數據之前並沒有加入進數據庫, 所以直接返回。

布隆過濾器的問題

上面這種方式, 應該你已經發現了, 布隆過濾器存在一些問題:

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

假如有這麼一個情景, 放入數據包 1 時, 將 bitmap 的 1,3,6 位設置爲了 1, 放入數據包 2 時將 bitmap 的 3,6,7 位設置爲了 1, 此時一個並沒有存過的數據包請求 3, 做三次哈希之後, 對應的 bitmap 位點分別是 1,6,7, 這個數據之前並沒有存進去過, 但是由於數據包 1 和 2 存入時將對應的點設置爲了 1, 所以請求 3 也會壓倒數據庫上, 這種情況, 會隨着存入的數據增加而增加。

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

一是, 由於有誤判的可能, 並不確定數據是否存在數據庫裏, 例如數據包 3。

二是, 當你刪除某一個數據包對應位圖上的標誌後, 可能影響其他的數據包, 例如上面例子中, 如果刪除數據包 1, 也就意味着會將 bitmap1,3,6 位設置爲 0, 此時數據包 2 來請求時, 會顯示不存在, 因爲 3,6 兩位已經被設置爲 0。

布隆過濾器增強版

爲了解決上面布隆過濾器的問題, 出現了一個增強版的布隆過濾器 (Counting Bloom Filter), 這個過濾器的思路是將布隆過濾器的 bitmap 更換成數組, 當數組某位置被映射一次時就 + 1, 當刪除時就 - 1, 這樣就避免了普通布隆過濾器刪除數據後需要重新計算其餘數據包 Hash 的問題, 但是依舊沒法避免誤判。

布穀鳥過濾器

爲了解決布隆過濾器不能刪除元素的問題, 論文《Cuckoo Filter：Better Than Bloom》作者提出了布穀鳥過濾器。相比布穀鳥過濾器，布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（刪除）以及不支持計數。

查詢性能弱是因爲布隆過濾器需要使用多個 hash 函數探測位圖中多個不同的位點，這些位點在內存上跨度很大，會導致 CPU 緩存行命中率低。

空間效率低是因爲在相同的誤判率下，布穀鳥過濾器的空間利用率要明顯高於布隆，空間上大概能節省 40% 多。不過布隆過濾器並沒有要求位圖的長度必須是 2 的指數，而布穀鳥過濾器必須有這個要求。從這一點出發，似乎布隆過濾器的空間伸縮性更強一些。

不支持反向刪除操作這個問題着實是擊中了布隆過濾器的軟肋。在一個動態的系統裏面元素總是不斷的來也是不斷的走。布隆過濾器就好比是印跡，來過來就會有痕跡，就算走了也無法清理乾淨。比如你的系統裏本來只留下 1kw 個元素，但是整體上來過了上億的流水元素，布隆過濾器很無奈，它會將這些流失的元素的印跡也會永遠存放在那裏。隨着時間的流失，這個過濾器會越來越擁擠，直到有一天你發現它的誤判率太高了，不得不進行重建。

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

爲啥要取名布穀鳥呢?

有個成語，「鳩佔鵲巢」, 布穀鳥也是, 布穀鳥從來不自己築巢。它將自己的蛋產在別人的巢裏，讓別人來幫忙孵化。待小布谷鳥破殼而出之後，因爲布穀鳥的體型相對較大，它又將養母的其它孩子（還是蛋）從巢裏擠走 —— 從高空摔下夭折了。

布穀鳥哈希

最簡單的布穀鳥哈希結構是一維數組結構，會有兩個 hash 算法將新來的元素映射到數組的兩個位置。如果兩個位置中有一個位置爲空，那麼就可以將元素直接放進去。但是如果這兩個位置都滿了，它就不得不「鳩佔鵲巢」，隨機踢走一個，然後自己霸佔了這個位置。

p1 = hash1(x) % l
p2 = hash2(x) % l
複製代碼

不同於布穀鳥的是，布穀鳥哈希算法會幫這些受害者（被擠走的蛋）尋找其它的窩。因爲每一個元素都可以放在兩個位置，只要任意一個有空位置，就可以塞進去。所以這個傷心的被擠走的蛋會看看自己的另一個位置有沒有空，如果空了，自己挪過去也就皆大歡喜了。但是如果這個位置也被別人佔了呢？好，那麼它會再來一次「鳩佔鵲巢」，將受害者的角色轉嫁給別人。然後這個新的受害者還會重複這個過程直到所有的蛋都找到了自己的巢爲止。

布穀鳥哈希的問題

但是會遇到一個問題，那就是如果數組太擁擠了，連續踢來踢去幾百次還沒有停下來，這時候會嚴重影響插入效率。這時候布穀鳥哈希會設置一個閾值，當連續佔巢行爲超出了某個閾值，就認爲這個數組已經幾乎滿了。這時候就需要對它進行擴容，重新放置所有元素。

還會有另一個問題，那就是可能會存在擠兌循環。比如兩個不同的元素，hash 之後的兩個位置正好相同，這時候它們一人一個位置沒有問題。但是這時候來了第三個元素，它 hash 之後的位置也和它們一樣，很明顯，這時候會出現擠兌的循環。不過讓三個不同的元素經過兩次 hash 後位置還一樣，這樣的概率並不是很高，除非你的 hash 算法太挫了。

布穀鳥哈希算法對待這種擠兌循環的態度就是認爲數組太擁擠了，需要擴容（實際上並不是這樣）。

優化

上面的布穀鳥哈希算法的平均空間利用率並不高，大概只有 50%。到了這個百分比，就會很快出現連續擠兌次數超出閾值。這樣的哈希算法價值並不明顯，所以需要對它進行改良。

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

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

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

布穀鳥過濾器

布穀鳥過濾器和布穀鳥哈希結構一樣，它也是一維數組，但是不同於布穀鳥哈希的是，布穀鳥哈希會存儲整個元素，而布穀鳥過濾器中只會存儲元素的指紋信息（幾個 bit，類似於布隆過濾器）。這裏過濾器犧牲了數據的精確性換取了空間效率。正是因爲存儲的是元素的指紋信息，所以會存在誤判率，這點和布隆過濾器如出一轍。

首先布穀鳥過濾器還是隻會選用兩個 hash 函數，但是每個位置可以放置多個座位。這兩個 hash 函數選擇的比較特殊，因爲過濾器中只能存儲指紋信息。當這個位置上的指紋被擠兌之後，它需要計算出另一個對偶位置。而計算這個對偶位置是需要元素本身的，我們來回憶一下前面的哈希位置計算公式。

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

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

特殊的 hash 函數

布穀鳥過濾器巧妙的地方就在於設計了一個獨特的 hash 函數，使得可以根據 p1 和 元素指紋 直接計算出 p2，而不需要完整的 x 元素。

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

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

p1 = p2 ^ hash(fp)

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

也許你會問爲什麼這裏的 hash 函數不需要對數組的長度取模呢？實際上是需要的，但是布穀鳥過濾器強制數組的長度必須是 2 的指數，所以對數組的長度取模等價於取 hash 值的最後 n 位。在進行異或運算時，忽略掉低 n 位 之外的其它位就行。將計算出來的位置 p 保留低 n 位就是最終的對偶位置。

作者：等不到的口琴

來源：www.cnblogs.com/Courage129/p/14337466.html

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/n2ske1NVu-9TsmtgwgHmhg