唐海娜，林小拉，韓春靜

(1.中山大學(xué) 信息科學(xué)與技術(shù)學(xué)院，廣東 廣州 510006；2.中國(guó)科學(xué)院 計(jì)算機(jī)網(wǎng)絡(luò)信息中心，北京 100190)

1 引言

近年來，伴隨著互聯(lián)網(wǎng)技術(shù)與應(yīng)用的迅猛發(fā)展，視頻分發(fā)、文件共享、網(wǎng)頁(yè)瀏覽、傳感器探測(cè)數(shù)據(jù)、娛樂游戲等網(wǎng)絡(luò)流量呈現(xiàn)持續(xù)高速增長(zhǎng)態(tài)勢(shì)。網(wǎng)絡(luò)數(shù)據(jù)流(data streaming)[1,2]是按時(shí)間遞增順序排列且具有相同屬性的數(shù)據(jù)分組序列，主要表現(xiàn)有實(shí)時(shí)性、連續(xù)性、單遍性、無(wú)限性等特征。目前，針對(duì)數(shù)據(jù)流的分析被日益廣泛地應(yīng)用于網(wǎng)絡(luò)安全監(jiān)測(cè)、負(fù)載均衡、緩存策略等領(lǐng)域。

研究發(fā)現(xiàn)，網(wǎng)絡(luò)數(shù)據(jù)流存在大量的冗余，如文獻(xiàn)[3]中研究了企業(yè)網(wǎng)主干鏈路流量組成，發(fā)現(xiàn)入方向存在約20%的數(shù)據(jù)冗余，出方向存在約50%的數(shù)據(jù)冗余。導(dǎo)致這一現(xiàn)象的原因有很多，如大量用戶訪問同樣的Web資源，或采用P2P交換視頻資源等。為了降低資源消耗，提高處理性能，目前數(shù)據(jù)流冗余消除技術(shù)已成為一個(gè)熱門的研究課題。數(shù)據(jù)流冗余消除是指通過單次遍歷從數(shù)據(jù)流無(wú)窮序列中識(shí)別出已出現(xiàn)過的數(shù)據(jù)對(duì)象并區(qū)別處理[4]。這一問題的研究有著廣泛的應(yīng)用價(jià)值，例如，網(wǎng)頁(yè)爬蟲中的去重問題[5]，互聯(lián)網(wǎng)廣告運(yùn)營(yíng)中的“惡意偽點(diǎn)擊”監(jiān)測(cè)問題[6]，以及電信話單中重復(fù)通話記錄消除[7]等。此外，在大規(guī)模分布式協(xié)作的網(wǎng)絡(luò)測(cè)量中，同一高速網(wǎng)絡(luò)的監(jiān)測(cè)由多個(gè)監(jiān)測(cè)探針共同完成，需要完成不同業(yè)務(wù)流監(jiān)測(cè)的任務(wù)分配管理，數(shù)據(jù)流冗余消除也是其中的關(guān)鍵技術(shù)[8～10]。

數(shù)據(jù)流冗余消除技術(shù)的研究中面臨如下問題與挑戰(zhàn)：首先，高數(shù)據(jù)分組傳輸速率與大并發(fā)數(shù)據(jù)流需要快速掃描，無(wú)法使用傳統(tǒng)的多遍掃描冗余檢測(cè)方法，必須通過單次遍歷實(shí)時(shí)監(jiān)測(cè)數(shù)據(jù)流冗余記錄。其次，由于數(shù)據(jù)流的無(wú)限性特征，不可能把所有歷史數(shù)據(jù)都保存在內(nèi)存中處理，一般取最近一段時(shí)間內(nèi)的數(shù)據(jù)對(duì)象作為數(shù)據(jù)流冗余消除的有效范圍，在有限的內(nèi)存空間中進(jìn)行近似計(jì)算。因此準(zhǔn)確性是數(shù)據(jù)流冗余消除算法的重要指標(biāo)。如何兼顧準(zhǔn)確性及處理性能是目前數(shù)據(jù)流冗余消除算法的研究重點(diǎn)。目前已有算法中，Stable Bloom filter[5]算法盡管可以實(shí)現(xiàn)O(n)的時(shí)間復(fù)雜度，但同時(shí)帶來假陽(yáng)性以及假陰性誤差。Decaying Bloom filter[11]算法在Stable Bloom filter算法的基礎(chǔ)上提升了準(zhǔn)確性，但它需要對(duì)Bloom filter結(jié)構(gòu)體的反復(fù)掃描，從而需要O(m·n)的查詢時(shí)間復(fù)雜度，無(wú)法滿足高速網(wǎng)絡(luò)環(huán)境海量數(shù)據(jù)的實(shí)時(shí)處理需求。如何在高速增長(zhǎng)的網(wǎng)絡(luò)環(huán)境下，設(shè)計(jì)準(zhǔn)確、實(shí)時(shí)的數(shù)據(jù)流冗余消除算法成為當(dāng)前學(xué)術(shù)界面臨的一大挑戰(zhàn)。

