随着移动互联网和大数据的快速发展，数据存储量呈现爆炸式的增长，致使存储系统的规模日益扩大，进而导致了越来越多磁盘和扇区同时出错的概率。存储系统的可靠性和可用性受到了极大的挑战。为保障数据的可靠性，存储容灾技术成为目前存储系统研究的重点课题之一。

复制备份的存储容灾策略由于操作简单，实施方便，成为当前常用的一种存储容灾技术，但是，其不超过50%的存储空间利用率造成了极大的空间浪费，特别是在大规模存储系统中，导致了高昂的存储成本开销。因此，编码存储容灾技术应运而生，受到越来越多的关注。

现有编码存储容灾技术可以划分为两大类：一类是确定性存储容灾技术，另一类是概率性存储容灾技术。确定性存储容灾技术一般采用固定的编译码参数，并具有严格的存储结构布局，能百分之百实现其容灾能力之内失效数据的译码恢复，通常具有最大距离可分（maximum distance separable，MDS）性质。进一步地，确定性存储容灾技术又可以划分为两类：一类是基于XOR运算的阵列码方案，典型的如EVENODD码^[1]、X-Code^[2]、RDP码^[3]、D-Code^[4]等，它们基于XOR运算，具有较高的编译码速率和更新效率，并具有MDS性质等优点，同时，也具有编码参数受到素数的限制，冗灾能力不超过3，存储结构难以线性扩展等缺点，致使其在大规模存储系统中的应用受到了极大的限制。另一类是基于有限域运算的纠删码方案，典型的如RS^[5]（Reed-Solomon）码、CRS^[6]（Cauchy Reed-Solomon）码等，其编译码参数在有限域范围内可灵活设置，具有一定的扩展能力和灵活性，从而其冗灾能力也可在有限域范围内灵活设置，同时也具有MDS性质。但是，由于有限域上的运算复杂度随着有限域规模的增大呈指数级增长，因此，在较大规模存储系统中，有限域运算效率严重影响了编译码速率，进而影响了存储系统的整体性能。对此，Luo等^[7–8]进行了有限域运算算法及CPU缓存利用上的改进；Plank等^[9]进行了一些指令集上的优化，但在较大规模参数下的运算效率依然不高。此外，为了应对实际存储系统中频发的扇区错，Blaum和Plank^[10]提出了SD码；作为SD码的改进，Li等^[11]提出了Stair码，进一步加强了存储系统的可靠性，但是它们仍然需要面对大规模有限域运算复杂度高这一难题。

概率性存储容灾技术完全基于XOR运算，同时编译码参数不受素数限制，具有很高的灵活性和扩展能力，并以可控的概率实现译码恢复，逐渐受到越来越多的关注，典型的如LDPC码^[12]（low-density parity-check）、Tornado码^[13]、LT码^[14]、Raptor码^[15]等。1962年，Gallager提出了LDPC码，鉴于其稀疏性及基于XOR运算具有很高的编译码速率，引起了学者们极大的兴趣。1997年，提出的Tornado码是一种级联的构造方式；2002年，提出的LT码实现了一种无码率构造方式；2006年，提出的Raptor码是一种对LT码的改进。目前，Tornado码已经应用在OceanStore^[16]存储系统，LT码应用在Robustore^[17]中。采用概率性存储容灾方案的优势在于：1）因为现实环境中的数据容灾系统的可靠性多以概率指标来衡量，符合事物的本性；2）由此途径有希望进一步寻求容灾性能（比如系统的可扩展性能、更高的容灾指标等）的突破。其缺点在于译码成功的概率性，但可以将其限制在一个可控的范围内。

针对大数据时代高容灾易扩展存储系统的要求，作者提出了一种基于随机矩阵的RAID容灾存储方法—随机阵列码（random RAID，R-RAID）。通过增加随机冗余δ，可保证很高的译码成功率，此外，随机阵列码还具有编译码参数可灵活设置，编译码效率较高以及近似MDS性质等特点。因此，适用于当前大规模RAID阵列存储容灾系统。

1 RAID存储模型

RAID存储系统通常采用条带化技术实现数据的高效容灾存储，各条带在编译码关系上是相互独立的，因此，本文提出的随机阵列码聚焦于RAID存储系统中的一个条带进行编码容灾存储的研究。

