基于改進(jìn)Simhash的虛擬機(jī)鏡像去重方法

張燦陽， 劉曉潔

(1.四川大學(xué)計算機(jī)學(xué)院， 成都 610065； 2.四川大學(xué)網(wǎng)絡(luò)空間安全學(xué)院， 成都 610065)

1 引 言

虛擬化技術(shù)歷經(jīng)多年的發(fā)展與沉淀，已經(jīng)成為搭建云環(huán)境的關(guān)鍵性技術(shù)，虛擬機(jī)的部署愈加廣泛.研究指出，虛擬機(jī)鏡像大量存在于企業(yè)的生產(chǎn)環(huán)境中，大型企業(yè)中鏡像數(shù)量甚至?xí)哌_(dá)5 000～20 000個，且增長速度極快[1]，這導(dǎo)致了云平臺需要管理數(shù)量龐大的鏡像文件.實際上，在應(yīng)用系統(tǒng)所保存的數(shù)據(jù)中，高達(dá)60%的數(shù)據(jù)是冗余的，備份歸檔系統(tǒng)中，重復(fù)數(shù)據(jù)的比例高達(dá)80%～90%[2].在針對虛擬機(jī)的備份場景中，這一比例甚至更高，主要原因有如下兩點：(1) 虛擬機(jī)鏡像文件通常會包含大量零塊(即空白數(shù)據(jù)塊)，例如分區(qū)格式化產(chǎn)生的未利用空間等，這些零塊對于備份系統(tǒng)來說均屬于重復(fù)數(shù)據(jù);(2) 用戶在部署虛擬機(jī)的過程中，選擇通過統(tǒng)一的OVF(Open Virtualization Format)模板創(chuàng)建，或者通過已存在的虛擬機(jī)實例進(jìn)行復(fù)制創(chuàng)建，將導(dǎo)致兩個虛擬機(jī)鏡像之間存在很高的數(shù)據(jù)冗余率，即使用戶創(chuàng)建全新的虛擬機(jī)，也有可能因為運(yùn)行了相同的操作系統(tǒng)或者相似的應(yīng)用而導(dǎo)致數(shù)據(jù)重復(fù)率較高.

大量的實驗數(shù)據(jù)表明，云環(huán)境中虛擬機(jī)鏡像文件的數(shù)據(jù)冗余率超過50%[3].對于備份中心來說，同一虛擬機(jī)可能存在多個備份副本，因此，使用重復(fù)數(shù)據(jù)刪除技術(shù)減少虛擬機(jī)鏡像的空間占用率成為降低存儲成本的主要技術(shù)之一.

虛擬機(jī)鏡像去重在本質(zhì)上是文件去重，但是對于海量的虛擬機(jī)鏡像文件，去重過程中會產(chǎn)生巨大的指紋索引數(shù)據(jù)(數(shù)據(jù)塊的摘要值和該數(shù)據(jù)塊對應(yīng)的偏移)，當(dāng)這些指紋索引超出可用內(nèi)存的大小時，將不得不進(jìn)行頻繁的內(nèi)外存交換來完成指紋的查找，這會帶來巨大的時間與空間開銷，增加服務(wù)器的響應(yīng)時間[4]，系統(tǒng)的服務(wù)質(zhì)量QOS(Quality Of Service)受到影響.針對上述問題，本文提出了一種基于改進(jìn)Simhash的鏡像聚類去重方法ICDA-IS(Image Clustering Deduplication Algorithm Based on Improved Simhash)，該方法使用改進(jìn)Simhash提取鏡像特征值，并利用DBSCAN算法對鏡像進(jìn)行分組去重.實驗結(jié)果證明，本文的方法犧牲了少量去重率，但是減少了相當(dāng)可觀的時間開銷和內(nèi)存占用.

2 虛擬機(jī)鏡像去重問題分析

虛擬機(jī)鏡像去重會產(chǎn)生海量的指紋索引數(shù)據(jù)，在去重過程中會頻繁進(jìn)行指紋查找.如果將這些數(shù)據(jù)全部置于可用內(nèi)存中，將會消耗大量的內(nèi)存資源，對服務(wù)器性能造成巨大影響.反之，如果將這部分?jǐn)?shù)據(jù)置于外存中，由于訪問一次外存的時間要遠(yuǎn)遠(yuǎn)大于一次內(nèi)存讀寫時間，因此會大大增加去重的時間開銷，Zhu等人將其稱為磁盤瓶頸問題[5].

