纠删码技术在vivo存储系统的演进【上篇】

发布时间：2025-11-02 21:58:08 来源：科技前瞻 作者：IT科技类资讯

本文借友商轮值CEO 于2020年8月28日在长沙“数学促进企业创新发展论坛”上分享的纠删《后香农时代，数学决定未来发展的码技边界》【85】进行开篇，发言提出了后香农时代，术v上篇ICT信息产业面向数学的存储系十大挑战性问题，其中就有一项“高效的演进纠删码问题”，虽然这个问题的纠删提出背景是出于通信编码领域，但对于纠删码在存储领域的码技使用同样面临着具大的机遇与挑战。

图1：纠删码问题挑战

针对纠删码的术v上篇研究分为两派：

本次分享的主题“纠删码技术在vivo存储系统的演进”，分为上下两篇：

图2：本文的组织结构

注：本文当中有大量的专业术语，不可能所有术语都去作个解释，因此针对不懂的有些术语可以自行去搜索相关含义

一、相关背景

分布式存储系统为了降低成本往往采用大量廉价通用的服务器提供服务，然而这些服务器的磁盘的可靠性是个很大的问题，云服务器其平均寿命在2-7年，还受外部环境因素的影响，受限于其机械构造，磁盘会发生磁盘故障、扇区故障和不可检测磁盘故障等。因此，分布式存储系统为了提高原始数据的可靠性，副本和纠删码是两种最常见的数据冗余方法。副本将原始数据复制到n份，并存储到不同的存储节点上，能够容忍任意n-1个节点失效，其缺点是存储开销大。纠删码则以计算资源换存储资源，采用了一种更高效的方式增加数据冗余，因此，纠删码成为了当前云存储的主流数据冗余方式，并且持续成为学术界和工业界在存储领域的一种研究热点。

图3：使用纠删码技术公司列表

纠删码也被称为纠错码，它将原始数据编码为数据量更大的编码数据，并能够利用编码后的部分编码数据恢复出原始数据。当有节点发生故障时，要恢复这个节点的b2b供应网数据需要读取多个节点的数据，这个过程会消耗大量的网络带宽和磁盘IO，另外解码复杂度对业务可用性和数据可靠性也有影响，解码复杂度越高，则临时修复时延就高，从而增加业务读取时延；因此，影响纠删码好坏的指标很多，主要有如下一些指标：以下指标都是以可靠性统一基准的前提下进行参考：

以应用最为广泛的【n,k】RS码【2】为例，RS的码长为n，码的维度为k，当出现有节点故障时，需要k个节点进行恢复，同时可以容忍n-k个节点的故障，这种编码也被称为最大距离可分纠删码MDS【3】，对应上述指标也就意味着相同的容错能力下RS码的存储开销小，另外RS码的码长不受限制，这也是RS码如此受欢迎的原因；而在通信领域大杀四方的LDPC【4】纠错码在存储领域应用较少，原因就是因为LDPC不满足MDS特性，容错能力不限，意味着相同的容错能力LDPC需要更大的存储开销, LDPC更多是应用在磁盘内部的冗余；而得益于早期在RAID5和RAID6中的广泛使用，具有MDS特性的阵列纠删码也被尝试着应用在分布式存储系统当中，MDS阵列码相对于RS码全是异或操作，编解码相对RS码复杂度低，但是同时相关参数有所受限，这也抑制了它在分布式存储的广泛应用；常见的阵列码有EVENODD码【5】、RDP码【6】、STAR码【7】支持3容错、Liberation码相对EVENODD更新复杂度接近理论下界【8】，ZigZag码【9】磁盘IO开销达理论下界，Blaum-Roth码【10】基于多项式环上构造的MDS阵列码，相对于RS是编解码复杂度要低些。

另外针对RS码高昂的网络修复带宽，涌现出一类再生码【11】来降低修复中所要消耗的带宽。再生码是一类通过允许节点发送编码过的数据来使得修复中可最小化修复带宽的纠删码，其可在不增加存储开销的情况下显著降低修复带宽。Dimakis等人将再生码分为两大类：MSR码【23-47】和MBR码【12,13】。MBR码是最小化修复带宽主要分为Polygonal MBR Code【14】和Product-Matrix MBR Code【15】；MSR码是在最小化存储开销下降低修复带宽，又分为精确修复码和功能修复码，精确修复码是指通过修复可修复出原始丢失数据，功能修复码则不保证，数据读取每次都需要进行解码操作。比如Hu等人提出了一种功能性MSR码F-MSR【16】，精确性MSR研究主要基于Product-Matrix MSR【26】，还有比如Butterfly码【48】、Coupled Layer Code码【38-40】等当前已经在工业界有所应用的再生码。最近又有一些工作【18,19,20】是针对跨机架带宽和机架内带宽进行区分，为最小化跨机架带宽为目标减少修复带宽。降低修复带宽还有一些其它的研究工作，比如2013年Rashmi等人提出Piggybacking框架【22】，框架以MDS码为基本码通过将子条带数据嵌入其它条带来显著降低修复带宽，Piggybacking框架的编码设计也有很多研究成果。【79-81】

针对修复节点数降低这个指标，Huang等人提出了一种局部修复码LRC【17,21】通过对传统编码数据块进行分组，并针对每组生成校验块，从而使得单块修复只需要组内节点参与修复提高修复性能。但由于引入额外存储开销，LRC没达到存储最优。但由于LRC的简易性，工业界有很多的实践反馈，因此LRC逐渐成为近年来纠删码领域的研究热点【66-78】。LRC的一个分支MRC码的研究PMDS也吸引了不少关注【49-60】，除了单节点修复相关的LRC码的构造，针对修复多个节点的LRC码【62-65)】是一个研究方向，另外，结合LRC和RC的Local Regeration Code【61】也是个研究思路。

图4：纠删码研究方向概览

二、原理解析

概念1：纠删码原理

