基于聚類的重復數據去冗算法的研究

劉 賽，聶慶節，劉 軍，王 超，李 靜

(1.南瑞集團公司，江蘇 南京 210003；2.南京航空航天大學 計算機學院，江蘇 南京 211106)

0 引 言

隨著物聯網時代的到來，從傳感器節點到企業日常業務中，收集到的數據越來越多[1]，收集大量數據組成的信息系統不僅方便了人們的生活，而且為未來決策提供了參考，但是人們也必須面對數據丟失的危險。災備系統[2]是數據保護最后的防護，用來提高數據的安全性。然而備份存儲中心中存在大量的冗余數據[3]，比如在多次備份時每次都存儲的全量備份中大部分都是重復數據，在各個版本的備份文件中也含有數目巨大的重復數據。備份系統中存在的重復數據導致了需要備份的數據量迅速增加。

備份海量的數據需要使用大量的磁帶，而大量的冗余數據浪費了許多磁帶。傳統的數據壓縮[4]方法是采用文件編碼中冗余的信息進行壓縮，沒有全局壓縮的思想，文件的壓縮效率很差，同時不能進行不同文件間的重復數據壓縮。與傳統數據壓縮算法不同，DELTA壓縮算法[5]是全局壓縮技術，針對在不同備份系統中，不同備份文件間進行重復數據檢測和消除，利用不同文件之間的重復信息進行冗余數據消除，大大提高了文件的壓縮率。由香農的信息論[6]原理可知，在任意非隨機生成的文件中都包含冗余信息，可以利用統計建模等方法，得到一個字符或者短語出現的頻率，用最短的字符表示出現頻率最高的數據。利用這種統計建模構造壓縮算法的編碼方式包括游程編碼[7]、熵編碼[8]以及字典編碼[9]。利用這些編碼方式，較長的字符串可以用較短的字符串信息表示。另外，Zhang等[10]介紹了線性回歸原理的分段常數逼近算法(PMC-MR)[11]及其改進算法(PMC-MENAN)[12]，其算法思想是利用時間相關性，在壓縮過程中確定數據差距限值，用分段函數的函數式擬合原始數據，同時記錄獲取最大、最小以及兩者差值。當差值超過設定的最大誤差值時，用序列的持續時間和數值大小來替代。Wang等[13]提出了基于重復數據消除的備份數據加密方法，根據分塊內容的哈希值生成分塊對稱密鑰，用于將明文分塊與密文分塊一一對應，采用分塊對稱密鑰方法保證了用戶私鑰與身份識別口令不同時，數據庫中的備份數據無法被外界解密破解，同時也保證了文件的壓縮效率。Kang等[14]提出面向容災的備份數據透明加密機制，著重解決備份數據的安全問題，采用一種層疊式文件系統來面向容災的備份數據進行透明加密，利用虛擬磁盤透明加密的方法，當數據寫入時進行加密，數據讀取時進行解密，保護了備份數據的安全性和機密性。

DELTA壓縮通過保存一份參考文件，采用內容無關的方法從文件中選取特征集，在系統中找出一份與新文件具有高度相似性的參考文件，再計算相似文件之間的DELTA壓縮編碼，在備份系統中直接存取DELTA壓縮編碼，不再存儲源文件。采用DELTA壓縮算法可節省存儲空間、減少需要傳輸的數據量，提高歸檔的效率。DELTA算法進行重復數據刪除時有較高的壓縮率，但是隨著壓縮數據規模變大，所需存儲的指紋塊數也隨之增長。大量的指紋塊存儲在硬盤上，讀取磁盤數據所需時間遠大于讀取內存所需時間，導致查詢時間過久無法用于實際生產環境。采用K-medoids聚類[15]進行預處理的DELTA壓縮算法可以提高壓縮率，同時減少了查找指紋的次數。

1 相關技術

1.1 重復數據刪除技術

重復數據刪除可以劃分成兩種類型，第一種是刪除相同數據，即僅僅保留一份相同的數據，然后用指針指向其他位置出現的相同數據。第二種是查找到相似度高的數據，采用DELTA壓縮算法對相似數據編碼存儲，節約存儲空間。DELTA壓縮的核心思想是將重復的數據標記出來，并存儲一份，當再次遇到這部分數據之后，用指針指向其存儲位置，以減少需備份的文件。

把文件看作是由字符、數字、字節等按一定順序組成的字符串。DELTA壓縮算法可以視為對字符串從左至右進行編碼，當出現一個字典里面不存在的字符串時，向DELTA壓縮編碼中添加(ADD,L,S)命令字符串，表示在該位置添加長度為L的字符串S，如果發現該字符串已經存儲過一份，則添加(COPY,L,O)命令字符串，表示從R中復制長度為L，偏移量為O的字符串到該位置。具體實現通過定義DELTA壓縮函數(記為D)，它的輸入為一個待壓縮文件V和一個參考文件R，輸出為一個DELTA文件Δ(R,V)。當備份系統進行DELTA壓縮時，首先從文件中選擇適當字串，通過計算每個字串的指紋得到指紋集合，利用指紋集合中相同指紋的個數來確定兩個文件的相似度。

