萝卜不毒的翻译-修改参考文献

1、基于再生码系统并发错误恢复的设计与实现概述：数据有效性在分布式系统中是起决定性的，尤其在当前节点出故障频繁的情况下。在恢复故障节点中丢失或者不可用数据的时候，关键在于将节点间的数据迁移量最小化。本基于原本设计用于提高容错率和减小带宽的再生码技术，探究数据恢复策略。当前最佳的再生码技术是用于单节点故障的情况。建立了一个系统 CORE，可用于增强现有的重编码技术，使之可以恢复包括单节点和多节点故障在内的故障。在理论上证明了CORE 在多数情况下达到了可行的最小带宽实现了一个 COR 的雏形并且在 20 个节点的 HDFS 集群中评估性能。可以发现 CORE 的雏形与理论结果一致并且与传统基于纠删码

2、的恢复方法相比，可以有效节约带宽。：再生码，故障恢复，分布式系统，编码理论，设计与实现1.介绍为了提供巨大的空间，集群分布式系统被企业广泛部署，比如File System,Amazon Dynamo, 和Azure。在这些系统中，数据是被条带化在许多提供本地空间的结点(或者服务器)上。结点通过网络，以机器集群或者广域设置的形式相互联系在一起。确保数据可用性在分布式系统中是非常重要的，因为结点故障是普遍发生的。可以通过纠删码实现数据的可用性(例如 Reed-Solomon codes41)，其主要是将数据段编码为奇偶校验段，使得数据段和奇偶校验段的自己可以完全重建原始数据。纠删码可以多个结点故障

3、，相比较与多副本，同时还可以减少开销。除了故障，另一个关键的可用性需求是恢复故障结点丢失或者不可用的数据。数据恢复有两个应用场景：(i) 故障结点，数据丢失，需要重新到新的结点上；(ii) 当不可用数据在故障恢复之前被客户端。目前常规的恢复策略，是应用纠删码，重构所有原始数据以获得丢失/不可用数据。由于丢失/不可用数据通常只占原始数据的一小部分，以前的研究探索如何通过最小化以优化恢复策略。一类方法是基于纠删码最小化I/O(例如26，30，42，53，55)，另一类方法是基于再生码最小化带宽(即恢复过程中通过网络传输的数据量)，其中每个幸存的结点最的数据机型编码并发送编码后的数据进行恢复。在网络

4、带宽受限的场景下，最小化带宽可以提高整体的恢复性能。在此，探究在实际分布式系统中部署再生码技术的可行性。大多数现有的恢复方法，包括最小化 I/O 和带宽，仅限于单个故障的恢复。虽然单结点故障在分布式系统39是常见的，但是在实践中，结点故障往往是相关和并发的，就如在集群(例如 14,43)和广域设置(例如6, 20, 33)中的那样。提供并发错误的容错机制，数据通常使用高度冗余进行保护。例如，Cleversafe7，一个商业广域设置系统，每 10 个数据段编码出 6 个奇偶校验段。一些广域系统，例如 OceanStore 和 CFS8，采冗余的纠删码技术(就是原始空间的两倍)。因此，认为最小化带

5、宽的并发恢复为如今大规模分布式系统提供了额外的好处，例如并发故障恢复是有利于延迟立即恢复的，2，50。也就是说，能够在达到极限的时候进行恢复操作。这避免了不必要的恢复如果故障是暂时的并且数据很快就能得到(例如，在重启故障结点之后)。鉴于并发故障恢复的重要性，提出下列问题：(1)可以基于再生码在并发恢复的时候达到减小带宽的目标吗？(2)如果可以应用再生码在并发恢复中，那么可以将其无缝整合到使用的分布式操作系统吗？在本文中，提出了一个完整的 CORE 系统，它支持单个结点和并发故障的恢复并能最小化带宽。CORE 在当前设计用于单结点故障恢复的再生码技术中增加内容，使之能够支持并发故障恢复。一个关键

6、的要点是它保留了原有的再生码代码结构和底层再生码数据。也就是说，并没有提出提出新的编码方式，CORE 在现有的再生码技术顶部添加了一个新的恢复方案。其主要是与每一个故障结点恢复所需要相同的数据，然后展示可以并发恢复所有故障结点。这项工作包含 CORE 在理论和应用两个方面。在理论方面，展示了 CORE 在大多数并发错误情况下实现了最小带宽。也提出了 CORE 的一个扩展，使之在其余情况下达到次优的带宽节省。的分析研究证实对比与基于纠删码的传统恢复策略，CORE 在并发恢复中可以达到显著的带宽节省。例如，对于(20，10)，带宽节省在最优和次优情况下分别为36-64%和 25-49%。还通过分析

7、得出 CORE 的耐久性明显高于常规恢复策略。实现了一个 CORE 的原型并展示实际部署的可能性，或者说是在实际的在应用方面，分布式系统中应用再生码技术。最为概念的证明，选择了Hadoop 分布式文件系统(HDFS)49作为起点。CORE 最为HDFS 的顶层用以支持一般性的故障恢复。还采用了流水线实现并发操作以加快恢复过程在多达20 个结点的HDFS 上广泛试验CORE系统，结果显示，与纠删码相比，CORE 达到恢复吞吐量的增益分别为单结点 3.4 倍，多结点 2.3 倍。的试验结果符合理论研究，同时还评估了结点故障情况下的 MapReduce 性能。注意到对实际部署再生码的研究仍然非常少，