纠删码通用由两个参数n和k来进行配置，称为(n,k)编码。在分布式系统当中，通常将数据以固定大小的块进行组织，编码时，存储系统将k个数据块进行编码生成额外的n-k = m个大小相同的校验块，这样n个数据块和校验块中有任意的磁盘节点故障，都可以通过其它的磁盘节点进行解码恢复丢失的数据。以下为纠删码的一个示意图：

图5：纠删码原理示意图

概念2：Singleton顿界

假设C是一个参数为[n,k]的线性码，则C的极小距离d≤n-k+1。以上表明一个线性码的极小距离不会“太大”，无论怎样努力，都不能够构造出一个参数为[n,k]的线性码，使得它的极小距离大于n-k+1，这个n-k+1就称为Singleton界。

概念3：MDS特性

一个参数为[n,k]的线性码C，若满足dmin(C)=n-k+1，则称该码为极大距离可分码，简称为MDS（Maximum Distance Separable）码。

概念4：系统性

系统性就是系统中存储了k个数据块可用来直接存取，如果故障的节点没包括数据块，则不影响数据的读取，系统性可降低读取时延。非系统性则在每次读取时都需要进行解码操作，读取时延相对偏大。

2.2.1 Reed-Solomon Code

RS码最早是ECC领域的一种纠错算法，RS编码算法是一种典型的系统编码，也是一种典型的MDS性质的编码。

