應用于海量存儲中高度容錯的新編碼方案

摘要：闡述了在網絡存儲系統中基于XOR的糾刪編碼的一種新方法，解決了傳統RAID系統不能解決的高容錯性問題，且比ReedSolomon等算法有更好的時間效率。Ningxy編碼方法對于解決高容錯性問題有著最佳的效果，該編碼更適用于動態增減磁盤數量的網絡存儲的數據修復；與此同時提出了新概念步長，步長對解決高度容錯起到了關鍵性作用；通過線性變換、高斯消元，迅速地恢復丟失的磁盤數據。更值得一提的是從整體性能和效率上來說，該編碼比其他的編碼更具有靈活性。

關鍵詞：獨立冗余磁盤陣列/DRAID; 最大距離分離; 臨界值

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

文章編號：1001-3695(2007)12-0041-03

隨著當前信息數據的爆炸式增長，如何確切地保護和妥善管理用戶的重要數據成為一個亟待解決的問題。目前擁有很多種方案來解決數據的安全性問題。例如當數據丟失后，仍可以讓其恢復或再生。在解決這個問題中，需要提及一個概念RAID。它是由美國的D.A.Patterson在1988年提出的。RAID將離散的磁盤變成了RAID子系統。RAID具有較高的性能，這是因為不同磁盤上的數據可以同時讀取，從而提高磁盤的帶寬；所有磁盤可以并行地進行尋道工作，減少了尋道的時間，提高整體性能。在性能提高的同時，還可以保證一定程度的容錯性。通過相應的冗余磁盤容錯機制，可以保證在不丟失保存在失效磁盤上的數據的前提下允許磁盤的失效。Gibson等人對磁盤驅動器失效的規律進行了研究。他們廣泛地收集實驗數據并分析了磁盤失效模型，認為負指數分布很好地表述了磁盤驅動器的失效規律。這種研究可以提供一種思維方式，如因為自然災害（地震、火災）、戰爭等情況下，多個磁盤驅動器同時發生故障、系統癱瘓，也能對機密資料進行快速恢復或修復，給把數據視為生命的機構和單位提供保障。

大多數情況，在目前單點失效模式下，磁盤陣列系統主要依靠RAID 5容錯來為用戶數據提供可靠性。在比特錯誤提高很少的情況下，磁盤容量的持續增長把RAID 5和RAID 6系統可靠性削弱到了無法令人接受的境地。本文提出了在磁盤陣列和其他可靠的存儲系統中基于XOR的糾刪編碼的一個新方法。這個新編碼的一個關鍵優勢是其并不是非MDS（在編碼理論中，MDS代表最大距離分離）。

1相關的概念術語

a)單元（element）是一個基本的數據或者校驗單元。

b)條帶（stripe）是一個完整的數據和校驗單元的集合。這些單元由于校驗關系而有著依賴相關性。實際上它相當于一個碼字，既有原始信息又有冗余信息，并且原始數據和冗余數據間必須有校驗關系。

c)條塊（strip）是所有連續的在同一磁盤和條帶上的存儲單元。它上面存放的是數據或者校驗數據或者兩者都有。值得說明的是，這些strip大小相同（包含同樣數量的elements）。

d)陣列（array）是存在一個或者多個條帶的數個磁盤的組合。磁盤陣列中的劃分如圖1所示。

e)堆棧（stack）是一個陣列中數個條帶的集合，這些條帶中的條塊數目是相同的。

f)水平碼（horizontal code）不同于數據，它單獨地存儲校驗數據。

g)步長(step)是一個數據條塊到另一個數據條塊之間的跨度（本文引入的新概念）。步長示意圖如圖2所示。圖中步長用S表示。

2糾錯碼原理