本文針對(duì)已有的數(shù)據(jù)流冗余消除算法時(shí)間復(fù)雜度高、誤判率高的問題，提出了一種基于移動(dòng)指針的數(shù)據(jù)流冗余消除算法——SKIP Bloom filter。它采用動(dòng)態(tài)指針在移動(dòng)區(qū)間中標(biāo)志當(dāng)前的計(jì)數(shù)值，并為每一條數(shù)據(jù)流分配一個(gè)當(dāng)前的計(jì)數(shù)標(biāo)記符，以此避免了對(duì)Bloom filter結(jié)構(gòu)的頻繁掃描，并保持了Bloom filter的準(zhǔn)確性。本文論證了算法具有O(n)的時(shí)間復(fù)雜度和O(1-(1- 1/(2m))w·k)k的假陽(yáng)性誤判率，與以往算法相比具有明顯的性能及準(zhǔn)確度優(yōu)勢(shì)。

2 相關(guān)工作

基于海量數(shù)據(jù)的數(shù)據(jù)流冗余消除算法設(shè)計(jì)具有極大的挑戰(zhàn)。最通常的方法采用Buffer存儲(chǔ)所有歷史數(shù)據(jù)[12]，通過逐行記錄比較得到精確計(jì)算結(jié)果。這種方法精度高，但需要大存儲(chǔ)開銷，處理效率低，在實(shí)際網(wǎng)絡(luò)環(huán)境中應(yīng)用困難。為提高處理性能，可以使用數(shù)據(jù)庫(kù)存儲(chǔ)的方式，通過基于散列的算法或基于排序的算法[13]進(jìn)行冗余消除，但一般需多次遍歷所有記錄，因此，隨著數(shù)據(jù)流不斷增長(zhǎng)，這些方法很難滿足高效查詢的需求。

BF(Bloom filter)[14]是一種允許存在一定誤判情況下存儲(chǔ)空間高效的散列結(jié)構(gòu)，它在查詢準(zhǔn)確率和存儲(chǔ)代價(jià)之間具有較好的折衷，目前被廣泛應(yīng)用于Web緩存、P2P網(wǎng)絡(luò)協(xié)作以及網(wǎng)絡(luò)測(cè)量等領(lǐng)域。BF對(duì)集合采用一個(gè)位串表示，既支持集合元素查詢，又能有效地過濾掉不屬于集合的元素。其算法結(jié)構(gòu)的實(shí)質(zhì)是將集合中的元素通過k個(gè)散列函數(shù)映射到位串向量中，來判斷一個(gè)元素是否已屬于某個(gè)集合。由于散列查找的常數(shù)時(shí)間和存儲(chǔ)空間開銷較小，BF算法具有很好的存取性能，因此近年來被研究人員應(yīng)用于數(shù)據(jù)流的冗余消除問題。

傳統(tǒng)BF基于靜態(tài)數(shù)據(jù)集設(shè)計(jì)，只支持插入與查詢操作。為了支持動(dòng)態(tài)數(shù)據(jù)集，文獻(xiàn)[15,16]等提出了Counting BF算法，它采用計(jì)數(shù)方式取代了原來的“0/1”存儲(chǔ)，可以支持對(duì)元素的刪除操作。Counting BF在應(yīng)用于數(shù)據(jù)流冗余消除問題時(shí)，可以存放時(shí)間計(jì)數(shù)(time-based)或元素計(jì)數(shù)(counterbased)，目前已經(jīng)提出的算法大部分是基于元素計(jì)數(shù)的方式。數(shù)據(jù)流冗余消除算法設(shè)計(jì)的關(guān)鍵問題是需實(shí)時(shí)刪除達(dá)到最大計(jì)數(shù)值的過期元素。由于數(shù)據(jù)流的單遍特性，Counting BF結(jié)構(gòu)在應(yīng)用于數(shù)據(jù)流冗余消除問題時(shí)缺乏刪除觸發(fā)條件。因此目前研究人員基于Counting BF，定義有效窗口區(qū)間，提出了一系列數(shù)據(jù)流冗余消除算法?；旧峡梢苑譃橐韵?類[6]。

