基于改進Simhash的虛擬機鏡像去重方法

張燦陽， 劉曉潔

(1.四川大學計算機學院， 成都 610065； 2.四川大學網絡空間安全學院， 成都 610065)

1 引 言

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

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

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

2 虛擬機鏡像去重問題分析

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

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

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

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

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

(1)

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

3 基于改進Simhash算法的聚類去重方法

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

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

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

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

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

3.1 虛擬機鏡像分段

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

3.2 提取鏡像段的特征值

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

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

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

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

2) 計算文件的指紋和權重.

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

(2)

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

3) 指紋向量加權.

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

(3)

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

4) 求和降維.

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

(4)

3.3 鏡像段的聚類

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

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

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

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

1) 操作系統鏡像段.

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

2) 應用數據鏡像段.

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

(5)

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

在此基礎上，我們采用DBSCAN聚類算法對應用數據鏡像段進行處理，聚類算法如算法1所示.

算法1 應用數據鏡像段聚類算法.

輸入:包含n個應用數據鏡像段的Simhash簽名集合D={S1,S2,…,Sn}，閾值THRESHOLD，每個類最少包含的鏡像段個數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 //類中元素過少被標記為噪音

7) else

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

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

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

12) if S’ is unvisited

13) markS’ as visited

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

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.

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

3) 非文件系統鏡像段.

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

3.4 二級去重策略

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

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

算法2 文件系統鏡像段的二級重刪算法

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

Begin:

1) SetF= { },B= { } //分組內所有不重復文件的集合、不重復數據塊的集合

2) for eachSiinC

3) Mount(Si) //掛載鏡像段并進入其文件系統

4) for eachfilejinSi

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

6)F=F∪ {filej} //將不重復的文件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，則該文件不進行塊級去重

13) else

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

15) for eachblockminfile_block_set

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

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

18) end if

19) end for

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

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

22) end if

23) end for

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

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

End.

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

4 實驗驗證

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

表1 實驗環境

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

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

圖5 小規模數據下的去重時間Fig.5 Deduplication time under small-scale data

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

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

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

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

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

圖6 大規模數據集下的去重時間Fig.6 Deduplication time under large-scale data

表3大規模數據集下的壓縮率

Tab.3Datacompressionrateunderbig-scaledata

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

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

圖7 去重過程中內存占用Fig.7 Memory usage during deduplication

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

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