< Back

纠删码技术在CubeFS的应用和实践

2023-07-31曾源

作者：曾源，CubeFS Contributor，中科大先进数据系统实验室研究生在读

1. 引言

1.1 纠删码的使用背景

随着互联网用户基数的不断增大，加上人工智能以及移动物联网等新兴领域的快速发展, 云上的数据量开始呈现指数型增长的趋势。为了处理与存储 ZB 级别的海量数据，云上大规模分布式存储系统的部署需求日益增加。然而，高性能的分布式存储系统通常由众多组件共同构成，整个系统的运作涉及到包括硬件，软件，网络，电力等等在内的许多方面。复杂的组成决定了存储系统必须应对包括磁盘损坏，节点失效，网络故障以及集群宕机等各种故障，以此来避免系统由于故障而造成的各方面损失，包括客户服务中断，备份数据丢失等。

一般而言，存储系统会通过存储一定量的冗余数据来保证可靠性。当系统出现故障时，冗余数据可以继续为用户提供各种服务，并且修复因故障而丢失的部分数据。目前主流的容错机制大致分为多副本机制和纠删码机制两类。由于冗余数据会增大存储成本，而多副本相较于纠删码的冗余存储开销过于巨大，目前纠删码已成为了当前云存储系统的主流数据冗余方式，并且持续成为学术界和工业界在存储领域的研究热点。

图1. 使用纠删码技术的部分公司列表

1.2 纠删码的研究方向

纠删码理论的研究大致分为两类：编码理论设计&系统流程优化。

前者专注于纠删码的理论分析，从编解码复杂度，修复流量，容错能力等维度进行研究，提出新的纠删码编码理论，更注重于数理证明，不会考虑其在真实系统部署的代价。此类研究常常发表于《IEEE Transactions on Information Theory》中，是各类商用纠删码的理论基础。

后者则专注于系统实现，这类研究将在编码理论的基础上，结合业务需求(跨 AZ，异构设备，宽条带等场景)对纠删码进行改造并部署到真实系统中，随后结合实验数据证明其可靠性与可用性。此类研究常常发表于各大系统会议，例如 ATC，FAST，OSDI，SOSP 等。

1.3 本文行文结构

本文接下来的行文结构如下：第 2 节我们将简单地梳理目前纠删码领域的研究现状，介绍理论与系统实现上的相关成果；第 3 节我们则将重点阐述三大典型纠删码(RS,MSR,LRC)的编码原理，同时进行各指标的比对；第 4 节我们将分享纠删码技术在 CubeFS 中的应用与实践。

2. 研究现状

目前最为经典的纠删码莫过于里德所罗门码 (Reed-Solomon Code)

【1】, 由于 RS 码的码长不受限制，且在相同容错能力下存储开销最小，其在工业界得到了广泛的部署。RS 码有范德蒙【2】形式与柯西形式【3】两种，其中柯西形式的 RS 码因为具有更好的计算性质而被广泛研究：包括但不限于针对柯西 RS 码的异或变换【4】，针对柯西矩阵的选型【5】，针对柯西 RS 码的计算加速【6】等研究。除了编码理论之外，学术界与工业界还对部署 RS 码的存储系统进行了相当多的系统优化，如通过局部并行计算减少修复网络带宽【7】，通过任务调度进行负载均衡【8】等工作。然而，RS 码在编码理论上有着较大的缺陷，即其存在修复流量过高的问题。

为了解决 RS 码修复流量过高的问题，学术界提出了一种名为再生码【9】的编码理论，再生码引入了帮助节点的概念，并从信息流图分析给出了修复丢失信息所需的最低数据量。在这个理论框架下存在着两种再生码的形式：最小存储量再生码(MSR 码)与最小修复带宽码(MBR 码)。而由于真实系统对存储开销的重视，学界的大量研究都集中于 MSR 码中。

MSR 码的构造是一项困难的工作，为了达到理论的修复流量下限，MSR 码需要对数据块进行细粒度划分，而这个划分的程度我们用分包数来表示。目前许多工作【10-13】对分包数的下限进行了细致的讨论，而基于这些理论分析，学术界也给出了一些经典的 MSR 码构造方案，例如 Zigzag 码【14】，PM-RBT 码【15】，Hashtag 码【16】, Butterfly 码【17】，Clay 码【18】等。同样的，除了理论研究，学术界对于 MSR 码的系统优化工作也颇有研究：清华的团队【19】研究了对象存储场景下 Clay 码部署时面临的磁盘 I/O 性能问题，华科的团队【20】研究了 Clay 码在编解码过程中的并行加速问题。

然而，由于分包数过大、码长受限制等原因，MSR 码在实际部署中往往存在许多目前无法有效解决的问题。为此，学术界和工业界也在寻找其他的编码来解决 RS 码修复流量过高的问题，在这其中，一个名为局部修复码(LRC)的编码理论应运而生。

LRC 是一个对数据分组，引入局部校验，通过牺牲存储开销来达到减少修复节点数的目的的编码。由于 LRC 实现简单，扩展性强，且非常契合真实业务中的故障场景，其在工业界有着相当多的实践，并逐渐称为近年来纠删码领域的研究热点。LRC 最先被 MicroSoft Azure 于【21】提出，随后又有相当多的变种工作出现： 如 optimal-LRC【22】, Xorbars【23】等。后来 Kolosov 于【24】中对多种 LRC 进行了全面的评估研究分析，并确定了 LRC 的评价标准。此外，大量 LRC 的系统优化工作也被提出：例如宽条带场景下的 LRC 部署【25】，跨 AZ 部署 LRC 场景下的流量优化【26】等。在 2023 年最新的 FAST 会议中，谷歌也给出了高可用性场景下的 LRC 实践经验【27】。由此可见，LRC 已经成为主流分布式存储系统中相当重要的容错机制备选项。

接下来我们将对 RS,MSR,LRC 码进行详细的介绍与分析。

3. 技术原理

3.1 基础原理

纠删码技术通过生成冗余的校验信息来保证系统的容错能力。原数据会通过计算得到多于原始信息量的编码数据，随后再进行持久化存储。一般而言，纠删码通常由两个参数(n,k)来配置，即使用 k 份原始数据计算得到 n 份数据。我们将这 n 份数据称为纠删码条带，当条带中的部分数据丢失时，剩余可访问的数据便能根据编码方程进行解码，从而恢复丢失数据，图 2 便是一个 (8,5) 纠删码的容错示意。

图 2. 纠删码容错示意

除了纠删码的容错模式之外，我们需要再了解两个概念：系统性与 MDS 性。

如果条带是以原始数据加校验数据的形式存储，即原始数据是条带内数据的子集，我们则称这种编码为系统码。系统码在读操作时可以直接获得原始数据，无需额外解码操作，解码流程仅在恢复数据时启用。由于系统码的便利性，流行的分布式存储系统都采用了具有系统码性质的纠删码作为其编码方式。因此，本文的讨论中也只关注系统码。

