題目描述

現(xiàn)在想要實(shí)現(xiàn)一個(gè)網(wǎng)頁(yè)過(guò)濾系統(tǒng)，利用該系統(tǒng)可以根據(jù)網(wǎng)頁(yè)的 URL 判斷該網(wǎng)頁(yè)是否在黑名單上，黑名單現(xiàn)在已經(jīng)包含 100 億個(gè)不安全網(wǎng)頁(yè)的 URL，每個(gè)網(wǎng)頁(yè)的 URL 最多占用 64B(字節(jié)) 大小。

請(qǐng)?jiān)O(shè)計(jì)該系統(tǒng)， 要求：

• 該系統(tǒng)允許有萬(wàn)分之一以下的判斷失誤率
• 使用的額外空間不要超過(guò) 30GB

解題思路

最簡(jiǎn)單的想法，把黑名單中所有的 URL 通過(guò)數(shù)據(jù)庫(kù)或哈希表保存下來(lái)，然后遍歷一遍就能判重。

But，每個(gè) URL 有 64 B(字節(jié))，黑名單中有 100 億條 URL，那想要用數(shù)據(jù)庫(kù)或者哈希表把這些數(shù)據(jù)全部存儲(chǔ)起來(lái)，至少需要 640GB 的空間，顯然不滿足要求 2(使用的額外空間不要超過(guò) 30GB)。

事實(shí)上，這個(gè)題目有一個(gè)很明顯的提示，那就是允許失誤率!

類似的這種 網(wǎng)頁(yè)黑名單系統(tǒng)、垃圾郵件過(guò)濾系統(tǒng)、爬蟲的網(wǎng)址判重系統(tǒng) 等題目，一般都是允許一定的失誤率的，但是對(duì)空間要求比較嚴(yán)格。

啥也別說(shuō)第一個(gè)就應(yīng)該想到布隆過(guò)濾器。

簡(jiǎn)單介紹下布隆過(guò)濾器的基本構(gòu)造，其實(shí)就是一個(gè) BitMap(更簡(jiǎn)單點(diǎn)來(lái)說(shuō)其實(shí)就是一個(gè)數(shù)組)，BitMap 中每個(gè)位上的元素由若干個(gè)哈希函數(shù)進(jìn)行賦值。布隆過(guò)濾器的優(yōu)勢(shì)在于使用很少的空間就可以將準(zhǔn)確率做到很高的程度(但想做到完全正確是不可能的)。

哈希函數(shù)(散列函數(shù))就不用多少了，主要有以下節(jié)點(diǎn)特性：

• 哈希函數(shù)一般都可以輸入任意數(shù)值，也就是有無(wú)限的輸入值域。
• 當(dāng)給哈希函數(shù)傳入相同的輸入值時(shí)，返回值一樣。
• 當(dāng)給哈希函數(shù)傳入不同的輸入值時(shí)，由于哈希沖突的存在，所以返回值可能一樣，也可能不一樣。
• 不同的輸入值所得到的返回值會(huì)均勻地分布。

顯然，返回值分布越均勻，哈希函數(shù)就越優(yōu)秀。有興趣的小伙伴可以了解哈希函數(shù)的一些經(jīng)典實(shí)現(xiàn)，比如 MD5 和 SHA1算法，這里就不詳細(xì)介紹了。

再來(lái)看布隆過(guò)濾器。假設(shè)有一個(gè)長(zhǎng)度為 m 的 bit(位) 類型的數(shù)組(也就是 BitMap 位圖，上篇文章介紹過(guò)的)，即數(shù)組中的每一個(gè)位置只占一個(gè) bit(每一個(gè) bit 只有 0 和 1 兩種狀態(tài))：

再假設(shè)一共有 k 個(gè)不同的哈希函數(shù)，它們的輸出域都 >= m。

那么對(duì)同一個(gè)輸入對(duì)象(假設(shè)是一個(gè) URL，字符串)，經(jīng)過(guò) k 個(gè)哈希函數(shù)算出來(lái)的結(jié)果也是不一樣的(當(dāng)然也有可能相同)。對(duì)算出來(lái)的每一個(gè)結(jié)果都對(duì) m 取余(%m)，然后在 BitMap 上把相應(yīng)的位置設(shè)置為 1(涂黑)：

按照上述方法，我們處理所有的輸入對(duì)象(黑名單中 200 億條 URL)，每個(gè)對(duì)象都可能把 BitMap 中的一些白位置涂黑(0 的位置為 1)。