8、CORE 系统的实现提供了在实际系统中部署基于再生码恢复策略可能性的先行试验。的系统模型，第三节介绍 CORE 的设计和本文的其余部分如下，第二节制定的分析结果，第四节描述 CORE 的实现细节，第五节展示实验结果，第六节回顾相关工作，第七节公开，最后，第八节总结这篇文章。也提供补充文件给读者作其他分析研究。2.系统模型2.1. 基础首先定义术语和符号， 表 1 总结了本文中主要使用的符号。考虑一个由若干个个结点集合组成的分布式系统，每一个结点代表一个物理设备。这个系统包含n个节点，标记为 N0，N1，.，Nn-1，其中 k 个节点（称为数据节点）原始（未编码）数据，剩余的 n-k 个节点（称

9、为奇偶校验节点奇偶校验（编码）数据。 编码结构是系统的，意思原始数据保存在器中。表 1中主要符号图 1 显示了分布式系统的一个示例，这也与称为 HDFS-RAID 22的基于纠删码 HDFS模块一致。每个节点多个段。段是系统中读/写操作的基本。如果它保存原始数据/奇偶校验信数据，则称为数据段，如果保存奇偶校验数据，则成为校验段。为了息，的数据分成包括 k 个数据段和 n-k 个校验段的集合。为了生成奇偶校验段，每个数据（奇偶校验）段被分割为由r 个包组成的，固定大小的数据（奇偶校验）条带，包是编码/操作的基本。每个奇偶校验条带是从 k 个数据条带编码得来的，一个条纹n节点数Ni第 i 个节点k

10、数据节点数r每个条带的数据包数目t节点并发故障数M的原始数据的大小si,j第 i 个节点的第 j 个包ei,i第 i 个节点用于恢复 i节点的编码包是由 k 个数据条和（n-k）奇偶校验条组成条纹，编码是在每个条纹内完成的。一个数据（奇偶校验）段包含所有数据（奇偶校验）条，因此每个n 个段的集合包括多个条纹。每个集合中的 n 个段分布在 n 上节点。为了负载平衡的原因，数据/奇偶校验节点被轮流使用，使得数据和奇偶校验段在节点上均匀分布30，36。图 1 分布式系统示例每个条带独立编码。的从而集中于单条带并且的恢复方案将基于每个条带操作。 令 M 为在条带中的原始未编码数据的总量。 让 si,j

11、 是在 Ni 结点偏移为 j 的包，其中 i = 0,1，.，n-1，j = 0,1，.，r-1。条带包含 nr 个的数据包，可以基于 Galois域算术，通过将 nrkr 生成矩阵乘以向量 kr 原始数据包来形成，其实现细节可以面前人的研究中找到17。GF（28）上的算术。注意工作的重点是在伽的恢复方案适用于数据和奇偶校验节点的故障。无论它是数据还是奇偶校验分组，它都以相同的方式处理每个的分组 si，j。对于数据可用性，有部署为最大可分距离（MDS）的系统，意味着任何 k 的数据节点可以用于重建原始数据。也就是说，（n，k）MDS 编码的系统可以任何 n个结点的 n-k 个故障。 MDS 代

12、码也确保最优效率，例如这个系统中每个条带M/k 个数据。-（RS）编码41是 MDS 代码的典型示例。 RS 码可以应用在条带大小 r = 1 的情况来最小化生成矩阵。2.2. 恢复的恢复解决两种类型的结点故障，第一种是从性故障中恢复(例如结点)，其中的数据丢失了。在这种情况下，在一个新结点上重建故障结点的数据以最小化故障影响。另一种情况是降级读暂时不可用的数据(例如由于系统重启或升级)或者在故障之前被恢复。这样的数据需要用降级读的方式从其他可用结点上重建数据。在的中，使用“丢失的数据”来指代性丢失数据和暂时不可用数据。当出现一个或者多个结点故障的时候，系统激活恢复进程。显然，需要 tn-k，

13、否则原始数据不可能被恢复。根据失败结点数量来区分失败模式，丢失的数据将会被重建到幸存结点中。的恢复策略简历在relayer 模型上，通过一个守护进程同步协调恢复操作。图 2 描述了relayer 模型，在恢复期间，每个幸存结点执行两个操作：(i)I/O：它本地数据，(ii)编码：组合的数据成某些线性组合，这对某些纠删码结构(见第 2.3 节)是必要的。Relayer守护进程执行三个步骤：(i)：来自其他幸存结点的数据，(ii)：使用的数据丢失的数据，(iii)上传：上传出的数据到新的结点(对于性故障恢复)或者请求数据的客户端(用于降级读时)。假设 relayer 在恢复过程中是可用的。注意到，

14、这个relayer 模型在先前的研究中已经用到，比如对等2，数据中心3和基于的云23.图 2 使用relayer 恢复N0 和N1最小化网络数据传输，对于网络带宽限制的分布式系统的性能是非常大的。如果结点故障的数量很少，那么从幸存结点的数据量将会大大超过恢复出来的数据量。如果同步和上传操作(见第 4.2 节)，那么就会成为瓶颈。因此，在恢复中着重优化步骤。正视地，定义在恢复过程中，每个条带从幸存结点的数据量为恢复带宽。的目标是最小化恢复带宽。2.3. 再生码当常规的纠删码编码系统检测到故障时，relayer 从任意 K 个存活的结点数据并恢复丢失的数据称之为传统恢复策略。传统恢复策略的数据量和

