淺談布隆過濾器在內(nèi)容管理系統(tǒng)中的應用

單劫++王純

摘要：內(nèi)容管理系統(tǒng)的內(nèi)容采集主要由爬蟲進行搜集，但內(nèi)容重復與否絕大多數(shù)情況下是根據(jù)內(nèi)容所在的頁面URI進行判定。作為一個完善的內(nèi)容管理系統(tǒng)，必須具備對已有內(nèi)容資源的識別功能。本文通過介紹布隆過濾器，并與傳統(tǒng)的判重方式進行對比，同時改進布隆過濾器并應用于內(nèi)容管理系統(tǒng)的資源判重的功能中，解決了內(nèi)存占用無限增加，查詢時間不斷增長，記錄內(nèi)容無法刪除等問題，實現(xiàn)了高效快速的資源判重。

關鍵詞：計算機工程；布隆過濾器；內(nèi)容管理系統(tǒng)；爬蟲；哈希

中圖分類號：TP399

文獻標識碼：A

DOI：10.3969/j.issn.1003-6970.2016.01.008

0 引言

Web信息的采集通常是利用網(wǎng)絡爬蟲等工具遍歷萬維網(wǎng)，它把萬維網(wǎng)看作一個以網(wǎng)頁為節(jié)點，網(wǎng)頁間鏈接為邊的超大規(guī)模有向圖，然后利用圖的遍歷算法對萬維網(wǎng)進行遍歷。在網(wǎng)絡遍歷的過程中.需要判斷待采集的頁面是否已經(jīng)采集過了，這就需要把已經(jīng)采集的網(wǎng)頁地址記錄下來，組成已采集網(wǎng)頁地址集合（記為：visited-set），當新的采集開始之前，首先判斷其地址是否在visited-set中，如在其中，表示網(wǎng)頁已經(jīng)采集，否則采集網(wǎng)頁，把網(wǎng)頁地址放在visited-set中，從而避免網(wǎng)頁的重復采集，浪費資源。為了實現(xiàn)集合中數(shù)據(jù)的快速查找，需要把URL映射為集合中的地址，這就需要設計一種高效且沖突率低的散列算法；同時由于萬維網(wǎng)上網(wǎng)頁數(shù)據(jù)的巨大，普通的Hash算法已經(jīng)不能滿足空間的要求，所以更需要一種節(jié)約空間的算法。

本文運用Bloom Filter設計了一種節(jié)省空間的大規(guī)模數(shù)據(jù)表示和查找方式，應用到內(nèi)容管理系統(tǒng)中，以應對海量信息采集中判重的需求，文中分析了布隆過濾器相對于HashMap的優(yōu)越之處，同時指出布隆過濾器的使用條件和弱點，并針對本系統(tǒng)的自身特點和需求，提出了一種針對過濾器的改進方案并予以實現(xiàn)，運用到該系統(tǒng)中。

1 布隆過濾器

1.1 概念

布隆過濾器是一種空間和時間效率很高的隨機訪問型數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組表示一個集合，并能判斷一個元素是否屬于這個集合。Bloom Filter看似簡潔，但這種高效是有一定代價的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合（false positive）。因此，BloomFilter不適合那些“零錯誤”的應用場合。而在能容忍低錯誤率的應用場合下，Bloom Filter通過極少的錯誤換取了存儲空間的極大節(jié)省，同時摒棄了沖突導致的一系列沖突處理。

1.2 集合表示和元素查詢

初始狀態(tài)時，Bloom Filter是一個包含m位的位數(shù)組，每一位都置為0。

為了表達S={xl，x2，…，xn}這樣一個n個元素的集合，Bloom Filter使用k個相互獨立的哈希函數(shù)（Hash Function），它們分別將集合中的每個元素映射到{1，…，m}的范圍中。對任意一個元素X，第i個哈希函數(shù)映射的位置hi （x）就會被置為1（1≤i≤k）。注意，如果一個位置多次被置為1，那么只有第一次會起作用，后面幾次將沒有任何效果。在圖2中，k=3，且有兩個哈希函數(shù)選中同一個位置（從左邊數(shù)第五位）。

在判斷v是否屬于這個集合時，我們對v應用k次哈希函數(shù)，如果所有hi （y）的位置都是1（1≤i≤k），那么我們就認為y是集合中的元素，否則就認為y不是集合中的元素。圖3中y1就不是集合中的元素。y2或者屬于這個集合，或者剛好是一個false positive。

2 布隆過濾器在內(nèi)容管理系統(tǒng)中的使用