1) 基準(zhǔn)窗口 (landmark window) 模式：基于時(shí)間或計(jì)數(shù)范圍把數(shù)據(jù)流分成若干段，每個(gè)段內(nèi)維護(hù)N個(gè)元素，段內(nèi)所有元素的到期時(shí)間相同。算法維持一個(gè)當(dāng)前段，當(dāng)計(jì)數(shù)到期時(shí)，自動(dòng)刪除當(dāng)前段，并繼續(xù)在下N個(gè)元素上處理。

2) 滑動(dòng)窗口 (sliding window) 模式：窗口保存最近的N個(gè)元素，每個(gè)新元素到來或舊元素過期都會(huì)更新窗口。由于sliding window中的元素都會(huì)依次到期，因此通常需要為每個(gè)元素維持一個(gè)序號(hào)以方便計(jì)算到期時(shí)間。

3) 跳躍窗口 (jumping window) 模式：最先在文獻(xiàn)[17]中被提出，介于landmark window與sliding window之間?；舅枷胧前岩粋€(gè)大的窗口切成若干子窗口，每個(gè)子窗口表示一個(gè)確定的時(shí)間段/計(jì)數(shù)范圍的數(shù)據(jù)。一旦所有子窗口滿，刪除最老的子窗口，并創(chuàng)建最新的子窗口。通過對(duì)子窗口的信息進(jìn)行綜合得到總體信息。

Metwally在文獻(xiàn)[6]中采用BF算法檢測(cè)點(diǎn)擊流(click stream)中的重復(fù)點(diǎn)擊問題，來判斷廣告點(diǎn)擊是來自人還是機(jī)器。論文主要針對(duì)landmark window模式采用原始BF結(jié)構(gòu)進(jìn)行冗余檢測(cè)，這種方法隨著數(shù)據(jù)流的無(wú)限增長(zhǎng)最終BF結(jié)構(gòu)會(huì)變“滿”(即所有位都為1)，因此不具備可操作性。Deng F與Rafiei D在文獻(xiàn)[5]中基于sliding window方式研究了數(shù)據(jù)流序列重復(fù)性近似檢測(cè)問題，提出了 stable BF算法，通過引入概率因子 p，把每次插入新數(shù)據(jù)時(shí)的輪詢更新范圍限制在p，并證明了算法可以維持BF的0元素比例在一個(gè)穩(wěn)定的范圍。但p因子的引入帶來假陽(yáng)性以及假陰性誤判率，同時(shí)加重了算法的復(fù)雜度。

文獻(xiàn)[11]提出了decaying BF (DBF)算法，每次插入新元素時(shí)需要掃描BF結(jié)構(gòu)體中所有非零元素并減1，因此單元素插入的時(shí)間復(fù)雜度是O(m)，其中m為BF結(jié)構(gòu)體長(zhǎng)度，這對(duì)于很多高速應(yīng)用是不可接受的。此外，還有Zhang等提出的timing BF算法[18,19]，BF結(jié)構(gòu)體中每個(gè)計(jì)數(shù)含bit，其中，w為窗口大小，c是一個(gè)常量。定義時(shí)間戳t的取值范圍為從0～w+c-1，并從中取w個(gè)連續(xù)的值，即(t-w+1)～t表示當(dāng)前窗口。每次新元素到來時(shí)只需檢查BF中m/c個(gè)位置以消除過期元素，經(jīng)c次后完成一輪對(duì)BF結(jié)構(gòu)體的完整掃描。Timing BF算法的核心思想是利用額外空間 c來提升處理性能，因此消耗了更多的內(nèi)存，同時(shí)單元素插入的時(shí)間復(fù)雜度仍為O(m/w)。