15、原始数据量是相等的(例如每个条带M 个数据单元)。注意到一些纠删码重建过程允许较少的数据(参考第 6 节)。无论如何，传统恢复策略只应用于 MDS 纠删码和少于 n-k 个结点故障的情况。在本文中，当提及纠删码，假设传统已经使用了传统恢复策略。考虑一种，称之为再生码11的允许 relayer少于原始数据的特殊编码类型。再生码是简历在网络编码1的基础上，即恢复过程中，幸存结点计算和发送编码数据到relayer，然后得出丢失数据。每个编码包是幸存结点所数据的线性组合(也可能与原始数据相同)。它表名再生码位于成本和恢复带宽之间权衡曲线的最佳位置上。有两再生码(MSR)和最小恢复带宽的最小带宽再生码个

16、：每个结点最少数据的最小(MBR)。注意 MSR 再生码具有最佳的效率并且是 MDS(见第 2.1 节)，而 MBR 再生码通过牺牲开销达到带宽最小化。在这项工作中，关注 MSR 再生码。现有的最佳 MSR 是被设计用于单结点故障恢复的，如下所述。首先，条具有 r =n-k 个实现最小可能带宽。在恢复期间，relayer 从 n-1 个幸存结点中的每一个结点一个编码包。令 ei,i从结点 Ni用于结点 Ni处数据恢复的编码包。每个编码包 ei,i是每个幸存结点中的数据包 si,0, si,1, , si,r1 的一个组合，并且和的数据包相同大小。使用编码包，relayer得出故障结点丢失的数据

17、，。MSR 再生码单结点故障恢复达到的最小化恢复带宽为：然而，如果多余一个节点故障，则最佳 MSR 再生码并不能连接到 n-1 个幸存结点并达到如等式(1)所示的带宽节省。为了恢复并发节点故障，一个直接的方法是使用常规方法，从任意 K 个幸存结点和原始数据一样大小的数据量。这篇文章探索是否能够在恢复并发故障的时候达到节省恢复带宽的目标。3.CORE 的设计CORE 建立在现有的用于单节点故障恢复的 MSR 代码结构上。CORE 有两个主要的设计目标，首先，CORE 保留现有代码结构和的数据，也就是说，仍然有数据条带并且存储为现有的 MSR 代码结构，而 CORE 则作为现有 MSR 再生码结构

18、的上层使之同时能够恢复单节点故障和多节点故障。MSR 再生码的最优效率依然被保留。第二，CORE 旨在当故障节点数 t(tnk)是变化的时候，达到最小化恢复带宽，而不需要在代码重建和数据被之前确定 t 的数值。在本节中，首先描述 CORE 的基准方法，其中扩展了现有的最优单节点故障恢复方案以支持并发故障恢复(第 3.1 节)。注意到 CORE 的基准方法不适用于一小部分故障模式，因此提出一个简单的扩展，其仍然可以减少恢复带宽(第 3.2 节)。理论结果表名 CORE 可以在大多数故障模式下达到最优结果(见 3.3 节)。最后，分析减少恢复带宽(第 3.4 节)和可靠性(第 3.5 节)。的电子

19、补充文件中，提出第 3.3 节中所述的定理证明。也提供基准 MSR 编在码和立即恢复策略对于恢复带宽节省的额外分析。3.1. CORE 的基准方法首先提供现有 MSR 再生码的背景结构。然后定义 CORE 的构建块，并解释 CORE如何使用这些构建块来支持并发故障恢复。背景 CORE 建立在现有的最优 MSR 代码结构上，包括erference Alignment(IA) codes 44, 46, 51 和 Product-Matrix (PM)codes 37。这里，提供一个 IA codes如何工作的概述，PM codes 的工作方式类似。IA codes 最初在46数据段的编码算法和5