內(nèi)容管理系統(tǒng)由若干部分構(gòu)成，其功能主要可以分為三大部分：來源、存儲和展示。其中，布隆過濾器主要應用在來源部分中的去重。

作為內(nèi)容管理系統(tǒng)，來源主要有兩個方面：爬蟲和手動上傳。對于絕大多數(shù)的數(shù)據(jù)搜集，都是通過爬蟲的自動化爬取獲得的。因此，在不經(jīng)過人為的干涉的情況下，如何能夠有效地抓取不同的內(nèi)容，防止重復內(nèi)容對空間和時間的浪費，才是過濾過程的關鍵所在。因此，為了能讓過濾器有的放矢，首先需要明確爬蟲的工作機理。下面對爬蟲的工作機制做一個簡單的介紹。

2.1 爬蟲工作流程

簡單來說，爬蟲可以歸結(jié)為一個生產(chǎn)者和消費者的問題。

在爬取內(nèi)容時經(jīng)歷了從“發(fā)現(xiàn)”到“爬取”的過程?！鞍l(fā)現(xiàn)”，即為對目標鏈接的獲取，目標來自于初始鏈接和內(nèi)容中存在的鏈接。一旦發(fā)現(xiàn)目標鏈接之后，就要將其放入待爬取的隊列中去，等待“爬取”功能的調(diào)用。那么，為了能夠快速的判斷哪些鏈接需要訪問，哪些已經(jīng)爬取過，最簡單的辦法就是，將已經(jīng)訪問過的鏈接（url）放入集合，在每次將新的鏈接放入隊列之前，首先與集合中的歷史信息相比對，若沒有，則放入隊列，否則丟棄。因此，歷史信息的比對模塊就應該放在生產(chǎn)者到隊列之間，提供過濾作用。最通用的方式即為HashMap進行歷史信息的存儲，但針對HashMap的不足之處，本文使用了BloomFilter進行了替換，下面針對HashMap的不足進行了說明。

2.2 HashMap

如圖5所示，HashMap的主體是由Entry[]構(gòu)成的，該數(shù)組中的每一個Entry節(jié)點都由Key和Value組成。HashMap通過key.hashcode計算所在entry對應在數(shù)組中的下標位置，如果遇到?jīng)_突，則以鏈表的形式儲存在鏈尾。

因此，hashMap首先需要存儲對象本身和它的key，其使用場景更趨向于，通過key去獲取對象本身，而不僅僅是判斷該對象是否存在，這樣就會在僅僅需要判斷對象是否存在的使用場景下造成極大的浪費，原因如下：

對象本身所需要的空間并不固定，有的對象很大，有的僅僅是基本類型，因此，該空間無法預估。

hashmap本身為了達到快速查找，在0（1）的時間復雜度獲取對象的目的，隨著對象的加入，需要不斷的擴容，這同時造成了時間和空間上的開銷，使得”增加歷史資源”的性能降低。

為了降低哈希的沖突率，hashmap本身會在資源總量的基礎上多預留一部分空間，從而造成浪費。

綜合以上HashMap的不足之處，結(jié)合“過濾及判重”功能的需求，布隆過濾器的優(yōu)勢非常突出：

1.不需要存儲對象本身，只需要知道該對象是否存在。

2.可以在0 （l）時間復雜度內(nèi)完成對對象存在性的判定。

3.在預估存儲目標的數(shù)量級后，可基本確定空間大小，不需動態(tài)調(diào)整。

但是，布隆過濾器也沒有做到十全十美，它依靠了錯誤率和冗余空間換取了高速度的查詢，相比于HashMap，加入了“錯誤率”這一概念，替換了“沖突”。下面分析BloomFilter的錯誤率情況，及所需位數(shù)組大小的判定條件。

2.3 錯誤率估計

Bloom Filter在判斷一個元素是否屬于它表示的集合時會有一定的錯誤率（false positive rate），不妨設：m為bit數(shù)組長度，n為集合元素個數(shù)，k為hash函數(shù)的個數(shù)和p為誤判概率。

假設kn

現(xiàn)在查詢一個不在集合中的元素，當它所對應的k個位置都為1時會發(fā)生誤判，這個概率p是：（（1-1/m）^kn）^k.既然Bloom Filter要靠多個哈希函數(shù)將集合映射到位數(shù)組中，如果哈希函數(shù)的個數(shù)多，那么在對一個不屬于集合的元素進行查詢時得到0的概率就大；但另一方面，如果哈希函數(shù)的個數(shù)少，那么位數(shù)組中的0就多。為了得到最優(yōu)的哈希函數(shù)個數(shù)，在給定m和n的情況下，當k取以下值時，誤判率p的值最小：k=（m/n） In2-0.7（m/n）此時誤判率p等于：Pmin=（1-1/2）^k=0.6185^（m/n）。換句話說，要想保持錯誤率低，最好讓位數(shù)組有一半還空著。

