杜 華，劉華春

(1.核工業(yè)西南物理研究院，四川 成都 610000；2.成都理工大學 工程技術學院，四川 樂山 614000)

0 引 言

重復數(shù)據(jù)刪除技術是一種數(shù)據(jù)縮減技術，常用于基于磁盤的備份系統(tǒng)中，旨在減少存儲系統(tǒng)中使用的存儲容量。以往的重復數(shù)據(jù)刪除系統(tǒng)往往采用單服務器結構，具有配置簡單、易于管理的優(yōu)點[1]。

近年來，隨著云計算、大數(shù)據(jù)技術的發(fā)展，企業(yè)數(shù)據(jù)中心存儲的需求量日益龐大[2]。據(jù)國際數(shù)據(jù)公司(IDC)統(tǒng)計[3]，全球數(shù)據(jù)總量預計2020年達到44 ZB，中國數(shù)據(jù)量將達到8 060 EB，占全球數(shù)據(jù)總量的18%。因此，重復數(shù)據(jù)刪除技術需要向分布式存儲結構轉變[4]，以適應云數(shù)據(jù)中心環(huán)境下的按需獲取、彈性增長、快速部署等多方面要求。

1 重復數(shù)據(jù)刪除技術綜述

重復數(shù)據(jù)刪除技術是一種基于數(shù)據(jù)自身的冗余度來檢測數(shù)據(jù)中是否有相同的對象，然后只傳輸和(或)存儲唯一的數(shù)據(jù)對象副本的數(shù)據(jù)去冗余技術。根據(jù)不同的區(qū)分原則，一般可以把重復數(shù)據(jù)刪除技術進行不同的分類。該技術的主要工作原理如圖1所示。

圖1 重復數(shù)據(jù)刪除技術工作原理示意

在單一存儲結構形式下[5]，平均響應時間、I/O吞吐量和重復率是評價重復刪除系統(tǒng)效率的三個重要指標。

(1)平均響應時間：是指完成單位大小的數(shù)據(jù)塊重復刪除操作所需要的平均延遲時間。這個時間包括對數(shù)據(jù)塊指紋進行內存查詢和磁盤查詢的開銷，以及查詢失敗之后的存儲開銷。平均響應時間越短，重復數(shù)據(jù)刪除系統(tǒng)效率越高。

(2)I/O吞吐率：是指單位時間內傳輸?shù)臄?shù)據(jù)量。由于重復刪除系統(tǒng)要在正常的數(shù)據(jù)讀寫時間之外，額外增加了重復刪除的操作，因此比起單純的磁盤數(shù)據(jù)傳輸，吞吐率會有所降低。吞吐率越高，重復數(shù)據(jù)刪除系統(tǒng)效率越高。

(3)冗余度：冗余度也稱重復率，是指應該刪除的重復數(shù)據(jù)字節(jié)數(shù)與未刪除之前的全部數(shù)據(jù)字節(jié)數(shù)的比值。一般來說，冗余度越高，重復數(shù)據(jù)刪除的經(jīng)濟效益越好。

2 云存儲環(huán)境下的重刪系統(tǒng)

在云數(shù)據(jù)中心存儲環(huán)境下，數(shù)據(jù)存儲有兩個顯著變化：

第一，云存儲是由大量的廉價存儲設備構成的龐大存儲中心，具有離散性和低可靠性的特點，需要依賴特別的方法將這些廉價設備聚合成一個高可靠性、高擴展性的資源池。因此，對單獨某個廉價設備的評價指標，并不適合直接用于評價存儲結構整體的存儲性能表現(xiàn)。

第二，云存儲是直接面向用戶評價的，挑剔的云用戶要求云存儲具備歷史數(shù)據(jù)版本多、數(shù)據(jù)保存期延長、備份時間窗口縮短和實時故障恢復要求高四個特點[6]，評價指標需要考慮這些新增的評價維度。

單一存儲和云存儲的區(qū)別如表1所示。

表1 單一存儲和云存儲的區(qū)別

