英文摘要:The problem of redundancy often occurs in mass data stored in distributed storage systems. Greater efficiency in storage and network bandwidth utilization can be achieved by employing de-duplication techniques to eliminate this problem. This article introduces the design and implementation of redundancy-removal systems in a distributed WAN environment. AegeanStore can eliminate redundancy prior to data being uploaded. This frees up storage space and resource use, and lowers the total cost of storage. Furthermore, disaster recovery features inherent in the distributed system are maintained, storage system scalability is enhanced, and overall performance of the network is improved.
英文關鍵字:distributed system; storage system; de-duplication
基金項目：國家重點基礎研究發(fā)展(“973”)規(guī)劃(2007CB311100)
由于數(shù)字信息的爆炸式增長，現(xiàn)今的大規(guī)模網絡應用中所存儲的數(shù)據規(guī)模，可以到達上百太字節(jié)甚至拍字節(jié)的數(shù)量級。而傳統(tǒng)的存儲系統(tǒng)，由于缺乏足夠的可擴展性，無法適應日益增長的需求。以Amazon S3[1]為代表的廣域網環(huán)境下的分布式存儲系統(tǒng)憑借其規(guī)模的可擴展性、數(shù)據的可靠性、服務的可用性、系統(tǒng)的可管理性以及低廉的使用成本等巨大優(yōu)勢，已經在構建網絡應用時被廣泛認可。
廣域網環(huán)境下的分布式存儲系統(tǒng)將分布在廣域網上的資源整合在一起，為網絡應用提供存儲服務平臺。來自不同網絡應用和用戶的數(shù)據存儲其中，這些海量的數(shù)據中存在著大量的冗余。這些冗余數(shù)據不僅在存儲時占據了存儲系統(tǒng)大量的存儲空間，并且在被傳輸?shù)酱鎯ο到y(tǒng)的過程當中，浪費了大量的網絡用戶、網絡應用和存儲系統(tǒng)的網絡帶寬資源，使存儲系統(tǒng)的資源利用率和整體性能受到嚴重影響。
本文提出一種在廣域網環(huán)境下的采用冗余數(shù)據刪除技術的分布式存儲系統(tǒng)原型——AegeanStore。在AegeanStore中采用客戶端相關的冗余數(shù)據刪除技術。該技術通過客戶端和服務器端的合作，不僅可提高存儲設備的利用率，而且可減輕客戶端和服務器之間的網絡負載壓力，從而進一步提高存儲系統(tǒng)的可擴展性和整體性能并且進一步降低其成本。
1 冗余數(shù)據刪除技術
冗余數(shù)據刪除技術是將數(shù)據集中的冗余數(shù)據發(fā)現(xiàn)并去除的應用技術，可以分為兩大類：相同數(shù)據刪除和相似數(shù)據刪除[2]。
1.1 相同數(shù)據刪除技術
相同數(shù)據刪除技術首先將數(shù)據劃分為數(shù)據塊，然后使用具有抗碰撞特性[3]的哈希函數(shù)計算每一個數(shù)據塊的哈希值作為該數(shù)據塊的數(shù)字指紋，再通過比較數(shù)據塊的數(shù)字指紋來發(fā)現(xiàn)相同的數(shù)據塊。目前，最常用的相同數(shù)據刪除技術是基于內容的劃塊(CDC)算法[4]，其流程如圖1所示。
CDC算法存在3個參數(shù)，一是目標可變數(shù)據塊的預期大小S，二是滑動窗口的大小W，三是一個小于S的自然數(shù)M。當使用CDC算法處理一個文件時，從文件頭開始以每次一字節(jié)的步長向后滑動窗口，使用哈希函數(shù)計算滑動窗口內部的哈希值H；將H mod S與M進行比較，如果不同，則滑動窗口；如果相同，則發(fā)現(xiàn)數(shù)據塊邊界，然后用具有抗碰撞特性的哈希函數(shù)計算該數(shù)據塊的數(shù)字指紋；最后，將獲得的數(shù)字指紋到索引中查找，如果存在則發(fā)現(xiàn)冗余數(shù)據塊，否則說明該數(shù)據塊是新的，需要存儲到系統(tǒng)當中。
1.2 相似數(shù)據刪除技術
相似數(shù)據刪除技術分為兩個階段，相似數(shù)據檢測和相似數(shù)據編碼：
(1)相似數(shù)據檢測，首先要定義數(shù)據的特征值，該特征值的特點是保證具有相同或相似的特征值的數(shù)據具有相同或相似的內容。在提取數(shù)據的特征值之后，通過特征值的比較獲得相似的數(shù)據。常用的相似數(shù)據檢測技術包括基于Shingle的檢測技術[5]。
(2)相似數(shù)據編碼是在使用相似數(shù)據檢測，獲得具有相似性的數(shù)據集之后，在該數(shù)據集上采用的編碼技術，用于減小該數(shù)據集所占用的存儲空間。常用的相似數(shù)據編碼技術包括基于Diff的相似編碼技術[6]等。
2 AegeanStore的體系結構
AegeanStore體系結構如圖2所示。AegeanStore由客戶端、應用服務、文件系統(tǒng)服務、索引服務和數(shù)據塊服務5個部分組成。
當客戶端需要將文件數(shù)據存儲到應用服務時，首先調用本地冗余數(shù)據刪除工具，運行數(shù)據塊劃分算法，將要上傳的文件分成數(shù)據塊，并計算每個數(shù)據塊的數(shù)字指紋，然后將這些數(shù)字指紋發(fā)送給應用服務；應用服務接收到文件上傳請求后，記錄應用相關信息，再將請求轉發(fā)給文件服務；文件服務記錄文件的元信息(包括文件屬性，例如文件的大小、修改時間等,以及文件的冗余數(shù)據刪除信息，如文件所有組成數(shù)據塊的數(shù)字指紋等)，再將請求轉發(fā)給索引服務；索引服務進行塊的數(shù)字指紋查詢工作，將結果返回給文件服務；文件服務將結果通過應用服務返回給客戶端；客戶端按照返回結果，只將未出現(xiàn)在數(shù)據塊服務中的數(shù)據塊上傳；最后，當所有新數(shù)據塊都存儲到數(shù)據塊服務中之后，文件服務將新數(shù)據塊的信息更新到索引服務當中。下面將分別介紹5個部分的設計與實現(xiàn)。
2.1 客戶端
客戶端是為某個應用服務開發(fā)，運行在使用該應用服務的用戶的網絡終端上的程序。程序通過響應用戶輸入并且同該應用服務進行消息交換，使用戶能夠使用該應用服務提供的服務。AegeanStore的客戶端除了完成傳統(tǒng)網絡應用的客戶端的響應用戶輸入、網絡消息交換、身份驗證、數(shù)據傳輸?shù)热蝿罩?，還要在冗余數(shù)據刪除技術中，完成重要的任務：因為AegeanStore使用冗余數(shù)據刪除技術的目標是減少冗余數(shù)據在網絡傳輸時造成的浪費，所以冗余數(shù)據刪除中的可變數(shù)據塊劃分和計算每個數(shù)據塊的數(shù)字指紋等工作必須在客戶端完成。在獲得需要上傳文件的所有數(shù)據塊的數(shù)字指紋后，通過應用服務提供的網絡接口，查詢這些文件塊是否已經在AegeanStore中存在，然后將新的數(shù)據塊上傳到數(shù)據塊服務部分，完成數(shù)據上傳過程；同時，客戶端需要管理已經存儲在本地的數(shù)據塊的數(shù)字指紋，用于下載時減少冗余數(shù)據傳輸。
2.2 應用服務
應用服務是以AegeanStore提供的存儲服務、開發(fā)框架和功能組件為基礎，構建而成的網絡應用服務。AegeanStore作為網絡應用開發(fā)的基礎平臺，為了方便應用服務的開發(fā)，提供了應用服務的開發(fā)框架，使得應用服務的開發(fā)可以忽略網絡應用中網絡端口監(jiān)聽、工作進程派生、負載均衡和調度等問題，專心解決應用服務的事務邏輯，使應用服務的開發(fā)工作更加方便快捷。應用服務開發(fā)者只需要將自己開發(fā)的消息處理模塊和消息序列化/反序列化模塊注冊到應用服務框架當中，即可被框架自動調用，進而提供網絡應用服務。除此之外，AegeanStore還為應用服務的開發(fā)者提供用戶管理、網絡消息交換等常用的功能組件，從而提高在AegeanStore上開發(fā)應用服務效率，降低應用服務的開發(fā)和運營成本。
2.3 文件系統(tǒng)服務
文件系統(tǒng)服務為AegeanStore提供文件系統(tǒng)視圖和文件管理接口。目前常用的提供公共存儲服務的分布式存儲系統(tǒng)當中，普遍使用的應用程序接口是Key/Value式的。雖然這種接口在開發(fā)應用服務時使用比較方便，但是與用戶習慣的基于目錄結構的文件系統(tǒng)式接口差異較大，導致大多數(shù)構建在Key/Value接口上的應用服務都要開發(fā)功能相似的文件系統(tǒng)視圖。這些重復開發(fā)增加了應用服務開發(fā)的難度和成本，更重要的是，因為缺少存儲系統(tǒng)內部信息的輔助，無法利用數(shù)據的局部性和網絡的就近訪問等優(yōu)化技術，在Key/Value接口上構建的文件系統(tǒng)效率往往較低，對應用服務以及存儲系統(tǒng)的網絡和存儲資源造成了嚴重的浪費。所以，AegeanStore為應用服務開發(fā)提供的接口是文件系統(tǒng)式的，以提高應用服務的開發(fā)效率，避免重復開發(fā)，并通過使用分布式B樹、網絡就近訪問、代理訪問等優(yōu)化技術，提高存儲系統(tǒng)的吞吐量。
2.4 索引服務
索引服務中存儲了AegeanStore中所有數(shù)據塊的數(shù)字指紋的索引，并提供網絡查詢索引接口，用來判斷數(shù)字指紋所對應的數(shù)據塊是否已經存在于AegeanStore當中。以SHA-1哈希函數(shù)計算出來的數(shù)據指紋為例，每個塊的數(shù)字指紋大小為20 B，假設可變塊劃分算法所分的數(shù)據塊的平均大小為4 kB，則索引服務中存儲的數(shù)字指紋索引的數(shù)據規(guī)模為實際存儲數(shù)據規(guī)模的0.5%。由于AegeanStore存儲系統(tǒng)具有良好的可擴展性，其數(shù)據規(guī)?？梢赃_到數(shù)百太字節(jié)甚至拍字節(jié)級，所以索引服務應該支持太字節(jié)級別的索引存儲。
2.5 數(shù)據塊服務
AegeanStore的數(shù)據塊服務提供分布式的基于內容定位的存儲系統(tǒng)[7]，其提供的接口是Key/Value形式的。數(shù)據塊服務由接口、一跳分布式哈希表(DHT)[8]和數(shù)據塊存儲節(jié)點3部分組成：當用戶存儲數(shù)據塊時，以該數(shù)據塊的數(shù)字指紋作為Key進行存儲；首先到一跳分布式哈希表中，查找該數(shù)字指紋，因為數(shù)字指紋由數(shù)據塊的內容決定，所以，如果該數(shù)字指紋已經存在于分布式哈希表當中，說明該數(shù)據塊已經存在于數(shù)據塊服務當中，無需再次存儲；如果不存在，將數(shù)據塊存入數(shù)據塊存儲節(jié)點，將數(shù)字指紋和所存儲的位置信息存入一跳分布式哈希表作為索引。當用戶讀取數(shù)據時，給出數(shù)據塊的數(shù)字指紋。塊存儲服務從分布式哈希表中查找是否存在這個數(shù)字指紋，如果存在則根據在其中獲得的數(shù)據塊位置從存儲節(jié)點讀取相應數(shù)據塊并返回給用戶，否則返回空。
3 冗余刪除技術的優(yōu)化
將冗余數(shù)據刪除技術應用于分布式存儲系統(tǒng)將遇到兩個問題。
(1)由于CDC算法開銷過大，無法滿足廣域網環(huán)境中的分布式存儲系統(tǒng)的客戶端的異構性帶來的計算性能瓶頸。
(2)由于分布式存儲系統(tǒng)的高可擴展性，造成索引服務中數(shù)字指紋索引過大，從而帶來的數(shù)字指紋索引查詢的性能瓶頸。
3.1 CDC算法的優(yōu)化
CDC算法中，無論在計算滑動窗口內的哈希值，還是獲得數(shù)據塊劃分之后計算數(shù)據塊的數(shù)字指紋都是計算密集型工作。在手機或上網本等運算能力較差的設備上，由于存在著性能瓶頸，制約了客戶端相關的冗余數(shù)據刪除技術的有效應用。
首先，在AegeanStore的客戶端中，為了優(yōu)化CDC算法的運行效率，在計算滑動窗口的哈希值時，采用了Rabin’s Fingerprinting[9]哈希函數(shù)進行計算。因Rabin’s Fingerprinting哈希函數(shù)具有可迭代計算的特性，滑動窗口時，只需要通過將滑動前哈希值、滑入字節(jié)值和滑出字節(jié)值進行復雜度為O(1)的計算，即可獲得滑動后的窗口內部字節(jié)數(shù)組的哈希值。因為每個字節(jié)的數(shù)值最多有256種可能，可以通過預先的計算，將滑入和滑出字節(jié)相關的計算制成表格，之后，只需要通過查表和簡單的位移操作和加減操作即可獲得滑動后的哈希值，大大提高了CDC算法的運算效率。
其次，AegeanStore引入了雙閾值雙除數(shù)算法(TTTD)[10]，對CDC算法進一步優(yōu)化。TTTD算法規(guī)定了數(shù)據塊大小的最小值Smin。每一個可變數(shù)據塊從開始到Smin的區(qū)間內的數(shù)據不需要進行哈希值計算。TTTD算法是為了對付可變數(shù)據塊劃分結果中數(shù)據塊大小差異太大而造成的冗余刪除率較差的問題，經試驗證明，Smin:S約等于0.85時，可以獲得最好的冗余刪除率。所以使用TTTD算法可以大大降低冗余數(shù)據刪除的計算開銷，提高AegeanStore客戶端的運行效率。
3.2 索引服務的優(yōu)化
AegeanStore的索引服務通過采用3種優(yōu)化方法，改進索引服務的數(shù)字指紋查詢效率，以提高冗余數(shù)據刪除技術在分布式存儲系統(tǒng)中的性能。
(1)基于文件的批量數(shù)字指紋查詢
AegeanStore提出了基于文件的批量數(shù)字指紋查詢協(xié)議，將相同文件的數(shù)據指紋列表，連同該文件的路徑、大小等元數(shù)據信息，組織到同一個文件上傳請求當中。經過這樣的優(yōu)化，既減少了AegeanStore客戶端的網絡請求數(shù)，增大了每個請求的數(shù)據量，提高網絡資源的利用率；并且，讓索引服務一次可以處理很多個數(shù)字指紋的索引查詢，增加了索引服務的吞吐量；更重要的是，使同一個文件的數(shù)據塊的數(shù)字指紋之間所存在的局部性得以保持，為索引服務進行預取和緩存等進一步優(yōu)化創(chuàng)造了條件。
(2)基于Bloom filter的快速新數(shù)據塊過濾
Bloom filter[11]是一種高效的利用有限的內存空間，以一定錯誤肯定率為代價，用于快速的判斷某一個元素是否在一個集合中的概率性數(shù)據結構。在AegeanStore的索引服務當中，使用一臺性能較好、內存空間較大的服務器來運行快速新數(shù)據過濾模塊。一個存于內存中的Bloom filter作為該模塊的核心數(shù)據結構。當接收到由請求節(jié)點轉發(fā)來的基于文件的批量數(shù)字指紋查詢請求之后，將其中每一個數(shù)字指紋送到Bloom filter中進行判斷其是否存在于AegeanStore當中。如果判定結果為可能存在，則將其忽略；如果為一定不存在，則將這個數(shù)字指紋標記為新數(shù)據塊；將標記后的數(shù)字指紋列表，返回給請求節(jié)點；最后，當數(shù)據塊被成功上傳到數(shù)據塊服務之后，將其對應的數(shù)字指紋加入到Bloom filter當中。
(3)基于文件局部性的緩存和預取
文件局部性是指出現(xiàn)在相同文件中的數(shù)據塊，再次出現(xiàn)在相同文件中的概率會比較高。文件局部性通過使用基于文件的批量索引請求被保存到索引服務當中，與某數(shù)字指紋具有文件局部性的其他數(shù)字指紋的列表稱之為局部性列表。緩存和預取節(jié)點中的緩存的數(shù)據結構提供Key/Value式的接口，同樣以數(shù)字指紋作為Key，以其局部性列表作為Value。當索引查找的數(shù)字指紋列表被分配到某個緩存和預取節(jié)點后，處理流程如下：對于每一個沒有被標記為新的數(shù)字指紋，首先到緩存中查找該數(shù)字指紋，如果命中，說明該數(shù)據塊已經存在于AegeanStore當中，將文件的數(shù)字指紋列表和緩存中局部性列表合并，并在結果中標記該塊為存在；若未命中，則到DHT中進行查找，如果命中，將DHT中存儲的局部性列表加入緩存當中，完成預取工作，之后的處理和緩存命中時相同；如果未命中，即該數(shù)據塊不存在于AegeanStore當中，在快速過濾模塊當中出現(xiàn)了錯誤的情況。
4 結束語
本文提出了廣域網環(huán)境下的分布式存儲系統(tǒng)原型AegeanStore。AegeanStore在提供互聯(lián)網上的存儲服務的同時，還為網絡應用的開發(fā)提供了框架和通用的功能模塊，以提高網絡應用開發(fā)和運營的效率，并降低其成本。分布式存儲系統(tǒng)中普遍存在的冗余數(shù)據，不僅浪費了存儲系統(tǒng)的資源，而且造成了存儲系統(tǒng)的性能損失。AegeanStore通過采用客戶端相關的冗余數(shù)據刪除技術，可提高對存儲資源以及網絡資源的利用率，降低運營成本，提高可擴展性以及整體性能。
5 參考文獻
[1] Amazon Simple Storage Service (Amazon S3) [EB/OL]. [2010-06-16]. http://aws.amazon.com/s3/.
[2] 敖莉, 舒繼武, 李明強. 重復數(shù)據刪除技術研究綜述 [J]. 軟件學報, 2010,21(5):916-929.
[3] Cryptographic Hash Function [EB/OL]. [2010-05-25]. http://en.wikipedia.org/wiki/Cryptographic_hash_functions.
[4] DENEHY T E, HSU W W. Duplicate Management for Reference Data [R]. Research Report. RJ 10305 (A0310-017). San Jose, CA,USA: IBM. 2003.
[5] BRODER A Z. Identifying and Filtering Near-duplicate Documents [C]//Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching(CPM’00), Jun 21-23, 2000, Montreal, Canada. Berlin, Germany: Springer-Verlag, 2000:1-10.
[6] HUNT J W, MCILLROY M C. An Algorithm for Differential File Comparison [R]. Computing Science Technical Report 41. Stanford, CA, USA: Stanford University, 1976.
[7] TOLIA N, KOZUCH M, SATYANARAYANAN M, et al. Opportunistic Use of Content-addressable Storage for Distributed File Systems [C]//Proceedings of the 2003 USENIX Annual Technical Conference (USENIX’03), Jun 9-14, 2003, San Antonio, TX,USA. Berkeley, CA, USA: USENIX Association, 2003: 127-140.
[8] GUPTA A, LISKOV B, RODRIGUES R. One Hop Lookups for Peer-to-peer Overlays [C]//Proceedings of the 9th Conference on Hot Topics in Operating Systems (HotOS’03), May 18-21, 2003, Lihue, HI,USA. Berkeley, CA, USA: USENIX Association,2003: 7-12.
[9] BRODER A Z. Some Applications of Rabin's Fingerprinting Method [M]//CAPOCELLI R, DE SANTIS A, VACCARO U. Sequences II: Methods in Communications, Security, and Computer Science. Berlin, Germany: Springer-Verlag, 1993: 143-152.
[10] ESHGHI K, TANG H K. A Framework for Analyzing and Improving Content-based Chunking Algorithms [R]. TR 2005-30. Hewlett-Packard Labs. 2009.
[11] BRODER A, MITZENMACHER M. Network Applications of Bloom Filters: A Survey [J]. Internet Mathematics, 2004,1(4): 485-509.
尹玉冰，清華大學高性能計算研究所在讀碩士研究生，主要研究領域為存儲系統(tǒng)。
孫競，清華大學高性能計算研究所在讀博士研究生，主要研究領域為分布式系統(tǒng)。
余宏亮，清華大學高性能計算研究所副教授、博士，主要研究領域為并行與分布式系統(tǒng)，曾作為主要成員參與和負責了5項國家級基金項目的研究工作，已在國內外重要學術刊物和會議上發(fā)表論文30余篇。