多維布隆算法在Redis指紋自動(dòng)過期中的應(yīng)用

賈小云 杜曉旭

(陜西科技大學(xué)電子信息與人工智能學(xué)院 陜西 西安 710021)

0 引 言

如果利用Scrapy-Redis框架進(jìn)行億級(jí)規(guī)模以上的數(shù)據(jù)爬取，且要滿足重復(fù)出現(xiàn)的指紋在一段時(shí)間內(nèi)二次遇到不采集、一段時(shí)間外二次遇到再采集的話，該框架本身是無法完成的。這不僅是因?yàn)榭蚣鼙旧碚加每臻g嚴(yán)重，還因?yàn)镽edis只能對(duì)去重集合設(shè)置過期時(shí)間，而不能對(duì)具體的某一指紋設(shè)置。如果對(duì)去重集合設(shè)置了過期時(shí)間，等過期后整個(gè)去重隊(duì)列都會(huì)被刪除，這顯然無法滿足我們的需求。因此，解決這些問題成為解決Scrapy-Redis指紋自動(dòng)過期難題的重點(diǎn)，也是本文研究內(nèi)容的關(guān)鍵。

1 Scrapy-Redis框架

單機(jī)模式的Scrapy框架是目前十分流行的爬蟲框架，其融合Redis組件后的Scrapy-Redis框架擺脫了單機(jī)的限制，能夠快速實(shí)現(xiàn)簡單分布式爬蟲的部署與運(yùn)行。Scrapy-Redis中有共用的數(shù)據(jù)庫用來存儲(chǔ)去重集合與請(qǐng)求隊(duì)列，并通過對(duì)它們的分享幫助分別部署在不同主機(jī)上的爬蟲程序協(xié)調(diào)工作。

Scrapy-Redis指紋是指把請(qǐng)求體、請(qǐng)求方式和請(qǐng)求URL通過MD5加密結(jié)合在一起，然后再利用32進(jìn)制轉(zhuǎn)義字符進(jìn)行轉(zhuǎn)義后生成的字符串。指紋放入Redis數(shù)據(jù)庫中作為請(qǐng)求的唯一標(biāo)識(shí)。

當(dāng)一個(gè)請(qǐng)求在Scrapy中被請(qǐng)求時(shí)，它會(huì)先在去重器中進(jìn)行校驗(yàn)，校驗(yàn)過程可以簡單概括如下：

Step1針對(duì)發(fā)起的請(qǐng)求，生成一個(gè)請(qǐng)求指紋。

Step2對(duì)該指紋是否已在指紋集合中進(jìn)行判斷。

Step3如果已經(jīng)存在，則舍棄它；如果不存在，則在指紋集合中添加該指紋并在請(qǐng)求隊(duì)列中添加該請(qǐng)求。

Scrapy-Redis為了實(shí)現(xiàn)爬蟲的分布式部署，通過連接Redis數(shù)據(jù)庫重寫了Scrapy的去重器。該數(shù)據(jù)庫可以存儲(chǔ)每個(gè)爬蟲的每個(gè)指紋并將其寫入同一個(gè)鍵中，以此實(shí)現(xiàn)共享功能。

利用Scrapy-Redis的這種去重機(jī)制，只要設(shè)置爬蟲不主動(dòng)清空去重集合，就可以實(shí)現(xiàn)采集過的信息不再二次采集。而且，通過對(duì)Redis設(shè)置過期時(shí)間也可以在過期時(shí)間后重新爬取先前采集過的所有信息。但在解決某采集過的特定信息隔上固定時(shí)間后再次進(jìn)行采集的問題上，Scrapy-Redis的去重機(jī)制卻無法滿足。

這是因?yàn)镽edis中設(shè)置過期時(shí)間只是針對(duì)去重集合的，而不能針對(duì)里面某一具體的指紋。Redis將所有指紋寫在同一個(gè)鍵中，當(dāng)為Redis的鍵設(shè)置過期時(shí)間后，一旦鍵過期，整個(gè)庫中的去重集合都會(huì)被刪除，這時(shí)所有過期時(shí)間前的去重隊(duì)列都會(huì)消失。