由此可見，云數(shù)據(jù)中心下的重復數(shù)據(jù)刪除技術，必須在原有機制下進行改進，提高執(zhí)行效率、縮短操作時間，并且保證數(shù)據(jù)可靠性。

2.1 指紋查詢模式改進

在云數(shù)據(jù)中心下，數(shù)據(jù)量大幅度提升，單一服務器下TB規(guī)模的數(shù)據(jù)量，在云數(shù)據(jù)中心下可能達到PB級別規(guī)模，直接導致指紋庫的增大。從而對數(shù)據(jù)塊指紋查詢提出新的要求。

以重復數(shù)據(jù)刪除系統(tǒng)的指紋庫設計為例。1 TB數(shù)據(jù)量的單一服務器下，按照每個數(shù)據(jù)塊固定大小為4 MB進行切分，且每個數(shù)據(jù)塊的數(shù)據(jù)指紋是64 bit(8 Byte)，那么指紋庫的大小只有2 MB，這就可以將指紋庫常駐內存中，從而減少平均響應時間。

但是當數(shù)據(jù)量達到1 PB規(guī)模時，同樣的指紋庫將達到2 GB，如果繼續(xù)將指紋庫常駐內存，就必須占據(jù)較大的內存資源，影響云服務的SLA(service level agreement，服務等級協(xié)議)。

所以，為了保證云用戶的SLA，提高服務響應速度，在云數(shù)據(jù)中心環(huán)境下，需要兼顧數(shù)據(jù)塊切分和指紋庫查詢的綜合效率，而不能照搬單一服務器存儲結構下的模式。

2.2 數(shù)據(jù)容錯機制改進

在云數(shù)據(jù)中心環(huán)境下，分布式存儲規(guī)模不斷增大，云數(shù)據(jù)中心采用虛擬化技術，將數(shù)以萬計的服務器共同構成一個資源存儲池，用戶按需申請。每個用戶的數(shù)據(jù)，可能存放在多個不同的物理服務器上，一個物理服務器中也可能保存著多個用戶的數(shù)據(jù)。因此，跨網(wǎng)絡、跨服務器形勢下的數(shù)據(jù)容錯問題就變得比較復雜。

數(shù)據(jù)容錯機制一般可以分為兩種：基于復制的數(shù)據(jù)容錯和基于糾刪碼的數(shù)據(jù)容錯。在單一存儲結構下，數(shù)據(jù)容錯基本上可以簡單采用基于復制的策略來完成，以更多的空間消耗來保障可靠性。在云數(shù)據(jù)中心下，本身巨大的數(shù)據(jù)量直接造成基于復制的備份技術成本倍增，更多的存儲設備不但意味著更多的設備成本，還意味著更多的人力、電力、管理等運維成本，這常常是企業(yè)不得不考慮降低的資源消耗。所以，基于糾刪碼的數(shù)據(jù)容錯逐漸為大家所重視。

2.3 資源可擴展性改進

存儲設備的擴展，一般分為垂直擴展和水平擴展兩種方式。垂直擴展是指對原有設備進行替換，用新的、性能更高的設備來替代原有設備。水平擴展是指在原有設備的基礎上，通過更新或是添加部件的方式提升原有存儲設備的性能。

在單一存儲結構服務器中，水平擴展的次數(shù)是比較有限的，大多數(shù)情況下只能選擇垂直擴展的方式，這降低了設備的利用率。

云數(shù)據(jù)中心模式下，可以通過增加同構(或異構)設施設備的方式近乎線性地擴充IT資源，而且擴展的過程中，不需要停止目前正在進行的服務。這種水平擴展的方式，正是云計算區(qū)別于其他計算范式的重要特點之一。

所以，為了適應新的計算范式，云數(shù)據(jù)中心環(huán)境下的重復刪除技術還要具備可水平擴展的能力，且在擴展的情況下盡可能做到“數(shù)據(jù)本地化與負載均衡”的兼顧

3 云存儲環(huán)境下重刪系統(tǒng)加速技術

