【正文】 中 p 個磁盤是數(shù)據(jù)盤，另兩個為校驗盤。由于 RDP 碼沒有類似 EVENODD 碼中S 的計算，因此計算復(fù)雜度要稍微低于 EVENODD 碼。與 EVENODD 碼類似的是， RDP 碼也使用兩個校驗盤存放冗余信息，一塊是行校驗盤，另一塊是對角線校驗盤。首先計算 S，而后利用 S 和對角線校驗數(shù)據(jù)恢復(fù) packet[3,3]，再利用行校驗數(shù)據(jù)恢復(fù) packet[3,2]，接著恢復(fù) packet[2,3]，如此進行下去，直到數(shù)據(jù)盤 2 和數(shù)據(jù)盤 3 在這個條紋中的數(shù)據(jù)都被恢復(fù)。x 磁盤利用對角線校驗組進行恢復(fù)，y磁盤利用行校驗組進行恢復(fù)，整個過程是一個迭代的過程。由式 。[1,]0(,1.)packetjjp??? （）10[,][,](1)modpjSacketxacketjj??????????，然后，就可以利用求出的 S 恢復(fù)丟失的數(shù)據(jù)盤，由式 。記丟失數(shù)據(jù)盤是第 x 塊。上述情況比較簡單，下面著重討論兩種比較復(fù)雜的情況，一種是一塊數(shù)據(jù)盤和行校驗盤同時發(fā)生數(shù)據(jù)丟失，另一種是兩塊數(shù)據(jù)盤發(fā)生了數(shù)據(jù)丟失。如果僅有校驗盤數(shù)據(jù)丟失，那么重新編碼計算即可。從計算角度，并不會提高編碼的計算復(fù)雜度。即一個條紋單元的更新一般會導(dǎo)致 2 個校驗單元更新。在實際系統(tǒng)中，磁盤布局為此周期的重復(fù)。這便是 EVENODD 碼名稱的由來。 （）20[,1][,](0,)pjpacketiacketijp?????（）10[,][,]()mod,01,.2)pjitiStjkijpi????????????? 其中， 。首先要將各個數(shù)據(jù)盤中相同的校驗組數(shù)據(jù)塊進行異或計算，然后將 S異或進去，才能得到位于對角線校驗盤中該校驗組的最終校驗數(shù)據(jù)。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)的校驗組。第一校驗盤同樣為水平校驗盤，第二校驗盤為對角線校驗盤。 編碼標(biāo)準(zhǔn)的 EVENODD 碼由 p+2 個磁盤組成（p 稱為控制參數(shù)，并且必須是素數(shù)） ，其中 p 個磁盤是數(shù)據(jù)盤，另兩個為校驗盤。由于 RS 碼的編碼、解碼計算都要在伽羅瓦域上進行，計算比較復(fù)雜。令xD， ，那么1({0}){01}yxyxgAg??????? 1({0}){01}yxyBgg???????7， 可以由式（） （）計算得出。x （）25()/()xxxg???如果 中的兩塊磁盤數(shù)據(jù)丟失，記數(shù)據(jù)丟失的磁盤是 和 。如果 中的一塊磁盤和 P 盤同時發(fā)生數(shù)據(jù)丟失，記數(shù)據(jù)丟失的磁盤01~nD?是 。具體如下：如果 中僅有一塊磁盤數(shù)據(jù)丟失，P 沒有數(shù)據(jù)丟失，那么只需要按01~n?照類似 RAID5 的方法利用奇偶校驗重構(gòu)。如果是 中有一個或者兩個發(fā)生了數(shù)據(jù)丟失，整個陣01~nD?列需要重構(gòu)。通常的實現(xiàn)都是事先構(gòu)造出 GF(28)下的對數(shù)表和反對數(shù)表，那么公式（）中對數(shù)和反對數(shù)的運算就6可以通過查表算得。 的計算與之類似。比如需要在 GF(28)下計算，那么計算方法如公式（） 。整個運算都是在GF(28)下進行， 指這個伽羅瓦域的生成元，通常取 。 （）??? （）??????公式（）和（）中，大寫字母表示的變量均指一個向量，該向量每個元素是磁盤上一個字節(jié)的數(shù)據(jù)，維度表示參與校驗的字節(jié)數(shù)目。 ReedSolomon 碼 編碼ReedSolomon 碼（簡稱 RS 碼）[8]最初出現(xiàn)于通訊領(lǐng)域，用于碼字糾錯。因此本章對于每種碼字都從編碼、解碼兩個方面去說明。52. 常見的 RAID6 編碼方式ReedSolomon、EVENODD 和 RDP 是三種重要的 RAID6 編碼方案。一方面對編碼、解碼實現(xiàn)的正確性進行了驗證，另一方面對不同編碼實現(xiàn)下 ZFS 的寫性能進行了測試，驗證了高效的編碼實現(xiàn)可以提升 RAID6 系統(tǒng)的性能這一觀點。第三章對新型的文件系統(tǒng) ZFS 進行了介紹，簡要的分析了 ZFS 上的編碼實現(xiàn)，給出了 EVENODD 和 RDP 碼在 ZFS 上編碼、解碼算法的具體實現(xiàn)，并且給出了使用 SSE 指令對編碼實現(xiàn)進行優(yōu)化的具體方法。全文一共分為五章：第一章是數(shù)據(jù)存儲的發(fā)展情況和 RAID 的簡介，以及全文的主要工作與組織結(jié)構(gòu)的概要。為了進一步的提高編碼的效率，采取使用 SSE 指令代替常規(guī)指令的方法，以 RDP 碼為例對編碼實現(xiàn)進行優(yōu)化。 主要工作和本文的組織結(jié)構(gòu)本文從存儲編碼的角度對 RAID6 進行性能優(yōu)化的研究。其中，每次寫操作，都要涉及編碼計算。4當(dāng)前，RAID0、鏡像機制和基于 RAID5 的單容錯陣列技術(shù)都已經(jīng)比較成熟，而且獲得了廣泛的使用，而 RAID6 還有待研究，如何提高雙容錯陣列的性能成為 RAID 研究的熱點。由于 RAID6 的每次寫操作需要進行兩套校驗數(shù)據(jù)的計算，以及這兩套校驗數(shù)據(jù)的寫入，因此高可靠性是以犧牲了一部分性能而獲得的。于是，單容錯陣列難以滿足人們的需求。一旦有任意的兩塊磁盤的數(shù)據(jù)同時出現(xiàn)錯誤，整個陣列就會變得不可靠。這樣一來，就避免了校驗盤成為系統(tǒng)瓶頸的問題。 RAID5：按塊交叉、奇偶校驗字散布RAID4 的基礎(chǔ)上，RAID5 按照一定的規(guī)律將校驗字散布到不同的磁盤中。相比之下，這種在扇區(qū)一級進行數(shù)據(jù)交叉存儲的分布方法能夠提高讀操作的性能。數(shù)據(jù)按位的方式交替散布寫到每個磁盤成員中，因此每次的讀寫操作都要涉及所有的磁盤，磁盤陣列只能同時相應(yīng)一個讀或?qū)懖僮鳎m合對于帶寬要求嚴(yán)格而 I/O 率較低的系統(tǒng)。對于由 N 塊磁盤組成的磁盤陣列，只需要其中一塊磁盤作為校驗盤存放冗余數(shù)據(jù)，冗余度僅為 1/N。同時，校驗的計算比較復(fù)雜，現(xiàn)在已經(jīng)很少被使用。在漢明碼中，校驗位的位數(shù) 和信息位的位數(shù) N 要K求滿足 的關(guān)系。但是缺點也是明顯的，即冗余度非常高，達到了50%。在這種方式下，只要鏡像對中的兩個磁盤不同時發(fā)生故障，即可以進行數(shù)據(jù)的恢復(fù)。磁盤成員之間組成鏡像對，互為鏡像。但是，也正是因為沒有存放任何冗余信息，陣列中任何磁盤數(shù)據(jù)的錯誤或者丟失，都會造成整個陣列數(shù)據(jù)的丟失，因此，它是 RAID 體系中可靠性最差的。由于數(shù)據(jù)以交替的方式寫入磁盤，多個磁盤通道可以以并行的方式進行工作。2 RAID 介紹RAID 體系可以分成從 0 級到 6 級的 7 個級別[4,5,6]，下面進行簡要的介紹?？梢灶A(yù)見，RAID 將在未來的存儲領(lǐng)域中仍將占據(jù)重要的位置。即使陣列中有磁盤成員出現(xiàn)了數(shù)據(jù)損壞和丟失，通過讀取校驗數(shù)據(jù)進行解碼計算，恢復(fù)丟失的數(shù)據(jù)，很大程度上提高了整個系統(tǒng)存儲數(shù)據(jù)的可靠性。由于每個磁盤成員能夠獨立地處理請求，因此，和使用單塊大容量磁盤相比，使用 RAID 技術(shù)不但能夠降低成本，而且可以獲得更好的 I/O 性能。1988 年，加州大學(xué)伯克利分校的 David A. Patterson 等人提出 RAID[2]（Redundant Arrays of Inexpensive Disks）技術(shù)，即采用多塊廉價磁盤構(gòu)成磁盤陣列，形成邏輯上的一塊大容量存儲設(shè)備提供給系統(tǒng)，十分易于管理[3]。然而，令人遺憾的是，幾十年來，盡管 CPU 的計算速度得到了飛速的提升，但是磁盤的訪問速度以及數(shù)據(jù)傳輸速度的提高遠(yuǎn)遠(yuǎn)比不上處理器的進步。因為磁盤的數(shù)目越多，系統(tǒng)中有磁盤數(shù)據(jù)損壞的可能性就越大，進而系統(tǒng)中數(shù)據(jù)就會變得不可用。盡管單塊磁盤的容量在不斷的變大，但是依然難以滿足人們對存儲容量的突飛猛進的需求。關(guān)鍵詞 磁盤陣列 雙容錯編碼 ZFSIIImplementation of EfficientEncoding Algorithm for Storage CodesAbstractWith 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, ZFSIII目 錄摘 要 ........................................................................................................................................................IABSTRACT.............................................................................................................................................II目 錄 .....................................................................................................................................................III1. 緒論 ...................................................................................................................................................1 課題背景 ......................................................................................................................................1 RAID 介紹 ..................................................................................................................................2 RAID0：沒有任何冗余信息 ..........................................................................................2 RAID1：鏡像機制 .............................................................................................................2 RAID2：漢明碼校驗 .....................................