图1为RAID存储系统中的一个条带（stripe）。该条带由N个磁盘中处于相同位置的一段连续存储空间组成，称为N个组块（chunk或strip），每个组块由r个块（block）构成，从而，可将该条带看做一个r×N的块阵列。在这N个组块中，T个组块被专门用来存储编码数据。另外，剩余的（N–T）个组块中，δ个块也被用来进行编码，称之为随机冗余，这些块可以在（N–T）个组块中均匀地分布。图1所示的条带中白色部分存储原始数据，阴影部分存储编码冗余数据。

作为RAID中的基本单元——块，既可以是一个扇区，也可以是多个扇区的组合，因此，块、扇区在本文中是通用的。

RAID存储系统经常遭受磁盘失效和扇区失效的情况。磁盘失效的情况可以被映射为条带中对应磁盘上组块的失效，而扇区失效则可以被映射为对应磁盘中块的失效。目前，纠删编码技术已经被用于实际存储系统中以预防数据的丢失。随机阵列码是一类具有近似最优存储空间利用率的高容灾易扩展的纠删编码方案，可以有两种层面的表述方式：1）从宏观磁盘上来看，它是一种MDS编码方案。（n，k）MDS码具有特点为，k个原始数据编码生成n个编码数据，其中，任意k个数据均可由剩余的（n–k）个数据恢复出来。对于随机阵列码而言，其任意T个组块失效，均可由剩余的（N–T）个组块恢复，因此，宏观上随机阵列码是一种MDS编码方案，可表示为（ $N,N \! - \! T$ ）码。2）从微观块上来看，由于随机阵列码为保证高概率成功译码额外增加了δ个随机冗余块，因此不再是MDS的。但是，随着k的增大，随机冗余δ的比重将越来越小，从而，通过合适的参数设置可使随机阵列码达到近似最优的存储空间利用率，此时，随机阵列码可表示为（ $n,k,t,\delta $ ）码。

此外，参数T作为可容灾的盘数，是随机阵列码容灾能力的一种体现。一般地，定义RAID存储系统的容灾能力（Fault tolerance，F）为存储系统中最大可删除的盘数或块数占整个存储区域的比例。对于随机阵列码有F=T/N。相对于传统阵列码，随机阵列码的编码参数不再受到素数的限制，因此其容灾能力可以超过3，实现更高的容灾能力。同时，由于随机阵列码中编码冗余分块的产生与RAID存储布局方式无关，其容灾只与失效块所占比例有关，因此它既可以实现传统阵列码磁盘模式的容灾，也可实现扇区–磁盘模式的容灾。而参数δ作为随机阵列码的随机冗余，是保证随机阵列码能够高概率译码的关键因素。

2 随机阵列码的编译码方案 2.1 编码过程

随机阵列码是一类线性分组码，其每个编码数据块均可看作原始数据块的线性组合。通常线性分组码的编码过程可以表示为： ${{\mathit{\boldsymbol{G}}}_{n \times k}} \times {{\mathit{\boldsymbol{\alpha }}}_{k \times 1}} = {{\mathit{\boldsymbol{\beta }}}_{n \times 1}}$ 。其中： ${{\mathit{\boldsymbol{G}}}_{n \times k}}$ 为编码矩阵，也可称为生成矩阵； ${{\mathit{\boldsymbol{\alpha }}}_{k \times 1}}$ 为信息向量，视为原始数据块向量； ${{\mathit{\boldsymbol{\beta }}}_{n \times 1}}$ 为码字，则可视为编码数据块向量。为便于数据的存取和恢复，本文将随机阵列码设计为系统码结构，也即编码矩阵 ${{\mathit{\boldsymbol{G}}}_{n \times k}}$ 为上单位矩阵形式。

聚焦于存储系统中的一个条带，假设其实施者已经给出了存储系统的设计参数N、r，可根据RAID存储系统容灾需求得到T，根据译码成功率需求得到随机冗余δ。从而，随机阵列码的编码冗余数据可以按照算法1产生。

算法1 　随机阵列码编码流程

输入：该条带含N个磁盘，T个编码盘，随机冗余δ，条带的行数为r。