與常規(guī)文件相比，虛擬機(jī)鏡像文件有如下鮮明特點：(1) 占用存儲空間較大，一般從若干GB到數(shù)百GB不等，特殊情況下會占用數(shù)TB的存儲資源; (2) 鏡像文件中往往會包含較多的零塊，如虛擬磁盤中的未分配區(qū)域，或者是分區(qū)中的未利用空間等，在去重中這些零塊均是重復(fù)數(shù)據(jù).文獻(xiàn)指出，零塊在鏡像文件中的比例高達(dá)35%以上[6]; (3) 在鏡像文件的內(nèi)部，包含了大量虛擬機(jī)操作系統(tǒng)文件，實驗結(jié)果表明，具有相同操作系統(tǒng)的虛擬機(jī)鏡像的重復(fù)數(shù)據(jù)刪除率能達(dá)到70%以上[7].同樣，在運(yùn)行了相同應(yīng)用的虛擬機(jī)鏡像中，也會有類似的現(xiàn)象.

如何提取鏡像中的有效數(shù)據(jù)，避免磁盤讀寫瓶頸，降低海量虛擬機(jī)鏡像的去重時間，是虛擬機(jī)鏡像去重的關(guān)鍵問題.

Jin等人[3]通過實驗證明，在虛擬機(jī)鏡像去重中，選取固定長度分塊和可變長分塊得到的去重率基本相同.Lillibridge等人[8]采用取樣方法，內(nèi)存中只保留文件分段的指紋樣本，雖然降低了內(nèi)存占用，但是隨著鏡像文件的增加，其內(nèi)存開銷依然會增大.Zhu等人[5]在LPC(Locality Preserved Caching)技術(shù)的基礎(chǔ)上提出了SISL(Stream-Informed Segment Layout)技術(shù)，優(yōu)化了傳統(tǒng)緩存方案，為數(shù)據(jù)塊和塊描述符提供了更好的空間局部性，大幅降減少了去重過程中磁盤的I/O次數(shù).但是在虛擬機(jī)鏡像去重這樣的特殊場景中，該方法無法過濾鏡像中的大量零塊，仍會有較多的CPU計算開銷.

文獻(xiàn)[1]提出了一種基于聚類分組的虛擬機(jī)鏡像去冗余方法VMIDM-BC(Virtual Machine Image Deduplication Method Based on Clustering)，將海量虛擬機(jī)鏡像先分組再去重，每次僅將分組內(nèi)的指紋數(shù)據(jù)載入內(nèi)存，解決了磁盤的讀寫瓶頸問題，但是同樣無法快速剔除鏡像中的大量空白數(shù)據(jù)塊，從而使得鏡像內(nèi)部去重時間較長.其次，該方法定義兩個鏡像A和B的相似度Sim(A,B)為

(1)

其中，M′=(f1,f2,…,fm)表示一個鏡像文件內(nèi)部定長分塊去重之后的數(shù)據(jù)塊指紋集合.可見計算兩個鏡像相似度的時間復(fù)雜度與鏡像包含數(shù)據(jù)塊的指紋數(shù)量成正比，在面對大鏡像文件時計算相似度的時間開銷較大.此外，VMIDM-BC采用K-means聚類完成分組操作，在去重中需要計算任意兩個鏡像之間的相似度，而鏡像的指紋數(shù)據(jù)存儲在磁盤上，因此聚類過程必定會頻繁讀寫外存去獲取某個鏡像的指紋集合，即使采用預(yù)處理的方法，在聚類之前計算出所有鏡像之間的相似度矩陣，也需要多次磁盤I/O才能完成，因此該去重方法的時間開銷依然較大.

3 基于改進(jìn)Simhash算法的聚類去重方法

本文方法旨在消除海量虛擬機(jī)鏡像去重過程中極易出現(xiàn)的磁盤瓶頸問題，并盡可能在去重之前就過濾掉鏡像中的空白數(shù)據(jù)塊，縮短去重時間.其主要思想如下：(1) 掛載虛擬機(jī)鏡像中的文件系統(tǒng)，獲取鏡像中的有效數(shù)據(jù)，避免在去重過程中讀取鏡像中的大量空白數(shù)據(jù)塊，有效降低I/O次數(shù); (2) 利用DBSCAN聚類算法和鏡像段的特征值將全部待去重鏡像段分組，從而將一個全局去重問題分解為若干個局部去重的子問題.在每個分組的去重過程中，能夠?qū)⒎纸M內(nèi)的指紋索引數(shù)據(jù)置于內(nèi)存中，大幅降低了由于頻繁訪問磁盤而帶來的時間開銷.