根據(jù)前面對云存儲環(huán)境下重復刪除技術的新要求，需要有針對性地設計加速技術，使得重刪系統(tǒng)可以更加有效地遷移到云存儲環(huán)境下。應該從以下幾個方面開展研究。

3.1 指紋查詢優(yōu)化

3.1.1 算法優(yōu)化

由于指紋庫的增大，只能將指紋庫中的一部分置入內存，顯然的是，如果置入部分選擇得當，那么查詢命中率高，可以在一定程度上節(jié)約查詢時間。理想狀態(tài)下，應該選擇那些最近最有可能被查詢的指紋來置入內存。

憑空預測即將查詢哪一個數(shù)據(jù)塊的指紋是沒有道理的，但是云計算的VIM(virtual instrument monitor，虛擬設備監(jiān)控器)采集了大量的虛擬機運行狀態(tài)數(shù)據(jù)，可以通過對CPU、內存和磁盤I/O運行狀況的監(jiān)控，收集虛擬機運行數(shù)據(jù)，并對此進行必要的處理，從而預測哪一個虛擬機可能有重復數(shù)據(jù)指紋比對的需要，進而提前將該虛擬機數(shù)據(jù)的相關指紋數(shù)據(jù)置入內存庫中。其工作原理如圖2所示。

圖2 最近最有可能使用(LPU)查詢算法工作原理示意

3.1.2 硬件優(yōu)化

算法上的優(yōu)化可以保證盡可能高地提升查詢的命中率，但是一旦發(fā)生未命中情況，就必然面臨額外的磁盤查詢和可能的內存換入換出操作，這就不可避免地影響磁盤I/O的速度。

在云數(shù)據(jù)中心環(huán)境下，通常一個物理服務器上會承載多個虛擬機以服務多個不同用戶。每個用戶的數(shù)據(jù)在邏輯上雖然是隔離開的，但是實際在物理服務器層面看來，都是存在于一個存儲設備中。因此，可以考慮在物理服務器的內存和磁盤設備之間引入SSD作為cache。具體結構如圖3所示[7]。

SSD作為一種新型存儲介質，跟傳統(tǒng)的磁盤相比速度更快，其順序讀寫速度約為機械硬盤的3～5倍,隨機讀寫IOPS約為機械硬盤的100～1 000倍[8]。更適用于應對大規(guī)模的隨機讀寫I/O負載。所以，如果將指紋庫加載到SSD中，即使出現(xiàn)了未命中現(xiàn)象，從SSD中進行指紋查詢，在速度上也比磁盤中進行查詢更快。

圖3 虛擬環(huán)境下SSD做cache的結構示意

3.2 基于糾刪碼的容錯機制

在提高存儲系統(tǒng)可靠性方面，還有一種普遍采用的技術就是糾刪碼技術。糾刪碼技術可以節(jié)約磁盤空間，但是計算耗時相對較長，并且任何數(shù)據(jù)位的變化，都必須重新計算糾刪碼，所以，對計算所需的時間比起其他重復刪除技術而言，沒有綜合優(yōu)勢，一般只是在空間約束特別嚴格的環(huán)境下才得以使用。

但是云數(shù)據(jù)中心環(huán)境下，計算能力已經(jīng)不能構成制約，云計算的計算范式跟以往的計算方式相比，計算能力上已經(jīng)有了巨大的變化，因此，利用糾刪碼技術來加速重復數(shù)據(jù)刪除方面，就有了新的可能。

但是在錯誤恢復方面，基于復制的容錯和基于糾刪碼的容錯的網(wǎng)絡開銷差異還是很大。當一個數(shù)據(jù)塊發(fā)生錯誤，基于復制的容錯只需要在網(wǎng)絡中下載一個同樣大小的數(shù)據(jù)恢復即可。而基于糾刪碼的方法就要刪除k個數(shù)據(jù)來計算得以恢復，這就需要更多的網(wǎng)絡開銷，占用更多的內部網(wǎng)絡帶寬。

因此，還需要進一步降低基于糾刪碼的數(shù)據(jù)修復成本，把數(shù)據(jù)修復所耗費的CPU資源和網(wǎng)絡資源降下來，這也是目前研究的熱點方向。