输出：编码冗余数据。

1. 计算 $n \! = \! r \! \times \! N$ ， $t \! = r \! \times \! T$ ， $k \! = \! r \times \! (N \! - \! T) \! - \! \delta $ ， $m \! = \! n \! - \! k$ ；

//构造编码矩阵

2. 构造 $GF(2)$ 上的随机矩阵 ${{\mathit{\boldsymbol{R}}}_{n \times k}}$ ；

3. if ${{\mathit{\boldsymbol{R}}}_{n \times k}}$ 非列满秩 then

4. 　goto步骤2；

5. end if

6. 利用初等矩阵变换将 ${{\mathit{\boldsymbol{R}}}_{n \times k}}$ 变换为上单位矩阵的 $\displaystyle{\mathit{\boldsymbol{R}}}_{n \times k}' = \left[ {\frac{{{{\mathit{\boldsymbol{I}}}_{k \times k}}}}{{{{\mathit{\boldsymbol{D}}}_{m \times k}}}}} \right]$ 形式；

7. 编码矩阵 $\displaystyle{{\mathit{\boldsymbol{G}}}_{n \times k}} = \left[ {\frac{{{{\mathit{\boldsymbol{I}}}_{k \times k}}}}{{{{\mathit{\boldsymbol{D}}}_{m \times k}}}}} \right]$ ；

//产生编码冗余

8. 将原始数据平均分为k个块，不足的位补零；

9. 在（N–T）个数据盘中依次选取k个块存放原始数据块；

10. 利用公式 ${{\mathit{\boldsymbol{G}}}_{n \times k}} \times {{\mathit{\boldsymbol{\alpha }}}_{k \times 1}} = {{\mathit{\boldsymbol{\beta }}}_{n \times 1}}$ 产生编码数据 ${{\mathit{\boldsymbol{\beta }}}_{n \times 1}}$ ；

11. 将编码数据 ${{\mathit{\boldsymbol{\beta }}}_{n \times 1}}$ 的最后m个数据块依次存储在剩余的m个编码冗余块中；

12. 编码结束。

根据算法1可知，随机阵列码的编码效率重点在于G下半部分的矩阵D中元素为“1”的个数。特别地，当随机矩阵为均匀分布时，G矩阵下半部分矩阵D中元素“1”的平均数目约为 $m \times k/2$ ，从而对于每个编码块，平均约需要k/2个原始数据块异或。因此，随机阵列码每个编码冗余数据的度为O（k）。

图2为存储系统中某条带参数为 $N = 6,T = 2,\delta = 3,$ $r = 4$ 。进一步地，n=24，k=13，t=8。由此，可构造（6，4）或（24, 13, 8, 3）随机阵列码。对于需要较高译码成功率的随机阵列码，可以设置较大的δ。但是，为了最大化利用存储空间，要求δ在条带中的比例较小，从而需要较大的编码参数。因此，随机阵列码在较大规模存储系统中更具优势。

2.2 译码过程

当RAID存储系统中由于磁盘损毁或扇区损坏等原因导致编码数据丢失时，也即条带中对应的组块或块失效时，可根据损毁程度进行失效数据的译码恢复。

定义条带上的失效率s为条带中失效编码块数或磁盘数占整个条带中编码块数或编码盘数的比例。

线性分组码通常利用校验矩阵进行译码恢复： ${\mathit{\boldsymbol{H}}}_{n \times (n - k)}^{\rm{T}} \times {{\mathit{\boldsymbol{\beta }}}_{n \times 1}} = {\mathit{\boldsymbol{\theta }}}$ ，该译码方式对于随机阵列码也是适用的。随机阵列码的译码方案可以按照算法2进行。

算法2 　随机阵列码译码流程

输入：编码矩阵G，容灾能力F。

输出：失效数据块数据。

1. 统计存储条带中的失效块数；

2. 计算该条带的失效率s；

3. if $s > F$ then

4. 　失效数据块过多，超过容灾能力F，无法恢复失效数据，重构失败；

5. 　return

6. end if

7. 标记失效编码块上的数据为未知；

8. 根据生成矩阵G产生校验矩阵H；

9. 提取H中失效数据块对应的行构建子矩阵 $\mathit{\boldsymbol{A}}$ ；

