網絡環境下基于Ｅｒａｓｕｒｅ Ｃｏｄｅｓ的高可靠性存儲體系設計

(西北工業大學 計算機學院 西安 710072)

摘 要：設計了一種基于Erasure Codes的網絡環境下的分布式文件存儲系統。初步的實驗結果證明這種存儲體系可以較好地解決人們當前所面臨的文件存儲的可靠性、安全性等問題。

關鍵詞：分布式存儲；數據可靠性；數據安全性；糾錯碼；加羅華域

中圖分類號：TP333.8文獻標志碼：A

文章編號：1001-3695(2009)05-1835-04

Design of storage scheme with high reliabilitybased on Erasure Codes in environment of networks

JIA Junbo，GU Jianhua，ZHU Jingfei，ZHANG Jiwei

(College of Computer Science Northwestern Polytechnical University Xi’an 710072 China)

Abstract:This paper provided a distributed storage scheme based on Erasure Codes in the environment of networks.Testing result proves that the scheme will ensure the high reliability and high security.

Key words:distributed storage；data reliability；data security；Erasure Codes；Galois field

隨著計算機的普及，人們逐漸習慣用計算機來處理各種信息，對計算機的依賴性也越來越強，伴隨而來的是大量數據的產生。相對于以往的各種信息管理方式，信息的數字化存儲具有容量大、易操作和可異地操作等特性。這種存儲方式有著巨大的優越性，同時這種單機文件存儲的方式也存在著極大的可靠性和安全性隱患。為了應對人們日益復雜的存儲需求，人們提出基于網絡的存儲方式，將數據存放在遠程分布的服務器上，這樣可以極大地擴充文件的存儲空間，同時便于數據的訪問、管理及共享。很多組織一直致力于這方面的研究。Berkeley大學提出的OceanStore存儲方案，是一種基于全球環境下的海量存儲機制^[1]；ESStore^[2]描述了一種用于提高基于分布式hash表的結構化P2P 存儲系統可靠性和可用性的機制。清華大學也提出了自己的Granary存儲系統。但當前大部分的網絡存儲機制的研究和開發都是針對數據的海量存儲和管理而提出的。本文針對在某些對文件的可靠性和安全性要求較高的領域（如國家科研院所），提出一種在網絡環境下提高文件的可靠性和安全性的存儲機制以及實現算法。

1 系統構架

該系統建立在網絡環境下，基于可擦除碼原理。其完成的主要功能如圖1所示。網絡中某個節點需要存儲數據時，它在本地機器上將需要存儲的信息進行分割編碼以后，將子文件分布存儲在其他可信任的機器上。當需要恢復文件時，該用戶只需要回收少量（總量和原始文件相等）任意的子文件便可將原來文件恢復。在原文件恢復之前，任何子文件都處于不可用狀態，并且原文件的恢復只授權于該文件用戶。該系統主要分為文件的編碼、數據存儲、數據回收、解碼四個過程，文件在本地節點的編碼和解碼將在第2章論述。下面介紹節點的交互過程。

1.1 信息列表的構造

該系統整體為一個P2P構架，但是仍然存在服務器的概念。服務器在該系統中只做節點信息查詢功能，不參與信息的傳輸和存儲。服務器通過維護一個信息列表來顯示系統中各節點的可用性信息。如圖1，該信息列表的構造分為公有和私有兩部分。公有部分供所有節點讀寫，每個用戶又對應一個私有的信息列表；私有部分只有對應惟一的用戶可以讀寫。

公有部分如圖1的左邊列表，存儲了節點地址，可用性及空間大小三項內容。當某個節點加入到該系統時，向服務器注冊其節點號或激活其可用性和所剩空間，表明該節點可用以及具體的可用空間大小。

每個節點用戶對應一個私有部分，如圖1的右邊部分。私有部分只能通過用戶驗證來訪問，每個用戶只能訪問自己的私有列表內容，其內容包括自己存儲在其他節點上的存儲信息標志和存儲信息的節點地址兩項內容（當服務器失效時，通過廣播，重構信息列表，這里不再討論）。

1.2 存儲過程

當需要存儲的數據在本地開始編碼以后，隨即開始與其他節點進行交互存儲。數據的存儲過程主要分為注冊服務器、查詢服務器、存儲數據和寫服務器列表四部分。

1.2.1 注冊服務器

各個被授權的節點首先注冊到服務器，訪問服務列表，注冊節點地址或激活節點使能，并上傳可用空間大小。

1.2.2 查詢服務器

當某節點有需要存儲的信息時，向服務器發出查詢，服務器給出可供使用的節點地址。

1.2.3 存儲數據

當存儲結束時，各個節點向主機回復，確認存儲成功。

1.2.4 寫服務器列表

存儲節點在服務器上該用戶對應的私有列表上保存被存儲該信息的標志和保存該信息的節點地址（同時在本地節點做一備份）存儲完成。

