英文摘要: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
基金項目：國家重點基礎研究發展(“973”)規劃(2007CB311100)
由于數字信息的爆炸式增長，現今的大規模網絡應用中所存儲的數據規模，可以到達上百太字節甚至拍字節的數量級。而傳統的存儲系統，由于缺乏足夠的可擴展性，無法適應日益增長的需求。以Amazon S3[1]為代表的廣域網環境下的分布式存儲系統憑借其規模的可擴展性、數據的可靠性、服務的可用性、系統的可管理性以及低廉的使用成本等巨大優勢，已經在構建網絡應用時被廣泛認可。
廣域網環境下的分布式存儲系統將分布在廣域網上的資源整合在一起，為網絡應用提供存儲服務平臺。來自不同網絡應用和用戶的數據存儲其中，這些海量的數據中存在著大量的冗余。這些冗余數據不僅在存儲時占據了存儲系統大量的存儲空間，并且在被傳輸到存儲系統的過程當中，浪費了大量的網絡用戶、網絡應用和存儲系統的網絡帶寬資源，使存儲系統的資源利用率和整體性能受到嚴重影響。
本文提出一種在廣域網環境下的采用冗余數據刪除技術的分布式存儲系統原型——AegeanStore。在AegeanStore中采用客戶端相關的冗余數據刪除技術。該技術通過客戶端和服務器端的合作，不僅可提高存儲設備的利用率，而且可減輕客戶端和服務器之間的網絡負載壓力，從而進一步提高存儲系統的可擴展性和整體性能并且進一步降低其成本。
1 冗余數據刪除技術
冗余數據刪除技術是將數據集中的冗余數據發現并去除的應用技術，可以分為兩大類：相同數據刪除和相似數據刪除[2]。
1.1 相同數據刪除技術
相同數據刪除技術首先將數據劃分為數據塊，然后使用具有抗碰撞特性[3]的哈希函數計算每一個數據塊的哈希值作為該數據塊的數字指紋，再通過比較數據塊的數字指紋來發現相同的數據塊。目前，最常用的相同數據刪除技術是基于內容的劃塊(CDC)算法[4]，其流程如圖1所示。
CDC算法存在3個參數，一是目標可變數據塊的預期大小S，二是滑動窗口的大小W，三是一個小于S的自然數M。當使用CDC算法處理一個文件時，從文件頭開始以每次一字節的步長向后滑動窗口，使用哈希函數計算滑動窗口內部的哈希值H；將H mod S與M進行比較，如果不同，則滑動窗口；如果相同，則發現數據塊邊界，然后用具有抗碰撞特性的哈希函數計算該數據塊的數字指紋；最后，將獲得的數字指紋到索引中查找，如果存在則發現冗余數據塊，否則說明該數據塊是新的，需要存儲到系統當中。
1.2 相似數據刪除技術
相似數據刪除技術分為兩個階段，相似數據檢測和相似數據編碼：
(1)相似數據檢測，首先要定義數據的特征值，該特征值的特點是保證具有相同或相似的特征值的數據具有相同或相似的內容。在提取數據的特征值之后，通過特征值的比較獲得相似的數據。常用的相似數據檢測技術包括基于Shingle的檢測技術[5]。
(2)相似數據編碼是在使用相似數據檢測，獲得具有相似性的數據集之后，在該數據集上采用的編碼技術，用于減小該數據集所占用的存儲空間。常用的相似數據編碼技術包括基于Diff的相似編碼技術[6]等。
2 AegeanStore的體系結構
AegeanStore體系結構如圖2所示。AegeanStore由客戶端、應用服務、文件系統服務、索引服務和數據塊服務5個部分組成。
當客戶端需要將文件數據存儲到應用服務時，首先調用本地冗余數據刪除工具，運行數據塊劃分算法，將要上傳的文件分成數據塊，并計算每個數據塊的數字指紋，然后將這些數字指紋發送給應用服務；應用服務接收到文件上傳請求后，記錄應用相關信息，再將請求轉發給文件服務；文件服務記錄文件的元信息(包括文件屬性，例如文件的大小、修改時間等,以及文件的冗余數據刪除信息，如文件所有組成數據塊的數字指紋等)，再將請求轉發給索引服務；索引服務進行塊的數字指紋查詢工作，將結果返回給文件服務；文件服務將結果通過應用服務返回給客戶端；客戶端按照返回結果，只將未出現在數據塊服務中的數據塊上傳；最后，當所有新數據塊都存儲到數據塊服務中之后，文件服務將新數據塊的信息更新到索引服務當中。下面將分別介紹5個部分的設計與實現。
2.1 客戶端
客戶端是為某個應用服務開發，運行在使用該應用服務的用戶的網絡終端上的程序。程序通過響應用戶輸入并且同該應用服務進行消息交換，使用戶能夠使用該應用服務提供的服務。AegeanStore的客戶端除了完成傳統網絡應用的客戶端的響應用戶輸入、網絡消息交換、身份驗證、數據傳輸等任務之外，還要在冗余數據刪除技術中，完成重要的任務：因為AegeanStore使用冗余數據刪除技術的目標是減少冗余數據在網絡傳輸時造成的浪費，所以冗余數據刪除中的可變數據塊劃分和計算每個數據塊的數字指紋等工作必須在客戶端完成。在獲得需要上傳文件的所有數據塊的數字指紋后，通過應用服務提供的網絡接口，查詢這些文件塊是否已經在AegeanStore中存在，然后將新的數據塊上傳到數據塊服務部分，完成數據上傳過程；同時，客戶端需要管理已經存儲在本地的數據塊的數字指紋，用于下載時減少冗余數據傳輸。
2.2 應用服務
應用服務是以AegeanStore提供的存儲服務、開發框架和功能組件為基礎，構建而成的網絡應用服務。AegeanStore作為網絡應用開發的基礎平臺，為了方便應用服務的開發，提供了應用服務的開發框架，使得應用服務的開發可以忽略網絡應用中網絡端口監聽、工作進程派生、負載均衡和調度等問題，專心解決應用服務的事務邏輯，使應用服務的開發工作更加方便快捷。應用服務開發者只需要將自己開發的消息處理模塊和消息序列化/反序列化模塊注冊到應用服務框架當中，即可被框架自動調用，進而提供網絡應用服務。除此之外，AegeanStore還為應用服務的開發者提供用戶管理、網絡消息交換等常用的功能組件，從而提高在AegeanStore上開發應用服務效率，降低應用服務的開發和運營成本。
2.3 文件系統服務
文件系統服務為AegeanStore提供文件系統視圖和文件管理接口。目前常用的提供公共存儲服務的分布式存儲系統當中，普遍使用的應用程序接口是Key/Value式的。雖然這種接口在開發應用服務時使用比較方便，但是與用戶習慣的基于目錄結構的文件系統式接口差異較大，導致大多數構建在Key/Value接口上的應用服務都要開發功能相似的文件系統視圖。這些重復開發增加了應用服務開發的難度和成本，更重要的是，因為缺少存儲系統內部信息的輔助，無法利用數據的局部性和網絡的就近訪問等優化技術，在Key/Value接口上構建的文件系統效率往往較低，對應用服務以及存儲系統的網絡和存儲資源造成了嚴重的浪費。所以，AegeanStore為應用服務開發提供的接口是文件系統式的，以提高應用服務的開發效率，避免重復開發，并通過使用分布式B樹、網絡就近訪問、代理訪問等優化技術，提高存儲系統的吞吐量。
2.4 索引服務
索引服務中存儲了AegeanStore中所有數據塊的數字指紋的索引，并提供網絡查詢索引接口，用來判斷數字指紋所對應的數據塊是否已經存在于AegeanStore當中。以SHA-1哈希函數計算出來的數據指紋為例，每個塊的數字指紋大小為20 B，假設可變塊劃分算法所分的數據塊的平均大小為4 kB，則索引服務中存儲的數字指紋索引的數據規模為實際存儲數據規模的0.5%。由于AegeanStore存儲系統具有良好的可擴展性，其數據規模可以達到數百太字節甚至拍字節級，所以索引服務應該支持太字節級別的索引存儲。
2.5 數據塊服務
AegeanStore的數據塊服務提供分布式的基于內容定位的存儲系統[7]，其提供的接口是Key/Value形式的。數據塊服務由接口、一跳分布式哈希表(DHT)[8]和數據塊存儲節點3部分組成：當用戶存儲數據塊時，以該數據塊的數字指紋作為Key進行存儲；首先到一跳分布式哈希表中，查找該數字指紋，因為數字指紋由數據塊的內容決定，所以，如果該數字指紋已經存在于分布式哈希表當中，說明該數據塊已經存在于數據塊服務當中，無需再次存儲；如果不存在，將數據塊存入數據塊存儲節點，將數字指紋和所存儲的位置信息存入一跳分布式哈希表作為索引。當用戶讀取數據時，給出數據塊的數字指紋。塊存儲服務從分布式哈希表中查找是否存在這個數字指紋，如果存在則根據在其中獲得的數據塊位置從存儲節點讀取相應數據塊并返回給用戶，否則返回空。
3 冗余刪除技術的優化
將冗余數據刪除技術應用于分布式存儲系統將遇到兩個問題。
(1)由于CDC算法開銷過大，無法滿足廣域網環境中的分布式存儲系統的客戶端的異構性帶來的計算性能瓶頸。
(2)由于分布式存儲系統的高可擴展性，造成索引服務中數字指紋索引過大，從而帶來的數字指紋索引查詢的性能瓶頸。
3.1 CDC算法的優化
CDC算法中，無論在計算滑動窗口內的哈希值，還是獲得數據塊劃分之后計算數據塊的數字指紋都是計算密集型工作。在手機或上網本等運算能力較差的設備上，由于存在著性能瓶頸，制約了客戶端相關的冗余數據刪除技術的有效應用。
首先，在AegeanStore的客戶端中，為了優化CDC算法的運行效率，在計算滑動窗口的哈希值時，采用了Rabin’s Fingerprinting[9]哈希函數進行計算。因Rabin’s Fingerprinting哈希函數具有可迭代計算的特性，滑動窗口時，只需要通過將滑動前哈希值、滑入字節值和滑出字節值進行復雜度為O(1)的計算，即可獲得滑動后的窗口內部字節數組的哈希值。因為每個字節的數值最多有256種可能，可以通過預先的計算，將滑入和滑出字節相關的計算制成表格，之后，只需要通過查表和簡單的位移操作和加減操作即可獲得滑動后的哈希值，大大提高了CDC算法的運算效率。
其次，AegeanStore引入了雙閾值雙除數算法(TTTD)[10]，對CDC算法進一步優化。TTTD算法規定了數據塊大小的最小值Smin。每一個可變數據塊從開始到Smin的區間內的數據不需要進行哈希值計算。TTTD算法是為了對付可變數據塊劃分結果中數據塊大小差異太大而造成的冗余刪除率較差的問題，經試驗證明，Smin:S約等于0.85時，可以獲得最好的冗余刪除率。所以使用TTTD算法可以大大降低冗余數據刪除的計算開銷，提高AegeanStore客戶端的運行效率。
3.2 索引服務的優化
AegeanStore的索引服務通過采用3種優化方法，改進索引服務的數字指紋查詢效率，以提高冗余數據刪除技術在分布式存儲系統中的性能。
(1)基于文件的批量數字指紋查詢
AegeanStore提出了基于文件的批量數字指紋查詢協議，將相同文件的數據指紋列表，連同該文件的路徑、大小等元數據信息，組織到同一個文件上傳請求當中。經過這樣的優化，既減少了AegeanStore客戶端的網絡請求數，增大了每個請求的數據量，提高網絡資源的利用率；并且，讓索引服務一次可以處理很多個數字指紋的索引查詢，增加了索引服務的吞吐量；更重要的是，使同一個文件的數據塊的數字指紋之間所存在的局部性得以保持，為索引服務進行預取和緩存等進一步優化創造了條件。
(2)基于Bloom filter的快速新數據塊過濾
Bloom filter[11]是一種高效的利用有限的內存空間，以一定錯誤肯定率為代價，用于快速的判斷某一個元素是否在一個集合中的概率性數據結構。在AegeanStore的索引服務當中，使用一臺性能較好、內存空間較大的服務器來運行快速新數據過濾模塊。一個存于內存中的Bloom filter作為該模塊的核心數據結構。當接收到由請求節點轉發來的基于文件的批量數字指紋查詢請求之后，將其中每一個數字指紋送到Bloom filter中進行判斷其是否存在于AegeanStore當中。如果判定結果為可能存在，則將其忽略；如果為一定不存在，則將這個數字指紋標記為新數據塊；將標記后的數字指紋列表，返回給請求節點；最后，當數據塊被成功上傳到數據塊服務之后，將其對應的數字指紋加入到Bloom filter當中。
(3)基于文件局部性的緩存和預取
文件局部性是指出現在相同文件中的數據塊，再次出現在相同文件中的概率會比較高。文件局部性通過使用基于文件的批量索引請求被保存到索引服務當中，與某數字指紋具有文件局部性的其他數字指紋的列表稱之為局部性列表。緩存和預取節點中的緩存的數據結構提供Key/Value式的接口，同樣以數字指紋作為Key，以其局部性列表作為Value。當索引查找的數字指紋列表被分配到某個緩存和預取節點后，處理流程如下：對于每一個沒有被標記為新的數字指紋，首先到緩存中查找該數字指紋，如果命中，說明該數據塊已經存在于AegeanStore當中，將文件的數字指紋列表和緩存中局部性列表合并，并在結果中標記該塊為存在；若未命中，則到DHT中進行查找，如果命中，將DHT中存儲的局部性列表加入緩存當中，完成預取工作，之后的處理和緩存命中時相同；如果未命中，即該數據塊不存在于AegeanStore當中，在快速過濾模塊當中出現了錯誤的情況。
4 結束語
本文提出了廣域網環境下的分布式存儲系統原型AegeanStore。AegeanStore在提供互聯網上的存儲服務的同時，還為網絡應用的開發提供了框架和通用的功能模塊，以提高網絡應用開發和運營的效率，并降低其成本。分布式存儲系統中普遍存在的冗余數據，不僅浪費了存儲系統的資源，而且造成了存儲系統的性能損失。AegeanStore通過采用客戶端相關的冗余數據刪除技術，可提高對存儲資源以及網絡資源的利用率，降低運營成本，提高可擴展性以及整體性能。
5 參考文獻
[1] Amazon Simple Storage Service (Amazon S3) [EB/OL]. [2010-06-16]. http://aws.amazon.com/s3/.
[2] 敖莉, 舒繼武, 李明強. 重復數據刪除技術研究綜述 [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.
尹玉冰，清華大學高性能計算研究所在讀碩士研究生，主要研究領域為存儲系統。
孫競，清華大學高性能計算研究所在讀博士研究生，主要研究領域為分布式系統。
余宏亮，清華大學高性能計算研究所副教授、博士，主要研究領域為并行與分布式系統，曾作為主要成員參與和負責了5項國家級基金項目的研究工作，已在國內外重要學術刊物和會議上發表論文30余篇。