分布式容错存储系统中阵列码的研究综述

李秋萍 赵军霞 李康满

摘要：计算机和网络技术的飞速发展，使得人们快速地步入了数据大爆炸的时代。数据的存储技术也得到了快速发展，从单机存储系统发展为廉价且存储扩展能力强的分布式存储。但随着存储数据量的增大，数据失效成为一种每天都会发生的事件，所以分布式系统的容错能力的研究，成为迫切需要解决的问题。阵列码因其可以用最少的冗余来容错，而且编解码容易实现，被广大学者所研究。该文首先介绍了阵列码容错技术研究生存在的挑战。然后根据阵列码的结构特点，分为水平码，垂直码和水平一垂直码对其研究现状进行了分析。最后，我们分别从数据编解码，数据修复和数据更新三个方面，对未来的研究方向进行了展望。

关键词：分布式;容错存储系统;阵列码;数据编解码;数据修复;数据更新

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2020）08-0250-02

随着计算机存储和压缩技术的发展，大容量存储设备、智能手机的广泛应用以及多媒体应用与社交网络的流行，互联网上的各种数据（文本、图像以及视频等）呈现出爆炸式的增长趋势，大量数据的产生己经成为必然趋势，随着数据存储规模的不断增长，传统的单机系统已经无法满足高速增加的数据存储需求，存储这些海量数据成了亟待解决的问题。分布式存储系统使用大量廉价商用服务器通过网络互联，可以提供极强的服务能力和扩展能力，但这些组件的数量和质量导致了该类存储系统的节点失效成为常态事件，而数据本身的价值往往是无法估量的，因此，相比于存储系统的存储容量、存取带宽、I＼0处理能力等指标，容错能力是其中最重要的一项。

多副本技术和纠删码技术是两种常用的容错技术。多副本技术的基本思想是为数据对象包含的数据块创建多个副本，并将多个副本放置在不同的节点中以最大化数据的可用性。多副本技术最大的优点是维护多个副本只需要额外的通信和存储开销，不需要任何计算，不占用服务器的CPU资源。但多副本技术的数据冗余度较大，存储效率低。纠删码技术的基本原理是将数据对象包含的多个数据块通过编码方式生成多个编码块，并将数据块与编码块分别存储在不同的节点中以最大化数据可用性。纠删码技术能够通过调节数据分块和冗余块的取值使系统在节约存储空间的同时，提供容忍更多失效节点的容错能力，这也使得基于纠删码的容错技术成为当前分布式存储领域一个重要的研究热点。阵列码是一类在存储系统中常用的纠删码，这类码可以使用最少的冗余来提供容错能力，并且其编解码过程只需要用到简单的异或和循环移位运算，因此近几年来受到了越来越广泛的关注。

1 问题与挑战

随着信息时代数据规模的快速增长，容错能力强且存储成本低的阵列码技术受到了越来越多的关注。但现有的阵列码在数据编解码，数据修复，数据更新三个方面仍可以进一步优化。

1.1 数据编解码

数据的编解码技术大概可以分成两个方向，一个是提高数据编解码计算效率，一个是提高阵列码容错能力。在基于纠删码的容错存储系统中，在数据写入系统时首先要对其进行编码，读出数据时需要对其进行解码，如果编解码效率不高，则会影响整个系统的读写效率，极大地制约了纠删码在存储系统中的应用。提高纠删码的容错能力可以提高数据的可靠性，可用性，节约存储空间。但是优化编解码效率与提高容错能力之间往往相互矛盾，现有的一些纠删码经常在二者之间进行权衡。

1.2 数据修复

基于纠删码的存储系统中，修复一个失效块前需要先对未失效固定个数的数据块进行下载，然后再对数据进行修复，这导致一旦一个数据块失效会有固定倍数的数据传输产生，这极大地降低了数据的传输效率和整个系统的传输效率。因此提高纠删码的修复效率是基于纠删码的容错系统急需解决的一个问题。

1.3 数据更新

