【正文】 編碼完畢。并且，陰影區(qū)域不參加計(jì)算。 EVENODD碼在 ZFS 中的實(shí)現(xiàn) 編碼 對(duì)圖 21 所示的編碼方案，結(jié)合 ZFS 條紋情況，采用如下的實(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)行組合即可完成。因此實(shí)現(xiàn)的時(shí)候，也需要在這方面對(duì)標(biāo)準(zhǔn)的 EVENODD、 RDP 碼編碼、解碼方式進(jìn)行相應(yīng)的調(diào)整。對(duì)于 ZFS 確定的實(shí) 際條紋長(zhǎng)度 g（ EVENODD： 21 g=p+2； RDP： g=p+1），刪除 多出的 數(shù)據(jù)單元（假定為全 0），顯然，這樣不會(huì)影響編碼的容錯(cuò)能力和編碼 /解碼算法。我們可以采取“編碼縮減”技術(shù)，來(lái)使這兩種陣列碼適應(yīng)變化的、非素?cái)?shù)的條紋長(zhǎng)度。而系統(tǒng)實(shí)際配置中，構(gòu)成一個(gè)磁盤(pán)陣列 top 節(jié)點(diǎn)的 leaf 節(jié)點(diǎn)數(shù)可能不是這樣的規(guī)模。對(duì)此的解決辦法是，在編碼 /解碼運(yùn)算中，陰影區(qū)域視為全 0，因?yàn)?0 對(duì)異或運(yùn)算 的結(jié)果不會(huì)有任何影響。為了滿(mǎn)足上述處理策略的需求，需要在標(biāo)準(zhǔn) EVENODD和 RDP 編碼結(jié)構(gòu)的基礎(chǔ)上加以變化。對(duì)于校驗(yàn)盤(pán)而言，顯然 應(yīng)該是完整條紋單元大小。上面的源碼中沒(méi)有標(biāo)記含義的變量在圖 33 中均已標(biāo)出。 …… } 20 一種很可能的分布如圖 33。 c acols。 /* 較大條紋單元個(gè)數(shù) */ acols = (q == 0 ? bc : dcols)。 r = s q * (dcols nparity)。 /* 數(shù)據(jù)以 1unit_shift 為單位大小分成單元進(jìn)行散布 */ /* dcols：所屬 top 節(jié)點(diǎn)下面的 leaf 虛設(shè)備的個(gè)數(shù) */ s = zioio_size unit_shift。 ZFS 在請(qǐng)求聚合之后，形成的條紋大?。](méi)算上校驗(yàn)字條紋）為磁盤(pán)扇區(qū)大小（ 512B）的整數(shù)倍，在 512B～ 128KB 之間，并不一定能夠被存放數(shù)據(jù)字的虛設(shè)備個(gè)數(shù)整除。為此， ZFS 采用了可變條紋設(shè)計(jì)。此 外，追加寫(xiě)還可有效解決寫(xiě)操作中系統(tǒng)崩潰造成的不一致問(wèn)題。即新數(shù)據(jù)并不覆蓋舊數(shù)據(jù)，而是寫(xiě)入新分配的磁盤(pán)空間中，而舊數(shù)據(jù)占用的空間會(huì)適時(shí)回收。這樣，多個(gè)寫(xiě)請(qǐng)求的覆蓋地址可能是不連續(xù)的，則無(wú)法組合為整條紋。但這一策略需要解決兩個(gè)問(wèn)題。 針對(duì)傳統(tǒng)磁盤(pán)陣列的這些缺點(diǎn)， ZFS 采用了寫(xiě)請(qǐng)求聚合策略。對(duì)于小數(shù)據(jù)， RMW 策略明顯優(yōu)于重構(gòu)寫(xiě) 19 策略（ Reconstruct Write，讀取不更新的數(shù)據(jù)單元來(lái)和更新數(shù)據(jù)一起計(jì)算出校驗(yàn)單元的新內(nèi)容），但仍然需要 4 次磁盤(pán)操作才能完成一次寫(xiě)請(qǐng)求。如果收到的請(qǐng)求是寫(xiě)操作，或者發(fā)現(xiàn)需要重構(gòu)，那么就調(diào)用底層函數(shù)，將條紋單元中的數(shù)據(jù)實(shí)際寫(xiě)入對(duì)應(yīng)的 leaf 虛設(shè)備上。 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)損壞的情況）。如果是寫(xiě)操作，將調(diào)用處理陣列編碼的函數(shù)，將校驗(yàn)單元寫(xiě)請(qǐng)求發(fā)送給子設(shè)備。 zio 將記錄的數(shù)據(jù)條紋化引用方式傳遞給此 raidz_map 對(duì)象。 /* 條紋單元的句柄 */ } raidz_map_t。 /* 無(wú)效的存放校驗(yàn)字的條紋單元數(shù) */ uint64_t rm_firstdatacol。 /* 條紋大小 */ uint64_t rm_missingdata。 /* 條紋單元個(gè)數(shù) */ uint64_t rm_bigcols。 } raidz_col_t。 /* 發(fā)生的 I/O 錯(cuò)誤數(shù) */ uint8_t rc_tried。 /* 條紋單元大小 */ void *rc_data。 /* 孩子虛設(shè)備下標(biāo) */ uint64_t rc_offset。 raidz_map 描述一個(gè)條紋的信息，包括這個(gè)條紋中的條紋單元個(gè)數(shù)、狀態(tài)、第一塊數(shù)據(jù)盤(pán)在條紋中的下標(biāo)，以及每個(gè)條紋單元的首址。當(dāng)發(fā)生磁盤(pán)故障，校驗(yàn)單元被用來(lái)重構(gòu)出丟失的數(shù)據(jù)單元。當(dāng)寫(xiě)請(qǐng)求到達(dá)， raidz將數(shù)據(jù)劃分為數(shù)據(jù)單元，并采用某種雙容錯(cuò)編碼方案計(jì)算出兩個(gè)校驗(yàn)單元，然后將這些條紋單元（包括數(shù)據(jù)和校驗(yàn)）寫(xiě)入物理虛設(shè)備。如果請(qǐng)求訪問(wèn)的 top 節(jié)點(diǎn)的是 raidz 或者raidz2 類(lèi)型，則由 raidz 組件負(fù)責(zé)請(qǐng)求映射。 raidz 組件剖析 17 在 ZFS 中，任何用戶(hù) I/O 請(qǐng)求都被封裝成為 zio 對(duì)象。用戶(hù)可以執(zhí)行這樣一條命令“ zpool create –f tank raidz /dev/sda5 /dev/sdb5 /dev/sdc5 raidz /dev/sda6 /dev/sdb6 /dev/sdc6”。容錯(cuò)編碼應(yīng)用于 top 層次，即一個(gè)top 的多個(gè)孩子（ leaf 設(shè)備）可組成一個(gè)磁盤(pán)陣列。根節(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è)備。池中所 有設(shè)備都抽象成為虛設(shè)備，組成三個(gè)層次的樹(shù)形結(jié)構(gòu)。實(shí)現(xiàn)容錯(cuò)編碼功能的 raidz 組件，就位于這一層。事務(wù)對(duì)象層集合了數(shù)據(jù)管理單元、快照、屬性處理、意圖日志等的對(duì)象級(jí)別的實(shí)現(xiàn)。 ZFS 的核心部分自上而下大致分為三層：接口層、事務(wù)對(duì)象層、存儲(chǔ)池層。 總體結(jié)構(gòu) ZFS 文件系統(tǒng)整體結(jié)構(gòu)分為用戶(hù)部分和核心部分 [16]。為了在 ZFS 中實(shí)現(xiàn)容錯(cuò)編碼，我們先要對(duì)編碼的上下文，即 raidz 組件，進(jìn)行分析。目前，標(biāo)準(zhǔn)版的 ZFS 只適用于 Solaris 操作系統(tǒng)中，在 Linux 下無(wú)法安裝和使用。 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ù)可靠性。與傳統(tǒng)文件相比，它具有許多革新性的 特點(diǎn)，能夠顯著提高文件系統(tǒng)的管理效率。上一章對(duì)幾種常見(jiàn)的 RAID6 編碼進(jìn)行了討論和分析，這一章將具體的結(jié)合文件系統(tǒng) ZFS，用新型的陣列碼 EVENODD 或 RDP 替換原有的RS 碼，以提升編碼的速度，進(jìn)而優(yōu)化文件系統(tǒng)寫(xiě)操作的性能。 15 3. 高效 RAID6編碼在 ZFS中的實(shí)現(xiàn) 構(gòu)造 RAID 可以采用硬件方法，亦可以采用軟件方法。由于每一列（磁 14 盤(pán)）的數(shù)據(jù)在內(nèi)存中 是連續(xù)的，相比之下，列優(yōu)先的方式可以更好地利用 cache的預(yù)取機(jī)制，掩蓋內(nèi)存至 cache 的延遲， 但需要全部校驗(yàn)單元一直駐留 cache才能獲得最佳性能， 因此當(dāng)條紋單元較小時(shí)具有更好的性能。一種是行優(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 處理完畢，如圖 27 所示。對(duì) RDP 碼，需要注意的是，當(dāng)所有數(shù)據(jù)字處理完畢后，還需訪問(wèn)對(duì)角線(xiàn)校驗(yàn)字所依賴(lài)的水平校驗(yàn)字一次，完成對(duì)角線(xiàn)校驗(yàn)的最終計(jì)算。由于基于奇偶校驗(yàn)的單 /雙容錯(cuò)碼的計(jì)算復(fù)雜性較低，可以認(rèn)為其編碼運(yùn)算是一種數(shù)據(jù)密集型運(yùn)算，因此編碼性能主要取決于訪存性能。 Data Disk 0 Data Disk 1 Data Disk 2 Data Disk 3 Row Parity Diag. Parity 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 圖 25： 以校驗(yàn)字為中心進(jìn)行編碼計(jì)算 Data Disk 0 Data Disk 1 Data Disk 2 Data Disk 3 Row Parity Diag. Parity 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 圖 26： 以數(shù)據(jù)字為中心進(jìn)行編碼計(jì)算（列優(yōu)先） 文獻(xiàn) [13]提出了以數(shù)據(jù)字為中心的策略，即，每讀入一個(gè)數(shù)據(jù)字，將它異或到所屬的兩個(gè)校驗(yàn)字，如圖 26 所示。我們知道，在計(jì)算機(jī)系統(tǒng)中，訪問(wèn)內(nèi)存數(shù)據(jù)時(shí)，首先會(huì)將數(shù)據(jù)讀入 cache，然后才會(huì)由 CPU 進(jìn)行處理。但在單容錯(cuò)系統(tǒng)中，每個(gè)數(shù)據(jù)字都只參與一個(gè)校驗(yàn)組，在編碼計(jì)算過(guò)程中只被訪問(wèn)一次。 以校驗(yàn)字為中心還是以數(shù)據(jù)字為中心 對(duì)于單容錯(cuò)的奇偶校驗(yàn)碼（ RAID4/5），編碼計(jì)算直接將數(shù)據(jù)字進(jìn)行異或運(yùn)算，即可得到校驗(yàn)字。在 Linux 內(nèi)核和 ZFS 中都已經(jīng)得到了很好的實(shí)現(xiàn)。其主要思想，是把 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ì)算。因此盡管 RS 碼的編碼復(fù)雜度高于 EVENODD 以及 RDP，依然占有很重要的地位。 值得一提的是，由于 RS 碼歷史最長(zhǎng)，使用非常廣泛，比如在 Linux 內(nèi)核 12 中的 RAID6 編碼就是用的 RS 碼。 對(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)。因而從理論上，對(duì)于全條 紋的覆寫(xiě)， RDP 碼的編碼計(jì)算復(fù)雜度會(huì)稍低于 EVENODD 碼。 EVENODD 碼和 RDP 碼都是基于異或操作的陣列碼，復(fù)雜度比 RS 碼要小很多。 第二 ，從計(jì)算的復(fù)雜度上對(duì)這三種存儲(chǔ)編碼方式進(jìn)行比較。 第一 ，從冗余度上對(duì)這三種存儲(chǔ)編碼方式進(jìn)行比較。磁盤(pán) 2 和磁盤(pán) 3 在該條紋中的 所有數(shù)據(jù)均被恢復(fù)。此時(shí)，利用對(duì)角線(xiàn)校驗(yàn)數(shù)據(jù)恢復(fù)packet[3,3]，再利用行校驗(yàn)數(shù)據(jù)恢復(fù) packet[3,2]。首先利用對(duì)角線(xiàn)校驗(yàn)數(shù)據(jù)恢復(fù) packet[0,2]，利用行校驗(yàn)數(shù)據(jù)恢復(fù) packet[0,3]。此時(shí)，重構(gòu)完畢。首先使用對(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ì)于這兩種情況，重構(gòu)的方法是相同的。 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 o d , 0 , 1 , ... 2 )pjjip a c k e t i p p a c k e t k j k i j p p i p????? ? ? ? ? ?? （ ） 解碼 對(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)似，這里不再贅述。和EVENODD 碼類(lèi)似，圖 23 依然表示的是一個(gè)編碼周期，而并不是把 packet 實(shí)現(xiàn)為條紋單元。圖 23 給出了 p=5的時(shí)候，由 6 個(gè)磁盤(pán)組成的 RDP 陣列 的示意圖，每個(gè)塊用一個(gè)數(shù)字表示所屬的對(duì)角線(xiàn)校驗(yàn)組。 編碼 標(biāo)準(zhǔn)的 RDP 碼由 p+1 個(gè)磁盤(pán)組成（ p 稱(chēng)為控制參數(shù)，并且必須是素?cái)?shù)）， 10 其中 p 個(gè)磁盤(pán)是數(shù)據(jù)盤(pán)，另兩個(gè)為校驗(yàn)盤(pán)。由于 RDP 碼沒(méi)有類(lèi)似 EVENODD 碼中S 的計(jì)算，因此計(jì)算復(fù)雜度要稍微低于 EVENODD 碼。與 EVENODD 碼類(lèi)似的是， RDP 碼也使用兩個(gè)校驗(yàn)盤(pán)存放冗余信息，一塊是行校驗(yàn)盤(pán)，另一塊是對(duì)角線(xiàn)校驗(yàn)盤(pán)。首先計(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ù)。 x 磁盤(pán)利用對(duì)角線(xiàn)校驗(yàn)組進(jìn)行恢復(fù)， y磁盤(pán)利用行校驗(yàn)組進(jìn)行恢復(fù)，整個(gè)過(guò)程是一個(gè)迭代的過(guò)程。由式 。 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)，由式 。記丟失數(shù)據(jù)盤(pán)是第 x 塊。上述情況比較簡(jiǎn)單，下面著重討論兩種比較復(fù)雜的情況，一種是一塊數(shù)據(jù)盤(pán)和行校驗(yàn)盤(pán)同時(shí)發(fā)生數(shù)據(jù)丟失，另一種是兩塊數(shù)據(jù)盤(pán)發(fā)生了數(shù)據(jù)丟失。如果僅有校驗(yàn)盤(pán)數(shù)據(jù)丟失，那么重新編碼計(jì)算即可。從計(jì)算角度，并不會(huì)提高編碼的計(jì)算復(fù)雜度。即一個(gè)條紋單元的更新一般會(huì)導(dǎo)致 2 個(gè)校驗(yàn)單元更新。在實(shí)際系統(tǒng)中，磁盤(pán)布局為此周期的重復(fù)。這便是 EVENODD 碼名稱(chēng)的由來(lái) 。 8 20[ ,