劉 賽，聶慶節(jié)，劉 軍，王 超，李 靜

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

0 引 言

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

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

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

1 相關技術

1.1 重復數(shù)據(jù)刪除技術

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

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

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

1.2 K-medoids聚類

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

2 基于K-medoids聚類的重復數(shù)據(jù)去冗算法

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

圖1 相似數(shù)據(jù)聚類模型描述

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

2.1 K-medoids聚類處理

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

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

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

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

(1)

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

(2)

2.2 聚類后DELTA壓縮

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

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

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

圖3 基于K-medoids聚類的重復數(shù)據(jù)去冗算法

3 實驗驗證

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

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

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

(3)

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

3.1 壓縮性能測試

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

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

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

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

結果如圖4所示。

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

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

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

圖4 部分文件塊壓縮對比

3.2 聚類合并性能測試

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

圖5 部分數(shù)據(jù)集在不同方式下的壓縮對比

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

4 結束語

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

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

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

[3] 馬發(fā)勇,厲啟鵬,馬志斌,等.電力調度SCADA系統(tǒng)中歷史數(shù)據(jù)壓縮及存儲策略[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] 付印金,肖 儂,劉 芳.重復數(shù)據(jù)刪除關鍵技術研究進展[J].計算機研究與發(fā)展,2012,49(1):12-20.

[6] 劉厚貴,邢 晶,霍志剛,等.一種支持海量數(shù)據(jù)備份的可擴展分布式重復數(shù)據(jù)刪除系統(tǒng)[J].計算機研究與發(fā)展,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] 張滬寅,周景才,陳毅波,等.用戶感知的重復數(shù)據(jù)刪除算法[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] 屈志偉.無線傳感器網絡數(shù)據(jù)壓縮算法綜述[J].科技創(chuàng)新與應用,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] 王 燦,秦志光,馮朝勝,等.面向重復數(shù)據(jù)消除的備份數(shù)據(jù)加密方法[J].計算機應用,2010,30(7):1763-1766.

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

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