布隆過濾器揭秘：讓URL黑名單存儲從640GB縮小到35.88GB！
1.引言
大家好，我是小米，一個熱愛分享技術的小伙伴。今天我們來聊一聊在實際工作中如何使用布隆過濾器（Bloom Filter）來處理大規(guī)模URL黑名單的存儲和查詢問題。
2.問題背景
假設我們有一個規(guī)模達到100億的黑名單URL集合，每個URL的長度為64字節(jié)。如何高效地存儲和查詢這個黑名單呢？
3.散列表方法
我們先考慮一下常規(guī)的散列表方法。如果使用HashMap來存儲這些URL：
- 每個URL 64字節(jié)
- 100億個URL需要存儲：100億 * 64B = 640GB
顯然，這樣的存儲需求是不可行的，因為它對內(nèi)存的要求太高。
4.布隆過濾器介紹
這時候，我們可以引入布隆過濾器，它是一種高效的概率型數(shù)據(jù)結構，用于檢測一個元素是否屬于一個集合。布隆過濾器具有以下特點：
- 占用空間小
- 查詢速度快
- 允許一定的誤判（即可能認為不存在的元素存在，但不會把存在的元素認為不存在）
5.布隆過濾器原理
布隆過濾器由一個很長的二進制位數(shù)組和一系列隨機映射函數(shù)（哈希函數(shù)）組成。
- 位數(shù)組：每個元素占用1 bit，初始時所有位都設為0。
- 哈希函數(shù)：假設有K個哈希函數(shù)，每個函數(shù)將輸入元素映射為位數(shù)組的一個下標。
插入元素
當一個元素加入布隆過濾器時，執(zhí)行以下步驟：
- 使用K個哈希函數(shù)對元素進行哈希計算，得到K個哈希值。
- 將位數(shù)組中對應哈希值位置的bit設為1。
查詢元素
查詢一個元素是否在布隆過濾器中時，執(zhí)行以下步驟：
- 使用K個哈希函數(shù)對查詢元素進行哈希計算，得到K個哈希值。
- 檢查位數(shù)組中對應哈希值位置的bit是否都為1。如果都為1，則認為該元素存在；如果有一個為0，則認為該元素不存在。
6.計算布隆過濾器參數(shù)
為了更好地理解布隆過濾器的存儲效率，我們需要計算以下參數(shù)：
- 位數(shù)組長度（m）：我們需要選擇一個合適的位數(shù)組長度來保證較低的誤判率。
- 哈希函數(shù)數(shù)量（K）：哈希函數(shù)的數(shù)量也需要根據(jù)集合大小和位數(shù)組長度來確定。
假設我們允許的誤判率為0.01%，我們可以使用以下公式來計算m和K：
圖片
其中，n是集合中的元素數(shù)量，p是允許的誤判率。
具體計算如下：
圖片
代入公式：
圖片
通過計算，我們得出位數(shù)組的長度為287億bit（約合35.88GB），需要20個哈希函數(shù)。這樣，布隆過濾器的內(nèi)存占用從原來的640GB大幅減少到了35.88GB，且具有較高的查詢效率。
7.布隆過濾器的實現(xiàn)
下面是布隆過濾器的Java實現(xiàn)，包括初始化、添加元素和查詢元素的代碼。
圖片
圖片
代碼說明
- BitSet：用于存儲位數(shù)組。
- MessageDigest：用于生成哈希值。
- add：將一個URL添加到布隆過濾器中。
- check：檢查一個URL是否存在于布隆過濾器中。
- getHash：生成哈希值，并結合種子（seed）確保多個哈希函數(shù)的實現(xiàn)。
- intToBytes：將整數(shù)轉換為字節(jié)數(shù)組，用于哈希函數(shù)的種子。
這個實現(xiàn)使用了MD5哈希函數(shù)，可以根據(jù)需求選擇其他哈希函數(shù)。通過調(diào)整位數(shù)組大小和哈希函數(shù)數(shù)量，可以在存儲效率和誤判率之間取得平衡。
END
布隆過濾器作為一種高效的概率型數(shù)據(jù)結構，能夠在大規(guī)模數(shù)據(jù)集上實現(xiàn)高效的存儲和查詢，特別適用于URL黑名單這樣的場景。通過合理地選擇位數(shù)組長度和哈希函數(shù)數(shù)量，我們可以在保證較低誤判率的前提下，大幅減少內(nèi)存使用。