這樣，存儲(chǔ)了黑名單中 200 億條 URL 的布隆過(guò)濾器就構(gòu)造完成了。

那么假設(shè)這時(shí)又來(lái)了一個(gè)新值，如何判斷這個(gè)新值之前是否已經(jīng)存在呢?(如何判斷某個(gè)網(wǎng)頁(yè)的 URL 是否在黑名單上呢?)

記這個(gè)網(wǎng)頁(yè)的 URL 為 input，想檢查它是否是存在于黑名單(BitMap)中，就把 input 通過(guò)同樣的 k 個(gè)哈希函數(shù)，得到 k 個(gè)值，然后繼續(xù)同樣地把 k 個(gè)值取余(%m)，就得到在 [0, m-1] 范圍上的 k 個(gè)值，接下來(lái)在 BitMap 上看這些位置是不是都為黑：

• 如果有一個(gè)不為黑，說(shuō)明 input 一定不在這個(gè) BitMap 里。
• 如果都為黑，說(shuō)明 a 可能在這個(gè) BitMap 里，也就是說(shuō)存在誤判的可能性。

解釋具體一點(diǎn)，如果 input 的確是之前已經(jīng)處理過(guò)的 URL，那么在生成布隆過(guò)濾器時(shí)，BitMap 中相應(yīng)的 k 個(gè)位置一定已經(jīng)涂黑了，所以在檢查階段，input 執(zhí)行一遍相同的操作，肯定不會(huì)產(chǎn)生誤判的。

會(huì)產(chǎn)生誤判的是，input 明明不是之前已經(jīng)處理過(guò)的輸入對(duì)象，但由于哈希沖突的存在，可能就那么巧，兩個(gè)不同的輸入得到的 k 個(gè)哈希輸出都是一樣的(當(dāng)然概率會(huì)非常小)，那么在檢查 input 時(shí)，可能 input 對(duì)應(yīng)的 k 個(gè)位置都是黑的，從而錯(cuò)誤地認(rèn)為 input 是輸入對(duì)象。

所以用布隆過(guò)濾器設(shè)計(jì)的系統(tǒng)，總結(jié)來(lái)說(shuō)就是：黑名單中存在的 URL，一定能夠檢查出來(lái)，黑名單中不存在的 URL，有比較小的可能性被誤判。

對(duì)于這種誤判，其實(shí)也有解決方案，那就是白名單，對(duì)已經(jīng)發(fā)現(xiàn)的誤報(bào)數(shù)據(jù)我們可以通過(guò)建立白名單來(lái)防止再次誤報(bào)。

比如，已經(jīng)發(fā)現(xiàn) www.baidu.com 這個(gè)樣本不在布隆過(guò)濾器(黑名單)中，但是每次計(jì)算后的結(jié)果都顯示其在布隆過(guò)濾器中，那么就可以把這個(gè)樣本加入白名單中，以后這個(gè)樣本再次輸入的時(shí)候，就不會(huì)進(jìn)入布隆過(guò)濾器的邏輯進(jìn)行判斷了。

手寫布隆過(guò)濾器

下面來(lái)用 Java 實(shí)現(xiàn)一個(gè)布隆過(guò)濾器，參考這篇文章：https://cloud.tencent.com/developer/article/1823271。

首先我們當(dāng)然需要一個(gè)位數(shù)組，Java 提供了一個(gè)封裝好的位數(shù)組 BitSet。

除此之外，寫一個(gè)簡(jiǎn)單的布隆過(guò)濾器需要考慮的點(diǎn)有這些：

• 位數(shù)組的大小空間，需要指定，其他相同的時(shí)候，位數(shù)組的大小越大，hash 沖突的可能性越小。
• 多個(gè) hash 函數(shù)，為了避免沖突，我們可以使用多個(gè)不同的質(zhì)數(shù)來(lái)當(dāng)種子。
• 應(yīng)該對(duì)外提供的方法：主要有兩個(gè)，一個(gè)往布隆過(guò)濾器里面添加元素，另一個(gè)是判斷布隆過(guò)濾器是否包含某個(gè)元素。

重點(diǎn)在下圖框出來(lái)了：

Hash 函數(shù)的實(shí)現(xiàn)這里就不多做研究了，給出一個(gè)比較簡(jiǎn)單的版本，主要是將 hashCode() 值的高位和低位進(jìn)行異或，然后乘以預(yù)設(shè)定的種子(seed)，再對(duì) BitMap 數(shù)組的大小進(jìn)行取余數(shù)：