基于重復數據刪除技術的霧存儲數據去冗余方案

陳思佳 溫 蜜 陳 珊

(上海電力大學計算機科學與技術學院 上海 200090)

0 引 言

當今社會數字化信息呈爆炸式增長，《數據時代2025》白皮書中預測，2025年全球的數據量將達到163 ZB，是目前的10倍之多。數據量的劇增和泛濫對數據存儲管理技術提出了巨大的挑戰，如何高效地管理和存儲數據已成為研究熱點。微軟[1]和EMC[2-3]生產的主存儲系統和二級存儲系統中，分別有50%和85%的冗余數據，隨著時間的推移，冗余數據的比例也會成倍上升，企業在存儲這些的數據時所需要的開銷也是巨大的。

如此龐大的數據對傳統存儲系統提出了挑戰。于是技術人員將目標轉向容量更大，成本更低廉的云存儲系統。云存儲架構集成了大規模用戶數據，數據中會存在許多重復數據，因此數據去重對于維護數據開銷具有重要的意義。

根據IDC最近的一項研究[4]表明，目前近80%的企業正在尋求存儲設備的重復數據刪除技術，從而消除設備中的冗余數據。重復數據刪除技術是一種數據縮減技術，在單機設備和云平臺中都有廣泛應用，其主要作用于文件內部和文件之間的冗余數據，通過與源數據進行對比，刪除相同的數據塊(文件)，達到在磁盤中存儲更多數據的目的。在工業界Datadomain的DDFS、IBM Diligent、EMC的Avarma、Veritas的PureDisk以及Commvault的Simpana都是比較知名的重復數據刪除產品，這些產品通常可以達到20∶1的重復刪除率。數據分塊和指紋管理是控制重復數據刪除性能的流程中關鍵的技術部分。傳統的重復數據刪除模塊是將數據流進行分塊，分塊的方式有多種：可變大小的分塊(CDC)、固定大小的分塊(fixed-size partion)以及兩者的混合，即滑動分塊(sliding block)。根據哈希函數(MD-5或SHA-1)計算每個數據塊的Hash值(我們稱之為指紋)，與已有指紋表中的指紋進行對比，判斷是否為重復數據塊。這一系列的指紋查詢操作會導致指紋表在內存中的隨機讀取，每次讀取都存在磁盤訪問，從而增加輸入和輸出(I/O)。

云存儲采取的是數據外包模式，許多云服務提供商為了降低成本，往往會將數據中心建立在低成本的偏遠地區，當云服務器距離客戶較遠時，必然會增加數據傳輸延遲。傳輸過程中的重復數據也會占用大量的網絡帶寬，造成數據中心和移動端的I/O瓶頸。據最新研究結果顯示，在各類云存儲產品中數據的重復率達到60%，龐大的重復數據對云中心去重同樣造成很大壓力。

為了解決現存的云存儲去重問題，并且滿足物聯網發展的需求，便產生了一種新的體系結構。即在終端和云數據中心之間加入網絡邊緣層，配上帶有存儲功能的小型服務器或路由器，將不需要放到云端的數據在邊緣層直接進行處理和存儲。其主要思想是將一些數據中心的任務遷移到邊緣服務器，目的是減少云端去重壓力，提升數據傳輸速率，從而快速響應底層設備的需求，減少用戶響應時間，降低時延，由此便誕生了“霧計算”[5]。

霧作為一種小型“云中心”，對附近的移動終端用戶或邊緣用戶的數據進行存儲、通信、控制、管理和測量。與云存儲不同的是，霧節點處理大多是無需放在遠端云數據中心的用戶經常訪問的數據。隨著連接霧節點的移動終端不斷變化，在霧節點中同樣存在存儲過程中產生的數據冗余問題。目前大部分去重方案為云數據中心這種分布式環境，去重對象多為數量較為龐大的數據，用來滿足云數據中心下按需分配、彈性增長、快速部署等方面的要求。對于霧環境中輕量級存儲設備目前還沒有提出重復數據刪除方案。因此，本文主要針對霧節點中的輕量級服務器提出了重復數據刪除方案[6]，在數據指紋的生成和查詢兩個關鍵技術上，對于霧服務器中頻繁訪問的數據在內存中建立數據查詢機制。方案的貢獻有以下幾方面：

