一种多磁盘毁损恢复数据策略

薛 东，严 雪，冯凯平

（四川旅游学院 信息技术系，四川 成都 610100）

服务器上的数据应当具备极高的安全系数，而这些数据的保护工作可以通过硬盘的冗余技术来实现，在以往的配置过程中是依据数据的安全级别和当前服务器硬件配置两个条件来选择冗余技术的级别，从最简单的RAID0到RAID1，从中级冗余技术RAID3到RAID5。然而即使是通过3块以上硬盘建立的RAID5磁盘阵列也不能百分之百保证数据安全，当其中同时有两块硬盘出现故障时仍有部分数据不能被恢复[1]。因此，为了提高数据的安全级别，保证工作硬盘在同时损坏两块或更多块的情况下均能正确进行数据恢复，本文以RAID6技术为基础，设计了一种三磁盘同时毁损时的数据恢复策略

1 基于RAID5单盘崩溃数据恢复策略

RAID5允许一个磁盘毁损并恢复其数据。

RAID5采用计算异或 (XOR) 的方式来实现容错，对于所存储的数据计算校验[2-3]。如表1，列出了一个三数据盘的存储系统。磁盘1、2、3为数据盘，盘4为冗余盘，它的内容由3个数据盘相应位的异或值决定，即P4 =P1⊕P2⊕P3。

因此，当其中一个存储设备出现故障，则可以通过计算异或，得到相对应的数据，比如2号盘出现故障，可以采用P2＝P1⊕P3⊕P4进行恢复。

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

对于RAID5，如果由N个存储设备组成，由于要保存额外的校验数据，那么其存储空间利用率为：(N-1)/N＝1-1/N

在此，数据盘数量为3，冗余盘数量为1。

2 三磁盘崩溃数据恢复策略

2.1 建立冗余表

假设系统包含14个磁盘，其中数据盘数量为8，编号为1、2、…8。冗余盘数量为6，编号9、10、…14。建立如表2的冗余码表，它有如下特征：

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

2）冗余盘的每一列仅有一个1；

3）数据盘中的每一行均为奇数个1，且每一行均不相同；

4）数据盘中的每一列至少两个1；

表2中冗余盘中的1是对应该行数据盘中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 冗余盘数据规则

假设8个数据盘中的相同位置某一数据块分别有如表3所示的随机代码。根据此8个数据盘已有数据，按表2修改6个冗余盘的数据，如表4。其中9号盘是4、5、8号盘对应位为1的异或值；10号盘是3、5、7号盘对应位1的异或值，等等。

表3 数据盘数据Tab.3 Data in data disc

表4 冗余盘数据Tab.4 Data in redundant disc

2.3 基于海明码的磁盘恢复数目规则

海明距离指两个相同位数的二进制代码对应位不相同的个数。

对于表2的六行二进制代码，组成长度为14的位向量，所有位向量相互之间的最小海明距离为HS=4，因此，基于表2的代码方案可以解决HS -1＝3个磁盘的同时损毁问题[3]。

2.4 写数据

对数据盘的写操作是随时都有可能进行的。当对数据盘重新写数据后，相对应的冗余盘代码必须随之改变。设1号数据盘某数据块变为00101101，查表2 可知，与1号磁盘对应的冗余盘有12号盘和14号盘，其中，12号盘的相应数据块的数据将根据1、5、6号盘的异或计算变为10111001；而14号盘则根据1、3、8号盘的数据改变为01110010。

如果5号数据盘被改写，将涉及9、10、11、12号等4个冗余盘的改变。

2.5 3个磁盘同时崩溃后的数据恢复

任何三个磁盘损坏后，均可通过查询表2进行数据恢复。

假如2、3、7号盘同时损坏，由表2查询可知，在冗余码中的第三行，2、3、7号盘的冗余码分别为1、0、0，3个盘的冗余码中仅有一个1，而在该行上，2、5、6、11 4个盘互为异或，在这4个盘中，只有2号盘损毁，它完全可以利用5、6、11号盘的数据对其进行恢复。

将表3中5、6、11号盘的数据重写如下：

对应位求异或后得到：

2号盘恢复后，将对3、7号盘进行恢复。从表2中可见，第五行3号盘与7号盘的冗余码不同，且7号盘冗余码为1，因此可以利用第五行先恢复7号盘数据。第五行2、4、7、13 4个盘互为冗余，其中仅有7号盘损毁，可以利用2、4、13 3个盘进行异或运算对其进行数据恢复。

最后，再利用表2中第二行的第5、7、10号冗余码对3号盘进行数据恢复。

事实上，最初也可以利用表2第六行首先恢复3号盘数据。因为在此行上2、3、7号盘中仅有3号盘的冗余码为1，再通过表3利用1、8、14号盘中的数据即可恢复3号盘中的数据。当3号盘数据被恢复后，再根据第三行冗余码对2号盘恢复数据，最后现利用第二或第五行对7号盘恢复数据。

下列情形会影响数据恢复操作：

1）如果表2中的某两列代码相同，比如第2、3列相同，此时假如恰好2、3号盘同时损毁，由于无法找到2、3列代码的不同点，致使无法进行数据恢复。由此可以推论，如果数据盘冗余表中的某一列仅有一个1，比如第1列仅在第4行有1，则将与第12号盘的冗余码相同，当1、12号盘同时损坏时则无法进行数据恢复。

