基于哈希計算的大數據冗余消除算法設計

張淑清

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

0 引言

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

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

為此，提出基于哈希計算的大數據冗余消除算法。在數據去重前計算冗余數據的權重值，根據權重值區分出訪問量較高的數據，結合哈希法進行冗余數據的判斷與消除。既提高了冗余數據的消除率又保證了數據吞吐量，解決了大數據存儲系統中冗余數據的消除過程中吞吐量與冗余數據消除率之間的沖突問題。

1 大數據資源冗余數據消除

1.1 數據分類

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

計算大數據存儲系統中樣本數據的權重值，以此反映樣本數據在數據集中的邊緣程度。具體計算過程如式(1)。

(1)

式中，k為該數據中虛擬節點個數;zi為第i個數據字符串長度;xi為樣本數據中第i個數據的被訪問頻率;λ為虛擬節點鍵值。根據權重值實現大規模數據的類別劃分，劃分類別數c如式(2)。

(2)

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

1.2 冗余數據消除

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

(3)

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

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

(4)

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

由此，針對相似數據中的冗余數據提取可通過式(5)實現。

(5)

其中,bi代表相似程度最高的數據;P為數據集內部離散值。

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

(6)

式中，si為結構復雜度最高的數據節點;α為數據量大小。

融合式(5)的數據相似度運算與式(6)的數據復雜度運算可得到去除冗余數據后的存儲系統數據輸出為式(7)。

(7)

由此，降低了信息集合相似度以及熵值，實現了網絡資源中冗余數據的消除。

1.3 算法執行步驟設計

有效消除冗余數據可以減少數據所占內存，從而有效提高存儲空間利用效率，避免由于系統故障造成數據損失。所提算法的具體執行步驟如圖1所示。

圖1 消除冗余數據執行示意圖

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

2 實驗設計與結果分析

2.1 實驗環境與數據準備

實驗過程所需裝置為處理機3臺、存儲服務器1臺、備份服務器1臺。硬件配置有20GB存儲內存、E5606微處理器、15TB磁盤陣列、150GB閃存、Ubuntu12.05操作系統。不同設備之間的連接通過百兆交換機實現，具體實驗環境如表1所示。

表1 實驗環境設置

根據表1所示實驗環境，對實驗數據展開分析。

實驗所用數據集文件共10個，總大小為130GB，依次對網絡資源進行命名為：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。分別采用文獻[4]算法，文獻[5]算法與所提算法對該數據資源進行去重，將3種方法的去重效果進行對比分析，并獲取驗證結果。

2.2 存儲空間占用對比

冗余數據消除的主要目的在于減少數據占有的存儲系統空間內存，因此需要對比不同算法對大數據中的冗余數據進行消除后，存儲系統空間的占用量，以此作為評價去重算法運算效果的標準。對比結果如圖2所示。

圖2 3種算法去重后的系統存儲空間對比

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

2.3 網絡帶寬對比

網絡帶寬占用量是評價系統性能的重要指標，高性能的系統所占用的網絡帶寬較低。為此，對比3種方法運算過程中所占用的網絡帶寬。具體對比結果如圖3所示。

圖3 3種算法所占用的的網絡帶寬對比

由圖3可知，文獻[4]算法所占用的網絡帶寬最大，次之是文獻[5]算法。帶寬占用量最低的是所提算法。這是由于所提算法中通過哈希算法生成虛擬節點，將數據映射到Hash中進行判斷和消除處理，對服務器網絡的占用較少。

2.4 冗余數據去重率對比

為了進一步說明所提算法的去重效果，對比不同數據塊下文獻[4]算法、文獻[5]算法與所提算法對大數據資源的冗余數據去重率，結果如表2所示。

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

表2 3種方法冗余數據去重率

2.5 吞吐量對比

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

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

表3 3種方法冗余數據吞吐量

3 總結

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

雖然冗余消除的效果較好，但該方法仍存在需要改進的地方，在實現全局冗余數據消除方面只能在網絡資源備份過程中實施，具有一定風險性，因此下一步可以充分考慮實現基于全局冗余數據消除功能。