一種廣域網(wǎng)環(huán)境下的分布式冗余刪除存儲系統

由于數字信息的爆炸式增長(cháng)，現今的大規模網(wǎng)絡(luò )應用中所存儲的數據規模，可以到達上百太字節甚至拍字節的數量級。而傳統的存儲系統，由于缺乏足夠的可擴展性，無(wú)法適應日益增長(cháng)的需求。以Amazon S3[1]為代表的廣域網(wǎng)環(huán)境下的分布式存儲系統憑借其規模的可擴展性、數據的可靠性、服務(wù)的可用性、系統的可管理性以及低廉的使用成本等巨大優(yōu)勢，已經(jīng)在構建網(wǎng)絡(luò )應用時(shí)被廣泛認可。

廣域網(wǎng)環(huán)境下的分布式存儲系統將分布在廣域網(wǎng)上的資源整合在一起，為網(wǎng)絡(luò )應用提供存儲服務(wù)平臺。來(lái)自不同網(wǎng)絡(luò )應用和用戶(hù)的數據存儲其中，這些海量的數據中存在著(zhù)大量的冗余。這些冗余數據不僅在存儲時(shí)占據了存儲系統大量的存儲空間，并且在被傳輸到存儲系統的過(guò)程當中，浪費了大量的網(wǎng)絡(luò )用戶(hù)、網(wǎng)絡(luò )應用和存儲系統的網(wǎng)絡(luò )帶寬資源，使存儲系統的資源利用率和整體性能受到嚴重影響。

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

1 冗余數據刪除技術(shù)

冗余數據刪除技術(shù)是將數據集中的冗余數據發(fā)現并去除的應用技術(shù)，可以分為兩大類(lèi)：相同數據刪除和相似數據刪除[2]。

1.1 相同數據刪除技術(shù)

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

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

1.2 相似數據刪除技術(shù)

相似數據刪除技術(shù)分為兩個(gè)階段，相似數據檢測和相似數據編碼：

(1)相似數據檢測，首先要定義數據的特征值，該特征值的特點(diǎn)是保證具有相同或相似的特征值的數據具有相同或相似的內容。在提取數據的特征值之后，通過(guò)特征值的比較獲得相似的數據。常用的相似數據檢測技術(shù)包括基于Shingle的檢測技術(shù)[5]。

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

2 AegeanStore的體系結構

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

當客戶(hù)端需要將文件數據存儲到應用服務(wù)時(shí)，首先調用本地冗余數據刪除工具，運行數據塊劃分算法，將要上傳的文件分成數據塊，并計算每個(gè)數據塊的數字指紋，然后將這些數字指紋發(fā)送給應用服務(wù)；應用服務(wù)接收到文件上傳請求后，記錄應用相關(guān)信息，再將請求轉發(fā)給文件服務(wù)；文件服務(wù)記錄文件的元信息(包括文件屬性，例如文件的大小、修改時(shí)間等,以及文件的冗余數據刪除信息，如文件所有組成數據塊的數字指紋等)，再將請求轉發(fā)給索引服務(wù)；索引服務(wù)進(jìn)行塊的數字指紋查詢(xún)工作，將結果返回給文件服務(wù)；文件服務(wù)將結果通過(guò)應用服務(wù)返回給客戶(hù)端；客戶(hù)端按照返回結果，只將未出現在數據塊服務(wù)中的數據塊上傳；最后，當所有新數據塊都存儲到數據塊服務(wù)中之后，文件服務(wù)將新數據塊的信息更新到索引服務(wù)當中。下面將分別介紹5個(gè)部分的設計與實(shí)現。

2.1 客戶(hù)端