20、1就校验段的算法中提出(后来称之为 MISER 码44)。从一个高角度来看，IA codes 扩展了无线通信中对齐干扰的想法并应用 到分布式系统的故障恢复中。回想一下每个条带在使用再生码时，包含 k（n-k）个原始数据包（见第 2.1 节）。每个的包可以被视为k(n-k)原始包的线性组合。假设数据结点出故障(奇偶校验节点也一样)，n-1 个幸存节点计算n-1 个编码分组(表示为 y = (y1, , yn1)T)。relayern-1 个编码出n-k 个丢失的数据包(表示为 x1 = (x1, , xnk)T)。还有其他(k-1)(n-k)个数据包(表示为 x2 =(x(nk)+1, , xk

21、(nk)T)是不需要生成的，因此可以视为干扰信号。可以将y 用 x1 和x2 表示出来：对于一些系数分别为（n-1）(n-k)的矩阵 A 和（n-k）和（n-1）（k-1）（n-k）的矩阵 B。通过基本行操作，可以转换等式为：此时变换矢量 y，变换矩阵 A和 B分别为(nk)(nk)和(k1)(k1)(nk)。注意到 IA codes确保存在一些变换使得 A是可逆矩阵，从而可以唯一求解 x1(即丢失的数据包)。IA code 构造的生成矩阵满足上述属性，PM codes 使用不同的生成矩阵，但是有着类似的思想。希望读者参考37，44，46，51关于生成矩阵设计的数学细节。，实现干扰对齐的构建体

22、代码已经在几年内具有性的话题。注意，IA codes 和 PM codes 都有参数约束，IA codes 要求 n2k，PM codes 要求n2k-1。在这项工作中，关注双冗余 n=2k 的情况，这也被视为是最先进的分布式系统，如OceanStore 31和 CFS 8。尽管对于（n，k）比较大的情况，冗余开销高于传统 RAID-5 和RAID-6 编码，但它仍然低于在实际系统（如 GFS 15和 HDFS 49）中使用的传统 3路。构件块观察得出任何最优MSR code结构可以由两个函数定义。令Enci,i为由节点Ni调用，使用节点Ni中的r = n k个包作为输入，为故障节点Ni生成编

23、码分组ei,i的编码函数，令Deci是使用来自其他n-1个幸存节点的编码包作为输入，返回故障节点Ni的n-k个包的函数。Enc和Dec都根据特定的代码结构来定义所的分组si，j的线性组合的操作。根据上面的，Enc是构造编码分组的y，而Dec是丢失的分组的x1。CORE用于任何最佳MSR code结构只要函数Enc和Dec能够被很好地定义，Enc和Dec两个函数了CORE的构件块。基准方法的主要考虑下来用于恢复的两种编码包：真实包和虚拟包。为了恢复t个失败节点中的每一个（其中t 1），如果它连接到n-1个节点，则relayer仍然工作，但是这次它表示要从故障节点作为虚拟包的包， 剩余的n-t个存

24、活节点作为真实包。 现在，使用Enc和Dec，计算每个虚拟分组作为的真实分组的函数。 最后，使用的真实分组和重构的虚拟分组，可以对失效节点中丢失的分组进行。图 3 relayer 如何用于故障节点 N0 和 N1 的恢复的真实和虚拟分组的示例。示例使用图 3描述的想法，图 3展示了具有（6,3）节点数并且具有故障N0和N1。两个编码分组e1,0和e0,1是虚拟且存在真实包。可以基于Enc和Dec单故障恢复表示e1,0和e0,1为：编码包e1,0通过对的包s1,0，s1,1和s1,2进行编码来计算，所有包可以基于单故障恢复从其他编码包e0,1，e2,1，e3,1，e4,1和e5,1中恢复。因此，

25、e1,0可以表示为编码包的函数。 以类似的方式表示编码包e0,1。 现在，有两个方程，有两个未知数e1,0和e0,1。如果这两个方程是线性独立的，可以求解e1,0和e0,1。 然后可以应用Dec0和Dec1来N0和N1的丢失包。一般来说，为了恢复t个失败的节点，总共有t（t-1）个虚拟包。 我们可以基于上述想法t（t-1）方程。 如果这些t（t-1）方程是线性独立的，可以解决虚拟包问题。 一个小是方程组可能没有唯一的解。在下一小节中解释总结我们对这一问题的方法。3.2. 恢复任何故障模式的目标是通过解方程组来表示虚拟包作为真实包的函数。然而，注意到对于一些故障模式（即故障节点数目），等式组不能

26、返回唯一解。 如果可以将虚拟包唯一地表达为真实包的函数，则说故障模式是好的，否则是坏的。的目标是即使对于坏的故障模式也降低恢复带宽。首先研究恢复坏的故障模式的可能性。然而，量化这种可能性的理论证明是有性的，因为它的可能性取决于代码构造。观察到IA和PM codes对于相同的参数（n，k）和t具有不同的可能性。幸运的是，在实际部署中，即使系统包含大量节点，条带大小n总是被限制为一个相当小的值，以避免额外的编码开销30，36。 因此，采用枚举，这足以满足实际使用情况，并使能够提前识别所有坏的故障模式。 具体地，给定（n，k）和t个故障，那么就有(n t)个可能的故障模式。枚举IA codes 和P

27、M codes所有可能的故障模式，并检查它们是否都是坏的。图 4展示了（n，k）和t的不同组合的坏故障模式的百分比。观察到，在考虑的所有参数中，坏故障模式仅占很小的百分比，IA和PM codes分别最多为0.9和1.6。 此外，对于某些参数集，没有发现任何坏的故障模式。 然而，即使它们很少，仍然希望减少这种不良故障模式的恢复带宽。图 4 不同 n，k，t 下坏模式的比例现在扩展的CORE基准方法来处理坏的故障模式，目标是相较于传统恢复方法，能够减少恢复带宽。 对于坏的故障模式F，包括一个附加的幸存节点并形成虚拟故障模式F，转换过程为| F| = | F | + 1 = t + 1。然后，rel

28、ayer从对F的丢失数据进行所需的F外的n-t-1个节点数据，尽管实际上只需要F的丢失数据。 图 5显示了如何使用虚拟故障模式进行恢复，如果F仍然是一个坏的故障模式，那么在F中包括一个额外的幸存节点，并重复，直到找到一个好的故障模式。 注意，F的大小必须由n-k来限定，保证我们总是可以总是连接到k个幸存节点以重建原始数据。图 5 使用虚拟故障模式为（6,3）代码的示例。 如果原始故障模式N0，N1是坏的，则我们可以改为恢复虚拟故障模式N0，N1，N2，并且仅从节点N3，N4，N5编码分组。坏故障模式的数量取决于代码构造和参数（n，k）。 推断坏故障模式的存在仍然是一个悬而未决，并且是未来的研究

29、工作。3.3. 理论结果提出两个定理。 第一个显示恢复带宽的下限。 第二个表明 CORE 实现了好故障的下限定理 1：假设恢复 t 个失败节点。恢复带宽的下限为：定理 2：CORE 建立在用于单故障恢复的 MSR code 上，如果恢复好故障模式，则能达到定理 1 中的下限。由于大多数故障模式是好的（对于 IA codes 和 PM codes 分别至少为 99.1和 98.4），得出结论，CORE 最小化了大多数故障模式的恢复带宽。 在下一小节中，展示 CORE在好模式和坏模式下的实际带宽节省。3.4. 带宽节省分析现在研究的 CORE 和传统恢复方法的带宽节省情况。定义 CORE 的恢复带

30、宽与常改变（n，k）和要恢复的故障节点的数量 t 来计算不同规恢复带宽的比值为带宽比。情况下的带宽比。首先考虑好模式。 对于 CORE，恢复带宽达到定理 1 中得出的下限，可以直接应的原始数据的量。 图 6（a）显示了带宽比。用理论结果。 对于常规恢复，恢复带宽是观察到 CORE 在单个和并发故障中实现带宽节省。 对于单个故障（即 t = 1），CORE直接使用现有的再生码，并且将恢复带宽节省 70-80。 对于并发故障（即 t 1），CORE也了带宽节省，例如对于 t = 2，t = 3 和 t = 4 的情况，分别为 44-64，25-49和11-36。 随着 t 增加，带宽节省减小，因为

31、需要重建的丢失数据，并且需要检索的原始数据量。 另一方面，带宽节省随着（n，k）的值而增加。 例如，当(20，几乎10)，2 t 4 时，节省是 36-64%。图 6 CORE 的恢复带宽占传统恢复策略的的比率现在研究 CORE 对坏故障模式的表现。 回顾第 3.2 节中对于每个坏故障模式 F，CORE生成好故障模式的虚拟故障模式 F。根据第 3.3 节中的理论结果计算 F的恢复带宽。图6（b）显示了带宽比。发现，在所有情况下，将一个幸存节点添加到 F（即| F| = | F | +1）就足够了，并且获得了好故障模式。 因此，坏 t-模式的 CORE 的恢复带宽总是等同于好（t + 1)-故障

