計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)畢業(yè)設(shè)計(jì)存儲(chǔ)編碼高效算法的實(shí)現(xiàn)

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