薛 東，嚴(yán) 雪，馮凱平

（四川旅游學(xué)院 信息技術(shù)系，四川 成都 610100）

服務(wù)器上的數(shù)據(jù)應(yīng)當(dāng)具備極高的安全系數(shù)，而這些數(shù)據(jù)的保護(hù)工作可以通過硬盤的冗余技術(shù)來實(shí)現(xiàn)，在以往的配置過程中是依據(jù)數(shù)據(jù)的安全級(jí)別和當(dāng)前服務(wù)器硬件配置兩個(gè)條件來選擇冗余技術(shù)的級(jí)別，從最簡單的RAID0到RAID1，從中級(jí)冗余技術(shù)RAID3到RAID5。然而即使是通過3塊以上硬盤建立的RAID5磁盤陣列也不能百分之百保證數(shù)據(jù)安全，當(dāng)其中同時(shí)有兩塊硬盤出現(xiàn)故障時(shí)仍有部分?jǐn)?shù)據(jù)不能被恢復(fù)[1]。因此，為了提高數(shù)據(jù)的安全級(jí)別，保證工作硬盤在同時(shí)損壞兩塊或更多塊的情況下均能正確進(jìn)行數(shù)據(jù)恢復(fù)，本文以RAID6技術(shù)為基礎(chǔ)，設(shè)計(jì)了一種三磁盤同時(shí)毀損時(shí)的數(shù)據(jù)恢復(fù)策略

1 基于RAID5單盤崩潰數(shù)據(jù)恢復(fù)策略

RAID5允許一個(gè)磁盤毀損并恢復(fù)其數(shù)據(jù)。

RAID5采用計(jì)算異或 (XOR) 的方式來實(shí)現(xiàn)容錯(cuò)，對(duì)于所存儲(chǔ)的數(shù)據(jù)計(jì)算校驗(yàn)[2-3]。如表1，列出了一個(gè)三數(shù)據(jù)盤的存儲(chǔ)系統(tǒng)。磁盤1、2、3為數(shù)據(jù)盤，盤4為冗余盤，它的內(nèi)容由3個(gè)數(shù)據(jù)盤相應(yīng)位的異或值決定，即P4 =P1⊕P2⊕P3。

因此，當(dāng)其中一個(gè)存儲(chǔ)設(shè)備出現(xiàn)故障，則可以通過計(jì)算異或，得到相對(duì)應(yīng)的數(shù)據(jù)，比如2號(hào)盤出現(xiàn)故障，可以采用P2＝P1⊕P3⊕P4進(jìn)行恢復(fù)。

表1 RAID5冗余表Tab.1 Redundance table of RAID 5

對(duì)于RAID5，如果由N個(gè)存儲(chǔ)設(shè)備組成，由于要保存額外的校驗(yàn)數(shù)據(jù)，那么其存儲(chǔ)空間利用率為：(N-1)/N＝1-1/N

在此，數(shù)據(jù)盤數(shù)量為3，冗余盤數(shù)量為1。

2 三磁盤崩潰數(shù)據(jù)恢復(fù)策略

2.1 建立冗余表

假設(shè)系統(tǒng)包含14個(gè)磁盤，其中數(shù)據(jù)盤數(shù)量為8，編號(hào)為1、2、…8。冗余盤數(shù)量為6，編號(hào)9、10、…14。建立如表2的冗余碼表，它有如下特征：

1）每一列均有1，且每一列均不相同；

2）冗余盤的每一列僅有一個(gè)1；

3）數(shù)據(jù)盤中的每一行均為奇數(shù)個(gè)1，且每一行均不相同；

4）數(shù)據(jù)盤中的每一列至少兩個(gè)1；

表2中冗余盤中的1是對(duì)應(yīng)該行數(shù)據(jù)盤中1的異或值，其中9號(hào)盤在第一行上有1，而在第一行上對(duì)應(yīng)的4、5、8號(hào)盤的冗余碼為1，因此，9號(hào)盤是4、5、8號(hào)盤的異或值；同理，10號(hào)盤在第二行上有1，它是3、5、7號(hào)盤的異或值；11-14號(hào)盤的冗余碼同樣推理。

