分布式存儲系統憑借優秀的可擴展性、可用性、可靠性、易管理性、高性能和低成本等優勢，在網絡應用的構建中，獲得了廣泛的認可。分布式存儲系統中存儲了海量的數據，這些數據中存在著大量的冗余，將冗余數據刪除技術應用到分布式存儲系統當中，用來發現并去除數據中的冗余，可以有效的提高存儲空間以及網絡帶寬的利用率。本文設計并實現了廣域網環境下的分布式冗余刪除存儲系統AegeanStore，在冗余數據被上傳到AegeanStore之前將其去除，達到提高存儲資源和網絡資源利用率的目的，并且進一步的降低存儲系統的成本，在保持分布式系統固有的容災特性同時，提高了存儲系統的可擴展性和整體性能

本文提出一種在廣域網環境下的采用冗余數據刪除技術的分布式存儲系統原型——AegeanStore。在AegeanStore中采用客戶端相關的冗余數據刪除技術。該技術通過客戶端和服務器端的合作，不僅可提高存儲設備的利用率，而且可減輕客戶端和服務器之間的網絡負載壓力，從而進一步提高存儲系統的可擴展性和整體性能并且進一步降低其成本。

1 冗余數據刪除技術

冗余數據就是一個數據表中，這個表中的行包含了一些相同的值，這些值理論上來說應該是唯一的（這些值一般來說能確定一條記錄）例如，像社會保險號，姓與名的集合。那么我們把這么含有相同信息的行中包含的數據叫做冗余數據，現在所有的數據庫表中都有主鍵約束，主鍵中記錄了一行記錄中的唯一值，從數據庫的角度來看，每一行都是唯一的，但是從我們用戶角度看來，這些記錄都是相同的記錄，因為它們都包含相同的鍵值（FirstName+LastName），即使他們有不同的主鍵

冗余數據刪除技術是將數據集中的冗余數據發現并去除的應用技術，可以分為兩大類：相同數據刪除和相似數據刪除。

1.1 相同數據刪除技術

相同數據刪除技術首先將數據劃分為數據塊，然后使用具有抗碰撞特性[3]的哈希函數計算每一個數據塊的哈希值作為該數據塊的數字指紋，再通過比較數據塊的數字指紋來發現相同的數據塊。目前，最常用的相同數據刪除技術是基于內容的劃塊（CDC）算法，其流程如圖1所示。

CDC算法存在3個參數，一是目標可變數據塊的預期大小S，二是滑動窗口的大小W，三是一個小于S的自然數M。當使用CDC算法處理一個文件時，從文件頭開始以每次一字節的步長向后滑動窗口，使用哈希函數計算滑動窗口內部的哈希值H；將H mod S與M進行比較，如果不同，則滑動窗口；如果相同，則發現數據塊邊界，然后用具有抗碰撞特性的哈希函數計算該數據塊的數字指紋；最后，將獲得的數字指紋到索引中查找，如果存在則發現冗余數據塊，否則說明該數據塊是新的，需要存儲到系統當中。

1.2 相似數據刪除技術

相似數據刪除技術分為兩個階段，相似數據檢測和相似數據編碼：

（1）相似數據檢測，首先要定義數據的特征值，該特征值的特點是保證具有相同或相似的特征值的數據具有相同或相似的內容。在提取數據的特征值之后，通過特征值的比較獲得相似的數據。常用的相似數據檢測技術包括基于Shingle的檢測技術。

（2）相似數據編碼是在使用相似數據檢測，獲得具有相似性的數據集之后，在該數據集上采用的編碼技術，用于減小該數據集所占用的存儲空間。常用的相似數據編碼技術包括基于Diff的相似編碼技術等。

2 AegeanStore的體系結構

AegeanStore體系結構如圖2所示。AegeanStore由客戶端、應用服務、文件系統服務、索引服務和數據塊服務5個部分組成。

當客戶端需要將文件數據存儲到應用服務時，首先調用本地冗余數據刪除工具，運行數據塊劃分算法，將要上傳的文件分成數據塊，并計算每個數據塊的數字指紋，然后將這些數字指紋發送給應用服務；客戶端按照返回結果，只將未出現在數據塊服務中的數據塊上傳；最后，當所有新數據塊都存儲到數據塊服務中之后，文件服務將新數據塊的信息更新到索引服務當中。下面將分別介紹5個部分的設計與實現。