在判斷兩個鏡像是否相似的過程中，存在如下兩種情況：(1) 兩個虛擬機(jī)鏡像的操作系統(tǒng)不同，但是包含了大量重復(fù)的應(yīng)用數(shù)據(jù)，此時鏡像之間的重復(fù)數(shù)據(jù)基本存在于保存該應(yīng)用數(shù)據(jù)的分區(qū)中; (2) 兩個鏡像的操作系統(tǒng)相同但是運(yùn)行了不同的應(yīng)用，在這種情況下，鏡像間的冗余數(shù)據(jù)絕大部分存在于鏡像的操作系統(tǒng)分區(qū)上.因此，有必要根據(jù)虛擬機(jī)鏡像的內(nèi)部分區(qū)結(jié)構(gòu)，將一個完整的磁盤鏡像分割為粒度更小的鏡像段，以獲得更為精確的相似關(guān)系.

在此基礎(chǔ)上，我們利用DBSCAN算法將分割后的虛擬機(jī)鏡像段分組，把重復(fù)度高的鏡像段歸在同一個類中進(jìn)行去重，基本流程如圖1所示.

圖1 聚類去重方法的基本流程Fig.1 Basic process of clustering deduplication method

圖2 鏡像段示意圖Fig.2 Schematic diagram of image segment

3.1 虛擬機(jī)鏡像分段

由于虛擬機(jī)鏡像文件中通常包含了完整的虛擬磁盤信息，因此可以通過讀取鏡像的分區(qū)表來獲得虛擬磁盤內(nèi)部的分區(qū)信息.分割后得到的鏡像段本質(zhì)上是一個虛擬機(jī)鏡像文件在特定偏移處的一部分，所有鏡像段按順序組成一個完整的虛擬機(jī)鏡像，如圖2所示.這些鏡像段大致分為三類：(1)包含操作系統(tǒng)分區(qū)的系統(tǒng)鏡像段；(2)包含用戶數(shù)據(jù)分區(qū)的應(yīng)用數(shù)據(jù)鏡像段；(3)不包含文件系統(tǒng)的鏡像文件頭、磁盤引導(dǎo)、分區(qū)間隙以及未利用空間等，統(tǒng)稱為非文件系統(tǒng)鏡像段.

3.2 提取鏡像段的特征值

Charikar提出的Simhash算法[9]本質(zhì)上是一種局部敏感哈希LSH(Locality-Sensitive Hashing)算法[10]，相似文本會有相似的Simhash簽名，即簽名之間的海明距離(Hamming Distance)較小.Manku等人[11]提出了基于Simhash的海量相似網(wǎng)頁去重方案，其核心是文本向量化[12]，效果顯著.

但是，Simhash算法只能用于文本的相似度[13]計算中，而鏡像段是虛擬機(jī)鏡像的一部分，屬于二進(jìn)制文件，不能直接應(yīng)用該算法獲取鏡像段的簽名，無法進(jìn)一步完成類似于文本聚類[14]的操作，從而也無法將全局問題分解為局部問題求解.下文給出提取鏡像段特征值的改進(jìn)Simhash算法，計算鏡像段S的Simhash簽名詳細(xì)過程如下.

1) 鏡像段映射到虛擬塊設(shè)備.

如果鏡像段S包含文件系統(tǒng)，則通過映射至空閑回環(huán)設(shè)備(loop device)的方式，將其虛擬為只讀塊設(shè)備并識別該文件系統(tǒng)類型，將其掛載到指定目錄，獲得鏡像段S包含的文件集合F={file1,file2,…,filen}.

2) 計算文件的指紋和權(quán)重.

使用MD5摘要算法計算文件filei的指紋fingeri=bit0bit1…bitL(L=128,即MD5摘要的比特寬度)，鏡像段S的文件指紋集合M={finger1,finger2,…,fingern}.在同一個鏡像段中，如果一個文件的尺寸越大，出現(xiàn)的次數(shù)越多，那么這個文件在該鏡像段中占用數(shù)據(jù)塊的比例則越高.據(jù)此，利用式(2)計算filei的權(quán)重weighti.