表2 冗余碼Tab.2 Redundant code

2.2 冗余盤數(shù)據(jù)規(guī)則

假設(shè)8個(gè)數(shù)據(jù)盤中的相同位置某一數(shù)據(jù)塊分別有如表3所示的隨機(jī)代碼。根據(jù)此8個(gè)數(shù)據(jù)盤已有數(shù)據(jù)，按表2修改6個(gè)冗余盤的數(shù)據(jù)，如表4。其中9號(hào)盤是4、5、8號(hào)盤對(duì)應(yīng)位為1的異或值；10號(hào)盤是3、5、7號(hào)盤對(duì)應(yīng)位1的異或值，等等。

表3 數(shù)據(jù)盤數(shù)據(jù)Tab.3 Data in data disc

表4 冗余盤數(shù)據(jù)Tab.4 Data in redundant disc

2.3 基于海明碼的磁盤恢復(fù)數(shù)目規(guī)則

海明距離指兩個(gè)相同位數(shù)的二進(jìn)制代碼對(duì)應(yīng)位不相同的個(gè)數(shù)。

對(duì)于表2的六行二進(jìn)制代碼，組成長度為14的位向量，所有位向量相互之間的最小海明距離為HS=4，因此，基于表2的代碼方案可以解決HS -1＝3個(gè)磁盤的同時(shí)損毀問題[3]。

2.4 寫數(shù)據(jù)

對(duì)數(shù)據(jù)盤的寫操作是隨時(shí)都有可能進(jìn)行的。當(dāng)對(duì)數(shù)據(jù)盤重新寫數(shù)據(jù)后，相對(duì)應(yīng)的冗余盤代碼必須隨之改變。設(shè)1號(hào)數(shù)據(jù)盤某數(shù)據(jù)塊變?yōu)?0101101，查表2 可知，與1號(hào)磁盤對(duì)應(yīng)的冗余盤有12號(hào)盤和14號(hào)盤，其中，12號(hào)盤的相應(yīng)數(shù)據(jù)塊的數(shù)據(jù)將根據(jù)1、5、6號(hào)盤的異或計(jì)算變?yōu)?0111001；而14號(hào)盤則根據(jù)1、3、8號(hào)盤的數(shù)據(jù)改變?yōu)?1110010。

如果5號(hào)數(shù)據(jù)盤被改寫，將涉及9、10、11、12號(hào)等4個(gè)冗余盤的改變。

2.5 3個(gè)磁盤同時(shí)崩潰后的數(shù)據(jù)恢復(fù)

任何三個(gè)磁盤損壞后，均可通過查詢表2進(jìn)行數(shù)據(jù)恢復(fù)。

假如2、3、7號(hào)盤同時(shí)損壞，由表2查詢可知，在冗余碼中的第三行，2、3、7號(hào)盤的冗余碼分別為1、0、0，3個(gè)盤的冗余碼中僅有一個(gè)1，而在該行上，2、5、6、11 4個(gè)盤互為異或，在這4個(gè)盤中，只有2號(hào)盤損毀，它完全可以利用5、6、11號(hào)盤的數(shù)據(jù)對(duì)其進(jìn)行恢復(fù)。

將表3中5、6、11號(hào)盤的數(shù)據(jù)重寫如下：

對(duì)應(yīng)位求異或后得到：

2號(hào)盤恢復(fù)后，將對(duì)3、7號(hào)盤進(jìn)行恢復(fù)。從表2中可見，第五行3號(hào)盤與7號(hào)盤的冗余碼不同，且7號(hào)盤冗余碼為1，因此可以利用第五行先恢復(fù)7號(hào)盤數(shù)據(jù)。第五行2、4、7、13 4個(gè)盤互為冗余，其中僅有7號(hào)盤損毀，可以利用2、4、13 3個(gè)盤進(jìn)行異或運(yùn)算對(duì)其進(jìn)行數(shù)據(jù)恢復(fù)。