10.将未失效数据块信息代入译码方程组中，得到数据块向量B；

11. 化简 ${{\mathit{\boldsymbol{H}}}^{\rm{T}}} \times {\mathit{\boldsymbol{\beta }}} = {\mathit{\boldsymbol{\theta }}}$ 为 ${\mathit{\boldsymbol{A}}} \times {\mathit{\boldsymbol{x}}} = {\mathit{\boldsymbol{B}}}$ ；

12. 求出子矩阵 $\mathit{\boldsymbol{A}}$ 的广义逆矩阵 $\mathit{\boldsymbol{A}}^{-1}$ ；

13. 由 ${\mathit{\boldsymbol{x}}} = {{\mathit{\boldsymbol{A}}}^{ - 1}} \times {\mathit{\boldsymbol{B}}}$ 求得各个失效数据块的数据；

14. 方程的解即为失效数据块的数据，并将其依次放入失效数据块中；

15. 重构成功，译码结束。

由随机阵列码的译码过程可知，通过对校验矩阵子矩阵构造的译码矩阵广义逆矩阵的求解，可以减少因直接使用高斯消去法而产生的大规模数据块的频繁异或。特别地，当数据块规模较大时，数据块间的异或产生的译码开销也是非常大的，因此利用译码矩阵的广义逆进行失效数据块数据的求解。

由随机阵列码的译码方案可以看出，相对于确定性的阵列码，随机阵列码的译码只考虑整个条带的失效率，而对失效块的分布情况不用关心。特别地，假定条带中第1行的数据全部失效，传统阵列码方案如EVENODD码是无法恢复的；随机阵列码只要失效率低于其容灾能力，就可以恢复，从而具有更广的容错模式。

2.3 可行性分析

随机阵列码的构造使用了 $GF(2)$ 上的随机矩阵及其重要性质，表述如下：

$GF(2)$ 上的矩阵 ${{\mathit{\boldsymbol{R}}}_{n \times k}}$ ， $n > k > 0$ ，若其中的各元素取值相互独立，且满足取“0”的概率为p，取“1”的概率为 $1-p$ ；当 $p \in (0,1)$ 时，则称其为随机矩阵；当p=0.5时，称为均匀随机矩阵。

定理1 　二元域 $GF(2)$ 上的随机高矩阵 ${{\mathit{\boldsymbol{G}}}_{n \times k}}(n > k)$ 其列满秩的概率为： $S = \prod\limits_{i = 1}^k {\left( {1 - {p^{\delta + i}}} \right)} $ ，其中， $\delta = n - k$ 。

逐列增加随机矩阵的秩，显然定理1易证。

定理2 　随机高矩阵 ${{\mathit{\boldsymbol{G}}}_{n \times k}}(n > k)$ 列满秩的概率 $S > 1 - \displaystyle\frac{1}{{1 - p}}{p^{\delta + 1}}$ 。

由定理1以及相关数学推导，定理2易证。

定理3 $GF(2)$ 上列满秩的生成矩阵为 ${{\mathit{\boldsymbol{G}}}_{n \times k}},k < n$ 和校验矩阵为 ${\mathit{\boldsymbol{H}}}_{n \times l}^{},l = n - k$ 。如果 ${{\mathit{\boldsymbol{G}}}_{n \times k}}$ 中删除任意 $t\left( t < \right.$ $\left. {\rm{min}} \{ k,l\} \right)$ 行仍然列满秩，则 ${\mathit{\boldsymbol{H}}}_{n \times l}^{}$ 中对应t行线性无关。

证明：假设 ${{\mathit{\boldsymbol{G}}}_{n \times k}}$ 中删除任意t行后仍然列满秩，而 ${\mathit{\boldsymbol{H}}}_{n \times l}^{}$ 中对应t行线性相关，从而 ${\mathit{\boldsymbol{H}}}_{n \times l}^{}$ 中对应t行构成的子矩阵 ${{\mathit{\boldsymbol{S}}}_{t \times l}}$ ，其秩 $Rank({{\mathit{\boldsymbol{S}}}_{t \times l}}) < t$ 。