因此，目前已有算法主要采用滑動(dòng)窗口模式，算法的主要開銷在于需要實(shí)時(shí)監(jiān)測(cè)和刪除過期元素。如decay Bloom filter算法通過對(duì)BF結(jié)構(gòu)體中m個(gè)元素的全掃描實(shí)現(xiàn)過期元素的及時(shí)刪除，因而加大了算法的時(shí)間復(fù)雜度。而stable Bloom filter算法通過引入概率因子提升了處理性能，但帶來一定的假陰性誤差。本文針對(duì)已有的數(shù)據(jù)流冗余消除算法時(shí)間復(fù)雜度高/誤報(bào)率高的問題，提出了一種基于移動(dòng)指針的數(shù)據(jù)流冗余消除算法——SKIP BF。它采用動(dòng)態(tài)指針在移動(dòng)區(qū)間中標(biāo)志當(dāng)前的計(jì)數(shù)值，并為每一條數(shù)據(jù)流分配一個(gè)當(dāng)前的計(jì)數(shù)標(biāo)記符。SKIP BF算法引入雙BF結(jié)構(gòu)區(qū)分歷史數(shù)據(jù)與當(dāng)前數(shù)據(jù)，通過定期刪除歷史數(shù)據(jù)避免了對(duì)BF結(jié)構(gòu)的頻繁掃描，并保持了BF的準(zhǔn)確性。

3 數(shù)據(jù)流冗余消除算法設(shè)計(jì)與分析

3.1 問題定義

假定數(shù)據(jù)流可表示為SN=x1, x2,…, xN，N為數(shù)據(jù)流元素個(gè)數(shù)，并趨于無(wú)窮大。假定xi出現(xiàn)后，在w個(gè)計(jì)數(shù)范圍內(nèi)出現(xiàn)的元素被認(rèn)為是xi的重復(fù)元素。則數(shù)據(jù)流冗余消除問題相關(guān)定義如下。

定義 1 (數(shù)據(jù)流冗余消除)給定數(shù)據(jù)流無(wú)窮序列SN，假定w為數(shù)據(jù)流老化計(jì)數(shù)值。定義B為保存SN歷史元素及其計(jì)數(shù)序號(hào)的結(jié)構(gòu)體。數(shù)據(jù)流冗余消除問題可表示為：

任取 xi∈SN，假設(shè) xi∈{xi-w,xi-w+1,…, xi-1}，即該元素為冗余元素，則 Duplicate(xi) = true，調(diào)用Reject(xi)丟棄該元素，并更新B的狀態(tài)；否則調(diào)用do(xi)處理該元素，并向B中插入新的項(xiàng)xi。

定義 2 (錯(cuò)誤概率)給定數(shù)據(jù)流無(wú)窮序列 SN，假定w為數(shù)據(jù)流老化計(jì)數(shù)值。錯(cuò)誤概率的定義如下：

任取 xi∈SN，假設(shè) xi?{xi-w,xi-w+1,…,xi-1}，即該元素為非冗余元素，若算法計(jì)算Duplicate(xi) = true，則為假陽(yáng)性錯(cuò)誤。假設(shè) xi∈{xi-w,xi-w+1,…,xi-1}，即該元素為冗余元素，若算法計(jì)算 Duplicate(xi) =false，則為假陰性錯(cuò)誤。錯(cuò)誤概率記作?fe，稱為假陽(yáng)性錯(cuò)誤概率(false positive rate)或假陰性錯(cuò)誤概率(false negative rate)。

3.2 算法描述

本文提出的SKIP BF算法稱為基于移動(dòng)指針的BF 算法。為了避免sliding window模式需要實(shí)時(shí)掃描整個(gè)BF結(jié)構(gòu)體以刪除過期元素所帶來的性能開銷，SKIP BF算法設(shè)計(jì)采用前后 2個(gè)計(jì)數(shù)窗口的jumping window模式，同時(shí)提出了雙BF之間的輪流切換及定時(shí)刪除機(jī)制以加速對(duì)過期元素的處理，并以此實(shí)現(xiàn)了良好的算法準(zhǔn)確性。

SKIP BF算法定義2個(gè)BF結(jié)構(gòu)體，每個(gè)結(jié)構(gòu)體是由 m 個(gè)整數(shù)組成的數(shù)組，即 BFO[1,…,m]和BFN[1,…,m]。其中，BFO為old BF, BFN為new BF。定義散列函數(shù)h1, h2, …, hk為BF的散列映射。假定w為數(shù)據(jù)流老化計(jì)數(shù)值。則SKIP BF算法中，BFO代表前一區(qū)間即[1, w]范圍內(nèi)的計(jì)數(shù)映射，BFN代表后一區(qū)間即[w+1，2w]范圍內(nèi)的計(jì)數(shù)映射。BF結(jié)構(gòu)中m個(gè)整數(shù)為計(jì)數(shù)。設(shè)定數(shù)據(jù)流算法的動(dòng)態(tài)控制指針p，它具備有效計(jì)數(shù)區(qū)間[p-w，p]。p的最大值為2w，即計(jì)數(shù)的最大范圍，具體如圖1所示。