32、模式的恢复带宽。 从图中，仍然看到 CORE 的带宽节省比传统恢复。 例如，当 2t4 时，节省是 25-49。3.5. 可靠性分析使用模型进行 CORE 和常规恢复的可靠性分析。 令X 是表示直到系统的数据变得不可恢复所经过的时间的随量。到数据丢失的平均时间（MTTDL）定义为 X 的期望值。尽管 MTTDL 有其缺陷18，但它已被广泛用于分析系统的可靠性（例如14）和纠删码（例如，16，26，42）。只使用 MTTDL 进行可靠性进行比较不同的恢复性能，而不是量化系统的真实可靠性。图 7显示了（n，k）下的模型。 令状态t(0 t n k)表示系统具有t个故障，状态n-k + 1表示系统具

33、有多于n-k个故障，其数据变得不可恢复。 为了简化问题，假设节点故障独立发生，并具有恒定的机率，如在先前的研究中所述（例如，14，16，26，42）。让表示单个节点的故障率。因此，从状态t（其中0tn-k）到状态t + 1的转换率是（n-t）。 在并发恢复（假设使用2.2节中的relayer模型）中，每个状态t（其中1tn-k）转变到状态0的转换率为t，t取决于所使用的恢复方案。 为了计算t，令B是从存活节点用于恢复的数据的传送速率，S是单个节点的容量（原始数据的量是kS）。 为了恢复t故障，在大多数情况下（参见定理1和2），CORE）/k（n-k）kS个数据单元，因此t=t = (nk)B/

34、)S；常规恢复kS数据，因此t= B/kS。 一旦使用模型，可以通过计算达到状态n-k + 1的时间来获得MTTDL。读者详读的MTTDL16的推导。图 7 可靠性模型使用（n，k）=（16,8）作为例子来比较CORE和常规恢复的MTTDL。MTTDL由三个变量确定：每个节点的容量S，传输速率B和节点故障率 首先，确定平均故障时间1/ = 4年42，S = 1TB，并评估B对MTTDL的影响。 图8（a）显示了MTTDL结果。 随着转移速率的增加，CORE和常规回收率的回收率和MTTDL都增加。接下来固定B = 1Gbps和S = 1TB，并评估在MTTDLs中的影响。 图8（b）示出了结果。

35、 CORE和常规恢复随着增加而MTTDL减少。 从图 8（a）和图 8（b）中，CORE具有比常规恢复（10-100倍）更大的MTTDL，因为它具有较高的恢复率和较少的恢复带宽。例如，考虑T = 1TB，B = 1Gbps，= 0.25，CORE的MTTDL是常规恢复的26倍。图 8 比较不同传输速率和节点故障率下 CORE 和常规恢复的 MTTDL4.实现用实现的一个 CORE 原型补充的理论分析。 作为一个概念证明，CORE 实现为 Hadoop 分布式文件系统（HDFS）49的一个扩展。修改HDFS 的源代码和它的纠删代码模块HDFS-RAID 22。需要的是，CORE 也适用于一般大规

36、模分布式系统。4.1. HDFS-RAID 概述在 HDFS 49中的文件被划分为大尺寸块（默认为 64MB），在本文中称为“段”，并形成 HDFS 读/写操作的基本单元。 默认情况下，HDFS 为每个段保留三个副本以实现数据可用性。 为了提供具有较小开销的数据可用性，HDFS-RAID 被设计为将副本转换为纠删码数据，并在不同节点上分配纠删码数据。称整个转换过程为条带化操作。HDFS-RAID 使用分布式 RAID 文件系统（DRFS）来管理在 HDFS 中的纠删码数据。HDFS-RAID 添加了一个名为 RaidNode 的新节点，该节点执行条带化操作并协调恢复操作。此外，HDFS-RAI