RS码基本思想其实就是拉格朗日插值多项式，我觉得用拉格朗日插值多项式来推导RS码相对于其它文献的讲解会更清晰，下面我们简单回顾一下拉格朗日插值多项式：对于任何k阶的多项式函数f(x)=a0+a1x+a2x^2+...+akx^k，我们很容易通过任意的n+1个点(x0, f(x0)，(x1,f(x1))，... (xk,f(xk))对这个多项式进行恢复。

解码过程如下：

那么RS码是如何使用拉格朗日插值的呢？对于一个(n,k)的RS码，假设a0,a1,...ak-1在Fq域内的k个发送信号，我们在Fq中采样n个插值点x0,x1,...xn-1，则可以得到拉格朗日插值多项式为：

不难发现，前k个插值的多项式值有如下：

如果用矩阵来表示则为：

令上式的范德蒙德矩阵的逆*a向量 = b向量，则校验矩阵有如下：

【A|B】【A^-1】 a向量= 【E|BA^-1】* a向量 = 【a0,a1,...ak, c1,...cn-k】

这样就有了经典的(A Performance Evaluation and Examination of Open-Source Erasure Coding Libraries For Storage)描述Reed-Solomon码的编解码方式如下图所示：

图6：RS编解码示意图

可以看出，RS(n,k)码一个满足MDS性质的编码，当有数据丢失需要k个节点同时进行恢复，另外，允许n-k+1个节点同时数据丢失。

2.2.2 MDS Array Code

MDS阵列码是一类比较特殊的线性分组码。阵列码相对于RS码避免了有限域计算，仅通过异或运算实现纠删码。在这类码中，符号均为m维的列向量，从而每个码字都是一个m*n的二维阵列。绝大部分的阵列码都是二元阵列码，阵列码的每一列可以全是数据位也可以既有数据位也有校验位。以下为一个m=2, n = 5, k = 3的阵列码的示意图：

图7：陈列码示意图

不难看出该码的奇偶校验方程为：

（1）EVENODD Code

EVENODD码是一种允许丢双列的容错码，有两列的校验列，是继RS码后最先运用在RAID当中的码，它是一个(m-1)*(m+2)的阵列码，其中m是一个素数。第m+1列和第m+2列的编码方式如下： 

另外，对于每一个l，0<= l <= m-2，可以通过以下方式获取冗余符号：

可以看到，第m+1列校验码的构造是前m列的数据位的异或；第m+2列的校验码的构造则是通过追加沿斜率为1的对角线异或和来达到容错目的。EVENODD码推出后，针对斜率不为1引入到纠删码的研究作为EVENODD码的推广为也就不足为奇。

图8：EVENODD码示意图

（2）RDP Code

RDP码的码字结构与EVENODD码非常类似，只是比EVENODD码少了一个数据列，是一个(m-1)*(m+1)阵列码，其中m是一个素数。RDP相对于EVENODD编解码复杂度都要低不少，因此在RAID应用广泛。

RDP码的编码结构示意框图如下所示：

图9：RDP码示意图

2.2.3 Regeration Code

在讨论再生码这前我们来分析一下存储开销和修复开销的关系，从定性分析，我们很容易理解，当码率越大，存储空间效率越高，修复所需要的数据量就越大。A.G.Dimakis等人首次利用信息流图推导出存储开销与修复开销满足以下：

其中，alpha代表每个节点存储数据量，belta代表修复过程中每个参与节点传输的数据量，d代表辅助节点的个数。那么存储开销为所有节点存储量的总和。n* alpha。而修复开销是所有参与修复的存储节点所需要传输的数据量，d* belta。不难看出，alpha和belta不可能同时最小，alpha最小也就是M/k；belta最小也就是上式所有的(d-i)* belta都最小，可以求得d * belta = 2Md/(2kd-k^2+k)。

图10：再生码信息流图

（1）MSR

MSR全称为最小存储再生码Minimum Storage Regenerating码，不难理解，MSR是保证了存储消耗最小，所以MSR的存储数据块大小和失效修复带宽值计算公式如下：

具体的编码方式就不介绍了，在下一章节介绍的Clay码就是MSR的一种工业上的应用MSR码。通过公式不难看出，d越大，修复开销越小。MSR的研究方向学术界和工程界侧重点有所有同，学术界是不考虑分包数大小，为了不断逼近最小的修复带宽去尽可能设计MSR码或者固定分包数然后在固定分包数下不断的去降低修复带宽；而工程界则更多考虑设计出分包数不高但是修复带宽低的MSR码，因为需要考虑工程实现。

（2）MBR

MBR全称为最小带宽再生码Minimum Bandwidth Regenerating，不难理解，MBR是保证了单节点失效修复带宽最小，所以MBR的存储数据块大小和失效修复带宽值计算公式如下：

MBR相对于MSR实用性没有那么高，原因是因为分布式系统更多的是在存储开销最小化的情况去尽量降低修复带宽，因而MBR的研究热度没有MSR那么高。

2.2.4 Locally Repairable Code

局部修复码则是通过一类增加额外的存储来将数据修复尽可能在少量节点内完成，从而达到大大降低网络开销操作的纠删码。由于引入了额外的存储开销，局部修复码并没有达到存储最优。但是局部修复码实现简单，因此生产环境有了很多的实践，当前，LRC编码成为最近几年纠删码研究领域的一个热点研究方向。

图11：LRC码示意图

Singleton-型上界：

针对于一个(n,k,r)的局部修复码，即码长为n的码中有k个信息位和具有局部修复性r，则有一个经过证明的该码的最小距离d(C)满足上界如下：

任何一个达到这个界的局部修复码称为最优局部修复码。因此，设计达到最优局部修复的码是LRC方向的一个研究热点。

上述局部修复码只能修复一个故障节点，多个故障节点没有考虑，学术界针对多个故障节点的LRC修复引入了(n,k,r,gama)-局部修复码，针对多个故障节点修复的局部修复码满足上界如下：

2.2.5 piggyback框架

piggyback框架严格意义上是MSR的一个子集，piggyback框架的核心思想是通过扩展后MDS码的子条带数据嵌入到其他子条带的操作，在不改变原有编码结构的情况下显著降低修复带宽。

例如，以一个（4，2）MDS码如图所示，它有两个子条带，每个子条带上分别有两个信息数据，每个子条带的后两位存储该条带的数据线性组合，图左1为MDS码，图左2为piggyback编码，我们来分析一下右图1和右图2两种节点故障的情况下修复带宽的消耗情况：

（1）右图1修复：传统MDS码：任意2个节点的2个符号来修复；piggyback码：b2, b1+b2, b1+2b2+a1这三个符号可以修复a1, b1两个符号；

（2）右图2修复：传统MDS码：任意2个节点的2个符号来修复；piggyback码：b1,b1+b2, 2a2-2b2-b1这三个符号可以修复a2,b2两个符号。

图12：PiggyBack框架示意图

三、纠删码行业探索与实践

在第二大章节以经对当前纠删码几个核心领域的编码原理进行了阐述，本章则介绍这几个核心领域的纠删码在工业界的应用。基本上每种类型的纠删码都或多或少在工业界有具体的编码算法及实践经验。为了保持和第二章的顺序保持一致，本章也从RS码、阵列码、RC、LRC、PiggyBack这几个方向应用于工业界的具体编码顺序进行详细介绍。

首先是应用最为广泛，也是最成熟的RS码，当前工业界大多数的纠删码都是基于该编码实现的。虽然RS码的修复带宽一直是一个痛点，但是由于其基本上每家公司的最早的纠删码算法上线都是基于RS完成的。比如早期的Google、AWS、阿里、腾讯、华为、百度等公有云厂商。

An alternate construction of an access-optimal regenerating code with optimal sub-packetization level

butterfly是FAST 2016年的一篇论文提出的编码算法，最多可校正2个节点故障的数据丢失，算法只涉及XOR操作，性能较好。节点故障后只需要所有节点的1/2数据参数修复。由于编码操作用线相连对应符号位看起来像蝴蝶一样，如下图所示，所以取名butterfly code。

图13：Butterfly码示意图

编码方法：

首先数据符号需要转换成一个bit矩阵2^(k-1) * k记为Dk，用矩阵表示如下：

其中，A,B是2^(k-2) * (k-1)的bit矩阵，a,b则是一个包含2^(k-2)个元素的列向量。如果把 butterfly编码后的码字记为：Ck = (Dk−1 k ,...,D0 k ,H,B),则不难看出，H,B分别带为butterfly后的一个水平校验列和butterfly校验列。H,B的生成遵循如下递归准则：

如果 k = 2，那么有：

如果 k > 2，那么有：

其中，Pk带表一个包含2^k * 2^k个元素的矩阵，矩阵的副对角线元素为1，其余元素为0。下图为一个k = 4的 butterfly编码：

图14：k=4 Butterfly编码构造

Clay码是FAST 2018年的一篇论文提出的编码算法，Clay码能够将一般的MDS码转化为MSR码，Clay码包含两个特点：1 将MDS码分层处理；2 分层之间数据耦合，以（4，2）Clay码为例，为了更形象了解编码方式，将编码后的数据放在棱形柱上，其中alpha = 4，也就是有4层，原始数据如下：

图15：原始数据结构

图中被耦合的数据用黄色表示，耦合关系如上图右虚线表示，黄色数据块存储的是耦合之后的数据，也就是不再是系统码，相当于解码需要进行解耦合才能得到原始数据。

图16：CLAY编码结构

当有一个节点失效后，CLAY码的修复过程如下：

图17：CLAY修复结构

Clay 修复该节点失效只需要第二层和第三层的剩余数据块（如上图（中）所示），修复步骤如下：

简单推导可以发现其他三个节点也可以以最小开销完成数据修复。

局部可恢复码LRC是微软在2012年FAST发表的一篇论文，该论文同时也是当年FAST的best paper。核心思路就是通过引入局部校验位来辅助全局校验位进行节点故障后的修复，由于局部校验节点的存在，所以当有一个节点故障的时候可以只用局部少数节点进行恢复，而不需要全局节点进行恢复提升修复带宽。以下以（6，2，2）LRC为例进行介绍：

图18：全局&局部校验示意图

如上图所示px,py为局部校验节点，p0,p1为全局校验节点，不难看出，虽然LRC有4个校验节点，但是LRC不满足MDS性质，比如x0,x1,x2,px 4个节点全都故障，LRC无论如何校造都是无法恢复的，因为全局校验节点只有2个，而py和x0,x1,x2无关，所以无论如何都恢复不出来x0,x1,x2这三个数据节点，这种故障也称为信息论无法解码故障；虽然LRC不能容忍这种场景的4个节点故障，但是如果LRC构造得好，是可以达成其它场景的4个节点的故障，比如下图所示：

图19：4数据节点失效示意图

a图是x0,x1,p1三个节点故障，b图是x0,x1,y0,y1四个节点故障，这类故障是有可能重建的也称为信息论可解码故障。那么LRC的研究就是设计合理的编码方式来尽可能的覆盖所有信息论可解码故障场景，当LRC的构造方式覆盖了所有信息论可解码场景则称LRC码符合Maximally Recoverable（MR）性质。 (6，2，2)的校验位构造方程如下：

然后该编码构造方法需要覆盖所有理论可解码故障场景比如以下三种典型场景：

（1）4个节点全故障，平均分布在6个数据节点

这种场景则不难看出要想可求解就必需保证：

G的行列为不为0，G矩阵是奇异矩阵。

（2）px,py中有一个故障，假设是py故障，则必须有：

（3）同理如果px,py全故障，则必须有：

因此，alpha，belta的取值必须满足上述矩阵的行列式不为0。（6，2，2）LRC与（6，3）的RS对比不难发现：LRC可靠性略高，成本也略高，修复带宽几乎是原来的一半。

piggyback框架的一个典型的工业界的应用实践场景是facebook在2014年提出的，当时facebook的f4系统原本也是用（10，4）RS纠删码来降低冗余度，但是RS码的修复带宽非常高，据当时统计数据，facebook一个PB级的集群中因为节点恢复所需要消耗的网络带宽达到了180TB。所以facebook针对冷存集群提出了一种基于piggyback框架的Hitchhiker编码来降低修复带宽。

（1) Hitchhiker-XOR