(2)

其中,file_sizei是文件filei的大小(單位：KB)，file_frequencyi表示文件filei出現(xiàn)的頻數(shù)，SegSize是鏡像段S的大小(單位：KB).式(2)實際上表明了一個文件及其所有副本在一個鏡像段中占用存儲空間的比例大小.

3) 指紋向量加權(quán).

對于M中的指紋fingeri，初始化其對應(yīng)的加權(quán)向量veci=[01,02,…,0L]，遍歷指紋中的每一個比特位fingerik.對于一個文件來說，其占用空間越大，則權(quán)重越大，同時對鏡像段的simhash值產(chǎn)生的影響越大，反之，小文件和少量數(shù)據(jù)塊僅會對最終的simhash值產(chǎn)生微小的影響.因此對于某個文件的指紋來說，若其中某個bit位為1，則將該位擴(kuò)大為其權(quán)重倍，反之則將該位減去其權(quán)重，即式(3)，利用該公式計算文件的加權(quán)向量veci，保證相似的鏡像段得到相似的simhash值.在此基礎(chǔ)上，將鏡像段S表示為一組向量集合V={vec1,vec2,…,vecn}.

(3)

圖3 提取Simhash簽名示例Fig.3 Example of extracting a Simhash signature

4) 求和降維.

為了得到一個鏡像段的Simhash值，我們將其包含的所有文件的加權(quán)向量求和，如式(4)所示.為了加速Simhash的查找并降低存儲空間，我們遍歷求和結(jié)果Sum，并將其中的正數(shù)置1，負(fù)數(shù)置0，得到最終長度為L的Simhash簽名.圖3是改進(jìn)Simhash算法的過程示例圖.

(4)

3.3 鏡像段的聚類

對于占用空間達(dá)到數(shù)TB甚至PB、EB級別的海量虛擬機(jī)鏡像而言，去重過程中產(chǎn)生的指紋索引表不可能全部放在內(nèi)存中，因此指紋查詢增加了大量額外的磁盤I/O時間，整體去重時間大幅延長.為了避免這些時間開銷，我們提出了一種基于DBSCAN的自適應(yīng)聚類去重方法，算法流程如圖4所示.

圖4 鏡像段聚類去重示意圖Fig.4 Flowchart of image segments cluster deduplication

上述流程圖的基本思想為：將包含文件系統(tǒng)的鏡像段按照系統(tǒng)分區(qū)和數(shù)據(jù)分區(qū)兩個分支進(jìn)行處理，含相同的操作系統(tǒng)的鏡像段歸為同一類，含相似應(yīng)用數(shù)據(jù)的鏡像段歸為同一類，與此同時，我們限制每個分類中所包含鏡像段的總大小，使得每個分類在去重中所產(chǎn)生的指紋索引表均小于可用內(nèi)存的大小，在指紋查找過程中完全避免了因內(nèi)存未命中而增加的磁盤I/O時間.

對這些鏡像段的聚類大致分為以下三種情況.

1) 操作系統(tǒng)鏡像段.

實驗結(jié)果[15]表明，在20個不同的Windows NT(windows new technology)映像的服務(wù)器中數(shù)據(jù)冗余率高達(dá)58%，實際上，同一操作系統(tǒng)的同種發(fā)行版本之間重復(fù)數(shù)據(jù)所占的比例將會更高.但是在不同類型的操作系統(tǒng)中，其系統(tǒng)文件的冗余率則很低.因此對于包含操作系統(tǒng)分區(qū)的鏡像段，按照其系統(tǒng)類型進(jìn)行分類去重，以獲得更高的去重率.

2) 應(yīng)用數(shù)據(jù)鏡像段.

對于不包含操作系統(tǒng)分區(qū)的鏡像段來說，我們利用3.2節(jié)提取的Simhash簽名對其進(jìn)行聚類.對于鏡像段A，B來說，如果二者之間的重復(fù)數(shù)據(jù)越多，那么兩個鏡像段的Simhash簽名SA和SB也就越相似，兩者的海明距離也會越小.我們用式(5)計算鏡像A、B的相似度.

(5)