除此之外，因?yàn)橹讣y在Redis去重集合中的長度為40位的16進(jìn)制，而每個(gè)16進(jìn)制占用4 B空間，所以一億規(guī)模的指紋就要占用2 GB的空間。而這并不包括存儲(chǔ)請(qǐng)求種子到隊(duì)列中所占用的空間，也不包括多個(gè)爬蟲協(xié)調(diào)工作的情況，所以事實(shí)上爬蟲中Redis的空間占比會(huì)更加嚴(yán)重。

2 算法原理

為了讓Scrapy-Redis適應(yīng)億級(jí)規(guī)模爬取，本文使用Bloom算法。目前針對(duì)Bloom算法在爬蟲上的應(yīng)用研究很少，但也有一些對(duì)簡單Bloom算法在Scarapy-Redis的去重效率優(yōu)化方面的嘗試，這對(duì)本文研究起到了一定的啟發(fā)作用。在如何讓請(qǐng)求指紋自動(dòng)過期的問題上，可以通過使用Redis散列表保存指紋到其過期時(shí)間的映射，以及多維Bloom算法與Scrapy-Redis的對(duì)接兩種方法進(jìn)行實(shí)現(xiàn)。

2.1 Bloom算法

在判斷元素是否在一個(gè)集合內(nèi)時(shí)，鏈表、樹等數(shù)據(jù)結(jié)構(gòu)都采用將所有元素保存起來之后進(jìn)行對(duì)比的方式，但這種方式會(huì)隨著集合的擴(kuò)增占用更多的存儲(chǔ)空間和檢索速度。哈希函數(shù)可以將位數(shù)組上的某一位作為某一元素的映射，以便利用位數(shù)組上該位置的值來判斷該元素是否在判斷集合中存在，很大程度上彌補(bǔ)了鏈表、樹等結(jié)構(gòu)的缺陷。Bloom算法便是利用哈希表來判斷集合中是否存在某元素的，其過程如下：

聲明一個(gè)初始條件下每一位都為0且長度大小為m的位數(shù)組，其結(jié)構(gòu)如圖1所示。

圖1 Bloom過濾器位數(shù)組的初始設(shè)定

現(xiàn)假設(shè)有一個(gè)集合S，S={x1,x2,…，xn}，使用k個(gè)相互獨(dú)立且隨機(jī)的哈希函數(shù)將S集合中每一個(gè)元素映射在{1，2，…，m}這一數(shù)組范圍內(nèi)。在映射時(shí)，位數(shù)組中哈希函數(shù)的映射值相同的位置會(huì)被置1，且在多次映射的情況下只有第一次的置1為有效設(shè)定。

舉個(gè)例子，當(dāng)k取3的時(shí)候，假設(shè)元素x1經(jīng)過3個(gè)哈希函數(shù)映射的結(jié)果分別為1、4、8，而元素x2經(jīng)過3個(gè)哈希函數(shù)映射的結(jié)果為4、6、10。那么位數(shù)組上將被置為1的位置是1、4、8、6、10這五位，位數(shù)組相應(yīng)位置置1后的結(jié)構(gòu)如圖2所示。

圖2 x1與x2映射后位數(shù)組的置1結(jié)果

圖2中x1和x2成功加入了去重集合S中，此時(shí)如果要判斷其他元素是否存在于S集合內(nèi)，同樣需要用k個(gè)哈希函數(shù)求映射結(jié)果并判斷結(jié)果對(duì)應(yīng)的位數(shù)組位置是否都已為1，若已都為1，則該元素屬于集合S，否則，不屬于集合S?，F(xiàn)假設(shè)兩個(gè)新元素y1、y2的映射結(jié)果如圖3所示。

圖3 y1和y2的映射結(jié)果

由圖3可知y1對(duì)應(yīng)位置有0，因此y1不屬于S集合，y2對(duì)應(yīng)位置全部為1，應(yīng)該屬于S集合。但這只是原則上的判斷結(jié)果，事實(shí)上，Bloom算法雖然在不屬于去重集合的元素的判斷上能夠保證百分之百的正確率，但對(duì)屬于該集合的元素的判斷卻存在一定的誤判率。

