基于文件路徑的重復數據刪除集群的數據路由策略

王麗芳, 張志珂, 蔣澤軍, 蔡小斌, 彭成章

(1.西北工業(yè)大學 計算機學院, 陜西 西安 710072; 2.國家電網 河南省電力公司, 河南 鄭州 450052)

人類每年產生的數據量以指數級別的速度快速增長。云存儲供應商、第3方備份服務和社交網絡等會產生大量數據[1]。例如，著名的社交網絡Facebook每天存儲8 300萬張照片，大約是200TB至400TB數據[2]。并且，由于越來越多的用戶使用這些服務，所產生的數據量也迅速增加。這些企業(yè)所存儲的數據是它們所提供服務的關鍵基礎。數據丟失會嚴重降低服務質量，從而降低企業(yè)的利潤。為了避免數據丟失，數據中心必須在幾年的備份周期內定期備份所有數據(通常是每周一次全備份)，并且保證在需要時能提供數據，另外，一些法律也規(guī)定數據中心必須定期備份所有數據[3]。

重復數據刪除技術能夠從已經存儲的數據中找到重復的數據，不存儲重復的數據，只存儲新數據。因此，重復數據刪除技術可以大量縮減存儲使用量，使基于磁盤的數據備份成本與磁帶相當甚至更低。這就使基于磁盤的重復數據刪除技術越來越流行，逐漸替代基于磁帶的數據備份技術[4-8]。單節(jié)點重復數據刪除的容量是有限的，目前最先進的重復數據刪除可以存儲幾十PB(petabyte)的數據[3]。然而，數據中心的備份需求已經超過單節(jié)點重復數據刪除的容量[1]。并且，隨著越來越多的企業(yè)把自己的存儲外包給云環(huán)境，數據中心的數據備份數量會繼續(xù)增長。

重復數據刪除集群可以滿足數據中心越來越大的數據備份需求[3,9-11]。重復數據刪除集群的關鍵問題是如何把數據合理分配到各個重復數據刪除節(jié)點上，即數據路由策略。重復數據刪除集群的數據路由策略的目標是：①保證較高的重復數據刪除率；②保證各個重復數據刪除節(jié)點的負載平衡。重復數據刪除率是待存儲的數據量與存儲使用量的比值，用于評估重復數據刪除的存儲利用率。已有的重復數據刪除集群的數據路由策略使用文件或者數據段的所有數據塊簽名中最小的數據塊簽名計算目標節(jié)點[3,9]，稱作MCS(minimum chunk signature)路由策略。對于包括幾個節(jié)點的小規(guī)模重復數據刪除集群，這種方法可以保證較高的重復數據刪除率。但是，當重復數據刪除集群的規(guī)模較大時，這種方法的重復數據刪除率急劇下降，遠遠低于單節(jié)點重復數據刪除[3]。

本文提出一種基于路徑的重復數據刪除集群的數據路由策略，稱作DRSD(data routing strategy based on directories)。文件的路徑是一種文件系統(tǒng)語義，指的是文件系統(tǒng)路徑。在連續(xù)的數據備份版本中，數據的目錄結構通常是穩(wěn)定的，那么具有相同目錄名稱的文件集很有可能包含一些相同的數據。用文件的路徑輔助數據路由可以把相關的或者相似的數據分配到同一個節(jié)點上，從而提高重復數據刪除率。文章使用文件路徑設計了一種數據路由策略。構建一個路徑路由索引保存路徑相關的路由信息。當需要路由數據時，先查詢路徑路由索引是否存在改路徑的路由信息，如果存在，就直接使用該路由信息路由數據到目標節(jié)點；如果不存在，就使用文件的最小塊簽名計算目標節(jié)點。

收集了一個來自真實世界的數據集，包含564個版本的Linux源代碼檔案。用它來評估提出的重復數據刪除集群的數據路由策略DRSD。實驗結果表明，對于各種不同的節(jié)點數量，DRSD的重復數據刪除率都明顯高于MCS，并且接近單節(jié)點重復數據刪除。當節(jié)點數量是64時，DRSD的重復數據刪除率比MCS高35%。此外，當節(jié)點數量小于8時，DRSD的數據傾斜率與MCS幾乎相同。

