再生码(Regenerating-Codes)开山之作

应用于分布式存储的网络编码AlexandrosG.Dimakis，P.BrightenGodfrey,MartinJ.WainwrightandKannanRamchandran翻译：dullgull摘要摘要—P2P分布式存储系统通过冗余方法将数据分布到Internet上各个节点上保证可靠性。其中的一个关键就是减少保证这种冗余的维持带宽。使用纠错码将文件分为多个分片保存在不同节点上，较副本策略保证同样的可靠性下需要更少的冗余数据和更小的维持带宽。然而，既然分片必须周期性地在节点失效后重建，一个关键问题就是如何以分布式的方式生成一个新的分片，同时保证通过网络传输的数据尽可能的少。在这篇文章中，我们引入一个一般性的技术来分析融合任何形式编码和副本的存储架构，同时提出两个使用纠错码维持冗余的新方案。首先，我们将展示如何从现有的系统中以最优的方式生成MDS分片。其次，我们引入一个新的称为再生码的方案，它仅比MDS具有稍大一些的分片，却比MDS具有更低的整体带宽使用。我们通过在真实环境中的仿真发现，再生码和之前最优设计—副本和纠删码混合策略，能够减少25%甚至更多的维持带宽，同时也简化了系统设计。1引言Oceanstore，TotalRecall和DHash++这类分布式存储系统目的就是使用一群分布式的磁盘（即是Internet上不同节点）集合上长期、可靠地保存数据。保证可靠性需要引入冗余，最简单的方法就是直接使用副本。有一些设计则是使用了纠错码。最大距离可分码（MDS）将Mbytes大小文件分为n个分片保存，每个分片M/kbytes大小，其中任意k个分片可以重建出原始文件。然而，一个问题随之而来：在分布式存储系统中，当节点失效或者磁盘故障，冗余必须不断地被刷新，这样就会导致大量数据在网络上传输。我们如何高效地重建新的分片来应对这种失效呢？一个新的分片副本应该直接从其他保存该分片的节点复制过来，但是传统的纠错码需要通过原始数据来产生一个新的编码分片。我们如何只访问纠错码分片来生成一个纠错码分片？在初始策略中，保存新的分片的节点—我们将称其为新手—下载k个分片并重建文件，并从原始文件中生成新的编码分片。因此，传输了Mbytes的数据却只产生了M/k大小的分片。为了减少带宽的使用，人们必须使用称为混合策略的方法：既维持着一个副本，还存在着多个纠错编码的数据分片。保存着副本的节点可以产生新的分片并发送给新手，因此为每个新的分片只需传输M/kbytes的数据。然而，节点上维持一个额外的副本削弱了纠错编码带来的带宽效率，使得系统设计变得复杂。比如，如果副本丢失了，将无法生成新的分片，直到新的副本被还原。实际上，有研究在分布式存储系统中比较了混合策略和副本策略，指出混合策略减少的带宽是有限的，甚至不及它的缺点，部分原因是因为维持两种类型冗余带来了复杂性。很自然地会提出下面的问题：有没有可能使用比初始策略更少的带宽来维持纠错编码，也不用采用像混合方式的不对称策略？更进一步，为了维持一个纠错码需要下载的最小量数据是多少？在文中我将展示网络编码如何在这种分布式存储场景一展身手。引入普通的图论框架，通过它我们获得更少的带宽限制以维持任何分布式存储架构，大家将看到随机线性网络编码是如何达到这些最低限。更具体地说，我们确定了一个新手需要产生一个MDS或者近似-MDS分片所必须的最小数据量，这种方案称为最优维持MDS（OMMDS）。我们特别地证明了如果新手只能连接k个节点下载数据生成分片，那么M-byte的下载量是信息论的最小值。出人意料的是，如果新手允许连接超过k个节点，那么需要下载的数据总量会显著地减少。比如k=7，n=14，新手可连接n1个节点，那么只需要传输0:27Mbytes数据来生成新的分片，比初始策略减少73%。然而，相关的额外开销也是必须的，结果是混合策略比OMMDS提供了更好的可靠性带宽开销。为了改进混合策略，我们必须看的比MDS更远。站在这个观点上，我们引入一个新方案，再生码（RegeneratingCodes），它在我们坚持MDS的“对称性”下最小化一个新手需要下载的数据量。在更高的层次上，RC方案通过新手保存所有下载得到的数据来改进OMMDS，而不是将这些数据扔掉。结果就是RC码会有比MDS更大的分片，但却只需要很少的维持带宽开销，即使新手之和k个节点交互。比如k=7，一个新手只需要下载0:16Mbytes数据—比OMMDS减少了39%，比初始策略减少了84%。更进一步，我们的在基于真实分布式系统测量得到的节点可靠性模拟实验中指出，在k=7时，RC较混合策略减少了25%的带宽。随着k增大RC性能更好。我们强调在RC较其他策略也有额外开销。比如用户重建数据需要付出一个小小的开销，因为RC分片更大。然而，再生码提供了一个简单、低带宽可供选择的方案。总结下，全文的贡献有以下几点：•我们引入一个框架用来分析分布式存储系统冗余方案的带宽需求。•我们给出了直接从其他节点生成一个新的MDS分片所需要的最小带宽。•我们引入了一个非-MDS方案，再生码，并通过仿真证实了其比之前的基于纠错码的方案（混合型）具有更低的维持带宽，并保持了MDS码的对称性。本文如下组织。在第二节中，我们讨论了编码理论和分布式存储的相关背景知识。在第三节我们引入我们的分析技术，并在第二小节确定如何最优地维持MDS码。我们在第四节介绍在再生码。最后在第五节中比较了混合策略，OMMDS与再生码，通过计量节点可靠性的traces并定量讨论不同策略的额外开销。22相关工作和背景2.1纠错码纠错编码是副本的推广，它将原始数据对象分为k个分片（或者块），接着k个分片编码生成n个编码分片。MDS（最大距离可分）纠错码具有特性：n个分片中任意k个可以恢复出原始的k个数据分片。好的（比如MDS或者近似MDS）纠错码相对于副本方案具有更高恢复的可能性，同时也带来了更大的计算复杂度。一个从理论上量化这种好处的方法是优惠劵收集问题：必须随机选择klnk个分片以收集k个原始数据，从这层意思来看，纠错编码节省的系数为lnk。减少纠错码的编码和解码复杂度已经被广泛地研究，最近优化的纠错码已经具有线性编码和解码复杂度。喷泉码（也称为无码率码）允许独立地创建每个编码分片，因此可用于分布式存储系统，因为这样的系统节点不断地加入和离开。2.2网络编码Ahlswede等人介绍了网络编码的基本想法—整合数据包而不只是路由、转发—并说明了它达到了多播最小割的最小值。后来发现了在有限域的线性操作足够达到网络编码容量。将网络编码应用于存储首先是在传感器网络中开始的。接着再P2P内容分发系统中也开始提出对包随机线性操作以改善下载。随机网络编码最近也被用在P2P网络诊断。我们的论文基于相同的想法，但存储系统需要分析不同的性能指标。2.3分布式存储系统最近的研究[4]，[18]，[7]，[21]，[2]，[27]设计和评估了大规模，P2P分布式存储系统。这些系统中冗余管理策略已经在[28]，[3]，[2]，[20]，[27]，[5]，[25]，[11]进行了评估。其中，[28]，[2]，[20]比较了副本和纠错码在带宽可靠性和空间之间的权衡。Weatherspoon和Kubiatowicz[28]的研究发现纠错码较副本能够减少一个数量级的带宽使用。Bhagwan等人[2]在模拟TotalRecall也得到了类似的结论。Rodrigues和Liskov[20]得到了不同的结论：在高扰动（high-churn，节点失效率高）环境中，纠错码具有更大的优势，但是带宽代价太高以至于根本不适合P2P分布式存储系统。在低扰动环境中，带宽的减少是微不足道的。在中毒扰动环境中，有一些好处，但是这点优势可能也被纠错码带来的系统复杂度所动摇。这些结论都是基于一个分析模型，通过放大真实系统的traces中评估的系数得到的。相对于[28]，[20]使用了更小的k值（7而不是32）和混合策略来指出码的重建问题。在第五节中，我们将重复[20]中的评估来测量我们介绍的两种冗余维持方案的性能。3图1:信息流图G的一个插图。假设这是一个（4,3）纠错码，其中任意3个分片足够恢复出原始数据。如果节点x4失效了，一个新的节点（译注：x5）加入到系统。接着我们需要在节点x5上重建出新的编码分片。为此，节点xin5和k=3个活跃存储节点连接。假定它从每个活跃节点下载了bits数据，我们感兴趣的是需要的最小值。将源数据和数据收集器分离开的最小割必须大于3才可能恢复出原始数据（应用最小割—最大流定理，只有最小割大于等于3，最大流才能大于3）。对于这幅图，最小割值为2+，也就是1，所以新手必须从每个节点下载整个数据对象，前提就是他只能和k=3个存储节点交互。3带宽的基本限制3.1信息流图我们的分析是基于一个分布式存储系统独特的图形表述，我们指的就是信息流图G。该图描述了数据对象的信息如何随着时间从存储节点到达重建节点和数据收集器。更准确地说，这是一个有向不循环的图，包含了三类节点：一个数据源S，存储节点xini，xouti和数据收集器DCi单个源节点S对应的是原始数据。在系统中的存储节点i由一个输入存储节点xini和一个输出节点xouti来表示。两个节点由一个有向边xini!xouti连接，边权重等于在节点i上存储的数据量。如图1所示。考虑存储方案的动态特性，信息流图也随着时间变化。在任意时间，图上的每个顶点要么是活跃的，要么是非活跃的，取决于该节点在网络中是否可用。在初始阶段，只有源节点是可用的。它紧接着和一系列初始存储节点交互，连接他们的输入节点（xin），这条边的权重为无限大。从这点开始，原始节点S变成并保持不活跃状态。在下一时间点，开始选中的存储节点变为活跃状态；他们代表一个分布式纠错码，对应着我们希望的系统稳定状态。如果一个新的节点（译注：新手）j加入到系统，它只能和系统中活跃的节点进行交互。如果一个新手j选择和活跃的存储节点i进行连接，那么我们就添加一条有向边从xouti到xinj，边权重等于新手从节点i下载的数据量。注意到一般新手下载的数据量是要多于他们所存储的，比如在（14,7）-纠错码中。如果一个节点离开了系统，就变为不活跃状态。最后，一个数据收集器DC对应的是发起请求重建数据的节点。数据收集器连接所有活跃节点的一个子集，边权重为无限大。一个信息流图相关的重要概念就是最小割：定义1.图G中源S和一个固定的数据收集器节点DC之间的一个割是边的一个子集C，使得：4从源点S出发到DC没有不经过集合C的。最小割是S和DC之间使得集合C总权重最小的割。3.2限制为了获取每个存储节点需要下载的限制，我们从下面的引理开始：引理3.1.如果图G中S和DC之间最小割小于初始对象大小，一个数据收集器DC永远也不能重建出初始数据对象。证明.初始数据对象的信息是从源流向指定的数据收集器。信息流图中每个连接最多只能使用一次（译注：不存在回路），点对点权重小于文件的大小，那么传输初始数据对象就不可能了。接下来的声明，基于网络编码已有的结论，展示了现有的线性网络编码存在对所有数据收集器同时满足这个限制，并且数据包使用有限域内（随机网络编码[13]）随机独立系数的简单线性混合（译注：异或加）将以很高的概率满足。命题1.假设对于一些分布式存储方案，我们创建图G并放置所有(nk)个可能的数据收集器，其中n是活跃节点的数目。如果分离源S和每个数据收集器的最小割都大于后者等于数据对象大小M，那么存在一个线性网络编码使得所有数据收集器可恢复出初始数据对象。更进一步，随机网络编码通过增加域的大小，保证了所有的收集器能够以任意高的概率恢复出初始数据对象。证明.数据重建问题等价于多播问题，即从一个源点发送数据到所有的数据收集器。由[1]知道网络编码能够满足相关的最小割—最大流限制，从[15]我们可以知道这样的线性网络编码是存在的。Ho等人[13]展示了在所有节点使用随机线性网络编码，通过增加域的大小可以将达到限制的概率推到任意高。（参考文献[13]中定理3证实了这种概率至少为(1d