1.3 恢復過程

該系統所要解決的主要問題之一就是當部分節點包括用戶節點自身出現突發問題導致信息不能被正確讀出來時，在一定的文件冗余度之下，保持原始信息的可恢復性。所以在文件恢復時，私有信息的獲取是通過用戶口令，用戶可以通過口令查詢其在服務器上的私有信息，然后向相關節點回收所需信息。

1.3.1 注冊服務器

用戶首先注冊服務器，在向服務器進行合法性驗證后，讀取該用戶的私有信息，讀取所需文件的存儲節點號。

1.3.2 發送請求

用戶向相關的節點發出消息，要求回傳子文件信息，各個相關節點在通過用戶合法性驗證之后回傳子文件。

1.3.3 數據恢復

用戶通過解碼子文件恢復原始信息，在恢復成功之后同時通知各個節點刪除相應的存儲內容，刪除在服務器上的相關信息。

如圖2所示，當0號節點加入該系統時，便在服務器列表上將該節點列表激活，然后在需要存儲時，將文件進行編碼，將三塊文件編碼為五塊。之后查詢列表，尋找可用節點，其中3號節點未被激活，而且6號節點存儲空間不夠，所以可以將五塊文件分別存儲在1、2、4、5、7節點上，當收到存儲確認時，在相應的私有列表上存儲相應的內容（圖2），存儲過程完畢。當0號節點需要恢復數據時，查詢私有列表，然后發現存儲節點中，2號節點未被激活，所以可以從1、4、5、7號節點中任意三個節點讀取三塊子文件，然后在本地將源文件恢復，之后通知相應節點刪除相應內容，更新服務列表，恢復完成。當本地節點不可用時，用戶通過登錄1號節點，然后通過系統認證，將文件進行恢復，所以部分節點的失效影響不到系統的恢復功能（圖3）。

2 編碼和解碼

文件的編碼和解碼主要基于可擦除碼理論，其實現方式為Erasure Codes、ReedSolomon Codes、矩陣變換等理論。

2.1 Erasure Codes

Erasure Codes作為一種FEC(forward error correction)技術，最初被提出來時是用來解決網絡中不相關丟包錯誤，它憑借對數據進行冗余編碼，然后依靠編碼后的數據對原數據進行最小塊數的恢復。其大致的工作過程如圖4所示。

對原始數據進行分割得到k塊子數據塊，對k個數據塊進行編碼得到n(n>k)個數據塊。由于傳輸過程導致得到的數據塊為k′≤n，但是只要k′≥k，解碼機制能夠用其中任意k個子文件塊對原文件進行恢復。可擦除碼進行理論研究同時也被應用到存儲、調至解調等其他領域，并探索出多種實現方法，如ReedSolomon Codes 和Tonardo Codes就是最常見的兩種編碼方式。

2.2 ReedSolomon Codes與Tonardo Codes

Tonardo Codes由Luby等人^[3]在1997年提出來的，相對于包含有多種運算的ReedSolomon Codes，Tonardo Codes只包含XOR（extended “OR”）運算的恢復體系，所以具有相當高的運算速度，用軟件實現的Tonardo Codes比ReedSolomon Codes快100～1 000倍，在Luby等人提出Tonardo Codes以后，隨即用Digital Fountain實現了該理論，并對代碼進行了專利申請。之后很多人都提出了相似的算法，但是幾乎沒有人實現相應的算法。現在對該系列算法和實現上的研究還一直在繼續^[4，5]。由于具有很高的編碼速度，Tonardo Codes適合在對實時性要求較高的通信領域實施。ReedSolomon Codes 作為一個比較成熟的方案，且不存在專利問題，適合在實時性要求不太高，而且考慮到系統的成本和實現難度，在該存儲系統中仍然采用ReedSolomon Codes來解決編碼技術。

2.3 ReedSolomon Codes 的實現

ReedSolomon Code的編/解碼建立在線性方程組、有限域和不可約多項式理論基礎之上。滿足一定條件線性方程存在相應的解，見文獻[4]。例如：

（1 2）1 21 1=（3 4）（1）

（3 4）-1 21 -1=（1 2）（2）

（1 2）1 2 11 1 3=（3 4 7）（3）