1 設 計

1.1 架 構

圖1描述了重復數據刪除集群的架構。備份服務器負責對數據的分塊工作，這種方式可以節(jié)約重復數據刪除服務器的計算資源。但是，這不是必需的，也可以由重復數據刪除集群的存儲節(jié)點負責數據分塊工作。備份服務器首先把數據和分塊結果發(fā)送到主節(jié)點。

主節(jié)點分配數據至重復數據刪除集群中的目標節(jié)點。目標節(jié)點是通過數據路由算法計算得到的，例如DRSD或者MCS。主節(jié)點同時也把數據的分塊結果發(fā)送至目標節(jié)點。這個架構只有一個主節(jié)點。采用這種設計的原因是數據路由策略不需要大量的計算資源，一個節(jié)點能夠滿足需要。

然后，存儲節(jié)點對數據做重復數據刪除工作，找到重復的數據。每個存儲節(jié)點獨立工作。這意味著一個存儲節(jié)點只能找到存儲在自己上的重復數據。最后，存儲節(jié)點把文件的元數據返回給主節(jié)點。文件的元數據包括用于讀取文件所必要的信息，例如，文件數據塊的簽名，文件數據塊的地址等。

圖1 重復數據刪除集群架構

1.2 基于文件路徑的數據路由策略

重復數據刪除集群的關鍵問題是如何合理地把數據分配至各個存儲節(jié)點。重復數據刪除集群的數據路由策略負責這項工作。數據路由算法的目標包括保證重復數據刪除集群的高重復數據刪除率和較好的負載平衡。

重復數據刪除集群的數據路由策略主要分為2類。第一類是有狀態(tài)數據路由策略。對于每個文件或者數據段，有狀態(tài)路由策略首先向重復數據刪除集群中的每個節(jié)點發(fā)送詢問請求，詢問每個節(jié)點能在這個文件或者數據段中找到的重復數據的數量。在此之后，有狀態(tài)路由策略再確定哪個節(jié)點存儲這個文件或者數據段需要最少的存儲空間，再把數據存儲在那個節(jié)點。

另外一種數據路由策略是無狀態(tài)數據路由策略。它做數據路由時，只依賴于數據本身，而不需要其他信息。例如，MCS僅僅需要文件或者數據段的最小數據塊ID確定把數據存儲在哪個節(jié)點。

與無狀態(tài)路由策略相比，有狀態(tài)路由策略可以提供更好的重復數據刪除率，但是卻需要較多的計算開銷，因此，它的速度較慢。重復數據刪除集群需要在較短的備份窗口內存儲大量的備份數據，需要高吞吐量。因此，無狀態(tài)路由策略更適合于重復數據刪除集群。

為了改進重復數據刪除集群的重復數據刪除率，最好能夠把相似的數據或者文件存儲在同一個節(jié)點上。文件的路徑是一種文件系統(tǒng)語義，指的是文件系統(tǒng)路徑。在連續(xù)的數據備份版本中，數據的目錄結構通常是穩(wěn)定的，備份版本中具有相同目錄名稱的目錄很可能對應同一個原始目錄，那么具有相同目錄名稱的文件集很有可能包含一些相同的數據?？梢岳梦募穆窂綖橹貜蛿祿h除集群設計一種數據路由策略。

本文提出一種基于路徑的重復數據刪除集群的數據路由策略，稱作DRSD(data routing strategy based on directories)。DRSD構建一個路徑路由索引保存路徑相關的路由信息。當需要路由數據時，先查詢路徑路由索引是否存在改路徑的路由信息，如果存在，就直接使用該路由信息數據到目標節(jié)點；如果不存在，就使用文件的最小塊簽名計算目標節(jié)點。