2.1 客戶端

客戶端是為某個應用服務開發，運行在使用該應用服務的用戶的網絡終端上的程序。程序通過響應用戶輸入并且同該應用服務進行消息交換，使用戶能夠使用該應用服務提供的服務。AegeanStore的客戶端除了完成傳統網絡應用的客戶端的響應用戶輸入、網絡消息交換、身份驗證、數據傳輸等任務之外，還要在冗余數據刪除技術中，完成重要的任務：因在獲得需要上傳文件的所有數據塊的數字指紋后，通過應用服務提供的網絡接口，查詢這些文件塊是否已經在AegeanStore中存在，然后將新的數據塊上傳到數據塊服務部分，完成數據上傳過程；同時，客戶端需要管理已經存儲在本地的數據塊的數字指紋，用于下載時減少冗余數據傳輸。

2.2 應用服務

應用服務是以AegeanStore提供的存儲服務、開發框架和功能組件為基礎，構建而成的網絡應用服務。AegeanStore作為網絡應用開發的基礎平臺，為了方便應用服務的開發，提供了應用服務的開發框架，使得應用服務的開發可以忽略網絡應用中網絡端口監聽、工作進程派生、負載均衡和調度等問題，專心解決應用服務的事務邏輯，使應用服務的開發工作更加方便快捷。除此之外，AegeanStore還為應用服務的開發者提供用戶管理、網絡消息交換等常用的功能組件，從而提高在AegeanStore上開發應用服務效率，降低應用服務的開發和運營成本。

2.3 分布式系統

分布式軟件系統（Distributed Software Systems）是支持分布式處理的軟件系統，是在由通信網絡互聯的多處理機體系結構上執行任務的系統。它包括分布式操作系統、分布式程序設計語言及其編譯（解釋）系統、分布式文件系統和分布式數據庫系統等。

分布式操作系統負責管理分布式處理系統資源和控制分布式程序運行。它和集中式操作系統的區別在于資源管理、進程通信和系統結構等方面。

分布式程序設計語言用于編寫運行于分布式計算機系統上的分布式程序。一個分布式程序由若干個可以獨立執行的程序模塊組成，它們分布于一個分布式處理系統的多臺計算機上被同時執行。它與集中式的程序設計語言相比有三個特點：分布性、通信性和穩健性。

2.4 文件系統服務

文件系統服務為AegeanStore提供文件系統視圖和文件管理接口。目前常用的提供公共存儲服務的分布式存儲系統當中，普遍使用的應用程序接口是Key/Value式的。雖然這種接口在開發應用服務時使用比較方便，但是與用戶習慣的基于目錄結構的文件系統式接口差異較大，導致大多數構建在Key/Value接口上的應用服務都要開發功能相似的文件系統視圖。所以，AegeanStore為應用服務開發提供的接口是文件系統式的，以提高應用服務的開發效率，避免重復開發，并通過使用分布式B樹、網絡就近訪問、代理訪問等優化技術，提高存儲系統的吞吐量。

2.5 索引服務

索引服務中存儲了AegeanStore中所有數據塊的數字指紋的索引，并提供網絡查詢索引接口，用來判斷數字指紋所對應的數據塊是否已經存在于AegeanStore當中。由于AegeanStore存儲系統具有良好的可擴展性，其數據規模可以達到數百太字節甚至拍字節級，所以索引服務應該支持太字節級別的索引存儲。

2.6 數據塊服務

AegeanStore的數據塊服務提供分布式的基于內容定位的存儲系統[7]，其提供的接口是Key/Value形式的。數據塊服務由接口、一跳分布式哈希表（DHT）[8]和數據塊存儲節點3部分組成：當用戶存儲數據塊時，以該數據塊的數字指紋作為Key進行存儲；首先到一跳分布式哈希表中，查找該數字指紋，因為數字指紋由數據塊的內容決定，所以，如果該數字指紋已經存在于分布式哈希表當中，說明該數據塊已經存在于數據塊服務當中，無需再次存儲；如果不存在，將數據塊存入數據塊存儲節點，將數字指紋和所存儲的位置信息存入一跳分布式哈希表作為索引。塊存儲服務從分布式哈希表中查找是否存在這個數字指紋，如果存在則根據在其中獲得的數據塊位置從存儲節點讀取相應數據塊并返回給用戶，否則返回空。

3 冗余刪除技術的優化