其中，SigLen表示Simhash簽名的長度.根據(jù)式(5)可知，兩個鏡像段之間的相似度取值范圍為[0,1]，如果相似度超過閾值THRESHOLD，則可認(rèn)為兩個鏡像段相似度較高.

在此基礎(chǔ)上，我們采用DBSCAN聚類算法對應(yīng)用數(shù)據(jù)鏡像段進(jìn)行處理，聚類算法如算法1所示.

算法1 應(yīng)用數(shù)據(jù)鏡像段聚類算法.

輸入:包含n個應(yīng)用數(shù)據(jù)鏡像段的Simhash簽名集合D={S1,S2,…,Sn}，閾值THRESHOLD，每個類最少包含的鏡像段個數(shù)MIN.

Begin:

1) SetC=0 //初始類編號

2) for each unvisitedSinD

3) markSas visited

4)N= RangeQuery(S,THRESHOLD) //找到與S相似度大于THRESHOLD的鏡像段

5) if |N| < MIN

6) markSas NOISE //類中元素過少被標(biāo)記為噪音

7) else

8) SetC=C+ 1 //類編號增加1,即創(chuàng)建新類

9) addSto clusterC//將鏡像段S添加到類C中

11) for eachS’ inN//訪問N中的每一個鏡像段

12) if S’ is unvisited

13) markS’ as visited

14)N’ = RangeQuery(S’, THRESHOLD) //類的擴(kuò)充

15) if |N’ | ≥ MIN

16)N=N∪N’ //鄰域合并

17) end if

18) end if

19) ifS’ is not yet member of any cluster

20) addS’ to clusterC

21) end if

22) end for

23) end if

24) end for

End.

為了減少噪音點對去重結(jié)果造成的影響，在聚類完成之后，我們將包含鏡像段比較少的類歸為一組進(jìn)行處理，最大限度地利用當(dāng)前可用內(nèi)存，減少去重的時間.

3) 非文件系統(tǒng)鏡像段.

對于虛擬機(jī)鏡像而言，除去包含文件系統(tǒng)的鏡像段之后，剩余的磁盤空間大致包含了鏡像文件頭、分區(qū)間隙、未格式化的分區(qū)以及磁盤的未利用空間等.這些鏡像段中，絕大部分扇區(qū)均是空白扇區(qū)，因此將所有非文件系統(tǒng)鏡像段作為一個單獨的分組進(jìn)行處理.如果該分組中鏡像段的總大小超出最大限制，將其分裂并確保每個小分組中的鏡像段總大小不超出上限.

3.4 二級去重策略

在所有的鏡像段分類完成之后，如果一個分組內(nèi)的鏡像段包含文件系統(tǒng)，那么我們采用文件級+塊級的二級去重策略進(jìn)行去重操作，文件級去重能夠保證同一個文件只保留一個副本，塊級去重能夠去除文件內(nèi)部和文件之間的重復(fù)數(shù)據(jù)塊，盡可能提高去重率.如果組內(nèi)的鏡像段不含文件系統(tǒng)，我們直接采用定長分塊去重策略.

由于在提取Simhash簽名的過程中，我們已經(jīng)計算了鏡像段中所有文件的指紋值，因此，對于一個鏡像段集合來說，我們先進(jìn)行分組范圍內(nèi)的文件級去重，在此基礎(chǔ)上，對于較大的文件，進(jìn)一步實現(xiàn)分組范圍內(nèi)的塊級去重，具體過程見算法2.

算法2 文件系統(tǒng)鏡像段的二級重刪算法

輸入:包含m個鏡像段的分組C={S1,S2,…,Sm}，定長分塊大小BLOCK_SIZE.

Begin:

1) SetF= { },B= { } //分組內(nèi)所有不重復(fù)文件的集合、不重復(fù)數(shù)據(jù)塊的集合

2) for eachSiinC

3) Mount(Si) //掛載鏡像段并進(jìn)入其文件系統(tǒng)

4) for eachfilejinSi

5) iffilejnot in F //通過filej的指紋判斷該文件是否重復(fù)

6)F=F∪ {filej} //將不重復(fù)的文件filej加入集合F

7) end if

8) end for

9) end for

10) for eachfilekinF//遍歷文件集合F

11) if QueryFileSize(filek) ≤ BLOCK_SIZE

12) continue //如果文件小于BLOCK_SIZE，則該文件不進(jìn)行塊級去重

13) else

14)file_block_set=FixedSizeChunk(filek) //固定長度分塊