文件路徑指的是文件的整個文件系統(tǒng)路徑，是由一些文件系統(tǒng)目錄名組成的，包括從根目錄至文件所在的目錄。用戶常見的一種操作是把某個目錄移動到另外一個目錄，或者修改某個目錄的名字。這種操作會改變文件目錄的父目錄，卻不會改變這個目錄的子目錄。這就意味著，在不同的備份版本內，被移動或者修改的目錄的所有子目錄中的所有文件的部分父目錄是保持不變的。因此，DRSD使用與文件最接近的部分父目錄路由數據，而不使用文件的整個目錄。

圖2 數據路由算法(MCS和DRSD)

圖2給出了DRSD數據路由算法的細節(jié)。為了便于比較，圖2也包括了MCS數據路由算法。在算法中，directoryName指的是文件的整個路徑，包括從根目錄至文件所在的目錄。directoryDepth表示目錄深度，指的是從文件所在的目錄開始向上的目錄層次。getSubDirectory函數的功能是從文件的目錄名中獲得特定目錄深度的子目錄名。例如，文件d.txt的文件目錄是'/a/b/c/d.txt'，那么文件d.txt的目錄深度為2的子目錄名是"/b/c"，類似的，文件d.txt的目錄深度為3的子目錄名是"/a/b/c"。

2 評 估

本節(jié)比較DRSD、已有的MCS和單節(jié)點重復數據刪除。收集了一個真實世界的數據集，并構建了一個仿真器比較它們。首先詳細描述了仿真器。然后，描述了評估標準。最后，描述并分析了實驗結果，包括存儲空間使用情況和負載均衡情況。

2.1 數據集

為了驗證文章提出的算法，收集了一個真實世界的數據集。這個數據集是Linux源代碼檔案，稱作Linux。它包括Linux1.2.0至Linux2.5.75之間的所有源代碼檔案，共計564個備份版本。Linux數據集的大部分文件時小文件，一般是幾十KB。Linux代表了主要包括小文件的、高冗余的數據集。表1給出了Linux的詳細數據。

表1 數據集

2.2 評估標準

重復數據刪除集群的評估標準如下所示：

1)重復數據刪除率：數據集的原始尺寸與消除重復數據后存儲空間使用量的比值。

2)數據傾斜率：重復數據刪除集群中存儲使用量最大節(jié)點的存儲使用量與所有節(jié)點的平均存儲使用量的比值。它用于測量重復數據刪除集群的負載均衡情況。

2.3 仿真器

為了評估DRSD，構建了一個仿真器，用于仿真重復數據刪除集群。重復數據刪除集群包括許多存儲節(jié)點。仿真器也包括一個主節(jié)點，負責把數據分配到各個存儲節(jié)點。仿真器包括分塊器。

仿真器的第1個部分是主節(jié)點。它運行數據路由算法，負責把文件分發(fā)至重復數據刪除集群的各個存儲節(jié)點。實現了2個數據路由算法，DRSD和MCS。數據路由算法逐個處理文件。它把文件的分塊結果作為輸入，然后確定目標節(jié)點，再把文件和分塊結果發(fā)送至目標節(jié)點。

仿真器的第2個部分是存儲節(jié)點。重復數據刪除集群包括一定數量的存儲節(jié)點。存儲節(jié)點負責重復數據刪除工作。這與單節(jié)點重復數據刪除是一樣的。存儲節(jié)點維護一個數據塊索引，包括所有已經存儲的數據塊的簽名。當處理1個文件時，它首先在數據塊索引中搜索文件的每個數據塊簽名或者ID。如果數據塊ID存在于數據塊索引中，那么，這個數據塊ID對應的數據塊就是重復的。否則，這個數據塊就是新數據塊。存儲節(jié)點然后構造文件的元數據。存儲節(jié)點采用最優(yōu)重復數據刪除，即把整個數據塊索引都放在內存中。

仿真器的第3個部分是分塊器。它逐個處理文件，輸出分塊結果到分塊結果文件中。分塊器首先從磁盤讀出文件，然后對它分塊。使用TTTD分塊算法[12]，設置平均數據塊尺寸為4 kB。

2.4 存儲空間使用量

