【文章內(nèi)容簡(jiǎn)介】 舊校驗(yàn)字、 計(jì)算新校驗(yàn)、 寫(xiě)新數(shù)據(jù)字、寫(xiě)新校驗(yàn)字， 因而 校驗(yàn)盤(pán)成為了系統(tǒng)瓶頸。 RAID5：按塊交叉、奇偶校驗(yàn)字散布 RAID4 的基礎(chǔ)上， RAID5 按照一定的規(guī)律將校驗(yàn)字散布到不同的磁盤(pán)中。對(duì)于多個(gè)“小讀”“小寫(xiě)”操作，如果訪問(wèn)的校驗(yàn)盤(pán)和數(shù)據(jù)盤(pán)互不相同，幾個(gè)操作就可以并行執(zhí)行。這樣一來(lái)，就避免了校 驗(yàn)盤(pán)成為系統(tǒng)瓶頸的問(wèn)題。 RAID6： P+Q 陣列 以上的 6 個(gè)級(jí)別的 RAID，最多只能容許其中任意的一塊磁盤(pán)損壞。一旦有任意的兩塊磁盤(pán)的數(shù)據(jù)同時(shí)出現(xiàn)錯(cuò)誤，整個(gè)陣列就會(huì)變得不可靠。由于 實(shí)際應(yīng)用對(duì)存儲(chǔ)需求的提高 ，陣列中的磁盤(pán)成員數(shù)目增多，系統(tǒng)故障的期望就會(huì)變大 [7]。于是，單容錯(cuò)陣列難以滿足人們的需求。 RAID6 是在單容錯(cuò)陣列的基礎(chǔ)上增加了一份校驗(yàn)數(shù)據(jù)，這兩份校驗(yàn)數(shù)據(jù)一份稱為 P，另一份稱為 Q， P 和 Q存放在不同的磁盤(pán)上，構(gòu)成雙容錯(cuò)陣列，大大提高了磁盤(pán)陣列的數(shù)據(jù)可靠性。由于 RAID6 的每次寫(xiě)操作需要進(jìn)行兩 套校驗(yàn)數(shù)據(jù)的計(jì)算，以及這兩套校驗(yàn)數(shù)據(jù)的寫(xiě)入，因此高可靠性是以犧牲了一部分性能而獲得的。適用于磁盤(pán)成員數(shù)目多或者對(duì)可靠性要求高的磁盤(pán)陣列。 當(dāng)前， RAID0、鏡像機(jī)制和基于 RAID5 的單容錯(cuò)陣列技術(shù)都已經(jīng)比較成熟，而且獲得了廣泛的使用，而 RAID6 還有待研究，如何提高雙容錯(cuò)陣列的性能成為 RAID 研究的熱點(diǎn)。對(duì)于 RAID 系統(tǒng)來(lái)說(shuō)，每次硬盤(pán) I/O 都可以歸結(jié)為對(duì)磁 4 盤(pán)陣列條紋的讀寫(xiě)。其中，每次寫(xiě)操作，都要涉及編碼計(jì)算。而隨著高性能存儲(chǔ)介質(zhì)如 SSD 的出現(xiàn)，以及應(yīng)用對(duì)更高容錯(cuò)能力（更大的編碼計(jì)算量）的冗余編碼的需求，編碼 計(jì)算時(shí)間占寫(xiě)操作總時(shí)間的比重逐漸加大，因此編碼的效率是影響 RAID 系統(tǒng)的性能的重要因素之一。 主要工作和本文的組織結(jié)構(gòu) 本文從存儲(chǔ)編碼的角度對(duì) RAID6 進(jìn)行性能優(yōu)化的研究。對(duì)幾種常見(jiàn)雙容錯(cuò)編碼進(jìn)行了比較，同時(shí)，對(duì)于近幾年由 Sun 公司開(kāi)發(fā)、備受關(guān)注的文件系統(tǒng) ZFS的編碼實(shí)現(xiàn)進(jìn)行了剖析，在其上設(shè)計(jì)并實(shí)現(xiàn)了 cache 優(yōu)化的 EVENODD 和 RDP碼的編碼方法。為了進(jìn)一步的提高編碼的效率，采取使用 SSE 指令代替常規(guī)指令的方法，以 RDP 碼為例對(duì)編碼實(shí)現(xiàn)進(jìn)行優(yōu)化。最終，通過(guò)實(shí)驗(yàn)驗(yàn)證了高效的編碼實(shí)現(xiàn)可以提升 RAID6 系統(tǒng)的性能這一觀點(diǎn)。全文一共分為五章： 第一章是數(shù)據(jù)存儲(chǔ)的發(fā)展情況和 RAID 的簡(jiǎn)介，以及全文的主要工作與組織結(jié)構(gòu)的概要。 第二章介紹了常見(jiàn)的 RAID6 編碼方式，對(duì)它們進(jìn)行比較，并且給出了采用cache 優(yōu)化的實(shí)現(xiàn)方法。 第三章對(duì)新型的文件系統(tǒng) ZFS 進(jìn)行了介紹，簡(jiǎn)要的分析了 ZFS 上的編碼實(shí)現(xiàn)，給出了 EVENODD 和 RDP 碼在 ZFS 上編碼、解碼算法的具體實(shí)現(xiàn)，并且給出了使用 SSE 指令對(duì)編碼實(shí)現(xiàn)進(jìn)行優(yōu)化的具體方法。 第四章是論文工作的實(shí)驗(yàn)部分。一方面對(duì)編碼、解碼實(shí)現(xiàn)的正確性進(jìn)行了驗(yàn)證，另一方面對(duì)不同編碼實(shí)現(xiàn)下 ZFS 的寫(xiě)性能進(jìn)行了測(cè)試，驗(yàn)證了高效的編碼實(shí)現(xiàn)可以提升 RAID6 系統(tǒng)的性能這一觀點(diǎn)。 第五章對(duì)全文進(jìn)行總結(jié)，以及對(duì)今后工作展望。 5 2. 常見(jiàn)的 RAID6編碼方式 ReedSolomon、 EVENODD 和 RDP 是三種重要的 RAID6 編碼方案 。對(duì)于RAID 系統(tǒng)，計(jì)算校驗(yàn)的過(guò)程是編碼的過(guò)程，故障恢復(fù)（重構(gòu)）的過(guò)程是解碼的過(guò)程。因此本章對(duì)于每種碼字都從編碼、解碼兩個(gè)方面去說(shuō)明。比較這三種編碼方式，其第一校驗(yàn)盤(pán)是水平校驗(yàn)盤(pán)，即每個(gè)校驗(yàn)塊由數(shù)據(jù)盤(pán)中相同偏移的數(shù)據(jù)塊經(jīng)異或運(yùn)算而得，不同之處在于第二校驗(yàn)盤(pán)的編碼方式。 ReedSolomon 碼 編碼 ReedSolomon 碼（簡(jiǎn)稱 RS 碼） [8]最初出現(xiàn)于通訊領(lǐng)域，用于碼字糾錯(cuò)。由 n 塊存放數(shù)據(jù)字的磁盤(pán)和 2 塊存放校驗(yàn)字的磁盤(pán)構(gòu)成的 RAID6 陣列，第二校驗(yàn)盤(pán)如果使用 RS 碼，則兩個(gè)校驗(yàn)盤(pán)按照公式（ ）和公式（ ）進(jìn)行構(gòu)造 [9]。 0 1 2 1... nP D D D D ?? ? ? ? ? （ ） 0 1 2 10 1 2 1... n nQ g D g D g D g D? ?? ? ? ? ? ? ? ? ? （ ） 公式（ ）和（ ）中 ，大寫(xiě)字母表示的變量均指一個(gè)向量，該向量每個(gè)元素是磁盤(pán)上一個(gè)字節(jié)的數(shù)據(jù)，維度表示參與校驗(yàn)的字節(jié)數(shù)目。 01~ nDD? 對(duì)應(yīng)n 塊存放數(shù)據(jù)字的磁盤(pán)， P、 Q 對(duì)應(yīng)兩塊存放校驗(yàn)字的磁盤(pán)。整個(gè)運(yùn)算都是在GF(28)下進(jìn)行， g 指這個(gè)伽羅瓦域的生成元，通常取 {02}g? 。 在 GF(28)下的加法、減法運(yùn)算，等同于普通的按位異或運(yùn)算，而乘法和除法運(yùn)算相對(duì)復(fù)雜，需要進(jìn)行對(duì)數(shù)和反對(duì)數(shù)的變換。比如需要在 GF(28)下計(jì)算AB? ，那么計(jì)算方法如公式（ ）。 ( l og l og )ggABA B g ??? （ ） 公式（ ）中，符號(hào) ? 表示運(yùn)算符的兩個(gè)操作數(shù)先進(jìn)行常規(guī)的加法，然后對(duì) 255 取模。 /AB的計(jì)算與之類(lèi)似。不難看出，采用這種方式進(jìn)行校驗(yàn)字的編碼，需要頻繁的進(jìn)行對(duì)數(shù)和反對(duì)數(shù)的運(yùn)算，比較復(fù) 雜。通常的實(shí)現(xiàn)都是事先構(gòu)造出 GF(28)下的對(duì)數(shù)表和反對(duì)數(shù)表，那么公式（ ）中對(duì)數(shù)和反對(duì)數(shù)的運(yùn)算就可以通過(guò)查表算得。 6 解碼 如果僅是 P、 Q 丟失，那么重構(gòu)只需要重新按照公式（ ）和（ ）再次進(jìn)行編碼的計(jì)算。如果是 01~ nDD? 中有一個(gè)或者兩個(gè)發(fā)生了數(shù)據(jù)丟失，整個(gè)陣列需要重構(gòu)。實(shí)際上重構(gòu)的方法就是解由式（ ）和（ ）組成的方程組。具體如下： 如果 01~ nDD? 中僅有一塊磁盤(pán)數(shù)據(jù)丟失， P 沒(méi)有數(shù)據(jù)丟失，那 么只需要按照類(lèi)似 RAID5 的方法利用奇偶校驗(yàn)重構(gòu)。如果 Q 的數(shù)據(jù)也發(fā)生了丟失，還需要按照公式（ ）重構(gòu) Q 盤(pán)。 如果 01~ nDD? 中的一塊磁盤(pán)和 P 盤(pán)同時(shí)發(fā)生數(shù)據(jù)丟失，記數(shù)據(jù)丟失的磁盤(pán)是 xD 。令 0xD? ，由式（ ）計(jì)算的結(jié)果記為 xQ ，則有 xxxQ g D Q? ? ? （ ） 公式（ ）經(jīng)過(guò)整理，可以得到計(jì)算 xD 的公式（ ）。 255( ) / ( )xxx x xD Q Q g Q Q g ?? ? ? ? ? （ ） 如果 01~ nDD? 中的兩塊磁盤(pán)數(shù)據(jù)丟失，記數(shù)據(jù)丟失的磁盤(pán)是 xD 和 yD 。令0xD? 并且 0yD? ，由式（ ）計(jì)算的結(jié)果記為 xyP ，由式（ ）計(jì)算的結(jié)果記為 xyQ ，則有 xy x yP D D P? ? ? （ ） xyx y x yQ g D g D Q? ? ? ? ? （ ） 公式（ ）經(jīng)過(guò)變形，得到 ()x y xx x y yD g Q Q g D??? ? ? ? ? （ ） 將式（ ）代 入式 （ ）， 并 且經(jīng) 過(guò)整 理， 可以 求出 xD 。令1( { 0 1 } ){ 0 1 }yx y x y xyxgA g gg ? ? ? ??? ? ? ?? ， 1( { 0 1 } ){ 0 1 }yx x y xyxgB g gg ? ? ? ??? ? ? ?? ，那么xD ， xD 可以由式（ ）（ ）計(jì)算得出。 7 ( ) ( )x x y x yD A P P B Q Q? ? ? ? ? ? （ ） ()y xy xD P P D? ? ? （ ） EVENODD碼 1995 年， Mario Blaum 等人提出 EVENODD[10]陣列編碼方式。由于 RS 碼的編碼、解碼計(jì)算都要在伽羅瓦域上進(jìn)行，計(jì)算比較復(fù)雜。而 EVENODD 碼所有的校驗(yàn)計(jì)算都是基于簡(jiǎn)單的異或操作，計(jì)算復(fù)雜度低，比 RS 碼具有更好的性能。 編碼 標(biāo)準(zhǔn)的 EVENODD 碼由 p+2 個(gè)磁盤(pán)組成（ p 稱為控制參數(shù)，并且必須是素?cái)?shù)），其中 p 個(gè)磁盤(pán)是數(shù)據(jù)盤(pán)，另 兩個(gè)為校驗(yàn)盤(pán)。每個(gè)磁盤(pán)劃分為 p1 個(gè)塊（ packet），因此一個(gè) EVENODD 編碼系統(tǒng)可以用一個(gè) (p1) (p+2)矩陣表示，這也是這類(lèi)編碼“奇偶校驗(yàn)陣列碼”（ parity array code）名稱的由來(lái)。第一校驗(yàn)盤(pán)同樣為水平校驗(yàn)盤(pán)，第二校驗(yàn)盤(pán)為對(duì)角線校驗(yàn)盤(pán)。圖 21 給出了 p=5 的時(shí)候，由 7 個(gè)磁盤(pán)組成的磁盤(pán)陣列的 EVENODD 編碼的示意圖，每個(gè)塊用一個(gè)數(shù)字表示所屬的對(duì)角線校驗(yàn)組。 Data Disk 0 Data Disk 1 Data Disk 2 Data Disk 3 Data Disk 4 Row Parity Diag. Parity 0 1 2 3 4 x 0 1 2 3 4 0 x 1 2 3 4 0 1 x 2 3 4 0 1 2 x 3 圖 21： EVENODD編碼示意圖（ p=5） 不難看出，標(biāo)記為“ 4”這些數(shù)據(jù)塊，在對(duì)角線校驗(yàn)盤(pán)中并沒(méi)有對(duì)應(yīng)的校驗(yàn)組。 EVENODD 規(guī)定，這些數(shù)據(jù)塊需要進(jìn)行異或運(yùn)算，得到一個(gè)新的數(shù)據(jù)塊，記為 S。首先要將各個(gè)數(shù)據(jù)盤(pán)中相同的校驗(yàn)組數(shù)據(jù)塊進(jìn)行異或計(jì)算，然后將 S異或進(jìn)去，才能得到位于對(duì)角線校驗(yàn)盤(pán)中該校驗(yàn)組的最終校驗(yàn)數(shù)據(jù)。 EVENODD碼的編碼計(jì)算方法可 以總結(jié)為公式（ ）和（ ）， packet[i,j]表示第 j 個(gè)磁盤(pán)的第 i 個(gè)數(shù)據(jù)塊。 8 20[ , 1 ] [ , ] , ( 0 , 1 , . . . 2 )pjp a c k e t i p p a c k e t i j i p??? ? ? ?? （ ） 10 1[ , ] [ , ] , ( ( ) m od , 0 , 1 , .. . 2)pjjipac k e t i p S pac k e t k j k i j p p i p????????? ? ? ? ? ? ????（ ） 其中， 11 [ , 1]piS p a c k e t i p i??? ? ? ?。 從另一個(gè)角度講，如果將奇偶校驗(yàn)分成奇校驗(yàn)和偶校驗(yàn)的話，正是 S 的每一位，確定了對(duì)角線校驗(yàn)盤(pán)中的某一數(shù)據(jù)塊對(duì)應(yīng)的位應(yīng)該是奇校驗(yàn)還是偶校驗(yàn)。這便是 EVENODD 碼名稱的由來(lái) 。 需要注意的是，圖 21 所示只是一個(gè)編碼周期。在實(shí)際系統(tǒng)中，磁盤(pán)布局為此周期的重復(fù)。另一點(diǎn)值得注意的是，如果我們將 packet 實(shí)現(xiàn)為條紋單元，將導(dǎo)致較差的更新代價(jià)。即一個(gè)條紋單元的更新一般會(huì)導(dǎo)致 2 個(gè)校驗(yàn)單元更新。但如果將編碼周期的一列實(shí)現(xiàn)為一個(gè)條紋單元，則可達(dá)到最優(yōu)的更新代價(jià)。從計(jì)算角度，并不會(huì)提高編碼的計(jì)算復(fù)雜度。 解碼 如果僅有一個(gè)數(shù)據(jù)盤(pán)的數(shù)據(jù)丟失，那么利用行校驗(yàn)盤(pán)可以很簡(jiǎn)單 地 計(jì)算出丟失數(shù)據(jù)。如果僅有校驗(yàn)盤(pán)數(shù)據(jù)丟失，那么重新編碼計(jì)算即可。如果是一個(gè)數(shù)據(jù)盤(pán)和對(duì)角線校驗(yàn)盤(pán)數(shù)據(jù)丟失，需要先用行校 驗(yàn)盤(pán)恢復(fù)那個(gè)數(shù)據(jù)盤(pán)上的數(shù)據(jù)，而后重新計(jì)算對(duì)角線校驗(yàn)數(shù)據(jù)。上述情況比較簡(jiǎn)單，下面著重討論兩種比較復(fù)雜的情況，一種是一塊數(shù)據(jù)盤(pán)和行校驗(yàn)盤(pán)同時(shí)發(fā)生數(shù)據(jù)丟失，另一種是兩塊數(shù)據(jù)盤(pán)發(fā)生了數(shù)據(jù)丟失。 對(duì)于第一種情況，首先要重新計(jì)算 S。記丟失數(shù)據(jù)盤(pán)是第 x 塊。令[ 1 , ] 0 , ( 0 , 1 , ... , 1 )pa c k e t p j j p? ? ? ?， S 的計(jì)算方法由式 。 10[ 1 , 1 ] [ , ]( ( 1 ) m o d )pjS p a c k e t x p p a c k e t k jk x j p p????? ? ? ? ?????? ? ? ?， （ ） 然后，就可以利用求出的 S 恢復(fù)丟失的數(shù)據(jù)盤(pán)，由式 。 9 10[ , ] [ , 1 ] [ , ] ,( ( ) m o d , ( ) m o d , 0 , 1 , .. ., 1 )pjjxp a c k e t i x S p a c k e t l p p a c k e t k jl i x p k i x j p p i p???????? ? ? ? ???? ? ? ? ? ? ? ? （ ） 對(duì)于第二種情況，依然要重新計(jì)算 S。由式 。 2200[ , ] [ , 1 ]ppiiS p a c k e t i p p a c k e t i p????? ? ? ?? ? ? ? ?? ? ? ?? ? ? ? （ ） 記丟失的數(shù)據(jù)盤(pán)是第 x 塊和第 y 塊。 x 磁盤(pán)利用對(duì)角線校驗(yàn)組進(jìn)行恢復(fù)， y磁盤(pán)利用行校驗(yàn)組進(jìn)行恢復(fù)，整個(gè)過(guò)程是一個(gè)迭代的過(guò)程。如圖 22 所示， p=5，x=2， y=3。首先計(jì)算 S，而后利用 S 和對(duì)角線校驗(yàn)數(shù)據(jù)恢復(fù) packet[3,3]，再利用行校驗(yàn)數(shù)據(jù)恢復(fù) packet[3,2]，接著恢復(fù) packet[2,3]，如此進(jìn)行下去，直到數(shù)據(jù)盤(pán) 2 和數(shù)據(jù) 盤(pán) 3 在這個(gè)條紋中的數(shù)據(jù)都被恢復(fù)。 Data Disk 0 D