圖1 SKIP Bloom filter原理示意

SKIP Bloom filter算法可以表示如下：

Algorithm: SKIP Bloom filter算法

輸入：數(shù)據(jù)流無(wú)限序列S=S1,S2,…,SN, N?∞

輸出：為數(shù)據(jù)流中的每個(gè)元素輸出“Yes/No”，表示該元素是否在BF中有效存在

Begin

初始化BFO[1]…BFO[m]=0;

初始化BFN[1]…BFN[m]=0;

算法說明如下：SKIP BF算法把計(jì)數(shù)空間[1,2w]分成 2個(gè)區(qū)域，分別是[1,w]和[w+1,2w]。定義BFN為當(dāng)前工作區(qū)間，定義BFO為上一工作區(qū)間。對(duì)于每個(gè)要添加的元素，計(jì)算它的k個(gè)BF散列值，并更新到BFN中。在更新時(shí)，為了節(jié)省空間以及保持計(jì)算的連續(xù)性，指針p的取值固定在[1,w]。所以判斷新元素是否在最近 w個(gè)計(jì)數(shù)范圍出現(xiàn)過的方法為：判斷 BFN中對(duì)應(yīng) k個(gè)值是否都大于1，或者判斷BFO中對(duì)應(yīng)k個(gè)值是否都大于p。因此，SKIP BF可以重新表示為圖 2。

圖2 SKIP Bloom filter實(shí)際設(shè)計(jì)示意

當(dāng)p到達(dá)臨界值w時(shí)，表示BFO中的流已經(jīng)成為老化流。因此刪除BFO，并對(duì)換BFO與BFN，使 BFO繼續(xù)存放上一工作區(qū)間的數(shù)據(jù)流映射，并使用 BFN保存當(dāng)前工作區(qū)間的數(shù)據(jù)流映射。同時(shí)重新初始化p=1。

新數(shù)據(jù)插入：當(dāng)新元素xi需要插入時(shí)，算法基于2k次散列，得到該元素在BFO及BFN中的對(duì)應(yīng)值。對(duì)于每一新元素的2組對(duì)應(yīng)值，算法計(jì)算得到每組的最小值v=min(v1,v2,…,vk)。如果 BFN對(duì)應(yīng)的最小值 v=0，則該元素沒有在當(dāng)前工作區(qū)間出現(xiàn)過。如果BFO對(duì)應(yīng)的最小值 v＜p，則表示沒有在前一工作區(qū)間出現(xiàn)過。如果新元素xi既沒有在 BFO 中出現(xiàn)過，也沒有在BFN中出現(xiàn)過，則處理該新元素，否則丟棄該冗余元素。然后在BFN中為該數(shù)據(jù)流對(duì)應(yīng)的 k個(gè)位置設(shè)置成當(dāng)前的指針計(jì)數(shù)器，即 p。

舉例如下：在圖3中，設(shè)定數(shù)據(jù)流SN，BF分別為BFO以及BFN。每個(gè)BF的長(zhǎng)度為m(m=12)，對(duì)應(yīng)的散列個(gè)數(shù)k=4。設(shè)定計(jì)數(shù)臨界值為w=16。當(dāng)xi要插入時(shí)，p為8。4次散列后對(duì)應(yīng)的值分別是{5，3，3，8}以及{4，0，5，6}。明顯可以看出在當(dāng)前工作區(qū)間BFN未出現(xiàn)過該元素。在上一工作區(qū)間BFO對(duì)應(yīng)的最小值為3，小于當(dāng)前指針值 8，因此上一工作區(qū)間也未存在該元素的有效計(jì)數(shù)值，因此該元素未存在冗余，即在BFN中更新4個(gè)相應(yīng)的位置為8。

圖3 新數(shù)據(jù)插入處理示意

3.3 算法性能分析