3.3 數(shù)據(jù)去重的方式選擇

3.3.1 數(shù)據(jù)去重的三個類型

數(shù)據(jù)去冗余的時機一般分為3種[9]：先備份再去重策略(deduplication after backup，DAB)、先去重再備份策略(deduplication before backup，DBB)和邊備份邊去重策略(deduplication during backup，DDB)。

去冗余的時機選擇恰當與否，直接關系到用戶體驗。根據(jù)Aberdeen Group的調查“頁面的顯示速度每延遲1 s，網(wǎng)站訪問量就會降低11%，從而導致營業(yè)額減少7%，顧客滿意度下降16”；Google發(fā)現(xiàn)“相應時間每延遲0.5s，查詢數(shù)將會減少20%”；Amazon發(fā)現(xiàn)“響應時間每延遲0.1 s，營業(yè)額下降1%”。下面是三種不同的去冗余方式所占用的總耗時差異對比，如表2所示。

表2 去冗余操作時機選擇的耗時區(qū)別

三種不同策略的總耗時分別為：

其中：

(1)Td、Ts、Tt分別表示數(shù)據(jù)塊指紋計算的耗時、數(shù)據(jù)塊本地存儲的耗時和數(shù)據(jù)塊網(wǎng)絡傳輸?shù)暮臅r；

(2)n表示需要備份的所有數(shù)據(jù)的數(shù)據(jù)塊數(shù)量，m表示經(jīng)過指紋比對之后需要更新備份的數(shù)據(jù)塊的數(shù)量。顯然(n-m)/n就是數(shù)據(jù)的重復率；

(3)該計算耗時是在假設所有的數(shù)據(jù)塊大小一致的情況下做出的分析結果?；诨瑒哟翱诘暮臅r分析可以類比得出。

3.3.2 云用戶的三種類型

根據(jù)用戶從云數(shù)據(jù)中心獲取資源的類型不同，通?？梢詫⒂脩舴盏念愋头譃?類：網(wǎng)絡密集型、計算密集型和存儲密集型。

網(wǎng)絡密集型：此類用戶對虛擬網(wǎng)絡傳輸?shù)膸?、延遲要求都很高，而且隨著觀看直播用戶數(shù)量的動態(tài)變化，負載也會隨之波動，一旦負載稍微高出資源承載能力，都會造成視頻卡頓，影響用戶體驗。同時，此類視頻數(shù)據(jù)信息本身冗余度很高，一般而言連續(xù)的畫面幀之間只有細微的變化，所以，DDB方式是這種情況下的首選。網(wǎng)絡直播[10]、視頻監(jiān)控[11]通常屬于這種類型。

計算密集型：此類用戶通常是批量地將數(shù)據(jù)輸入到虛擬服務器上，然后虛擬服務器自主進行計算，在操作過程中幾乎不再與用戶產(chǎn)生數(shù)據(jù)交互。因此，針對這種類型的用戶，數(shù)據(jù)去重的方式可以選擇DAB方式，科學計算通常屬于這種類型[12]。

存儲密集型：此類用戶通常是有大量突發(fā)性的數(shù)據(jù)讀寫需要完成，單次操作所耗費的時間都不是很長，但是對網(wǎng)絡帶寬要求較高[13]。針對此類用戶，數(shù)據(jù)去重的時機可以根據(jù)數(shù)據(jù)量的大或小來適當?shù)剡x擇DAB或DBB方式，云存儲、Web服務通常屬于這種類型。

4 結束語

云數(shù)據(jù)中心環(huán)境下的重復數(shù)據(jù)刪除技術，與單一存儲結構模式在指紋查詢模式、數(shù)據(jù)可靠性保證和備份方式選擇等方面都提出了更多樣化的要求，因此，有必要根據(jù)云服務的特點來設計具有云特征的重復數(shù)據(jù)刪除技術，從而達到節(jié)約提高云數(shù)據(jù)中心存儲效率、提升云用戶服務感受的目的。