【正文】 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è)數(shù)據(jù)盤中相同的校驗(yàn)組數(shù)據(jù)塊進(jìn)行異或計(jì)算，然后將 S異或進(jìn)去，才能得到位于對角線校驗(yàn)盤中該校驗(yàn)組的最終校驗(yàn)數(shù)據(jù)。 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ù)塊，在對角線校驗(yàn)盤中并沒有對應(yīng)的校驗(yàn)組。第一校驗(yàn)盤同樣為水平校驗(yàn)盤，第二校驗(yàn)盤為對角線校驗(yàn)盤。 編碼 標(biāo)準(zhǔn)的 EVENODD 碼由 p+2 個(gè)磁盤組成（ p 稱為控制參數(shù)，并且必須是素?cái)?shù)），其中 p 個(gè)磁盤是數(shù)據(jù)盤，另 兩個(gè)為校驗(yàn)盤。由于 RS 碼的編碼、解碼計(jì)算都要在伽羅瓦域上進(jìn)行，計(jì)算比較復(fù)雜。令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ì)算得出。 255( ) / ( )xxx x xD Q Q g Q Q g ?? ? ? ? ? （ ） 如果 01~ nDD? 中的兩塊磁盤數(shù)據(jù)丟失，記數(shù)據(jù)丟失的磁盤是 xD 和 yD 。 如果 01~ nDD? 中的一塊磁盤和 P 盤同時(shí)發(fā)生數(shù)據(jù)丟失，記數(shù)據(jù)丟失的磁盤是 xD 。具體如下： 如果 01~ nDD? 中僅有一塊磁盤數(shù)據(jù)丟失， P 沒有數(shù)據(jù)丟失，那 么只需要按照類似 RAID5 的方法利用奇偶校驗(yàn)重構(gòu)。如果是 01~ nDD? 中有一個(gè)或者兩個(gè)發(fā)生了數(shù)據(jù)丟失，整個(gè)陣列需要重構(gòu)。通常的實(shí)現(xiàn)都是事先構(gòu)造出 GF(28)下的對數(shù)表和反對數(shù)表，那么公式（ ）中對數(shù)和反對數(shù)的運(yùn)算就可以通過查表算得。 /AB的計(jì)算與之類似。比如需要在 GF(28)下計(jì)算AB? ，那么計(jì)算方法如公式（ ）。整個(gè)運(yùn)算都是在GF(28)下進(jìn)行， g 指這個(gè)伽羅瓦域的生成元，通常取 {02}g? 。 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? ?? ? ? ? ? ? ? ? ? （ ） 公式（ ）和（ ）中 ，大寫字母表示的變量均指一個(gè)向量，該向量每個(gè)元素是磁盤上一個(gè)字節(jié)的數(shù)據(jù)，維度表示參與校驗(yàn)的字節(jié)數(shù)目。 ReedSolomon 碼 編碼 ReedSolomon 碼（簡稱 RS 碼） [8]最初出現(xiàn)于通訊領(lǐng)域，用于碼字糾錯(cuò)。因此本章對于每種碼字都從編碼、解碼兩個(gè)方面去說明。 5 2. 常見的 RAID6編碼方式 ReedSolomon、 EVENODD 和 RDP 是三種重要的 RAID6 編碼方案 。一方面對編碼、解碼實(shí)現(xiàn)的正確性進(jìn)行了驗(yàn)證，另一方面對不同編碼實(shí)現(xiàn)下 ZFS 的寫性能進(jìn)行了測試，驗(yàn)證了高效的編碼實(shí)現(xiàn)可以提升 RAID6 系統(tǒng)的性能這一觀點(diǎn)。 第三章對新型的文件系統(tǒng) ZFS 進(jìn)行了介紹，簡要的分析了 ZFS 上的編碼實(shí)現(xiàn)，給出了 EVENODD 和 RDP 碼在 ZFS 上編碼、解碼算法的具體實(shí)現(xiàn)，并且給出了使用 SSE 指令對編碼實(shí)現(xiàn)進(jìn)行優(yōu)化的具體方法。全文一共分為五章： 第一章是數(shù)據(jù)存儲(chǔ)的發(fā)展情況和 RAID 的簡介，以及全文的主要工作與組織結(jié)構(gòu)的概要。為了進(jìn)一步的提高編碼的效率，采取使用 SSE 指令代替常規(guī)指令的方法，以 RDP 碼為例對編碼實(shí)現(xiàn)進(jìn)行優(yōu)化。 主要工作和本文的組織結(jié)構(gòu) 本文從存儲(chǔ)編碼的角度對 RAID6 進(jìn)行性能優(yōu)化的研究。其中，每次寫操作，都要涉及編碼計(jì)算。 當(dāng)前， RAID0、鏡像機(jī)制和基于 RAID5 的單容錯(cuò)陣列技術(shù)都已經(jīng)比較成熟，而且獲得了廣泛的使用，而 RAID6 還有待研究，如何提高雙容錯(cuò)陣列的性能成為 RAID 研究的熱點(diǎn)。由于 RAID6 的每次寫操作需要進(jìn)行兩 套校驗(yàn)數(shù)據(jù)的計(jì)算，以及這兩套校驗(yàn)數(shù)據(jù)的寫入，因此高可靠性是以犧牲了一部分性能而獲得的。于是，單容錯(cuò)陣列難以滿足人們的需求。一旦有任意的兩塊磁盤的數(shù)據(jù)同時(shí)出現(xiàn)錯(cuò)誤，整個(gè)陣列就會(huì)變得不可靠。這樣一來，就避免了校 驗(yàn)盤成為系統(tǒng)瓶頸的問題。 RAID5：按塊交叉、奇偶校驗(yàn)字散布 RAID4 的基礎(chǔ)上， RAID5 按照一定的規(guī)律將校驗(yàn)字散布到不同的磁盤中。相比之下，這種在扇區(qū)一級進(jìn)行數(shù)據(jù)交叉存儲(chǔ)的分布方法能夠提高讀操作的性能。數(shù)據(jù)按位的方式 交替 散布寫到每個(gè)磁盤成員中，因此每次的讀寫操作都要涉及所有的磁盤，磁盤陣列只能同時(shí)相應(yīng)一個(gè)讀或?qū)懖僮鳎m合對于帶寬要求嚴(yán)格而 I/O 率較低的系統(tǒng)。對于由 N 塊磁盤組成的磁盤陣列，只需要其中一塊磁盤作為校驗(yàn)盤存放冗余數(shù)據(jù)，冗余度僅為 1/N。同時(shí)，校驗(yàn)的計(jì)算比較復(fù)雜，現(xiàn)在已經(jīng)很少被使用。在漢明碼中，校驗(yàn)位的位數(shù) K 和信息位的位數(shù) N 要求滿足 121K NK? ? ? ?的關(guān)系。 但是缺點(diǎn)也是明顯的，即冗余度非常高，達(dá)到了 50%。在這種方式下，只要鏡像對 中的兩個(gè) 磁盤 不同時(shí)發(fā)生故障，即 可以進(jìn)行數(shù)據(jù)的恢復(fù)。磁盤成員之間組成鏡像對，互為鏡像。但 是，也正是因?yàn)闆]有存放任何冗余信息，陣列中任何磁盤數(shù)據(jù)的錯(cuò)誤或者丟失，都會(huì)造成整個(gè)陣列數(shù)據(jù)的丟失，因此，它是 RAID 體系中可靠性最差的。由于數(shù)據(jù)以交替的方式寫入磁盤，多個(gè)磁盤通道可以以并行的方式進(jìn)行工作。 2 RAID介紹 RAID 體系可以分成從 0 級到 6 級的 7 個(gè)級別 [4,5,6]，下面進(jìn)行簡要的介紹?？梢灶A(yù)見， RAID 將在未來的存儲(chǔ)領(lǐng)域中 仍將 占據(jù)重要的位置 。即使陣列中有磁盤成員 出現(xiàn)了數(shù)據(jù)損壞和丟失，通過讀取校驗(yàn)數(shù)據(jù)進(jìn)行解碼計(jì)算，恢復(fù)丟失 的數(shù)據(jù)，很大程度上提高了整個(gè)系統(tǒng)存儲(chǔ)數(shù)據(jù)的可靠性。由于每個(gè)磁盤成員能夠獨(dú)立 地 處理請求，因此，和使用單塊 大 容量磁盤相比，使用 RAID 技術(shù)不但能夠降低成本，而且可以獲得更好的 I/O 性能。 1988 年，加州大學(xué)伯克利分校的 David A. Patterson 等人提出 RAID[2]（ Redundant Arrays of Inexpensive Disks）技術(shù)，即采用多塊廉價(jià)磁盤構(gòu)成磁盤陣列，形成邏輯上的一塊大容量存儲(chǔ)設(shè)備提供給系統(tǒng)，十分易于管理 [3]。然而，令人遺憾的是，幾十年來，盡管 CPU 的計(jì)算速度得到了飛速的提升，但是磁盤的訪問速度以及數(shù)據(jù)傳輸速度的提高遠(yuǎn)遠(yuǎn)比不上處理器的進(jìn)步。因?yàn)榇疟P的數(shù)目越多，系統(tǒng)中有磁盤數(shù)據(jù)損壞的可能性就越大，進(jìn)而系統(tǒng)中數(shù)據(jù)就會(huì)變得不可用。 盡管單塊磁盤的容量在不 斷的變大，但是依然難以滿足人們對存儲(chǔ)容量的突飛猛進(jìn)的需求。 關(guān)鍵詞 磁盤陣列 雙容錯(cuò)編碼 ZFS II Implementation of Efficient Encoding Algorithm for Storage Codes Abstract With the rapid expansion of the information, the requirement of storage is more and more serious. The mon solution is using the RAID (Redundant Arrays of Inexpensive Disks) technology. For a RAID system with faulttolerant feature, every write operation should be concerned with encoding calculation, so the performance of the encoding calculation will take a great effect on the RAID system. This article has pared the performance of the three mon RAID6 codes that ReedSolomon, EVENODD and RDP. The classical one, ReedSolomon, has a high encoding putation plexity because of its encoding putation must be proceed on the Galois Field. So we focus on the research of the new array codes, EVENODD and RDP whose encoding putation is based on XOR operation. Moreover, in this article, in order to improve the system performance of writing operations’ speed, we can reduce the encoding putation plexity by using EVENODD or RDP in the RAID6 system whose original double erasure code is ReedSolomon. We have implemented this method on the new file system called ZFS. The experimental results prove the efficiency of our design. Key Words RAID, doubleerasure code, ZFS III 目 錄 摘 要 ...............................................................................................................................................................I ABSTRACT .................................................................................................................................................. II 目 錄 ............................................................................................................................................................III 1. 緒論 ......................................................................................................................................................... 1 課題背景 ........................................................................................................................................... 1 RAID 介紹 ........................................................................................................................................ 2 RAID0：沒有 任何冗余信息 ............................................................................................. 2 RAID1：鏡像機(jī)制 ................................................................................................................. 2 RAID2：漢