15) for eachblockminfile_block_set

16) ifblockmnot inB//通過blockm的指紋判斷該數(shù)據(jù)塊是否重復(fù)

17)B=B∪ {blockm} //將不重復(fù)的數(shù)據(jù)塊blockm加入集合B

18) end if

19) end for

20)SaveFileMetadata(filek) //保存大文件元數(shù)據(jù)

21)F=F- {filek} //將進(jìn)行了塊級去重的文件從F中刪除

22) end if

23) end for

24)SaveBlockData(B) //保存唯一數(shù)據(jù)塊集合B

25)SaveSmallFile(F) //保存F中剩余的小文件

End.

二級重刪的目的是在保證去重速度的同時達(dá)到較高的去重率.在第一級的文件重刪過程中，我們僅讀取了鏡像中的文件，從而減少了讀取和計算大量空白數(shù)據(jù)塊所消耗的時間.其后的塊級去重主要是針對相似的大文件而設(shè)計，因為相似文件的指紋不同，卻包含了較多的重復(fù)數(shù)據(jù)塊，為了提高去重率，我們增加了大文件之間的塊級去重.

4 實驗驗證

我們通過一系列的實驗來驗證本文提出算法ICDA-IS的有效性.從vSphere云平臺和OpenStack云環(huán)境中選取100個不同的虛擬機(jī)鏡像，每個鏡像的大小在3～50 GB之間，共計989 GB，其中包括vmdk格式的鏡像27個，raw格式鏡像73個.實驗中，去重服務(wù)器的具體配置如表1所示，我們將聚類去重的內(nèi)存限制為500 MB，采用16字節(jié)的MD5值作為文件和數(shù)據(jù)塊的指紋，8字節(jié)的地址作為唯一數(shù)據(jù)塊索引，如果我們采用4 KB大小的定長分塊全局去重，在最壞的情況下指紋索引數(shù)據(jù)將達(dá)到5.8 GB，遠(yuǎn)超可用內(nèi)存的大小.

表1 實驗環(huán)境

在對比實驗中，首先我們實現(xiàn)了基于硬盤哈希表的全局去重算法，該方法將所有的指紋索引數(shù)據(jù)存放在磁盤中，并在查找過程中進(jìn)行讀寫磁盤操作.其次與開源去重工具Deduputil做對比，該工具使用布隆過濾器[16]和集合關(guān)聯(lián)緩存等方案優(yōu)化關(guān)鍵字的查找，核心是一個輕量級的KeyValue存儲系統(tǒng).經(jīng)多年市場使用反饋，該去重工具性能穩(wěn)定，且指紋查找效率與命中率均表現(xiàn)十分優(yōu)秀.

小規(guī)模數(shù)據(jù)(10個鏡像共計120 GB)的情況下，分別采用硬盤哈希表、Deduputil和ICDA-IS算法進(jìn)行去重操作，為了降低偶然性誤差的影響，每組對比實驗重復(fù)10次，圖5給出了去重消耗的時間.在小規(guī)模數(shù)據(jù)集的實驗結(jié)果中，與基于硬盤哈希表的去重相比，ICDA-IS算法節(jié)約了超過50%的去重時間.由于小規(guī)模數(shù)據(jù)集所產(chǎn)生的指紋索引數(shù)據(jù)相對較小(不足1 GB)，對于Deduputil來說相當(dāng)于全內(nèi)存去重(指紋索引全部緩存在內(nèi)存中)，但是ICDA-IS仍能夠減少約30%的去重時間，原因就在于，ICDA-IS算法僅讀取鏡像中的有效數(shù)據(jù)，減少了處理大量空白數(shù)據(jù)塊的時間.三種方法的數(shù)據(jù)壓縮率如表2所示，可以看到，基于硬盤哈希表的去重可以達(dá)到18.23%的數(shù)據(jù)壓縮率，Deduputil可以達(dá)到18.55%的數(shù)據(jù)壓縮率，本文提出的ICDA-IS算法的實際數(shù)據(jù)壓縮率為19.26%，與前兩者的差距不足1%.

圖5 小規(guī)模數(shù)據(jù)下的去重時間Fig.5 Deduplication time under small-scale data

實驗結(jié)果原始鏡像ICDA-ISDeduputil硬盤哈希表鏡像總大小/GB12123.322.4422.06壓縮率/%10019.26 18.55 18.23