對(duì)于Bloom算法的誤判率，仍然假設(shè)存在k個(gè)相互獨(dú)立且隨機(jī)的哈希函數(shù)，存在已有n個(gè)元素的待對(duì)比集合以及長度為m的位數(shù)組，且k、m和n之間滿足kn

(1)

式中：1/m為k個(gè)哈希函數(shù)中有任意一個(gè)選中位數(shù)組上該位置的概率，顯然1-1/m就代表k個(gè)哈希函數(shù)都未選中這一位置的概率。

該位置在經(jīng)過k次哈希映射后仍然沒有被置為1的概率為：

(2)

對(duì)于集合S={x1,x2,…，xn}，需要做kn次散列運(yùn)算才能將其所含元素全部映射到位數(shù)組中，此時(shí)位數(shù)組的該位置仍然沒有被置為1的概率為：

(3)

經(jīng)過kn次散列運(yùn)算后，位數(shù)組中某一位置成功被置為1的概率則為：

(4)

當(dāng)某元素經(jīng)k次哈希映射后所得結(jié)果對(duì)應(yīng)的位數(shù)組內(nèi)位置全部為1時(shí)，會(huì)將該元素判定為屬于集合S。因此，不在集合中的元素被檢測(cè)為已存在于該集合的誤判概率為：

(5)

由式(5)可以看出，在n和m確定的情況下，最小誤判率可以通過最優(yōu)的k獲得。而最優(yōu)哈希函數(shù)個(gè)數(shù)的獲取公式如下：

(6)

顯然，誤判率與m/n的值以及k的值有關(guān)。當(dāng)m/n保持不變時(shí)，k值越靠近Ki越能保證判斷的準(zhǔn)確性；而當(dāng)k值保持不變的時(shí)候，m/n的值越大越能保證判斷的正確性。雖然整體而言存在誤判率，但由于誤判率可以調(diào)節(jié)且很小，所以相較于其在空間占比和時(shí)間效率方面的優(yōu)勢(shì)，Bloom算法在能夠容許誤判的情況下是不錯(cuò)的選擇。

2.2 多維Bloom算法

多維Bloom算法由多個(gè)基本Bloom過濾器組成，且多個(gè)基本過濾器具有相同元素維數(shù)的位數(shù)組空間。每個(gè)基本過濾器負(fù)載待對(duì)比元素在某一維上的屬性，進(jìn)行對(duì)比判斷時(shí)，需要對(duì)元素在每一維上的映射是否都存在于各自對(duì)應(yīng)的過濾器位向量上進(jìn)行判斷，并最終給出元素是否已存在于集合中的判定結(jié)果。

將多維Bloom算法的維數(shù)設(shè)為L，則其誤判概率為：

(7)

由式(1)可知，多維Bloom算法的誤判概率與其維數(shù)大小成負(fù)相關(guān)，當(dāng)k、m和n一致的時(shí)候，誤判率隨維數(shù)的增加而減小。且多維過濾器的誤判率始終低于基本過濾器的誤判率，是其每一維過濾器誤判率的乘積。

在解決實(shí)際問題時(shí)需要使用按時(shí)間排列的多個(gè)Bloom過濾器。首先，根據(jù)需求決定時(shí)間序列的粒度，然后在該粒度下選擇相應(yīng)的要使用的Bloom過濾器的數(shù)量。例如，當(dāng)去重周期為7天時(shí)，比較合適的時(shí)間粒度為“天”，過濾器數(shù)量為7；當(dāng)去重周期為7個(gè)月，比較合適的時(shí)間粒度為“月”，過濾器數(shù)量同樣為7；當(dāng)去重周期為一個(gè)月時(shí)，可以選擇時(shí)間粒度為“天”也可以選擇時(shí)間粒度為“月”，相應(yīng)的過濾器數(shù)量為30和1。