最后，再利用表2中第二行的第5、7、10號(hào)冗余碼對(duì)3號(hào)盤進(jìn)行數(shù)據(jù)恢復(fù)。

事實(shí)上，最初也可以利用表2第六行首先恢復(fù)3號(hào)盤數(shù)據(jù)。因?yàn)樵诖诵猩?、3、7號(hào)盤中僅有3號(hào)盤的冗余碼為1，再通過表3利用1、8、14號(hào)盤中的數(shù)據(jù)即可恢復(fù)3號(hào)盤中的數(shù)據(jù)。當(dāng)3號(hào)盤數(shù)據(jù)被恢復(fù)后，再根據(jù)第三行冗余碼對(duì)2號(hào)盤恢復(fù)數(shù)據(jù)，最后現(xiàn)利用第二或第五行對(duì)7號(hào)盤恢復(fù)數(shù)據(jù)。

下列情形會(huì)影響數(shù)據(jù)恢復(fù)操作：

1）如果表2中的某兩列代碼相同，比如第2、3列相同，此時(shí)假如恰好2、3號(hào)盤同時(shí)損毀，由于無法找到2、3列代碼的不同點(diǎn)，致使無法進(jìn)行數(shù)據(jù)恢復(fù)。由此可以推論，如果數(shù)據(jù)盤冗余表中的某一列僅有一個(gè)1，比如第1列僅在第4行有1，則將與第12號(hào)盤的冗余碼相同，當(dāng)1、12號(hào)盤同時(shí)損壞時(shí)則無法進(jìn)行數(shù)據(jù)恢復(fù)。

2）如果表2中的某一列完全為0，比如第1列全為0，由于它無法與其他任何一個(gè)盤發(fā)生冗余，當(dāng)出現(xiàn)1號(hào)盤損毀時(shí)，無法對(duì)其進(jìn)行數(shù)據(jù)恢復(fù)。

此例列舉的實(shí)例中，3個(gè)盤均為數(shù)據(jù)盤。如果損壞盤中包含冗余盤，或者損壞的3個(gè)盤均為冗余盤，其數(shù)據(jù)恢復(fù)方法相同，只要能保證冗余表中3個(gè)損壞盤的冗余碼僅有一個(gè)為1而其余兩個(gè)為0即可。

表2擁有8個(gè)數(shù)據(jù)盤，而其中3個(gè)數(shù)據(jù)盤同時(shí)損壞的情況共有56種組合情形。表2所列0、1序列可以對(duì)56種所有可能損壞的盤序進(jìn)行數(shù)據(jù)恢復(fù)。

3 一種改進(jìn)的冗余盤配置方案

3.1 冗余表規(guī)則

表2共有14個(gè)磁盤，其中數(shù)據(jù)盤8個(gè)，冗余盤6個(gè)。改進(jìn)后的冗余表如表5。它共有13個(gè)盤，數(shù)據(jù)盤仍為8個(gè)，冗余盤減少為5個(gè)。

表5除了具有表2的基本特征外，它的另一個(gè)特征是數(shù)據(jù)盤冗余碼的對(duì)稱性。表2中，第一行與第四行互補(bǔ)、第二行與第三行互補(bǔ)、第五行自對(duì)稱。

根據(jù)此原理，表6（a）、（b）給出了另外兩種數(shù)據(jù)盤冗余碼方案，也可以實(shí)現(xiàn)解決所有3個(gè)磁盤損毀的問題。

表5 改進(jìn)型冗余碼方案Tab.5 Improved redundancy scheme

表6 另兩種冗余碼方案Tab.6 The other two redundancy schemes

3.2 優(yōu)劣比較

1）磁盤利用率

表5對(duì)應(yīng)的13盤方案磁盤利用率為（13-5）/13=0.62；表2的14盤方案利用率為（14-6）/14=0.57。因此，在存儲(chǔ)空間利用率方面13盤方案有優(yōu)勢，并且在系統(tǒng)組織方面結(jié)構(gòu)相對(duì)簡單[4]。

