英语原文共 12 页
修复树：基于纠删码的分布式存储系统中单一故障的快速修复方法
摘要——为了保证数据的可靠性，纠删码被用在了分布式存储系统中。然而，这种机制受到修复单个故障需要过多数据的问题困扰，导致网络带宽消耗太高、替换节点的计算负载过重。为了减少修复流量，研究人员指出存储和修复流量之间的权衡，并通过组合网络编码提出了再生码。然而，这种组合只关注储存终端，并且代码的构造非常复杂。因此，本文进一步将网络编码与网络结构相结合，提出了一种基于通用纠删码的修复树模型，简化了修复过程。我们的模型通过将修复计算分解并分配给树节点的方法，缓解了计算矛盾。在经过初步仿真分析和修复树性能评估后，结果表明，与传统方法相比，我们的模型可以使计算速度提高大约三倍，如果存在网络瓶颈，则可以将修复吞吐量增加一倍。对于正确的拓扑结构，它可以显著减少维修流量。我们提出了算法来跨网络拓扑生成树。最后，我们提出了扩展修复树来修复多个故障的想法。
关键词——分布式存储系统，纠删码，分解修复计算，单一故障，修复树，传递向量，网络编码，中间节点
一、简介
在大规模分布式存储系统（DSS）[2]，[3]中，失败是常态而不是例外。为了保证数据的长期可靠性，人们通常采用冗余策略，其中一种流行的方法是纠删码策略[4]，[5]，[6]。例如，将大小为B的文件分成k个带，每个带的大小为，并使用（n，k）最大距离可分离（MDS）代码编码为n个编码带，然后将n个带分布在n个节点上。从n个带中的任何k个，可以通过下载最小数据来重建大小等于B的原始文件。虽然纠删码可以容忍n-k并发故障并提供最佳的冗余可靠性权衡，但是它自身的修复问题削弱了它的优势。也就是说，当一个带失效时，我们通常需要访问其他编码带来回复他。我们从n-1个幸存节点的子集中下载k个带来重新编码新的带，这意味着重建数据会导致当带宽和计算资源不足时，下载和计算B数据不可避免地会降低修复速度。因此，降低流量和提高计算性能至关重要。
Dimakis等人创造性地向DSS中引入了网络编码，并腿断了存储和修复带宽之间的权衡。塔姆提出了再生码（RGC）。其中一个剋以将整个修复流程减少到，其存储开销与传统的纠删码相同，称为最小存储再生（MSR）码，其中d是可用辅助数量，kle;dle;n-1。其核心思想是我们进一步将每个带划分为d-k 1个部分，每个帮助节点将这些部分的一个线性组合发送到替换节点，然后替换节点从d个收集的组合中回复丢失的带。当d=n-时，该值最小化：，当正确选择n和k的值时，可以大大节省带宽。
然而，当d=k时，它仍然需要B的数据，并且如果d在动态系统中波动，我们将不得不从每个帮助节点中下载不同大小的数据，这可能导致更复杂的操作，例如将一个带分成更多块，扩展编码矩阵等。事实上，RGC的构造比一般的纠删码更为复杂。通过回顾网络编码与纠删码DSS修复问题之间的联系，我们发现Dimakis等人仅关注在终端存储节点上应用网络编码而不考虑网络本身。鉴于网络编码的诞生和著名的蝴蝶模型，网络拓扑在应用程序中起着重要作用，这激发了我们探索和开发故障恢复的兴趣。
考虑如图1所示的实际系统，其中包含通过路由器/交换机部署在网络中的大量廉价服务器。在这个系统中，编码的带分散在不同的服务器上，一个守护进程在发生故障时开始修复。传统的修复（CR）程序是：守护进程从幸存的服务器收集k个带，计算相应的解码矩阵，解码原始文件，然后通过失败的编码向量重新编码丢失的带。它只保留一个恢复的条带，最后丢弃所有帮助数据。通常，守护进程在替换服务器中执行。在这种情况下，恢复计算和网络流量的开销都很大。此外，主流DSS的层次结构[2]，[3]决定了带宽或I / O资源在更高层中更为宝贵，因为它们处理更多事务，这意味着减少这些路由器/交换机的流量是非常必要的。
图1 (5; 3)纠删码分布式存储系统中的单个故障修复示例。 为了修复h4，替换节点h4rsquo;从h1，h2和h3下载数据，占用路由器R3, R4, R6的三倍带宽，占用路由器R2的2倍带宽。
受到这些想法的启发，我们假设如果我们计算带尽可能靠近帮助节点并减少中间节点通过网络传输的冗余数据，这样核心路由器/交换机的流量将减少。例如，我们将图1中的网络逻辑映射到图2中的信息流图。图2a表示传统路由器{R3; R4; R6}缓解重网络流量（三条{a; b; c}）和替换服务器重新编码丢失的数据（{a; b; c}为{5a 2b 3c}）。而在图2b中，计算路由器{R2; R3}在助手{h2;h3; h1}之后的加法运算;发出计算数据{5a; 2b; 3c}，则链路R2-R3和R3-h4#39;上的网络流量达到最小（一条带{5a 2b 3c}）并且替换服务器{h4#39;}的计算成本最低（确切地说，不再有计算）。基于这样的假设，我们通过将网络拓扑结合到修复过程中，提出了一种用于纠删码DSS中的单个故障的快速修复（FR）机制。
第一个方面是分解修复计算。 由于代码的线性组合属性，我们分解修复编码并将其分布在网络上。核心是辅助数据及其系数的乘法运算是在每个发送节点而不是沉降节点上执行的。 例如，我们首先获得传递矢量（图2b中的lt;5 2 3gt;），丢失带的编码矢量和解码矩阵的乘积，然后将传递矢量的每个元素发送到相应的辅助节点。帮助节点在发送之前将帮助数据乘以元素。 在这种情况下，分布式助手共享复杂的有限场上的乘法，只留下加法（恰好是XOR）。 特别地，分解可以显着减轻沉降片的编码负担。
第二个方面是修复树模型。假设存在计算中间节点，我们进行简单的网络编码以减少修复流量。与网络编码路由器[14]类似，计算中间节点能够进行计算和转发，而不是存储转发。即，如果有两个或更多并发流经过同一计算中间节点，则该节点计算这些流的线性组合，并仅将结果转发到下一个目的地。事实上，当在通过中间节点之后将多个带组合成一个带时，可以预先获得部分最终恢复数据的组合。由于防止了不必要的数据通过其余链路传输，因此可以减少整个系统的流量。我们在信息流图中制定这个修复模型并称之为修复树，其中替换节点是根，帮助者是叶子。如果发生碰撞，则数据流在中间节点处组合。
图 2 图为图1的信息修复流程图。图(a)为传统路由器遇到巨量网络流量时的情况，图(b)具有计算能力的路由器最小化修复流量。
我们考虑修复树模型中的分解。由于它主要涉及在帮助发送数据之后的XOR操作，因此计算成本最小。更重要的是，应该注意帮助节点的位置在影响所节省的交通量方面起着重要作用。例如，如果XOR操作接近DSS中的较低级别，则较高级别或最终替换服务器将显着节省带宽。因此，从分布式网络构建适当的修复树至关重要。
实际上，修复树可以被视为多点传送的逆过程，比如多对一模型。 尽管在中间节点处收集来自分支的n个独立流，并且最终获得它们的1个线性组合，但是它与一对多多点传送模型不同，其中1个数据流在中间节点处被复制并且被发布到n个分支。 网络上修复树的基本构造可以模仿多点传送树的结构。在构建最优全类修复树时，我们提出相关的启发式算法，以获得最优的修正树。
为了验证我们修复策略的效果，我们首先考虑重新编码的分解。实验表明，与传统修复相比，它可以提高计算速度约3倍。我们在HSN实验室的演示系统中实现了整个修复树模型[15]。它基于OpenFlow交换机。结果表明，在适当的树形拓扑下，我们的模型可以显着提高修复速度。
此外，上述考虑仅涉及单一故障，这是最常见的故障，发生率为99.75％[16]。至于多个故障，比如t故障，这个机制是可行的。如果在通过交叉节点sgt; t后将s输入条组合成t条，则可以节省流量。我们从类似的想法扩展初步模型。
二、分解修复计算
2.1纠删码的背景
主要的纠删码是基于行列式或柯西矩阵的Reed Solomon（RS）码[17]，[18]。 RS码的构造涉及对有限域x的算术运算。具体来说，每个条带被分成代码字。每个单词的大小是w-bits，由程序员选择并且wge;log（n k）。在伽罗华域（GF（））中，每个单词都是被定义过的。因此，加法和减法是简单的XOR运算，而乘法或除法则更复杂。后者的基本方法是查找表[18]，它几乎不支持更大的w。为了简化这种复杂性，XOR 柯西算法[17]将乘法转换为XOR运算（见图3a），有助于提高计算性能。 Plank J S等通过构造良好的柯西分布矩阵进一步优化其性能[19]。虽然计算复杂度可能达到最优，但计算负担集中在单个节点进行修复，其中所有k个带被收集以通过柯西-XOR操作重新编码丢失的数据。数据量的不断扩大对CPU和内存造成了巨大压力。我们尝试将计算分配给分布式节点，以尽可能早地分担压力并减少数据量。
2.2分解修复计算
根据公式（3）和（4），我们通过在k帮助节点分布来分析修复带的性能。我们将它与最快的纠删码方法进行比较，最佳的Cauchy RS（CRS）代码在Jerasure Library中实现[20]。 CRS在有限字段上采用XOR运算。如图3所示，系数被映射到一个w * w bits的正方形，其中黑色表示1，白色表示0。L单元条被分成w个代码字，每个代码字是长度为bits的单位。乘法转换为相应代码字之间的XOR运算。小黑方块的数量减去w等于XOR的数量。图3a表示传统的CRS修复方法，XOR的数量为14；图3b示出了分解的CRS（D-CRS），其中我们在将帮助数据发送到网络之前划分传递矢量并在辅助节点处进行XOR。然后每个助手的XOR数分别为0,1,1和3。下载预处理数据后，替换节点仅需要9个XOR。在这种情况下，替换节点中的XOR数量小于良好柯西矩阵中的任何修复向量[19]。从图中可以看出，帮助节点只处理帮助数据而不是直接读取和发送。表1进一步揭示了相关的修复计算复杂性，其中我们还比较了公共RS修复和分解RS（D-RS）修复的性能。它表明替换服务器的恢复时间在传统过程的整个修复过程中占主导地位。当帮助节点共享计算时，替换节点仅需要复杂度的CR。对于每个帮助节点，计算成本是可接受的。
图3 图(a)为传统CRS修复一个带的实例，图(b)为分解后的CRS修复一个带的实例
即使两种情况下的XOR总数相等，替换节点的修复速度也会显着提高，而帮助节点中的计算开销在我们的模型中可以忽略不计。
三、修复树模型
根据上面的陈述，替换节点将发送给帮助节点，计算 = 并发送回。收集节点只计算{,hellip;,}的总和来进行恢复。因此，终端帮助节点不仅分担乘法运算所产生的计算压力而且在替换节点简化修复程序。更重要的是，如果助手和替换节点之间存在中间节点，并且两个或多个数据流同时通过同一个中间节点时，我们可以对这些数据进行异或，只发送结果以减少带宽。 因此，单个修复过程可以被视为多对一网络通信问题，这类似于多点传输的逆过程[21]。
四、构建修复树
如图4所示，修复树依赖于网络拓扑以通过中间节点计算来保存修复流程，这表明我们需要构造具有已知终端节点的树，即根据网络的Ucup;T。 对于逻辑树本身，当k ge;3时，在不同数量的中间节点下存在变量结构。即使对于相同数量的中间节点，也存在一种异构树。 在这种情况下，由于各种网络布局，任何一棵树都可能是最佳的（例如，极端情况（a）对于星形拓扑是最佳的）。 我们只关注根据以下原则从真实网络生成修复树：
- 建立链路时，帮助节点应靠近下层;
- 中间节点应该靠近辅助节点;
- 从辅助节点到根的路径应尽可能短。
图 4 使用中间节点作为计算节点以减少用于修复的流量的示例。假设U={，，}，M={}，则每条路径上的流量均为L。
4.1 修复树，多点传输树和斯坦纳树
第3节中我们演示了修复树类似于多点传输树的逆过程。但是，他们之间的差异决定了我们不能无差别地模仿多点传输构建修复树。主要区别在于多点传输树的每个链路中的数据是源信息的副本，而数据可能在修复树中的流量集中后发生变化。与多点传输相比，这三个原则增强了中间节点的重要性。然而，通过检查多点传输树，我们发现源树和共享树都可以被吸收和利用。源树也称为最短路径树（SPT），是从根到每个叶子的最短路径的生成树。虽然共享树具有共同的根，称为集合点（RP），但对于所有多播组。流量从共享树和RP向下转发以到达每个接收节点。如果接收节点位于源和RP之间，则通过源树直接处理接收节点。类似地，需要考虑RP相对于源的位置和树的大小。
对于最优的G，目标是最小化w(G)，这就是斯坦纳树问题[23]，这与最小化多点传输共享树相同。也就是说，给定N=Ucup;T，其目标是以最小的总成本通过边缘将它们连接起来，这样任何两点都可以通过边缘直接或通过其他点和边缘互连。然而，斯坦纳树问题是全类，我们采用启发式或近似算法。
五、修复树的恢复功能评估
由于交换机和路由器都具有物理地融合不同数据流的能力，因此在这些设备中嵌入计算模块是可行的。 事实上，随着软件定义网络（SDN）[27]和OpenFlow [28]的发展，将出现更多的计算交换机和路由器。因此，我们使用OpenFlow交换机连接上述系统中的分布式存储节点。我们的OpenFlow交换机在NetFPGA中实现。我们基于HSN实验室[15]的工作模拟了图4的模型。
六、修复树构造算法的仿真研究
在本文中，我们提出了一种基于纠删码的分布式存储系统中修复故障的新方法。 首先，我们在替换节点处分解复杂的修复计算并将其分发给所有帮助程序，为剩余的网络节点留下简单的XOR操作。其次，我们将网络拓扑结合起来，通过在中间节点中嵌入这些简单的XOR运算来优化修复流量。我们提出修复树模型并证明修复树高斯属性。在最好的情况下，我们可以将修复流量降至最低，等于丢失数据的大小。我们讨论了修复树和多点传输树之间的关系，并提出了相关的算法。我们的初步实验表明，我们的模型可以显着减少维修流量，从而在更换节点上实现巨大的吞吐量改进。
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
