計算機科學與技術專業(yè)畢業(yè)設計存儲編碼高效算法的實現

南開大學本科生畢業(yè)論文（設計）中文題目：存儲編碼高效算法的實現外文題目：ImplementationofEfficientEncodingAlgorithmforStorageCodes學號：0610405姓名：年級：2006級學院：信息技術科學學院系別：計算機科學與技術專業(yè)：計算機科學與技術完成日期：2010.5.17指導教師：關于南開大學本科生畢業(yè)論文（設計）的聲明本人鄭重聲明：所呈交的學位論文（設計），題目《存儲編碼高效算法的實現》是本人在指導教師指導下，進行研究工作所取得的成果。除文中已經注明引用的內容外，本學位論文的研究成果不包含任何他人創(chuàng)作的、以公開發(fā)表或沒有公開發(fā)表的作品內容。對本論文所涉及的研究工作做出貢獻的其他個人和集體，均已在文中以明確方式標明。本學位論文原創(chuàng)性聲明的法律責任由本人承擔。學位論文作者簽名：年月日本人聲明：該學位論文是本人指導學生完成的研究成果，已經審閱過論文的全部內容，并能夠保證題目、關鍵詞、摘要部分中英文內容的一致性和準確性。學位論文指導教師簽名：年月日存儲編碼高效算法實現摘要由于信息的飛速膨脹，人們對存儲的需求越來越高，常見的策略是使用RAID（RedundantArraysofInexpensiveDisks）技術以滿足這種需求。對于具有容錯功能的RAID系統，每一次寫操作都會進行編碼計算。因此，編碼的計算性能是影響系統的重要因素之一。本文對Reed-Solomon、EVENODD、RDP這幾種常見的RAID6編碼方式的效率進行比較。傳統Reed-Solomon碼需要在伽羅瓦域上進行運算，其編碼復雜度高。本文著重研究基于異或運算的新型陣列碼EVENODD、RDP編碼的算法和實現技巧，并且提出用EVENODD或RDP替換RAID6系統中原有的Reed-Solomon編碼方式，從而有效地降低編碼運算復雜度，進而提升RAID6系統寫操作的速度。作者將這種思想在新型文件系統ZFS上進行了實現，最終通過測試證明了這一設想。關鍵詞磁盤陣列雙容錯編碼ZFSImplementationofEfficientEncodingAlgorithmforStorageCodesAbstractWiththerapidexpansionoftheinformation,therequirementofstorageismoreandmoreserious.ThecommonsolutionisusingtheRAID(RedundantArraysofInexpensiveDisks)technology.ForaRAIDsystemwithfault-tolerantfeature,everywriteoperationshouldbeconcernedwithencodingcalculation,sotheperformanceoftheencodingcalculationwilltakeagreateffectontheRAIDsystem.ThisarticlehascomparedtheperformanceofthethreecommonRAID6codesthatReed-Solomon,EVENODDandRDP.Theclassicalone,Reed-Solomon,hasahighencodingcomputationcomplexitybecauseofitsencodingcomputationmustbeproceedontheGaloisField.Sowefocusontheresearchofthenewarraycodes,EVENODDandRDPwhoseencodingcomputationisbasedonXORoperation.Moreover,inthisarticle,inordertoimprovethesystemperformanceofwritingoperations’speed,wecanreducetheencodingcomputationcomplexitybyusingEVENODDorRDPintheRAID6systemwhoseoriginaldoubleerasurecodeisReed-Solomon.WehaveimplementedthismethodonthenewfilesystemcalledZFS.Theexperimentalresultsprovetheefficiencyofourdesign.KeyWordsRAID,double-erasurecode,ZFS目錄摘要IAbstractII目錄III1.緒論11.1課題背景11.2RAID介紹21.2.1RAID0：沒有任何冗余信息21.2.2RAID1：鏡像機制21.2.3RAID2：漢明碼校驗21.2.4RAID3：按位交叉存儲的奇偶校驗21.2.5RAID4：按塊交叉存儲的奇偶校驗31.2.6RAID5：按塊交叉、奇偶校驗字散布31.2.7RAID6：P+Q陣列31.3主要工作和本文的組織結構42.常見的RAID6編碼方式52.1Reed-Solomon碼52.1.1編碼52.1.2解碼62.2EVENODD碼72.2.1編碼72.2.2解碼82.3RDP碼92.3.1編碼92.3.2解碼102.4幾種編碼方式的比較112.5編碼實現122.5.1以校驗字為中心還是以數據字為中心122.5.2采用行優(yōu)先的方式還是采用列優(yōu)先的方式133.高效RAID6編碼在ZFS中的實現153.1ZFS簡介153.2容錯編碼在ZFS中的位置153.2.1總體結構153.2.2存儲設備的組織方式163.2.3raidz組件剖析163.3實現中需要注意的問題183.3.1問題由來183.3.2解決方案203.4EVENODD碼在ZFS中的實現213.4.1編碼213.4.2解碼223.5RDP碼在ZFS中的實現233.5.1編碼233.5.2解碼253.6使用SSE指令加速編碼過程274.實驗驗證294.1實驗環(huán)境294.2正確性驗證294.3性能測試305.總結和展望33參考文獻34致謝361.緒論1.1課題背景隨著信息化的不斷發(fā)展，人們對存儲的需求越來越高。IDC表示，全球的數據量已經超出了可用的存儲空間——對存儲容量的需求以每年60%的速度增長[1]。盡管單塊磁盤的容量在不斷的變大，但是依然難以滿足人們對存儲容量的突飛猛進的需求。簡單地在系統中增加多塊磁盤雖然可以滿足容量的需求，但是會給系統的可靠性帶來影響。因為磁盤的數目越多，系統中有磁盤數據損壞的可能性就越大，進而系統中數據就會變得不可用。同時，由于海量數據的頻繁寫入與訪問，存儲設備的I/O性能也變得至關重要。然而，令人遺憾的是，幾十年來，盡管CPU的計算速度得到了飛速的提升，但是磁盤的訪問速度以及數據傳輸速度的提高遠遠比不上處理器的進步。于是，在較低成本基礎上實現大容量、高可靠性和高性能數據存儲，成為了研究的熱點，并且也是政府和企業(yè)的重要需求。1988年，加州大學伯克利分校的DavidA.Patterson等人提出RAID[2]（RedundantArraysofInexpensiveDisks）技術，即采用多塊廉價磁盤構成磁盤陣列，形成邏輯上的一塊大容量存儲設備提供給系統，十分易于管理[3]。它將I/O數據進行劃分，將I/O請求劃分到多個磁盤成員上。由于每個磁盤成員能夠獨立地處理請求，因此，和使用單塊大容量磁盤相比，使用RAID技術不但能夠降低成本，而且可以獲得更好的I/O性能。在可靠性方面，磁盤陣列采用一定的編碼方式，計算存放的數據字的校驗和，在陣列中分出部分空間存放這些校驗字。即使陣列中有磁盤成員出現了數據損壞和丟失，通過讀取校驗數據進行解碼計算，恢復丟失的數據，很大程度上提高了整個系統存儲數據的可靠性。經過了20余年的發(fā)展，RAID已經獲得了廣泛應用，技術也在不斷的前進?？梢灶A見，RAID將在未來的存儲領域中仍將占據重要的位置。同時，該技術還有很多方面需要發(fā)展和完善，因此對其進行研究具有重要的意義。1.2RAID介紹RAID體系可以分成從0級到6級的7個級別[4,5,6]，下面進行簡要的介紹。RAID0：沒有任何冗余信息該級別的RAID僅僅提供將數據進行條紋化寫入磁盤陣列和將數據從磁盤陣列去條紋化讀出的功能，沒有任何校驗計算，因此也沒有存放任何冗余信息。由于數據以交替的方式寫入磁盤，多個磁盤通道可以以并行的方式進行工作。同時由于不需要任編碼操作計算校驗數據，因此RAID0是RAID體系中寫操作性能最好的。但是，也正是因為沒有存放任何冗余信息，陣列中任何磁盤數據的錯誤或者丟失，都會造成整個陣列數據的丟失，因此，它是RAID體系中可靠性最差的。RAID1：鏡像機制該級別的RAID采用一種比較簡單的方式存放冗余數據——鏡像機制。磁盤成員之間組成鏡像對，互為鏡像。對于每次寫操作，需要向構成鏡像對的兩個磁盤成員上，寫入相同的數據。在這種方式下，只要鏡像對中的兩個磁盤不同時發(fā)生故障，即可以進行數據的恢復。RAID1的特點是易于實現，具有極高的可靠性和很好的性能。但是缺點也是明顯的，即冗余度非常高，達到了50%。RAID2：漢明碼校驗RAID2采用漢明碼進行校驗位的編碼，這種校驗碼可以檢測出兩位錯誤或者校正一位錯誤的校驗碼。在漢明碼中，校驗位的位數和信息位的位數N要求滿足的關系。因此使用的冗余盤數目多，與數據盤的數目成正相關。同時，校驗的計算比較復雜，現在已經很少被使用。RAID3：按位交叉存儲的奇偶校驗RAID3是由RAID2發(fā)展而來，其顯著的特點是用簡單的奇偶校驗方式代替RAID2復雜的漢明碼校驗方式。對于由N塊磁盤組成的磁盤陣列，只需要其中一塊磁盤作為校驗盤存放冗余數據，冗余度僅為1/N。如果其中一塊存放數據位的磁盤數據丟失，可以利用其余的磁盤和唯一的校驗磁盤通過異或操作進行恢復。數據按位的方式交替散布寫到每個磁盤成員中，因此每次的讀寫操作都要涉及所有的磁盤，磁盤陣列只能同時相應一個讀或寫操作，適合對于帶寬要求嚴格而I/O率較低的系統。RAID4：按塊交叉存儲的奇偶校驗RAID4和RAID3的不同僅僅在于數據分塊的粒度，它的條紋單元大小一般是磁盤扇區(qū)大小的倍數。相比之下，這種在扇區(qū)一級進行數據交叉存儲的分布方法能夠提高讀操作的性能。但是，對于“小寫”請求，需要用“讀——修改——寫”（Read-Modify-Write，RMW）的方式進行處理：讀舊數據字、讀舊校驗字、計算新校驗、寫新數據字、寫新校驗字，因而校驗盤成為了系統瓶頸。RAID5：按塊交叉、奇偶校驗字散布RAID4的基礎上，RAID5按照一定的規(guī)律將校驗字散布到不同的磁盤中。對于多個“小讀”“小寫”操作，如果訪問的校驗盤和數據盤互不相同，幾個操作就可以并行執(zhí)行。這樣一來，就避免了校驗盤成為系統瓶頸的問題。RAID6：P+Q陣列以上的6個級別的RAID，最多只能容許其中任意的一塊磁盤損壞。一旦有任意的兩塊磁盤的數據同時出現錯誤，整個陣列就會變得不可靠。由于實際應用對存儲需求的提高，陣列中的磁盤成員數目增多，系統故障的期望就會變大[7]。于是，單容錯陣列難以滿足人們的需求。RAID6是在單容錯陣列的基礎上增加了一份校驗數據，這兩份校驗數據一份稱為P，另一份稱為Q，P和Q存放在不同的磁盤上，構成雙容錯陣列，大大提高了磁盤陣列的數據可靠性。由于RAID6的每次寫操作需要進行兩套校驗數據的計算，以及這兩套校驗數據的寫入，因此高可靠性是以犧牲了一部分性能而獲得的。適用于磁盤成員數目多或者對可靠性要求高的磁盤陣列。當前，RAID0、鏡像機制和基于RAID5的單容錯陣列技術都已經比較成熟，而且獲得了廣泛的使用，而RAID6還有待研究，如何提高雙容錯陣列的性能成為RAID研究的熱點。對于RAID系統來說，每次硬盤I/O都可以歸結為對磁盤陣列條紋的讀寫。其中，每次寫操作，都要涉及編碼計算。而隨著高性能存儲介質如SSD的出現，以及應用對更高容錯能力（更大的編碼計算量）的冗余編碼的需求，編碼計算時間占寫操作總時間的比重逐漸加大，因此編碼的效率是影響RAID系統的性能的重要因素之一。1.3主要工作和本文的組織結構本文從存儲編碼的角度對RAID6進行性能優(yōu)化的研究。對幾種常見雙容錯編碼進行了比較，同時，對于近幾年由Sun公司開發(fā)、備受關注的文件系統ZFS的編碼實現進行了剖析，在其上設計并實現了cache優(yōu)化的EVENODD和RDP碼的編碼方法。為了進一步的提高編碼的效率，采取使用SSE指令代替常規(guī)指令的方法，以RDP碼為例對編碼實現進行優(yōu)化。最終，通過實驗驗證了高效的編碼實現可以提升RAID6系統的性能這一觀點。全文一共分為五章：第一章是數據存儲的發(fā)展情況和RAID的簡介，以及全文的主要工作與組織結構的概要。第二章介紹了常見的RAID6編碼方式，對它們進行比較，并且給出了采用cache優(yōu)化的實現方法。第三章對新型的文件系統ZFS進行了介紹，簡要的分析了ZFS上的編碼實現，給出了EVENODD和RDP碼在ZFS上編碼、解碼算法的具體實現，并且給出了使用SSE指令對編碼實現進行優(yōu)化的具體方法。第四章是論文工作的實驗部分。一方面對編碼、解碼實現的正確性進行了驗證，另一方面對不同編碼實現下ZFS的寫性能進行了測試，驗證了高效的編碼實現可以提升RAID6系統的性能這一觀點。第五章對全文進行總結，以及對今后工作展望。2.常見的RAID6編碼方式Reed-Solomon、EVENODD和RDP是三種重要的RAID6編碼方案。對于RAID系統，計算校驗的過程是編碼的過程，故障恢復（重構）的過程是解碼的過程。因此本章對于每種碼字都從編碼、解碼兩個方面去說明。比較這三種編碼方式，其第一校驗盤是水平校驗盤，即每個校驗塊由數據盤中相同偏移的數據塊經異或運算而得，不同之處在于第二校驗盤的編碼方式。2.1Reed-Solomon碼編碼Reed-Solomon碼（簡稱RS碼）[8]最初出現于通訊領域，用于碼字糾錯。由n塊存放數據字的磁盤和2塊存放校驗字的磁盤構成的RAID6陣列，第二校驗盤如果使用RS碼，則兩個校驗盤按照公式（2.1）和公式（2.2）進行構造[9]。（2.1）（2.2）公式（2.1）和（2.2）中，大寫字母表示的變量均指一個向量，該向量每個元素是磁盤上一個字節(jié)的數據，維度表示參與校驗的字節(jié)數目。對應n塊存放數據字的磁盤，P、Q對應兩塊存放校驗字的磁盤。整個運算都是在GF(28)下進行，指這個伽羅瓦域的生成元，通常取。在GF(28)下的加法、減法運算，等同于普通的按位異或運算，而乘法和除法運算相對復雜，需要進行對數和反對數的變換。比如需要在GF(28)下計算，那么計算方法如公式（2.3）。（2.3）公式（2.3）中，符號表示運算符的兩個操作數先進行常規(guī)的加法，然后對255取模。的計算與之類似。不難看出，采用這種方式進行校驗字的編碼，需要頻繁的進行對數和反對數的運算，比較復雜。通常的實現都是事先構造出GF(28)下的對數表和反對數表，那么公式（2.3）中對數和反對數的運算就可以通過查表算得。解碼如果僅是P、Q丟失，那么重構只需要重新按照公式（2.1）和（2.2）再次進行編碼的計算。如果是中有一個或者兩個發(fā)生了數據丟失，整個陣列需要重構。實際上重構的方法就是解由式（2.1）和（2.2）組成的方程組。具體如下：如果中僅有一塊磁盤數據丟失，P沒有數據丟失，那么只需要按照類似RAID5的方法利用奇偶校驗重構。如果Q的數據也發(fā)生了丟失，還需要按照公式（2.2）重構Q盤。如果中的一塊磁盤和P盤同時發(fā)生數據丟失，記數據丟失的磁盤是。令，由式（2.2）計算的結果記為，則有（2.4）公式（2.4）經過整理，可以得到計算的公式（2.5）。（2.5） 如果中的兩塊磁盤數據丟失，記數據丟失的磁盤是和。令并且，由式（2.1）計算的結果記為，由式（2.2）計算的結果記為，則有（2.6）（2.7）公式（2.7）經過變形，得到（2.8）將式（2.8）代入式（2.6），并且經過整理，可以求出。令，，那么，可以由式（2.9）（2.10）計算得出。（2.9）（2.10）2.2EVENODD碼1995年，MarioBlaum等人提出EVENODD[10]陣列編碼方式。由于RS碼的編碼、解碼計算都要在伽羅瓦域上進行，計算比較復雜。而EVENODD碼所有的校驗計算都是基于簡單的異或操作，計算復雜度低，比RS碼具有更好的性能。編碼標準的EVENODD碼由p+2個磁盤組成（p稱為控制參數，并且必須是素數），其中p個磁盤是數據盤，另兩個為校驗盤。每個磁盤劃分為p-1個塊（packet），因此一個EVENODD編碼系統可以用一個(p-1)×(p+2)矩陣表示，這也是這類編碼“奇偶校驗陣列碼”（parityarraycode）名稱的由來。第一校驗盤同樣為水平校驗盤，第二校驗盤為對角線校驗盤。圖2-1給出了p=5的時候，由7個磁盤組成的磁盤陣列的EVENODD編碼的示意圖，每個塊用一個數字表示所屬的對角線校驗組。DataDisk0DataDisk1DataDisk2DataDisk3DataDisk4RowParityDiag.Parity01234x012340x123401x234012x3不難看出，標記為“4”這些數據塊，在對角線校驗盤中并沒有對應的校驗組。EVENODD規(guī)定，這些數據塊需要進行異或運算，得到一個新的數據塊，記為S。首先要將各個數據盤中相同的校驗組數據塊進行異或計算，然后將S異或進去，才能得到位于對角線校驗盤中該校驗組的最終校驗數據。EVENODD（2.11）（2.12）其中，。從另一個角度講，如果將奇偶校驗分成奇校驗和偶校驗的話，正是S的每一位，確定了對角線校驗盤中的某一數據塊對應的位應該是奇校驗還是偶校驗。這便是EVENODD碼名稱的由來。需要注意的是，圖2-1所示只是一個編碼周期。在實際系統中，磁盤布局為此周期的重復。另一點值得注意的是，如果我們將packet實現為條紋單元，將導致較差的更新代價。即一個條紋單元的更新一般會導致2個校驗單元更新。但如果將編碼周期的一列實現為一個條紋單元，則可達到最優(yōu)的更新代價。從計算角度，并不會提高編碼的計算復雜度。解碼如果僅有一個數據盤的數據丟失，那么利用行校驗盤可以很簡單地計算出丟失數據。如果僅有校驗盤數據丟失，那么重新編碼計算即可。如果是一個數據盤和對角線校驗盤數據丟失，需要先用行校驗盤恢復那個數據盤上的數據，而后重新計算對角線校驗數據。上述情況比較簡單，下面著重討論兩種比較復雜的情況，一種是一塊數據盤和行校驗盤同時發(fā)生數據丟失，另一種是兩塊數據盤發(fā)生了數據丟失。對于第一種情況，首先要重新計算S。記丟失數據盤是第x塊。令，S的計算方法由式2.13。（2.13）然后，就可以利用求出的S恢復丟失的數據盤，由式2.14。（2.14）對于第二種情況，依然要重新計算S。由式2.15。（2.15）記丟失的數據盤是第x塊和第y塊。x磁盤利用對角線校驗組進行恢復，y磁盤利用行校驗組進行恢復，整個過程是一個迭代的過程。如圖2-2所示，p=5，x=2，y=3。首先計算S，而后利用S和對角線校驗數據恢復packet[3,3]，再利用行校驗數據恢復packet[3,2]，接著恢復packet[2,3]，如此進行下去，直到數據盤2和數據盤3在這個條紋中的數據都被恢復。DataDisk0DataDisk1DataDisk2DataDisk3DataDisk4RowParityDiag.Parity01234x012340x123401x234012x32.3RDP碼2004年，PeterCorbett等人提出一種新型雙容錯陣列碼——RDP碼[11]。與EVENODD碼類似的是，RDP碼也使用兩個校驗盤存放冗余信息，一塊是行校驗盤，另一塊是對角線校驗盤。但是，EVENODD碼計算對角線校驗數據的時候，沒有把行校驗盤的數據計算進去，因此屬于“校驗無關”的陣列碼；而RDP碼在計算對角線校驗數據的時候，需要將行校驗盤和其他數據盤一起計算進去，屬于“校驗相關”的陣列碼。由于RDP碼沒有類似EVENODD碼中S的計算，因此計算復雜度要稍微低于EVENODD碼。更進一步的，文獻[11]在理論上進行了證明，RDP碼達到了雙容錯編碼的最優(yōu)編碼計算復雜性和接近最優(yōu)的解碼計算復雜性。編碼標準的RDP碼由p+1個磁盤組成（p稱為控制參數，并且必須是素數），其中p個磁盤是數據盤，另兩個為校驗盤。每個磁盤劃分為p-1個塊（packet），因此一個RDP編碼系統可以用一個(p-1)×(p+1)矩陣表示。圖2-3給出了p=5的時候，由6個磁盤組成的RDP陣列的示意圖，每個塊用一個數字表示所屬的對角線校驗組。同樣，標記為“4”的這些塊沒有參與任何對角線校驗組。和EVENODD碼類似，圖2-3依然表示的是一個編碼周期，而并不是把packet實現為條紋單元。DataDisk0DataDisk1DataDisk2DataDisk3RowParityDiag.Parity012340123401234012340123兩個校驗盤的編碼計算可以總結為公式（2.16）和（2.17）。（2.16）（2.17）解碼對于僅有一個數據盤的數據丟失、僅有校驗盤的數據丟失以及一個數據盤和對角線校驗盤的數據丟失的情況，重構的方法與EVENODD類似，這里不再贅述。這里主要考慮一個數據盤和行校驗盤的數據丟失、兩個數據盤的數據同時丟失的情況發(fā)生時，丟失的數據如何重構。對于這兩種情況，重構的方法是相同的。記丟失的數據盤是第x塊和第y塊。首先使用對角線校驗數據恢復x，利用行校驗數據恢復y，反復進行下去，直到磁盤x不能通過對角線數據恢復為止（磁盤x中不參加對角線校驗的數據塊）。然后使用對角線校驗數據恢復y，使用行校驗數據恢復x，反復進行下去，直到磁盤y不能通過對角線數據恢復為止。此時，重構完畢。圖2-4描述了情況下解碼的過程。首先利用對角線校驗數據恢復packet[0,2]，利用行校驗數據恢復packet[0,3]。重復這個過程，直到packet[2,2]不能依靠對角線校驗數據恢復。此時，利用對角線校驗數據恢復packet[3,3]，再利用行校驗數據恢復packet[3,2]。重復這個過程，直到packet[1,3]不能依靠對角線校驗數據恢復。磁盤2和磁盤3在該條紋中的所有數據均被恢復。DataDisk0DataDisk1DataDisk2DataDisk3RowParityDiag.Parity0123401234012340123401232.4幾種編碼方式的比較下面，我們將RS碼、EVENODD碼和RDP碼這幾種重要的RAID6編碼進行比較。第一，從冗余度上對這三種存儲編碼方式進行比較。對于由n塊磁盤組成的RAID6陣列，無論采用哪種編碼方式，陣列只需要兩塊磁盤存放校驗字，因此冗余度均為。第二，從計算的復雜度上對這三種存儲編碼方式進行比較。RS碼需要在GF(28)上進行運算，整個過程計算復雜。EVENODD碼和RDP碼都是基于異或操作的陣列碼，復雜度比RS碼要小很多。對EVENODD和RDP兩種編碼方式之間進行比較：由于EVENODD碼計算對角線校驗的時候需要把S計算在內，因而需要額外進行S的計算；而RDP碼沒有計算S的開銷。因而從理論上，對于全條紋的覆寫，RDP碼的編碼計算復雜度會稍低于EVENODD碼。三種編碼方式計算冗余信息時在單個條紋上的異或次數的比較如表（2-1）和表（2-2）[12]。對于小的寫操作，如果采用RMW的方法，那么對于EVENODD碼，如果修改的數據涉及到計算S的數據塊，那么整個對角線校驗盤該條紋上的數據塊都要和舊的S以及新的S進行異或操作，而RDP碼沒有這種開銷。從這個角度上講，RDP碼也會優(yōu)于EVENODD碼。值得一提的是，由于RS碼歷史最長，使用非常廣泛，比如在Linux內核中的RAID6編碼就是用的RS碼。另外已經有很多硬件電路實現了RS碼。因此盡管RS碼的編碼復雜度高于EVENODD以及RDP，依然占有很重要的地位。表2-1：EVENODD碼和RS碼的比較磁盤個數EVENODDRS改進系數79.811.81.21913.819.91.441321.940.61.851525.953.32.05表2-2：EVENODD碼和RDP碼的比較磁盤個數RDPEVENODD改進系數666.671.1181010.81.08142222.911.04183030.931.032.5編碼實現對于RS碼，前人已經總結出了很成熟的實現方法，基本已經成型。其主要思想，是把GF(28)上的單個字節(jié)的校驗數據計算，轉化成為多個字節(jié)存放在一個字中同時計算：對于32位系統采用4字節(jié)同時計算；對于64位系統采用8字節(jié)同時計算。另外，對伽羅瓦域上第二校驗盤的計算采用移位、掩模、異或的方法進行實現以提升編碼速度。在Linux內核和ZFS中都已經得到了很好的實現。這里，本文主要關注新型陣列碼——EVENODD和RDP的實現方法。以校驗字為中心還是以數據字為中心對于單容錯的奇偶校驗碼（RAID4/5），編碼計算直接將數據字進行異或運算，即可得到校驗字。由前三節(jié)給出的編碼公式，直觀的編碼算法也可以校驗字為中心，即按順序計算水平校驗字packet[0,0]~packet[p-2,0]，然后以類似順序計算對角線校驗數據，如圖2-5所示（線型表示計算順序，順序為先實線、后虛線，下同）。但在單容錯系統中，每個數據字都只參與一個校驗組，在編碼計算過程中只被訪問一次。而在雙容錯RAID系統中，每個數據字參與兩個校驗組，如果以校驗字為中心進行編碼計算，每個數據字會被訪問兩次。我們知道，在計算機系統中，訪問內存數據時，首先會將數據讀入cache，然后才會由CPU進行處理。因此，在以校驗字為中心進行RDP編碼計算時，若條紋單元較大，每個數據字會兩次進入/換出cache，導致對內存帶寬的較大壓力。DataDisk0DataDisk1DataDisk2DataDisk3RowParityDiag.Parity012340123401234012340123DataDisk0DataDisk1DataDisk2DataDisk3RowParityDiag.Parity012340123401234012340123文獻[13]提出了以數據字為中心的策略，即，每讀入一個數據字，將它異或到所屬的兩個校驗字，如圖2-6所示。這樣，每訪問一個數據字，它所涉及的運算一次性完成，每個數據字只進入cache一次，極大地提高了cache的使用效率。由于基于奇偶校驗的單/雙容錯碼的計算復雜性較低，可以認為其編碼運算是一種數據密集型運算，因此編碼性能主要取決于訪存性能。以數據字為中心的計算方式由于可以更為有效地利用cache，帶寬需求更低，因此可以明顯提高編碼性能。對RDP碼，需要注意的是，當所有數據字處理完畢后，還需訪問對角線校驗字所依賴的水平校驗字一次，完成對角線校驗的最終計算。采用行優(yōu)先的方式還是采用列優(yōu)先的方式在以數據字為中心進行編碼計算的基礎上，對于數據字參與運算的順序，同樣有兩種選擇。一種是行優(yōu)先的方式：首先處理第一個數據盤的第一個packet，接著處理第二個數據盤的第一個packet，依此類推，直至完成水平校驗盤的第一個packet；之后，再處理第一個數據盤的第二個packet，依此類推，直至水平校驗盤的最后一個packet處理完畢，如圖2-7所示。另一種是列優(yōu)先的方式，即首先順序處理第一個數據盤的所有packet，接著處理第二個數據盤的所有packet，依此類推，直至水平校驗盤，如圖2-6所示。由于每一列（磁盤）的數據在內存中是連續(xù)的，相比之下，列優(yōu)先的方式可以更好地利用cache的預取機制，掩蓋內存至cache的延遲，但需要全部校驗單元一直駐留cache才能獲得最佳性能，因此當條紋單元較小時具有更好的性能。DataDisk0DataDisk1DataDisk2DataDisk3RowParityDiag.Parity012340123401234012340123綜上所述，實現中宜采用以數據字為中心、列優(yōu)先的方式。3.高效RAID6編碼在ZFS中的實現構造RAID可以采用硬件方法，亦可以采用軟件方法。由于本文主要討論的是通過軟件方式實現RAID，因此，RAID的管理屬于操作系統內核和/或文件系統的一部分。上一章對幾種常見的RAID6編碼進行了討論和分析，這一章將具體的結合文件系統ZFS，用新型的陣列碼EVENODD或RDP替換原有的RS碼，以提升編碼的速度，進而優(yōu)化文件系統寫操作的性能。3.1ZFS簡介ZFS是Sun推出的一款革新性的文件系統。與傳統文件相比，它具有許多革新性的特點，能夠顯著提高文件系統的管理效率。Sun驕傲的稱其為“史上最后一個文件系統”[14]。ZFS的特點主要包括：用存儲池取代了卷管理器，文件系統的大小不再受限于設備，而是可以隨著存儲池的規(guī)模變化動態(tài)調整；引入事務性語義，避免了文件系統一致性檢查帶來的性能損失；128位文件系統和元數據動態(tài)分配為ZFS提供了充分的存儲空間和靈活性；基于鏡像、raidz（單容錯RAID5的變形）和raidz2（雙容錯）提供的數據可靠性。由于實驗所采用的操作系統是Linux，所以筆者選用的文件系統是基于Fuse[15]版本的ZFS，版本號。目前，標準版的ZFS只適用于Solaris操作系統中，在Linux下無法安裝和使用。3.2容錯編碼在ZFS中的位置在ZFS中，容錯編碼的功能實現位于raidz組件。為了在ZFS中實現容錯編碼，我們先要對編碼的上下文，即raidz組件，進行分析。在考察raidz組件的數據結構以及接口實現之前，有必要對系統結構以及ZFS對存儲設備的組織方式進行了解和分析。總體結構ZFS文件系統整體結構分為用戶部分和核心部分[16]。用戶部分提供與用戶的接口，包括用戶輸入的命令解析，將某個存儲池虛擬為操作系統/dev下的一個卷呈現給用戶等等。ZFS的核心部分自上而下大致分為三層：接口層、事務對象層、存儲池層。接口層為用戶空間提供的數據接口和控制接口。事務對象層集合了數據管理單元、快照、屬性處理、意圖日志等的對象級別的實現。最底層的存儲池層負責對存儲設備進行管理，是事務對象層的各項策略與存儲設備交互的通道。實現容錯編碼功能的raidz組件，就位于這一層。存儲設備的組織方式ZFS以存儲池的方式組織存儲設備，池中的文件系統不局限于單個設備，不同文件系統也可共享同一設備。池中所有設備都抽象成為虛設備，組成三個層次的樹形結構。如圖3-1所示，每個節(jié)點表示一個虛設備，每個虛設備的信息都存儲在對應的vdev對象中。根節(jié)點稱為root節(jié)點或者root虛設備；內部節(jié)點稱為top節(jié)點或者top虛設備；葉節(jié)點稱為leaf節(jié)點或者leaf虛設備。root和top都是文件系統的邏輯虛設備；而leaf節(jié)點是物理虛設備，對應物理存儲設備，可以是一個磁盤，或者是一個分區(qū)。容錯編碼應用于top層次，即一個top的多個孩子（leaf設備）可組成一個磁盤陣列。這里，用一個例子可以更清楚地表示這種樹形結構。用戶可以執(zhí)行這樣一條命令“zpoolcreate–ftankraidz/dev/sda5/dev/sdb5/dev/sdc5raidz/dev/sda6/dev/sdb6/dev/sdc6”raidz組件剖析在ZFS中，任何用戶I/O請求都被封裝成為zio對象。請求被ZFS系統映射到虛設備進行進行實際的讀寫操作。如果請求訪問的top節(jié)點的是raidz或者raidz2類型，則由raidz組件負責請求映射。圖3-2顯示了數據流向和層次關系，圖3-2中是一個由7個物理虛設備組成的雙容錯磁盤陣列。當寫請求到達，raidz將數據劃分為數據單元，并采用某種雙容錯編碼方案計算出兩個校驗單元，然后將這些條紋單元（包括數據和校驗）寫入物理虛設備。對于讀請求，只需映射到正確的物理虛設備，讀取數據單元即可。當發(fā)生磁盤故障，校驗單元被用來重構出丟失的數據單元。ZFS維護兩個數據結構來完成磁盤陣列的讀寫：raidz_col描述一個條紋單元的相關信息，包括條紋單元在條紋中的下標、I/O請求大小、I/O數據的指針、條紋單元的狀態(tài)等。raidz_map描述一個條紋的信息，包括這個條紋中的條紋單元個數、狀態(tài)、第一塊數據盤在條紋中的下標，以及每個條紋單元的首址。typedefstructraidz_col{ uint64_trc_devidx; /*孩子虛設備下標*/ uint64_trc_offset; uint64_trc_size; /*條紋單元大小*/ void*rc_data; /*條紋單元存儲的數據*/ intrc_error; /*發(fā)生的I/O錯誤數*/ uint8_trc_tried; uint8_trc_skipped; }raidz_col_t;typedefstructraidz_map{ uint64_trm_cols; /*條紋單元個數*/ uint64_trm_bigcols; /*比較大的條紋單元個數*/ uint64_trm_asize; /*條紋大小*/ uint64_trm_missingdata; /*無效的存放數據字的條紋單元數*/ uint64_trm_missingparity; /*無效的存放校驗字的條紋單元數*/ uint64_trm_firstdatacol; /*存放數據字的條紋單元在條紋中的下標*/ raidz_col_trm_col[1]; /*條紋單元的句柄*/}raidz_map_t;此外，raidz組件對外提供6個接口，其中和編碼密切相關的接口如下：I/O啟動（vdev_raidz_io_start）接口：該接口生成一個raidz_map結構的實例。zio將記錄的數據條紋化引用方式傳遞給此raidz_map對象。然后，對條紋中數據部分（而非校驗盤數據）進行修改。如果是寫操作，將調用處理陣列編碼的函數，將校驗單元寫請求發(fā)送給子設備。如果是讀操作，則從對應數據單元所在leaf虛設備進行讀取。I/O完成（vdev_raidz_io_done）接口：該接口根據當前狀態(tài)決定重構的策略：如果僅僅是校驗盤損壞，調用編碼函數重新編碼即可；否則需要調用解碼函數，對于雙容錯陣列，分為三種情況，即依靠P盤解碼（Q和一個數據盤損壞的情況）、依靠Q盤解碼（P和一個數據盤損壞的情況）、依靠P/Q盤解碼（兩個數據盤損壞的情況）。如果任何方法均無法完成重構，將返回錯誤信息。如果收到的請求是寫操作，或者發(fā)現需要重構，那么就調用底層函數，將條紋單元中的數據實際寫入對應的leaf虛設備上。3.3實現中需要注意的問題問題由來傳統磁盤陣列對小數據寫的處理方式為“讀－修改－寫”策略（Read-Modify-Write，RMW），即首先讀取要更新的數據單元的舊有內容和校驗單元的舊有內容，然后結合更新數據計算出校驗單元的新內容，最后將更新數據和校驗單元的新內容寫入磁盤。對于小數據，RMW策略明顯優(yōu)于重構寫策略（ReconstructWrite，讀取不更新的數據單元來和更新數據一起計算出校驗單元的新內容），但仍然需要4次磁盤操作才能完成一次寫請求。而且當寫操作過程中發(fā)生系統崩潰，就有可能造成同一條紋中數據單元和校驗單元的不一致。針對傳統磁盤陣列的這些缺點，ZFS采用了寫請求聚合策略。即推遲寫請求的處理，將多個寫請求組合在一起，形成整條紋寫入磁盤，這樣即可解決小寫性能缺陷。但這一策略需要解決兩個問題。首先，傳統的用戶地址到磁盤陣列地址的映射為固定映射方式，數據更新應覆蓋固定地址的舊數據。這樣，多個寫請求的覆蓋地址可能是不連續(xù)的，則無法組合為整條紋。為此，ZFS采取了追加寫方式。即新數據并不覆蓋舊數據，而是寫入新分配的磁盤空間中，而舊數據占用的空間會適時回收。這樣，只要將多個寫請求分配到同一條紋的地址中，即可實現整條紋寫。此外，追加寫還可有效解決寫操作中系統崩潰造成的不一致問題。另一個問題是，若系統負載較輕，可能較長時間也無法組合出足夠大小的寫數據量。為此，ZFS采用了可變條紋設計。即條紋長度（條紋單元數）與條紋單元大小均是可變的，根據寫請求聚合情況動態(tài)確定。ZFS在請求聚合之后，形成的條紋大?。]算上校驗字條紋）為磁盤扇區(qū)大?。?12B）的整數倍，在512B～128KB之間，并不一定能夠被存放數據字的虛設備個數整除。于是，ZFS進行了如下的處理。/*數據以1<<unit_shift為單位大小分成單元進行散布*/ /*dcols：所屬top節(jié)點下面的leaf虛設備的個數*/s=zio->io_size>>unit_shift;/*I/O數據的大?。▎挝?<<unit_shift）*/ q=s/(dcols-nparity);r=s-q*(dcols-nparity); bc=(r==0?0:r+nparity);/*較大條紋單元個數*/ acols=(q==0?bc:dcols);/*條紋單元個數*/for(c=0;c<acols;c++){……rm->rm_col[c].rc_size=(q+(c<bc))<<unit_shift;…… }一種很可能的分布如圖3-3。部分條紋單元是較大的條紋，其他是較小的條紋，圖3-3中將較小的條紋的不足的部分用陰影區(qū)域補足。上面的源碼中沒有標記含義的變量在圖3-3中均已標出?？梢钥吹剑@個策略盡量均勻分布數據，未將全部“不足”部分分布在最后一個數據盤，這樣可以使不同數據盤的讀寫負載更為均衡。對于校驗盤而言，顯然應該是完整條紋單元大小。由上述的分析可以看出，ZFS很可能無法滿足EVENODD和RDP陣列碼對條紋單元大小的需求。為了滿足上述處理策略的需求，需要在標準EVENODD和RDP編碼結構的基礎上加以變化。解決方案首先，這兩種陣列碼要求條紋單元大小為控制參數減1的整數倍（其中控制參數為素數），而且每個條紋單元大小均相同。對此的解決辦法是，在編碼/解碼運算中，陰影區(qū)域視為全0，因為0對異或運算的結果不會有任何影響。然后，另一個需要解決的問題是，標準EVENODD編碼結構要求條紋長度為p+2，標準RDP編碼結構要求條紋長度為p+1，p為素數。而系統實際配置中，構成一個磁盤陣列top節(jié)點的leaf節(jié)點數可能不是這樣的規(guī)模。而且，ZFS采用寫請求聚合整條紋寫的策略，實際條紋長度還可能小于leaf節(jié)點數。我們可以采取“編碼縮減”技術，來使這兩種陣列碼適應變化的、非素數的條紋長度。即，預先選定一個較大的控制參數p，使p+2（EVENODD）或p+1（RDP）大于可能出現的實際條紋長度。對于ZFS確定的實際條紋長度g（EVENODD：g<=p+2；RDP：g<=p+1），刪除多出的數據單元（假定為全0），顯然，這樣不會影響編碼的容錯能力和編碼/解碼算法。第三，由于編碼上下文的實現要求，第一校驗盤需要作為整個條紋的第一個條紋單元，第二校驗盤需要作為整個條紋的第二個條紋單元。因此實現的時候，也需要在這方面對標準的EVENODD、RDP碼編碼、解碼方式進行相應的調整。綜合考慮到本小節(jié)提到的實現中需要注意的若干問題，以及第二章第五節(jié)提到的編碼實現的技巧，本文將在本章的第四節(jié)和第五節(jié)給出在ZFS上EVENODD和RDP兩種陣列碼（編碼和解碼）的具體實現。對于解碼計算，由于只有一個數據盤數據丟失、只有校驗盤數據丟失、一個數據盤和對角線校驗盤數據丟失這三種情況的解碼實現非常簡單，把類似RAID5的解碼和相應的RAID6編碼過程進行組合即可完成。因此解碼的部分，本文只具體給出一個數據盤行校驗盤數據丟失、兩個數據盤數據丟失這兩種情況的實現。3.4EVENODD碼在ZFS中的實現編碼對圖2-1所示的編碼方案，結合ZFS條紋情況，采用如下的實現策略。圖3-3中每列數據從上到下分為三個部分：第一部分（參與標記為x~p-2的校驗組）需要計算到行校驗列和對角線校驗列中，第二部分（參與標記為p-1的校驗組）需要計算到行校驗列和S中，第三部分（該列的剩余部分）需要計算到行校驗列和對角線校驗列中。并且，陰影區(qū)域不參加計算。最終，再將S計算到對角線校驗列中。編碼完畢。整個過程用偽代碼表示如下：/*算法3-1：EVENODD編碼算法*/packet_size數據塊大小rcountdcount校驗列條紋單元大小r行校驗列的數據首地址d對角線校驗列的數據首地址ccount第一塊數據列的條紋單元大小src第一塊數據列的數據首地址r[0..ccount]d[0..ccount]src[0..ccount]ForcIn3to條紋單元個數-1Dodoffset(c-2)*packet_size ccount當前條紋單元大小 src當前條紋單元數據首地址 i0jdoffsetWhilei<ccountAndj<dcountDo r[i]r[i]Xorsrc[i]d[j]d[j]Xorsrc[i]ii+1jj+1 j0Whilei<ccountAndj<packet_sizeDor[i]r[i]Xorsrc[i]S[j]S[j]Xorsrc[i] ii+1jj+1j0Whilei<ccountDor[i]r[i]Xorsrc[i]d[j]d[j]Xorsrc[i]i0Whilei<dcountDoForjIn0topacket_size–1Dod[i]d[i]XorS[j] ii+1解碼.1數據列x和水平校驗列失效/*算法3-2：EVENODD解碼算法一（數據列x和水平校驗列失效）*/Ifx>2Then使用每個條紋單元，校驗組為x-3的數據塊計算SElse按照編碼的方法直接計算SEndif將S復制到x上每個數據塊，水平校驗列清零將其他數據列，按照相同對角線校驗組，Xor到x上和水平校驗列上將對角線校驗列，按照相同對角線校驗組，Xor到x上將x列水平的Xor到水平校驗列上.2數據列x和數據列y失效/*算法3-3：EVENODD解碼算法二（數據列x和數據列y失效）*/將水平校驗列和對角線校驗列的所有數據塊Xor，計算出Sxdata[0..xcount]r[0..xcount]，將x和y以外的數據列Xor到x上將S復制到y上每個數據塊，將x和y以外的數據列、對角線校驗列，按照相同對角線校驗組，Xor到y上s(x–y-1)modpWhiles!=p-1Do將x上第(s+y–x)modp個數據塊Xor到y上第s個數據塊將y上第s個數據塊Xor到x上第s個數據塊 s(s+y–x)modp3.5RDP碼在ZFS中的實現編碼由于RDP編碼的水平校驗列參與編碼，所以水平校驗列數據塊以怎樣的順序參與對角線校驗列的計算十分重要。為了表示明確，這里給出結合了ZFS條紋情況和圖2-2所示編碼方案，重新設計的數據塊校驗組的分布方法。RowParityDiag.ParityDataDisk0DataDisk1DataDisk2DataDisk3400123011234122340233401圖3-3中每列數據從上到下同樣分為三個部分：第一部分（參與標記為x~p-2的校驗組）需要計算到行校驗列和對角線校驗列中，第二部分（參與標記為p-1的校驗組）只需要計算到行校驗列，第三部分（該列的剩余部分）需要計算到行校驗列和對角線校驗列中。并且，陰影區(qū)域不參加計算。最終，將水平校驗列計算到對角線校驗列中，編碼完畢。整個編碼過程用偽代碼表示如下：/*算法3-4：RDP編碼算法*/packet_size數據塊大小rcountdcount校驗列條紋單元大小r行校驗列的數據首地址d對角線校驗列的數據首地址ccount第一塊數據列的條紋單元大小src第一塊數據列的數據首地址r[0..ccount]d[0..ccount]src[0..ccount]ForcIn3to條紋單元個數-1Dodoffset(c-2)*packet_size ccount當前條紋單元大小 src當前條紋單元數據首地址 i0jdoffsetWhilei<ccountAndj<dcountDo r[i]r[i]Xorsrc[i]d[j]d[j]Xorsrc[i]ii+1jj+1 j0Whilei<ccountAndj<packet_sizeDor[i]r[i]Xorsrc[i] ii+1jj+1 j0Whilei<ccountDor[i]r[i]Xorsrc[i] d[j]d[j]Xorsrc[i]ForiIn0torcount–packet_size d[i]d[i]Xorr[i+packet_size]解碼.1數據列x和水平校驗列失效/*算法3-5：RDP解碼算法一（數據列和水平校驗列失效）*/row_diskp+1diag_diskxgrp–2gx(x-3)modprow_datardatadiag_dataxdataggrSTART:Ifg==p–1ThenIfgr==(row_disk-3)modpThenrow_diskx; diag_diskp+1; row_dataxdata;diag_datardata; ggx;GotoSTARTElse GotoEXITEndifElse 將數據列（diag_disk除外）、對角線校驗列上，對角線校驗組為g的數據塊 Xor到diag_disk上的對角線校驗組為g的數據塊 Ifdiag_disk不是行校驗列Then 行校驗列上對角線校驗組為g的數據塊Xor到diag_disk上的校驗組為g的數據塊上EndIf row_index(g–diag_disk+2)modp 將數據列、行校驗列（row_disk除外）上第row_index個數據塊Xor到row_disk的第row_index個數據塊 g(row_index+row_disk–2)modp GotoSTARTEndifExit:.2數據列x和數據列y失效/*算法3-6：RDP解碼算法二（數據列x和數據列y失效）*/row_diskxdiag_diskygx(x-3)modpgy(y-3)modprow_dataxdatadiag_dataydataggxSTART:Ifg==p–1ThenIfgr==(row_disk-3)modpThenrow_disky; diag_diskx; row_dataydata; diag_dataxdata; ggy; GotoSTARTElseGotoEXITEndifElse 將數據列（diag_disk除外）、對角線校驗列上，對角線校驗組為g的數據塊 Xor到diag_disk上的對角線校驗組為g的數據塊 Ifdiag_disk不是行校驗列Then 行校驗列上對角線校驗組為g的數據塊Xor到diag_disk上的校驗組為g的數據塊上 Endif row_index(g–diag_disk+2)modp 將數據列、行校驗列（row_disk除外）上第row_index個數據塊Xor到row_disk的第row_index個數據塊g(row_index+row_disk–2)modp GotoSTARTEndifExit:3.6使用SSE指令加速編碼過程SSE[17]（StreamingSIMDExtensions）是英特爾在AMD的3DNow!發(fā)布一年之后，在其計算機芯片PentiumIII中引入的指令集。這個指令集增加了對8個128位寄存器XMM0-XMM7的支持，每個寄存器可以存儲4個單精度浮點數。該指令集的第二個版本添加了對64位雙精度浮點數的支持，以及對整型數據的支持。配合128位SSE的執(zhí)行單元，使用SSE指令集可以使處理器在一個頻率周期同時執(zhí)行128位的運算。和每次進行64位字的運算相比，可以明顯提高運算的速度。由于對RAID6的每次寫操作都需要進行校驗字的編碼計算，為了進一步的提高編碼的效率，對于編碼計算中的每次異或操作，都利用SSE指令進行。比如，一個數據列上地址是data的128位數據需要計算到行校驗列地址是h_parity和對角線校驗列地址是d_parity上面，使用SSE原語，過程如下。__m128id,hp,dp; d=_mm_load_si128(data);hp=_mm_load_si128(h_parity);dp=_mm_load_si128(d_parity); hp=_mm_xor_si128(hp,d); dp=_mm_xor_si128(dp,d); _mm_store_si128(h_parity,hp); _mm_store_si128(d_parity,dp);_mm_load_si128用于從內存中取一個128位字，_mm_store_si128用于將一個128位字存到內存中，_mm_xor_si128進行兩個128位字的異或運算[18]。4.實驗驗證4.1實驗環(huán)境具體的實驗環(huán)境如表4-1所示。測試工具采用的是iozone，版本是，測試文件大小3GB。在實驗中，控制參數p取17。表4-1：實驗環(huán)境配置CPUIntel(R)Xeon(TM)3.00GHz×2內存1GB硬盤SAS73.2GB×615KRPM操作系統LinuxRedHatAS5文件系統Zfs-fuse-安裝文件系統之前需要依次安裝一些支持軟件包。表4-2給出了實驗中使用的這些軟件包名稱和版本號。表4-2：支持軟件包名稱版本fusefuse-libsfuse-devellibaiolibaio-develzlib-3.x86_64zlib-devel-3.x86_64scons.d200909194.2正確性驗證論文的工作中，對于編碼、解碼的程序正確性檢測方法如下：使用本地的6個磁盤分區(qū)以及通過2個遠端的磁盤分區(qū)通過NBD虛擬在本地的分區(qū)組建雙容錯（raidz2）存儲池，向其中拷貝文件，計算其MD5。這里使用的測試文件是VMware7的安裝文件，大小512MB。如圖4-1所示。斷開兩個NBD分區(qū)的連接，重新計算其MD5?？梢猿晒τ嬎愠雠c預先計算的MD5值相吻合的結果，說明編碼、解碼正確。如圖4-2所示。4.3性能測試本文提到的3種編碼方案，不同之處僅僅在于校驗計算，從磁盤讀角度看則無任何差異。因此，我們僅測試采用兩種編碼情況下ZFS的寫性能，以此來考察編碼計算性能對系統整體性能的影響。三種RAID6編碼都是使用兩個校驗單元來提供雙容錯數據冗余能力。從理論上分析，采用上述兩種雙容錯編碼的由N個硬盤構成的存儲系統，它的最大I/O性能應該不高于由N-1塊硬盤組成的RAID5系統?？紤]到雙容錯系統的第二塊校驗盤的編碼計算所需時間，雙容錯系統的實際I/O性能應該低于由N-1塊硬盤組成的基于RAID5單容錯系統。圖4-3所示的實驗結果驗證了這一點。我們使用6塊相同型號硬盤，分別基于RS、EVENODD、RDP和RAID5組成存儲系統，并利用iozone來測試系統的寫操作性能。其中，RAID5的寫性能最優(yōu)，利用RS碼的RAID6的寫性能最差，利用EVENODD和RDP碼的RAID6的寫性能在以上二者之間，而且利用RDP碼比利用EVENODD碼的RAID6寫性能稍好一些。此外，圖4-4給出了通過使用SSE指令代替常規(guī)的運算指令，對編碼性能的影響。通過對比使用SSE指令的RDP編碼和使用常規(guī)指令的RDP編碼下系統的寫性能，可以看出，特別是請求大小大于256KB的時候，使用SSE指令能夠明顯加快編碼的速度，從而提升文件系統總體的寫性能。由于使用的ZFS是基于Fuse的版本，程序在用戶態(tài)，需頻繁進出內核，所以總體性能并不是很好。而且用戶態(tài)的程序容易受系統的影響，因而測試結果的波動較大。圖中的每個數據都是進行了幾次測試取平均值的結果。5.總結和展望RAID6的提出，增加了磁盤陣列可靠性，而校驗編碼的效率直接影響著整個RAID6系統的效率。本文從編碼的角度，對RAID6進行了研究。主要工作包括兩方面：一方面，比較Reed-Solomon、EVENODD、RDP這幾種常見的RAID6編碼方式和效率，著重研究新型陣列碼EVENODD、RDP這兩種編碼的算法和利用Cache優(yōu)化的編碼實現技巧。另一方面，對新型文件系統ZFS對存儲設備的組織方式和raidz組件進行了剖析，針對ZFS條紋的特點，在raidz組件上設計并實現了結合了Cache優(yōu)化的EVENODD、RDP碼的編碼、解碼，并且使用SSE指令對編碼過程進行加速。最終，用權威的Benchmark軟件iozone進行了測試：對比不同RAID6碼對整個文件系統的影響，得出采用新型陣列碼EVENODD、RDP替代原有的RS碼實現文件系統的雙容錯，能夠提高系統的寫性能的結論；比較有無使用SSE指令的RDP編碼，得出使用SSE指令可以明顯加快編碼計算的結論。列優(yōu)先編碼的實現方式比行優(yōu)先的方式可以更好的利用Cache，但是由于利用每列數據字做對角線校驗的編碼計算時，對角線校驗列所有數據塊都要依次讀入Cache。當Cache資源較少而條紋單元較長的時候，采用列優(yōu)先的方式可能造成對角線校驗列的數據塊頻繁的進出Cache。另有一種行列優(yōu)先的編碼實現方式，通過犧牲掉一點Cache對數據字的預取節(jié)約的時間，力圖減少對角線校驗字頻繁進出Cache，是行優(yōu)先和列優(yōu)先編碼方式的折衷。對這種實現方式的研究還在進行中，還需要很多參數的調整與實驗工作。另外，對應用更為廣泛的Linux內核磁盤陣列模塊采用類似的技術進行優(yōu)化，也是未來重要的研究內容之一。參考文獻[1]ZDNet存儲頻道.IBM存儲業(yè)務持續(xù)增長創(chuàng)新成為主要動力.2010[2]DavtdAPatterson,GarthGibson,RandyHKatz.AC