基于纠删码的数据存储系统中，一个数据块往往关联着许多数据块，这导致更新一块数据将要面临更新许多块数据的传输和更新，这导致了与数据修复面临相同的问題，即需要提高数据的更新效率。

2 研究现状分析

阵列码是一种将数据以二维形式排列的线性分组码，其具有实现容易，编解码以及更新计算开销较低的优点。阵列码无论是在编解码的复杂度，还是在冗余开销，更新复杂度等方面较其他纠删码都有明显的优势。根据阵列码的结构特点，阵列码分为水平码，垂直码，水平一垂直码，本小节我们将这三个方面对国内外的研究进展进行分析。

2.1 水平码

水平码是把原数据和校验数据分别存储在不同的数据块中的阵列码。目前已知最具代表性的水平码主要包括EVENODD[2]码，RDP[3]码，Liberation码等及它们的推广码。

EVENODD码和RDP码都是可以容忍任意两个磁盘同时出错的阵列码，并且都满足MDS性质。EVENODD码是最早应用于RAID-6的阵列码，但随着硬盘容量的增加，对系统的容错能力要求也越来越高，为解决这些问题，许多学者对这两种编码方式进行了一定的改进，如总体解码效率得到提高的可以容忍任意三个磁盘同时出错的STAIR阵列码及一些二进制MDS阵列码。RDP码是与EVENODD码十分相似的阵列码，它的特点是编码过程中首先计算第一个校验列的值，然后将其作为数据列参与对角线校验列的计算，值得一提的是它的编解码效率最优。RDP码提出后，EVENODD码的作者Mario Blaum提出了一种广义的RDP码，这种码在满足一定条件时肯定是MDS码。同时RDP的原作者受到STAR码的启发，提出了RTP码[5]，使得其总体解码性能优于原RDP码。Liberation码的奇偶校验矩阵的密度达到了水平码的下界，这使得其更新复杂度是所有水平阵列码中最低的，但是其解码复杂度要比以上两种阵列码的高许多。除此之外，也有学者提出了可以有效降低数据修复成本的LRC码和LRCs码这两组码可以在修复开销与存储空间开销之间灵活地进行权衡。

2.2 垂直码

垂直码是将数据分组后按照一定的计算方式得到校验块，并将得到的校验块与数据块交叉放置在磁盘的阵列码。具有代表性的垂直码包括X-code码和WEAVER码，B-碼等。

X-code码是一种非常易于实现的垂直码，它最大的优点是编解码复杂度和更新复杂度均能达到最低。它的缺陷是对码长的限制太过严格，虽然文献中根据水平码码长的扩展方法对其进行了扩展，但扩展过程比水平码复杂。WEAVER码是限定了数据块和校验块的个数后，通过搜索找出最优的放置方法，使其容错能力达到最高。WEAVER码的不足是冗余度较高以及空间利用率较低。B-码的优点是其码长限制最少，同时编解码复杂度和更新复杂度同时达到了最低，值得一提的是B-码的作者将完全图的PIF（Perfect One Factorization）问题与最低密度MDS码的构造结合，证明了只要给定的一个完全图PIF，就可以构造出一个与之相对应的B-码。

2.3 水平一垂直码

水平一垂直码是指数据块和校验块兼有水平码和垂直码的特征，部分数据块和校验块单独放置，部分交叉放置。具有代表性的水平垂直码包括HVPC码，GRID码和HoVer码和SHEC码等。

HVPC码是很早提出的一种编码，它的容错能力为3，同时也能够被扩展成多维的情况，以便有更高的容错能力，但是它的存储空间利用率较低。在HVPC的基础上，GPID码使用了一些其他的编码来替代HVPC码中的保护码，提高了容错能力，同时也有较高的存储空间利用率，但是它要求构造它的两类编码必须相互匹配，这导致适用于它的编码对较少。另外一类水平一垂直码是HoVer码，它的存储利用率较高，容错能力最多能达到4，可以很方便的调节存储利用率和计算效率间的均衡。

