乐趣区

关于分布式存储:纠删码技术在vivo存储系统的演进上篇

jiezi

作者：vivo 互联网服务器团队 - Gong Bing

本文将学术界和工业界的纠删码技术的外围研究成果进行了相应的梳理，而后针对公司线上存储系统的纠删码进行剖析，联合互联网企业通用的 IDC 资源、服务器资源、网络资源、业务个性进行剖析对原有纠删码技术进行优化和微翻新，提出了交融 EC 整体计划以及可落地的 RS+LRC+ 两头后果优化 + 并行修复跨 AZ 带宽设计方案，为后续的工程实际提供重要原理和架构撑持。

引言

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

图 1：纠删码问题挑战

针对纠删码的钻研分为两派：

  • 一派则是纯理论界针对纠删码编码技术在编解码复杂度、修复带宽及磁盘 IO、存储开销等维度进行钻研提出新的实践齐备性证实过的纠删码，这类钻研可能思考更多的是实践齐备性的证实；不会思考工程界的实现复杂度等状况；
  • 一派是不扭转编码实践，利用纠删码联合生产环境进行适当革新（多 AZ、异构服务器、大条带、跨 rack 等）再联合试验数据在修复开销、存储开销、可靠性等指标来证实价值。这两派的钻研相辅相成独特推动纠删码技术在分布式存储畛域的倒退。

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

  • 上篇偏重介绍和剖析纠删码技术的演进历程、外围纠删码技术的原理和以及工业界存储产品当中的纠删码技术的摸索与实际，最初介绍 vivo 存储系统在纠删码技术上的一些摸索；
  • 下篇重点开展介绍存储团队在纠删码畛域的研究成果及纠删码研究成果在 vivo 存储系统中的实际，与工业界存储产品中的纠删码相干指标进行全方位比照，以及将来的一些布局。

图 2：本文的组织构造

注：本文当中有大量的专业术语，不可能所有术语都去作个解释，因而针对不懂的有些术语能够自行去搜寻相干含意

一、相干背景

1.1 钻研意义

分布式存储系统为了降低成本往往采纳大量便宜通用的服务器提供服务，然而这些服务器的磁盘的可靠性是个很大的问题，其平均寿命在 2 - 7 年，还受外部环境因素的影响，受限于其机械结构，磁盘会产生磁盘故障、扇区故障和不可检测磁盘故障等。因而，分布式存储系统为了进步原始数据的可靠性，正本和纠删码是两种最常见的数据冗余办法。正本将原始数据复制到 n 份，并存储到不同的存储节点上，可能容忍任意 n - 1 个节点生效，其毛病是存储开销大。纠删码则以计算资源换存储资源，采纳了一种更高效的形式减少数据冗余，因而，纠删码成为了以后云存储的支流数据冗余形式，并且继续成为学术界和工业界在存储畛域的一种钻研热点。

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

1.2 钻研现状

纠删码也被称为纠错码，它将原始数据编码为数据量更大的编码数据，并可能利用编码后的局部编码数据复原出原始数据。当有节点产生故障时，要复原这个节点的数据须要读取多个节点的数据，这个过程会耗费大量的网络带宽和磁盘 IO，另外解码复杂度对业务可用性和数据可靠性也有影响，解码复杂度越高，则长期修复时延就高，从而减少业务读取时延；因而，影响纠删码好坏的指标很多，次要有如下一些指标：以下指标都是以可靠性对立基准的前提下进行参考：

  • 【编码复杂度】编码复杂度决定了数据写入的时延
  • 【解码复杂度】解码复杂度决定了读取的时延以及节点故障时数据长期修复及永恒修复的时延
  • 【修复网络带宽】节点故障时数据修复所需耗费的整体网络带宽，这个指标十分要害
  • 【修复磁盘 IO】磁盘 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：纠删码钻研方向概览

二、原理解析

2.1 基础知识介绍

概念 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 经典纠删码介绍

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 这几个方向利用于工业界的具体编码程序进行具体介绍。

3.1 RS：CRS