DELTA壓縮算法針對R和V之間的冗余數據，當R中已存在該數據時，保存Δ(R,V)的復制命令，將其指向R中對應數據的鏈接，針對R中不存在的數據，用添加命令顯式添加。R和V相似度較高時，Δ(R,V)比V小得多；R和V完全相同時，Δ(R,V)就是一個命令。因此，通過保存Δ(R,V)來替代V可大大節省存儲空間。

1.2 K-medoids聚類

K-medoids聚類是一種基于劃分的聚類算法。與K-means算法以簇內所有樣本點的均值作為簇聚類中心不同，K-medoids聚類是以簇中實際樣本點作為簇的聚類中心，減少K-means算法對少數誤差點的敏感性。K-medoids聚類首先任意選擇K個不同的數據對象作為初始簇中心，其他數據對象根據其與簇中心的距離，將它們分配到距離最近的簇，然后在每個簇內部順序選擇一個非簇中心點的數據代替簇中心點，選擇代價最小的點作為簇中心點，然后反復迭代，用非簇中心點來代替簇中心點，當一個中心點被某個非中心點替代時，除了未被替換的中心點外，其余各點將被重新分配。當聚類中心和各個點所屬聚類簇都不再變化時，算法結束。K-medoids聚類算法使用最接近聚類中心的對象作為簇中心，增強了算法的魯棒性，具有數據抗干擾性強、聚類結果與輸入順序無關以及對小數據集聚類效果明顯等特點。

2 基于K-medoids聚類的重復數據去冗算法

對于一個新的數據塊，根據其與其他數據塊之間的相似度，會出現兩種情況，分別如圖1中的S1和S2所示。圖中的每個點都表示一個對應的數據塊，兩個點之間的距離表示二者之間的相似度。S1表示該數據塊屬于一號簇的情況，它到其他簇的距離遠大于到一號簇的距離，并且與它相近距離的點也屬于一號簇。S2表示該數據塊不屬于任意簇，與其最相似的數據塊是屬于其他簇的數據塊，但是這些數據塊都在其他簇的邊界。即表示S2也可作為聚類中心，它周圍的數據塊與它都較相似，也可以達到高效壓縮，所以，通過設置閾值的方法無法考慮到各個文件之間的相似性。K-means算法是采用簇內所有點的均值作為簇聚類中心，無法計算該中心到其他數據塊之間的距離(相似度)，故無法評價該聚類中心是否合理。K-medoids聚類算法可以通過不斷迭代的方式選擇簇內的一個點作為聚類中心，使得每個數據塊可以歸屬到更加合適的聚類簇中，所以采用K-medoids聚類算法作為DELTA壓縮前的預處理。

圖1 相似數據聚類模型描述

針對DELTA壓縮大文件時所需數據指紋較多、查找速度慢等問題，且當文件足夠大時，內存將無法存儲，所以將大文件切割成小文件塊，然后將小文件塊兩兩合并，進行DELTA壓縮，并把DELTA壓縮后的文件大小作為文件的相似度，根據得到的相似度進行K-medoids聚類。最后，按照聚類結果合并小文件塊，再將合并后相似度高的文件進行DELTA壓縮。基于K-medoids聚類的DELTA壓縮的框架圖如圖2所示。

2.1 K-medoids聚類處理

對需要壓縮的大文件進行切分，采用1 M文件大小作為劃分單位，之后對劃分的文件塊兩兩之間進行DELTA壓縮，DELTA壓縮后的文件大小存儲在臨時矩陣arr_delta[N][N]，將它作為文件塊之間的相似度。為方便敘述，現在統一規定本文所用符號。

圖2 基于K-medoids聚類的DELTA壓縮框架圖

兩個相似數據塊之間的相似度表示為二者的DELTA距離，即：

dist(Si,Sj)=delta(Si,Sj)

(1)

整個聚類的流程為：在S中任意選擇K個聚類中心點，分別用{m1,m2,…,mk}表示。將代表剩余數據塊的點分配給距它最近的簇中，獲得聚類簇C={C1,C2,…,Ck}。然后對每一個簇Ci,i∈{1,2,…,k}，遍歷簇中的第i個非中心點對象Sj，用式(2)計算當Sj代替中心點mi的總代價。

(2)

2.2 聚類后DELTA壓縮