除了上述三种结构，阵列码还有许多其他形式的编码。如2014年Tosato和Sandell提出的一种适用于存储系统中各节点容量不同的场合的不规则MDS阵列码，清华大学的Fu[4]等人提出的对RAID-6在正常模式和降级模式下的读性能进行优化的一种由最低密度MDS阵列码。数据修复时只传输数据而不需要进行任何数学运算的MBR码。以及可以将数据修复时所需下载的数据量降低45%的Hichhiker码。带扇区容错的SD码，PMDS码[1]等。

可见针对阵列码容错性的研究一直在进行，不断地在优化，但随着数据量的不断增长，这一研究仍然需要持续的关注。

3 研究展望

从阵列码研究遇到的问题和研究现状可以看出，阵列码在以下几个方面仍然需要进一步的研究。

3.1 数据编解码

阵列码在相同的容错能力的前提下，能够极大的节约存储空间。数据的编解码效率直接与阵列码本身相关，何种方法构造的阵列码可以提高编解码效率同时节约硬件存储资源，是我们需要研究的问题。因此，研究在保证容错能力的条件下，如何提高编解码效率，降低计算复杂度是值得研究的方向。

3.2 数据修复

阵列码由于码字本身的特殊性，可以通过增加一些额外的冗余数据来减少修复时下载的数据量，通过构造一些低复杂度的码来优化修复能力，以达到提高数据修复效率的目标。因此，数据修复效率与阵列码生成矩阵的元素计算效率息息相关，如何选择矩阵来提高计算效率仍然是我们要解决的问题。

3.3 数据更新

阵列码中的计算可以通过简单的异或运算和循环移位来实现，所以我们可以通过一些稀疏矩阵的迭代来简化数据的计算与更新，以达到提高数据更新效率的目标。而数据更新效率与数据修复效率相同，主要是数据传输量和计算量大的问题，因此如何构造矩阵使其有较低的计算量是我们可以研究的方向。

4 总结

近年来人类社会所产生的数据急剧膨胀，分布式存储系统由于其在成本、性能、可扩展性及存储容量等方面的优势，被广泛应用于商业和科学计算等大数据的存储之中。而分布式存储系统中的节点故障已经成为系统运行中一个常态化的行为，因此容错能力已经成为区分分布式存储系统好坏的一个重要指标。本文首先指出了阵列码在分布式容错存储系统中的优势和面临的主要问题。随后，对分布式存储系统中阵列码容错技术的国内外研究现状进行了分析。最后，本文基于面临的问题和研究现状对未来的研究进行了展望。

[1] Blaum M，Hafner J L，Hetzler S.Partial-MDS codes and theirapplication to RAID type of architectures[J].lEEE Transactionson Information Theory， 2013，59（7）：4510-45 19.

[2] Blaum M， Brady J， Bruck J， et al. EVENODD： An efficientscheme for tolerating double diskfailures in RAID architec-tures [J]. Computers. IEEE Transactions on. 1995， 44 （2）：192-202.

[3] Corbett P， English B， Goel A， et al. Row-diagonal parity fordouble disk failure correction. in：Proceedings of the 3rd USE-NIX Conference on File and Storage Technologies （FAST' 04），2004，1-14.

[4] Fu Y X，Shu J W.D-code：an efficient RAID-6 code to opti-mize l/0 loads and read performance[Cy/2015 lEEE Intema-tional Parallel and Distributed Processing Symposium，May 25-29， 2015. Hyderabad， India. IEEE. 2015.

[5] Coel A，Corbett P.RAID triple parity[J].ACM SIGOPS Operat-ing Systems Review， 2012，46（3）：41.

收稿日期：2019-12-25

基金项目：《轻量级MDS扩散层研究与实现》，衡阳师范学院科研基金项目（No.18D23）;《一种低资源的轻量级分组密码的研究与实现》，湖南省教育厅科学研究一般项目（NO.18C0678）

作者简介：李秋萍（1989-），女，辽宁沈阳人，博士研究生，讲师，主要研究方向为密码编码学。