37、D 提供了称为 DRFS 客户端的客户端接口，它处理对在 HDFS 中的纠删码数据的所有读/写请求。 如果请求了丢失的段，则其对丢失的段执行降级读。条带化操作如下进行。 对于给定的（n，k），RaidNode 首先一组 k 个段（每个段的一个副本）。 然后，它以段为，将k 个段编码为 n 个段（见第 2.1 节）。 然后将 n 个段放置在 n 个DataNode 上。 k 个分段的未使用副本之后将从 HDFS 中删除。 RaidNode 对另一组 k 个段重复相同的过程。4.2. 整合到 HDFS-RAID 中为了将的 relayer 模型集成到 HDFS-RAID 中，可以分别在 RaidN

38、ode 和 DRFS 客户端中部署一个 relayer 守护进程，用于故障恢复和降级。 CORE 在 HDFS 版本 0.22.0 上实现，并启用 HDFS-RAID。修改 RaidNode 和 DRFS 客户端以支持并发恢复。 由于再生码需要 DataNodes 在恢复期间生成编码数据包，因此在每个 DataNode 中添加一个信号处理程序，以响应编码数据包的请求。在恢复期间，RaidNode 或 DRFS 客户端向幸存的 DataNode 通知故障节点的位置，然后DataNode 相应地生成编码包。代码优化 在当前的原型中，分别实施 RS 码41和 IA 码51作为纠删码和再生码的候选。在

39、 HDFS-RAID 的 ErasureCode 模块中实现它们。 为了最小化编码/操作的计算开销，使用 Jerasure 库36实现 C +中的编码方案，并使 ErasureCode 模块通过Java 本地接口执行特定的编码方案（HDFS-RAID 是用 Java 写成的）。 对于实现的每个代码，添加 XOR 变换3，其将所有编码/操作改变为纯异或操作，以及 XOR 调度21，以减少编码/期间的 XOR 操作。在 Jerasure 库36中都提供 XOR 变换和XOR调度。图 9 在 CORE 中用流水线实现于恢复操作的示意图，假设恢复单个故障。相同的流水线实现应用于条带化（在 RaidNo

40、de 中）和降级的（在 DRFS 客户端中）。流水线模型 原始的HDFS-RAID 使用单线程实现。 为了进一步加速，实现了一个流水线模型，利用多线程来并行化编码/操作。 图 9 显示了在 CORE 中的流水线设计的实现，假设要恢复单个故障。 RaidNode 从 NameNode 请求元数据（步骤 1-2）并从幸存节点段（步骤 3-4）。 然后 RaidNode 使用流水线实现重建丢失的数据，流水线实现由三个阶段组成。 首先，有一个输入线程，从幸存的 DataNode 收集数据。 对于再生码，输入线程从 DataNode 提取相应的编码包。 然后，输入线程通过共享循环缓冲区将数据分派给工作线

41、程，该工作线程对故障节点的丢失数据进行。 它将的丢失数据发送到输出线程，然后输出线程上传生成的段（步骤 5）。5.原型实验系统测试 CORE。主要的部署问题是恢复的总体性能由包括网络带宽，使用分布式磁盘 I / O，编码/开销的的组合确定。解决以下问题：（i）最小化恢复带宽是否在提高整体恢复性能方面发挥关键作用（见第 5.1 节）？（ii）CORE 能否保持 HDFS-RAID提供的正常条带化操作的性能（见第 5.2 节）？ （iii）CORE 能提高恢复，降级和MapReduce 的性能（参见第 5.3-5.5 节）多少？在具有一个 NameNode 和 20 个 DataNode 的 HD

42、FS 测试台上进行实验。 每个节点运行在配备有el Core i5-2400 3.10GHz CPU，8GB RAM 和希捷ST31000524AS 7200RPM 1TBSATA 硬盘的四核电脑上。 所有机器都配有 1Gb / s 以太网卡，并通过 1Gb / s 以太网交换机互连，并且都运行 Linux Ubuntu 12.04。比较常规恢复的 RS 代码41和建立在 IA 代码51（参见第 4.2 节）上的 CORE。 这两个代码在 C +中实现，并使用带有-O3 选项的 g + 4.6.3 编译。的微基准（见5.1 节）在 10 次运行中取平均值，而宏在 5 次运行中取平均值。5.1.

43、 微观基准研究在本小节中对恢复操作进行微观基准研究首先评估性能与分组大小的关系。然后提供不同恢复步骤的逐步分析。性能 为了评估 RS 码和 CORE 在恢复中的计算开销，测量 relayer 使用从幸存节点的包来丢失的数据的时间。 由于操作是在数据包上执行的（参见第 2.1 节），研究包大小对性能的影响。包大小从 8 字节改为 32KB。 评估对不同组（n，k）的 30 条数据进行操作。 为了显示测试的计算性能，通过预先加载需要的数据来消除磁盘 I / O 的影响。 然后，测量对内存中数据执行所有操作的时间。计算吞吐量，定义为丢失数据的大小除以时间。图 10 RS 码和 CORE 的吞吐量图

44、10 展示了针对 RS 码和 CORE 的一至三个故障的吞吐量。 更大的（n，k）意味着可以的故障，但是具有更小的吞吐量，因为生成矩阵变得更大并且开销更高。 注意吞吐量趋势与分组大小也符合研究中不同纠删码的结果36。 吞吐量最初随着分组大小而增加，并且当分组大小为大约 4KB 到 8KB 时达到最大。 当分组大小进一步增加时，吞吐量由于高速缓存缺失而下降36。RS 码具有比 CORE（基于 IA 码）更高的吞吐量。 原因是虽然 CORE 从幸存节点比 RS码更少的数据（即更少的包），但是它来自（n-t）t 个的包的每个丢失的包，而 RS 码来自 k 个的包的每个丢失的包。 因此，CORE 对于