經過以上步驟的預處理，得到了各個相似的數據塊的聚類集合，根據聚類結果將文件塊合并。合并之后的大文件內部之間的相似度較高，即通過合并相似文件塊之后，|Δ(R,V)|小于甚至遠小于|V|，考慮通過Δ(R,V)替代存儲V，可以達到壓縮文件大小的目的。根據聚類后的結果進行去冗余，對文件整體進行數據壓縮。在重復數據去冗階段再次使用DELTA壓縮算法消除重復數據。

對于聚類后的待壓縮文件，首先采用內容無關的方法從文件中選取特征集，根據可分配內存的大小，確定產生中間指紋數量與文件大小。設定一個滑動窗口的大小，不斷向前移動滑動窗口，計算移動窗口下的數據指紋，在特征數據庫中搜索一個與它高度相似的參考文件，找到該參考文件后，根據壓縮函數D進行壓縮。為了提高檢索速度，降低查找時間，采用Hash函數映射成超級特征或超級指紋集。若超級指紋相匹配，則兩個文件的相似度較大。通過以上算法找到了與該文件具有極大相似性的文件，然后通過函數D對有序符號串進行編碼，利用ADD編碼命令(其命令格式為(ADD,L,S))，表示在V中的指定位置添加長度為L的字符串S；COPY編碼命令(其命令格式為(COPY,L,O))，表示從R中復制長度為L，偏移量為O的字符串到V中的指定位置。獲得經過DELTA壓縮后的文件Δ(R,V)，最后存儲壓縮文件。基于K-medoids聚類的重復數據去冗算法的整體流程如圖3所示。

Input:輸入大備份文件(待壓縮文件)Output:輸出已經壓縮好的文件(1)輸入大備份文件;(2)按照文件大小=1M切割該文件;(3)fori=1:M{forj=1:M{第i個文件和第j個文件合并進行DELTA壓縮將壓縮后的文件存儲到臨時數組arr_delta[N][N]}}(4)確定聚類個數K(5)while 聚類中心或者聚類中的點有變化do 根據arr_delta[N][N]確定各個點所屬類fori←1toKdo更新聚類中心endend輸出聚類情況(6)根據聚類情況,合并文件塊(7)將合并后的文件塊進行DELTA壓縮

圖3 基于K-medoids聚類的重復數據去冗算法

3 實驗驗證

為了驗證基于K-medoids聚類的DELTA壓縮算法的有效性，利用一臺配置為Intel Core i5-3470，2 GB內存，SATA 5 600 轉磁盤的臺式計算機作為測試環境進行測試。利用Oracle數據庫的測試數據作為待壓縮數據，測試基于K-medoids聚類的DELTA壓縮效果。通過在測試集上直接使用DELTA壓縮與先聚類再進行DELTA壓縮兩種方式進行對比，來驗證該算法的有效性。

首先，定義壓縮率為DELTA壓縮文件與待壓縮文件大小的比率，即壓縮率為：

compress_rate=經過壓縮之后的文件大小/總文件大小

(3)

式(3)表明壓縮率的值越小越好。DELTA壓縮的算法思想表明待壓縮文件與同一個參考文件之間的相似性越高，壓縮效果就越好，換言之，文件內含有的相似數據越多，文件的壓縮率越高。接下來進行實驗驗證。

3.1 壓縮性能測試

為了驗證基于K-medoids聚類方法的DELTA壓縮方法的性能，對比源文件大小、經過DELTA壓縮后的文件大小以及聚類之后再經過DELTA壓縮后的文件大小。

首先將大文件切割為每個文件大小為1 M的小文件，作為初始的源文件。然后將切割后的每個文件直接進行DELTA壓縮，作為另一組對比實驗。將切割后的文件塊兩兩合并，然后對合并后的文件進行DELTA壓縮，將DELTA壓縮后的文件大小作為文件間的相似度。再根據文件間的相似度利用K-medoids對文件塊進行聚類，根據聚類結果進行文件塊合并，然后再進行DELTA壓縮，作為最后一組對比實驗。

針對Oracle數據庫測試數據進行測試，選取測試數據的前30個文件塊進行描述。

由式(3)可得，直接通過DELTA壓縮的壓縮率約為50%；經過K-medoids聚類預處理之后再經過DELTA壓縮的壓縮率約為25%。

結果如圖4所示。

直接經過DELTA壓縮，壓縮率在50%，經過DELTA壓縮算法可以使得文件壓縮率降低40%以上，在此基礎上，經過K-medoids聚類預處理之后再進行DELTA壓縮的方式，即在DELTA壓縮之前依據相似度進行聚類，又可提高50%左右的壓縮率。

由此可證，通過聚類后的文件有很大程度上的相似，可大大提高文件內的相似度。對于相似度越高的文件，DELTA壓縮的效率越高。

