賈文鋼，高錦濤

(1.內蒙古工業(yè)大學信息工程學院，內蒙古 呼和浩特 010051；2.內蒙古特種設備檢驗院，內蒙古 呼和浩特 010051)

1 引言

大數(shù)據(jù)時代以來，計算機技術與信息處理技術快速發(fā)展。很多行業(yè)領域都將其相關信息存儲在計算機系統(tǒng)中，從而形成海量日志數(shù)據(jù)。雖然存儲設備在不斷更新、容量不斷增大，但仍然難以滿足數(shù)據(jù)量增長的需要，導致大量的數(shù)據(jù)冗余點出現(xiàn)[1-2]。因此，高效、準確地濾除數(shù)據(jù)量爆發(fā)增長而出現(xiàn)的冗余點，減輕數(shù)據(jù)存儲開銷的負擔成為相關領域的研究熱點。

朱超平[3]等人提出基于智能優(yōu)化算法的數(shù)據(jù)冗余點消除算法。首先采用多個節(jié)點采集檢測對象狀態(tài)數(shù)據(jù)，并對每個節(jié)點采集的數(shù)據(jù)進行噪聲點過濾，減少數(shù)據(jù)規(guī)模。然后引入聚類分析算法處理簇首數(shù)據(jù)，消除數(shù)據(jù)間的冗余點。但該算法僅對冗余點進行了特征提取，導致冗余點特征不夠突出，濾除時準確率較低。許愛東[4]等人提出了一種基于動態(tài)時間規(guī)整的數(shù)據(jù)去重算法，該算法通過計算數(shù)據(jù)之間的相似性，從而達到數(shù)據(jù)冗余點濾除的目的。但該算法對冗余點濾除前，未利用線性頻譜法將獲取到的數(shù)據(jù)冗余點特征進行分類處理，導致冗余點濾除時間過長，效率較差。為了解決上述傳統(tǒng)算法存在的不足，本研究提出了基于HDFS的海量日志數(shù)據(jù)冗余點過濾算法。

2 冗余點特征提取與分類處理

HDFS(Hadoop分布式文件系統(tǒng))是將Hadoop平臺中的數(shù)據(jù)進行分類、提取、存儲的分布式文件系統(tǒng)[5-6]。因其具有高容錯性，所以對設備的硬件配置沒有過高要求，能夠對系統(tǒng)中大部分的錯誤數(shù)據(jù)容忍，這一特性能夠降低存儲空間通過的特點，幫助系統(tǒng)節(jié)省大量的存儲空間，滿足廉價設備上對海量日志數(shù)據(jù)冗余點的處理需求。

2.1 HDFS體系架構

當數(shù)據(jù)量過大時，數(shù)據(jù)的相似特征容易形成循環(huán)分類，多次處理等問題。因此，在濾除前，需要專門提取數(shù)據(jù)冗余點的特征。首先利用HDFS體系架構，通過數(shù)據(jù)采樣時間序列獲取數(shù)據(jù)冗余點的特征[7]，并將其進行分類處理，加快濾除速率。HDFS體系主要采用Master/Slave結構，如圖1所示。

圖1 HDFS體系架構

圖1中，Name Node(名稱節(jié)點)是HDFS中的集群的管理者，主要負責管理HDFS名字空間、存儲元數(shù)據(jù)、處理客戶端的數(shù)據(jù)請求，但是其本身不能進行文件讀取的操作；Data Node(數(shù)據(jù)節(jié)點)主要負責數(shù)據(jù)的實際存儲與操作。會定時通過心跳機制向名稱節(jié)點反饋各個節(jié)點的運行狀態(tài)及映射信息，并接受名稱節(jié)點的指令，進行數(shù)據(jù)刪除等操作；Secondary Name Node(輔助名稱節(jié)點)是名稱節(jié)點的冷備份，會定時獲取其相關信息并進行儲存，而且在發(fā)生故障時，可以輔助恢復Name Node。

2.2 數(shù)據(jù)冗余特征獲取

