基于哈希計(jì)算的大數(shù)據(jù)冗余消除算法設(shè)計(jì)

張淑清

(廣西警察學(xué)院 交通管理工程學(xué)院，廣西 南寧 530022)

0 引言

當(dāng)前由于大數(shù)據(jù)系統(tǒng)中冗余數(shù)據(jù)的緩存量較大，在系統(tǒng)中占據(jù)了較大的存儲(chǔ)空間，且數(shù)據(jù)的總體冗余率已超過80%[1-2]，因此亟需尋求一種有效方法消除重復(fù)數(shù)據(jù)。對(duì)于大數(shù)據(jù)的去重操作有利于降低系統(tǒng)的運(yùn)維成本和消耗，使系統(tǒng)運(yùn)行過程中對(duì)于網(wǎng)絡(luò)帶寬的占用量降低，但目前的冗余數(shù)據(jù)消除技術(shù)仍面臨巨大的問題，如數(shù)據(jù)結(jié)構(gòu)較為復(fù)雜、數(shù)據(jù)相似性較高以及數(shù)據(jù)類型多樣等，同時(shí)還需要注意冗余數(shù)據(jù)消除的吞吐量和冗余數(shù)據(jù)消除率這兩個(gè)沖突的目標(biāo)[3]。

目前已有相關(guān)領(lǐng)域的研究學(xué)者對(duì)存儲(chǔ)系統(tǒng)中的數(shù)據(jù)去重技術(shù)進(jìn)行了相關(guān)研究。文獻(xiàn)[4]以多節(jié)點(diǎn)樣條理論為基礎(chǔ)，提出了數(shù)據(jù)自適應(yīng)快速去重方法。該方法首先提取了冗余數(shù)據(jù)特征，根據(jù)冗余數(shù)據(jù)的線性頻譜對(duì)其進(jìn)行分類。通過節(jié)點(diǎn)樣條理論降低分類過程中出現(xiàn)的偏差。建立小波函數(shù)消除數(shù)據(jù)中噪聲，設(shè)計(jì)快速消除冗余數(shù)據(jù)的方法，其去重復(fù)速度較快，但重復(fù)率消除效果還需要進(jìn)一步研究。文獻(xiàn)[5]提出存儲(chǔ)數(shù)據(jù)中重復(fù)數(shù)據(jù)去冗余方法。以霧節(jié)點(diǎn)中訪問頻率較高數(shù)據(jù)作為測試數(shù)據(jù)，引入循環(huán)冗余碼技術(shù)實(shí)時(shí)數(shù)據(jù)塊是否重復(fù)。若判斷結(jié)果為數(shù)據(jù)重復(fù)，則將重復(fù)數(shù)據(jù)置于鏈表結(jié)構(gòu)中，并加以去除，完成符合霧節(jié)點(diǎn)實(shí)際情況的數(shù)據(jù)去冗余方法的設(shè)計(jì)。雖然數(shù)據(jù)存儲(chǔ)成本較低，但冗余去重率不理想，且網(wǎng)絡(luò)資源集合中仍存在部分冗余數(shù)據(jù)。

為此，提出基于哈希計(jì)算的大數(shù)據(jù)冗余消除算法。在數(shù)據(jù)去重前計(jì)算冗余數(shù)據(jù)的權(quán)重值，根據(jù)權(quán)重值區(qū)分出訪問量較高的數(shù)據(jù)，結(jié)合哈希法進(jìn)行冗余數(shù)據(jù)的判斷與消除。既提高了冗余數(shù)據(jù)的消除率又保證了數(shù)據(jù)吞吐量，解決了大數(shù)據(jù)存儲(chǔ)系統(tǒng)中冗余數(shù)據(jù)的消除過程中吞吐量與冗余數(shù)據(jù)消除率之間的沖突問題。

1 大數(shù)據(jù)資源冗余數(shù)據(jù)消除

1.1 數(shù)據(jù)分類

針對(duì)復(fù)雜數(shù)據(jù)以及相似度較高的數(shù)據(jù)，為降低去重的時(shí)間和能源消耗，需要在消除冗余數(shù)據(jù)前針對(duì)樣本數(shù)據(jù)進(jìn)行分類。

計(jì)算大數(shù)據(jù)存儲(chǔ)系統(tǒng)中樣本數(shù)據(jù)的權(quán)重值，以此反映樣本數(shù)據(jù)在數(shù)據(jù)集中的邊緣程度。具體計(jì)算過程如式(1)。

(1)

式中，k為該數(shù)據(jù)中虛擬節(jié)點(diǎn)個(gè)數(shù);zi為第i個(gè)數(shù)據(jù)字符串長度;xi為樣本數(shù)據(jù)中第i個(gè)數(shù)據(jù)的被訪問頻率;λ為虛擬節(jié)點(diǎn)鍵值。根據(jù)權(quán)重值實(shí)現(xiàn)大規(guī)模數(shù)據(jù)的類別劃分，劃分類別數(shù)c如式(2)。

(2)