MDS 码 (Maximum Distance Separable) 的定义为：极小距离达到理论最大值，即 Singleton 界的线性码。若该线性码 C 的参数为 (n,k)，则 dmin(C)=n-k+1。通俗来讲便是，对于一个参数为 (n,k) 的纠删码，任取 k 个数据块都能将剩余 n-k 个数据解码出来。在同一容错能力下，MDS 码代表着存储开销最小的线性码。

除了上述两种性质外，影响纠删码好坏的指标还有很多（表 1），而编解码的设计则直接决定了各项指标的理论界限。在本章节中，我们将详细讨论三种不同的纠删码类型：里德所罗门码(Reed-Solomon Code), 最小存储再生码 (Minimum-Storage Regenerating Code) 以及局部修复码 (Local Reconstruction Code)，并从理论角度分析部分重要指标，进而阐明各类纠删码的优劣势。

表 1 纠删码的评价指标

存储冗余度	实际存储的数据量与原始数据量的比值，这项指标直接决定了存储开销。
容错上限	纠删码单个条带所能容忍的最大坏块个数，这项指标决定了整个系统的容错能力。（p.s. 相同存储冗余度下，MDS 码拥有最高的容错上限）
修复流量	节点故障时修复数据所需要传输的数据流量，该指标是纠删码系统最重要的指标，直接决定了系统的性能。
编解码复杂度	即纠删码的计算复杂读，编码复杂度决定了数据的写入时延，解码复杂度影响数据的降级读与修复时延。
分包数	部分纠删码的构造需要将数据块拆成多个子块，每个数据块的子块个数称之为分包数，该指标将影响数据的 I/O 性能。
参数限制	部分纠删码构造对 n,k 有限制，该指标将决定纠删码的通用性与使用场景。

3.2 里德所罗门码

里德所罗门码（Reed-Solomon Code，简称RS ）码是一种 MDS码，其拥有两个无约束参数(𝑛, 𝑘)。优秀的MDS 性质，加上灵活的参数设置，使得RS码成为目前纠删码系统中使用最为广泛的编码。RS 码的设计非常简单：其通过编码矩阵计算校验块，使用高斯消元法对损坏数据进行恢复，且所有运算均在伽罗瓦域 (Galois Fields) 上进行。

3.2.1 编解码流程

接下来我们来介绍一下 (n,k) RS 码的编码流程。我们用 $[D_0,...,D_{k-1}]$来表示原始数据块，用 $[P_0,...,P_{n-k-1}]$来表示校验数据块。则 RS 码的编码计算可用(1)式的矩阵乘法进行表示。编码矩阵的维度为$n*k$，为了保证编码的系统性，其前 k 行将构成一个单位方阵。而为了满足其 MDS 性，其后 n-k 行的系数需要精心设计。

$$\left[\begin{matrix}1&0&...&0&0\\0&1&...&0&0\\.&.&.&.&.\\.&.&.&.&.\\.&.&.&.&.\\0&0&...&0&1\\\alpha_{0,0}&\alpha_{0,1}&...&\alpha_{0,k-2}&\alpha_{0,k-1}\\.&.&.&.&.\\.&.&.&.&.\\.&.&.&.&.\\\alpha_{n-k-1,0}&\alpha_{n-k-1,1}&...&\alpha_{n-k-1,k-2}&\alpha_{n-k-1,k-1}\\\end{matrix}\right]*\left[\begin{matrix}D_0\\D_1\\.\\.\\.\\D_{k-1}\end{matrix}\right]=\left[\begin{matrix}D_0\\D_1\\.\\.\\.\\D_{k-1}\\P_0\\.\\.\\.\\P_{n-k-1}\end{matrix}\right] (1)$$

为了阐述该系数设计所需满足的性质，我们先简要说明一下 RS 码的修复流程。不失一般性地，我们假设损坏了 n-k 个数据块, 假设这 n-k 块为 $[D_{2k-n},...,D_{k-1}]$。现在我们需要使用存活的 $[D_0,...,D_{2k-n-1},P_0,...,P_{n-k-1}]$来修复所有的损坏块。根据(1)式，我们可以轻松得到：

$$\left[\begin{matrix}D_0\\D_1\\.\\.\\.\\D_{k-1}\end{matrix}\right]=\left[\begin{matrix}1&0&...&0&0\\0&1&...&0&0\\.&.&.&.&.\\.&.&.&.&.\\.&.&.&.&.\\0&...&1&...&0\\\alpha_{0,0}&...&\alpha_{0,2k-n-1}&...&\alpha_{0,k-1}\\.&.&.&.&.\\.&.&.&.&.\\.&.&.&.&.\\\alpha_{n-k-1,0}&...&\alpha_{n-k-1,2k-n-1}&...&\alpha_{n-k-1,k-1}\\\end{matrix}\right]^{-1}*\left[\begin{matrix}D_0\\D_1\\.\\.\\.\\D_{2k-n-1}\\P_0\\.\\.\\.\\P_{n-k-1}\end{matrix}\right] (2)$$

我们只需要保证(2)式中的方阵可逆，就能保证解码得到所有的数据块。显然，n-k 个数据坏块是最“难以修复”的损坏场景，当这一损坏情况都能被修复时，其余损坏情况 RS 码也是能够修复的。因此，我们对 RS 码的编码矩阵有则如下的要求：

对于 (n,k)-RS 码的编码矩阵，我们需要保证其 nk 维矩阵中任意 kk 维子矩阵可逆。

而为了满足上述性质，RS 码通常基于范德蒙 (Vandermonde) 矩阵或柯西 (Cauchy) 矩阵进行编码矩阵的构造。下一小节我们将详细介绍这两种形式的 RS 码。

3.2.2 编码矩阵

3.2.2.1 范德蒙矩阵

首先我们先来讨论范德蒙矩阵的定义，范德蒙矩阵是一个各行呈现出等比关系的矩阵,一个维度为 n*k 的范德蒙矩阵形式如下所示(n>k)：

$$\left[\begin{matrix}\alpha_{0}^0&\alpha_{0}^1&\alpha_{0}^2&...&\alpha_{0}^{k-1}\\\alpha_{1}^0&\alpha_{1}^1&\alpha_{1}^2&...&\alpha_{1}^{k-1}\\.&.&.&.&.\\\alpha_{n-1}^0&\alpha_{n-1}^1&\alpha_{n-1}^2&...&\alpha_{n-1}^{k-1}\\\end{matrix}\right]$$

通过数学归纳法，我们可以轻松证明, 一个 n 阶范德蒙方阵的行列式为(3)式所示。因此，我们只需要保证范德蒙矩阵的构成满足 $\forall i,j\quad \alpha_i\neq \alpha_j$ ，即可使维度为 n*k 的范德蒙矩阵满足其任意 k 阶方阵可逆的性质。