首先，用四元組G表示數(shù)據(jù)冗余點的存儲通道，如式(1)所示

G=(V，E，W，C)

(1)

其中，V為數(shù)據(jù)空間屬性對象；E為非空間屬性對象；W為時間屬性對象；C為三者之間的相互關系。然后假設數(shù)據(jù)中的第i個傳輸?shù)臄?shù)據(jù)包為ith，因該數(shù)據(jù)包為靜態(tài)分塊數(shù)據(jù)鏈上傳數(shù)包，所以為了得到不同大小的冗余數(shù)據(jù)塊，需要對其進行文件切分，隱通道內的數(shù)據(jù)切片函數(shù)計算算法如式(2)所示

(2)

式中，t0和tg分別為數(shù)據(jù)的邊緣特征分解初始時間向量和在海量日志數(shù)據(jù)內的迭代步數(shù)，則冗余數(shù)據(jù)采樣時間序列如式(3)所示

x(t0+iΔt)，i=0，1，…，N-1

(3)

在此基礎上，假設N為原始的數(shù)據(jù)集的全部樣本數(shù)，大類樣本數(shù)為Nmax，Nmin為小類樣本數(shù)。當大類樣本數(shù)大于小類樣本數(shù)，那么Nmax>Nmin，則每個樣本的分類密度的計算算法如式(4)所示

(4)

其中，數(shù)據(jù)K為空間中基于歐式距離的最鄰數(shù)目，K個最鄰數(shù)目中數(shù)據(jù)大類的樣本數(shù)為Ml，其密度分布表達式如式(5)所示

(5)

設對ρ個樣本的第j個輸出值和目標值分別是ypj(τ)和dpj，則特征提取的約束條件如式(6)所示

(6)

式中，τ為迭代數(shù)目；輸出數(shù)據(jù)量為n。然后設迭代速率為η，動量因子為α，則數(shù)據(jù)集的迭代次數(shù)表達式如式(7)所示

w(τ+1)=[ηw(τ)+α(w(τ)-w(τ-1))]

(7)

冗余點特征提取過程的收縮量如式(8)所示

(8)

其中，o(τ)為冗余點輸出量，輸入量總和為pj(τ)?；诖?，設Nh為一個標準的樣本數(shù)據(jù)集，g(x)為激勵函數(shù)，Ns為采集的樣本數(shù)，(xq，tq)為樣本，其關系表達式如式(9)所示

Nh=(xq，tq)×Ns×g(x)

(9)

基于上述建立一個有效的冗余數(shù)據(jù)特征提取模型，提取海量日志數(shù)據(jù)中含有冗余點的數(shù)據(jù)。如式(10)所示

(10)

其中，冗余數(shù)據(jù)偏置為bq。

2.3 數(shù)據(jù)冗余特征分類

在海量日志數(shù)據(jù)里，冗余點的特征在時間和空間上通常為離散狀態(tài)，因此，分類的過程也應該建立在離散狀態(tài)下，所提算法利用線性頻譜分析法計算求得冗余數(shù)據(jù)的適應值函數(shù)[8]，基于此對海量日志數(shù)據(jù)中的冗余數(shù)據(jù)進行分類處理。

當數(shù)據(jù)集z=z0時，其分類分量如下所示

S+(Zm)=W+(Zm，Z0)S+(Z0)

(11)

其中，W+(Zm，Z0)為Z0到Zm的分類算子，分類集合為S+(Z0)。因此，在進行分類時，只需要將M項多次分類去除即可，提取前M項分類結果表示如下所示

(12)

其中，p(Z0)為原始數(shù)據(jù)，冗余點特征為t(Z0)。然后設最初的冗余點采樣頻率為f0，計算確定冗余點提取結果如式(13)所示

(13)

則冗余數(shù)據(jù)的分類約束函數(shù)如式(14)所示

F=XmaxA+(1-Xmax)B

(14)

其中，分類準確率為A，消減百分比為B，再對異常數(shù)據(jù)的類內離散度集合進行加權處理，得到的分類結果如式(15)所示