45、相同（n，k）具有比RS 码更高的计算复杂度。 然而，在所有情况下，认为，CORE 在数据包大小为 8KB时至少有 500MB / s 的吞吐量。接下来的基准表明，性能不是恢复操作的瓶颈。细分分析 回想图 2，恢复操作可以分解成五个不同的步骤。现在对 RS 码和 CORE 中每个恢复步骤的预期性能进行简化分析。的目标是识别瓶颈，以证明最小化恢复带宽的需要。表 2 在 RS 码和 CORE 中在（20,10），每个节点 1GB 数据时，不同恢复步骤的时间比较time(s)RSt=1RSt=2RSt=3COREt=1COREt=2COREt=3I/O8.838.838.838.838.838.83

46、每个节点的容量固定为 1GB。 假设用总共 tGB 的数据来恢复 t 个失败的节点，并且使用（n，k）=（20,10）。基于的测试台硬件上的测量收集系统参数，并且导出每个恢复步骤的预期时间，如表 2 在 RS 码和 CORE 中在（20,10），每个节点 1GB数据时，不同恢复步骤的时间比较所示。详细阐述的推导如下。I / O 步骤。 在 RS 码和 CORE 中，每个存活节点所有的数据。 对于的磁盘模型，的测量（使用 Linux 命令 hdparm）表明磁盘速度为 116MB / s。 假设所有幸存节点并行数据，在 I / O 步骤中，这两种方案都需要 1GB116MB / s 8.83s。

47、编码步骤。 在 RS 码中，幸存节点不执行编码，而在 CORE 中，幸存节点编码其的数据。假设所有幸存节点并行执行编码步骤。的测量表明，对于 1GB 的原始数据，i5-2400机器上的编码时间不超过 0.4 秒。步骤。 relayer 通过其 1Gb / s 接口从其他存活节点数据，因此其有效传输速率的上限为 1Gb / s（或 125MB / s）。 对于 RS 代码，继电器总是相同量的原始数据，即 k1GB= 10GB。 对于 CORE，只考虑良好的故障模式，因为这是大多数情况（参见第 3.4 节）。从定理 1，继承者0.1t（20-t）GB 的数据（其中 t 1 时仅重建一个丢失段，则可

48、以使用甚至更少的恢复带宽。 然而，的结果仍然显示 CORE 相对于常规方法的改进。5.5. 带节点故障的 MapReduce 运行MapReduce9是在 HDFS 上运行的一个重要的数据处理的框架。在这里，进行在节点故障情况下，CORE 是如何影响一个 MapReduce 工作性能的。使用 MapReduce 运行经典的 WordCount 作业来计算文档集合中的单词。 Word-Count作业运行两种类型的多个任务：任务从 HDFS段，并将每个字发送到 reduce 任务，reduce 任务聚合多个任务的结果。 对于节点故障，一些任务可能执行到不可用段的降级。考虑与第 5.4 节中相同的评

49、估设置。 这里，关注（20,10）。对从 Gutenberg获得的 10GB 纯文本数据运行一个 WordCount 作业19。 使用 CORE 或 RS 代码，对DataNodes 中的编码段进行条带化，禁用 t 个节点以模拟 t 节点故障，然后对编码数据运行WordCount 作业。还在没有故障时考虑基线 MapReduce 工作性能。使用默认的MapReduce 调度程序来调度 DataNode 上的任务。测量不同类型的 MapReduce 任务的运行时性能：（i）运行在正常节点的可用数据上的正常任务的平均运行时间，（ii）运行在故障节点不可用数据上的降级任务的平均运行时间，以及（iii

50、）reduce 任务的平均运行时间。map / reduce 任务的运行时间定义为从调用任务初始化函数直到调用任务完成函数的持续时间。捕获要处理的段的时间为 map 任务的运行时间;如果 map 任务降级并不可用的数据，则它会降级读。另一方面，reduce 任务的运行时间仅包括 map 任务的中间结果的处理时间（即从 map 任务传送数据到reduce 任务的时间被排除）。除了任务运行时，还测量 WordCount 作业的总体运行时间，即定义为从开始到完成的持续时间。图 14 显示了不同 MapReduce 组件的运行时间。 对于正常的 map 任务和reduce 任务，它们的运行时间几乎与基

51、线相同，这意味着 CORE 对这些任务没有不利影响。 由于降级的，降级的任务所花费的时间比基线长。 然而，CORE 在该项目中优于 RS 代码。 对于 t =1,2 和 3，CORE 比 RS 码少 29，22和 18的时间运行降级 map 任务。 结果也符合我们的理论发现。在正常 map 任务上的降级 map 任务的额外运行时间主要是由于降级的读请求。 考虑 t = 1。对于 RS 代码，额外的运行时间是 12.4s，而对于 CORE，额外的运行时间是 2.96s（或少 80）。 这与在第 3.4 节中的分析结果一致。图 14 不用 MapReduce 任务的运行时间CORE 还提高了Wor