(1) 為了實現高效查詢，針對霧節點中訪問頻率較高的數據，在內存中構建索引表，每個索引值對應的紅黑樹作為存儲數據指紋的結構，減少磁盤與內存間的I/O，提高查詢速度。

(2) 為解決計算數據指紋時產生的Hash沖突問題，利用循環冗余碼(CRC)技術判斷具有相同數據指紋的數據塊是否重復，并將沖突數據塊用鏈表結構存儲在指紋節點中。

(3) 為防止系統的突然崩潰，提出在內存中持久化保存指紋表，分為內存某一時刻的映射文件和記錄更新的日志文件。通過固定時刻刷新內存將內存中的指紋表永久保存在磁盤的映射文件中，新的數據指紋插入時，將更新情況記錄在日志文件中。一旦系統崩潰重啟，內存中的數據會消失，此時磁盤中的兩個文件合并重新構建內存中的指紋表，同時兩個文件內容清空重新記錄。

1 預備知識

1.1 去重相關研究

重復數據刪除研究過程主要包括基于粒度的劃分、指紋的查詢、數據去冗余的時機。

Won等[7-8]發現分塊是重復數據刪除過程的主要開銷之一。基于粒度的重復數據刪除技術包括基于文件級的、塊級的[13-14]和字節級的。基于文件級的情況比較少見，只有當兩個文件內容完全相同時，才能利用去重技術刪除，所以這種方式的去重率很低。基于字節級的方式在數據量非常龐大的情況下，顯然也是不現實的，這種方式會耗費過多CPU資源，運算效率不理想。基于塊級的粒度是目前應用最廣泛的，散列值(MD-5,SHA-1等)可以作為唯一塊的標識，概括數據塊的內容，無需對數據塊進行讀取，從而提高查詢速度。

在指紋管理方面，也提出了許多方法。第一個方案就是Bloom等[9]提出的主存儲過濾器，即布隆過濾器(Bloom Filter)。Bloom Filter由k個散列函數和m位的數組構成，當插入n個元素時，只需要判斷該元素通過k個Hash函數映射在數組的點是否為1，若k個點都為1，則表示存在，否則不存在。其好處在于在查找指紋是否重復時可以避免不必要的磁盤I/O，同時Bloom Filter占用空間小，所以廣泛應用于備份[10]、分布式文件系統[11]和Web代理[12]。但Bloom Filter存在假陽性，即返回的結果不一定正確，存在概率性。誤報率如下式所示：

(1)

另一種方案就是指紋表存放數據指紋。利用傳統搜索結構，例如B+樹或散列表，查找序列中的相鄰指紋不可能以聚類方式存儲，這樣就會導致指紋的隨機讀取，導致查詢效率降低。

數據去冗余的時機一般分為3種：先備份再去重策略(Deduplication Ater Backup strategy，DAB)、先去重再備份策略(Deduplication Before Backup strategy，DBB)和邊備份邊去重策略(Deduplication During Backup strategy，DDB)。DBB在傳輸前將數據進行去重，可以有效提高傳輸效率，節省帶寬。

1.2 數據結構分析

對于在內存中的查找結構中，平衡二叉樹是使用較為廣泛的檢索樹。AVL樹和紅黑樹都是平衡二叉樹的一種，與AVL樹相比，紅黑樹可以確保沒有一條搜索路徑會比其他路徑長2倍，因而是近似平衡的。所以相對于嚴格要求平衡的AVL樹來說，它保持平衡的插入和刪除旋轉次數較少，從而保證了系統運行時間，總體性能優于AVL樹。AVL樹與紅黑樹性能對比如表1所示。

表1 AVL樹與紅黑樹性能對比

2 系統模型

霧計算框架如圖1所示，結構分為三部分：移動終端區、霧計算區和遠端云計算區。霧計算位于云服務器和移動終端之間。作為云節點的服務者，移動終端區的執行者，霧計算在框架中為上下兩層服務，起到了承上啟下的作用。

圖1 系統結構圖

系統結構三個部分的作用如下：

? 移動終端區：移動可連接局域網絡設備，如手機、電腦、平板電腦、智能手表等。