SKIP BF算法把整個(gè)計(jì)數(shù)范圍以2w個(gè)計(jì)數(shù)分段為2個(gè)不同的區(qū)間，每個(gè)區(qū)間分別表示前半段的計(jì)數(shù)映射情況以及后半段的計(jì)數(shù)映射情況。每插入一個(gè)元素時(shí)，依次比較該元素是否在前半段中出現(xiàn)過，以及是否在后半段中出現(xiàn)過。算法的核心在于定期刪除前半段的計(jì)數(shù)，從而避免了對(duì)BF結(jié)構(gòu)的頻繁掃描，且保障了SKIP BF中記錄的一直為最近2w個(gè)計(jì)數(shù)范圍內(nèi)的映射情況。從SKIP BF算法描述上可以看出，每更新一個(gè)元素，需要2k次散列及k次賦值，因此，單元素插入需要3k次操作。由于k為常數(shù)，算法的時(shí)間復(fù)雜度可表示為O(n)。

當(dāng)集合S={x1,x2,…,xn}的所有元素都被k個(gè)散列函數(shù)映射到2個(gè)m長(zhǎng)度的位數(shù)組時(shí)，BFO和BFN中某一位在過去w個(gè)計(jì)數(shù)中被未訪問過的概率為：(1- 1/(2m))w·k，因此SKIP BF算法的假陽(yáng)性錯(cuò)誤概率為O(1-(1- 1/(2m))w·k)k。其中，m為BF的數(shù)組長(zhǎng)度，w為數(shù)據(jù)流老化計(jì)數(shù)值，k為散列個(gè)數(shù)。

如果某元素在過去w個(gè)計(jì)數(shù)中出現(xiàn)過，一定存在BFO中對(duì)應(yīng)指針計(jì)數(shù)器值大于p或者BFN中對(duì)應(yīng)指針計(jì)數(shù)器值大于0，也就是說SKIP BF不會(huì)返回不存在，因此算法的假陰性錯(cuò)誤概率為0。

基于對(duì)SKIP BF算法的性能分析，本文對(duì)比了已提出的幾個(gè)冗余消除算法，見表1。其中，n為數(shù)據(jù)流集合S={x1,x2,…,xn}的元素個(gè)數(shù)，m為BF結(jié)構(gòu)體的長(zhǎng)度，w或Max為BF結(jié)構(gòu)體的單元最大值，p為Stable BF算法中的特定因子。從表中可以看出，相對(duì)于其他算法，SKIP BF算法與stable BF算法具有更優(yōu)的時(shí)間復(fù)雜度，但stable BF因p引子的引入帶來假陰性誤判率。此外，在空間消耗上，SKIP BF的空間消耗約為stable BF以及decay BF的2倍，Timing BF算法的空間消耗則隨c值的選取而動(dòng)態(tài)變化。

表1 數(shù)據(jù)流冗余消除算法性能比較

4 實(shí)驗(yàn)驗(yàn)證

本文實(shí)現(xiàn)了SKIP BF算法、decay BF算法以及Buffer算法，算法的實(shí)現(xiàn)部分參考文獻(xiàn)[20]給出的代碼。Buffer算法沿用文獻(xiàn)[5]中的buffer方法，即在內(nèi)存中開辟一塊buffer, 存放目前w計(jì)數(shù)范圍內(nèi)的有效數(shù)據(jù)流。每新來一個(gè)元素，查找該元素有沒有在該buffer中存在，如果存在則冗余消除，否則加入該元素，并刪除buffer中w計(jì)數(shù)范圍之前的元素。為方便buffer中元素的增刪，該buffer采用指針管理。

實(shí)驗(yàn)基于中國(guó)科技網(wǎng)(China science and technology network) 實(shí)際網(wǎng)絡(luò)環(huán)境，從骨干路由器上收集netflow流數(shù)據(jù)進(jìn)行測(cè)試。實(shí)驗(yàn)分析的目標(biāo)是在數(shù)據(jù)源一定的情況下，分析驗(yàn)證SKIP BF算法和decay BF算法在m、k發(fā)生變化時(shí)對(duì)假陽(yáng)性誤判率的影響及相互的對(duì)比。其中，誤判率的比較以buffer算法作為準(zhǔn)確的冗余消除值，其他2個(gè)算法與該算法進(jìn)行比較得到最終的誤判率。實(shí)驗(yàn)分10次進(jìn)行，分別采集4h、8h、12h…40h的數(shù)據(jù)流。實(shí)驗(yàn)機(jī)器配置為3臺(tái)IBM 3650服務(wù)器，2.13GHz主頻的雙核4×CPU，內(nèi)存大小為24GB。

1) m動(dòng)態(tài)變化時(shí)誤判率分析