传统的(10,4)的RS编码如下图左1所示，引入piggyback框架后则编码方式如下左2所示，Hitchhiker-XOR编码方式如下右1所示：

图20：Hitchhiker-XOR编码示意图

编码：4个校验单元：f1保持不变，f2引入a1,a2,a3的奇偶校验位，f3引入a4,a5,a6的奇偶校验位，f4引入a7,a8,a9,a10的奇偶校验位。

修复：当1-3有一个节点故障，则可以通过，b1-10,f1(b)中的任意10个但愿恢复出故障的bi，然后可以通过f2函数计算出f2(b)，再结合第2个子条带的第2个校验单元以及a1-a3中的2个单元一起，可以计算出ai，这样就把ai,bi修复出来了。 同理，当4-6有一个节点故障时，也是一样的，可以通过13个byte将ai,bi进行恢复。

而当7-10有一个节点故障时，则需要通过14个byte进行恢复，原因是第2个子条带的第4个校验单元是由a7,a8,a9,10四个组合，其中有一个失效，需要引入第1个子条带的3个单元才能进行恢复。

（2）Hitchhiker-XOR+

针对Hitchhiker-XOR算法，可以看到在第7-10节点故障时需要14个Bytes进行修复，XOR+通过对RS码进行适当限制来降低这一部分的开销，限制条件如下：4个校验单元的函数f需要有一个满足：ALL-XOR性质，也就是子条带数据全部进行异或操作的同时满足MDS性质。通过该限制，则两个子条带的校验单元的编码方式如下图所示：

图21：Hitchhiker-XOR+编码示意图

修复： 

不难看出，1-9节点故障时的修复是和Hitchhiker-XOR是完全一样的，只需要13个bytes进行修复，第10个节点故障时，则通过第2个子条带的1-10，13，14单元和第1条带的12单元可以恢复a10,b10，不难看出，恢复节点10也只需要13个bytes。

所以Hitchhiker-XOR+相对于Hitchhiker-XOR限制了RS码构造的条件，但进进一步降低了部分数据修复的开销。

（3）Hitchhier-NoXOR

这种编码是针对于Hitchhier-XOR+是引入了限制条件，为了消除这个限制条件，可以通过有限域运算的方式来达到Hitchhier-XOR+同样的效果，但是可以消除RS的校验生成限制，与此同时也是通过有限域运算开销来替换XOR操作。

图22：Hitchhier-NoXOR编码示意图

以上编码方式可以扩展到任意的(k,r)，对于不同的k,r参数，HH码相对传统RS码可以降低25%-45%不等的开销。

3.7 纠删码对比

（n,k）纠删码，数据大小为M，划分为k份，生成m份校验数据 k + m = n，则相关纠删码算法的相关开销和性质总结如下：

图23：纠删码算法相关维度对比

四、vivo 纠删码探索与实践

vivo对象存储的EC方案是采用RS纠删码，前面章节已经介绍过RS码是通过构造生成矩阵来编码数据块。生成矩阵可以采用范德蒙德矩阵，原因是因为范德蒙德矩阵是可逆的，另外，还有一种矩阵是也可逆矩阵那就是Cauchy矩阵，Cauchy矩阵是由两个交集为空的集合构成的矩阵，具体为：令C = [c(i,j)]m*n，有集合X = {x1,x2,...xm}，Y = {y1,y2, ...,yn}，且X交集Y={空}。矩阵C中的元素cij满足：

不难理解，如果不做优化，柯西编解码过程会充斥着大量的有限域的乘法和加法运算，为了降低复杂度，通过利用有限域任何一个GF（2^w）域上的元素都可以映射到GF(2)域上的一个二进制矩阵，例如，GF(2^3)域中的元素可以表示成GF（2）域中的二进制矩阵：

图24：GF(2^3)在GF(2)映射矩阵

其中，M ( e )的第i 列为V ( e ∗ 2^ (i − 1 )) 其中e ∗ 2^(i-1) 为G F ( 2 ^3 ) )上的乘法。

