[發明專利]高效容多錯的快速恢復編碼方法及其驗證矩陣生成方法

有效

• 申請號: 201310689402.2
• 申請日: 2013-12-16
• 公開（公告）號: CN103809919A
• 公開（公告）日: 2014-05-21
• 發明（設計）人: 曹強;黃建忠;萬勝剛;李詩逸;宋馳;謝長生
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F3/06
• 分類號: G06F3/06;G06F11/20
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 朱仁玲

技術領域

本發明屬于計算機存儲領域，更具體地，涉及一種高效容多錯的快速恢復編碼方法及其驗證矩陣生成方法。

背景技術

可靠性與可用性是衡量在線存儲服務質量的重要標準。對于為商業與工業應用提供在線服務的系統，數據丟失以及時常間斷的服務往往意味著經濟損失。磁盤冗余陣列獨立冗余磁盤陣列（Redundant?Array?of?Independent?Disk，簡稱RAID）是能夠提供高可靠性與高可用性的主流選擇之一。在早期的RAID規范中，例如RAID-0到RAID-5，其僅僅提供單盤容錯能力。近年來，具有更高容錯能力的各種RAID系統逐漸開始被采用，因其在兩個或兩個以上磁盤同時失效時仍然能夠恢復所有丟失的數據，與此同時還能夠提供不間斷的在線服務。

但是現在很多存儲系統中在發生磁盤失效后重構和降級讀的速度都非常的慢。而且由于現在磁盤失效發生的概率越來越頻繁，因此能夠容一個或兩個磁盤失效的RAIDs已經無法提供足夠的安全性了。因此現在急需提出一種具有高容錯性的編碼。

Reed-Solomon編碼是一種基于伽羅華域的編碼，其主要的優勢是能夠容任意多的磁盤失效，但是由于伽羅華域上的運算開銷非常的大，雖然現在Plank等人提出了一種采用Intel公式的SIMD指令來加速伽羅華域上的乘法運算的方法，但是其計算開銷相比異或運算來說還是很大。因此最近許多研究都是在基于異或運算的編碼上進行的。

存儲系統的存儲效率與糾刪碼的設計存在很大的關系。有一類編碼叫做最大距離可分離（Maximum?Distance?Separable，簡稱MDS）編碼，這種編碼的存儲效率是最高的。但是MDS編碼存在很明顯的缺點：容錯能力差，且I/O開銷和降級讀與重構的計算復雜度很高。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種高效容多錯的快速恢復編碼方法及其驗證矩陣生成方法。其目的在于，解決現有技術中存在的容錯能力低、降級讀與重構的性能差的技術問題。

為實現上述目的，按照本發明的一個方面，提供了高效容多錯的快速恢復編碼方法，包括以下步驟：

（1）獲取用戶輸入的系統參數，包括磁盤的大小S*C、一個條帶中數據塊的個數R_d、一個條帶中校驗快的個數2個，其中S表示條帶集的數量，C表示每個條帶集中條帶的數量；

（2）根據用戶輸入的系統參數建立快速恢復編碼的第一行校驗元素C(s^p₀，r^p₀，c^p₀)，C(s^p₁，r^p₀，c^p₁)，…，C(s^p_S-1，r^p₀，c^p_C-1)，其中s表示條帶集在編碼單元中的序號，r₀表示校驗元素在條帶集中的第一行，且r₀=0，c表示校驗元素在條帶集中的列序號，本步驟具體包括以下子步驟：

（2-1）初始化s^p₀=0，c^p₀=0；

（2-2）判斷是否有c^p₀<C，若是則轉入步驟（2-3），否則轉入步驟（2-6）；

（2-3）將第<s^p₀+1>_S個條帶集中的第c^p₀+2行的元素進行異或運算，以得到校驗元素，并將該校驗元素存放在C(s^p₀，r，c^p₀)中；