记 ${{\mathit{\boldsymbol{\beta }}}_{n \times 1}}$ 为 ${{\mathit{\boldsymbol{G}}}_{n \times k}}$ 中k列任意非零组合。由 ${{\mathit{\boldsymbol{G}}}_{n \times k}}$ 列满秩可知， ${{\mathit{\boldsymbol{\beta }}}_{n \times 1}} \ne {\mathit{\boldsymbol{\theta }}}$ ，且由生成矩阵 ${{\mathit{\boldsymbol{G}}}_{n \times k}}$ 与校验矩阵 ${\mathit{\boldsymbol{H}}}_{n \times l}^{}$ 的相互正交性可知， ${\mathit{\boldsymbol{H}}}_{n \times l}^{\rm{T}} \times {{\mathit{\boldsymbol{\beta }}}_{n \times 1}} = {\mathit{\boldsymbol{\theta }}}$ 。从而对于 ${\mathit{\boldsymbol{H}}}_{n \times l}^{}$ 中对应的t行子矩阵 ${\mathit{\boldsymbol{S}}}_{t \times l}^{}$ 以及 ${{\mathit{\boldsymbol{\beta }}}_{n \times 1}}$ 中对应的t个删除元素组成的向量 ${\mathit{\boldsymbol{\beta }}}_{t \times 1}'$ 有， ${\mathit{\boldsymbol{S}}}_{t \times l}^{\rm{T}} \times {\mathit{\boldsymbol{\beta }}}_{t \times 1}' = {{\mathit{\boldsymbol{C}}}_{l \times 1}}$ 。由 $Rank({{\mathit{\boldsymbol{S}}}_{t \times l}}) < t$ 可知， ${\mathit{\boldsymbol{S}}}_{t \times l}^{\rm{T}} \times {\mathit{\boldsymbol{\beta }}}_{t \times 1}' = {{\mathit{\boldsymbol{C}}}_{l \times 1}}$ 至少有两组不同解x₁、x₂，分别将解代入到 ${{\mathit{\boldsymbol{\beta }}}_{n \times 1}}$ 中对应的位置上，得到互不相同的 ${{\mathit{\boldsymbol{\beta }}}_1}$ 、 ${{\mathit{\boldsymbol{\beta }}}_2}$ ，二者存在如下性质：

1） ${{\mathit{\boldsymbol{\beta }}}_1}$ 和 ${{\mathit{\boldsymbol{\beta }}}_2}$ 中t个分量存在不同，另外 $n - t$ 个分量则完全相同。

2）记 ${{\mathit{\boldsymbol{\beta }}}_3} = {{\mathit{\boldsymbol{\beta }}}_1} - {{\mathit{\boldsymbol{\beta }}}_2}$ ，则有 ${{\mathit{\boldsymbol{\beta }}}_3} \ne {\mathit{\boldsymbol{\theta }}}$ ，且 ${{\mathit{\boldsymbol{\beta }}}_3}$ 中 $n - t$ 个分量全为0，又因 ${{\mathit{\boldsymbol{\beta }}}_3}$ 为 ${{\mathit{\boldsymbol{\beta }}}_1}$ 和 ${{\mathit{\boldsymbol{\beta }}}_2}$ 的线性组合，从而 ${{\mathit{\boldsymbol{\beta }}}_3}$ 也可由 ${{\mathit{\boldsymbol{G}}}_{n \times k}}$ 的k列非零组合生成。

根据已知条件， ${{\mathit{\boldsymbol{G}}}_{n \times k}}$ 删除t行后仍然列满秩，从而 ${{\mathit{\boldsymbol{G}}}_{(n - t) \times k}}$ 中k列任意非零组合不可能产生（ $n - t$ ）维零向量。这与 ${{\mathit{\boldsymbol{\beta }}}_3}$ 的性质2）矛盾。从而假设不成立。 ${\mathit{\boldsymbol{H}}}_{n \times l}^{}$ 中对应t行线性无关。

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \;\;\;\;\; \text{证毕。}$

推　论 　当 $p = 1/2$ ，对于任意t个块的失效，随机阵列码成功译码的概率至少为 $1 - \displaystyle\frac{1}{{{2^{\delta + t}}}},\delta = n - k$ 。