在式（1）中，1和2經過運算得到3和4，同時，3和4經過一定的逆運算也會得到1和2，見式（2）。如果將1、2看做原始信息，那么3、4將為編碼后的信息。從此可以看出，原始信息和編碼后的信息存在轉換和逆轉換的空間。那么如何實現信息的冗余編碼以及通過無關數據恢復原始數據呢？式（3）給出了一個很好的解決辦法，即通過多個多項式可以得到多個編碼后的數據3、4和7，同時，可以從3、4和7中任意取出兩個數字均可以逆變化出原始數據1和2（具體證明不再闡述）。但該矩陣需要滿足一定的條件，即任意兩列均是線性無關的。這樣就可以通過矩陣和逆矩陣來映射原始數據和編碼后的數據。將通過k個數據編碼后得到n個數據，再從n個編碼塊取出k塊來恢復原來的數據記做GF(n，k)（上例中的3和2分別對應n和k），那么對原文件進行編碼的關鍵問題在于構造一個m×n的方程組，使得其滿足任意m列可以構造一個m×n的可逆矩陣。Vandermonde行列式值滿足式（4）。

Dn=11…1

x1x2…xn

x21x22…x2n



xn-11xn-12…xn-1n=n≥i＞j≥1(xi-xj)(4)

由此可知，Vandermonde矩陣是構造滿足上述條件的矩陣的理想選擇。只要初始值滿足xi≠xj（i≠j），就會保證任意m列可以構造出一個可逆矩陣。但是矩陣運算會導致數據的膨脹和浮點數的出現，這樣會給數據的運算和存儲帶來極大的不方便。Galois Field（也叫Finite Field）的引入，可以控制在一個編碼過程中數據的膨脹，使得數據可以方便地運算或存儲。Galois Field的基本思想是對于任何的素數p都存在一個Galois Field，記為GF(p)，含有p個元素。可以將這個GF(p)擴展為GF(pm)，包含pm個數據。其中：m是正整數；GF(p)為GF(pm)的子域。通常用GF(2m)來構所羅門編碼的元素以及運算法則。在GF(2m)域中，除了0和1，通常還包括一個元素，記為α，該域中的其余元素將由{0，1，α}相互運算構成（包含α的自乘積運算），一個域又是建立在一個不可分解的多項式之上的^[6]，x3+x+1是一個不可分解的多項式，設α為x3+x+1=0的一個根，則可以根據該方程計算出GF(23)中其余的元素。如表1，同時可以根據mod2運算得到相應的運算規則^[7]。

式（5）為GF（23）中建立在x3+x+1之上的所有元素，表1為由此得出加法運算表；表2為乘法運算表，同時可以根據系數mod2得到相應的減法和除法表。那么就可以完成這個域中基本的復合運算。以Golois Field元素構造相應的Vandermonde矩陣，滿足運算的封閉性，避免了數據的膨脹。該系統的編碼、求逆、解碼運算開銷分別為O(n×m)、O(n×n×n)、O(n×n)。矩陣求逆的時間復雜度最大，所以一般通過構造求逆列表來求得逆矩陣。

文件的冗余編碼和恢復功能。同時，為了實現快速的矩陣變換，一般采用系統碼作為編碼基礎。

3 仿真與實驗結果分析

該存儲系統采用文件編碼機制主要解決在同樣冗余度的備份存儲基礎之上文件的可靠性問題，通過分布式存儲提高文件存儲的安全性。其中，文件可靠性基于大量獨立事件發生的統計穩定性；安全性基于大量獨立事件同時發生的概率隨著事件數量的增加逐漸趨向于無窮小。同時，作為存儲系統的時間效率問題也是需要關心的一個問題。下面通過對仿真和實驗數據的分析來對該存儲系統的性能進行直觀的了解。

文獻[8]給出了該系統的可用性P的計算方法，表示如下： 

其中：P為文件對象可用概率；n為文件對象編碼后的所有碎片的數目；m為重構文件對象所需要的碎片數目；n為系統中機器的數目；M為系統中當前不可用的機器數目，即文件對象可用的概率P等于存放在不可用的機器上的碎片數目少（n-m）的存儲方法比上所有碎片存放在任意機器上的方法數。假如單個文件的可靠性為95％，并且相互獨立；系統中可分配的節點數目為1 000，如果利用Erasure Codes以冗余度為2的編碼機制進行存儲，那么其可靠性隨著編碼子塊數的增加而變化的情況如圖5所示。從圖5可以看出，當編碼后的子文件塊數逐漸增加時，其系統可靠性急劇趨向于1。例如，在冗余率為2的條件下，通過RS(4，2)的Erasure Codes編碼系統進行存儲，可知其可用性大于0.999 756 453 66，而對于完全備份系統來說，它具有的可用性為0.997 5。

在安全性方面，文件被竊取的幾率與分布式存儲子文件數目呈指數關系，隨著子文件數目的增加，其被攻擊成功的可能性將趨向于無窮小。

在時效性能方面，其測試數據如圖6、7所示。其中，圖6為單機環境下文件的編/解碼速度圖，其測試環境為一臺Pentium 4 2.0 GHz處理器，磁盤讀寫速度為5400RPM的PC機，文件編碼率為RS(10，8)。圖7為網絡環境下的存儲、恢復速度測試結果，其測試環境為10臺上述配置的PC機器，100 Mbps網卡，100 Mbps交換機，文件編碼率為RS(5，4)。從測試結果可以看出，在上述條件下，單機上文件的編碼速度約為3.8 Mbps，恢復速度約為2.1 Mbps。而在網絡環境下由于存在各個工作環節銜接不優化，以及各種不可預知的因素，數據的存儲和恢復速度都遠遠小于單機文件的編碼和恢復速度。