2）運(yùn)算復(fù)雜度

表2每行有4個(gè)1，對(duì)任何一個(gè)盤的寫操作均要對(duì)冗余盤進(jìn)行改寫，改寫的過程需要進(jìn)行3組次的異或運(yùn)算（用符號(hào)“⊕”表示異或運(yùn)算）。

以8號(hào)盤被寫操作為例，并且假定每個(gè)數(shù)據(jù)塊大小為8位：

觀察表2，8號(hào)盤被寫將涉及第1行的9號(hào)冗余盤和第6行的第14號(hào)冗余的改寫，對(duì)于第1行，P(9)=P(4)⊕P(5)⊕P(8)；對(duì)于第6行，P(14)=P(1)⊕P(2)⊕P(8)。共需要進(jìn)行6塊48位讀操作、4組共32次異或運(yùn)算、2塊16位寫操作，觀察表5，8號(hào)盤被寫將涉及第2行的10號(hào)冗余盤和第4行的第12號(hào)冗余的改寫，對(duì)于第2行，P(10)=P(3)⊕P(4)⊕P(7)⊕P(8)；對(duì)于第4行，P(12)=P(2)⊕P(4)⊕P(6)⊕P(8)。共需要進(jìn)行8塊64位讀操作、6組共48次異或運(yùn)算、2塊16位寫操作。

表2所確定的冗余方案其查表時(shí)間更少、過程較表5方案簡單，中大型數(shù)據(jù)中心數(shù)據(jù)的吞吐量和計(jì)算量非常大，且過程頻繁，選擇此方案較為合適。而表5所確定的方案更加適合圖書館、校園網(wǎng)等數(shù)據(jù)流量相對(duì)較小同時(shí)對(duì)成本有一定要求的環(huán)境中。

4 均衡性配置

以上操作中，任何一個(gè)數(shù)據(jù)盤中數(shù)據(jù)的改變均要涉及兩個(gè)以上冗余盤的讀寫，因此，冗余盤的工作負(fù)荷要遠(yuǎn)遠(yuǎn)大于數(shù)據(jù)盤。

事實(shí)上，無論是數(shù)據(jù)盤還是冗余盤，它們之間都是互為異或的[3,5]。因此，為了保持所有磁盤工作強(qiáng)度的均衡性，可將冗余盤所有存儲(chǔ)空間按一定規(guī)則均勻分布到全部磁盤中[6]。

以14個(gè)磁盤配置方案為例，將14個(gè)磁盤分別命名為n=0、1、2、…13號(hào)，設(shè)F為某一個(gè)磁盤的冗余柱面，F(xiàn)除以14取余數(shù)C，C則表示某一數(shù)據(jù)盤的盤號(hào)，即[3,7]：

圖1 磁盤均衡性配置Fig. 1 Disk equilibrium configuration

當(dāng)F分別取0、14、28、42、…等數(shù)字作為磁盤柱面編號(hào)時(shí)，余數(shù)C=0，因此，0、14、28、42等柱面將作為0號(hào)盤的基礎(chǔ)柱面。然后在基礎(chǔ)柱面之上加9并上推5（冗余盤個(gè)數(shù)減一）個(gè)柱面即n+9、n+10、n+11、n+12、n+13，這樣，對(duì)于n=0的基柱面，與9、10、11、12、13共6個(gè)柱面作為0號(hào)盤的第一組冗余塊。

當(dāng)F分別取1、15、29、43、…等數(shù)字時(shí)C＝1，是對(duì)1號(hào)盤操作。

其他情況類推。

由于每次寫數(shù)據(jù)要計(jì)算取余操作，所以磁盤被均勻分配后，對(duì)磁盤的保護(hù)有利，但額外增加了CPU的計(jì)算負(fù)擔(dān)。

5 過程分析

5.1 磁盤寫概率

