使用布隆過濾器在開發數據查重時更高效

傳統方式

假設你現在要處理這樣一個問題,你有一個網站並且擁有很多訪客,每當有用戶訪問時,你想知道這個ip是不是第一次訪問你的網站。這是一個很常見的場景,為了完成這個功能,你很容易就會想到下面這個解決方案:

把訪客的ip存進一個hash表中,每當有新的訪客到來時,先檢查哈希表中是否有改訪客的ip,如果有則說明該訪客在黑名單中。你還知道,hash表的存取時間複雜度都是O(1),效率很高,因此你對你的方案很是滿意。

然後我們假設你的網站已經被1億個用戶訪問過,每個ip的長度是15,那麼你一共需要15 * 100000000 = 1500000000Bytes = 1.4G,這還沒考慮hash衝突的問題(hash表中的槽位越多,越浪費空間,槽位越少,效率越低)。

於是聰明的你稍一思考,又想到可以把ip轉換成無符號的int型值來存儲,這樣一個ip只需要佔用4個字節就行了,這時1億個ip佔用的空間是4 * 100000000 = 400000000Bytes = 380M,空間消耗降低了很多。

那還有沒有在不影響存取效率的前提下更加節省空間的辦法呢?

當然有

BitSet

32位無符號int型能表示的最大值是4294967295,所有的ip都在這個範圍內,我們可以用一個bit位來表示某個ip是否出現過,如果出現過,就把代表該ip的bit位置為1,那麼我們最多需要429496729個bit就可以表示所有的ip了。舉個例子比如10.0.0.1轉換成int是167772161,那麼把長度為4294967295的bit數組的第167772161個位置置為1即可,當有ip訪問時,只需要檢查該標誌位是否為1就行了。

4294967295bit = 536870912Byte = 512M。如果用hash表示所有4294967295範圍內的數組的話,需要十幾G的空間。

當然,這裡舉ip的例子不一定合適,主要目的是為了引出BitSet。

下面我們來看看BitSet具體怎樣實現。

首先,比如我們有一個長度=2的byte數組,2個字節一共有16位,可以表示0-15的數字是否存在。比如我們要驗證11是否出現過,那麼我們先檢查第11個位置是否為1,如果為0,說明11沒出現過,然後我們把第11位置為1,表示11已經出現過了

所以,BitSet基本只有兩個操作,set(int value) 和 isHas(int value)

set(int value)

我們先來看set怎麼實現,因為一個byte佔8位,所以對於一個給定的value,我們先求出該value應該位於哪個Byte上,這很簡單,int byteIndex = value / 8;

找到value在byte數組中的位置後,再就是在該字節中尋找表示value的bit位,我們知道,一個byte其實就是一個長為8的bit數組,那麼value在該bit數組中的位置也就很好算了,int bitIndex = value % 8;

最後我們把該bit位設置為1就可以了:byte[byteIndex] = byte[byteIndex] | 1 << ( 7 - bitIndex)

整個流程如下面所示:

public void set(int value){
int byteIndex = value / 8;
int bitIndex = value % 8;
byte[byteIndex] = byte[byteIndex] | 1 << (7 - bitIndex)
}

isHas(int value)

同樣的,isHas(int value)的推導過程和set(int value)差不多:

public boolean isHash(int value){
int byteIndex = value / 8;
int bitIndex = value % 8;
return byte[byteIndex] & 1 << (7 - bitIndex) > 0
}

BitSet的侷限性

想必有同學已經意識到了BitSet使用起來似乎並不總是那麼完美,BitSet有兩個比較侷限的地方:

當樣本分佈極度不均勻的時候,BitSet會造成很大空間上的浪費。

舉個例子,比如你有10個數,分別是1、2、3、4、5、6、7、8、99999999999;那麼你不得不用99999999999個bit位去實現你的BitSet,而這個BitSet的中間絕大多數位置都是0,並且永遠不會用到,這顯然是極度不划算的。

當元素不是整型的時候,BitSet就不適用了。

想想看,你拿到的是一堆url,然後如果你想用BitSet做去重的話,先得把url轉換成int型,在轉換的過程中難免某些url會計算出相同的int值,於是BitSet的準確性就會降低。

那針對這兩種情況有沒有解決辦法呢?

第一種分佈不均勻的情況可以通過hash函數,將元素都映射到一個區間範圍內,減少大段區間閒置造成的浪費,這很簡單,取模就好了,難的是取模之後的值保證不相同,即不發生hash衝突。

第二種情況,把字符串映射成整數是必要的,那麼唯一要做的就是保證我們的hash函數儘可能的減少hash衝突,一次不行我就多hash幾次,hash還是容易碰撞,那我就擴大數組的範圍,使hash值儘可能的均勻分佈,減少hash衝突的概率。

基於這種思想,BloomFilter誕生了。

BloomFilter

實現原理

BloomFiler又叫布隆過濾器,下面舉例說明BlooFilter的實現原理:

比如你有10個Url,你完全可以創建一長度是100bit的數組,然後對url分別用5個不同的hash函數進行hash,得到5個hash後的值,這5個值儘可能的保證均勻分佈在100個bit的範圍內。然後把5個hash值對應的bit位都置為1,判斷一個url是否已經存在時,一次看5個bit位是否為1就可以了,如果有任何一個不為1,那麼說明這個url不存在。這裡需要注意的是,如果對應的bit位值都為1,那麼也不能肯定這個url一定存在,這個是BloomFilter的特點之一,稍後再說。

核心思想

BloomFilter的核心思想有兩點:

多個hash,增大隨機性,減少hash碰撞的概率擴大數組範圍,使hash值均勻分佈,進一步減少hash碰撞的概率。

BloomFilter的準確性

儘管BloomFilter已經儘可能的減小hash碰撞的概率了,但是,並不能徹底消除,因此正如上面提到的:

如果對應的bit位值都為1,那麼也不能肯定這個url一定存在

也就是說,BloomFilter其實是存在一定的誤判的,這個誤判的概率顯然和數組的大小以及hash函數的個數以及每個hash函數本身的好壞有關,具體的計算公式,可以查閱相關論文,這裡只給出結果:

Wiki的Bloom Filter詞條有關於誤報的概率的詳細分析:Probability of false positives。從分析可以看出,誤判概率還是比較小的,空間利用率也很高。

BloomFilter的應用

黑名單

比如郵件黑名單過濾器,判斷郵件地址是否在黑名單中

排序(僅限於BitSet)

仔細想想,其實BitSet在set(int value)的時候,“順便”把value也給排序了。

網絡爬蟲

判斷某個URL是否已經被爬取過

K-V系統快速判斷某個key是否存在

典型的例子有Hbase,Hbase的每個Region中都包含一個BloomFilter,用於在查詢時快速判斷某個key在該region中是否存在,如果不存在,直接返回,節省掉後續的查詢。