一種多磁盤毀損恢復數(shù)據(jù)策略

薛 東，嚴 雪，馮凱平

（四川旅游學院 信息技術系，四川 成都 610100）

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

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

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

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

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

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

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

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

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

2.1 建立冗余表

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

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

2）冗余盤的每一列僅有一個1；

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

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

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

表2 冗余碼Tab.2 Redundant code

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

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

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

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

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

海明距離指兩個相同位數(shù)的二進制代碼對應位不相同的個數(shù)。

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

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

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

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

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

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

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

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

對應位求異或后得到：

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

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

事實上，最初也可以利用表2第六行首先恢復3號盤數(shù)據(jù)。因為在此行上2、3、7號盤中僅有3號盤的冗余碼為1，再通過表3利用1、8、14號盤中的數(shù)據(jù)即可恢復3號盤中的數(shù)據(jù)。當3號盤數(shù)據(jù)被恢復后，再根據(jù)第三行冗余碼對2號盤恢復數(shù)據(jù)，最后現(xiàn)利用第二或第五行對7號盤恢復數(shù)據(jù)。

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

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

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

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

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

3 一種改進的冗余盤配置方案

3.1 冗余表規(guī)則

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

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

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

表5 改進型冗余碼方案Tab.5 Improved redundancy scheme

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

3.2 優(yōu)劣比較

1）磁盤利用率

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

2）運算復雜度

表2每行有4個1，對任何一個盤的寫操作均要對冗余盤進行改寫，改寫的過程需要進行3組次的異或運算（用符號“⊕”表示異或運算）。

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

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

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

4 均衡性配置

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

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

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

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

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

當F分別取1、15、29、43、…等數(shù)字時C＝1，是對1號盤操作。

其他情況類推。

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

5 過程分析

5.1 磁盤寫概率

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

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

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

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

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

5.2 異或過程

完成一次異或操作需要經過許多步驟。

假設A、B分別是一位的二進制碼， 和 分別是A、B的非，A、B的異或操作完成以下動作：

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

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

6 結束語

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

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

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

[2]董歡慶,李戰(zhàn)懷,林偉. RAID-VCR：一種能夠承受三個磁盤故障的raid結構[J].計算機學報.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ù)恢復與硬盤修理[M].北京:電子工業(yè)出版社,2012.

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

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

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