客戶(hù)端是為某個(gè)應用服務(wù)開(kāi)發(fā)，運行在使用該應用服務(wù)的用戶(hù)的網(wǎng)絡(luò )終端上的程序。程序通過(guò)響應用戶(hù)輸入并且同該應用服務(wù)進(jìn)行消息交換，使用戶(hù)能夠使用該應用服務(wù)提供的服務(wù)。AegeanStore的客戶(hù)端除了完成傳統網(wǎng)絡(luò )應用的客戶(hù)端的響應用戶(hù)輸入、網(wǎng)絡(luò )消息交換、身份驗證、數據傳輸等任務(wù)之外，還要在冗余數據刪除技術(shù)中，完成重要的任務(wù)：因為AegeanStore使用冗余數據刪除技術(shù)的目標是減少冗余數據在網(wǎng)絡(luò )傳輸時(shí)造成的浪費，所以冗余數據刪除中的可變數據塊劃分和計算每個(gè)數據塊的數字指紋等工作必須在客戶(hù)端完成。在獲得需要上傳文件的所有數據塊的數字指紋后，通過(guò)應用服務(wù)提供的網(wǎng)絡(luò )接口，查詢(xún)這些文件塊是否已經(jīng)在A(yíng)egeanStore中存在，然后將新的數據塊上傳到數據塊服務(wù)部分，完成數據上傳過(guò)程；同時(shí)，客戶(hù)端需要管理已經(jīng)存儲在本地的數據塊的數字指紋，用于下載時(shí)減少冗余數據傳輸。

2.2 應用服務(wù)

應用服務(wù)是以AegeanStore提供的存儲服務(wù)、開(kāi)發(fā)框架和功能組件為基礎，構建而成的網(wǎng)絡(luò )應用服務(wù)。AegeanStore作為網(wǎng)絡(luò )應用開(kāi)發(fā)的基礎平臺，為了方便應用服務(wù)的開(kāi)發(fā)，提供了應用服務(wù)的開(kāi)發(fā)框架，使得應用服務(wù)的開(kāi)發(fā)可以忽略網(wǎng)絡(luò )應用中網(wǎng)絡(luò )端口監聽(tīng)、工作進(jìn)程派生、負載均衡和調度等問(wèn)題，專(zhuān)心解決應用服務(wù)的事務(wù)邏輯，使應用服務(wù)的開(kāi)發(fā)工作更加方便快捷。應用服務(wù)開(kāi)發(fā)者只需要將自己開(kāi)發(fā)的消息處理模塊和消息序列化/反序列化模塊注冊到應用服務(wù)框架當中，即可被框架自動(dòng)調用，進(jìn)而提供網(wǎng)絡(luò )應用服務(wù)。除此之外，AegeanStore還為應用服務(wù)的開(kāi)發(fā)者提供用戶(hù)管理、網(wǎng)絡(luò )消息交換等常用的功能組件，從而提高在A(yíng)egeanStore上開(kāi)發(fā)應用服務(wù)效率，降低應用服務(wù)的開(kāi)發(fā)和運營(yíng)成本。

2.3 文件系統服務(wù)

文件系統服務(wù)為AegeanStore提供文件系統視圖和文件管理接口。目前常用的提供公共存儲服務(wù)的分布式存儲系統當中，普遍使用的應用程序接口是Key/Value式的。雖然這種接口在開(kāi)發(fā)應用服務(wù)時(shí)使用比較方便，但是與用戶(hù)習慣的基于目錄結構的文件系統式接口差異較大，導致大多數構建在Key/Value接口上的應用服務(wù)都要開(kāi)發(fā)功能相似的文件系統視圖。這些重復開(kāi)發(fā)增加了應用服務(wù)開(kāi)發(fā)的難度和成本，更重要的是，因為缺少存儲系統內部信息的輔助，無(wú)法利用數據的局部性和網(wǎng)絡(luò )的就近訪(fǎng)問(wèn)等優(yōu)化技術(shù)，在Key/Value接口上構建的文件系統效率往往較低，對應用服務(wù)以及存儲系統的網(wǎng)絡(luò )和存儲資源造成了嚴重的浪費。所以，AegeanStore為應用服務(wù)開(kāi)發(fā)提供的接口是文件系統式的，以提高應用服務(wù)的開(kāi)發(fā)效率，避免重復開(kāi)發(fā)，并通過(guò)使用分布式B樹(shù)、網(wǎng)絡(luò )就近訪(fǎng)問(wèn)、代理訪(fǎng)問(wèn)等優(yōu)化技術(shù)，提高存儲系統的吞吐量。