觀察表2，如果1號(hào)盤被寫，12、14號(hào)盤將同時(shí)被改寫，3個(gè)盤的寫盤概率為1/8+2/6；同理，2、3、4、6、7、8號(hào)盤被寫，分別涉及3個(gè)盤被寫，寫盤概率分別為1/8+2/6；只有5號(hào)盤被寫時(shí)，9、10、11、12號(hào)4個(gè)盤同時(shí)被寫，此時(shí)的寫盤概率為1/8+4/6。

全部磁盤總的寫盤概率為：

平均每個(gè)盤的寫概率為4/14=0.286。

對(duì)于表5，用同樣的計(jì)算方法得到總的寫概率為5，平均每個(gè)盤的寫概率為5/13＝0.385。

從寫概率來看，14盤方案要優(yōu)于13盤方案。

5.2 異或過程

完成一次異或操作需要經(jīng)過許多步驟。

假設(shè)A、B分別是一位的二進(jìn)制碼， 和 分別是A、B的非，A、B的異或操作完成以下動(dòng)作：

首先求A和B的“非”，再求兩次“與”，再求一次“或”。一次寫操作涉及多少個(gè)位就會(huì)有多少次異或操作，過程漫長，占用較多的CPU時(shí)間周期。

因此，在計(jì)算校驗(yàn)過程上，鏡像式數(shù)據(jù)備份方式優(yōu)于冗余式備份方式[7]。

6 結(jié)束語

在數(shù)據(jù)量爆漲的今天，數(shù)據(jù)中心的磁盤數(shù)量迅猛增長，多磁盤同時(shí)崩潰的可能性越來越大。目前有的數(shù)據(jù)中心布署了上萬塊磁盤。據(jù)研究表明，當(dāng)一個(gè)磁盤損壞后，其他磁盤損壞的概率將會(huì)上升[2]。對(duì)于布置了1500塊磁盤的中型數(shù)據(jù)中心，同時(shí)出現(xiàn)三個(gè)盤同時(shí)崩潰的概率為100年，此概率非常高，特別當(dāng)發(fā)生如火災(zāi)、數(shù)據(jù)庫節(jié)點(diǎn)爆炸、病毒侵害等災(zāi)難時(shí)，這種多磁盤同時(shí)崩潰的可能性更大。本文通過實(shí)例，給出了一種三個(gè)磁盤同時(shí)崩潰后的數(shù)據(jù)恢復(fù)策略，以供探討。

作為本例，在實(shí)際應(yīng)用過程中，可以將每13或14個(gè)磁盤劃分為一組，就可以對(duì)存儲(chǔ)系統(tǒng)中所有磁盤進(jìn)行三磁盤損壞的數(shù)據(jù)恢復(fù)。

[1]汪中夏,張京生,劉偉.RAID數(shù)據(jù)恢復(fù)技術(shù)揭秘[M].北京:清華大學(xué)出版社.2010.

[2]董歡慶,李戰(zhàn)懷,林偉. RAID-VCR：一種能夠承受三個(gè)磁盤故障的raid結(jié)構(gòu)[J].計(jì)算機(jī)學(xué)報(bào).2006,29(5),792-800.

DONG Huan-qing,LI Zhan-huai,LIN Wen.RAID-VCR:A new RAID architecture for Tolerating triple disk failures[J].Chinese Journal of Computers, 2006, 29(5): 792-800.

[3]Hector Garcia-Molina,Jeffrey D.Ullman,Jennifer Widom.Database System Implementation[M]. Palo Alto, California:StanfordUniversity,2010.

[4]戴士劍.數(shù)據(jù)恢復(fù)與硬盤修理[M].北京:電子工業(yè)出版社,2012.

[5]劉偉.數(shù)據(jù)恢復(fù)技術(shù)深度揭秘[M].北京:電子工業(yè)出版社,2010.

[6]張京生,汪中夏,劉偉.數(shù)據(jù)恢復(fù)方法及案例分析[M].北京:電子工業(yè)出版社, 2008.

[7]Amteam.解析RAID6:最新的冗余技術(shù)[EB/OL].(2006-10-07) [2012-07].http://www. vsharing.com.