由定理3可知，若G中删除任意t行仍然列满秩，则H中对应的t行线性无关，也即译码矩阵有唯一解。从而，随机阵列能够成功译码的概率等价于G中删除任意t行仍然列满秩的概率。根据定理1、定理2可知，当 $p = 1/2$ 时，随机阵列码G删除任意t行仍然列满秩的概率至少为 $1 - \displaystyle\frac{1}{{{2^{\delta {\text{ + }}t}}}}$ 。从而，随机阵列码在 $p = 1/2$ 时，成功译码恢复t个失效块的概率也至少为 $1 - \displaystyle\frac{1}{{{2^{\delta {\text{ + }}t}}}}$ 。因此，若取较大的δ（如δ=20）时，随机阵列码的译码失败率将低于10^–7。从而，随机阵列码可以应用于实际的存储编码方案中。

3 实验结果与性能分析

实验运行环境：测试所用计算机CPU为Intel（R）Core（TM）i3，3.07 GHz；内存4.0 GB；64位Ubuntu 15.10操作系统。

3.1 可行性分析

选取 $p = 0.5$ ， $n = k + \delta $ ，构建均匀随机矩阵 ${{\mathit{\boldsymbol{R}}}_{n \times k}}$ ，统计 ${{\mathit{\boldsymbol{R}}}_{n \times k}}$ 列满秩的情况如下。

由图3可见，当δ ≥15时，对于任意的k，随机高矩阵 ${{\mathit{\boldsymbol{R}}}_{n \times k}}$ 列满秩的概率已经基本为1，从而进一步验证了随机矩阵 ${{\mathit{\boldsymbol{R}}}_{n \times k}}$ 高概率列满秩的特性。这也为随机阵列码的可行性提供了实验基础。

3.2 编码参数及容灾能力

随机阵列码与部分现有的确定性存储容灾技术和概率性存储容灾技术在编码参数上的对比如表1所示。

由表1可知：对于确定性存储容灾技术之基于XOR的传统阵列码方案，如EVENODD、X-Code、RDP等，编码参数u（u>2）受限于素数的影响，只能产生一些固定结构的编码方案，相应地，其容灾能力也受到影响，一般只为2～3。而其优势在于具有MDS性质并基于XOR运算，因此具有最优的存储空间利用率和较高编译码速率。对于基于有限域上的编码方案，如RS码、CRS码等，其编码参数可以在有限域范围内灵活设置，相应的容灾能力也可以灵活设置，且均为MDS码，因此其存储空间利用率也可以达到最优。但是，由于有限域上的运算随着有限域规模的增大，计算复杂度呈指数级增长，因此，在较大规模的有限域中，其编译码速率很低（详见第3.3节）。对于概率性存储容灾技术，如LDPC、Tornado码、LT码，其编码参数可以灵活设置，其容灾能力也可以灵活设置。此外，它们基于XOR运算，具有较高编译码效率。但是，由于其概率性译码和非MDS特性，为了保证高概率译码通常需要较多的编码冗余块，因此其存储空间利用率一般较低。而随机阵列码吸取各方所长，既基于XOR运算，又可达到近似MDS性质，从而，其编译码效率较有限域方式较高，而存储空间利用率较LT码等方式也较高，同时还具有容灾扩展性。因此，具有很好的研究和应用价值。

3.3 性能分析

假定原始文件大小为256 MB，存储系统的容灾能力F=20%，随机冗余δ=20，随机概率p=0.5。不同码长下，构造随机阵列码方案与Plank提供的Jerasure2.0库中经过SIMD指令集优化的相应RS码及CRS码方案，并进行编译码效率比较。

1）编码速率比较

选取码长n=100～1 000，间隔100，根据存储系统的容灾能力设置相应的编译码参数，构造编码方案进行编码速率比较。

由图4可见，在相同码长下，随机阵列码方案较相应的RS码、CRS码方案，其编码速率更快。这主要是由于基于XOR运算的随机阵列码较使用有限域运算的RS码在运算效率上更高。尽管CRS码本质上采用了XOR运算，但由于其是在有限域 $GF({2^w})$ 上构造，从而编码矩阵规模较随机阵列码增大了 ${w^2}$ 倍，因此，较随机阵列码有更多的XOR次数，从而其编码速率也比较低。此外，随着码长的增大，三者的编码速率均呈下降趋势，但是随机阵列码的编码速率下降速度更慢。