在第2節中，分析得出重復文件刪除的效率瓶頸在于當檢測重復指紋時需要大量的讀磁盤操作，尤其當指紋數量超過內存大小時，檢索算法需要大量的I/O操作將指紋從磁盤中讀入到內存，使得程序效率大大降低。將大文件切割成小文件，再按照相似度相近的原則進行聚類，然后以數據指紋可以在內存上可接受為原則進行合并。再對合并之后的文件進行DELTA壓縮，通過對數據DELTA壓縮前的預處理步驟來提高數據的壓縮率。經實驗驗證，效果有明顯提高。

圖4 部分文件塊壓縮對比

3.2 聚類合并性能測試

在數據壓縮中，可以采取對小文件直接壓縮、隨機合并文件壓縮(一般采取直接按照序號合并)、聚類合并后壓縮三種方式，對比這三種方式的壓縮情況，如圖5所示。

圖5 部分數據集在不同方式下的壓縮對比

經過實驗證明，直接對小文件進行壓縮時，得到的壓縮率最小；對小文件合并之后再進行壓縮，可以提高壓縮率；根據文件塊相似度差異的大小先聚類再進行合并，可以大大提高文件壓縮率。通過聚類將小文件進行合并，提高了合并后文件的相似度，之后再進行DELTA壓縮，減少了查找相似文件塊的時間，并且提高了文件的壓縮率。采用文件切分、聚類、合并、再壓縮的方式，可以保證數據指紋的數量在一定的限度內(保證數據指紋存儲在內存中)，減少磁盤的I/O操作，有助于大文件的壓縮。從測試結果來看，聚類后壓縮可以很好地達到壓縮效果。這也證明了聚類后壓縮去冗的有效性。

4 結束語

針對大文件在進行DELTA壓縮時數據指紋過多的問題，提出了一種基于K-medoids聚類算法的DELTA壓縮方法。測試結果表明，該算法可有效地減少數據指紋數量、提高壓縮率，使重復數據刪除的效果更加明顯。下一步將研究如何設置最優的聚類中心個數，以進一步提高壓縮率，降低壓縮時間。

[1] 蔣 鵬,吳建峰,吳 斌,等.基于自適應最優消零的無線傳感器網絡數據壓縮算法研究[J].通信學報,2013,34(2):1-7.

[2] 毛 波,葉閣焰,藍琰佳,等.一種基于重復數據刪除技術的云中云存儲系統[J].計算機研究與發展,2015,52(6):1278-1287.

[3] 馬發勇,厲啟鵬,馬志斌,等.電力調度SCADA系統中歷史數據壓縮及存儲策略[J].電網技術,2014,38(4):1109-1114.

[4] QUAN W，XU C，GUAN J，et al.Scalable name lookup with adaptive prefix bloom filter for named data networking[J].IEEE Communications Letters,2014,18(1):102-105.

[5] 付印金,肖 儂,劉 芳.重復數據刪除關鍵技術研究進展[J].計算機研究與發展,2012,49(1):12-20.

[6] 劉厚貴,邢 晶,霍志剛,等.一種支持海量數據備份的可擴展分布式重復數據刪除系統[J].計算機研究與發展,2013,50:64-70.

[7] MEISTER D,BRINKMANN A.Multi-level comparison of data deduplication in a backup scenario[C]//SYSTOR 2009:the Israeli experimental systems conference.New York,NY,USA:ACM,2009.

[8] 張滬寅,周景才,陳毅波,等.用戶感知的重復數據刪除算法[J].軟件學報,2015,26(10):2581-2595.

[9] BILIMOVIC A.Boundary value problems for nonlinear fractional differential equations[J].Acta Mathematica Scientia,2015,31(4):1337-1346.

[10] 屈志偉.無線傳感器網絡數據壓縮算法綜述[J].科技創新與應用,2015(32):90.

[11] AHMAD B,NTOUYAS S.Existence of solutions for fractional differential inclusions with nonlocal Riemann-Liouville integral boundary conditions[J].Boundary Value Problems,2014,139(3):451-465.

[12] MIN J,YOON D,WON Y.Efficient deduplication techniques for modern backup operation[J].IEEE Transactions on Computers,2011,60(6):824-840.

[13] 王 燦,秦志光,馮朝勝,等.面向重復數據消除的備份數據加密方法[J].計算機應用,2010,30(7):1763-1766.

[14] 康瀟文,楊英杰,杜 鑫.面向容災的備份數據透明加密機制[J].計算機工程,2009,35(20):131-133.

[15] 祁 蘭,毛燕琴,沈蘇彬.一種傳感數據的壓縮和高效存儲方案[J].計算機技術與發展,2016,26(11):177-181.