Redis布隆過濾器和布谷鳥過濾器

• 2022 年 6 月 29 日
• 筆記

一、過濾器使用場景：
比如有如下幾個需求：
1、原本有10億個號碼，現在又來了10萬個號碼，要快速準確判斷這10萬個號碼是否在10億個號碼庫中？
　　解決辦法一：將10億個號碼存入資料庫中，進行資料庫查詢，準確性有了，但是速度會比較慢。
　　解決辦法二：將10億號碼放入記憶體中，比如Redis快取中，這裡我們算一下佔用記憶體大小：10億*8位元組=8GB，通過記憶體查詢，準確性和速度都有了，但是大約8gb的記憶體空間，挺浪費記憶體空間的。
2、接觸過爬蟲的，應該有這麼一個需求，需要爬蟲的網站千千萬萬，對於一個新的網站url，我們如何判斷這個url我們是否已經爬過了？
解決辦法還是上面的兩種，很顯然，都不太好。
3、同理還有垃圾郵箱的過濾。
　　那麼對於類似這種，大數據量集合，如何準確快速的判斷某個數據是否在大數據量集合中，並且不佔用記憶體，過濾器應運而生了。

二、布隆過濾器（Bloom Filter）
布隆過濾器：一種數據結構（bitmap），是由一串很長的二進位向量組成，可以將其看成一個二進位數組。既然是二進位，那麼裡面存放的不是0，就是1，但是初始默認值都是0。

布隆過濾器使用exists()來判斷某個元素是否存在於自身結構中。當布隆過濾器判定某個值存在時，其實這個值只是有可能存在；當它說某個值不存在時，那這個值肯定不存在，這個誤判概率大約在 1% 左右。
工作流程-添加元素
布隆過濾器主要由位數組和一系列 hash 函數構成，其中位數組的初始狀態都為 0。
下面對布隆過濾器工作流程做簡單描述，如下圖所示：

當使用布隆過濾器添加 key 時，會使用不同的 hash 函數對 key 存儲的元素值進行哈希計算，從而會得到多個哈希值。根據哈希值計算出一個整數索引值，將該索引值與位數組長度做取余運算，最終得到一個位數組位置，並將該位置的值變為 1。每個 hash 函數都會計算出一個不同的位置，然後把數組中與之對應的位置變為 1。通過上述過程就完成了元素添加(add)操作。

工作流程-判定元素是否存在
當我們需要判斷一個元素是否存時，其流程如下：首先對給定元素再次執行哈希計算，得到與添加元素時相同的位數組位置，判斷所得位置是否都為 1，如果其中有一個為 0，那麼說明元素不存在，若都為 1，則說明元素有可能存在。

為什麼是可能「存在」
您可能會問，為什麼是有可能存在？其實原因很簡單，那些被置為 1 的位置也可能是由於其他元素的操作而改變的。比如，元素1 和 元素2，這兩個元素同時將一個位置變為了 1（圖1所示）。在這種情況下，我們就不能判定「元素 1」一定存在，這是布隆過濾器存在誤判的根本原因。

將這個新的數據通過上面自定義的幾個哈希函數，分別算出各個值，然後看其對應的地方是否都是1，如果存在一個不是1的情況，那麼我們可以說，該新數據一定不存在於這個布隆過濾器中。
反過來說，如果通過哈希函數算出來的值，對應的地方都是1，那麼我們能夠肯定的得出：這個數據一定存在於這個布隆過濾器中嗎？
答案是否定的，因為多個不同的數據通過hash函數算出來的結果是會有重複的，所以會存在某個位置是別的數據通過hash函數置為的1。
我們可以得到一個結論：布隆過濾器可以判斷某個數據一定不存在，但是無法判斷一定存在。

3.布隆過濾器優缺點

優點：優點很明顯，二進位組成的數組，佔用記憶體極少，並且插入和查詢速度都足夠快。
缺點：隨著數據的增加，誤判率會增加；還有無法判斷數據一定存在；另外還有一個重要缺點，無法刪除數據。

1.將演算法和bitmap數據放在client
2.演算法在client，bitmap數據在redis
3.講演算法和bitmap數據都放在redis

升級版的布隆過濾器（Counting Bloom Filter）
原理就是把點陣圖的位 升級為計數器(Counter). 添加元素, 就給對應的Counter分別+1; 刪除元素, 就給對應的Counter分別減一. 用多出幾倍存儲空間的代價, 來實現刪除功能

三、布谷鳥過濾器（Cuckoo filter）
為了解決布隆過濾器不能刪除元素的問題, 論文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鳥過濾器。相比布谷鳥過濾器，布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支援反向操作（刪除）以及不支援計數。
1、查詢性能弱是因為布隆過濾器需要使用多個 hash 函數探測點陣圖中多個不同的位點，這些位點在記憶體上跨度很大，會導致 CPU 快取行命中率低。
2、空間效率低是因為在相同的誤判率下，布谷鳥過濾器的空間利用率要明顯高於布隆，空間上大概能節省 40% 多。不過布隆過濾器並沒有要求點陣圖的長度必須是 2 的指數，而布谷鳥過濾器必須有這個要求。從這一點出發，似乎布隆過濾器的空間伸縮性更強一些。
3、不支援反向刪除操作這個問題著實是擊中了布隆過濾器的軟肋。在一個動態的系統裡面元素總是不斷的來也是不斷的走。布隆過濾器就好比是印跡，來過來就會有痕迹，就算走了也無法清理乾淨。比如你的系統里本來只留下 1kw 個元素，但是整體上來過了上億的流水元素，布隆過濾器很無奈，它會將這些流失的元素的印跡也會永遠存放在那裡。隨著時間的流失，這個過濾器會越來越擁擠，直到有一天你發現它的誤判率太高了，不得不進行重建。
4、布谷鳥哈希
最簡單的布谷鳥哈希結構是一維數組結構，會有兩個 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 位就是最終的對偶位置。