所以基于Cauchy矩阵的RS编码方案可以优化为bit-matrix为生成矩阵，原有的有限域上的乘法和加法也变成了有限域的“与运算”和“XOR”运算，从而提高编码效率。

在真正实现的时候， vivo纠删码的CRS编码和jeasure的CRS编码一样，针对bit-matrix在GF(2)有限域的与和OXR操作进行也进一步优化，就是通过将bit-matrix转化为一个schedule的方式，也就是一个五元组，其中，op操作是O,1对应是拷贝还是XOR，sd是源数据的id，sb为源数据中bit位的相对id，dd和db则为目的校验数据的id和校验数据bit位id。如下图针对一个k = 3, w = 5的bit-matrix对应的schedule操作为如下：

图25：bitmatrix的schedule操作

不难看出，通过schedule方式转化后编解码操作简化了好多，以下为一段C++代码：

图26：存储纠删码schedule代码片断

注：这里的生产环境分析章节是参照常规的业界生产环境部署规范进行假设和模拟，不代表本公司的真实生产环境。

4.2.1 IDC资源

现在很多公司为了能够防止数据中心因为某些不可抗力比如自然灾害、断电等极端情况导致整体故障而造成数据丢失和服务中断建设了多个数据中心，分布式存储服务可以通过将数据打散存储在多个不同的数据中心来保证当某个IDC故障后依然能提供稳定可靠的存储服务。纠删码技术通过将数据分块和校验码分块均匀打散到不同数据中心，实现同城容灾冗余。当某个数据中心不可用时，另外其他数据中心的数据依旧可以正常读取和写入，保障客户数据持久存储不丢失，维持客户业务数据连续性和高可用。

以下为一个同城冗余的示意图【引用自公有云多region多AZ机构】

图27：同城冗余机房示意图

4.2.2 存储资源

随着近年互联网业务的非速发展，互联网业务数据的规模及多样性也越来越复杂，各大公司的存储型服务器由于历史原因迭代过很多的版本，从4xTB到1x00TB容量不等的演进了有多种套餐类型，因此生产环境很难避免的有多种存储类型的服务器共存的情况出现，服务器的携带的HDD硬盘的块数和单盘的容量也不尽相同，单盘容量从4T到20多T不等，服务器携带的硬盘数目也从12到60多不等，还有各种其它类型的存储阵列比如JBOD产品（由多块60TB的硬盘组成的存储资源阵列）。

4.2.3 网络资源

如第1章所述，纠删码技术在海量分布式存储系统的引入为企业节省了大量的成本，但是在节约成本的同时，由于纠删码技术特点也带了带宽成本的上升，基于纠删码冗余的分布式系统在出现节点或硬盘故障时，需要多个节点进行同时恢复，这就需要大量的网盘带宽，而且以（n,k）RS码为例，1个RS码的节点故障，需要n个节点进行恢复，而副本技术的系统只需要1个节点参与，相当于纠删码技术的系统网络带宽放大了n倍速。因此，在IDC内部和IDC机房之间的带宽就成为了纠删码技术实施的关键因素。

以下为业界某司的IDC之间的网络拓扑架构如下：【引用自公有云多region多AZ机构】

图28：业界IDC带宽拓扑架构

而由于成本上的考虑，往往数据中心与数据中心之间的专线带宽都不会太高，但是传统的纠删码技术在提供低冗余度和高可靠的同时带来的是大理的修复带宽的成本，因此，跨IDC之间的纠删码技术不得不考虑IDC之间的带宽不大这个因素。

4.2.4 业务特性

4.3.1 纠删码优化思路

4.3.2 可靠性模型设计

在优化思路我们提到引入可靠性评估模型来对集群进行近实时的预估，那么可靠性模型如何预估是合理的？当前并没有一个统一的可靠性评估方案，不过学术界基本都是基于马尔可夫链的MTTDL模型来进行EC的可靠性计算，工业界就没有特别统一的可靠性评估方案，在调研了行业内相关方案后我们的可靠性模型主要是基于MTTDL马尔可夫链模型再结合我之前分享的一篇【分布式存储系统的可靠性估算】形成特有的分布式存储可靠性模型估算方案。这套方案是结合了两种可靠性估算最合理的部分逻辑：MTTDL模型的理论严谨性 + 集群级磁盘故障的组合概率引入的必要性。

在介绍可靠性模型之前，我们先来看几个概念如下图所示：

图29：系统故障处理流流程【时间线】

（1）Markov可靠性模型

Markov可靠性模型是基于MTTDL进行预估的，Markov可靠性模型是基于下图来进行状态转移的：

图30：马尔科夫链的故障状态转移模型

初始状态为1状态，1状态为n块磁盘都没有故障的概率为1-n* ramda，从状态1转移到状态2则是有n*ramda概率，状态2恢复到1状态则由u决定，状态2转移到状态3的概率为1-(n-1)* ramda，则不难计算出维持2状态的概率如上图所示：

本文不对马尔科夫链状态转移进行详细推导，仅给出最终的MTTDL的简化版计算公式如下：

（2）其它可靠性模型

Markov可靠性模型是把所有磁盘都用在了数据的条带化处理，但是真实的线上环境集群可能非常庞大，整个集群的节点数会远大于进行纠删码的n的大小，那么从集群角度看可靠性如何估算呢？我曾经在21年有发表过一篇外发期刊【分布式存储系统可靠性：系统量化估算】，这篇文章就是以生产环境以集群部署的角度进行分析分布式存储系统的可靠性如何估算，这篇文章相对于Markov可靠性模型一个最大的借鉴意义是它把集群内的一个数据的条带化组合引入到了可靠性估算，因此，新的可靠性估算模型可以结合Markov可靠性模型和集群条带化组合比例进行设计，更加具体的设计方案会在【纠删码技术在vivo存储系统的演进-下篇】中介绍。

4.3.3 多融合EC方案设计