存儲空間使用量對于重復數據刪除系統(tǒng)是非常重要的。存儲空間使用量決定了磁盤使用量。由于備份數據通常都是海量的，那么磁盤是備份系統(tǒng)的主要成本。因此，存儲使用量決定了重復數據刪除系統(tǒng)的成本。重復數據刪除率一般用于測量重復數據刪除系統(tǒng)的存儲使用量。

對于重復數據刪除集群的不同的節(jié)點數量，比較了DRSD、MCS和單節(jié)點重復數據刪除。圖3給出了比較結果。對于重復數據刪除集群的各種不同的節(jié)點數量(包括2，4，8，16，32，64，128，256，512，1 024)，測量了算法的重復數據刪除率。在圖3中，Single node表示單節(jié)點重復數據刪除；DRSD(2)表示DRSD并且路徑深度是2。

如圖3所示，單節(jié)點重復數據刪除具有最好的重復數據刪除率。因為是所有的數據都存儲在同一個節(jié)點上，可以找到所有的重復數據塊。而對于DRSS和MCS，數據分布在許多節(jié)點上。每個節(jié)點獨立工作，這意味著每個節(jié)點只在自己上存儲的數據中查找重復數據，而不查找其他節(jié)點上存儲的數據。因此，DRSS和MCS的重復數據刪除率小于單節(jié)點重復數據刪除。

如圖3所示，對于不同的節(jié)點數量，路徑深度為1的DRSD的重復數據刪除率都非常接近單節(jié)點重復數據刪除，并且遠遠優(yōu)于MCS。這表明DRSD能夠有效地把相似的文件分配至同一個節(jié)點。隨著節(jié)點數量的增加，DRSD和MCS的重復數據刪除率迅速下降。當節(jié)點數量大于64時，其重復數據刪除率不再有明顯的降低。此時，DRSD(1)的重復數據刪除率比MCS高35%。

隨著路徑深度的增加，DRSD的性能逐漸降低。對于各種不同的節(jié)點數量，路徑深度為1和2的DRSD的重復數據刪除率都比MCS好一些，路徑深度為3和4的DRSD的重復數據刪除率都比MCS差。

圖3 重復數據刪除率比較

2.5 負載均衡

負載均衡對于重復數據刪除集群是很重要的。重復數據刪除集群的某個節(jié)點的存儲使用量不能太大，否則，這個節(jié)點會成為整個集群的性能瓶頸，惡化整個集群的性能。使用數據傾斜率測量重復數據刪除集群的負載均衡。數據傾斜率越高，說明負載均衡越差。數據遷移策略一般用于保證重復數據刪除集群各節(jié)點的負載均衡。但是，這不是本文的重點，本文主要研究不包括數據遷移的DRSD的原始數據傾斜率。實驗不包括數據遷移策略。

圖4 負載均衡比較

對于各種不同節(jié)點數量，圖4比較了DRSD、MCS和單節(jié)點重復數據刪除的數據傾斜率。Single node表示單節(jié)點重復數據刪除；DRSD(2)表示DRSD并且路徑深度是2。

隨著節(jié)點數量的增加，DRSD和MCS的數據傾斜率也隨之增加。當節(jié)點數量小于64時，DRSD和MCS的數據傾斜率緩慢增加。然而，當節(jié)點數量大于64時，DRSD的數據傾斜率快速增加。當節(jié)點數量小于8時，DRSD與MCS的數據傾斜率幾乎相同。當節(jié)點數量是8時，DRSD(1)的重復數據刪除率比MCS高29%。

當節(jié)點數量是大于32時，DRSD(1)的數據傾斜率明顯大于MCS。注意，這是不包括數據遷移策略的原始數據傾斜率。在將來的工作中，將研究如何改進DRSD的數據傾斜率。

隨著路徑深度的增加，DRSD的數據傾斜率隨之降低。DRSD(3)和DRSD(4)具有幾乎相同的數據傾斜率。DRSD(1)和DRSD(2)的數據傾斜率則大于其它算法，并且隨著節(jié)點數量的增加，這種區(qū)別更加明顯。

3 結 論