大規(guī)模數(shù)據(jù)集(100個鏡像共計989 GB)情況下增加與文獻(xiàn)[1]中VMIDM-BC算法的對比，圖6和表3記錄了4種去重方式的數(shù)據(jù)壓縮率和去重時間.

從實驗結(jié)果可以看出，在海量鏡像去重情況下：

(1) 就去重時間而言，ICDA-IS算法比Deduputil減少了60%～70%的時間開銷，這是因為隨著讀入數(shù)據(jù)塊的增加，Deduputil產(chǎn)生的指紋索引數(shù)據(jù)在不斷增大，內(nèi)存引作為磁盤中指紋索引數(shù)據(jù)的緩存，其命中率持續(xù)降低，從而導(dǎo)致讀寫磁盤次數(shù)增加，去重效率低下.在與VMIDM-BC算法的對比中，由于ICDA-IS算法在預(yù)處理的過程中剔除了大量的無效空白數(shù)據(jù)塊，從而降低了磁盤I/O次數(shù)，并利用改進(jìn)Simhash算法提取了固定長度的鏡像段特征值加快了聚類過程，因此比后者節(jié)省了約30%的去重時間.

(2) 就壓縮率來看，ICDA-IS算法比全局去重(Deduputil和硬盤哈希表)低3%左右，但是從表3可知，對于壓縮掉的近90%的重復(fù)數(shù)據(jù)來說，增加微小的存儲開銷而減少約70%的去重時間開銷，是可以接受且值得的.

圖6 大規(guī)模數(shù)據(jù)集下的去重時間Fig.6 Deduplication time under large-scale data

表3大規(guī)模數(shù)據(jù)集下的壓縮率

Tab.3Datacompressionrateunderbig-scaledata

實驗結(jié)果原始鏡像ICDA-ISDeduputilVMIDM-BC硬盤哈希表鏡像總大小/GB989132.4102.2113.2101.8壓縮率/%10013.3810.3311.4510.29

在大規(guī)模數(shù)據(jù)集的去重測試中，各算法占用的內(nèi)存情況如圖7所示.可以看出，隨著去重鏡像總量的增加，Deduputil消耗的內(nèi)存空間也逐漸增大，在完成500 GB的鏡像去重時，該算法消耗的內(nèi)存高達(dá)18 GB.本文提出的ICDA-IS算法與文獻(xiàn)[1]中的VMIDM-BC算法均是在完成分類的基礎(chǔ)上進(jìn)行多次小規(guī)模去重，保證了內(nèi)存消耗始終在1 GB以下，極大減少了云數(shù)據(jù)中心的資源開銷.

圖7 去重過程中內(nèi)存占用Fig.7 Memory usage during deduplication

云環(huán)境中，將重復(fù)數(shù)據(jù)刪除技術(shù)引入海量虛擬機(jī)備份場景可以節(jié)省大量的存儲資源，但是去重過程中極易出現(xiàn)磁盤瓶頸導(dǎo)致重刪效率急劇下降.針對該問題，本文提出了一種基于改進(jìn)Simhash算法的海量虛擬機(jī)鏡像聚類去重方法，利用虛擬機(jī)鏡像的內(nèi)部結(jié)構(gòu)將完整的鏡像分割為若干個較小粒度的鏡像段，并針對鏡像段的特殊性改進(jìn)了傳統(tǒng)的Simhash算法，將其用來提取二進(jìn)制鏡像段的特征值.利用該特征值和DBSCAN算法實現(xiàn)了對鏡像段的聚類，從而將全局去重變成了局部的分組內(nèi)部去重，避免了磁盤瓶頸，使得去重操作的時間大幅度降低.本文通過實驗驗證了該方法在海量虛擬機(jī)鏡像去重的情景中，能夠以消耗微小的存儲空間為代價，減少相當(dāng)可觀的時間開銷.

但是本文仍存在一些不足，在處理自組織格式的虛擬機(jī)鏡像文件(如qcow2格式)時，由于其內(nèi)部結(jié)構(gòu)與物理磁盤不同，因此無法按照分區(qū)將其分割為鏡像段，以及云環(huán)境中為了保護(hù)用戶隱私[17]而存在的大量加密數(shù)據(jù)[18]，如何處理這種類型的鏡像文件實現(xiàn)快速去重，也是今后研究的方向.