纠删码项目总结（1.0）

1. 为什么要使用纠删码？
随着数据的持续增长，在 PB 级别的数据中心，多副本技术会引入极大的存
储开销。比如，现有的分布式存储系统，如 HDFS（Hadoop distributed file system）、
Ceph，普遍采用三副本的配置，这将占用原始数据的 3 倍存储空间。
面对如此情况，纠删码技术因其低存储开销的特点近年来受到越来越多的关
注。其中，RS 编码（Reed-Solomon code）是目前被广泛使用的纠删码方案，它
将 k 个数据块按照一定的编码规则，生成 m 个校验块，对于这 k + m 个编码块，
其编码性质保证通过任意的 k 个编码块均能重建出所有数据。以 RS（4, 2）编码
为例，它只需占用 1.5 倍的存储空间，就具有与三副本技术相同的容错能力。
2. 纠删码的缺点
然而当数据丢失时，纠删码技术数据修复的速度没有多副本快。为了修复丢
失的数据，多副本技术只需拷贝对应数据的冗余副本。而纠删码需要读取 k 块数
据，通过计算重建丢失的数据，相比之下，占用了更多的磁盘带宽和网络带宽，
也引入了额外的计算开销。这不仅导致修复时间过长，而且也对前台应用带来干
扰。在大规模集群环境下，磁盘、服务器和网络的错误已经成为常态，为了保持
数据可靠性，存储系统需要频繁进行修复操作，进一步加重了纠删码修复给系统
带来的压力。
3. 纠删码相关概念
（1）数据块（Data Block）：初始数据对象根据系统的数据分布规则在磁盘
中分散存储后产生的块。
（2）局部校验块（Local Parity Block）：在数据块被分组后，组内数据利用
纠删码算法计算得到的一块冗余数据。
（3）全局校验块（Global Parity Block）：一个条带上全部数据块利用纠删码
算法计算得到的一块冗余数据。
（4）编码块（Coded Block）：数据块、局部校验块以及全局校验块统称为编
码块。
（5）条带（Stripe）：属于一个容错组的数据块和校验块在逻辑上处于同一
个条带上。一个存储系统可以划分为很多个条带，条带之间相互独立。
（6）MDS（Maximum Distance Separable）：当一个 纠删码满足 ，则该纠删
码满足 MDS 性质，也称该纠删码为 MDS 码。与其它纠删码相比，MDS 码在具
有相同容错能力的条件下具有最低的存储开销。
（7）数据重构（Data Decoding）：当一个条带中的编码块因磁盘或节点失效
等原因而丢失时，利用条带内剩余的编码块重新计算生成出失效的编码块的过程。
（8）容错能力（Fault Tolerance Ability）：一个条带上理论可重构的编码块失
效个数的最大值。如果一个编码方案的容错能力为 ，则该码可以在不多于 个编
码块失效的、理论上可重构的情况下，重构出失效的编码块。
（9）容错率（Fault Tolerance Rate）：当编码块中有 块丢失时，这 块数据可
能是数据块、局部校验块和全局校验块的任意组合。容错率就是这些组合中理论
上可以被重构的组合数和所有组合数的比值。
（10）存储开销（Storage Overhead）：编码块的个数，即数据块和校验块的
总和。
（11）重构读取开销（Reconstruction Read Overhead）：数据重构时需要从条
带中读取的编码块的个数。
4. 纠删码研究方向
纠删码容错技术在大规模分布式存储中面临的主要挑战已不再是其较高的
运算复杂度，而是其较高的网络资源消耗，以及实现上的复杂性。一方面，随着
CPU 运算能力的飞速发展，现在普通商用服务器的运算能力对于大部分存储系
统已经严重过剩。例如，百度云盘的云端存储系统 Atlas 甚至由于普通处理器利
用率过低而采用了 ARM 处理器。另一方面，与 RAID 的集中式操作不同，分布
式系统的分布特性使得纠删码容错的相关操作需要多个节点相互协作，不可避免
地带来大量的数据传输，占用较多的网络资源。一直以来，网络都是分布式系统
中的稀缺资源，往往是整个系统性能的瓶颈所在。此外，分布式系统的特性也增
加了实现的难度。具体来说，大规模分布式存储系统中纠删码容错技术面临的挑
战主要表现在编码实现、数据修复和数据更新等 3 个方面。
4.1 编码实现
编码实现是指根据给定的纠删码对数据块进行运算、得到校验块并将数据块
和相应的校验块分散到不同存储节点上的过程。其主要挑战在于如何在编码实现
完全完成之前保证数据的可靠性。一方面，由于存储系统一般以大小固定的块为
基本管理单位，数据产生只有累积到一定量才能启动编码实现；另一方面，由于
编码实现的复杂性，其编码过程需要花费一定的时间。因此，在将数据块和校验
块分散到相应的存储节点之前都有可能发生数据失效，造成数据丢失。此外，编
码过程中数据块的读取和校验块的分发也会产生大量的数据传输，占用网络资源。
总之，编码实现不仅要考虑数据可靠性还要尽量降低数据传输量。
在采用纠删码容错的分布存储系统中，需要对新写入的数据进行编码，为了
保证数据可用性，通常先利用复制技术保存新数据，等到编码完成后再将多余的
副本删除。具体的编码实现方法包括集中式编码实现方法和分布式编码实现方法。
集中式编码实现方法：在集中式编码实现方法中，一个条带的所有编码工作
都由一个编码节点来单独完成。编码节点从存储节点下载条带中的所有数据块，
编码计算校验块，然后再把校验块发送到其它存储节点上。在具体实现中，可以
从存储数据块的节点中选择一个作为编码节点，以便减少传输数据量，降低网络
资源开销。HDFS-RAID、Atlas、WAS 和 TFS 等分布式存储系统均采用集中式
编码实现方法。
优缺点：集中式编码实现方法的优点是简单易于实现，其缺点是存在较为严
重的性能瓶颈。编码节点负责编码计算和分发编码块，易产生计算瓶颈和网络传
输瓶颈，从而影响编码实现效率。
分布式编码实现方法：为了解决集中式编码实现方法的性能瓶颈问题，
Pamies-Juarez 等人针对 RapidRaid 码的特点，提出了基于流水线的分布式编码实
现方法。该方法将 RapidRaid 码的编码计算分解为可以在不同节点上并行执行的
子任务，将编码实现的网络传输负载和计算负载均衡分布到多个节点上，采用流
水线方式进行编码计算。
优缺点：相对于集中式编码实现方法，现有分布式编码实现方法可以提升编
码实现的性能，但提升效果较为有限。现有分布式编码实现方法一般对纠删码或
数据放置等有严格要求，并且数据传输方面的提升往往以更多的数据读取量或计
算量为代价。
4.2 数据修复
数据修复的挑战主要在于如何降低数据读取量和数据传输量。与多副本容错
技术只需重新拷贝一个副本不同，采用纠删码容错的分布式存储系统进行数据修
复时，需要从多个存储节点下载数据并对这些数据进行编解码运算。一个编码块
失效，需要使用多个其它编码块进行修复，过程中需要读取并传输大量的数据。
这不仅会影响数据修复的速度而且会对数据访问效率产生明显的影响。
低修复开销纠删码：
分组码：传统 MDS 码(RS)数据修复开销大的根本原因是其条带内的每个校
验块都与所有数据块相关，导致任何一个块失效都需要下载其它 k 个块才能修
复。因此，如果将一个条带内的数据块分组，利用组内的数据块产生局部校验块，
就可以降低数据修复时需要下载的数据量。以该思想为基础构造的纠删码称为分
组码。根据不同的分组方法，分组码可进一步分为层次分组码和交叉分组码两类。
层次分组码的分组呈现明显的层次。首先将一个条带内的数据块分成少数几
个较大且互不重叠的组，然后每个组再进一步分成几个若干互不重叠的子组。以
此类推，可以根据需要划分多个层次。最后，每组各产生一个只与组内数据块相
关的局部校验块，整个条带再产生若干与条带内所有数据块相关的全局校验块。
这样大部分数据失效就可以在组内进行修复，从而降低成本。典型应用是微软的
WAS 中的 LRC 码。
在组内有多个块失效时，两层分组码仍然需要在全局范围内进行修复。为此，
可以对数据块进行更多层次的分组，高层的组包含若干低层较小的组。Pyramid
码就是根据该思想构造的多层次分组码。随着分组层次的增多，多层分组码的平
均修复开销会降低，但其存储空间开销会增大。因此，多层分组码可以在修复开
销与存储空间开销之间灵活地进行权衡。
交叉分组码与层次分组码的不同之处有两点：
（1）交叉分组码中各组包含的数据块数目基本相同，且各组包含的数据块
有一部分相同，而层次分组码不同层级的分组大小差别很大，每个高层的分组会
包含若干较低层次的组；（2）交叉分组码一般不存在全局校验块。经典交叉分组
码有 SHEC，WEAVER。
再生码：再生码（Regenerating Codes）是一种基于网络编码思想设计的纠删
码，由 Dimakis 等人在 2007 年首次提出。其基本思想是通过适当增加冗余并且
使新生节点从尽量多的节点下载数据来降低修复需要下载的总数据量。再生码具
有两个明显的特点：（1）再 生 码 的 数 据 块 和 校 验 块 都 包 含 相 同
数量的子块，编码与修复时以子块为基本单位，子块之间的关系也 更 为 复 杂；
（2）再 生 码 在 进 行 数 据 修 复时，新生节点需要从尽量多的节点来下载
数据。
再生码一般用三元组n k d , ,  来表示。n k d , ,  -再生码的一个条带包含 n 个编
码块，可以容忍任意 n k  个块失效，进行数据修复时新生节点可以连接 d 个存活
节点下载数据，其中 k d n   1。另外，再生码还有 3 个常用的辅助参数，  ,
和 B，分别表示单个编码块包含的子块个数，连接到 d 个节点进行数据修复时从
单个节点下载的子块个数和一个条带包含的所有数据子块个数。
再生码根据信息流图最小割信息，可分为最小数据存储量点( minimum
storage regenerating，MSR) 称为 MSR 编码( MSR codes)；最小带宽点( minimum
bandwidth regenerating，MBR) 称为 MBR 编码( MBR codes) 。在 MSR 这一点，
每个节点存储的数据量与 MDS 码相同， 但是在 d ＞ k 时， 总修复带宽相比
于 MDS 码更小；在 MBR 这一点，每个节点存储的数据量比 MDS 码多，并
且   = ，也就是说修复带宽不可能再小，再小就达不到所需要存储的数据量大
小。
根据失效节点修复数目，可分为单节点修复再生码和多节点修复再生码。单
节点修复再生码主要代表编码有 E_MSR、PM_MBR 和 PM_MSR。干扰对齐
（interference alignment）技术是构造 MSR 编码的一种主要方式，其思想是同时
消去多个不需要的变量。根据该思想构造出 E_MSR；矩阵乘（product matrix，
PM）是构造再生码的另一种主要方式，它可以同时构造出 MSR 编码和 MBR 编
码。再生码的矩阵构造由编码矩阵和数据矩阵构成， PM_MBR 与 RS 编码相
比，PM 编码采用数据矩阵替换了数据向量，并且在数据矩阵中存在重复的数据
子块，实现了更低的网络传输量。
多节点修复再生码包括 MBCR,MSCR，主要是单节点修复技术的扩展，原理
相近。
再生码作为对纠删码的改进， 具有很好的理论结果。但目前提出的多数再
生码的构造编解码复杂度较高且码率较底。如何提出码率较高并且复杂度很低的
编码策略就很有意义。将来的编码策略应结合安全问题，网络拓扑和磁盘 I /O
读写复杂度来设计，从而使再生码更为实用。
阵列码：（你来补充）
数据修复技术：
除了从纠删码本身入手降低数据修复的代价之外，从数据修复的具体过程入
手，通过优化修复时的数据读取和数据传输过程也可以进一步提高数据修复的效
率。传统的数据修复方法通常采用星型的数据传输方式，所有提供节点直接将数
据发送给新生节点，所有参与修复的节点构成一个以新生节点为中心的星型结构。
星型数据修复方法简单直观，但是其存在严重的性能瓶颈。
现有的数据修复技术大部分都基于树型数据修复方法。系统会先构建覆盖所
有参与修复的节点且以新生节点为根的修复树。在修复过程中，叶节点先将自己
的数据乘以相应的系数后将其向上传输给自己的父节点，内部节点收取其所有子
节点发送的数据并将这些数据和自己的数据进行一定的组合，然后再将组合结果
传输给自己的父节点，以此类推，直至最终到达修复树的根节点。根节点将收到
的所有数据进行组合后就可恢复出失效数据。根据修复树构造方法的不同，现有
数据修复技术可以分为两大类：一是带宽感知的数据修复技术，依据网络带宽来
构建修复树；二是拓扑感知的数据修复技术，依据网络拓扑来构建修复树。
带宽感知的数据修复技术主要考虑到大规模分布式系统往往是异构的，即节
点的性能不尽相同，节点之间的网络带宽也不同。此类方法试图根据网络带宽来
构造修复树，通过尽量利用网络中的高可用带宽达到提高数据传输速度、缩短修
复时间的目的。Li 等人证明，采用以节点间可用网络带宽作为边权重的最大生成
树作为修复树，可使数据修复时间达到最小。
拓扑感知的数据修复技术的基本思想是通过构造与物理拓扑相符的修复树，
以减少数据修复时在网络拓扑的高层链路上传输的数据量。目前，最常见的网络
拓扑仍然为多层的树型结构，由下到上依次为由机架交换机（Top – of – Rack, TOR）
组成的边界层(Edge Layer)，由聚合交换机组成的数据聚合层(Aggregation Layer)
和 由核心交换机和路由器组成的核心层(Core Layer)。树形网络的突出问题是高
层 的带宽往往非常紧张，目前部署的网络中边界层的总带宽仍然为核心层的
4~10 倍。近来有关数据中心网络负载的研究均表明，核心层链路的利用率是最
高的。因此，如果能够有效减少核心层的带宽消耗，将极大提高系统整体的性能。
带宽感知的数据修复技术虽然在理论上非常吸引人，但是存在难以克服的缺
点：（1）分布式系统中节点间的带宽是实时动态变化的，测试成本高且难以获得
精确的结果；（2）该类技术只是将数据传输导向到较快的链路，并没有降低数据
修复的负载，所以不能有效提升总体的数据修复效率。此外，很多研究工作涉及
的网络模型也与实际网络不符。相对而言，拓扑感知的数据修复技术更加具有可
操作性。但是，目前这类方法也存在比较明显的缺点。需要由交换机完成修复过
程中的数据合并，交换机需要支持数据运算，也需要设计专门的底层通讯协议。
这些问题限制了拓扑感知的数据修复技术在实际系统中的应用。（网络距离和中
心节点）。
4.3 数据更新
数据更新的挑战主要在于如何降低数据读写量和数据传输量。在基于多副本
容错的数据更新中，仅需用新的数据依次覆盖各个副本中的原数据即可。在基于
纠删码容错的数据更新中，需要先将数据块中校验块中更新部分的原数据读取出
来，重新计算相应的校验数据，然后再写入。在纠删码容错中一个数据块关联的
校验块较多，需要更新的编码块也更多，这必将产生较大的数据读写量和数据传
输量，直接影响到数据更新即覆盖写操作的性能。此外，更新过程中节点也可能
失效，造成部分数据已更新而其余部分未更新，从而导致数据不一致。因此，保
证数据的一致性也是纠删码容错技术中数据更新的主要挑战之一。
纠删码中一个数据块关联着较多的校验块，导致数据更新需要同时更新较多
的块，不仅需要大量的数据传输和写入，也使保持数据的一致性面临挑战。依据
更新方式，可将现有纠删码容错技术中的数据更新方法分为 3 种：替换式更新方
法、追加式更新方法和混合式更新方法。
替换式更新方法直接用新的数据覆盖原有数据，完成对数据块和校验块的更
新后才返回更新成功。替换式更新方法能够保证数据块与校验块实时更新，对提
高系统的性能有重要作用。数据块的实时更新能够保证应用访问到的数据始终是
最新的，有利于提高应用运行的效率和准确性。校验块的实时更新能够保证访问
的校验数据始终是最新的，有利于提高数据修复的性能。但是，替换式更新方法
存在数据读写量大和数据传输量大等不足，对数据更新效率产生显著影响。
追加式更新方法先将新数据以日志的形式追加在原始数据块之后，将新数据
与原数据的差值以日志的形式追加在校验块之后；一段时间之后或需要访问新的
数据块或校验块时再将追加的数据与原数据合并。相比于替换式更新方法，追加
式更新方法避免了数据更新过程中对原校验数据的读取，追加式的写入也将随机
写转化为了顺序写，这些都有利于提高数据更新的效率。但是，追加式更新方法
存在存储空间消耗较多和数据访问性能较差等不足：(1)追加式更新方法需要同
时保存原数据和新数据与原数据的差值，这必然会消耗更多的存储空间。当数据
更新频繁发生时，该问题会更加严重；(2)经过更新后，原来数据块中连续的数据
将随机地分布在日志中，导致无法顺序读取数据，明显影响了数据访问的效率。
此外，访问校验块需要先合并数据，这影响了数据修复的性能。
混合式更新方法是替换式更新方法和追加式更新方法的结合。具体来讲，混
合式更新方法采用替换式更新方法对数据块进行实时更新，同时采用追加式更新
方法对校验块进行延迟更新。相比于追加式更新方法，混合式更新方法对数据块
的实时更新使得对数据块的读取可以顺序进行，提高了数据读取效率，也一定程
度上降低了存储空间的消耗。但是，混合式更新方法对数据块的写操作是随机的，
影响了数据更新的效率。在不考虑数据合并的情况下，混合式更新方法的数据读
写量和传输量与追加式更新方法完全相等。此外，由于在访问校验块时仍然需要
先合并数据，混合式更新方法也同样存在数据修复性能差等不足。
5. 其它优化方案
5.1 混合使用多种纠删码
不同纠删码具有不同的存储空间开销和数据修复开销。一般情况下，存储空
间开销越高的纠删码其数据修复开销越低；反之亦然。混合使用多种纠删码可以
同时发挥多种纠删码的优势。Xia 等人提出通过跟踪数据的访问频率来动态调整
纠删码的参数，以达到既降低存储空间开销又提高失效数据访问速度的目的。有
些纠删码存储空间利用率较高，但数据修复速度很慢；有些纠删码存储空间利用
率较低，但是数据修复速度较快。我们知道，对系统中数据的访问往往是不均衡
的．有些数据很“热”，经常被访问；有些数据则很“冷”，很少被访问。数据的
“冷”和“热”也是动态变化的。当数据较“热”的时候使用存储空间开销较大
但数据修复较快的纠删码；当数据较“冷”的时候则使用数据修复较慢但存储空
间开销较低的纠删码。这样整体上既能保证较快的失效数据访问速度也能保持较
低存储空间开销。但是，如果使用完全不同种类的纠删码，每次动态转换都相当
于完全重新进行了一次编码，成本极高。较好的方法是在同一种纠删码的不同参
数之间转换，这样可以减少转换需要重新产生的校验数据以及数据的读取和传
输。
除了多种纠删码混合使用，多副本也经常和纠删码一起使用。最常见的使用
方式是先用多副本保存新产生的数据，过一段时间后再转换为纠删码。这种方式
不仅简化了编码实现，也提高了数据的访问速度，因为新产生的数据往往是被频
繁访问的“热”数据。HDFS – RAID、微软的云存储系统 WAS、百度云盘的存
储系统 Atlas 和阿里巴巴的 TFS 等系统都使用了这种方式。另外一种常见的混
合使用方式是，用多副本保存那些被频繁访问、对性能有重大影响且规模小的数
据，用纠删码保存规模庞大的数据。
6. 未来展望
关于大规模分布式存储中纠删码容错技术，未来值得进一步研究的方向主要
包括以下几个方面。
（1）同步编码实现技术
现有的编码实现方法都是异步编码，利用多副本技术来保证编码之前的数据
可靠性。在编码之前，数据的多个副本同时提供服务，可以获得更高的访问吞吐
率，这对那些需要对数据进行大量分析计算的存储系统具有较大意义。但是，对
于无需进行大量运算的系统，比如向用户提供文件存储服务的个人云盘、提供视
频流或视频分享的视频存储系统等，由于访问瓶颈存在于互联网，异步编码中的
多个副本无法有效提高用户的访问速度，并存在较为严重的资源浪费。因此，有
必要研究同步编码实现技术，在数据存储时就立刻进行编码，避免复制数据占用
大量磁盘和网络资源。
（2）低冗余再生码设计
再生码能够显著降低数据修复开销，但是其存储开销较大。现有的关于再生
码的研究工作都是在一定数据修复开销的前提下，大致估算存储空间消耗，然后
再构造具体编码。但是以存储空间利用率为前提，研究再生码数据修复开销的下
界，并进一步构造具体的再生码，也是极具挑战的研究工作。从这个思路出发，
就有可能设计出兼顾存储开销和数据修复开销的再生码。
（3）数据失效预测技术
较高的数据修复开销一直是纠删码在大数据存储中面临的一个重大挑战。设
计新的纠删码和数据修复技术可以在一定程度上解决这些问题，但是无法根本解
决问题。Ma 等人对磁盘失效预测的研究为解决这个挑战指出了一个新的有效思
路。如果能够预测节点或磁盘的失效，就可以提前复制其中的数据，避免失效后
的数据修复．根据我们的初步估算，即使失效预测的准确率只有 50%，也可将数
据修复开销降低 50%。
《基于分组码的跳跃纠删码》
针对纠删码中分组码多组之间关联性差导致的容错率低等问题，本文基于分
组码的思想提出一种跳跃纠删码--跳跃局部重构码。通过将初始数据分组并且在
每组选取单块数据跳跃再生成校验块来加强组间联系，以提升容错率、容错能力
以及降低重构开销等不同性能，并且可以权衡存储开销与其他性能以满足分布式
系统的不同需求。此外，本文通过改变跳跃局部重构码自身参数来对比性能变化，
并且与其他常用类型纠删码进行对比实验分析。
JLRC 码中有四个参数(