在創(chuàng)建Bloom過濾器列表時(shí)，不會(huì)對(duì)數(shù)據(jù)庫中原有的數(shù)據(jù)產(chǎn)生影響。若Redis中已存在該鍵，會(huì)創(chuàng)建過濾器列表的Python對(duì)象并連接到Redis對(duì)應(yīng)的鍵上；如果不存在，創(chuàng)建該鍵后再創(chuàng)建對(duì)象并連接到對(duì)應(yīng)鍵上。當(dāng)然，創(chuàng)建Python對(duì)象時(shí)也會(huì)聲明每個(gè)鍵的過期時(shí)間。比如，當(dāng)粒度為“天”、過濾器數(shù)量為7、今天是2019年6月3日時(shí)，列表的結(jié)構(gòu)如表1所示。

表1 創(chuàng)建Bloom過濾器列表的舉例

采用這種方法，當(dāng)去重周期到后，對(duì)應(yīng)Bloom過濾器里的內(nèi)容會(huì)被自動(dòng)清空，不再需要手動(dòng)刪除以釋放內(nèi)存，也不會(huì)影響其他時(shí)間的過濾器。

每當(dāng)有新請(qǐng)求需要發(fā)出時(shí)，首先要生成當(dāng)前時(shí)間有效的過濾器列表，然后對(duì)過濾器列表中的每一個(gè)過濾器進(jìn)行對(duì)比判斷，只有全部過濾器都不包含此請(qǐng)求時(shí)，才能說明該請(qǐng)求沒有在有效期內(nèi)進(jìn)行請(qǐng)求過，才能夠?qū)⑵浞湃胝?qǐng)求隊(duì)列等待請(qǐng)求，并將該指紋存入當(dāng)前時(shí)間對(duì)應(yīng)的過濾器中。

2.3 Redis散列表設(shè)置指紋過期

Redis中存在散列表數(shù)據(jù)結(jié)構(gòu)，它保存了鍵到值的映射，因此可以利用它進(jìn)行請(qǐng)求指紋的自動(dòng)過期設(shè)置。步驟如下：

Step1因?yàn)镽edis的去重集合中只保存了指紋，所以為了保存從該指紋到其過期時(shí)間的映射，需要先將去重?cái)?shù)據(jù)的集合結(jié)構(gòu)轉(zhuǎn)換為哈希表結(jié)構(gòu)。

Step2判斷每一個(gè)需要發(fā)起的請(qǐng)求是否在哈希表中存在。

Step3當(dāng)該請(qǐng)求存在于哈希表中時(shí)，對(duì)比當(dāng)前時(shí)間和已存在指紋的過期時(shí)間。如果當(dāng)前時(shí)間大于過期時(shí)間，需要更新指紋的過期時(shí)間并將請(qǐng)求種子放入請(qǐng)求隊(duì)列；反之，則說明該請(qǐng)求在有效期內(nèi)已經(jīng)被處理過，可以放棄訪問。

Step4當(dāng)該請(qǐng)求不存在于哈希表中時(shí)，將請(qǐng)求種子加入請(qǐng)求隊(duì)列，將指紋和過期時(shí)間寫入哈希表中。

需要注意的是，該算法在實(shí)現(xiàn)時(shí)需要在Scrapy-Redis的settings中設(shè)置過期時(shí)間，同時(shí)通過from_crawler方法進(jìn)行獲取。

使用這種方法來實(shí)現(xiàn)請(qǐng)求指紋的自動(dòng)過期雖然簡單靈活，也可以指定任意的過期時(shí)間，且保證相同的請(qǐng)求兩次進(jìn)行采集的時(shí)間間隔必定不小于指定的時(shí)間，但該方法存在很大的缺陷：其一，使用該方法后無法使用Bloom算法壓縮內(nèi)存；其二，如果有URL在第一次被請(qǐng)求后再也沒有被請(qǐng)求或很長時(shí)間內(nèi)再?zèng)]有被請(qǐng)求，那么始終緩存在Redis中的這些請(qǐng)求指紋會(huì)逐漸堆積造成巨大的空間消耗。要處理這些占用空間的指紋需要額外編寫腳本，這就代表不能直接依賴框架的去重機(jī)制來設(shè)置指紋，自然會(huì)消耗更多的計(jì)算和存儲(chǔ)資源。

3 重構(gòu)Scripy-Redis框架