首先是利用最为宽泛，也是最成熟的 RS 码，以后工业界大多数的纠删码都是基于该编码实现的。尽管 RS 码的修复带宽始终是一个痛点，然而因为其基本上每家公司的最早的纠删码算法上线都是基于 RS 实现的。比方晚期的 Google、AWS、阿里、腾讯、华为、百度等私有云厂商。

3.2 阵列码：HashTag

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

3.3 MSR：Butterfly

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 编码结构

3.4 MSR：Clay

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

图 15：原始数据构造

图中被耦合的数据用黄色示意，耦合关系如上图右虚线示意，黄色数据块存储的是耦合之后的数据，也就是不再是零碎码，相当于解码须要进行解耦合能力失去原始数据。

图 16：CLAY 编码构造

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

图 17：CLAY 修复构造

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

  • 两个耦合的数据块(b\_3,d\_1) 和[b\_3, d\_1] 解耦失去 b3 和 d1，如上图（右）；
  • 第二层通过 b1，b3 的 MDS 解码失去 b\_0, b\_2，第四层 MDS 解码失去 d\_0，d\_2；
  • 利用第二层中[a\_2, b\_0] 和步骤 2 失去的 b\_0 失去 a\_2，同理失去 c_2。

简略推导能够发现其余三个节点也能够以最小开销实现数据修复。

3.5 LRC：azure、yottachain LRC

部分可复原码 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 可靠性略高，老本也略高，修复带宽简直是原来的一半。

3.6 piggyback：Hitchhiker

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 纠删码摸索与实际

4.1 线上 EC 计划介绍

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 生产环境剖析

注：这里的生产环境剖析章节是参照惯例的业界生产环境部署标准进行假如和模仿，不代表本公司的实在生产环境。

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 业务个性

  • 对象存储业务特点 1 ：通常接入对象存储的大规模业务的更新的操作比拟少，因而原有的更新的操作耗费带宽老本高的痛点能够不思考；
  • 对象存储业务特点 2 ：通常接入对象存储业务在线场景和离线场景辨别比拟显著；大存储业务出现冷数据趋势；
  • 对象存储业务特点 3 ：互联网行业的数据类型丰盛，个别对跨 AZ 和不跨 AZ 的需要有所不同，数据可靠性的要求各有不同；可用性指标各有不同。

4.3 vivo 新纠删码计划

4.3.1 纠删码优化思路

  • 基于纠删算法思考：通过对学术界和工业界的整体调研思考实现复杂度和成果发现还是 RS 码还是以后工业界纠删码的支流，特地是对 RS 码引入并行修复后十分的适宜升高跨 IDC 之间的带宽耗费；能够将大部分的带宽耗费收敛到 IDC 外部；
  • 基于机房资源思考：基于多数据中心的数据分布思考，纠删码能够思考引入 LRC，在数据中心外部引入部分校验块来进行数据中心外部的疾速修复从而进步整体可靠性；
  • 基于业务个性思考：依据互联网业务的通用个性剖析能够将离线在线存储集群进行拆散；以及数据可靠性要求进行布局 EC 集群，比方不思考机房容灾的业务能够在同一个数据中心外部的不同 Region 进行部署 EC 集群；
  • 基于服务资源思考：互联网行业的存储服务器资源的存储和网卡配置迭代较快，线上这种异构环境导致的线上扩缩容操作都会引起集群可靠性的变动，因而引入可靠性评估模型对集群进行近实时的预估；
  • 基于复原带宽思考：优化指标是为了进一步升高 EC 冗余度但同时可靠性不升高，因而复原带宽升高是一个重要优化思路，因而在全局引入并行修复和在部分引入 MSR 纠删修复的形式进一步升高复原带宽。

4.3.2 可靠性模型设计

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

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

图 29：系统故障解决流流程【工夫线】

  • MTTF：Mean Time To Failure，均匀无故障工夫，指零碎无故障运行的均匀工夫，取所有零碎开始失常远行到产生故障之间的时间段的平均值，如上图的 T1 的平均值；
  • MTTR：Mean Time To Repair，均匀修复工夫，指零碎从产生故障到培修完结之间的时间段的平均值。如上图的 T2+T3 的平均值；
  • MTTDL：Mean Time to Data Loss，均匀数据失落工夫，换个说法也能够是零碎两次故障产生工夫的距离平均值，如上图的 T1+T2+T3 的平均值。