? 霧計算區：考慮到輕量級移動設備的有限存儲空間和計算能力，霧計算區接收來自移動終端的請求/服務，處理和存儲無需放在云端的少部分訪問頻繁的數據。每個霧計算區由霧管理員(Fog Manager)、進程日志管理服務器(Services Logging Server)、霧計算服務器(Fog Computing Server)和霧存儲服務器(Fog Storage Server)四部分構成。其在霧節點中的功能如表2所示。

表2 系統組成成員

? 遠端云計算區：大規模虛擬化的計算機集群，接收來自霧計算區的請求/服務。當霧計算區沒有可用虛擬機容量處理終端區的請求服務時，會將服務委托給云計算。云數據中心將請求分配給有足夠容量完成服務的其他霧節點服務器。作為系統的上層結構，其成員功能與霧計算區大致相同。但云數據中心作為由大量服務器聚合而成的高可靠性、高拓展性的資源共享池，其接收到的用戶請求遠超小規模的霧節點。故云節點還包括了第三方云服務器，其功能如表2所示。

進程日志管理器中的兩個記錄霧節點進程和當前虛擬機可用容量的兩張列表內容的樣例，如表3、表4所示。

表3 虛擬機資源占用表

表4 服務(請求)進程表

霧計算[15]的理念是將一些輕量級的智能處理設備部署在靠近移動用戶的地方，方便用戶可以在比較近的距離范圍內直接連接霧服務器，通常霧服務器與用戶是一跳(one-hop)的通信距離。霧節點存儲和處理的數據多是在一定的距離內用戶經常訪問的數據，將這些數據存儲在霧節點中，用戶無需將任務請求發送到遠端的云數據中心進行處理，這樣避免了發送過程中產生的網絡延遲，進而提升數據傳輸速度，減少云服務提供商的計算壓力。

購物中心作為人流量較大的公共場所，用戶對與商場有關的購物信息會有較高的訪問頻率，包括餐廳的類型、位置、用戶評價，品牌商店的購物信息、位置、產品價格等。將購物中心的詳細信息放到云數據中心，讓顧客通過手機實時獲取云端上存儲的商場信息是一種可行方案，但是存在不足之處。首先用戶通過手機訪問云端具有不穩定性，會受到信號的影響，而且云端信息需要經過網絡多路轉發才能到達用戶，會影響用戶的服務體驗。如果在商場的每個角落里部署霧服務器，用戶在訪問這些數據時就會避免查詢延遲、信號弱等情況，提高了用戶的購物體驗。

3 基于霧存儲的去重方案

霧存儲中的數據通常是用戶經常訪問和查詢的，針對這些高訪問頻率的存儲數據，霧存儲系統中同樣存在同一文件的多個副本，以及文件中出現重復數據塊的問題。目前已經提出許多有效的重復刪除機制來解決文件冗余副本問題。這些方案通常解決的是分布式云存儲中數據量達到PB級以上的數據，大規模的數據直接導致指紋表增大。龐大的指紋表讀取時只能將一部分內容置入內存，只有置入的部分得當，才能保證查詢的命中率，并且這種方式會占用大量的隨機磁盤訪問。為了防止磁盤的隨機訪問，我們提出將霧計算中訪問頻繁的數據指紋表保存在內存中進行讀取，這樣可以減少磁盤I/O。利用紅黑樹作為數據指紋表結構，提升查詢效率。

3.1 方案流程

本文提出的數據指紋查詢方案，將完整的指紋表保存于內存中，將非重復數據塊置于磁盤中。當判斷數據指紋是否重復時，可以直接在內存中進行查詢，無需磁盤I/O讀取。若指紋表中沒有相同指紋，即為非重復數據塊指紋，插入指紋表中。若指紋表中存在相同指紋，將該指紋的數據塊與指紋表中相同指紋對應的數據塊的循環冗余碼(CRC)進行比較。如果不同，判斷該數據塊為非重復數據塊，保存在該指紋的數據塊鏈表中；反之，返回該數據塊的地址指針。方案流程如圖2所示。

圖2 方案流程圖

3.2 索引表

通過將數據指紋進行哈希計算得到索引值(由0到n構成的整數)。將數據分成非重疊等分數據塊b1,b2,…,bn。運用MD5哈希算法計算每個指紋，f1=h(b1),f2=h(b2),…,fn=h(bn)。將數據指紋再次進行哈希計算，得到整數型索引值，i1=h(f1),i2=h(f2),…,in=h(fn)。用戶查詢冗余數據塊時，計算該數據塊的索引值，查詢該索引值下的指紋表。遍歷索引表的時間復雜度為O(1)，索引表如圖3所示。