根据对IDC资源、服务器资源、业务特性、网络资源的分析，结合可靠性评估近实时系统的支撑，我们在原有的8+4 CRS纠删码算法的基础上进行优化，将整体的EC策略分为两种如下图所示：

图31：多融合EC方案架构图

跨AZ-EC策略

核心业务数据有跨AZ存储需求进行机房数据容灾，但是同时也带来在节点故障情况下有跨机房网络带宽的影响，因此EC策略是LRC+RS+并行修复+MSR结合的EC方式，针对不同的场景有不同的优化措施：

为了能描述清楚我们的策略，我们以（16，4，4）4机房，4个局部校验块，4个全局校验块，16个数据块【如下图所示】为例来说明：

图32：（16，4，4）LRC编码拓扑

我们假设局部校验块P1、P2、P3、P4的构造按如下所示：

同样按RS码构造方式，我们假设Q1、Q2、Q3、Q4的构造按如下所示：

接下来我们来分析一下不同场景下的恢复情况：

具体算法的详细细节会在后续的【纠删码技术在vivo存储系统的演进-下篇】介绍，整体思路就是全局RS+并行修复结合局部MSR最小带宽修复的策略来达到多AZ数据可靠性保障的目标。

五、总结

云存储领域针对纠删码技术的研究截止到现在仍然是学术界和工业界研究的热点，如何能降低网络的修复带宽，降低存储开销同时保证数据的可靠性的同时编解码算法又能工程落地，编解码复杂度又偏低，这些维度的考量衍生了各式各样的纠删码编码技术，vivo也在纠删码技术根据生产环境可落地的前提下在传统RS码的基础上引入并行修复以利用LRC+MSR局部校验块的组合来降低传统LRC在生产环境上运用导致的跨机房带宽开销，从而较低的跨机房带宽开销为高条带低冗余度的EC策略提供了保障。随着业务的发展，数据的存储开销成本会越来越明显，因此，针对纠删码技术的研究会是一个长期的过程，本人也会时刻关注学术界和工业界的动态，结合IDC、服务器、网络及业务的特性进行创新和优化为业务持续助力。

参考文献：

Reed I S, Solomon G. Polynomial Codes over Certain Finite Fields. Journal of the society for industrial and applied mathematics, 1960, 8(2):300-304Plank J S, Ding Y. Note: Correction to the 1997 tutorial on Reed-Solomon coding.Software: Practice and Experience, 2005, 35(2):189-194Shokrollahi A. LDPC codes: An Introduction. Technical report, 2003.Blaum M, Brady J, Bruck J, et al. EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures. IEEE Transactions on computers (TOC), 1995, 44(2):192-202.Corbett P, English B, Goel A, et al. Row-diagonal Parity for Double Disk Failure Correction. in: Proceedings of The 2nd USENIX Conference on File and Storage Technologies (FAST04), Berkeley, CA, USA, March 31 - April 2, 2004, 1-14.Huang C, Xu L. STAR: An Efficient Coding Scheme for Correcting Triple Storage Node Failures. IEEE Transactions on Computers (TOC), 2008, 57(7):889-901.James S. Plank: The RAID-6 Liberation Codes. FAST 2008: 97-110I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616,2013.Blaum M, Roth R, New array codes for multiple phased burst correction. IEEE Trans on Inform Theory, 1993,39(1): 66 ~ 77.A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE Trans. Inf. Theory,vol. 56, no. 9, pp. 4539–4551, Sep. 2010.M. N. Krishnan and P. V. Kumar, “On MBR codes with replication,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016, pp. 71–75.N. B. Shah, “On Minimizing Data-Read and Download for Storage-Node Recovery,” IEEE Communications Letters, vol. 17, no. 5, pp. 964–967, 2013.K. Rashmi, N. Shah, P. Kumar, and K. Ramchandran, “Explicit construction of optimal exact regenerating codes for distributed storage,” in Proc. 47th Annu. Allerton Conf. Communication, Control, and Computing, Urbana-Champaign, IL, Sep. 2009, pp. 1243–1249.K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239, 2011.Y. Hu, H. C. H. Chen, P. P. C. Lee, and Y. Tang, “NCCloud: applying network coding for the storage repair in a cloud-of-clouds,” in Proc. 10th

USENIX conference on File and Storage Technologies, San Jose, CA, USA,2012, p. 21.Huang C, Simitci H, Xu Y, et al. Erasure Coding in Windows Azure Storage. in: Proceedings of USENIX Annual Technical Conference (ATC), Boston, MA, USA, June, 2012, USENIX.Hu Y, Li X, Zhang M, et al. Optimal repair layering for erasure-coded data centers: From therory ot practive. ACM Transactions on Storage (TOS), 2017, 13(4):33.Rashmi K, Nakkiran P, Wang J, et al. Having Your Cake and Eating It Too: jonintly Optimal Erasure Codes for I/O, Storage, and Network-bandwidth. in: Proceedings of USENIX Conference on File and Storage Technologies (FAST), Santa Clara, CA, USA, February, 2015, USENIX, 81-94.Hou H, Lee P, Shum K, et al. Rack-aware regenerating codes for data centers. IEEE Transactions Information Theory, 2019,65(8):4730-4745.Sathiamoorthy M, Asteris M, Papailiopoulos D, et al. XORing Elephants: Novel Erasure Codes for Big Data. in: Proceedings of VLDB Endowment. VLDB, March, 2013, 325-336.RASHMI K, SHAN N B, RAMCHANDRAN K. A Piggybacking Design Framework for Read and Download-Efficient Distributed Storage Codes[J]. IEEE Transactions on Information Therory, 2017,63(9):5802-5820.N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and