2.4 位數(shù)組的大小

在不超過一定錯誤率的情況下，設Bloom Filter至少需要m位才能表示全集中任意n個元素的集合。假設全集中共有u個元素，允許的最大錯誤率為e，下面我們來求位數(shù)組的位數(shù)m。

假設X為全集中任取n個元素的集合，F(xiàn)（X）是表示X的位數(shù)組。那么對于集合X中任意一個元素x，在s=F（X）中查詢x都能得到肯定的結(jié)果，即s能夠接受x。顯然，由于Bloom Filter引入了錯誤，s能夠接受的不僅僅是X中的元素，它還能夠e（u-n）個誤判（false positive）。因此，對于一個確定的位數(shù)組來說，它能夠接受總共n+e（u-n）個元素。在n+e（u-n）個元素中，s真正表示的只有其中n個，所以一個確定的位數(shù)組可以表示n+e（u-n）/n個集合。m位的位數(shù)組共有2m個不同的組合，進而可以推出，m位的位數(shù)組可以表示2^m（n+e（u-n）/n）個集合。全集中n個元素的集合總共有（u?。?（n！*（u_n）！），因此要讓m位的位數(shù)組能夠表示所有n個元素的集合，必須有（2^m）（n+e（u-n）/n）>（u?。?（n！*（u-n）?。?

綜上所述，我們得出結(jié)論：在錯誤率不大于e的情況下，m至少要等于n log2 （1/e）才能表示任意n個元素的集合。

上文中計算出，當k= In2- （m/n）時錯誤率f最小，這時f=（1/2） k=（1/2） mln2/n?，F(xiàn)在令f≤e，可以推出n《log2（1/e））/ln2）=nlog2elog2 （l/e）≤m

這個結(jié)果比之前計算的下界n log2 （l/e）大了log2（e）≈1.44倍。這說明在哈希函數(shù)的個數(shù)取到最優(yōu)時，要讓錯誤率不超過e，m至少需要取到最小值的1.44倍。

3 布隆過濾器的工程改進和實現(xiàn)

上面所述，布隆過濾器引入了錯誤率這一項，傳統(tǒng)的過濾器還有一個最大的缺陷，即：無法刪除已有的記錄。由于原生的布隆過濾器所引用的數(shù)組是bit數(shù)組（這也是它體積小的最大優(yōu)勢），因此，當hash散列之后，對應位只有0和1的區(qū)別。最終，即便多個對象被某個散列函數(shù)定位到同一個下標，值也只能標記為1，而不能累計。在這一點上，如果使用integer數(shù)據(jù)類型對比bit數(shù)據(jù)類型，則可以做到累計的效果，因此具備刪除的可行性，但是勢必會使得整個數(shù)組的體積增大，integer為32位，則整個數(shù)組將至少膨脹為原來的32倍。單從這一點上對過濾器的優(yōu)化不是很困難，只要存儲夠用即可。為了適用于內(nèi)容管理系統(tǒng)，為系統(tǒng)增加刪除資源的功能，因此過濾器選擇優(yōu)化方案即為將bit替換為integer類型。

在替換前，根據(jù)上述公式，取n為1000000個頁面鏈接，￡為0.01錯誤率，算得的最小空間是0.88M，不妨取IM（工程中采用1M），而替換后過濾器的總大小為32M，但很好的在原有誤判率的基礎上解決了刪除的問題。由于誤判的定性為：將不存在的對象判做有，因此對于存在的對象而言，是不可能判做沒有的，因此刪除的過程中不會存在錯誤?；谏鲜龅睦碚撏茖В瑢Ω倪M版的布隆過濾器具體實現(xiàn)參數(shù)如下：

