基于HDFS的海量日志數(shù)據(jù)冗余點過濾算法仿真

賈文鋼，高錦濤

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

1 引言

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

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

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

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

2.1 HDFS體系架構(gòu)

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

圖1 HDFS體系架構(gòu)

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

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

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

G=(V，E，W，C)

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

(6)

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

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

(7)

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

(8)

其中，o(τ)為冗余點輸出量，輸入量總和為pj(τ)?；诖?，設(shè)Nh為一個標(biāo)準(zhǔn)的樣本數(shù)據(jù)集，g(x)為激勵函數(shù)，Ns為采集的樣本數(shù)，(xq，tq)為樣本，其關(guān)系表達(dá)式如式(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)，因此，分類的過程也應(yīng)該建立在離散狀態(tài)下，所提算法利用線性頻譜分析法計算求得冗余數(shù)據(jù)的適應(yīng)值函數(shù)[8]，基于此對海量日志數(shù)據(jù)中的冗余數(shù)據(jù)進(jìn)行分類處理。

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

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

(11)

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

(12)

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

(13)

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

F=XmaxA+(1-Xmax)B

(14)

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

(15)

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

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

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

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

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

首先，利用濾除前含有冗余特征的數(shù)據(jù)字節(jié)數(shù)與正常的字節(jié)數(shù)之比來進(jìn)行數(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ù)組中進(jìn)行映射，此數(shù)據(jù)組某一位是0的概率為P′，計算公式如下所示

(18)

(19)

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

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

(20)

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

(21)

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

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

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

(22)

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

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

(23)

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

(24)

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

(25)

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

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

(26)

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

4 實驗分析

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

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

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

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

4.1 準(zhǔn)確率

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

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

圖2 不同算法準(zhǔn)確率對比結(jié)果

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

4.2 濾除效率

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

圖3 不同算法濾除效率對比結(jié)果

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

4.3 存儲開銷

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

圖4 不同算法存儲開銷對比結(jié)果

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

5 結(jié)束語

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