網絡環境下文件的存儲和恢復過程的時效函數可表示為f（sread、sencode、stransmit、swrite）。四個相關參數依次表示文件讀速度、編碼速度、傳輸速度和寫速度。而且文件的存儲過程為一個讀取、編碼、傳輸、寫磁盤的四級流水過程，在文件的傳輸和技術部分為流水過程，其他時間里同時工作，卻又相互影響，所以整體速度受到最小處理速度環節的限制。在原型系統測試中，因為網絡環境的傳輸速度和磁盤的讀寫速度都為數十兆每秒，所以網絡環境下的讀寫速度主要受到文件編碼速度的限制。從上述的實驗結果可知，該原型系統可以滿足一般大小文件的存儲。同時，在單個PC機上作出的文件分割和恢復的模擬實驗中，10萬次的文件分割和恢復測試全部成功。另外，加密技術作為提高文件安全性的一種有效機制，作為該系統的一個應用接口，本文在此不予以討論。在整個信息的處理過程中，本文采用文件的小單位輪訓分割，而不是文件的整體分割，這樣，重組后的子文件能很好地對文件的真實信息進行隱藏。在筆者已進行的實驗中，對圖像進行分割編碼后，產生的子文件不可讀。文件的編碼是基于文件的ASCII值來進行計算的，以流的形式讀取，這樣可以保持文件處理速度的格式無關性。同時，多種編碼率、冗余率的選擇可以提高系統的靈活性。

4 結束語

微電子技術和工藝經過多年的高速發展，使得如今的單機性能已經得到了很大的提高。然而，人們在現有的計算機系統框架之下想再次大幅度提升單機性能時卻遇到了諸多瓶頸。所以，人們開始思索用其他方法解決所面臨的種種困難。采用分布式理論，充分利用現有網絡中的各種計算和存儲資源

被公認為是信息處理領域中的一種整體趨勢^[10]，世界上各大IT公司已經將分布式運算理論的研究正式提上議程（如Google的云計算平臺），希望通過一種新的計算和存儲理念來進一步提高人們現有的信息處理能力。

本文所設計的分布式存儲系統利用Erasure Codes技術對文件進行分布式存儲，使得在同樣冗余率的情況下，文件存儲的可靠性得到提高，同時，分布式存儲使得文件的安全性也得到了提高。該原型系統使用比較普遍的所羅門編碼算法進行文件編碼，實驗證明該實現方式實現的文件編碼速度與現有網絡的傳輸速度差距較大，成為分布式存儲速度提升的瓶頸，所以該編碼可以有效解決普通大小文件的分布式存儲，但對大容量文件而言，在編碼速度上還存在一些問題，也是筆者下一步研究的重點。

參考文獻：

［1］KUBIATOWQICZ J，BINDEL D，CHEN Y，et al.OceanStore:an architecture for globalscale persistent storage[C]//Proc of ACM ASPLOS.[S.l.]:ACM Press，2000.

[2]田敬，張大為，代亞非，等.ESStore：P2P網絡的可靠存儲協議[C]//全國網絡與信息安全技術研討會.2005.

[3]LUBY M，MITZENMACHER M，SHOKROLLAHI M A，et al.Practical LossResilient Codes[C]//Proc of the 29th Symposium on Theory of Computing.1997.

[4]PLANK J S.All about Erasure Code:ReedSolomon coding，LDPC coding[EB/OL].http://www.cs.utk.edu/~plank/plank/classes/cs560/560/notes/Erasure/2004ICL.pdf.

[5]KHISTI A.Tornado Codes and Luby Transform Codes[EB/OL].(200310).http://Web.mit.edu/6.454/www/www_fall_2003/khisti/tor_summary.pdf.

[6]SKLAR B.ReedSolomon Codes[EB/OL].http://www.informit.com/content/images/art_sklar7_reedsolomon/elementLinks/art_sklar7_reedsolomon.pdf.

[7]李莉.Notes to erasure control codes[Z].2007：15.

[8]WEATHERSPOON H，KUBIATOWICZ J.Erasure Coding vs.replication:a quantitative comparison[C]//Proc of the 1st International Workshop on PeertoPeer Systems (IPTPS).2002.

[9]REED I S，SOLOMON G.Polynomial Codes over certain finite fields[J].SIAM Journal of Applied Math，1960，8:300304.

[10]鄭緯民，胡進鋒，黎明，等.廣域存儲系統[R].清華大學計算機系高性能計算研究所.