按照誤碼控制的不同功能可分為檢錯碼、糾錯碼和糾刪碼等。檢錯碼僅具備識別錯碼功能而無糾正錯碼功能；糾錯碼不僅具備識別錯碼功能，同時具備糾正錯碼功能；糾刪碼則不僅具備識別錯碼和糾正錯碼的功能，而且當錯碼超過糾正范圍時可把無法糾錯的信息刪除。

按照誤碼產生的原因不同，可分為糾正隨機錯誤的碼與糾正突發性錯誤的碼。前者主要用于產生獨立的局部誤碼；后者主要用于產生大面積連續誤碼的情況，如磁帶數碼記錄中磁粉脫落而發生的信息丟失。按照信息碼元與附加的監督碼元之間的檢驗關系可分為線性碼與非線性碼。如果兩者呈線性關系，即滿足一組線性方程式，稱為線性碼；否則，兩者關系不能用線性方程式來描述，稱為非線性碼。

6進一步工作

本文闡述了容錯度為t且根據決定空間效率的參數r/v來進行磁盤整列的設計、分析時間復雜度的情況。這種編碼算法對于在RAID或者DRAID結構中的磁盤損壞有很好的恢復效果。就存儲效率和性能來說，也比其他很多編碼有更強的優勢，如比Weaver、ReedSolomon等算法空間復雜性與時間復雜性都好。同時也引進了一個新的概念，即步長。這個概念的引入對解決高容錯性磁盤陣列問題或者更大的網絡存儲數據修復問題起著非常重要的作用。進一步工作是如何用解決高容錯度的思路去得出v、r、t和n的關系，求出最佳的公式表達。主要的工作就是探討存儲效率更高、容錯更大，使得空間效率和時間效率在某一應用中能達到最佳狀態，對這個DRAID或者RAID系統的影響，并提出一些新的觀點，以求解決在高容錯情況下高容錯度問題。

致謝：筆者向對本文的工作給予支持和建議的同行，特別是蘭州理工大學電通院的董建設、徐維濤以及江南大學的劉英戈表示感謝。

參考文獻：

[1]PLANK J S. A tutorial on ReedSolomon coding for faulttolerance in RAIDlike systems [J].Software Practice Experience， 1997， 27(9):995-1012.

[2]HAFNER J L. HoVer erasure codes for disk arrays[C]//Proc of International Conference on Dependable Systems and Networks. Washington DC:IEEE Computer Society， 2006:217-226.

[3]XU Lihao， BRUCK J. Xcode: MDS array codes with optimal encoding [J].IEEE Trans on Information Theory，1999，45(1):272-276.

[4]BLAUM M， BRADY J， BRUCK J，et al. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures [J].IEEE Trans on Computers， 1995，44(2):192-202.

[5]PERUMAL S， KRITZINGER P. Objectoriented design of the groupware layer for the ecosystem information system [D]. Montana:University of Montana， 1995.

[6]ZAITSEV G V， ZINOVEV V A， SEMAKOV N V. Minimum check density codes for correcting bytes of errors [J].Problems in Information Transmission， 1983，19(3):29-37.

[7]周敬禮，余勝生.網絡存儲原理與技術[M].北京：清華大學出版社，2005:33-55.

[8]江藤良純，金子敏信.糾錯碼及其應用[M].北京：科學出版社，2003:45-93.

[9]HAFNER J L. Weaver erasure codes for disk arrays[R].San Jose:IBM Research， 2005.

[10]XIN Qin，MILLEAR E L，SCHWARZ T，et al. Reliability mechanisms for very large storage systems[C]//Proc of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies. Washington DC:IEEE Computer Society，2003:146-156.

[11]HAFNER J L. Matrix methods for lost data reconstruction in erasure codes[C]//Proc of the 4th USENIX Conference on File and Storage Technologies.San Francisco:[s.n.]，2005:183-196.

[12]PLANK J S. T1:erasure codes for storage applications[C]//Proc of the 4th USENIX Conference on File and Storage Technologies.San Francisco:[s.n.]，2005:1-74.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”