Code Constructions,” IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2134–2158, Apr. 2012.Y.WuandA.G.Dimakis,“Reducingrepairtrafficforerasurecoding-basedstorageviainterferencealignment,”Proc.IEEEInternationalSymposium on Information Theory, Seoul, Korea, June 2009, pp. 2276–2280.C.SuhandK.Ramchandran,“Exact-repairMDScodeconstructionusinginterferencealignment,”IEEETrans.Inf.Theory,vol.57,no.3,pp.1425–1442,Mar. 2011.K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239, Aug. 2011.S. J. Lin, W. H. Chung, Y. S. Han, and T. Y. Al-Naffouri, “A Unified Form of Exact-MSR Codes via Product-Matrix Frameworks,” IEEE Trans Inf

Theory, vol. 61, no. 2, pp. 873–886, Feb 2015.D. Papailiopoulos, A. Dimakis, and V. Cadambe, “Repair Optimal Erasure Codes through Hadamard Designs,” IEEE Trans. Inf. Theory, vol. 59, no. 5,pp. 3021–3037, 2013.V.Cadambe,S.A.Jafar,H.Maleki,K.Ramchandran,andC.Suh,“AsymptoticInterferenceAlignmentforOptimalRepairofMDSCodesinDistributed

Storage,” IEEE Trans. Inf. Theory, vol. 59, no. 5, pp. 2974–2987, 2013.I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616,2013.Z. Wang, I. Tamo, and J. Bruck, “On codes for optimal rebuilding access,” in Proc. 49th Annual Allerton Conference on Communication, Control, and Computing, Sept 2011, pp. 1374–1381.V. R. Cadambe, C. Huang, J. Li, and S. Mehrotra, “Polynomial length MDS codes with optimal repair in distributed storage,” in Proc. Forty Fifth Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA*, 2011, pp. 1850–1854.Z. Wang, I. Tamo, and J. Bruck, “Long MDS codes for optimal repair bandwidth,” in Proc. IEEE International Symposium on Information Theory,Cambridge, MA, USA, 2012, pp. 1182–1186.I. Tamo, Z. Wang, and J. Bruck, “Access Versus Bandwidth in Codes for Storage,” IEEE Trans. Inf. Theory, vol. 60, no. 4, pp. 2028–2037, 2014.S. Goparaju, I. Tamo, and A. R. Calderbank, “An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes,” IEEE Trans. on Inf.Theory, vol. 60, no. 5, pp. 2770–2779, 2014.B. Sasidharan, G. K. Agarwal, and P. V. Kumar, “A high-rate MSR code with polynomial sub-packetization level,” in Proc. IEEE International Symposium on Information Theory, 2015, pp. 2051–2055.A.S.Rawat,O.O.Koyluoglu,andS.Vishwanath,“Progressonhigh-rateMSRcodes:Enablingarbitrarynumberofhelpernodes,”in Proc.Information Theory and Applications Workshop, La Jolla, CA, USA, 2016, pp. 1–6.S. Goparaju, A. Fazeli, and A. Vardy, “Minimum Storage Regenerating Codes for All Parameters,” IEEE Trans. Inf. Theory, vol. 63, no. 10, pp.6318–6328, 2017.G. K. Agarwal, B. Sasidharan, and P. V. Kumar, “An alternate construction of an access-optimal regenerating code with optimal sub-packetization level,” in Proc. Twenty First National Conference on Communications, Mumbai, India, 2015, pp. 1–6.N. Alon, “Combinatorial nullstellensatz,” Combinatorics, Probability and Computing, vol. 8, no. 1-2, pp. 7–29, 1999.N. Raviv, N. Silberstein, and T. Etzion, “Constructions of High-Rate Minimum Storage Regenerating Codes Over Small Fields,” *IEEE Trans. Inf.Theory, vol. 63, no. 4, pp. 2015–2038, 2017.M. Ye and A. Barg, “Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth,” IEEE Trans. Inf. Theory, vol. 63, no. 4,pp. 2001–2014, 2017.——, “Explicit Constructions of Optimal-Access MDS Codes With Nearly Optimal Sub-Packetization,” IEEE Trans. Inf. Theory, vol. 63, no. 10, pp.6307–6317, 2017.B. Sasidharan, M. Vajha, and P. V. Kumar, “An Explicit, Coupled-Layer Construction of a High-Rate MSR Code with Low Sub-Packetization Level,Small Field Size and All-Node Repair,” CoRR, vol. abs/1607.07335, 2016.J. Li, X. Tang, and C. Tian, “A generic transformation for optimal repair bandwidth and rebuilding access in MDS codes,” in Proc. IEEE International**Symposium on Information Theory, Aachen, Germany, June 2017, pp. 1623–1627.S. B. Balaji and P. V. Kumar, “A tight lower bound on the sub-packetization level of optimal-access MSR and MDS codes,” CoRR, Accepted at ISIT**2018, vol. abs/1710.05876, 2017.M. Vajha, S. B. Balaji, and P. V. Kumar, “Explicit MSR Codes with Optimal Access, Optimal Sub-Packetization and Small Field Size for d =k + 1, k + 2, k + 3,” CoRR, vol. abs/1804.00598, 2018.E.E.Gad,R.Mateescu,F.Blagojevic,C.Guyot,andZ.Bandic,“Repair-optimalMDSarraycodesoverGF(2),”inProc.IEEEInternationalSymposium on Information Theory, Istanbul, Turkey, 2013, pp. 887–891.P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the Locality of Codeword Symbols,” IEEE Trans. Inf. Theory, vol. 58, no. 11, pp. 6925–6934,2012.S. B. Balaji and P. V. Kumar, “On partial maximally-recoverable and maximally-recoverable codes,” in Proc. IEEE International Symposium on

