【文章內(nèi)容簡介】 SSD 的出現(xiàn)，以及應(yīng)用對更高容錯能力（更大的編碼計算量）的冗余編碼的需求，編碼計算時間占寫操作總時間的比重逐漸加大，因此編碼的效率是影響 RAID 系統(tǒng)的性能的重要因素之一。 主要工作和本文的組織結(jié)構(gòu)本文從存儲編碼的角度對 RAID6 進(jìn)行性能優(yōu)化的研究。對幾種常見雙容錯編碼進(jìn)行了比較，同時，對于近幾年由 Sun 公司開發(fā)、備受關(guān)注的文件系統(tǒng)ZFS 的編碼實現(xiàn)進(jìn)行了剖析，在其上設(shè)計并實現(xiàn)了 cache 優(yōu)化的 EVENODD 和RDP 碼的編碼方法。為了進(jìn)一步的提高編碼的效率，采取使用 SSE 指令代替常規(guī)指令的方法，以 RDP 碼為例對編碼實現(xiàn)進(jìn)行優(yōu)化。最終，通過實驗驗證了高效的編碼實現(xiàn)可以提升 RAID6 系統(tǒng)的性能這一觀點。全文一共分為五章：第一章是數(shù)據(jù)存儲的發(fā)展情況和 RAID 的簡介，以及全文的主要工作與組織結(jié)構(gòu)的概要。第二章介紹了常見的 RAID6 編碼方式，對它們進(jìn)行比較，并且給出了采用cache 優(yōu)化的實現(xiàn)方法。第三章對新型的文件系統(tǒng) ZFS 進(jìn)行了介紹，簡要的分析了 ZFS 上的編碼實現(xiàn)，給出了 EVENODD 和 RDP 碼在 ZFS 上編碼、解碼算法的具體實現(xiàn)，并且給出了使用 SSE 指令對編碼實現(xiàn)進(jìn)行優(yōu)化的具體方法。第四章是論文工作的實驗部分。一方面對編碼、解碼實現(xiàn)的正確性進(jìn)行了驗證，另一方面對不同編碼實現(xiàn)下 ZFS 的寫性能進(jìn)行了測試，驗證了高效的編碼實現(xiàn)可以提升 RAID6 系統(tǒng)的性能這一觀點。第五章對全文進(jìn)行總結(jié)，以及對今后工作展望。52. 常見的 RAID6 編碼方式ReedSolomon、EVENODD 和 RDP 是三種重要的 RAID6 編碼方案。對于RAID 系統(tǒng)，計算校驗的過程是編碼的過程，故障恢復(fù)（重構(gòu)）的過程是解碼的過程。因此本章對于每種碼字都從編碼、解碼兩個方面去說明。比較這三種編碼方式，其第一校驗盤是水平校驗盤，即每個校驗塊由數(shù)據(jù)盤中相同偏移的數(shù)據(jù)塊經(jīng)異或運算而得，不同之處在于第二校驗盤的編碼方式。 ReedSolomon 碼 編碼ReedSolomon 碼（簡稱 RS 碼）[8]最初出現(xiàn)于通訊領(lǐng)域，用于碼字糾錯。由 n 塊存放數(shù)據(jù)字的磁盤和 2 塊存放校驗字的磁盤構(gòu)成的 RAID6 陣列，第二校驗盤如果使用 RS 碼，則兩個校驗盤按照公式（ ）和公式（）進(jìn)行構(gòu)造[9]。 （）??? （）??????公式（）和（）中，大寫字母表示的變量均指一個向量，該向量每個元素是磁盤上一個字節(jié)的數(shù)據(jù)，維度表示參與校驗的字節(jié)數(shù)目。 對應(yīng)01~nD?n 塊存放數(shù)據(jù)字的磁盤，P、Q 對應(yīng)兩塊存放校驗字的磁盤。整個運算都是在GF(28)下進(jìn)行， 指這個伽羅瓦域的生成元，通常取 。g {2}g?在 GF(28)下的加法、減法運算，等同于普通的按位異或運算，而乘法和除法運算相對復(fù)雜，需要進(jìn)行對數(shù)和反對數(shù)的變換。比如需要在 GF(28)下計算，那么計算方法如公式（） 。AB? （）(logl)gAB???公式（）中，符號 表示運算符的兩個操作數(shù)先進(jìn)行常規(guī)的加法，然后對 255 取模。 的計算與之類似。不難看出，采用這種方式進(jìn)行校驗字的編/碼，需要頻繁的進(jìn)行對數(shù)和反對數(shù)的運算，比較復(fù)雜。通常的實現(xiàn)都是事先構(gòu)造出 GF(28)下的對數(shù)表和反對數(shù)表，那么公式（）中對數(shù)和反對數(shù)的運算就6可以通過查表算得。 解碼如果僅是 P、 Q 丟失，那么重構(gòu)只需要重新按照公式（）和（）再次進(jìn)行編碼的計算。如果是 中有一個或者兩個發(fā)生了數(shù)據(jù)丟失，整個陣01~nD?列需要重構(gòu)。實際上重構(gòu)的方法就是解由式（）和（）組成的方程組。具體如下：如果 中僅有一塊磁盤數(shù)據(jù)丟失，P 沒有數(shù)據(jù)丟失，那么只需要按01~n?照類似 RAID5 的方法利用奇偶校驗重構(gòu)。如果 Q 的數(shù)據(jù)也發(fā)生了丟失，還需要按照公式（）重構(gòu) Q 盤。如果 中的一塊磁盤和 P 盤同時發(fā)生數(shù)據(jù)丟失，記數(shù)據(jù)丟失的磁盤01~nD?是 。令 ，由式（）計算的結(jié)果記為 ，則有xx?x （）xgDQ???公式（）經(jīng)過整理，可以得到計算 的公式（） 。x （）25()/()xxxg???如果 中的兩塊磁盤數(shù)據(jù)丟失，記數(shù)據(jù)丟失的磁盤是 和 。令01~nD? xDy并且 ，由式（）計算的結(jié)果記為 ，由式（）計算的結(jié)果x?y xyP記為 ，則有yQ （）xyyPD?? （）xyQgQ??公式（）經(jīng)過變形，得到 （）()xyxxg??????將式（）代入式（） ，并且經(jīng)過整理，可以求出 。令xD， ，那么1({0}){01}yxyxgAg??????? 1({0}){01}yxyBgg???????7， 可以由式（） （）計算得出。xD （）()()xxyxyDAPBQ???? （）y EVENODD 碼1995 年，Mario Blaum 等人提出 EVENODD[10]陣列編碼方式。由于 RS 碼的編碼、解碼計算都要在伽羅瓦域上進(jìn)行，計算比較復(fù)雜。而 EVENODD 碼所有的校驗計算都是基于簡單的異或操作，計算復(fù)雜度低，比 RS 碼具有更好的性能。 編碼標(biāo)準(zhǔn)的 EVENODD 碼由 p+2 個磁盤組成（p 稱為控制參數(shù)，并且必須是素數(shù)） ，其中 p 個磁盤是數(shù)據(jù)盤，另兩個為校驗盤。每個磁盤劃分為 p1 個塊（packet） ，因此一個 EVENODD 編碼系統(tǒng)可以用一個(p1) (p+2)矩陣表示，這也是這類編碼“奇偶校驗陣列碼” （parity array code）名稱的由來。第一校驗盤同樣為水平校驗盤，第二校驗盤為對角線校驗盤。圖 21 給出了 p=5 的時候，由 7 個磁盤組成的磁盤陣列的 EVENODD 編碼的示意圖，每個塊用一個數(shù)字表示所屬的對角線校驗組。Data Disk 0 Data Disk 1 Data Disk 2 Data Disk 3 Data Disk 4 Row Parity Diag. Parity0 1 2 3 4 x 01 2 3 4 0 x 12 3 4 0 1 x 23 4 0 1 2 x 3圖 21： EVENODD 編 碼 示 意 圖 （ p=5）不難看出，標(biāo)記為“4”這些數(shù)據(jù)塊，在對角線校驗盤中并沒有對應(yīng)的校驗組。EVENODD 規(guī)定，這些數(shù)據(jù)塊需要進(jìn)行異或運算，得到一個新的數(shù)據(jù)塊，記為 S。首先要將各個數(shù)據(jù)盤中相同的校驗組數(shù)據(jù)塊進(jìn)行異或計算，然后將 S異或進(jìn)去，才能得到位于對角線校驗盤中該校驗組的最終校驗數(shù)據(jù)。EVENODD 碼的編碼計算方法可以總結(jié)為公式（ ）和（） ，packet[i,j] 表8示第 j 個磁盤的第 i 個數(shù)據(jù)塊。 （）20[,1][,](0,)pjpacketiacketijp?????（）10[,][,]()mod,01,.2)pjitiStjkijpi????????????? 其中， 。1[,]piacketi???從另一個角度講，如果將奇偶校驗分成奇校驗和偶校驗的話，正是 S 的每一位，確定了對角線校驗盤中的某一數(shù)據(jù)塊對應(yīng)的位應(yīng)該是奇校驗還是偶校驗。這便是 EVENODD 碼名稱的由來。需要注意的是，圖 21 所示只是一個編碼周期。在實際系統(tǒng)中，磁盤布局為此周期的重復(fù)。另一點值得注意的是，如果我們將 packet 實現(xiàn)為條紋單元，將導(dǎo)致較差的更新代價。即一個條紋單元的更新一般會導(dǎo)致 2 個校驗單元更新。但如果將編碼周期的一列實現(xiàn)為一個條紋單元，則可達(dá)到最優(yōu)的更新代價。從計算角度，并不會提高編碼的計算復(fù)雜度。 解碼如果僅有一個數(shù)據(jù)盤的數(shù)據(jù)丟失，那么利用行校驗盤可以很簡單地計算出丟失數(shù)據(jù)。如果僅有校驗盤數(shù)據(jù)丟失，那么重新編碼計算即可。如果是一個數(shù)據(jù)盤和對角線校驗盤數(shù)據(jù)丟失，需要先用行校驗盤恢復(fù)那個數(shù)據(jù)盤上的數(shù)據(jù)，而后重新計算對角線校驗數(shù)據(jù)。上述情況比較簡單，下面著重討論兩種比較復(fù)雜的情況，一種是一塊數(shù)據(jù)盤和行校驗盤同時發(fā)生數(shù)據(jù)丟失，另一種是兩塊數(shù)據(jù)盤發(fā)生了數(shù)據(jù)丟失。對于第一種情況，首先要重新計算 S。記丟失數(shù)據(jù)盤是第 x 塊。令，S 的計算方法由式 。[1,]0(,1.)packetjjp??? （）10[,][,](1)modpjSacketxacketjj??????????，然后，就可以利用求出的 S 恢復(fù)丟失的數(shù)據(jù)盤，由式 。9 （）10[,][,][,]()mod,()mod,.1)pjxpacketixSpacketlacketjlixjip?????????????? ?對于第二種情況，依然要重新計算 S。由式 。 （）2200[,][,]ppi iSacketiacketi?????????????????記丟失的數(shù)據(jù)盤是第 x 塊和第 y 塊。x 磁盤利用對角線校驗組進(jìn)行恢復(fù)，y磁盤利用行校驗組進(jìn)行恢復(fù)，整個過程是一個迭代的過程。如圖 22 所示，p=5，x =2，y =3。首先計算 S，而后利用 S 和對角線校驗數(shù)據(jù)恢復(fù) packet[3,3]，再利用行校驗數(shù)據(jù)恢復(fù) packet[3,2]，接著恢復(fù) packet[2,3]，如此進(jìn)行下去，直到數(shù)據(jù)盤 2 和數(shù)據(jù)盤 3 在這個條紋中的數(shù)據(jù)都被恢復(fù)。Data Disk 0 Data Disk 1 Data Disk 2 Data Disk 3 Data Disk 4 Row Parity Diag. Parity0 1 2 3 4 x 01 2 3 4 0 x 12 3 4 0 1 x 23 4 0 1 2 x 3圖 22： x=2 y=3 時 候 EVENODD 解 碼 過 程 （ p=5） RDP 碼2022 年，Peter Corbett 等人提出一種新型雙容錯陣列碼——RDP 碼[11] 。與 EVENODD 碼類似的是， RDP 碼也使用兩個校驗盤存放冗余信息，一塊是行校驗盤，另一塊是對角線校驗盤。但是，EVENODD 碼計算對角線校驗數(shù)據(jù)的時候，沒有把行校驗盤的數(shù)據(jù)計算進(jìn)去，因此屬于“校驗無關(guān)”的陣列碼；而 RDP 碼在計算對角線校驗數(shù)據(jù)的時候，需要將行校驗盤和其他數(shù)據(jù)盤一起計算進(jìn)去，屬于“校驗相關(guān)”的陣列碼。由于 RDP 碼沒有類似 EVENODD 碼中S 的計算，因此計算復(fù)雜度要稍微低于 EVENODD 碼。更進(jìn)一步的，文獻(xiàn)[11]在理論上進(jìn)行了證明，RDP 碼達(dá)到了雙容錯編碼的最優(yōu)編碼計算復(fù)雜性和接近最優(yōu)的解碼計算復(fù)雜性。 編碼標(biāo)準(zhǔn)的 RDP 碼由 p+1 個磁盤組成（p 稱為控制參數(shù)，并且必須是素數(shù)） ，10其中 p 個磁盤是數(shù)據(jù)盤，另兩個為校驗盤。每個磁盤劃分為 p1 個塊（packet） ，因此一個 RDP 編碼系統(tǒng)可以用一個(p1)(p+1) 矩陣表示。圖 23 給出了 p=5的時候，由 6 個磁盤組成的 RDP 陣列的示意圖，每個塊用一個數(shù)字表示所屬的對角線校驗組。同樣，標(biāo)記為“4”的這些塊沒有參與任何對角線校驗組。和EVENODD 碼類似，圖 23 依然表示的是一個編碼周期，而并不是把 packet 實現(xiàn)為條紋單元。Data Disk 0 Data Disk 1 Data Disk 2 Data Disk 3 Row Parity Diag. Parity0 1 2 3 4 01 2 3 4 0 12 3 4 0 1 23 4 0 1 2 3圖 23： RDP 編 碼 示 意 圖 （ p=5）兩個校驗盤的編碼計算可以總結(jié)為公式（）和（） 。 （）20[,1][,](0,)pjpacketiacketij????? （）01[,][,]()mod,01,.2)pjititjijpip??????? 解碼對于僅有一個數(shù)據(jù)盤的數(shù)據(jù)丟失、僅有校驗盤的數(shù)據(jù)丟失以及一個數(shù)據(jù)盤和對角線校驗盤的數(shù)據(jù)丟失的情況，重構(gòu)的方法與 EVENODD 類似，這里不再贅述。這里主要考慮一個數(shù)據(jù)盤和行校驗盤的數(shù)據(jù)丟失、兩個數(shù)據(jù)盤的數(shù)據(jù)同時丟失的情況發(fā)生時，丟失的數(shù)據(jù)如何重構(gòu)。對于這兩種情況，重構(gòu)的方法是相同的。記丟失的數(shù)據(jù)盤是第 x 塊和第 y塊。首先使用對角線校驗數(shù)據(jù)恢復(fù) x，利用行校驗數(shù)據(jù)恢復(fù) y，反復(fù)進(jìn)行下去，直到磁盤 x 不能通過對角線數(shù)據(jù)恢復(fù)為止（磁盤 x 中不參加對角線校驗的數(shù)據(jù)塊） 。然后使用對角線校驗數(shù)據(jù)恢復(fù) y，使用行校驗數(shù)據(jù)恢復(fù) x，反復(fù)進(jìn)行下去，直到磁盤 y 不能通過對角線數(shù)據(jù)恢復(fù)為止。此時，重構(gòu)完畢。圖 24 描述了 情況下解碼的過程。首先利用對角線校驗數(shù)5,23px?據(jù)恢復(fù) packet[0,2]，利用行校驗數(shù)據(jù)恢復(fù) packet[0,3]。重復(fù)這個過程，直到11packet[2,2]不能依靠對角線校驗數(shù)據(jù)恢復(fù)。此時，利用對角線校驗數(shù)據(jù)恢復(fù)packet[3,3]，再利用行校驗數(shù)據(jù)恢復(fù) packet[3,2]。重復(fù)這個過程，直到packet[1,3]不能依靠對角線校驗數(shù)據(jù)恢復(fù)。磁盤 2 和磁盤 3 在該條紋中的所有數(shù)據(jù)均被恢復(fù)。Data Disk 0 Data Disk 1 Data Disk 2 Data Disk 3 Row Parity Diag. Parity0 1 2 3 4