容錯存儲系統(tǒng)中的MDS陣列碼研究.pdf

1、隨著現(xiàn)代存儲系統(tǒng)在規(guī)模和復雜性上的不斷增長，硬盤（節(jié)點）故障已經(jīng)成為系統(tǒng)運行中的一個日常事件。為了防止各類硬件故障造成數(shù)據(jù)丟失，存儲系統(tǒng)一般使用兩種方式對數(shù)據(jù)進行保護，即多路鏡像和糾刪編碼。多路鏡像雖然實現(xiàn)簡單，但這種方式的存儲效率通常較低；而糾刪碼技術由于可以靈活地調節(jié)存儲效率而被越來越多的存儲系統(tǒng)采用。最大距離可分的（MDS）陣列碼是一類主要面向存儲系統(tǒng)的糾刪碼，這類碼可以使用最少的冗余來提供特定的容錯能力，并且其編解碼過程只需要用

2、到簡單的異或和循環(huán)移位運算，因此在近幾年受到了越來越多的關注。本文主要針對糾雙刪和糾三刪的MDS陣列碼進行了深入的研究，并取得了以下幾點成果：
　　1、RAID-6正在逐步取代RAID-5成為RAID的主流形式，因為它可以在兩個磁盤同時故障的情況下也能夠恢復數(shù)據(jù)。有許多糾雙刪的MDS陣列碼是專為實現(xiàn)RAID-6設計的，但是這些碼都有它們各自的局限性。本文研究了其中一種有代表性的碼（Blaum-Roth碼），分析其優(yōu)勢及局限性，并對

3、其編解碼算法進行改進。改進后的Blaum-Roth碼具有以下優(yōu)秀特性：
　　1）編碼復雜度達到理論下界；
　　2）解碼復雜度接近理論下界；
　　3）可以在幾乎沒有性能損失的前提下實現(xiàn)RAID-6的可擴展性。與其它最常用于RAID-6的MDS陣列碼相比，改進后的Blaum-Roth碼更適于構建高性能并且可伸縮的RAID-6磁盤陣列。
　　2、糾雙刪的最低密度MDS陣列碼是一類結構優(yōu)美的糾刪碼，具有最優(yōu)的編碼、解碼和

4、更新復雜度。然而，現(xiàn)有的這類碼或者對碼長的限制過于嚴格，或者編碼規(guī)則沒有明顯的幾何規(guī)律，這使得它們的實用性較差。為此，本文構造了一種新的糾雙刪最低密度MDS陣列碼，稱為對稱碼。對稱碼的編碼、解碼和更新復雜度均達到最優(yōu)，而且碼長可以是素數(shù)或者素數(shù)減1。此外，對稱碼在恢復單個刪除列時所需的I/O開銷比大多數(shù)最低密度MDS陣列碼要少，并且在碼長較短時這個開銷可以接近理論下界。
　　3、最低密度MDS陣列碼由于其編碼和更新復雜度的最優(yōu)性而

5、廣受歡迎。然而，目前已知的絕大多數(shù)最低密度MDS陣列碼都只能糾兩個刪除列，雖然有少部分例外，但是它們對碼長的限制非常嚴格。例如，現(xiàn)有的糾三刪的最低密度MDS陣列碼通常要求碼長為p（或p?1），其中p必須是滿足以下條件的素數(shù)：2為GF(p)的一個本原元且p?1能夠被3整除。如此嚴格的碼長限制使得這些碼幾乎無法被實際存儲系統(tǒng)采用。為此，本文構造了一種實用的糾三刪的最低密度MDS陣列碼，能夠糾正碼字中的任意三個刪除列或者一個刪除列連同一個差錯

6、列。這類碼的解碼復雜度可以達到或接近理論下界（取決于刪除模式），并且碼長可以是p或p+1，其中p是一個奇素數(shù)。這是目前已知最具實用價值的糾三刪的最低密度MDS陣列碼。
　　4、廣義RDP碼被認為是目前最實用和最高效的強系統(tǒng)的MDS碼，因為其編碼復雜度達到了理論下界，并且可以支持任意碼長。然而，廣義RDP碼的現(xiàn)有解碼算法的解碼復雜度離理論下界有點遠，還有一定的改進空間。本文對糾三刪的廣義RDP碼的解碼算法進行了研究，并提出了一種針對