2.4 索引服務(wù)

索引服務(wù)中存儲了AegeanStore中所有數據塊的數字指紋的索引，并提供網(wǎng)絡(luò )查詢(xún)索引接口，用來(lái)判斷數字指紋所對應的數據塊是否已經(jīng)存在于A(yíng)egeanStore當中。以SHA-1哈希函數計算出來(lái)的數據指紋為例，每個(gè)塊的數字指紋大小為20 B，假設可變塊劃分算法所分的數據塊的平均大小為4 kB，則索引服務(wù)中存儲的數字指紋索引的數據規模為實(shí)際存儲數據規模的0.5%。由于A(yíng)egeanStore存儲系統具有良好的可擴展性，其數據規?？梢赃_到數百太字節甚至拍字節級，所以索引服務(wù)應該支持太字節級別的索引存儲。

2.5 數據塊服務(wù)

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

3 冗余刪除技術(shù)的優(yōu)化

將冗余數據刪除技術(shù)應用于分布式存儲系統將遇到兩個(gè)問(wèn)題。

(1)由于CDC算法開(kāi)銷(xiāo)過(guò)大，無(wú)法滿(mǎn)足廣域網(wǎng)環(huán)境中的分布式存儲系統的客戶(hù)端的異構性帶來(lái)的計算性能瓶頸。

(2)由于分布式存儲系統的高可擴展性，造成索引服務(wù)中數字指紋索引過(guò)大，從而帶來(lái)的數字指紋索引查詢(xún)的性能瓶頸。

3.1 CDC算法的優(yōu)化

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

首先，在A(yíng)egeanStore的客戶(hù)端中，為了優(yōu)化CDC算法的運行效率，在計算滑動(dòng)窗口的哈希值時(shí)，采用了Rabin’s Fingerprinting[9]哈希函數進(jìn)行計算。因Rabin’s Fingerprinting哈希函數具有可迭代計算的特性，滑動(dòng)窗口時(shí)，只需要通過(guò)將滑動(dòng)前哈希值、滑入字節值和滑出字節值進(jìn)行復雜度為O(1)的計算，即可獲得滑動(dòng)后的窗口內部字節數組的哈希值。因為每個(gè)字節的數值最多有256種可能，可以通過(guò)預先的計算，將滑入和滑出字節相關(guān)的計算制成表格，之后，只需要通過(guò)查表和簡(jiǎn)單的位移操作和加減操作即可獲得滑動(dòng)后的哈希值，大大提高了CDC算法的運算效率。

其次，AegeanStore引入了雙閾值雙除數算法(TTTD)[10]，對CDC算法進(jìn)一步優(yōu)化。TTTD算法規定了數據塊大小的最小值Smin。每一個(gè)可變數據塊從開(kāi)始到Smin的區間內的數據不需要進(jìn)行哈希值計算。TTTD算法是為了對付可變數據塊劃分結果中數據塊大小差異太大而造成的冗余刪除率較差的問(wèn)題，經(jīng)試驗證明，Smin:S約等于0.85時(shí)，可以獲得最好的冗余刪除率。所以使用TTTD算法可以大大降低冗余數據刪除的計算開(kāi)銷(xiāo)，提高AegeanStore客戶(hù)端的運行效率。

3.2 索引服務(wù)的優(yōu)化

AegeanStore的索引服務(wù)通過(guò)采用3種優(yōu)化方法，改進(jìn)索引服務(wù)的數字指紋查詢(xún)效率，以提高冗余數據刪除技術(shù)在分布式存儲系統中的性能。

(1)基于文件的批量數字指紋查詢(xún)