圖3 索引表生成

3.3 基于紅黑樹的指紋查詢

紅黑樹作為數據指紋的搜索結構，與其他在內存中的數據結構相比，具有較低的時間復雜度。與在磁盤中的數據結構相比，查詢過程中降低了磁盤I/O讀取，加快查詢速度。遍歷紅黑樹，找到數據塊指紋的所在地址，避免存在哈希沖突情況，在計算數據塊指紋的同時，計算出數據塊的循環冗余碼附加在數據后面。當出現數據指紋相同的情況時，比較數據塊的CRC。若相同，表示該數據塊重復；否則，存在哈希沖突，將數據塊保存在其指紋的鏈表中(鏈表中保存的是指紋相同的不同數據塊)。若沒有找到與該數據塊指紋相同的指紋，則數據塊為非重復數據塊，將其插入在相應的紅黑樹節點中。紅黑樹的指紋插入和查詢過程如圖4所示。

圖4 指紋的插入與查詢

3.4 內存中持久化保存指紋表

為了保證數據結構在內存中的持久性，防止操作系統在崩潰狀況下內存中數據消失，指紋表原有的數據信息通過映射的方式寫入映射文件，在對數據指紋表做更改前，將數據指紋的插入操作信息寫入日志文件。由于日志是立即持久化的，可以作為恢復其他所有持久化結構的可靠來源。當系統發生崩潰，內存中的內容消失，此時再次啟動映射文件和日志文件中的內容合并成新的數據結構存入內存中，清空文件內容，新的指紋表映射到映射文件，日志文件記錄下一次的數據變更，為數據提供容災保障。

算法1介紹了數據流等分塊的過程。將數據流作為去重系統的輸入，根據設置的數據塊大小(size)將數據流進行等分切塊，將等分后的數據塊傳入列表中輸出。

算法1數據流定長分塊

輸入:數據流

數據流長度：len

等分數據塊的大小：size

begin:

list=[]

count=len/size+1

//等分的數據塊數量

for i in count do

將等分后的數據塊依次放入list中

end for

end

輸出：list={b1,b2,…,bn}

//每個數據塊的首地址

算法2介紹了指紋和循環冗余碼的生成過程。等分后的數據塊作為輸入。MD5、SHA-1、SHA-256都是目前較為常用的散列算法，我們選擇生成指紋較小的MD5算法，得到f1=h(b1),f2=h(b2),…,fn=h(bn)。我們選擇應用最廣泛的crc32作為循環冗余碼的生成公式，得到的CRC值附加在數據后面。

算法2生成數據指紋和CRC

輸入：等分后的所有數據塊bx

數據塊數量：num

指紋生成公式(MD5)：h

CRC生成公式：crc32

begin:

for j in num do

數據指紋fx=h(bx)

CRC碼cx=crc(bx)

end for

end

輸出：數據塊指紋fx和CRC碼cx

算法3介紹了索引表的生成以及指紋的插入、查詢過程。MD5算法得到的數據塊指紋作為輸入，重哈希確定索引表中索引值的位置，遍歷索引值對應的指紋表，若沒有相同的指紋，確定該數據塊為非重復塊，指紋插入指紋表中。若存在相同指紋，通過比較數據塊的CRC值判斷是否存在哈希沖突情況，如果兩個數據塊的CRC值相同，則為重復數據塊，返回其數據塊所在地址指針，反之，則為非重復數據塊，將該數據塊插入其指紋所在的鏈表中。

算法3生成索引表和指紋插入、查詢

輸入:生成的數據指紋fx

數據指紋數量：n

索引表的索引數量：m

索引值對應的紅黑樹：T

計算索引的二次哈希公式：h1

CRC生成公式：crc32

begin:

索引值ix=h1(fx) % m

for i in n do

for j in m do

if fxin T(ix) then

//T(ix) 表示索引ix對應的紅黑樹

if crc32(fx)==crc32(T(fx)) then

//T(fx)表示紅黑樹中指紋fx連接的數據塊，返回數據塊所在

//地址指針

else

判斷為非重復數據塊，將指紋插入指紋表中，存入數據塊

end if

else