(15)

其中，樣本的最大協(xié)方差和最小的協(xié)方差為covmax和covmin。通過上述計算可知，在HDFS體系架構通過數(shù)據(jù)采樣時間序列對數(shù)據(jù)冗余點進行提取、分類處理，不僅可以保證每個數(shù)據(jù)節(jié)點之間都相互通信，還可以在提高算法可靠性的同時加快濾除效率。

3 海量日志數(shù)據(jù)冗余點濾除算法設計

對海量日志數(shù)據(jù)中的數(shù)據(jù)冗余點進行濾除可以進一步優(yōu)化系統(tǒng)的數(shù)據(jù)存儲空間。但數(shù)據(jù)冗余點的濾除加大了數(shù)據(jù)壓縮的力度，為了使所提算法存儲開銷量更小，必須在冗余點濾除前對其縮減率、誤判率進行計算分析。

3.1 數(shù)據(jù)縮減率與誤判率計算

3.1.1 數(shù)據(jù)縮減率計算

首先，利用濾除前含有冗余特征的數(shù)據(jù)字節(jié)數(shù)與正常的字節(jié)數(shù)之比來進行數(shù)據(jù)縮減率的計算，如式(16)所示

(16)

通過式(16)可知，數(shù)據(jù)大小的開銷為G，計算算法如式(17)所示

(17)

其中，MwtadataSize為數(shù)據(jù)大小，AverageChunkSize為平均數(shù)據(jù)塊的大小。

3.1.2 數(shù)據(jù)誤判率計算

首先，由k個Hash函數(shù)將數(shù)據(jù)組S=(x1，x2…，xn)中全部數(shù)據(jù)向m位的數(shù)據(jù)組中進行映射，此數(shù)據(jù)組某一位是0的概率為P′，計算公式如下所示

(18)

(19)

若數(shù)據(jù)組當中值為0的比例為β，那么可將其示為數(shù)學期望。為了使運算更加快速、便捷，可設p=e-nk/m，當β值已知時，錯誤率的計算公式如下所示

(1-β)k≈(1-p′)k≈(1-p)k

(20)

通過上式可知，中值為1的比例為(1-β)，其中k次Hash剛好選擇了1區(qū)域，由(1-β)k表示。所以設數(shù)據(jù)組位數(shù)為m，元素數(shù)為n，則誤判率R的計算公式如下所示

(21)

3.2 數(shù)據(jù)冗余點濾除

經(jīng)過上述計算分析處理后，即可進行冗余點的濾除。為了避免在特征不明顯的情況下，發(fā)生不能及時濾除冗余點的情況，所提算法采用均值漂移傳遞函數(shù)對冗余點進行濾除，進一步提高所提算法的消除性能。

首先計算冗余點采集速度，設Lu為U時刻采集分類后的冗余點，Lv為V時刻采集分類后的冗余點，冗余點采集速度如式(22)所示

(22)

式中，最大速度為Smax，Savg為平均速度，Smin為最小速度差異程度的絕對值，dist(Lu，Lv)為數(shù)據(jù)冗余點的歐式距離。由此可知，Lu與Lv之間的位置距離獲取表達式如下所示

D=V(Lu，Lv)dist(Lu，Lv)

(23)

為了進一步所提算法的準確率，引入相似度概念，根據(jù)冗余點的突出特征計算整體相似度。設第i個冗余點的整體相似度為

(24)

對于單個冗余點來說，它包括γi個冗余數(shù)據(jù)的突出特征，而數(shù)據(jù)冗余點的整體相似度，可以表示突出特征βi的結構相似度，如式(25)所示，為數(shù)據(jù)冗余點整體相似度的加權處理平均數(shù)表達式

(25)

式中，si為第i個冗余點的加權平均數(shù)，數(shù)據(jù)集上的特征數(shù)量為I。

均值漂移傳遞函數(shù)是通過冗余點活動時間t消除冗余點的Hash函數(shù)，設數(shù)據(jù)集O中，存在Hi個冗余點的活動次數(shù)，To為O中冗余點的活動周期，根據(jù)活躍程度對冗余點進行濾除，其表達式如下所示