式中，?j為數(shù)據(jù)冗余度閾值，以此將訪問頻率較高的數(shù)據(jù)劃分到單獨(dú)的類別之中，完成了數(shù)據(jù)的分類。

1.2 冗余數(shù)據(jù)消除

基于數(shù)據(jù)的分類結(jié)果，進(jìn)行高訪問頻率數(shù)據(jù)中冗余數(shù)據(jù)的判斷與消除處理。為提高算法的運(yùn)算速度，通過哈希法[6-8]計(jì)算數(shù)據(jù)塊的哈希值，具體計(jì)算內(nèi)容如式(3)。

(3)

式中,H表示固定長度的哈希值;G表示哈希函數(shù)，該式可提升重復(fù)的數(shù)據(jù)塊的判斷速度。

為提高去重效果，通過計(jì)算數(shù)據(jù)的散列值，判斷數(shù)據(jù)之間的相似性，定理描述如式(4)。

(4)

式中,U表示數(shù)據(jù)散列值；S(Q)表示冗余數(shù)據(jù)集;數(shù)據(jù)的相似性為R。當(dāng)集合相似性為70%時(shí)，說明在該集合中有70%的數(shù)據(jù)在同一位置是具有相同屬性的。

由此，針對(duì)相似數(shù)據(jù)中的冗余數(shù)據(jù)提取可通過式(5)實(shí)現(xiàn)。

(5)

其中,bi代表相似程度最高的數(shù)據(jù);P為數(shù)據(jù)集內(nèi)部離散值。

除相似數(shù)據(jù)的去重問題外，還需實(shí)現(xiàn)復(fù)雜數(shù)據(jù)中的冗余消除，因此需要計(jì)算該相似數(shù)據(jù)集合中的熵，如式(6)。

(6)

式中，si為結(jié)構(gòu)復(fù)雜度最高的數(shù)據(jù)節(jié)點(diǎn);α為數(shù)據(jù)量大小。

融合式(5)的數(shù)據(jù)相似度運(yùn)算與式(6)的數(shù)據(jù)復(fù)雜度運(yùn)算可得到去除冗余數(shù)據(jù)后的存儲(chǔ)系統(tǒng)數(shù)據(jù)輸出為式(7)。

(7)

由此，降低了信息集合相似度以及熵值，實(shí)現(xiàn)了網(wǎng)絡(luò)資源中冗余數(shù)據(jù)的消除。

1.3 算法執(zhí)行步驟設(shè)計(jì)

有效消除冗余數(shù)據(jù)可以減少數(shù)據(jù)所占內(nèi)存，從而有效提高存儲(chǔ)空間利用效率，避免由于系統(tǒng)故障造成數(shù)據(jù)損失。所提算法的具體執(zhí)行步驟如圖1所示。

圖1 消除冗余數(shù)據(jù)執(zhí)行示意圖

根據(jù)圖1可知，基于哈希計(jì)算的大數(shù)據(jù)冗余消除算法，無需頻繁計(jì)算數(shù)據(jù)的特征值，可利用現(xiàn)有數(shù)據(jù)進(jìn)行數(shù)據(jù)塊之間的相似性與熵值的檢測，消除大數(shù)據(jù)中的冗余重復(fù)數(shù)據(jù)，減少數(shù)據(jù)占用的存儲(chǔ)空間。

2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

2.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)準(zhǔn)備

實(shí)驗(yàn)過程所需裝置為處理機(jī)3臺(tái)、存儲(chǔ)服務(wù)器1臺(tái)、備份服務(wù)器1臺(tái)。硬件配置有20GB存儲(chǔ)內(nèi)存、E5606微處理器、15TB磁盤陣列、150GB閃存、Ubuntu12.05操作系統(tǒng)。不同設(shè)備之間的連接通過百兆交換機(jī)實(shí)現(xiàn)，具體實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)環(huán)境設(shè)置

根據(jù)表1所示實(shí)驗(yàn)環(huán)境，對(duì)實(shí)驗(yàn)數(shù)據(jù)展開分析。

實(shí)驗(yàn)所用數(shù)據(jù)集文件共10個(gè)，總大小為130GB，依次對(duì)網(wǎng)絡(luò)資源進(jìn)行命名為：DA-1，DA-2，DA-3，DA-4，DA-5，DA-6，DA-7，DA-8，DA-9，DA-10，其大小依次為：2.05 GB、4GB、5.6GB、7.8GB、9.2GB、12.3GB、15.7GB、19.5GB、23.8 GB、30.05 GB。分別采用文獻(xiàn)[4]算法，文獻(xiàn)[5]算法與所提算法對(duì)該數(shù)據(jù)資源進(jìn)行去重，將3種方法的去重效果進(jìn)行對(duì)比分析，并獲取驗(yàn)證結(jié)果。

2.2 存儲(chǔ)空間占用對(duì)比

冗余數(shù)據(jù)消除的主要目的在于減少數(shù)據(jù)占有的存儲(chǔ)系統(tǒng)空間內(nèi)存，因此需要對(duì)比不同算法對(duì)大數(shù)據(jù)中的冗余數(shù)據(jù)進(jìn)行消除后，存儲(chǔ)系統(tǒng)空間的占用量，以此作為評(píng)價(jià)去重算法運(yùn)算效果的標(biāo)準(zhǔn)。對(duì)比結(jié)果如圖2所示。