2）如果表2中的某一列完全为0，比如第1列全为0，由于它无法与其他任何一个盘发生冗余，当出现1号盘损毁时，无法对其进行数据恢复。

此例列举的实例中，3个盘均为数据盘。如果损坏盘中包含冗余盘，或者损坏的3个盘均为冗余盘，其数据恢复方法相同，只要能保证冗余表中3个损坏盘的冗余码仅有一个为1而其余两个为0即可。

表2拥有8个数据盘，而其中3个数据盘同时损坏的情况共有56种组合情形。表2所列0、1序列可以对56种所有可能损坏的盘序进行数据恢复。

3 一种改进的冗余盘配置方案

3.1 冗余表规则

表2共有14个磁盘，其中数据盘8个，冗余盘6个。改进后的冗余表如表5。它共有13个盘，数据盘仍为8个，冗余盘减少为5个。

表5除了具有表2的基本特征外，它的另一个特征是数据盘冗余码的对称性。表2中，第一行与第四行互补、第二行与第三行互补、第五行自对称。

根据此原理，表6（a）、（b）给出了另外两种数据盘冗余码方案，也可以实现解决所有3个磁盘损毁的问题。

表5 改进型冗余码方案Tab.5 Improved redundancy scheme

表6 另两种冗余码方案Tab.6 The other two redundancy schemes

3.2 优劣比较

1）磁盘利用率

表5对应的13盘方案磁盘利用率为（13-5）/13=0.62；表2的14盘方案利用率为（14-6）/14=0.57。因此，在存储空间利用率方面13盘方案有优势，并且在系统组织方面结构相对简单[4]。

2）运算复杂度

表2每行有4个1，对任何一个盘的写操作均要对冗余盘进行改写，改写的过程需要进行3组次的异或运算（用符号“⊕”表示异或运算）。

以8号盘被写操作为例，并且假定每个数据块大小为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方案简单，中大型数据中心数据的吞吐量和计算量非常大，且过程频繁，选择此方案较为合适。而表5所确定的方案更加适合图书馆、校园网等数据流量相对较小同时对成本有一定要求的环境中。

4 均衡性配置

以上操作中，任何一个数据盘中数据的改变均要涉及两个以上冗余盘的读写，因此，冗余盘的工作负荷要远远大于数据盘。

事实上，无论是数据盘还是冗余盘，它们之间都是互为异或的[3,5]。因此，为了保持所有磁盘工作强度的均衡性，可将冗余盘所有存储空间按一定规则均匀分布到全部磁盘中[6]。

以14个磁盘配置方案为例，将14个磁盘分别命名为n=0、1、2、…13号，设F为某一个磁盘的冗余柱面，F除以14取余数C，C则表示某一数据盘的盘号，即[3,7]：

图1 磁盘均衡性配置Fig. 1 Disk equilibrium configuration

当F分别取0、14、28、42、…等数字作为磁盘柱面编号时，余数C=0，因此，0、14、28、42等柱面将作为0号盘的基础柱面。然后在基础柱面之上加9并上推5（冗余盘个数减一）个柱面即n+9、n+10、n+11、n+12、n+13，这样，对于n=0的基柱面，与9、10、11、12、13共6个柱面作为0号盘的第一组冗余块。

当F分别取1、15、29、43、…等数字时C＝1，是对1号盘操作。

其他情况类推。

由于每次写数据要计算取余操作，所以磁盘被均匀分配后，对磁盘的保护有利，但额外增加了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盘方案要优于13盘方案。

5.2 异或过程

完成一次异或操作需要经过许多步骤。

假设A、B分别是一位的二进制码， 和 分别是A、B的非，A、B的异或操作完成以下动作：

首先求A和B的“非”，再求两次“与”，再求一次“或”。一次写操作涉及多少个位就会有多少次异或操作，过程漫长，占用较多的CPU时间周期。

因此，在计算校验过程上，镜像式数据备份方式优于冗余式备份方式[7]。

6 结束语

在数据量爆涨的今天，数据中心的磁盘数量迅猛增长，多磁盘同时崩溃的可能性越来越大。目前有的数据中心布署了上万块磁盘。据研究表明，当一个磁盘损坏后，其他磁盘损坏的概率将会上升[2]。对于布置了1500块磁盘的中型数据中心，同时出现三个盘同时崩溃的概率为100年，此概率非常高，特别当发生如火灾、数据库节点爆炸、病毒侵害等灾难时，这种多磁盘同时崩溃的可能性更大。本文通过实例，给出了一种三个磁盘同时崩溃后的数据恢复策略，以供探讨。

作为本例，在实际应用过程中，可以将每13或14个磁盘划分为一组，就可以对存储系统中所有磁盘进行三磁盘损坏的数据恢复。

[1]汪中夏,张京生,刘伟.RAID数据恢复技术揭秘[M].北京:清华大学出版社.2010.

[2]董欢庆,李战怀,林伟. 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]戴士剑.数据恢复与硬盘修理[M].北京:电子工业出版社,2012.

[5]刘伟.数据恢复技术深度揭秘[M].北京:电子工业出版社,2010.

[6]张京生,汪中夏,刘伟.数据恢复方法及案例分析[M].北京:电子工业出版社, 2008.

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