(26)

式中，數(shù)據(jù)冗余點最短活躍時間為tmin，最長活躍時間為tmax，總活躍時間為t。由此可知，Y越大說明數(shù)據(jù)冗余點越活躍，對其消除結果越好；反之，Y越小，說明越不活躍，冗余點的消除結果越差。

4 實驗分析

為驗證基于HDFS的海量日志數(shù)據(jù)冗余點過濾算法的整體有效性，設計對比實驗，將其與文獻[3]中的基于智能優(yōu)化算法的數(shù)據(jù)冗余點消除算法、文獻[4]中的基于動態(tài)時間規(guī)整的數(shù)據(jù)去重算法進行性能對比。實驗參數(shù)如表1所示。

表1 實驗背景參數(shù)

測試數(shù)據(jù)集內的數(shù)據(jù)特征設置如表2所示。

表2 實驗數(shù)據(jù)特征設置

4.1 準確率

為了驗證本文算法具有更高的準確率，實驗在固定數(shù)據(jù)量的情況下與文獻[3]算法、文獻[4]算法進行冗余點濾除準確率對比。

本次實驗在GCC數(shù)據(jù)集中進行，實驗準確率用消除數(shù)據(jù)量與原始數(shù)據(jù)量的比值表示，對比結果如圖2所示。

圖2 不同算法準確率對比結果

由圖2可知，三種算法隨著數(shù)據(jù)量的增加，數(shù)據(jù)冗余點濾除的準確率均出現(xiàn)下降的趨勢。但與文獻[3]算法和文獻[4]算法相比，本文算法濾除數(shù)據(jù)冗余點準確率最高。因為本文算法在對冗余點濾除前，利用數(shù)據(jù)采樣時間序列構建了數(shù)據(jù)冗余點特征提取模型，對冗余點進行了特征提取，使數(shù)據(jù)中的冗余點更加突出，進而在濾除時提高了本文算法的準確率。

4.2 濾除效率

為了驗證所提算法擁有更高的效率，實驗在SciLab數(shù)據(jù)集中進行，對不同算法的效率進行對比，對比結果如圖3所示。

圖3 不同算法濾除效率對比結果

分析圖3的對比結果可知，與文獻[3]算法和文獻[4]算法相比，本文算法濾除數(shù)據(jù)冗余點所需時間最少。因為本文算法在對冗余點濾除前，通過線性頻譜法將獲取到的數(shù)據(jù)冗余點特征進行了分類處理，降低了計算量，進而縮短了冗余點的濾除時間。雖然其在后期濾除時，時間有所增加，但濾除效率仍然高于傳統(tǒng)算法。

4.3 存儲開銷

為了驗證本文算法擁有更小的存儲開銷量，實驗在Linux數(shù)據(jù)集中進行，對不同算法進行存儲開銷對比，結果如圖4所示。

圖4 不同算法存儲開銷對比結果

分析圖4中的對比結果可知，三種算法的存儲開銷都隨著數(shù)據(jù)量的增加而增加。文獻[4]算法在冗余點濾除過程中，存儲開銷比例超過了47.2%，開銷最多；文獻[3]算法存儲開銷最高時在41.1%左右；而本文算法的存儲開銷最少。因為本文算法在濾除前對數(shù)據(jù)冗余點進行了特征提取，分類處理，然后利用含有冗余點特征的數(shù)據(jù)字節(jié)數(shù)與正常的字節(jié)數(shù)之比來進行縮減率和誤判率的計算，減輕了數(shù)據(jù)壓縮的力度，從而減少了濾除時的存儲開銷量。

5 結束語

利用傳統(tǒng)算法濾除數(shù)據(jù)冗余點時存在濾除效率差、準確率低、存儲開銷過大等問題，因此，本研究提出基于HDFS的海量日志數(shù)據(jù)冗余點過濾算法，高效實現(xiàn)了對數(shù)據(jù)冗余點的濾除。