所有針對(duì)Scrapy-Redis框架的重構(gòu)過程，不會(huì)影響到框架的其他功能，更不會(huì)對(duì)其進(jìn)行破壞。同時(shí)，多維Bloom過濾器中位數(shù)組的實(shí)現(xiàn)和維護(hù)需要依賴Redis數(shù)據(jù)庫，所以改造Redis數(shù)據(jù)庫是對(duì)框架進(jìn)行改造的基礎(chǔ)。

3.1 多維Bloom算法的實(shí)現(xiàn)

(1) 算法流程圖。該算法實(shí)現(xiàn)過程如圖4所示。

圖4 實(shí)現(xiàn)Redis指紋自動(dòng)識(shí)別的算法流程圖

(2) 獲取時(shí)間粒度、設(shè)置Bloom過濾器個(gè)數(shù)，并初始化過濾器。選擇時(shí)間粒度及設(shè)置過濾器個(gè)數(shù)的方法在2.2節(jié)中已有介紹。對(duì)每個(gè)過濾器key(鍵)的過期時(shí)間的設(shè)定，可以在settings中設(shè)置然后通過from_crawler方法獲得，也可以在下一步“初始化過濾器”中進(jìn)行設(shè)置。

初始化過濾器時(shí)，因?yàn)楦鱾€(gè)過濾器之間是獨(dú)立的，所以主要設(shè)置的參數(shù)如下：需要的總bit位數(shù)、需要最少的哈希次數(shù)、需要多少M(fèi)B內(nèi)存、需要多少個(gè)512 MB的內(nèi)存塊(指紋的第一個(gè)字符必須為ASCII碼，最多有256個(gè)內(nèi)存塊)，以及seed值的選擇、key的獲取、最大指紋量和位數(shù)組長度的設(shè)置等。

關(guān)于總的bit位數(shù)和需要的最少哈希次數(shù)，因?yàn)橐幚韮|級(jí)之上的數(shù)據(jù)去重，所以指紋量n的值為1億以上，此時(shí)哈希函數(shù)個(gè)數(shù)k的取值可以為10左右，這樣位數(shù)組長度m至少要在10億以上，因?yàn)閿?shù)值較大，所以采用左移的位操作來實(shí)現(xiàn)，左移的位數(shù)設(shè)為bit。假設(shè)bit=30，就有m為1<<30，因?yàn)?<<30=1 073 741 824=230=128 MB，此時(shí)再設(shè)k取6，則能夠處理的最大指紋量為230/k=178 956 970個(gè)。

在seed值的選擇上為每個(gè)過濾器內(nèi)置了100個(gè)隨機(jī)種子；在能夠處理的最大指紋量上，本文在初次編碼中將其設(shè)為1億，而位數(shù)組長度設(shè)為了231-1。

(3) 生成周期內(nèi)有效的過濾器key列表。在生成針對(duì)當(dāng)前時(shí)間的有效周期內(nèi)過濾器key列表時(shí)，定義了get_bloomfilter_keys()方法，該方法能夠根據(jù)當(dāng)前時(shí)間、時(shí)間粒度和過濾器個(gè)數(shù)來返回有效的過濾器key列表。例如，假設(shè)當(dāng)前時(shí)間為20190508，filter_granularity=′d′，filter_num=7，則返回的列表為[′xxx:20190502′,′xxx:20190503′,...,′xxx:20190508′]，其中，′xxx′代表RFPDupeFilter的key。另外，在實(shí)現(xiàn)過濾器“判斷指紋是否存在于當(dāng)前key對(duì)應(yīng)的過濾器中”時(shí)，定義了一個(gè)exists()方法。在該方法中，為了應(yīng)對(duì)日期的變化，像從20190508到20190509的過渡之類的，需要每次都重新計(jì)算當(dāng)前有效的過濾器的鍵名列表，然后再進(jìn)行判斷和處理。

(4) 判斷指紋是否在key對(duì)應(yīng)的過濾器中。需要實(shí)現(xiàn)一個(gè)關(guān)鍵方法：判定指紋是否重復(fù)的exists()方法。部分代碼如下：

if not value:

return False

exist=1

for map in self.maps:

offset=map.hash(value)

exist=exist & self.server.getbit(self.key,offset)

return exist