$$det(V)=\sum_{0\leq i\leq j\leq n-1}(\alpha_j-\alpha_i) \quad (3)$$

因此基于范德蒙矩阵构造的 RS 码将按照如下方法构造，其中第一步保证了 RS 码的 MDS 性，第二步保证 RS 码的系统性：

• 第一步，根据 RS 码的参数 n,k 构造对应的 n*k 维范德蒙矩阵。
• 第二步，对该范德蒙矩阵进行初等行列变换，使得前 k 行构成的方阵转换为单位阵。

3.2.2.2 柯西矩阵

柯西矩阵则是从有限域的性质出发，直接构造出了符合 RS 码需求的编码矩阵。一个 n*k 维的柯西矩阵形式如下所示（n>k）

$$\left[\begin{matrix}\frac{1}{x_0+y_0}&\frac{1}{x_0+y_1}&...&\frac{1}{x_0+y_{k-1}}\\\frac{1}{x_1+y_0}&\frac{1}{x_1+y_1}&...&\frac{1}{x_1+y_{k-1}}\\.&.&.&.\\\frac{1}{x_{n-1}+y_0}&\frac{1}{x_{n-1}+y_1}&...&\frac{1}{x_{n-1}+y_{k-1}}\end{matrix}\right] , \left\{\begin{array}{c} x_i\in X , |X|=n \\ y_j\in Y,|Y|=k \end{array}\right.$$

当 $X,Y$内的元素两两不同时，柯西矩阵的构造保证了其任意 k 阶方阵可逆，证明不在此处展开。此外，基于柯西矩阵构造的 RS 码，其可以通过一些线性映射，将 $GF(2^w)$ 的运算映射到$GF(2)$上，进而将大量的有限域乘法转换为异或计算，提高计算效率。详细的映射算法与异或加速方案在此处不展开，感兴趣的读者可在参考文献【4】中了解。

3.2.3 小结

总的来说，RS 码是一个具有 MDS 性质的最优容错编码，一个参数为(n,k)的 RS 码可以使用条带中任意 k 个块来解码出其余任意数量的块。而且 RS 码的构造与工程实现相对简单，同时有诸如 Jerasure,ISA-L,Kluaspot 等开源库实现，因此 RS 码被广泛地运用于各大分布式系统中。但从另一角度，即使只进行单块修复，RS 码也必须读取 k 个可访问的存储块才能完成修复，这意味着部署着 RS 码的纠删码系统拥有着巨大的修复流量代价，这一代价会随着 k 的增长显得愈发不可接受。而在真实系统中，单块故障又是最为常见的场景，因此针对单块故障的修复流量优化是非常有必要的。

3.3 最小存储再生码

为了解决 RS 码单块故障修复流量开销过高的问题，Dimakis 等学者提出了再生码的概念。再生码从信息论的角度出发，刻画了节点修复流量下界与节点信息量的关系，为后来多种理论修复流量最优的系统实现打下来坚实的理论基础。而其中的分支最小存储量再生码(Minimum-Storage Regenerating Code，简称MSR)，则是最符合真实系统需求的编码理论。

然而，从 MSR 码的理论到构造存在着巨大的鸿沟，目前提出的 MSR 码构造往往存在着部分缺陷，例如 Butterfly 码只能容两错等。在本节中，我们将从实用性角度出发，介绍两种参数不受限，构造相对简单的 MSR 码方案。

3.3.1 Zigzag 码

Zigzag 码的设计理念包括：数据分层、交错编码与数据复用。我们通过图 3 这个简单的(5,3)Zigzag 为例，来直观地理解其精妙的设计。

3.3.1.1 示例

首先我们简单介绍图 3 的含义：在(5,3)Zigzag 中，数据块有 3 块，编号为 0、1、2, 对应图中的前 3 列；校验块有 2 块，编号为 R、Z，对应图中的后两列；同时，每个块都被拆分成了 4 个子块(即分包数为 4)，分别对应图中的 4 行。其中，R 校验通过同层的数据子块计算得来，而 Z 校验则通过异层的数据交错计算得来。例如，位于图中(0, 0), (2, 1), (1, 2)位置的拥有♣ 标记的数据块将共同参与计算得到位于(0,Z)位置的校验数据。

图 3. (5,3)Zigzag 码的编解码示意

现在我们暂时忽视计算系数，考虑单块故障的情景，进而揭示 Zigzag 码对于修复流量的优化。我们假设数据块 1 发生了损坏，此时的修复流程中，(5,3)Zigzag 仅需要读取阴影所示的数据即可将数据块 1 重构。其中(0, 1), (1, 1)的数据通过 R 校验复原，而(2, 1), (3, 1)的数据则通过 Z 校验复原，即♣ 与♡ 标记的数据块。由于在修复过程中，所有原始数据块上的♣ 与♡ 数据得到了复用，即同时参与了由R/Z校验块主导的数据修复，整个(5,3)-zigzag码的单节点故障修复流量得到了削减，仅为传统RS码的 2/3倍，而这正好符合MSR码的理论修复流量下限。同样地，对于其他的单节点故障情况，(5,3)Zigzag码也能达到相同的优化比。接下来我们将阐述如何系统地构造一个具有MSR性质的Zigzag码。

3.3.1.2 构造流程

从图 3 的例子我们可以感受到，Zigzag 码设计的核心理念是寻找一个好的花色排序规则，来为修复过程的数据复用提供可能，进而优化修复流量。在这里，我们简单给出(k+2,k)Zigzag 码的构造方法，其向任意参数的推广以及编码系数的选取则留给感兴趣的读者自行查阅文献【14】。

现在我们将整个 zigzag 码的构造问题简化为两个子问题：

1. 如何设计排序函数集 $\mathbb{F} = \{f_0,...,f_{k-1}\},f_i : \{0,1\}^{k-1} \rightarrow \{0,1\}^{k-1}$，这决定了整个 Zigzag 码的编码结构，即花色如何排布；
2. 如何设计修复集合划分 $\mathbb{X} = \{X_i|i\in[0,k-1]\}$，这指示了 Ziazag 码在进行修复时的指派方案，即当前花色该使用哪种校验块修复。 在(k+2,k)Zigzag 码中，数据块的分包数为 $2^{k-1}$, 且花色总数等于分包数。为了方便形式化描述，我们可以用 k-1 维的 01 向量来同时表示花色和数据子块的层数，同时使用排列函数 $f_i(x)=y$来表示对第 $i$个数据块的$x$子块赋花色$y$。

随后我们定义单位向量 $e_i$，其表示该向量在第$i$位为 1，其余位置为 0 ($e_0$则表示零向量)。现在我们便可为(k+2,k)Zigzag 码的排列函数集进行简洁的构造：

$$\mathbb{F} = \{f_i(x)=x+e_i|i=0,..,k-1\}$$

以(5,3)Zigzag 为例，我们假设 0-3 表示花色 $\clubsuit,\heartsuit,\spadesuit,\diamondsuit$, 现在我们对数据块 1 进行花色划分，则由图 4 所示，我们先将每层子块的位置转化为 01 向量，随后使用对应的排列函数将每层映射一个新的 01 向量，最后再将得到的 01 向量转换为对应花色。因此数据块 1 的花色分布从上到下为$\spadesuit,\diamondsuit,\clubsuit,\heartsuit$, 与图 2 所示一致。

图 4. (5,3)-Zigzag 中数据块 1 的花色划分流程

紧接着我们来定义修复集合划分： $\mathbb{X} = \{X_i|i=0,...,k-1\}, X_i=\{x|x\cdot e_i=0\}$。当数据块 $j$损坏时，所有层数属于 $S_r=\{i|i\in X_{e_j}\}$的数据将通过 R 校验块恢复，而所有层数属于 $S_z=\{i|i\notin X_{e_j}\}$的数据将通过 Z 校验块恢复。仍然以(5,3)Zigzag 为例说明，当数据块 1 损坏时，我们根据修复集合划分有：

$$X_1 = \{x|x\cdot e_1 = x\cdot(1,0) = 0\} = \{(0,0),(0,1)\}$$

因此层数为 0,1 的数据块使用 R 校验块恢复，层数为 2,3 的数据块使用 Z 校验块恢复，这也与图 3 的修复流程一致。 这便是(k+2,k)Zigzag 码的结构设计方案，由于篇幅问题，其编码系数的选取以及编码参数的推广在此便不再展开。

综上，Zigzag 码是一个巧妙利用数据分层、交错编码与数据复用的纠删码。然而，其编码系数的生成存在很多数学层面的困难，设计一个好的 Zigzag 码需要较强的数学功底。幸运地是，学界对 MSR 码的研究不仅止步于此，FAST'18 上发表的 Clay 码便很好地规避了系数生成的问题。Clay 码是一个正交于系数生成的 MSR 码设计方案，其能在任意已有的 MDS 码上进行拓展，将其改造为具有 MSR 码性质的纠删码系统，接下来我们将详细介绍 Clay 码的设计思路。

3.3.2 Clay 码

3.3.2.1 概述

Clay 码的全称为 Coupled Layer Codes，其特点便是系统在数据分层的基础上增加了大量的耦合对，所有的耦合对提供跨层的数据关联，这与 Zigzag 码中 Z 校验的意义类似。Clay 码在层内采用常规 MDS 编码，例如传统 RS 码，而在耦合对之间进行可逆变换，耦合对之间的跨层联系便在此处产生。如此编码之后，当数据块发生损坏时，所有耦合对所在的数据子块便能同时提供同层与跨层的数据信息，以此减少修复流程中所传输的数据量。

如图 5 所示，Clay 码中的所有数据拥有两种形式，其中红色为原始数据形式，蓝色则为中间数据形式。Clay 码在编码数据时，会首先采用可逆矩阵(4)对耦合对中的原始数据进行编码，这一过程称为结对逆向转换(Pairwise Reverse Transform, PRT)。在 PRT 结束，所有数据变为蓝色形式时，Clay 码再对所有同层级的数据进行层内的 MDS 编码，最后，所有耦合对再进行结对前向转换(Pairwise Forward Transform, PFT)还原为原始数据形式。

$$\left[\begin{matrix}C(p)\\C^*(p)\end{matrix}\right]=\left[\begin{matrix}1&\gamma\\\gamma&1\end{matrix}\right]^{-1}*\left[\begin{matrix}U(p)\\U^*(p)\end{matrix}\right] (4)$$

图 5. (4,2)Clay 码结构示意图

接下来我们将以图 5 中的(4,2)Clay 码为例，展示 Clay 码的修复流程，揭示其能实现 MSR 性质的原因。

3.3.2.2 示例

我们假设(4,2)-Clay 码出现了单节点故障，如图 6 所示，此时 Clay 码首先对存活的耦合对进行 PRT 变换，得到耦合对的中间数据形式。随后 Clay 码通过存活耦合对所在层的幸存数据进行 MDS 解码，将故障节点对应层的数据还原成中间形式，即图 6 的右下角所示。最后，由于 Clay 码耦合对变换的可逆性，未被 MDS 解码得到的故障耦合对数据可以通过其关联的数据计算得到，至此，故障节点便得到了重构。纵观整个修复过程，Clay 码仅仅利用了存活耦合对所在层的数据便将数据还原，而由于 Clay 码对耦合对进行了巧妙的设计，这一过程所需读取的数据量恰好实现了 MSR 码的理论修复流量。

图 6. (4,2)Clay 码的修复流程

接下来我们将仔细分析 Clay 码关于耦合对的精妙设计。

3.3.2.3 核心设计

Clay 码采用三个维度对节点的位置信息进行了描述，其中节点的索引信息包含 $x/y$轴两个维度，其中 $x$轴的范围为 $[0,n-k-1]$; $y$轴的范围为 $[0,\lceil\frac{n}{n-k}\rceil-1]$。我们分别将两者的模记为$|x|=q=n-k,|y|=t=\lceil\frac{n}{n-k}\rceil$。此时节点的层数信息便可采用 $t$维向量进行刻画，其中向量的每个分量范围为 $[0,q-1]$。因此，整个 Clay 码可以看做一个 $q*t*q^t$的三维立方体，而耦合对的设计将基于这样的位置刻画设计。

对于 Clay 码中的任意节点 $(x,y,z_0,...,z_{t-1})$， $(z_y,y,z_0,...,z_{y-1},x,z_{y+1},...,z_{t-1})$为其耦合节点。倘若该节点的耦合节点为其本身，则该节点不包含在耦合对中，即图 4 中红色部分所示。分析耦合节点的定义我们可以发现，耦合对的连接是以 $y$轴为片区划分的，耦合对拥有着相同的 $y$分量，而其关联的跨度随着 $y$值的增大而增大。以图 5 为例，对于 $y=0$的片区，其耦合对只跨单层产生联系；而对于 $y=1$的片区，其耦合对跨双层才产生联系。这样的组合设计与 Zigzag 中排列函数的偏移量 $e_i$成指数增长类似，能使得不同片区的耦合对节点交错分布在系统的不同层内，进而使系统在修复时能利用更少层数的数据关联更多的未使用数据。

综上所述，Clay 码从数据的多种表示形式出发，用耦合对与数据变换的方法为存储节点内的数据提供多层次的信息关联，进而绕开了如 Zigzag 码的编码设计，对所有的 MDS 码进行了 MSR 化的拓展，是极其优秀的纠删码设计。

3.3.3 小结

3.3 节介绍了两种参数不受限制的 MRS 码构造方案，两者均通过巧妙的组合设计，在数据分层的基础上产生跨层关联，进而复用尽可能少的数据量来修复损坏数据。然而，无论是 Zigzag 码还是 Clay 码，都无法避开 MSR 码理论本身所面临的挑战：为了达到 MSR 码的理论修复流量，编码本身的分包数最少需要达到 $(n-k)^{\lceil\frac{n}{n-k}\rceil}$的量级。这意味着当我们的编码参数稍微扩大时，每个数据块的子块个数将指数级上升，哪怕是(14,4)这样的常见参数，其分包数也达到了 256。这一性质在系统中的负面影响体现在：数据修复时的 I/O 性能由于访问连续性的欠缺而大幅下降，此时磁盘 I/O 将变成整个系统的瓶颈,严重影响系统的正常运行。这也是除了编解码复杂外，再生码目前仍没有被大规模使用的原因之一。

3.4 局部修复码（Local Reconstruction Code）

为了优化单盘修复流量，工业界给出了另一种编码，这便是由 Microsoft Azure 最先提出并应用的 LRC。LRC 通过对数据块进行分组，并针对每组数据块生成局部校验块，从而使得单盘修复只需要组内节点参与即可。由于 LRC 的简易以及对业务需求的契合， 工业界对 LRC 有着很多的实践经验。在本章节中，我们将详细阐明 LRC 的实现原理，同时介绍几种不同的构造方式。

3.4.1 核心设计

LRC 通常具有 3 个正整数参数$k,l,g$，$(k,l,g)$LRC 将$k$个数据块划分为$l$组，每一组内生成 1 个局部校验块，并通过$k$个数据块生成$g$个全局校验块。同一条带中的$k+l+g$ 个块分别存储在各个独立的存储设备上。当条带发生单块故障时，LRC 将启动局部修复算法，仅使用与故障块隶属同一组的其他块进行数据解码修复；当故障数量大于 1 时，LRC 将使用全局+局部校验块进行解码修复，这一修复流程与 RS 码类似。

以图 7 为例，局部校验块 $p_x,p_y$分别由数据块 $x_0,x_1,x_2$ 和 $y_0,y_1,y_2$编码生成，并各自负责组内数据块的局部修复。全局校验块 $p_0,p_1$则由 $x_0,x_1,x_2,y_0,y_1,y_2$编码生成，保证整个条带多故障的容错性。

图 7. (k=6,l=2,g=2)LRC 码示意图

从构造形式可以看出，LRC 在只有一个数据块丢失时，只需要读取故障块对应组内的其他数据块以及局部校验块即可进行解码。相比于(n, k)RS 码需要读取 k 个块才能完成的修复流程，(k, l, g)LRC 在单块修复时的数据传输开销大约只有 k/l 个数据块；同时，LRC 在修复时的计算量也随着参与数据量的减少而大大降低，这保证了整个纠删码系统能以较快的速度恢复损坏数据，并继续提供用户服务。不过 LRC 因为增设了局部校验块，扩大了存储开销，其不再具有 MDS 性质。通过好的系数设计，(k, l, g)LRC 可以容忍任意 g+1 个并发故障，同时也能修复部分坏块数多于 g+1 但少于 g+l 的故障场景。

值得一提的是，除了使用参数(k,l,g)来描述外，LRC 还可以用另一种参数(n,k,r)来描述。其中 n 表示条带中块的总数，k 表示数据块的个数，而 r 则表示单个组内非局部校验块的个数上限。使用这一套参数可以更好地描述 LRC 的分组情况，更方便于编码理论的分析。当前 LRC 有着许多种构造方式，其容错能力也各有不同，我们将在这下一小节中对其进行简要的介绍。

3.4.2 多种构造方式

本小节我们将讨论四种不同的 LRC 构造，分别是：Azure-LRC, Azure-LRC+1 以及 Xorbas。它们的容错能力如表 2 所示，接下来我们将对其构造进行简要的介绍。

表 2 不同类型 LRC 的容错能力

LRC 种类	极小码距，即能容忍的任意坏盘数最大值+1
Azure-LRC	$d=n-k-\lceil \frac{k}{r} \rceil+2$
Azure-LRC+1	$d=n-k-\lceil \frac{k}{r} \rceil+1$
Xorbas	$d=g+1$

3.4.2.1 Azure-LRC

Azure-LRC 即 3.4.1 节所提到的原始的 LRC 构造方式，在此不做赘述。以图 8 为例，其所能容忍的任意坏盘数最大值为 $10-6-\lceil \frac{6}{3} \rceil + 2 -1 = 3$。然而，该构造方式存在一个缺陷：对于全局校验块的修复，哪怕是单块故障修复，Azure-LRC 都需要付出较大的修复开销，这可能使得全局校验块所在的节点变成整个系统的热点，进而影响整个系统的负载均衡。

图 8. (n=10,k=6,r=3)Azure-LRC 示意图

3.4.2.2 Azure-LRC+1

为了解决 Azure-LRC 全局校验块修复开销大的问题，其改良版 Azure-LRC+1 应运而生。该构造在 Azure-LRC 的基础上，为全局校验块增加了额外的局部校验。以图 9 为例，其在图 7 的基础上增加了 L2 局部校验，其容错能力与 Azure-LRC 相同，也为$11-6-\lceil \frac{6}{3} \rceil + 1 -1 = 3$。相较于 Azure-LRC 中数据块与校验块地位的不对等，Azure-LRC+1 中两者的修复代价是完全相同的，这意味着 Azure-LRC+1 在维持容错能力不变的前提下，仅仅通过增加额外一块的存储开销便能解决条带修复开销不均的问题。

图 9. (n=13,k=6,r=3)Azure-LRC+1 示意图

3.4.2.3 Xorbas

Xorbas 则是从编码系数的角度出发来解决 Azure-LRC 全局校验块修复开销大的问题。在 Xorbas 的设计中，其局部校验块的异或和等于全局校验块的异或和，当全局校验块出现单块故障时，Xorbas 可以通过聚集 l 个局部校验块而非 k 个存活块的方法来恢复坏块(l 往往小于 k)。

以图 10 为例，其编码结构与 Azure-LRC 完全一致，但是在编码上进行了特殊的设计，具体的编码矩阵如下，其中系数的选取可见参考文献的附录【23】：

$$\left[\begin{matrix}1&0&0&0&0&0\\0&1&0&0&0&0\\0&0&1&0&0&0\\0&0&0&1&0&0\\0&0&0&0&1&0\\0&0&0&0&0&1\\\alpha_{0,0}&\alpha_{0,1}&\alpha_{0,2}&\alpha_{0,3}&\alpha_{0,4}&\alpha_{0,5}\\\alpha_{1,0}&\alpha_{1,1}&\alpha_{1,2}&\alpha_{1,3}&\alpha_{1,4}&\alpha_{1,5}\\\alpha_{0,0}+\alpha_{1,0}&\alpha_{0,1}+\alpha_{1,1}&\alpha_{0,2}+\alpha_{1,2}&0&0&0\\0&0&0&\alpha_{0,3}+\alpha_{1,3}&\alpha_{0,4}+\alpha_{1,4}&\alpha_{0,5}+\alpha_{1,5}\\\end{matrix}\right]*\left[\begin{matrix}D_0\\D_1\\D_2\\D_3\\D_4\\D_5\end{matrix}\right]=\left[\begin{matrix}D_0\\D_1\\D_2\\D_3\\D_4\\D_5\\G_0\\G_1\\L_0\\L_1\end{matrix}\right]$$

图 10. (k=6,l=2,g=2)Xorbas 示意图

3.4.3 小结

总的来说，LRC 是一种针对单盘修复流量优化的，适合工程实现的纠删码。其通过牺牲 MDS 性质，将部分校验块用于组内局部校验来实现单盘故障迅速修复。由于不具有 MDS 性质，(k,l,g)LRC 最多只能保证任意g+1 个并发故障是可以修复的，而在大规模集群中 g+1 以上并发故障的发生频率不能忽视，这使得 LRC 在高容错场景下的应用受到了限制。

3.5 总结与比较

表 3 总结了前文介绍的所有纠删码的多个重要指标，包括存储冗余、容错上限、系统性、MDS 性、单块修复流量以及分包数。在真实系统中，企业应该根据业务的需求以及工程实现的难度来评估不同的纠删码，随后选择最契合的类型进行部署，进而满足系统的容错需求。

表 3 不同纠删码的指标对比

编码类型	参数	存储冗余	容错上限	系统性	MDS 性	单块修复流量	分包数
Vandermonde RS code	$(n,k)$	$\frac{n}{k}$	$n-k$	√	√	$k$	$1$
Cauchy RS Code	$(n,k)$	$\frac{n}{k}$	$n-k$	√	√	$k$	$1$
Cauchy RS Code (Xor version)	$(n,k)$	$\frac{n}{k}$	$n-k$	√	√	$k$	$w$ (有限域为 $GF(2^w)$)
Zigzag Code	$(n,k)$	$\frac{n}{k}$	$n-k$	√	√	$\frac{n-1}{n-k}$	$(n-k)^{k-1}$
Clay Code	$(n,k)$	$\frac{n}{k}$	$n-k$	√	√	$\frac{n-1}{n-k}$	$(n-k)^{\lceil\frac{n}{n-k}\rceil}$
Azure-LRC	$(n,k,r)$	$\frac{n}{k}$	$n-k-\lceil \frac{k}{r} \rceil+1$	√	×	$\frac{k}{l}$	$1$
Azure-LRC+1	$(n,k,r)$	$\frac{n}{k}$	$n-k-\lceil \frac{k}{r} \rceil$	√	×	$\frac{k}{l}$	$1$
Xorbas Code	$(k,l,g)$	$\frac{k+l+g}{k}$	$g$	√	×	$\frac{k}{l}$	$1$

4.CubeFS中纠删码的应用与实践

CubeFS的纠删码系统支持多种纠删码模式部署，并且能根据业务需要的存储冗余度、AZ级别容灾以及跨AZ修复流量代价，提供CubeFS-LRC、Azure-LRC+1以及优化版RS等多种编码。在进行编码选型时，系统需要考虑存储冗余度、IO扇出度以及是否需要AZ容灾等多个因素。如果需要AZ容灾，需要使用多AZ的编码。相同冗余度情况需要考虑IO扇出度，例如RS(4,2)和RS(8,4)的冗余度相同，但是后者扇出度更大，意味着相同大小文件会被切分成更多份数，每个数据片的数据量更少，出现长尾时延的概率更高，在选择编码时候需要考虑多个因素。

图11. CubeFS的多模式纠删码部署

为缓解纠删码高扇出可能增加长尾时延问题的概率，我们采用写quorum的读写机制，写任意n+t份就返回成功（t根据实际情况可以配置）。读数据会发起n+t个读请求（t可配置，t越大需要带宽越高，生产环境建议配置成1），任意前n份数据返回后就通过解码还原出原始数据即可返回。这里读者会考虑每次读数据都解码是否会影响性能，实际情况每个数据片一般为8M,解码速度平均可达5GB/s以上，所以这里解码不会成为整个IO的瓶颈。当然我们也支持直接读特定的数据块。详细的流程可以参考以前【CubeFS存储技术揭秘系列文章】。

CubeFS采用的编解码引擎库是https://github.com/klauspost/reedsolomon，支持指令集加速。

4.1 CubeFS-LRC

在CubeFS中我们通过两次RS计算实现了一个简单的LRC编码。在CubeFS-LRC中，我们认为全局校验块和数据块的地位是一致的，其在编码时首先会将全局校验块平均分配到不同AZ内，然后由AZ内部的数据块和全局校验块重新计算一次RS码得到本地校验块。

type lrcEncoder struct {
	engine      reedsolomon.Encoder  //用于全局校验块计算
	localEngine reedsolomon.Encoder  //用于本地校验块计算
}

图12. CubeFS-LRC的简单示意

这种方式的优点是工程实现比较简单，依靠简单RS编解码就能满足需求，同时又能满足坏一块盘的数据修复在本AZ内部实现。缺点是部分场景m+1块数据损坏不能恢复,同时数据块更新时产生的跨AZ流量大。但是毕竟m+1块数据损坏的场景非常罕见，只要保证及时修复数据、一般不会出现这种情况。

4.2 Azure-LRC + 1

CubeFS-LRC通过计算两次RS编码来实现LRC，缺点是不能保证m+1块损坏下场景一定能够修复。而Azure-LRC + 1的编码可以容忍任意m+1块数据损坏。实际生成环境中我们限制每个AZ内部只有生成一块本地校验块，因为绝大部分场景都是坏一块盘，并且坏盘后会立刻发起修复。

在AzureLRC+1的实现中，我们通过生成特殊的矩阵，随后使用引擎库的编码接口通过一次编码生成全局校验块和本地校验块。我们通过扩展Jearsure形式的范德蒙矩阵来构造AzureLRC+1的生成矩阵。对于(n,m,k)-AzureLRC+1而言，我们首先构造一个(n,m+1)-RS的Jearsure形式范德蒙矩阵，随后将校验系数的第一行（全1行）按组拆分得到数据块的局部校验块系数，最后将第一行之外的所有校验系数行进行相加得到全局校验块的局部校验块系数。下图是一个(8,4,3)-AzureLRC+1的生成矩阵构造示意。

$$\left[\begin{matrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&0&0&1\\1&1&1&1&1&1&1&1\\1&55&39&73&84&181&225&217\\1&39&217&161&92&60&172&90\\1&73&161&239&220&132&15&24\\1&172&70&235&143&34&200&101\\\end{matrix}\right]\Rightarrow\left[\begin{matrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&0&0&1\\1&55&39&73&84&181&225&217\\1&39&217&161&92&60&172&90\\1&73&161&239&220&132&15&24\\1&172&70&235&143&34&200&101\\1&1&1&1&0&0&0&0\\0&0&0&0&1&1&1&1\\0&245&25&236&91&47&138&254\\\end{matrix}\right]$$

// buildMatrixSpecialJerasure creates the incomplete encoding matrix from buildMatrixJerasure
//
// The top square of the matrix is guaranteed to be an identity
// matrix, which means that the data shards are unchanged after
// encoding.
//
// we generate an totalShards+1 * dataShards Jerasure matrix firstly.
// Then we will delete the XOR-sum row to fit the property of AzureLrc+1's encoding matrix
//
// e.g. to encode the global parity of AzureLrc+1 (n=4, m=2, l=3)
// we will use the matrix on the left side below as the basic vandermonde matrix ((4+2+1)*4)
//
//	 	[[1, 1,  1,   1],			   [[1,   0,   0,   0],
//		 [1, 2,  4,   8],				[0,   1,   0,   0],
//		 [1, 3,  5,  15],				[0,   0,   1,   0],
//		 [1, 4, 16,  64],	 ----->     [0,   0,   0,   1],
//		 [1, 5, 17,  85],				[1,   1,   1,   1],
//		 [1, 6, 20, 120],				[1, 123, 166, 244],
//		 [1, 7, 21, 107]]				[1,  82, 245, 167]]
//
// Then we use elementary transformations to get the jerasure style matrix
// on the right side above and take the last two row as the encoding coefficient.
// This mean we use [[1,123,166,244],[1,82,245,167]] to encode the global parity.
//
// This function is used to encoding the GLOBAL parity of AzureLrc+1
func buildMatrixSpecialJerasure(dataShards, totalShards int) (matrix, error) 

// buildMatrixAzureLrcP1 creates the entire encoding matrix
// with dimensions of (n+m+l)*n for (n,m,l)-AzureLrc+1
//
// The top (n+m)*n row of the matrix is generated by
// buildMatrixSpecialJerasure to caculate the global parity.
//
// The n+m+1 to n+m+l-1 row is 0-1 vector which is used to
// generate the DATA-AZ's local parity. (this is as same as the
// jerasure style vandermonde matrix whose parity number equal to 1)
//
// The last row is the sum of the n+1 to n+m row, which means
// that the PARITY-AZ's local parity is the XOR-sum of all golbal parity.
//
// Warnings: This function has the following limitations for arguments
// * localParityShards is equal to AZ count , actually.
// This means we have only one LOCAL parity in each AZ.
func buildMatrixAzureLrcP1(dataShards, globalParityShards, localParityShards int) (matrix, error)

坏一块盘，在AZ内部的修复流程和CubeFS-LRC流程一样，这里不再赘述。当AzureLRC+1出现m+1块损坏时，我们需要在剩余的n+k-1份存活块中挑选合适的k块数据进行数据修复。此时CubeFS会先调用GetSurvivalShards()接口来获取正确的存活块ID,随后再使用这k份存活数据进行解码操作。该流程与RS唯一的区别便在于：RS码只需要随机获得k份存活数据即可进行解码，而AzureLRC则需要挑选合适的k份数据。

// GetSurvivalShards allows system to select the
// CORRECT n shards to form an invertable decode
// matrix.
//
// the first []int is selected survival index,
// which determines the decode matrix
//
// the second []int is real read shards index,
// which actually participate the decoding
//
// This function is specially design for LRC.
func GetSurvivalShards(badIndex []int, azLayout [][]int) ([]int, []int, error)

4.3 RS码跨AZ流量优化

LRC编码可以节约跨AZ的网络流量，当然相同情况下会增加每个局部校验块的存储成本。如果既不想增加存储成本，又想节约跨AZ的网络流量。我们提供一种折中的方式，在传统RS码的基础上，通过局部解码方式来减少跨AZ的流量，我们以图 13 中的(12,4)RS 为例子来展示这一技术在工程中的应用。

图 13 多 AZ 场景下 RS 码的局部解码示意图

不妨令数据的布局如图 13 所示，当 D1 数据出现故障时，如果采用简单的聚集重构的方法，修复流程所产生的跨 AZ 流量将会达到 5~8 个数据块(取决于参与修复的存活数据的分布)。显然采用这种简单的修复流程会引入巨大的跨 AZ 流量，而这一代价是可以被削减的。

我们利用RS编码的线性性，将损坏数据的修复方程拆分成多个子方程，每个子方程仅对应计算 AZ 内方程式，随后仅跨 AZ 传输子方程计算得到的中间校验数据即可。以图 13 为例，假如 D1 的线性表示为：

$$D_1 = \sum_{i=4}^7 \alpha_{1,i}*D_i +\sum_{i=0}^3 \beta_{1,i}*P_i$$

那么我们仅需在 AZ1 中计算算式的第一个分量，在 AZ2 中计算第二个分量，随后通过网络将其发送给 AZ0 的新节点，两个分量相加便能还原损坏数据 D1。通过这一实现，我们便能将 RS 的跨 AZ修复流量从 5~8 块降低至 2 块。

实现层面我们为局部解码提供了相应的函数PartialReconstruct()，通过传入指定参数就能计算出中间校验块的数据。

// PartialReconstruct is specifically designed for reconstruction
// optimization, which supports the partial decoding with the
// selected survival shards in an AZ
//
// Assum we need to use D0 = x1*D1 + x2*D2 + x3*D3 + x4*P0 to reconstruct
// the D0, while D1 、D2 are stored in AZ0 and D3 、P0 are stored in AZ1.
// Using PartialReconstruct() allows the upper-level application to compute
// intermediate parity containing the specified shards.
// For example, if we pass (shards[][],[D1,D2,D3,P0],[D0]) to the PartialReconstruct()
// and shards[][] only contains D1 and D2, this function will only compute
// x1*D1 + x2*D2 and ADD it into D0.
// P.S. [D1,D2,D3,P0] is used to determine the decoding matrix
//
// The length of the array must be equal to Shards.
// You indicate that a shard is missing by setting it to nil
func PartialReconstruct(shards [][]byte, survivalIdx, badIdx []int) error

4.4 小结

从工程实现与代码维护的角度，CubeFS-LRC是一个非常简单的实现方案。其只需要复用RS编码引擎进行两次计算，便能很好的解决RS码单盘修复跨AZ流量的问题。当然CubeFS-LRC除全局校验块外，引入的局部校验块只能做AZ内坏盘的修复优化，并不能提供容错能力，CubeFS-LRC所能支持的最大任意坏盘数仅等于全局校验数。且如果需要实现纠删码的更新操作，CubeFS-LRC在数据更新方面要承担更多的开销。

如果想要引入的局部校验块也能提供容错能力，同时仍要解决单盘修复跨AZ流量的问题，那么Azure-LRC+1将是优于CubeFS-LRC的选择。此外，由于AzureLRC+1中数据块与校验块的对等地位，其在修复、更新时的开销大致相同，这更有利于系统进行负载均衡。

倘若不愿意承担LRC编码引入局部校验块的额外存储开销，同时又想尽可能减少坏盘场景跨AZ的修复流量，则可以考虑使用传统的RS码辅以局部解码作为折中方案，在存储开销与修复流量上找到一个业务能够接受的平衡点。

参考文献

1. I.S. Reed and G. Solomon, "Polynomial Codes over Certain Finite Fields." Journal of the society for industrial and applied mathematics, 1960, 8(2):300-304
2. J.S. Plank and Y. Ding "Note: Correction to the 1997 tutorial on Reed-Solomon coding." Software: Practice and Experience, 2005, 35(2):189-194
3. L. Rizzo. "Effective Erasure Codes for Reliable Computer Communication Protocols." ACM SIGCOMM Computer Communication Review, 1997, 27(2):24-36
4. J. Blomer, M. Kalfane, M. Karpinski, et al. "An XOR-based Erasure-resilient Coding Scheme.", Technical Report TR-95-048, International Computer Science Institute, 1995
5. J. S. Plank and Lihao Xu, "Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Network Storage Applications," Fifth IEEE International Symposium on Network Computing and Applications*,*2006, pp. 173-180
6. Y. Uezato, "Accelerating XOR-Based Erasure Coding using Program Optimization Techniques," International Conference for High Performance Computing, Networking, Storage and Analysis, 2021, pp. 1-15.
7. S. Mitra, R. Panta, M. Ra, and S. Bagchi. "Partial-parallel-repair(PPR): A Distributed Technique for Repairing Erasure Coded Storage." Eleventh European Conference on Computer Systems, 2016, pp. 1-16.
8. S. Lin, G. Gong, Z. Shen. "Boosting Full-Node repair in Erasure-Coded storage" USENIX Annual Technical Conference, 2021, pp. 641-655.
9. A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran,“Network Coding for Distributed Storage Systems,” IEEE Transactions on Information Theory, 2010, 56(9): 4539–4551.
10. V. Cadambe, A. Mazumdar "An Upper Bound on the Size of Locally Recoverable Codes", International Symposium on Network Coding . 2013,pp. 1-5.
11. S. Goparaju, I. Tamo, R. Calderbank. "An Improved Sub-packetization Bound for Minimum Storage Regenerating Codes." IEEE Transactions on Information Theory, 2014, 60(5): 2770-2779.
12. B. Sasidharan, G. K. Agarwal, P. V. Kumar. "A High-rate MSR Code with Polynomial Sub-packetization Level",IEEE International Symposium on Information Theory. 2015: 2051-2055.
13. M. Ye, A. Barg,  "Explicit Constructions of Optimal-access MDS Codes with Nearly Optimal Sub-packetization." IEEE Transactions on Information Theory, 2017, 63(10): 6307-6317.
14. I. Tamo, Z. Wang, J. Bruck, "Zigzag codes: MDS Array Codes with Optimal Rebuilding." IEEE Transactions on Information Theory, 2013, 59(3): 1597–1616.
15. K.V. Rashmi, P. Nakkiran, J. Wang, et al. "Having Your Cake and Eating It Too: Jointly Optimal Erasure Codes for I/O, Storage and Network-bandwidth",The 13th USENIX Conference on File and Storage Technologies, 2015: 81–94.
16. K. Kralevska, D. Gligoroski, R. E. Jensen, et al. "Hashtag Erasure Codes: From Theory to Practice." IEEE Transactions on Big Data, 2018, 4(4): 516-529.
17. L. Pamies-Juarez, F.  Blagojević, R. Mateescu, et al. "Opening the Chrysalis: On the Real Repair Performance of MSR Codes" The 14th USENIX Conference on File and Storage Technologies,2016,pp. 81-94.
18. M. Vajha, V. Ramkumar, B. Puranik, et al. "Clay codes: Moulding MDS Codes to Yield An MSR Code",The 16th USENIX Conference on File and Storage Technologies,2018, pp.139–153.
19. Y. Shan, K. Chen, T. Gong, et al. "Geometric partitioning: Explore the Boundary of Optimal Erasure Code Repair",The ACM SIGOPS 28th Symposium on Operating Systems Principles.2021, pp.457–471.
20. X. Li, K. Cheng, P. C. C. Lee, et al. "ParaRC: Embracing Sub-Packetization for Repair Parallelization in MSR-Coded Storage",The 21st USENIX Conference on File and Storage Technologies,2023, pp.17-31.
21. C. Huang, H. Simitci, Y. Xu, et al. "Erasure Coding in Windows Azure Storage." USENIX Annual Technical Conference , 2012,pp.2-2.
22. I. Tamo and A. Barg, "A Family of Optimal Locally Recoverable Codes," 2014 IEEE International Symposium on Information Theory, 2014, pp.686-690.
23. M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, et al, "XORing Elephants: Novel Erasure Codes for Big Data.", In 39th International Conference on Very Large Data Bases, 2013.
24. O. Kolosov, G. Yadgar, M. Liram, et al, "On Fault Tolerance, Locally, and Optimality in Locally Repairable Codes.", ACM Transaction on Storage, 2020, 16(2):1-32.
25. Y. Hu, L. Cheng, Q. Yao, et al, "Exploiting Combined Locally for Wide-Stripe Erasure Coding in Distributed Storage.", 19th USENIX Conference on File and Storage Technologies, 2021, pp.233-248.
26. Z. Shen, J. Shu, P. P. C. Lee, "Reconsidering Single Failure Recovery in Clustered File Systems.", 46th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, 2016, pp. 323-334.
27. S. Kadekodi, S. Silas, D. Clausen, et al, "Practical Design Considerations for Wide Locally Recoverable Codes(LRCs).", 21st USENIX Conference on File and Storage Technologies, 2023, pp. 1-16.

< Previous

京东Elasticsearch使用ChubaoFS实现计算存储分离

2020-02-08京东

NEXT >

CubeFS十分钟入门 - 轻松掌握CubeFS对象存储生命周期管理策略

2024-04-22CubeFS

京东Elasticsearch使用ChubaoFS实现计算存储分离 CubeFS十分钟入门 - 轻松掌握CubeFS对象存储生命周期管理策略