2）译码速率比较

当条带中存在容灾能力允许下最大可删除的块数丢失时，也即t个删除块时，可利用该条带中剩余的块进行译码恢复。

由图5可见，在相同码长及删除块数下，随机阵列码方案较相应的RS码、CRS码方案，其译码速率更快。这进一步说明采用XOR运算较有限域运算具有巨大优势。另外，随着码长的增大，三者的译码速率均呈下降趋势，但是随机阵列码的译码速率下降速度更慢。

3）存储空间利用率比较

当前大规模存储系统中，存储空间利用率是一个很重要衡量标准，也是纠删码方案替代复制方案的重要驱动之一。存储空间利用率反映了在保证存储容灾能力的情况下，存储容灾技术对存储空间的使用情况有两种表达方式：可利用原始数据量占整个存储区域的比例进行描述；也可利用恢复k个数据块，所需要的编码块数量衡量。根据后一种表述方式，对于随机阵列码，高概率恢复k个数据块需要 $(k + \delta )$ 个编码块，当δ=20时，译码失败率将不超过10^–7；对于RS或CRS码，由于具有MDS性质，恢复k个数据块只需要k个编码块；对于Tornado码，文献[13]指出，高概率恢复k个数据块需要编码块的数量为1.05k；对于LT码，文献[14]指出，高概率恢复k个数据块需要1.05k～1.1k个编码块，同时，Tornado码和LT都要求较大的k，如k=10 000。

由图6可见，随着码长的不断增加，随机阵列的存储空间利用率越来越接近RS和CRS方案。由于RS和CRS方案具有MDS性质，因此，随机阵列码在较大码长时可具有近似MDS性质。

综上所述，随机阵列码随着k的增长，恢复k个数据块所需的编码块数量将越来越接近k，而Tornado码和LT码所需的编码块数量均呈k的倍数级增长。显然，随机阵列码相较于Tornado码和LT码具有更优的存储空间利用率。

4）更新效率比较

根据随机阵列码的构造方案可知，在一个条带中对于k个原始数据块，需要m个编码块进行容灾，因此，根据随机阵列码的随机性特点，每更新一个原始数据块，最坏情况下m个编码块均要更新。特别地，对于均匀随机矩阵，由于矩阵中每行每列中为“1”的元素比较均匀，因此，每更新一个原始数据块，平均需要更新m/2个编码冗余块；对于稀疏随机矩阵，平均需要更新的编码冗余块数将更少。对于RS码来讲，每更新一个原始数据块，则条带中所有的编码块都要更新一遍，因此其更新次数也为编码块的数目m。对于LT码来讲，根据文献[14]，要覆盖所有k个输入块，编码块的度和约为 $k\ln (k/\varepsilon )$ ，其中 $\varepsilon $ 为译码失败率，从而对于每个输入块的平均出度约为 $\ln (k/\varepsilon )$ ，也即每个输入块的更新将伴随平均 $\ln (k/\varepsilon )$ 个编码冗余块的更新。因此，在高概率成功译码下，LT码的更新复杂度也比较高。综上所述，随机阵列码的更新效率略优于RS码，但明显优于LT码。

4 结　论

依据随机高矩阵高概率列满秩的特性，提出了一种随机阵列码编译码方案。与确定性存储容灾技术之传统阵列码如EVENODD码、X码等相比，随机阵列码具有编码参数不受素数限制，容灾能力随规模扩展可灵活扩展等优势。与确定性存储容灾技术之基于有限域运算的编码方案如RS码、CRS码相比，随机阵列码采用XOR运算，避免了有限域上高昂的计算开销，具有较高的编译码速率。与概率性存储容灾技术如Tornado码、LT码比较，随机阵列码又具有较高的存储空间利用率，因此，具有良好的研究价值和广阔的应用前景。

本文提出的随机阵列码为RAID存储容灾系统的概率性存储容灾技术提供了一种新的思路和解决方案。该方案还有需要进一步解决的问题，例如，如何构建更稀疏的编译码矩阵，以及编译码效率的改进提升等问题，都将成为下一步的研究工作。