圖2 3種算法去重后的系統(tǒng)存儲(chǔ)空間對(duì)比

由圖2可知，通過3種方法去重后，文獻(xiàn)[4]算法的剩余數(shù)據(jù)在存儲(chǔ)系統(tǒng)中占據(jù)的空間最大，次之為文獻(xiàn)[5]算法，最后為所提方法，剩余數(shù)據(jù)占用系統(tǒng)存儲(chǔ)空間非常小，這是由于所提方法中采用的哈希計(jì)算方法根據(jù)數(shù)據(jù)相似度對(duì)冗余數(shù)據(jù)進(jìn)行識(shí)別和消除，可以區(qū)分出數(shù)據(jù)間的細(xì)微差別，對(duì)冗余數(shù)據(jù)的識(shí)別度更高。

2.3 網(wǎng)絡(luò)帶寬對(duì)比

網(wǎng)絡(luò)帶寬占用量是評(píng)價(jià)系統(tǒng)性能的重要指標(biāo)，高性能的系統(tǒng)所占用的網(wǎng)絡(luò)帶寬較低。為此，對(duì)比3種方法運(yùn)算過程中所占用的網(wǎng)絡(luò)帶寬。具體對(duì)比結(jié)果如圖3所示。

圖3 3種算法所占用的的網(wǎng)絡(luò)帶寬對(duì)比

由圖3可知，文獻(xiàn)[4]算法所占用的網(wǎng)絡(luò)帶寬最大，次之是文獻(xiàn)[5]算法。帶寬占用量最低的是所提算法。這是由于所提算法中通過哈希算法生成虛擬節(jié)點(diǎn)，將數(shù)據(jù)映射到Hash中進(jìn)行判斷和消除處理，對(duì)服務(wù)器網(wǎng)絡(luò)的占用較少。

2.4 冗余數(shù)據(jù)去重率對(duì)比

為了進(jìn)一步說明所提算法的去重效果，對(duì)比不同數(shù)據(jù)塊下文獻(xiàn)[4]算法、文獻(xiàn)[5]算法與所提算法對(duì)大數(shù)據(jù)資源的冗余數(shù)據(jù)去重率，結(jié)果如表2所示。

由表2可知，多用戶備份情況下，所提算法最高去重率可達(dá)到99%，而另2種對(duì)比算法最高去重率可達(dá)到57%；單用戶備份情況下，所提算法最高去重率可達(dá)到99%，而傳統(tǒng)算法最高去重率可達(dá)到90%。由于所提算法具有針對(duì)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的識(shí)別能力，通過計(jì)算并降低數(shù)據(jù)的熵值，突出相似度較高的數(shù)據(jù)。因此，所提算法無論在多用戶還是單用戶備份模式下，都具有較高去重率。

表2 3種方法冗余數(shù)據(jù)去重率

2.5 吞吐量對(duì)比

分析數(shù)據(jù)去重率方面的對(duì)比結(jié)果可知所提方法具有較好的去重效果，但由于冗余數(shù)據(jù)的去重效果與數(shù)據(jù)吞吐量是相互沖突的，若數(shù)據(jù)去重率較高則會(huì)影響數(shù)據(jù)的去重速度。因此，需要驗(yàn)證所提算法的數(shù)據(jù)吞吐量。具體對(duì)比結(jié)果如表3所示。

根據(jù)表3所示，所提算法的數(shù)據(jù)吞吐量最高可達(dá)26 MB/s，而文獻(xiàn)[4]算法與文獻(xiàn)[5]算法的數(shù)據(jù)吞吐量較低，最高為16 MB/s。這是由于所提方法不需要反復(fù)提取數(shù)據(jù)的特征點(diǎn)，可直接針對(duì)數(shù)據(jù)的相似度進(jìn)行計(jì)算，且在數(shù)據(jù)去重前，進(jìn)行了數(shù)據(jù)預(yù)分類操作，提升了運(yùn)算效率。

表3 3種方法冗余數(shù)據(jù)吞吐量

3 總結(jié)

基于哈希計(jì)算的大數(shù)據(jù)冗余消除算法實(shí)現(xiàn)了不同用戶之間的數(shù)據(jù)去重，能夠提取出復(fù)雜數(shù)據(jù)與相似度較高數(shù)據(jù)中的冗余數(shù)據(jù)塊，在保證去重率的同時(shí)提升了數(shù)據(jù)的吞吐量，證明所提方法具有一定的可行性。

雖然冗余消除的效果較好，但該方法仍存在需要改進(jìn)的地方，在實(shí)現(xiàn)全局冗余數(shù)據(jù)消除方面只能在網(wǎng)絡(luò)資源備份過程中實(shí)施，具有一定風(fēng)險(xiǎn)性，因此下一步可以充分考慮實(shí)現(xiàn)基于全局冗余數(shù)據(jù)消除功能。