Information Theory, Hong Kong, 2015, pp. 1881–1885.M. Chen, C. Huang, and J. Li, “On the maximally recoverable property for multi-protection group codes,” in IEEE International Symposium on Information Theory, June 2007, pp. 486–490.M. Blaum, J. L. Hafner, and S. Hetzler, “Partial-MDS Codes and Their Application to RAID Type of Architectures,” IEEE Trans. Inf. Theory, vol. 59, no. 7, pp. 4510–4519, 2013.G. Calis and O. O. Koyluoglu, “A General Construction for PMDS Codes,” IEEE Communications Letters, vol. 21, no. 3, pp. 452–455, 2017.R. Gabrys, E. Yaakobi, M. Blaum, and P. H. Siegel, “Constructions of partial MDS codes over small fields,” in Proc. IEEE International Symposium on Information Theory, Aachen, Germany, 2017, pp. 1–5.P. Gopalan, C. Huang, B. Jenkins, and S. Yekhanin, “Explicit Maximally Recoverable Codes With Locality,” IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5245–5256, 2014.G. Hu and S. Yekhanin, “New constructions of SD and MR codes over small finite fields,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016, pp. 1591–1595.J. Chen, K. W. Shum, Q. Yu, and C. W. Sung, “Sector-disk codes and partial MDS codes with up to three global parities,” in Proc. IEEE International Symposium on Information Theory, Hong Kong, 2015, pp. 1876–1880.M. Blaum, “Construction of PMDS and SD codes extending RAID 5,” CoRR, vol. abs/1305.0032, 2013.M. Blaum, J. S. Plank, M. Schwartz, and E. Yaakobi, “Construction of Partial MDS and Sector-Disk Codes With Two Global Parity Symbols,” IEEE Trans. Inf. Theory, vol. 62, no. 5, pp. 2673–2681, 2016.V.LalithaandS.V.Lokam,“Weightenumeratorsandhighersupportweightsofmaximallyrecoverablecodes,”inProc.53rdAnnualAllertonConference on Communication, Control, and Computing, Monticello, IL, USA, 2015, pp. 835–842.G. M. Kamath, N. Prakash, V. Lalitha, and P. V. Kumar, “Codes With Local Regeneration and Erasure Correction,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4637–4660, 2014.Cai H, Miao Y, Schwartz M, et al. On optimal locally repairable codes with super-linear length. IEEE Trans Inform Theroy, 2020, 66: 4853-4868.Chen B, Fang W, Xia S, et al. Constructions of optimal (r,sigma) locally repairabl codes via constacyclic codes. IEEE Trans Commun, 2019, 67: 5253-5263.Chen B, Xia S, Hao J, et al. Constructions of optimal cyclic (r,sigma) locally repairable codes. IEEE Trans Inform Theory, 2018, 64:2499-2511.Fang W, Fu F. Optimal cyclic (r,sigma) locally repairable codes with unbounded length. Finite Fields Appl, 2020,63:101650.A. Agarwal, A. Barg, S. Hu, A. Mazumdar, and I. Tamo, “Combinatorial alphabet-dependent bounds for locally recoverable codes,” IEEE Trans. Inf. Theory, vol. PP, no. 99, pp. 1–1, 2018.I. Tamo, A. Barg, S. Goparaju, and A. R. Calderbank, “Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes,” CoRR, vol. abs/1603.08878, 2016.S. Goparaju and A. R. Calderbank, “Binary cyclic codes that are locally repairable,” in Proc. IEEE International Symposium on Information Theory, Honolulu, HI, USA, 2014, pp. 676–680.A. Zeh and E. Yaakobi, “Optimal linear and cyclic locally repairable codes over small fields,” in Proc. IEEE Information Theory Workshop, Jerusalem, Israel, 2015, pp. 1–5.I. Tamo, A. Barg, and A. Frolov, “Bounds on the Parameters of Locally Recoverable Codes,” IEEE Trans. Inf. Theory, vol. 62, no. 6, pp. 3070–3083, 2016.A. Barg, I. Tamo, and S. Vldu, “Locally Recoverable Codes on Algebraic Curves,” IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 4928–4939, 2017.X. Li, L. Ma, and C. Xing, “Construction of asymptotically good locally repairable codes via automorphism groups of function fields,” CoRR, vol. abs/1711.07703, 2017.M.Y.NamandH.Y.Song,“BinaryLocallyRepairableCodesWithMinimumDistanceatLeastSixBasedonPartialt-Spreads,”IEEECommunications Letters, vol. 21, no. 8, pp. 1683–1686, Aug 2017.N. Silberstein and A. Zeh, “Optimal binary locally repairable codes via anticodes,” in Proc. IEEE International Symposium on Information Theory, Hong Kong, 2015, pp. 1247–1251.J. Hao, S. T. Xia, and B. Chen, “Some results on optimal locally repairable codes,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016, pp. 440–444.M. Shahabinejad, M. Khabbazian, and M. Ardakani, “A Class of Binary Locally Repairable Codes,” IEEE Transactions on Communications, vol. 64, no. 8, pp. 3182–3193, 2016.J. Hao, S. T. Xia, and B. Chen, “On optimal ternary locally repairable codes,” in Proc. IEEE International Symposium on Information Theory, Aachen, Germany, 2017, pp. 171–175.J. Hao and S. Xia, “Bounds and Constructions of Locally Repairable Codes: Parity-check Matrix Approach,” CoRR, vol. abs/1601.05595, 2016. X. Li, L. Ma, and C. Xing, “Optimal locally repairable codes via elliptic curves,” CoRR, vol. abs/1712.03744, 2017.KMM,et,al：An Efficient Piggybacking Design Framework with Sub-packetization l 􏲐 r for All-Node RepairFrancisco Maturana and K. V. Rashmi, et, al：Bandwidth Cost of Code Conversions in the Split RegimeHanxu Hou, et, al：New Piggybacking Codes with Lower Repair Bandwidth for Any Single-Node FailureHan Cai,et,al: On Optimal Locally Repairable Codes and Generalized Sector-Disk CodesA “Hitchhiker’s” Guide to Fast and Efficient Data Reconstruction in Erasure-coded Data CentersMean time to meaningless: MTTDL, Markov models, and storage system reliability“后香农时代，数学将决定未来发展的边界”

相关文章