public class BloomFilter{

private intm；

private intn；

private intk；

private Atomiclnteger count= new Atomicclnteger （0）：

int[] vector；

static final Charset charset=Charset.forName（“UTF-8”）：

static final String algorithmName=“MD5”；

）

重要參數(shù)分析說明：

整型變量m為vector的長度，也就是過濾器所能容納的最多的int整型個數(shù)，如果vector數(shù)組越大，在其他變量保持不變的情況下能夠減少過濾器的沖突率。

整型變量n，表示預期元素數(shù)量；m和n所代表的意義是不同的，需要區(qū)分開。n所代表的元素數(shù)量并不是指int數(shù)組的數(shù)量。由于課題需要對統(tǒng)一資源定位符（ur1）進行判重，因此n所代表的就是url的數(shù)量，即整個過濾器預期能夠在某個準確率內(nèi)的最大容納url的數(shù)值。

整型變量k，表示hash函數(shù)個數(shù)，即當一個url進行判重時，需要對該url的摘要進行hash散列的次數(shù)。由于過濾器需要根據(jù)hash散列的結(jié)果尋找對應位置的integer，進而判定是否重復，因此需要進行多次相互之間沒有關聯(lián)的hash散列求值，在一定的準確率內(nèi)，k擁有一個最優(yōu)解。

容器vector，即布隆過濾器的主要數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類型為Integer數(shù)組，每個元素為一個32位的int值，用于累計命中次數(shù)，擁有刪除的能力。

algorithmName參數(shù)限定了生成消息摘要的算法。JDK自帶使用MD5算法對字符串進行摘要加密的方法。該算法以5 12位分組來處理輸入的信息，且每一分組又被劃分為16個32位子分組，經(jīng)過了一系列的處理后，算法的輸出由四個32位分組組成，將這四個32位分組級聯(lián)后將生成一個128位散列值。BloomFilter會借助經(jīng)過k次散列得到的k個下標位置的相應值，判斷是否重復。若這k個位置上存在為0的計數(shù)，則認為該url沒有出現(xiàn)過，反之，若k個位置均不為0，意味著該url已經(jīng)重復。

系統(tǒng)使用集合規(guī)模為350000的int數(shù)組，且根據(jù)系統(tǒng)需求，誤判率為百分之一即可，經(jīng)測算所占空間約為20M，可完全滿足系統(tǒng)的空間要求，同時能夠確保判重順利正常的進行。根據(jù)以上對布隆過濾器的改造，需要實現(xiàn)的關鍵步驟是對目標對象進行散列求值，以下為生成Hash碼的具體實現(xiàn)，使用MD5生成摘要，然后進行k次hash獲得32位的int數(shù)組，數(shù)組中的每一個數(shù)字代表布隆過濾器的下標，然后再依次對k個下標中的int位進行比對，判斷是否存在重復url。以下為改進版布隆過濾器生成Hash摘要的主要實現(xiàn)部分：

public static int[] createHashes （byte[] data， int k）{

int[] result=new int[k]；

int curhsh=0；

byte salt=0；

while （curHash

byte[] digest；

synchronized （digestFunction）{

digestFunction.update （salt）；

salt++：

digest= digestFunction.digest （data）；

）

for （int i=0i

int h=0；

for（intj=（I*4）；j<（i*4_卜4）；j++）{

h<<=8；

hl=（（int） digest[j]） &OxFF；

）

result[curHash]=h；

curHash++；

）

）

return result；

）

其中，對于MD5生成的每一個digest值，由于保證了其128位的長度，因此可以統(tǒng)一對其進行每四個字節(jié)分割，再將獲得的四個字節(jié)首位連接起來，得到一個新的integer值，即為最終散列結(jié)果。結(jié)果返回長度為k的int數(shù)組，其中的每個元素都是散列結(jié)果。

4 結(jié)論

布隆過濾器在識別郵件黑名單、過濾重復資源的效率上有一定優(yōu)勢，同時因其同等數(shù)量級下占用內(nèi)存小，查找效率高而獲得廣泛應用。尤其是在內(nèi)容管理系統(tǒng)中，使得過濾功能可以非常的高效而輕量，做到事半功倍。但是，如此高效便捷的工具使用也是有條件的，系統(tǒng)必須容忍一定概率的誤判。雖然改進版的布隆過濾器能夠提供刪除功能，但是代價為將原有空間增大了32倍。至于使用時，是選擇零錯誤率的Hash Map還是選擇高效的Bloom Filter，就要看工程的背景了。在本項目中，原生的布隆過濾器無法達到項目對已經(jīng)記錄在案的資源進行刪除的需求，因此對布隆過濾器進行了改造，使用int數(shù)組數(shù)據(jù)類型替換了原有的BitSet數(shù)據(jù)類型，并更改優(yōu)化了原有的基于bit的哈希散列值的生成方式，使得生成hash結(jié)果更高效。改進版布隆過濾器在本系統(tǒng)中得到了很好的應用。