（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 形式，针对不同的场景有不同的优化措施：

  • 当只有一个数据节点故障状况下 ，通过在各机房的 部分校验块，只须要在机房内用 MSR 最小带宽进行疾速修复；
  • 当只有一个部分校验节点故障下，也是通过在各机房的数据块在机房内进行疾速修复；
  • 当只有一个全局校验节节点故障下 ，则能够通过一个机房的 部分校验块再联合其它机房的两头后果数据 进行并行复原；条带越宽，带宽节俭越多，比方单机房 12 数据块，3 机房可节俭跨机房带宽 80%+；
  • 当有两个或两个以上节点同时故障的状况下 ，才须要进行跨机房传输数据修复，咱们能够通过 部分校验块 + 其它机房两头后果联合 + 并行修复 的模式来升高网络带宽耗费。

为了能形容分明咱们的策略，咱们以（16，4，4）4 机房，4 个部分校验块，4 个全局校验块，16 个数据块【如下图所示】为例来阐明：

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

咱们假如部分校验块 P1、P2、P3、P4 的结构按如下所示：

同样按 RS 码结构形式，咱们假如 Q1、Q2、Q3、Q4 的结构按如下所示：

接下来咱们来剖析一下不同场景下的复原状况：

  • 只有一个数据节点或 P 节点故障：只须要在每个部分进行即可，利用生成矩阵的逆矩阵：
  • 只有一个 Q 节点故障：按原来的算法是须要 D1-16 全副参加进行计算，然而咱们剖析能够发现生成矩阵是固定的，因而，齐全能够在机房外部进行两头运算后再发送到故障机房进行最终运算失去，以 Q2 为例，只须要以下四个生成矩阵在各自机房与机房数据 Di 进行两头后果运算即可：
  • 有两个或两个以上节点故障：能够通过在集群运行前先把所有可能的校验矩阵【如下图所示】筹备好，而后再通过在各自机房与机房数据 Di 或 Qj 进行两头后果的计算，最初在须要复原机房进行最终后果的合并计算失去复原数据：

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

五、总结

云存储畛域针对纠删码技术的钻研截止到当初依然是学术界和工业界钻研的热点，如何能升高网络的修复带宽，升高存储开销同时保证数据的可靠性的同时编解码算法又能工程落地，编解码复杂度又偏低，这些维度的考量衍生了各式各样的纠删码编码技术，vivo 也在纠删码技术依据生产环境可落地的前提下在传统 RS 码的根底上引入并行修复以利用 LRC+MSR 部分校验块的组合来升高传统 LRC 在生产环境上使用导致的跨机房带宽开销，从而较低的跨机房带宽开销为高条带低冗余度的 EC 策略提供了保障。随着业务的倒退，数据的存储开销老本会越来越显著，因而，针对纠删码技术的研究会是一个长期的过程，自己也会时刻关注学术界和工业界的动静，联合 IDC、服务器、网络及业务的个性进行翻新和优化为业务继续助力。

