單劫++王純

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

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

中圖分類號：TP399

文獻(xiàn)標(biāo)識碼：A

DOI：10.3969/j.issn.1003-6970.2016.01.008

0 引言

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

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

1 布隆過濾器

1.1 概念

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

1.2 集合表示和元素查詢

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

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

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

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

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

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

2.1 爬蟲工作流程

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

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

2.2 HashMap

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

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

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

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

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

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

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

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

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

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

2.3 錯(cuò)誤率估計(jì)

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

假設(shè)kn

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

2.4 位數(shù)組的大小

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

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

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

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

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

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

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

在替換前，根據(jù)上述公式，取n為1000000個(gè)頁面鏈接，￡為0.01錯(cuò)誤率，算得的最小空間是0.88M，不妨取IM（工程中采用1M），而替換后過濾器的總大小為32M，但很好的在原有誤判率的基礎(chǔ)上解決了刪除的問題。由于誤判的定性為：將不存在的對象判做有，因此對于存在的對象而言，是不可能判做沒有的，因此刪除的過程中不會存在錯(cuò)誤?；谏鲜龅睦碚撏茖?dǎo)，對改進(jìn)版的布隆過濾器具體實(shí)現(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整型個(gè)數(shù)，如果vector數(shù)組越大，在其他變量保持不變的情況下能夠減少過濾器的沖突率。

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

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

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

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

系統(tǒng)使用集合規(guī)模為350000的int數(shù)組，且根據(jù)系統(tǒng)需求，誤判率為百分之一即可，經(jīng)測算所占空間約為20M，可完全滿足系統(tǒng)的空間要求，同時(shí)能夠確保判重順利正常的進(jìn)行。根據(jù)以上對布隆過濾器的改造，需要實(shí)現(xiàn)的關(guān)鍵步驟是對目標(biāo)對象進(jìn)行散列求值，以下為生成Hash碼的具體實(shí)現(xiàn)，使用MD5生成摘要，然后進(jìn)行k次hash獲得32位的int數(shù)組，數(shù)組中的每一個(gè)數(shù)字代表布隆過濾器的下標(biāo)，然后再依次對k個(gè)下標(biāo)中的int位進(jìn)行比對，判斷是否存在重復(fù)url。以下為改進(jìn)版布隆過濾器生成Hash摘要的主要實(shí)現(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生成的每一個(gè)digest值，由于保證了其128位的長度，因此可以統(tǒng)一對其進(jìn)行每四個(gè)字節(jié)分割，再將獲得的四個(gè)字節(jié)首位連接起來，得到一個(gè)新的integer值，即為最終散列結(jié)果。結(jié)果返回長度為k的int數(shù)組，其中的每個(gè)元素都是散列結(jié)果。

4 結(jié)論

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