相對(duì)于buffer算法，SKIP BF算法以及decay BF算法會(huì)產(chǎn)生一定的假陽(yáng)性誤判。圖4給出在10次實(shí)驗(yàn)中，選取k=4，并動(dòng)態(tài)改變m(m取值分別為4 096，8 192，16 384，65 536)，得到的算法假陽(yáng)性誤判率的分析結(jié)果。從圖4可以看出，m增大時(shí)，SKIP BF算法及decay BF算法的假陽(yáng)性誤判率明顯降低，這是因?yàn)閙增大時(shí)，散列映射的沖突機(jī)率隨之降低。其中，SKIP BF算法誤判率下降的幅度更大。對(duì)于同樣的 m，Decay BF算法的假陽(yáng)性誤判率明顯高于SKIP BF算法，約為SKIP BF算法的2～12倍。

圖4 m變化時(shí)不同算法的假陽(yáng)性錯(cuò)誤概率

2) k動(dòng)態(tài)變化時(shí)誤判率分析

本實(shí)驗(yàn)驗(yàn)證選取m=8 192時(shí)，動(dòng)態(tài)改變k=4，k=8，k=12，k=16進(jìn)行比較，查看k動(dòng)態(tài)變化時(shí)兩算法的性能對(duì)比情況。從圖5可以看出，k=4時(shí)，2個(gè)算法具有更優(yōu)的假陽(yáng)性誤判率。在相同的 k值下， Decay BF算法的假陽(yáng)性誤判率明顯高于 SKIP BF算法，約為SKIP BF算法的3～11倍。但總體上，k對(duì)假陽(yáng)性誤判率的影響遠(yuǎn)遠(yuǎn)低于m變化時(shí)產(chǎn)生的影響。

圖5 k變化時(shí)不同算法的假陽(yáng)性錯(cuò)誤概率

5 結(jié)束語(yǔ)

隨著網(wǎng)絡(luò)的高速化發(fā)展，數(shù)據(jù)流冗余消除問題需要滿足實(shí)時(shí)性和高效性的需求。目前存在的stable BF算法以及decaying BF算法存在較高的更新開銷和假陽(yáng)性誤判等問題。本文提出了一種基于移動(dòng)指針的數(shù)據(jù)流冗余消除算法，其核心思想是：設(shè)計(jì) 2個(gè) BF，分別表示前半計(jì)數(shù)區(qū)間的有效計(jì)數(shù)元素以及后半計(jì)數(shù)區(qū)間的有效計(jì)數(shù)元素。定義動(dòng)態(tài)指針p來構(gòu)建當(dāng)前有效工作區(qū)間(p-w, p)。每插入一個(gè)元素，判斷其在當(dāng)前有效工作區(qū)間是否存在。算法最核心的設(shè)計(jì)是采用在區(qū)間邊界刪除前半段計(jì)數(shù)歷史的方式，以取代stable BF等算法對(duì)結(jié)構(gòu)的頻繁掃描，從而保證了算法的高效性和穩(wěn)定性。本文通過理論分析和實(shí)驗(yàn)驗(yàn)證證明了算法具有更優(yōu)的插入/查詢效率以及更優(yōu)的誤判率。SKIP BF算法是一種高效的數(shù)據(jù)結(jié)構(gòu)，可廣泛應(yīng)用于數(shù)據(jù)分組分類、網(wǎng)頁(yè)爬蟲去重以及流量監(jiān)測(cè)與分析等高速數(shù)據(jù)分組處理等場(chǎng)景。

基于本文的工作，可以進(jìn)一步研究如何優(yōu)化算法的空間存儲(chǔ)性能。當(dāng)前，針對(duì)BF結(jié)構(gòu)體的存儲(chǔ)壓縮技術(shù)研究[16,21,22]已有很多進(jìn)展，可以應(yīng)用到數(shù)據(jù)流冗余消除技術(shù)中。此外，結(jié)合多核處理器的并行算法研究[23,24]也是提升數(shù)據(jù)流冗余消除性能的另一方向。

[1] BABCOCK B, BABU S, DATAR M. Models and issues in data streams[A]. Proc of the 21st ACMSIGACT-SIGMOD-SIGART Symp on Principles of Database Systems[C]. Madison: ACM Press, 2002.1-16.

[2] 金澈清, 錢衛(wèi)寧, 周傲英. 流數(shù)據(jù)分析與管理綜述[J]. 軟件學(xué)報(bào),2004 , 15 (8) : 1172-1181.JIN C Q, QIAN W N, ZHOU A Y. Analysis and management of streaming data: a survey[J]. Journal of Software, 2004, 15 (8):1172-1181.