value為待判斷的元素即一個(gè)新到來的指紋，定義變量exist為1后，將其與每一個(gè)哈希函數(shù)對(duì)value進(jìn)行哈希運(yùn)算后得到的映射結(jié)果進(jìn)行循環(huán)與運(yùn)算，利用Redis中g(shù)etbit()方法取每一次映射結(jié)果對(duì)應(yīng)位置的值。若每一次取到的值都為1，則結(jié)果為True，表示value在集合內(nèi)已存在；相反，只要getbit()的結(jié)果有一次為0，則結(jié)果為False，表示value不在集合內(nèi)。

另外，由于在實(shí)現(xiàn)多維Bloom過濾器時(shí)使用到的key和server是可變的，所以不同于單個(gè)的基本過濾器的實(shí)現(xiàn)，這里的exists()方法在傳參時(shí)需要將key和server也一并傳入。

(5) 將指紋寫入當(dāng)前時(shí)間的過濾器。同樣需要實(shí)現(xiàn)另一個(gè)關(guān)鍵方法：添加指紋到集合中去的insert()方法。部分代碼如下：

for f in self.maps:

offset=f.hash(value)

self.server.setbit(self.key,offset,1)

insert()方法同樣遍歷調(diào)用哈希函數(shù)以對(duì)元素進(jìn)行運(yùn)算并得到映射位置，然后利用Redis的setbit()方法將其位置置為1。同時(shí)，該方法的傳參相較于簡單的Bloom過濾器同樣多了server和key。

3.2 多維Bloom與Scrapy-Redis的對(duì)接

要完成已經(jīng)實(shí)現(xiàn)的多維Bloom算法與Scrapy-Redis的對(duì)接，還需要繼續(xù)修改框架內(nèi)源碼，同時(shí)將它的組件Dupefilter去重類替換為多維Bloom過濾器的邏輯。替換過程主要通過更改RFPDupeFilter類中的request_seen()來實(shí)現(xiàn)：

def request_seen(self,request):

fp=self.request_fingerprint(request)

if self.bf.exists(fp):

return True

else:

self.bf.insert(fp)

return False

獲取請(qǐng)求指紋的方法是request_fingerprint()方法，判斷該指紋是否已在任意過濾器的key中存在的方法是exists()方法。如果任何一個(gè)過濾器顯示存在，則說明該Request是重復(fù)的，返回True，不再訪問該請(qǐng)求。相反，如果全部過濾器顯示不存在，則返回False并調(diào)用insert()方法添加指紋到當(dāng)前過濾器，添加請(qǐng)求到請(qǐng)求隊(duì)列。

重構(gòu)后框架和Scrapy-Redis具有相似的使用方法，但還有幾個(gè)關(guān)鍵的參數(shù)需要配置。

使用時(shí)需要替換掉DUPEFILTER_CLASS后使用，可以將其設(shè)置為：DUPEFILTER_CLASS="scrapy_redis_bloomfilter.dupefilter.RFPDupeFilter"。

在初次代碼編寫中設(shè)置了最大指紋處理量為1億，位數(shù)組選擇了231-1，但在實(shí)際運(yùn)用中，可以根據(jù)自己的需要在初始化過濾器時(shí)配置預(yù)處理的指紋量(capacity)、左移位數(shù)(bit)等參數(shù)。

同時(shí)為了控制誤判率，在設(shè)置bit參數(shù)時(shí)，可以引入error_rate變量來表示誤判率，然后使用math.ceil(capacity*math.log2(math.e)*math.log2(1/error_rate))來計(jì)算需要的總bit位數(shù)。這樣，根據(jù)不同誤判率的要求設(shè)置不同的誤判率參數(shù)就可以獲得不同的左移位數(shù)，但會(huì)影響到指紋自動(dòng)過期的空間占用問題。

4 測(cè) 試