將冗余數據刪除技術應用于分布式存儲系統將遇到兩個問題。

（1）由于CDC算法開銷過大，無法滿足廣域網環境中的分布式存儲系統的客戶端的異構性帶來的計算性能瓶頸。

（2）由于分布式存儲系統的高可擴展性，造成索引服務中數字指紋索引過大，從而帶來的數字指紋索引查詢的性能瓶頸。

3.1 CDC算法的優化

CDC算法中，無論在計算滑動窗口內的哈希值，還是獲得數據塊劃分之后計算數據塊的數字指紋都是計算密集型工作。在手機或上網本等運算能力較差的設備上，由于存在著性能瓶頸，制約了客戶端相關的冗余數據刪除技術的有效應用。

首先，在AegeanStore的客戶端中，為了優化CDC算法的運行效率，在計算滑動窗口的哈希值時，采用了Rabin’s Fingerprinting哈希函數進行計算。因Rabin’s Fingerprinting哈希函數具有可迭代計算的特性，滑動窗口時，只需要通過將滑動前哈希值、滑入字節值和滑出字節值進行復雜度為O的計算，即可獲得滑動后的窗口內部字節數組的哈希值。因為每個字節的數值最多有256種可能，可以通過預先的計算，將滑入和滑出字節相關的計算制成表格，之后，只需要通過查表和簡單的位移操作和加減操作即可獲得滑動后的哈希值，大大提高了CDC算法的運算效率。

3.2 索引服務的優化

AegeanStore的索引服務通過采用3種優化方法，改進索引服務的數字指紋查詢效率，以提高冗余數據刪除技術在分布式存儲系統中的性能。

（1）基于文件的批量數字指紋查詢

AegeanStore提出了基于文件的批量數字指紋查詢協議，將相同文件的數據指紋列表，連同該文件的路徑、大小等元數據信息，組織到同一個文件上傳請求當中。并且，讓索引服務一次可以處理很多個數字指紋的索引查詢，增加了索引服務的吞吐量；更重要的是，使同一個文件的數據塊的數字指紋之間所存在的局部性得以保持，為索引服務進行預取和緩存等進一步優化創造了條件。

（2）基于Bloom filter的快速新數據塊過濾

Bloom filter[11]是一種高效的利用有限的內存空間，以一定錯誤肯定率為代價，用于快速的判斷某一個元素是否在一個集合中的概率性數據結構。在AegeanStore的索引服務當中，使用一臺性能較好、內存空間較大的服務器來運行快速新數據過濾模塊。一個存于內存中的Bloom filter作為該模塊的核心數據結構。如果為一定不存在，則將這個數字指紋標記為新數據塊；將標記后的數字指紋列表，返回給請求節點；最后，當數據塊被成功上傳到數據塊服務之后，將其對應的數字指紋加入到Bloom filter當中。

（3）基于文件局部性的緩存和預取

文件局部性是指出現在相同文件中的數據塊，再次出現在相同文件中的概率會比較高。緩存和預取節點中的緩存的數據結構提供Key/Value式的接口，同樣以數字指紋作為Key，以其局部性列表作為Value。當索引查找的數字指紋列表被分配到某個緩存和預取節點后，處理流程如下：對于每一個沒有被標記為新的數字指紋，首先到緩存中查找該數字指紋，如果命中，說明該數據塊已經存在于AegeanStore當中，將文件的數字指紋列表和緩存中局部性列表合并，并在結果中標記該塊為存在；若未命中，則到DHT中進行查找，如果命中，將DHT中存儲的局部性列表加入緩存當中，完成預取工作，之后的處理和緩存命中時相同；如果未命中，即該數據塊不存在于AegeanStore當中，在快速過濾模塊當中出現了錯誤的情況。

4 結束語

本文提出了廣域網環境下的分布式存儲系統原型AegeanStore。AegeanStore在提供互聯網上的存儲服務的同時，還為網絡應用的開發提供了框架和通用的功能模塊，以提高網絡應用開發和運營的效率，并降低其成本。分布式存儲系統中普遍存在的冗余數據，不僅浪費了存儲系統的資源，而且造成了存儲系統的性能損失。AegeanStore通過采用客戶端相關的冗余數據刪除技術，可提高對存儲資源以及網絡資源的利用率，降低運營成本，提高可擴展性以及整體性能，給公司帶來豐厚的利潤。