AegeanStore提出了基于文件的批量數字指紋查詢(xún)協(xié)議，將相同文件的數據指紋列表，連同該文件的路徑、大小等元數據信息，組織到同一個(gè)文件上傳請求當中。經(jīng)過(guò)這樣的優(yōu)化，既減少了AegeanStore客戶(hù)端的網(wǎng)絡(luò )請求數，增大了每個(gè)請求的數據量，提高網(wǎng)絡(luò )資源的利用率；并且，讓索引服務(wù)一次可以處理很多個(gè)數字指紋的索引查詢(xún)，增加了索引服務(wù)的吞吐量；更重要的是，使同一個(gè)文件的數據塊的數字指紋之間所存在的局部性得以保持，為索引服務(wù)進(jìn)行預取和緩存等進(jìn)一步優(yōu)化創(chuàng )造了條件。

(2)基于Bloom filter的快速新數據塊過(guò)濾

Bloom filter[11]是一種高效的利用有限的內存空間，以一定錯誤肯定率為代價(jià)，用于快速的判斷某一個(gè)元素是否在一個(gè)集合中的概率性數據結構。在A(yíng)egeanStore的索引服務(wù)當中，使用一臺性能較好、內存空間較大的服務(wù)器來(lái)運行快速新數據過(guò)濾模塊。一個(gè)存于內存中的Bloom filter作為該模塊的核心數據結構。當接收到由請求節點(diǎn)轉發(fā)來(lái)的基于文件的批量數字指紋查詢(xún)請求之后，將其中每一個(gè)數字指紋送到Bloom filter中進(jìn)行判斷其是否存在于A(yíng)egeanStore當中。如果判定結果為可能存在，則將其忽略；如果為一定不存在，則將這個(gè)數字指紋標記為新數據塊；將標記后的數字指紋列表，返回給請求節點(diǎn)；最后，當數據塊被成功上傳到數據塊服務(wù)之后，將其對應的數字指紋加入到Bloom filter當中。

(3)基于文件局部性的緩存和預取

文件局部性是指出現在相同文件中的數據塊，再次出現在相同文件中的概率會(huì )比較高。文件局部性通過(guò)使用基于文件的批量索引請求被保存到索引服務(wù)當中，與某數字指紋具有文件局部性的其他數字指紋的列表稱(chēng)之為局部性列表。緩存和預取節點(diǎn)中的緩存的數據結構提供Key/Value式的接口，同樣以數字指紋作為Key，以其局部性列表作為Value。當索引查找的數字指紋列表被分配到某個(gè)緩存和預取節點(diǎn)后，處理流程如下：對于每一個(gè)沒(méi)有被標記為新的數字指紋，首先到緩存中查找該數字指紋，如果命中，說(shuō)明該數據塊已經(jīng)存在于A(yíng)egeanStore當中，將文件的數字指紋列表和緩存中局部性列表合并，并在結果中標記該塊為存在；若未命中，則到DHT中進(jìn)行查找，如果命中，將DHT中存儲的局部性列表加入緩存當中，完成預取工作，之后的處理和緩存命中時(shí)相同；如果未命中，即該數據塊不存在于A(yíng)egeanStore當中，在快速過(guò)濾模塊當中出現了錯誤的情況。

4 結束語(yǔ)

本文提出了廣域網(wǎng)環(huán)境下的分布式存儲系統原型AegeanStore。AegeanStore在提供互聯(lián)網(wǎng)上的存儲服務(wù)的同時(shí)，還為網(wǎng)絡(luò )應用的開(kāi)發(fā)提供了框架和通用的功能模塊，以提高網(wǎng)絡(luò )應用開(kāi)發(fā)和運營(yíng)的效率，并降低其成本。分布式存儲系統中普遍存在的冗余數據，不僅浪費了存儲系統的資源，而且造成了存儲系統的性能損失。AegeanStore通過(guò)采用客戶(hù)端相關(guān)的冗余數據刪除技術(shù)，可提高對存儲資源以及網(wǎng)絡(luò )資源的利用率，降低運營(yíng)成本，提高可擴展性以及整體性能。