英语原文共 8 页
异构分布式存储系统的非对称再生码
Shan Qu， Jinbei Zhang，王新兵
上海交通大学电子工程系，中国
西安电子科技大学综合业务网理论及关键技术国家重点实验室
电子邮件：{qushan, abelchina, xwang8}@sjtu.edu.cn
摘要：抽象分布式存储系统通过在多个存储节点上分布数据来提供可靠性。一旦有一个节点发生故障，就会向系统引入一个新节点，以维持存储数据的可用性。新节点从称为帮助节点的其他幸存节点下载信息，以恢复故障节点中丢失的数据。帮助节点的数量被称为修复度。与传统方法(例如，复制和纠删码)相比，现有的再生码可以显著降低同构分布式存储系统的修复带宽。目前的大多数工作集中于设置相同的节点参数(例如，在修复度和修复带宽方面)。
但是，由于网络结构或是网络连接的限制，每一个不同的故障节点，所需的帮助节点的数量可能不同。另外，考虑到网络流量的带宽限制，从每一个帮助节点能够下载的信息量也有所差异。因此，我们需要对异构分布式存储系统进行研究，在这一系统中，修复度和从每个帮助节点下载的信息量可以是不同的。为了得到修复故障节点所需的最小带宽，我们构建了这种异构分布式存储系统的信息流图。通过分析信息流图的割集界限，得出了存储容量和修复带宽之间的最佳权衡。然后，我们提出了可以实现最佳权衡曲线的非对称再生码；并给出了该非对称再生码的线性结构。与之前的再生码相比，这种非对称再生码在一定的约束条件下能够具有更低的修复带宽，其减少量可高达36.2％。
一 导言
分布式存储系统以分布数据的方式来确保对大量节点上的冗余存储数据的可靠访问。其应用场景包括许多商业系统，如Amazon[1]，SkyDrive [2]，Facebook [3]和Microsoft Azure Systems [4]。（保留英文还是翻译成中文呢）一旦有一个节点发生故障，一个名为新生节点(newcomer)的新节点将会加入系统，并从其他的幸存节点(称为帮助节点)下载数据，以恢复故障节点中丢失的数据，达到系统的标准可靠性水平。
关于提高同构分布式存储系统(其中存储节点的设置是相同的)的可靠性提出了提出了各种策略。其中最为简单的策略是复制，而更有效的策略是使用纠删码，使用纠删码可以减少存储容量并增强容错能力。纠删码得到了广泛的应用[5] [6]。在纠删码中，大小为B的文件被分成大小均为B / k的k个片段。然后将这些片段编码成n个片段，大小均为B / k。每一个编码片段存储在不同的节点中，并使得利用任何k个节点都可以恢复出原始文件。这种性质称为“最大距离可分”(MDS)。在单个节点发生故障时，对于(n，k)纠删码，修复故障节点的常规方法是下载k个片段以恢复原始文件，然后可以直接从原始文件中恢复故障片段。因此，纠删码的修复带宽为B，是发生故障的片段大小的k倍。为了减少修复带宽，在[7]中引入了再生码，其中对于每一个故障节点，新生节点连接到d(dge;k)个帮助节点并从每个帮助节点下载beta;比特数据。帮助节点的数量d称为修复度。在[7]中实现了存储容量和修复带宽之间的基本权衡。在[8] - [10]中对再生码的显式结构进行了介绍。
在现实生活中的系统中，应该考虑系统的异构性[11] - [14]。在[11]中，不同的节点可能具有不同的下载开销，并且导出了成本和带宽之间的权衡。[12]着重于在重构条件不同并且从每个帮助节点下载的信息量也不同的情况下灵活再生码的最小带宽。[14]给出了具有动态存储、动态带宽以及不同修复度(即用于恢复原始文件的节点数)的通用模型的一些数值结果。由于网络结构的不同和实际系统中网络流量的限制，节点修复过程中的修复度和从每个帮助节点下载的信息量是很重要的，然而现有的工作中并没有考虑到这些。
图1 （6,2）最小存储非对称再生码的单节点修复过程。将大小为B = 2Mb的文件分成四个片段，每个片段的大小为0.5Mb，由向量x =（，，，）表示。这四个片段在有限域上被编码成具有相同大小0.5Mb的十二个片段，并存储在六个节点中。可以从两个节点的一些集合（例如节点1和5，2和4，3和6等）恢复原始文件。
在本文中，我们关注的是异构系统，其中存储节点可以具有不同的修复度和修复带宽。由于修复度不同，所有的存储节点被分为多种类型，并且不同类型的节点可以从帮助节点下载的数据量也不同。因此，不同类型的节点在修复过程中应该满足不同的修复条件。图1提供了当n = 6且k = 2时的激励性示例。假设所有节点都放在一条直线上，并且每个节点仅允许从相邻的节点下载信息。同时，由于流量限制，中间的所有节点仅被允许互相传送一个编码片段。这样一来，所有的节点就可以分为两种类型：只有一个相邻节点的位于两端的节点(n = 1,6)和有两个相邻节点的节点(节点2-5)。假设节点3发生了故障，可以通过从节点2和节点4分别下载一个编码片段来修复它。类似地，节点2,4,5也可以从两个相邻节点各下载一个下载编码片段来修复。节点1,6都需要从一个相邻节点下载两个编码片段以完成修复过程。如果考虑同构系统(其中所有节点完全连接并且带宽足够)，则可以不受网络结构和网络流量的限制，通过从任意两个其他节点各下载一个编码片段来修复任意一个存储节点。在这个例子中，同构系统和异构系统中的单节点修复带宽均等于存储容量1Mb。因此，修复带宽在理论上达到最小值(修复带宽的最小值等于单个节点的存储容量[7])。但是，对于一个一般的异构系统，先前同构系统中存储容量和修复带宽之间的权衡[7]不再适用。因此，一个重要的问题是，恢复故障节点需要多少带宽？
为了分析恢复故障节点的最小带宽，我们构建了这种异构系统的信息流图。基于该信息流图，导出了存储容量和修复带宽之间的最佳权衡。此外，为了达到权衡，我们提出了非对称再生码。当系统中只有一种节点时，我们的非对称再生码将会退化为[7]中的再生码。
总而言之，我们的主要贡献如下。
bull; 我们研究了异构分布式存储系统的信息流图的最小割，并在存储容量和修复带宽之间进行了权衡。
bull; 我们提出了非对称再生码，这是一种新的经过改进的异构系统再生码，可以实现曲线的权衡。并给出了非对称再生码的线性结构。
bull; 说明了一个研究案例，该研究表明，在某些范围内，非对称再生码的修复带宽低于之前的再生码[7]，并且修复带宽可降低多达36.2％。
本文的其余部分安排如下：在第二节中，我们简要介绍了再生码和灵活再生码。在第三节中，我们描述了系统模型，并得出了存储和修复带宽之间的最佳权衡。在第四节中，我们给出了非对称再生码的线性结构。在第五节中，我们定量和定性地对非对称再生码和其他的储存策略进行了比较。最后，在第六节中，我们得出结论。
二 相关工作
在本节中，我们将简要介绍分布式系统的两种现有存储策略。我们首先展示了同构系统的再生码，其中每个节点都具有完全相同的参数。然后为一类异构系统引入灵活再生码。
A.再生码
对于同构系统，在[7]中引入了再生码。假设系统中有n个活跃的存储节点，每个节点具有相同的存储容量alpha;。在某一节点发生故障时，向系统内引入新生节点并从d个帮助节点下载大小同为beta;的数据以完成修复过程。总修复带宽由gamma;表示，其中gamma;=dbeta;。通过分析信息流图的切割界限，得到了存储容量alpha;与修复带宽gamma;之间的最佳权衡。此外，对应于最小存储(MSR代码)和最小带宽(MBR代码)的权衡曲线上的两个极值点如下所示：
（1）
和
（2）
它要求dge;k，其中k是恢复出原始文件所需的最小节点数。请注意，在我们的模型中，每个存储节点的修复度可能是不同的，并且不一定大于k。
B.灵活再生码
[12]为一类具有灵活重建和灵活再生的异构系统引入了灵活再生码。灵活重建意味着原始文件可以从每个存储节点下载不同量的信息来恢复。灵活再生意味着新生节点从每个帮助节点下载的信息量可以是不同的。通过分析信息流图的割集界限，可以得出修复带宽的下限。
虽然从每个帮助节点下载的信息量可能不同，但帮助节点的数量是固定的，这也就限制了灵活再生码的应用。在我们的模型中，存储节点被分为多个集合，，...，，并且通过从个帮助节点下载比特数据来修复集合(mu;= 1，2，...，m)中的节点。对于不同集合中的节点，帮助节点的数量可以不同。从这个意义上讲，我们尝试为存储节点具有各种不同修复条件的再生码提供新的见解。
三 系统模型
在本节中，我们将在异构分布式存储系统中制定再生过程。然后，我们通过分析信息流图的割集界限，得出存储和修复带宽之间的最佳权衡，并在权衡曲线上表示两个极值点。
A.非对称再生码
大小为B的文件存储在n个存储节点中。每个存储节点具有alpha;比特的高速缓存。在异构分布式存储系统中，每个故障节点所需的帮助节点数量是不同的。n个节点可以分为m个集合，，...，，这样集合(mu;= 1，2，...，m)中的任意节点都可以通过连接到任意个帮助节点来修复。设|| 表示集合中的节点数。此外，由于网络流量的限制，不同集合中的节点可以从每个帮助节点下载不同量的数据。
图2 非对称再生过程：大小为B的文件以异构分布式存储系统中的分散片段的形式存储在许多节点中。假设集合（mu;= 1，2，...，m）中的节点发生故障，则新生节点连接到个帮助节点并从其中每一个节点下载比特数据以完成修复过程。
单节点故障的修复过程描述如下。一旦集合中的节点发生故障，就会向系统引入一个新生节点，并从个帮助节点各自下载比特数据。这一特性称为非对称再生(见图2)。假设每个存储节点的总修复带宽相等并用gamma;表示，即=gamma;(mu;= 1,2，...，m)。那么，非对称再生就可以由参数集(n，k，，||，alpha;，gamma;)表示。为了便于描述，我们假设有 lt; lt;··· lt;le; n-1并且有|| ··· || lt;kle;|| ··· || | 1 |。
此外，n个节点中的任意k个节点构成的集都可以恢复出原始文件，这种性质称为数据重建。请注意，如果新生节点与故障节点中存储的数据完全相同，则称此修复模式为完全非对称再生。如果存储在新生节点中的数据与存储在故障节点中的数据不同，则称此修复模式为功能非对称再生，但是这样修复的网络仍然满足非对称再生和数据重建的特性。我们一般考虑单节点故障[15]，这是实际分布式存储系统中最为常见的故障情况。
我们的目标是在功能非对称再生修复模式下将修复带宽gamma;最小化。为了进一步探究，构造信息流图[7]以在接下来的小节中得出存储容量和修复带宽之间的最佳权衡。
B.信息流图
信息流图G具有三种节点：单个源节点S，数据收集器节点DC和存储节点对和。单源节点S代表了原始文件。存储节点对和称为节点i的输入节点和输出节点。这两个节点通过有向边连接，使用容量alpha;表示存储节点的大小。DC表示数据收集器节点，它可以通过连接到k个输出节点来恢复原始文件。
根据最大流最小割定理[16]，信息流图中的最小割相当于最大网络流量。分离了源节点S和数据收集器节点DC的切割是边缘子集C，其满足从S到DC的所有路径在C中都具有一个或多个边缘。最小割就是边缘容量的总和最小的切割。因此，如果S和DC的最小割小于原始文件大小B，那么就没有DC可以重建原始文件。
图3 对应于图1中用于单节点修复的（6,2）最小存储非对称再生码的信息流图
图3给出了对应于图1中用于单节点修复的(6,2)MSAR代码的信息流图的示例。在图3中有两种类型的存储节点，以两种颜色表示。每个节点存储两个编码片段，每个片段大小都为0.5Mb。如果节点发生故障，则新节点将加入系统来替换它。考虑到线性拓扑的限制，节点只能连接到节点和，并从两个节点各下载比特数据。我们的目标就是得出所需的的下限。请注意，在我们的系统模型中，帮助节点是不确定的，这是最坏的情况分析。在这个例子中，最小割值是1 2，这意味着必要条件是1 2ge;2。那么，的最小值就是0.5Mb。
C.存储-带宽权衡
通过在非对称再生下的所有可能的信息流图中分析最小割的下限，切割界限如下所示：
引理1：在异构分布式存储系统中，当且仅当满足以下切割界限时，才能实现(n，k，，||，gamma;)的非对称再生：
， (3)
其中
=max{0,min{(-j),alpha;}} p=1,2,...,i 1。
引理1的证明在附录A中给出。然后，从引理1得到的最佳权衡如下所示。
定理1：对于任何alpha;ge;(n，k，，||，gamma;)，参数集的非对称再生(n，k，，||，gamma;)是可以实现的，并且可以通过线性网络代码实现。如果alpha;lt;(n，k，，||，gamma;)，则(n，k，，||，gamma;)参数集的非对称再生在信息理论上是无法达到的。当条件|| = 0时，gt; k，ge;|| ··· ||和(|| ··· ||-1)le;(|| ··· ||)，对于p = 1，2，...,i同时满足，阈值函数(n，k，，||，gamma;)是
，
gamma;的最小值是
，
符号，，，H(p,q)和的表达在附录B中有所列出。
从定理1可以看出，实现该最佳权衡曲线上的每个点的代码是存在的，被称为非对称再生码。定理1的证明在附录B中给出。虽然条件和表达看起来很复杂，但最为有趣的案例是两个比较容易理解的极值点，如下所示。
D.两个特例：MSAR码和MBAR码
在非对称再生下的权衡曲线上有两个极值点，分别对应于最小存储容量和最小修复带宽。实现这些点的代码分别称为最小存储非对称再生(MSAR)码和最小带宽非对称再生(MBAR)码。
对于MSAR码，其存储容量和修复带宽如下所示：
，
和
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