[3] ANAND A, MUTHUKRISHNAN C, AKELLA A. Redundancy in network traffic: findings and implications[A]. Proc of SIGMETRICS[C]. Seattle, WA, USA, 2009.37-48.

[4] WANG X, ZHANG Q, JIA Y. Efficiently filtering duplicates over distributed data streams[A]. International Conference on Computer Science and Software Engineering (CSSE)[C]. 2008. 631-634.

[5] F. DENG, D. RAFIEI. Approximately detecting duplicates for streaming data using stable bloom filters[A]. Proc 2006 ACM SIGMOD International Conference on Management of Data (SIGMOD) [C]. Chicago, Illinois, USA, 2006.25-36.

[6] METWALLY D, AGRAWAL A E. ABBADI. Duplicate detection in click streams[A]. Proc 14th International World Wide Web Conference (WWW)[C]. Chiba, Japan, 2005.12-21.

[7] V. GARG, A. NARANG, S. BHATTACHERJEE. Real-time memory efficient data redundancy removal algorithm[A]. CIKM[C]. 2010.1259-1268.

[8] SEKAR V, REiTER M K, WILLINGER W. CSAMP: a system for network-wide flow monitoring[A]. Proceedings of the 5th USENIX Sympo-sium on Networked Systems Design and Implementation.Berkeley[C]. CA, USA: USENIX Association, 2008. 233-246.

[9] SHARMA M, BYERS J. Scalable coordination techniques for distributed network monitoring[A]. Passive and Active Measurement Conference[C]. 2005. 349-352.

[10] COPPENS J, MARKATOS E, NOVOTNY J. Scampi - a scalable monitoring platform for the internet[A]. International Workshop on Inter-Domain Performance and Simulation(IPS)[C]. Budapest, Hungary, 2004.

[11] SHEN H, ZHANG Y. Improved approximate detection of duplicates for data streams over sliding windows[J]. Journal of Computer Science and Technology, 2008, 23(6): 973-987.

[12] GARCIA-MOLINA H, ULLMAN J D, WIDOM J. Database System Implementation[M]. Inc, Upper Saddle River, New Jersey, 2000.

[13] GRAEFE G, LINVILLE A, SHAPIRO L D. Sort vs. hash revisited[J].IEEE Transactions on Knowledge and Data Engineering, 1994,6(6):934-944.

[14] BURTON H B. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7): 422-426.

[15] FAN L, CAO P, ALMEIDA J, BRODER A Z. Summary cache: a scalable wide-area Web cache sharing protocol[J]. IEEE-ACM Trans on Networking, 2000,8(3):281-293.

[16] FLAVIO B, MICHAEL M, RINA P, et al. An improved construction for counting Bloom filters[A]. Proc of the 14th Conf on Annual European Symp[C]. Zurich: Springer-Verlag, 2006. 684-695.

[17] ZHU Y, SHASHA D. StatStream: statistical monitoring of thousands of data streams in real time[A]. Proceedings of the 28th ACM VLDB International Conference on Very Large Data Bases[C]. 2002.358-369.

[18] ZHANG L F, GUAN Y. Detecting click fraud in pay-per-click streams of online advertising networks[A]. Proc 28th IEEE International Conference on Distributed Computing Systems (ICDCS)[C]. Beijing,China, 2008. 77-84.

[19] LINFENG ZHANG. Effective Techniques for Detecting and Attributing Cyber Criminals[D]. Iowa State University, 2008.

[20] MATTHIAS VALLENTIN. LIBBF, a header-only C++11 library that implements various types of of Bloom filters [EB/OL]. http://matthias.vallentin.net/libbf/.

[21] MITZENMACHER M. Compressed bloom filters[J]. IEEE/ACM Transactions on Networking, 2002, 10(5): 604-612.

[22] FICARA D, GIORDANO S, PROCISSI G. Multilayer compressed counting bloom filters[A]. Proceedings of the 27th Conference on Computer Communications[C]. 2008.

[23] BHATTACHERJEE S, NARANG A, GARG V K. High throughput data redundancy removal algorithm with scalable performance[A]. Proceedings of the 6th International Conference on High Performance and Embedded Architectures and Compilers[C]. Heraklion, 2011. 87-96.

[24] GARG V, NARANG A, BHATTACHERJEE S. Real-time approximate range motif discovery & data redundancy removal algorithm[A].Proceedings of the 14th International Conference on Extending Database Technology[C]. Uppsala, Sweden, 2011. 485-496.