Redis布隆過濾器大小的演算法公式是什麼

1. 簡介

客戶端：這個key存在嗎？

伺服器：不存在/不知道

布隆過濾器是一種比較巧妙的機率型資料結構，其本質是一種資料結構。它的特點是有效率地插入和查詢。但我們要檢查一個key是否在某個結構中存在時，透過使用布隆過濾器，我們可以快速了解到「這個key一定不存在或可能存在」。相較於傳統的List、Set、Map這些資料結構，它更有效率、佔用的空間也越少，但是它回傳的結果是機率性的，是不確切的。

布隆過濾器僅用於測試集合中的成員資格。經典的布隆過濾器範例是透過減少對不存在的金鑰的昂貴的磁碟（或網路）查找來提高效率。正如我們所看到的那樣，布隆過濾器可以在O（k）恆定時間內搜尋密鑰，其中k是雜湊函數的數量，測試密鑰的不存在將非常快。

2. 應用程式場景

2.1 快取穿透

為了提高存取效率，我們會將一些資料放在Redis快取中。當進行數據查詢時，可以先從快取中獲取數據，無需讀取資料庫。這樣可以有效提升性能。
在數據查詢時，首先要判斷快取中是否有數據，如果有數據，就直接從快取中獲取數據。
但如果沒有數據，就需要從資料庫中取得數據，然後放入快取。如果大量存取都無法命中緩存，會造成資料庫要扛較大壓力，導致資料庫崩潰。而使用布隆過濾器，當存取不存在的快取時，可以迅速回傳避免快取或DB crash。

2.2 判斷某個數據是否在海量數據中存在

HBase中儲存著非常海量數據，要判斷某個ROWKEYS、或者某個列是否存在，使用布隆過濾器，可以快速取得某個資料是否存在。但有一定的誤判率。但如果某個key不存在，一定是準確的。

3. HashMap的問題

要判斷某個元素是否存在其實用HashMap效率是非常高的。 HashMap透過把值映射為HashMap的Key，這種方式可以實現O(1)常數級時間複雜​​度。
但是，如果儲存的資料量非常大的時候（例如：上億的資料），HashMap將會耗費非常大的記憶體大小。而且根本無法一次將海量的資料讀進記憶體。

4. 理解布隆過濾器

工作原理圖：

#布隆過濾器是一個bit數組或稱為一個bit二進位向量
這個陣列中的元素存的要麼是0、要麼是1
k個hash函數都是彼此獨立的，並將每個hash函數計算後的結果對數組的長度m取模，並將對一個的bit設為1（藍色單元格）
我們將每個key都按照這種方式設定單元格，就是「布隆過濾器」

5. 根據布隆過濾器查詢元素

假設輸入一個key，我們使用之前的k個hash函數求哈希，得到k個值
判斷這k個值是否都為藍色，如果有一個不是藍色，那麼這個key一定不存在
如果都有藍色，那麼key是可能存在（布隆過濾器會存在誤判）
因為如果輸入物件很多，而集合比較小的情況，會導致集合中大多位置都會被描藍，那麼檢查某個key時候為藍色時，剛好某個位置正好被設定為藍色了，此時，會錯誤認為該key在集合中
範例：

6. 可以刪除麼

傳統的布隆過濾器並不支援刪除操作。但是名為 Counting Bloom filter 的變種可以用來測試元素計數個數是否絕對小於某個閾值，它支援元素刪除。文章Counting Bloom Filter的原理和實作寫得非常詳細，可以詳細閱讀了解。

7. 如何選擇哈希函數個數和布隆過濾器長度

很顯然，過小的布隆過濾器很快所有的bit 位元均為1，那麼查詢任何值都會返回“可能存在”，起不到過濾的目的了。隨著布隆過濾器長度的增加，其誤報率會減少。

另外，雜湊函數的數量也需要權衡，個數越多則布隆過濾器bit 位置位1 的速度越快，且布隆過濾器的效率越低；但是如果太少的話，那我們的誤報率會變高。

從上圖可以看出，增加雜湊函數k的數量將大大降低錯誤率p。

不必擔心，實際上我們需要確認 m 和 k 的值。那麼，如果我們指定了容錯率p和元素數量n，可以利用以下公式計算這些參數：

我們可以根據濾波器的大小m，雜湊函數的數量k和插入的元素的數量n來計算誤報率p，公式如下：由上面，又怎麼選擇適合業務的k 和m 值呢？
公式：

k 為雜湊函數個數，m 為布隆過濾器長度，n 為插入的元素個數，p 為誤報率。
至於如何推導這個公式，我在知乎發布的文章有涉及，感興趣可以看看，不感興趣的話記住上面這個公式就行了。

我還要在這裡提到另一個重要的觀點。由於使用Bloom篩選器的唯一目的是搜尋速度更快，所以我們不能使用慢速雜湊函數，對嗎？加密雜湊函數（例如Sha-1，MD5）對於bloom過濾器不是一個好選擇，因為它們有點慢。因此，從更快的哈希函數實現中更好的選擇是murmur，fnv系列哈希，Jenkins哈希和HashMix。

更多應用程式場景

在給定的範例中您已經看到，我們可以使用它來警告使用者輸入弱密碼。
您可以使用布隆過濾器，以防止使用者從造訪惡意網站。
您可以先使用Bloom Bloom篩選器進行廉價的查找檢查，而不是用查詢SQL資料庫來檢查是否存在具有特定電子郵件的使用者。如果電子郵件不存在，那就太好了！如果確實存在，則可能必須對資料庫進行額外的查詢。您也可以執行相同的操作來搜尋「使用者名稱已被佔用」。
您可以根據網站訪客的IP位址保留一個Bloom過濾器，以檢查您網站的使用者是「回頭用戶」還是「新用戶」。 「回頭用戶」的一些誤報不會傷害您，對嗎？
您也可以透過使用Bloom過濾器追蹤字典單字來進行拼字檢查。

以上是Redis布隆過濾器大小的演算法公式是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！