英语原文共 5 页
用于分层数据中心的双重再生码
胡玉冲、Patrick P.C.Lee、张晓阳
摘要：数据中心越来越多地采用纠删编码来确保低冗余的容错存储, 但数据中心的层次结构性质会导致故障修复过程中出现大量的跨机架带宽过载。我们目前的双再生代码 (DRC), 其想法是执行两阶段再生, 以最小的存储冗余最小化单节点的跨机架修复带宽。我们证明了DRC结构的存在，并通过定量比较表明，DRC显著降低了最小存储再生代码的跨机架修复带宽。
Ⅰ介绍
企业部署数据中心用于大规模存储，但一个关键的部署挑战是容忍数据丢失。纠删编码支持高容错存储的特性，具有比传统复制少得多的冗余。随着数据的不断增长，纠删编码广泛地应用于数据中心存储(如[6]、[8]、[11]、[16])。例如，Facebook从3times;三倍复制更新到1.4times;纠删编码[11][16]以减少冗余，因此节省了PB级的存储空间。
纠删码通常由两个可配置参数n和k（其中k lt;n）构成。给定大小为M的原始数据，（n，k）纠删码将原始数据分成大小为M / k的k个片段，并将它们转换为相同大小的n个编码片段。每个编码的片段存储在不同的节点（或服务器）中。本文重点介绍满足最大距离可分（MDS）属性的纠删码构造，这意味着n个编码片段中的任何k个都可以重建原始数据，而且存储冗余最小。
纠删编码可以提高存储效率。特别是，任何丢失的片段的修复都涉及其它片段的转移。修复丢失片段的传统方法是从其他非故障节点检索k个片段，以便重建原始数据和重建丢失的片段。为了减少修复带宽（即，用于修复的传输流量），通过允许非故障节点在修复期间编码和发送其存储的纠删码片段，再生代码实现了两者之间修复带宽和存储效率的最优权衡。最小存储再生(MSR)码[4]是再生码的一种构造，它在保留MDS特性的同时，最小化了重建单个丢失片段的修复带宽。
但是，由于数据中心的分层性质，在数据中心部署纠删编码仍然具有挑战性。数据中心通常组织在多个机架中，每个机架包括多个用于存储的节点。每个机架内的节点通过架顶式交换机互连，多个机架的架顶式交换机通过交换机的网络核心进一步互连。为了容忍节点和机架故障，一种典型的方法是将片段放置在不同的节点中，每个节点都位于不同的机架中[6]，[8]，[11]，[13]，[14]，[16] ]。这样放置会导致任何丢失片段的修复都会不可避免地从机架上的其他非故障节点上传输片段。这就导致了大量的跨机架修复带宽，这大量地被超额认购，例如5到20倍[1]，[3]，[19]（即，在最坏的情况下每个节点可用的跨机架容量只有内架容量的1/5到1/20）。因此，我们的目标是在分层数据中心中最小化跨机架修复带宽（即，在修复期间传输的跨机架数据量）。在这里，我们专注于修复单节点故障，这是实践中最常见的故障情况[8]，[13]，[14]。
我们认为我们可以为每个机架放置多个片段（同时我们仍然为每个节点保留一个片段）而不是每个机架放置一个片段，并利用内部机架再生来减少跨机架修复带宽。图1提供了一个激励示例，其中n = 6且k = 3.假设节点1失败。图1（a）显示了常见的修复，其中跨机架修复带宽就是原始数据的大小M.图1（b）显示了使用MSR代码进行修复，其中跨机架修复带宽为5M / 9，基于[4]中的最优性结果。图1（c）显示了我们的新修复方案，它将跨机架修复带宽降低到M / 3，或者相当于比MSR代码低40％。图1（c）中的核心思想是执行两次再生：首先在机架内，然后跨多个机架。我们将这种方法称为双重再生，其修复设计专门针对分层数据中心内部机架和跨机架容量不平衡的性质。
双重再生需要两次权衡。首先，图1（c）中的代码只能容忍单机架故障（与图1（a）和1（b）中的三机架故障相反）。然而，在实践中，机架故障比节点故障少得多[6]。因此，我们可以容忍相同的多节点故障，但只能承受单机架故障，而不是容忍多个节点和机架故障。其次，图1（c）中的内机架和跨机架修复带宽之和为M，高于MSR代码（即5M / 9）。然而，由于超额订购，内部机架容量比跨机架容量更丰富。因此，我们可以交换内部机架修复带宽以用于跨机架修复。
图1. n = 6且k = 3的示例：（a）常规修复重建原始数据并产生跨机架修复带宽M;（b）MSR代码产生5M / 9的跨机架修复带宽[4];（c）双重再生执行内部机架编码并产生跨机架修复带宽M / 3。
本文针对于分层数据中心提出了双重再生代码（DRC）。我们的贡献是双重的。首先，我们证明存在一种DRC结构，可以最小化单节点修复的跨机架修复带宽，同时保留MDS属性（即DRC保持最小的存储冗余）。其次，我们通过定量比较表明，DRC比最先进的MSR代码的跨机架修复带宽降低了45.5％。
II. 双重再生
我们提出了一种正式的双重再生系统模型。我们通过信息流图分析系统模型，并在双重再生下得出跨机架修复带宽的下限。
系统模型
我们使用（n，k）MDS纠删码将大小为M的原始数据编码为大小为M / k的n个片段。然后我们将编码的片段分布在n个节点（每个节点一个编码片段）并且均匀的位于r中，每个机架都有n/r个节点。我们提出了三个条件参数：(i)n是r的倍数（n/r是整数）；（ⅱ）我们要求n/rle;k，这样任何的单节点故障都不可能在机架内本地修复，必须要有跨机架修复带宽；（iii）我们要求n/rle;n-k，所以在单机架故障中不会有数据丢失。注意我们可以通过添加更多的冗余来增加可容忍故障的机架数量（即增加n-k）。让机架Rh成为hth机架（其中1le;hle;r)，节点Xh,i是机架Rh中的ith节点（其中1le;ile;n/r)。
双再生码中的单节点修复工作如下。在不失一般性的情况下，我们分析假设节点X1,1在整篇论文中都失败了。我们在机架R1中选择一个新的节点X1,1以恢复X1,1中的丢失片段。该修复分为两个阶段。在第一阶段，在机架Rh（当2le;hle;r时）中，我们选择一个特殊节点Xh,1(不失去一般性），它从同一机架的每个幸存节点（包括自身)收集编码数据（即Xh,1，Xh,2....Xh,n/r)，我们称这个特殊节点叫做中继器，它重新编码收集数据并把这些数据发送到机架上的X1,1.在第二个修复阶段，X1,1首先从机架R1中的其他幸存节点X1,2，X1,3，··，X1,n/r收集编码数据。然后，它使用来自同一机架内的所有收集数据以及来自其他机架中中继器的数据来重建丢失的片段。
我们的分析假设任何一对机架之间的带宽是均匀的，并用beta;表示。因此，单节点修复的跨机架修复带宽是（r-1）beta;。我们的目标是在保持MDS特性的同时最小化beta;。
B.信息流图
我们构造了一个信息流图G（n，k，r，beta;）来描述单节点修复的数据中心网络。图2描绘了当 n = 6，k = 3，并且r = 3时的G。G有三种类型的节点：（i）虚拟源S；(ii)数据收集器T，对应于源和信息流的目的节点；（iii）输入/输出节点对应于（Xinh,i Xouth,i)存储节点Xh,1。类似的，输入/输出节点对（Xinh,i Xouth,i)表示新节点X1,1。
G有六种类型的定向边：（ⅰ）从S到每个Xinh,i；（ⅱ）从Xinh,i到Xouth,i，从Xin1,1到Xout1,1，容量为M/k（即存储数据量）；（ⅲ）从Xinh,i的边缘到Xouth,i（hne;1，ine;1），容量为M/k（即Rh中两个节点之间的机架修复带宽的最大值）；（ⅳ）从Xout1,i的一边到Xin1,i，容量为M/k（即R1中两个节点之间的机架修复带宽的最大值）；（ⅴ）从Xouth,1的一边到Xin1,1，容量为beta;（即最大跨架修复带宽）；（ⅵ）从k个选定输出节点中的每一个到T的边缘，具有无限容量用于数据重建。
C.下界
我们通过考虑G的所有种可能的最小割的容量来导出beta;的下界。我们将切割定义为有向边的集合，使得从S到T的任何路径在切割中必须至少具有一个边缘。最小割是所有边缘的最小容量总和的切割。需要注意的是由于MDS属性会有（个可能的数据收集器）。因此，存在着种G的变形以及个可能的最小割。
引理 1：如果所有可能的种G切割分割成的S和T不小于M，当随机线性网络n个节点中的任何k个连接到T时，代码足以重建原始数据，其概率通过增加字段大小而接近于1.基于引理1，我们提出下一个引理，G中beta;下限存在的必要条件是存在有效的代码。
引理 2：如果G中所有可能的最小割的容量小于M，则
证明：要指定与每个数据收集器对应的最小割，假设以下k个节点连接到T，以便可以重建原始数据：（i）新节点X1,1;（ii）机架R1 的x个节点（故障节点X1,1除外）;(iii) y中继器;（iv）其内机架中继器不是连接到T的w1 节点;（v）其内机架中继器的节点连接到T的w2节点 .根据定义：
1 x y w1 w2 = k （1）
图2给出x = 1，y = 0，w1 = 1，w2 = 0.设Lambda;（x，y，w1，w2）表示切割的容量，它是x，y，w1和w2的函数。
我们推导Lambda;如下。我们不考虑具有从S或T指向边缘的切割，因为该边缘具有无限容量。我们观察到（例如，参见图2）:（i）R1 的所有幸存节点（例如，X1,2）可以贡献（n / r -1）·M / k到Lambda;;（ii）所有内机架中继器的节点连接到T（例如，X2,1 和X2,2）可以贡献y·n / rM / k到Lambda;;（iii）所有（r-1-y）未连接的中继器到T（例如，X3,1）可以贡献（r - 1 - y）beta;到Lambda;1;（iv）w1 节点，其机架中继器未连接到T.可以贡献w1 ·M / k到Lambda;;（v）w2节点，其机架中继器连接到的w2 节点不能对Lambda;做任何贡献，因为它的所有信息都是由它们贡献的。因此，削减的能力是：
Lambda; = (n/r minus; 1) · M/k y · n/r · M/k
(r minus; 1 minus; y)beta; w1 · M/k. （2）
由于所有的最小割至少为M，因此等式2意味着对G的所有变体
（3）
X3,1可以对Lambda;贡献2M / k，但beta;明显不大于2M / k,因为前者具有来自后者的编码信息。
令为等式（3）的右侧，然后对于所有G的变体，等式3可以简化为：
beta; ge;max{} (4)
我们现在导出max {}。机架R1 中最多n / r-1个节点（节点X1,1故障）可以连接到T.从而:
x le; n/r minus; 1. （5）
此外，对于每个中继器连接到T的机架而言，最多n / r - 1个节点也可以连接到T.从而，
w2 le; (n/r minus; 1)y. (6)
通过等式（1），我们观察到x和W2的较大值将为y和W1设置较小的范围值。通过等式（3），我们观察到alpha;-y和alpha;-w1。从而，当x和w2 达到最大值时，最大化（即，x=n/r-1和w2=n/r-1）y）。在这种情况下，等式（1）可以简化为：
w1=kminus;n/rminus;y·n/r. (7)
由于w1 ge;0，因此等式（7）意味着：
yle;[kr/n] - 1，yisin;Z。 （8）
因此，如果等式（7）和（8）成立，则可以导出max {}。如下式：
Max{}=(m/k).[1/(r-kr/n)] (9)
通过等式（4）
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