判斷為非重復數據塊，將指紋插入指紋表中，存入數據塊

end if

end for

end for

end

4 實驗分析

實驗運行平臺為Windows 10系統，Intel core i5 CPU，8 GB內存，處理器速度2.30 GHz，使用Python編程實現。實驗使用名為gcc-3.4.1和emacs-20.7的數據集，分別為19.4 MB、34.1 MB。指紋搜索效率通過計算搜索一個指紋所需的時間即查找延遲來判定，對數據進行10 KB、100 KB、1 MB、10 MB定長分塊。在這兩個數據集上對比Prefix indexing與DeFog，結果如圖5、圖6所示，可以看出，DeFog指紋搜索效率分別提高54.1%、38.78%。

圖5 emacs-20.7指紋查詢時間

圖6 gcc-3.4.1指紋查詢時間

霧計算作為云計算的邊緣延申，目前沒有針對其存儲數據的去重方案，DeFog根據霧環境的特征，對已有的prefix[13]方案進行了改進。DeFog減少了磁盤I/O，在不同的分塊情況下，查詢時間都有一定的減少。數據塊為10 KB時，gcc-3.4.1數據集的查詢速率從9.8 ms降至1.21 ms，效率提高了87.7%。隨著分塊大小增加，數據塊的個數減少，兩方案的查詢時間趨于相同。

圖7、圖8表明在運行時間上DeFog與現有的方案相比，效率也有了一定的提高。將數據流按100 KB、1 MB、10 MB進行分塊，索引表長度為1 000。emacs-20.7數據集中，當數據塊大小為10 MB時，DeFog的運行時間在240 ms，比現有的方案減少了81.2%。但在數據塊為1 MB的情況下，DeFog在兩個數據集上的運行時間與原有的方案相比沒有太大的改進，這體現了選取合適的數據分塊大小對實驗結果有一定的幫助。

圖7 emacs-20.7運行時間

圖8 gcc-3.4.1運行時間

在數據集中進行第一次實驗時，因為當前指紋表為空，生成的大部分指紋都是非冗余的，多為插入操作，無需檢查冗余數據。第二次實驗在指紋表非空的情況下進行，需要判斷重復數據塊，因此延遲時間會隨著冗余數據塊數量的增加而變長。但由于指紋表全部保存在內存中，不會出現磁盤中部分指紋表隨機讀取的情況，確保了查詢時間。

索引表對指紋的插入與查詢的影響如圖9所示。利用索引表可以迅速定位到指紋所在的紅黑樹，進而判斷指紋是否重復。索引表是鏈式結構，讀取時間基本可以忽略，與沒有索引表的方案相比，效率有所提高。但索引表的長度對運行時間影響不大，兩個數據集在索引表為10、100、1 000時運行時間基本相同。

圖9 索引表對時間的影響

霧計算作為云計算在網絡邊緣的延伸，其與云計算在原理是相似的，但在環境布局上也有不同之處，其方案不能直接應用于霧計算中。因此，將DeFog與近年來提出的方案進行性能對比，結果如表5所示。

表5 方案性能對比

DeFog適用于霧環境，在數據量較大且單一的情況下能夠加快查詢速度，防止查詢延遲。

5 結 語

本文提出了在霧服務器內存中置入紅黑樹作為指紋插入與查詢的數據結構，從而實現重復數據刪除系統(DeFog)。為防止系統突然崩潰，提出用日志文件記錄指紋的更新，為數據容災提供保障。所提出的系統通過減少指紋查找時間和消除冗余數據來提高重復數據刪除系統的性能和效率。根據實驗證明，固定分塊對冗余檢測有較好結果，并且可以減少一定的計算開銷。索引表在一定程度上加快了指紋查詢的速度，時間復雜度為O(1)。紅黑樹作為指紋表與其他數據結構相比在插入和查詢時間上都比較短，適合作為存儲指紋的結構。

霧節點的出現一定程度上緩解了云計算中心的壓力，DeFog針對霧服務器中頻繁訪問的數據提出了重復數據刪除技術，減少了網絡數據傳輸量，優化系統的整體功能。在人流較大、對通信速度要求較高的霧節點中，可以加快冗余查詢速度，保證去重效率。實驗證實，本文的方案更適用于訪問頻繁的小范圍數據，通過更快的數據結構提高整體性能。