首先測(cè)試多維Bloom過濾器能否正確使用，因?yàn)樵谔幚韮|級(jí)規(guī)模指紋存儲(chǔ)時(shí)難以尋找誤判的URL，因此，此部分利用每小時(shí)爬取100個(gè)URL的方法對(duì)過濾器的功能進(jìn)行了測(cè)試。將時(shí)間粒度設(shè)為小時(shí)，并以兩個(gè)小時(shí)為過期時(shí)間創(chuàng)建兩個(gè)Bloom過濾器，編寫爬蟲程序分別在相應(yīng)的時(shí)間訪問“https://www.baidu.com/s?wd=”并抓取100篇新聞的URL。結(jié)果顯示，第一小時(shí)與第二小時(shí)內(nèi)所存儲(chǔ)的指紋中無重合，第三小時(shí)與第一小時(shí)的指紋有重合而與第二小時(shí)的指紋無重合，第四小時(shí)的指紋與前兩小時(shí)的指紋都有重合而與第三小時(shí)的指紋無重合，由此可知重構(gòu)后的框架可以實(shí)現(xiàn)指紋的自動(dòng)過期功能。

在此基礎(chǔ)上可以分析重構(gòu)后框架在實(shí)現(xiàn)指紋自動(dòng)過期時(shí)的誤判率。編寫爬蟲程序，分三天爬取某博客網(wǎng)站的博文，三天內(nèi)再次遇到某博文不進(jìn)行訪問和指紋的存儲(chǔ)，三天后再遇到該博文進(jìn)行訪問并存儲(chǔ)指紋。根據(jù)需求顯然可知過期周期為3，因此將時(shí)間粒度選為天，需要?jiǎng)?chuàng)建3維Bloom過濾器，每個(gè)過濾器設(shè)置各自對(duì)應(yīng)的key為20190603-20190605、過期時(shí)間分別為20190606-20190608。此外為了適應(yīng)抓取規(guī)模、便于實(shí)驗(yàn)測(cè)試，每個(gè)過濾器的哈希函數(shù)個(gè)數(shù)k統(tǒng)一設(shè)置為6。此時(shí)根據(jù)抓取的數(shù)據(jù)量的不同，可以計(jì)算出最優(yōu)的位數(shù)組長度，即最優(yōu)的左移位數(shù)。表2為不同數(shù)據(jù)量需求下最佳左移位數(shù)及其最低誤判率的展示。

表2 k固定時(shí)最佳左移位數(shù)及誤判率

由表2可以看出，即使是在k固定的情況下，重構(gòu)后框架的誤判率也可以滿足低于萬分之一的條件，更不用說在最優(yōu)k和最優(yōu)m/n值之下了。

除了誤判率外，另一項(xiàng)需要關(guān)注的點(diǎn)是重構(gòu)后框架所占用空間。實(shí)驗(yàn)部署在內(nèi)存總大小為175 GB的服務(wù)器上，虛擬機(jī)選用Centos7，分別以每天1億爬取量和每天2億爬取量的需求設(shè)置爬蟲，所以三天內(nèi)最高指紋存儲(chǔ)需求可以達(dá)到6億。通過對(duì)比使用Redis和使用重構(gòu)后框架存儲(chǔ)不同量指紋時(shí)所占用的空間，得到結(jié)果如圖5所示。

圖5 兩種方式下的空間占用情況

Redis的占用空間既包括指紋所占空間也包括請(qǐng)求種子所占用的空間，重構(gòu)后框架的占用空間為依據(jù)表2在k值固定情況下選擇最優(yōu)左移數(shù)之后，多維過濾器所開辟的位數(shù)組的總空間。綜上可以看出，重構(gòu)后的框架可以在極低的誤判率下實(shí)現(xiàn)指紋的自動(dòng)過期，且大大節(jié)省所需空間。

5 結(jié) 語

本文采用了多維Bloom算法對(duì)分布式爬蟲所用的Scrapy-Redis框架進(jìn)行了重構(gòu)，將實(shí)現(xiàn)后的攜帶當(dāng)前時(shí)間及過期時(shí)間信息的多維Bloom過濾器替換掉原框架內(nèi)的去重類，從而達(dá)到了Redis鍵內(nèi)所存指紋自動(dòng)過期的要求。該方法可以用于類似“過期時(shí)間內(nèi)再次遇到某URL不訪問不存儲(chǔ)，過期時(shí)間后再次遇到該URL訪問并存儲(chǔ)”的場(chǎng)景，且能夠在誤判率低于萬分之一的情況下，大大縮減指紋存儲(chǔ)所占用的空間。