参考文献：

  1. Reed I S, Solomon G. Polynomial Codes over Certain Finite Fields. Journal of the society for industrial and applied mathematics, 1960, 8(2):300-304
  2. Plank J S, Ding Y. Note: Correction to the 1997 tutorial on Reed-Solomon coding.Software: Practice and Experience, 2005, 35(2):189-194
  3. Shokrollahi A. LDPC codes: An Introduction. Technical report, 2003.
  4. 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.
  5. 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 (FAST’04), Berkeley, CA, USA, March 31 – April 2, 2004, 1-14.
  6. 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.
  7. James S. Plank: The RAID-6 Liberation Codes. FAST 2008: 97-110
  8. 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.
  9. Blaum M, Roth R, New array codes for multiple phased burst correction. IEEE Trans on Inform Theory, 1993,39(1): 66 ~ 77.
  10. 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.
  11. 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.
  12. N. B. Shah,“On Minimizing Data-Read and Download for Storage-Node Recovery,”IEEE Communications Letters, vol. 17, no. 5, pp. 964–967, 2013.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. Hou H, Lee P, Shum K, et al. Rack-aware regenerating codes for data centers. IEEE Transactions Information Theory, 2019,65(8):4730-4745.
  20. 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.
  21. 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.
  22. 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.
  23. Y.WuandA.G.Dimakis,“Reducingrepairtrafficforerasurecoding-basedstorageviainterferencealignment,”Proc.IEEEInternationalSymposium on Information Theory, Seoul, Korea, June 2009, pp. 2276–2280.
  24. C.SuhandK.Ramchandran,“Exact-repairMDScodeconstructionusinginterferencealignment,”IEEETrans.Inf.Theory,vol.57,no.3,pp.1425–1442,Mar. 2011.
  25. 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.
  26. 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.
  27. 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.
  28. V.Cadambe,S.A.Jafar,H.Maleki,K.Ramchandran,andC.Suh,“AsymptoticInterferenceAlignmentforOptimalRepairofMDSCodesinDistributedStorage,”IEEE Trans. Inf. Theory, vol. 59, no. 5, pp. 2974–2987, 2013.
  29. 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.
  30. 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.
  31. 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.
  32. 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.
  33. 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.
  34. 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.
  35. 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.
  36. 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.
  37. 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.
  38. 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.
  39. N. Alon,“Combinatorial nullstellensatz,”Combinatorics, Probability and Computing, vol. 8, no. 1-2, pp. 7–29, 1999.
  40. 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.
  41. 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.
  42. ——,“Explicit Constructions of Optimal-Access MDS Codes With Nearly Optimal Sub-Packetization,”IEEE Trans. Inf. Theory, vol. 63, no. 10, pp.6307–6317, 2017.
  43. 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.
  44. 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.
  45. 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.
  46. 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.
  47. 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.
  48. 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.
  49. 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.
  50. 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.
  51. 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.
  52. G. Calis and O. O. Koyluoglu,“A General Construction for PMDS Codes,”IEEE Communications Letters, vol. 21, no. 3, pp. 452–455, 2017.
  53. 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.
  54. 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.
  55. 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.
  56. 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.
  57. M. Blaum,“Construction of PMDS and SD codes extending RAID 5,”CoRR, vol. abs/1305.0032, 2013.
  58. 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.
  59. V.LalithaandS.V.Lokam,“Weightenumeratorsandhighersupportweightsofmaximallyrecoverablecodes,”inProc.53rdAnnualAllertonConference on Communication, Control, and Computing, Monticello, IL, USA, 2015, pp. 835–842.
  60. 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.
  61. 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.
  62. 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.
  63. 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.
  64. Fang W, Fu F. Optimal cyclic (r,sigma) locally repairable codes with unbounded length. Finite Fields Appl, 2020,63:101650.
  65. 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.
  66. 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.
  67. 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.
  68. 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.
  69. 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.
  70. 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.
  71. 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.
  72. M.Y.NamandH.Y.Song,“BinaryLocallyRepairableCodesWithMinimumDistanceatLeastSixBasedonPartialt-Spreads,”IEEECommunications Letters, vol. 21, no. 8, pp. 1683–1686, Aug 2017.
  73. 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.
  74. 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.
  75. 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.
  76. 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.
  77. 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.
  78. KMM,et,al：An Efficient Piggybacking Design Framework with Sub-packetization l 􏲐 r for All-Node Repair
  79. Francisco Maturana and K. V. Rashmi, et, al：Bandwidth Cost of Code Conversions in the Split Regime
  80. Hanxu Hou, et, al：New Piggybacking Codes with Lower Repair Bandwidth for Any Single-Node Failure
  81. Han Cai,et,al: On Optimal Locally Repairable Codes and Generalized Sector-Disk Codes
  82. A“Hitchhiker’s”Guide to Fast and Efficient Data Reconstruction in Erasure-coded Data Centers
  83. Mean time to meaningless: MTTDL, Markov models, and storage system reliability
  84. “后香农时代，数学将决定将来倒退的边界”[(https://www.ithome.com/0/508/768.htm)]
退出移动版