為了改進重復數據刪除集群的重復數據刪除率，利用文件路徑提出了一種新穎的數據路由策略DRSD。構建了一個仿真器，并用來自真實世界的數據集評估了DRSD。實驗結果表明，對于各種不同的節(jié)點數量，DRSD的重復數據刪除率都明顯高于MCS，并且接近單節(jié)點重復數據刪除。當節(jié)點數量是64時，DRSD的重復數據刪除率比MCS高35%。此外，當節(jié)點數量小于8時，DRSD的數據傾斜率與MCS幾乎相同，即二者的負載均衡幾乎相同。

參考文獻：

[1] Gantz J F, Chute C, Manfrediz A, Minton S, Reinsel D, Schlichting W, Toncheva A . The Diverse and Exploding Digital Universe: An Updated Forecast of Worldwide Information Growth through 2011[R]. An IDC White Paper-Sponsored by EMC, 2008

[2] Stoica I. A Berkeley View of Big Data. https://amplab.cs.berkeley.edu/about/.

[3] Dong W, Douglis F, Li K, Patterson H, Reddy S, Shilane P. Tradeoffs in Scalable Data Routing for Deduplication Clusters[C]∥Proceedings of the 9th Conference on USENIX Conference on File and Storage Technologies. San Jose, CA, USA: USENIX Association, Berkeley, CA, USA, 2011: 15-17, 15-29

[4] You L, Pollack K, Long D. Deep Store: An Archival Storage System Architecture[C]∥Proceedings of the 21th International Conference on Data Engineering. Tokyo, Japan: IEEE Computer Society, Washington, DC, USA, 2005: 804-815

[5] Zhu B, Li K, Patterson H. Avoiding the Disk Bottleneck in the Data Domain Deduplication File System[C]∥Proceedings of the 6th Conference on USENIX Conference on File and Storage Technologies. San Jose, CA, USA: USENIX Association, Berkeley, CA, USA, 2008: 269-282

[6] Zhang Zhike, Bhagwat D, Litwin W, Long D, Schwarz S. Improved Deduplication through Parallel Binning[C]∥Performance Computing and Communications Conference (IPCCC), 2012 IEEE 31st International. IEEE, Washington, DC, USA, 2012: 130-141

[7] Zhang Zhike, Jiang Zejun, Liu Zhiqiang, et al. LHs: A Novel Method of Information Retrieval Avoiding an Index Using Linear Hashing with Key Groups in Deduplication[C]∥Proceedings of 2012 International Conference on Machine Learning and Cybernetics. Washington, DC: IEEE, 2012: 1312-1318

[8] Zhang Zhike, Jiang Zejun, Cai Xiaobin, Peng Chengzhang. A Novel Cache Prefetching Algorithm for Restoration Operations of Deduplication Systems[J]. Lecture Notes in Electrical Engineering, 2012, 219(4): 331-338

[9] Bhagwat D, Eshghi K, Long D, Lillibridge M. Extreme Binning: Scalable, Parallel Deduplication for Chunk-Based File Backup[C]∥Proceedings of the 17th Annual Meeting of the IEEE/ACM International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems. London, UK: IEEE Computer Society, Washington, DC, USA, 21-23 September 2009, 1-9

[10] Dubnicki C, Gryz L, Heldt L, Kaczmarczyk M, Kilian W, Strzelczak P, Szczepkowski J, Ungureanu C, Welnicki M. Hydrastor: A Scalable Secondary Storage[C]∥Proceedings of the 7th Conference on USENIX Conference on File and Storage Technologies. San Francisco, CA, USA: USENIX Association, Berkeley, CA, USA, 2009: 197-210

[11] Frey D, Kermarrec A, Kloudas K. Probabilistic Deduplication for Cluster-Based Storage Systems[C]∥Proceedings of the Third ACM Symposium on Cloud Computing. ACM, New York, NY, USA, 2012: 17

[12] Forman G, Eshghi K, Chiocchetti S. Finding Similar Files in Large Document Repositories. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Chicago, IL, USA: ACM, New York, NY, USA, 2005: 394-400