52、d-Count 作业的总体运行时间，尽管由于其他开销，改进不那么明显。另一方面，期望在网络带宽有限的大规模分布式设置中，CORE 的改进变得更加显着。 我们认为这里的 MapReduce 评估是初步的。计划在未来的工作中考虑的工作负载和测试环境。6.相关工作回顾有关恢复问题的纠删码和再生码的相关工作。最小化 I / O 几个研究集中在最小化在纠删码中恢复单个故障所需的 I / O。 他们的方法主要集中在磁盘阵列系统，其中磁盘是瓶颈。 53，55的作者提出了 RAID-6 代码的最佳单一故障恢复。 Khan et al。 30表明，找到任意纠删码的最佳恢复解决方案是NP-hard问题。 注意，上

53、述解决方案相对于常规恢复的性能增益通常小于 30，而再生码在单个故障恢复中获得高得多的增益（见第 5 节）。13，26，34，423 的作者已经提出了在恢复丢失的数据时减少带宽和 I / O 的本地恢复代码。 他们评估云系统模拟器（例如34），Azure（例如26）和 HDFS（例如13，42）。 值得注意的是，本地恢复编码是添加额外奇偶校验数据到器用以获得更好的恢复性能的非 MDS 编码。 所有这些研究集中在优化单一故障恢复。的工作在几个方面与它们不同：（i）考虑最佳的最小再生代码，即 MDS 代码，（ii）考虑恢复单个和并发故障，（iii）实现和执试实验，需要节点执行编码操作。最小化带宽。

54、 再生码11最小化了分布式系统中单个故障恢复的带宽。 已经有许多关于构建再生代码的理论研究（例如，4，11，35，37，38，44，51，52）。 大多数再生码构造需要幸存节点在恢复期间对的数据进行编码。 一些再生码构造（例如，23，40，45，54）在恢复期间消除这种编码操作，以便最小化 I / O 和带宽，但是它们做出不同的权衡 (见24中的)。再生码的实现研究最近受到了研究团体的关注，如12，23，27，28。 注意，研究12，27，28没有将再生代码集成到真正的系统，而NCCloud 23实现了基于非系统化的再生码的原型。并行恢复。几个理论研究（例如，25，29，47，48）基于再生码

55、来解决并发故障恢复，并且它们专注于在新节点上恢复丢失的数据。他们都考虑一个合作模型，其中新的节点之间交换他们在恢复期间从幸存节点的数据。 25，29的作者证明合作模型实现了与相同的最佳恢复带宽，但它们不提供实现最优的再生码的显式构造。 47，48的作者提供了这样的显式实现，但是它们集中在有限的参数上，并且所得到的实现不提供任何超过纠删码的带宽节省。合作模型的缺点是新节点需要执行操作并在它们之间交换数据，并且其实现复杂性是未知的。相反，CORE 在 relayer 中执行所有操作并且更容易实现。7.在本节中，一些本文未涉及的开放性问题。高冗余的CORE在本文中，由于最佳再生码的基础结构要求，采用

56、具有相当高的冗余（即双冗余）的MSR代码。 在44中显示，具有精确恢复的所有（n，k）线性MSR码必须满足条件n 2k 2。其他（n，k）可以通过用于归档数据23的非系统的再生码结构11来构造。如何扩展CORE的功能再生代码仍然是一个开放。非MDS码的并发恢复。考虑实现了最小的效率，如MDS编码（见第2.1节）的MSR编码并发恢复问题，。可以考虑非MDS代码，虽然有较高的开销，但是实现更好的单一故障恢复性能（例如MBR代码38和本地恢复代码13，26，34，42）。 一个开放是如何扩展这些非MDS代码以支持高效的并发恢复。广域系统。目前在HDFS上实现CORE。计划探索在广域系统（例如，2，7

57、，8，31）中的CORE的实现，其中网络带宽有限并且再生码的优势应该变得更突出。 此外，CORE的一个好处是可以延迟恢复，直到失败的节点数量达到某个阈值，以避免恢复在广域网中常见的瞬态故障2，6，33 。8.结论在存在单个和并发故障的情况下，从理论和应用的角度来解决分布式系统中的恢复问题。探索使用再生码（或网络编码）来提供容错，并在恢复期间最小化数据传输的带宽。提出了一种系统 CORE，其概括了现有的基于单故障的再生码，以支持单个故障和并发故障的恢复。理论上表明，CORE 最大限度地减少了大多数并发故障模式中的恢复带宽。进一步将 CORE 原型作为 Hadoop HDFS 顶层的一个原型，并通

58、过测试实验显示，其可以加快恢复和降级操作。的 CORE 原型的源代码可以从。致谢AoE / E-02/08 和 ECS CUHK419212 的支持。这项工作得到大学教育资助参考文献1 R. Ahlswede, N. Cai, S. Li, and R. Yeung. Network Information low. IEEE Trans. onInformation Theory, 46(4):12041216, Jul 2000.2 R. Bhagwan, K.i, Y. Cheng, S. Savage, and G. Voelker. Total ecall: System Suppo

59、rt forAutomated Availability Management. n Proc. of USENIX NSDI, Oct 2004.3 J. Bloemer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, and . Zuckerman. An XOR-basedErasure-Resint Coding Scheme. echnical report, Theernational Computer Science Institute,erkeley, CA, Aug 1995.4 V. R. Cadambe, C. Huang, an

60、d J. Li. Permuion Code: Optimal xact-Repair of a SingleFailed NodeDS Code Based istributed Storage Systems. In Proc. of IEEE ISIT, 2011.5 B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie, Y. Xu, S. Srivastav,J. Wu, H. Simitci, et al. Windows Azure Storage: A Highly Available Cl