英语原文共 16 页
部分并行修复（PPR）：
一种修复纠删码存储的分布式技术
Subrata Mitra ，Rajesh Panta ，Moo-Ryong Ra ，Saurabh Bagchi
普渡大学，AT＆T实验室研究
摘要
随着我们周围应用程序数据的爆炸式增长，纠删码存储相对于复制已成为一种有吸引力的替代方案，因为即使存储开销显著降低，它们也能提供更好的数据可靠性。里德-索罗门编码是目前使用最广泛的纠删码，因为它为给定的存储开销提供了最大的可靠性，并且在选择确定可实现的可靠性的编码参数方面是灵活的。然而，不可用数据的重构时间变得非常长，主要是因为网络瓶颈。一些提议的解决方案要么使用额外的存储，要么限制可以使用的编码参数。在本文中，我们提出了一种新的分布式重构技术，称为部分并行修复（PPR），它将重构操作划分为小的部分操作，并在已经参与数据重构的多个节点上安排它们。然后，分布式协议逐步组合这些部分结果以重构不可用数据块，这种技术降低了网络压力，从理论上讲，我们的技术可以在[（log2（k 1））]时间内完成网络传输，而(k,m)里德-索罗门编码需要k时间。我们的实验表明PPR可以显著缩短修复时间并缩短读取时间。此外，我们的技术与现有的纠删编码兼容。我们通过将PPR叠加在两个先前的方案（局部重构码和旋转的里德-所罗门码）之上来证明这一点，以便于节省重构时间。
关键词：纠删码，分布式存储，网络传输，修复，重构，利用
1.介绍
在过去几年里，大量数据被创造出来，一些研究表明，世界上90％的数据都是在过去两年中创造出来的[7]。我们不仅生成了大量数据，而且数据创建的速度也在迅速增加。随着这种增加，面对磁盘或磁盘块故障，用户仍存在对数据具有高可用性的期望。复制是提供存储数据可靠性的常用技术，但是，复制使数据存储更加昂贵，因为它将原始存储的成本增加了一个等于复制计数的因子。例如，许多实际存储系统（例如，HDFS [43]，Ceph [1]，Swift [6]等）维护三个数据副本，这将原始存储成本增加了三倍。
近年来，纠删编码（EC）作为数据复制的替代方案受到青睐和越来越多的应用，因为它们可以显著减少存储开销，同时保持相同（或更好）的可靠性。在最广泛使用的EC方案的（k，m）里德-所罗门（RS）码中，将给定k个数据块组编码成（k m）个块。整个组块构成条带，编码后使得（k m）数据块中的任何k块足以重构原始数据。例如，在RS（4,2）编码中，4MB的用户数据被分成4个1MB的块。然后，创建另外两个1MB奇偶校验块以提供冗余。通过三重复制系统，所有四个1MB块被复制三次。因此，RS（4,2）编码系统需要1.5x字节的原始存储来存储x字节的数据，并且它可以容忍多达两个数据块故障。另一方面，三重复制系统需要3x字节的原始存储空间，并且可以容忍相同数量数据块的同时出错。
尽管在可靠性和存储开销方面具有吸引力，但是纠删编码的一个主要缺点是昂贵的修复或重构过程。当编码块（比如c字节）由于磁盘或服务器1故障而丢失时，在（k，m）编码系统中，需要从k个服务器检索ktimes;c字节的数据以恢复丢失的数据。另一方面，在三重复制系统中，由于每个c字节块被复制三次，因此可以通过仅复制来自任何一个剩余副本的c字节数据来恢复块的丢失。网络流量中的这个k因子增加导致重构非常缓慢，这对于任何大小合理的数据中心来说是一个关键问题，其中磁盘，服务器或网络故障经常发生，从而需要频繁的数据重构。另外，较长的重构时间降低了尝试读取丢失数据的正常操作性能。在较长的重建时间窗口，数据进一步丢失的可能性增加，从而增加了数据永久丢失的敏感性。
应当注意，虽然减少修复流量很重要，但实际存储系统还需要维持一定水平的数据可靠性和存储开销。因此，以增加存储开销和较差的数据可靠性为代价，使用低修复流量的纠删编码是不可取的。但是，减少修复流量并且不会对存储开销和数据可靠性产生负面影响是一项具有挑战性的任务，在理论上已经证明，数据可靠性，存储开销，修复流量和修复程度之间存在基本的权衡。Dimakis等人[17]提出了一个最优权衡曲线的数学公式，它回答了以下问题：对于给定的数据可靠性水平（即给定的（k，m）纠删码方案），在保证一定级别的存储开销的同时，可行的最小修复流量是多少？在这个最佳曲线的一端有一系列称为最小存储代码的纠删码，它需要最小的存储开销，但需要很高的修复带宽。在频谱的另一端有一组称为最小带宽代码的纠删码，它需要最佳的修复流量，但会产生很高的存储开销和修复程度。现如今使用的代码处于该最佳权衡曲线的不同位置，例如，在许多实际存储系统[14,36]中流行的RS码需要最小的存储空间，但会产生大量的修复流量。本地可修复代码[22,31,42]需要较少的修复流量，但添加了额外的奇偶校验块，从而增加了存储开销。
在本文中，我们设计了一种称为PPR的实用EC修复技术，它可以减少修复时间，而不会对数据可靠性，存储开销和修复程度产生负面影响。请注意，我们的技术可以减少修复时间，但不会减少链接上聚合的总修复流量。此外，我们的方法是对现有的易修复代码的补充，因为PPR可以简单地覆盖在任何现有的EC方案上。
关键见解：EC系统中重构缓慢的关键原因是重构期间网络资源的利用率低。重构失败的数据块需要修复服务器从k个不同的服务器获取k个数据块（属于与失效块相同的条带）。 这会导致进入修复服务器的网络链路变得拥挤，从而增加了网络传输时间。集群中的测量结果表明，网络传输时间占整个重构时间的94％，如图1所示。其他研究人员也报告了类似的结果[26,36,42,44]。图2是在（3,2）EC系统中重构失败的数据块示例。进入修复服务器（服务器S7）的网络链接比到其他服务器的网络链接的拥塞程度高三倍。PPR试图通过在现有网络链路上更均匀地重新分配重构流量来解决该问题，从而提高网络资源的利用率并减少重构时间。 为了重新分配重构流量，PPR采用了一种新的方法来执行重构，而不是在单个重构服务器中集中重构，PPR将重构分成几个部分并行修复操作，这些操作在多个服务器上同时执行，如图2所示。然后使用树状覆盖网络收集部分计算的这些结果。通过在多个服务器之间拆分修复操作，PPR消除了修复服务器的网络链路中的拥塞，并在现有网络链路上更均匀地重新分配重构流量。从理论上讲，与（k，m）RS码所需的O（k）时间相比，PPR可以在O（log 2（k））时间内完成单个块重构的网络传输。表1显示在实际系统中使用典型纠删编码参数所需的重构网络传输时间比预期少。虽然PPR不会减少重构期间传输的数据总量，但通过在网络链路上更均匀地分配数据进行传输，可以显著减少重构时间。
PPR的一个好处是它可以叠加在几乎所有已发布的纠删编码方案之上。包括但不限于最广泛使用的RS码，LRC码（本地可修复码或本地重构码[22,31,42]），PM-MSR码[36]，RS-Hitchhiker码[38] ]，旋转RS [24]码。这是因为PPR的布局与这些先前使用的编码和放置技术正交。
在考虑任何方案对EC系统中丢失块重构的影响时，我们需要考虑两种不同的重构方式。第一种称为常规修复或主动修复，其中监视守护进程主动检测到块丢失或错误并触发重构。第二种称为降级读取，其中客户端尝试读取尚未修复的丢失数据块，然后必须在关键路径中执行重构。 PPR显著缩短了这两种重构的时间。降级读取是实际存储系统的一个重要问题，因为降级的读取操作经常发生，比常规修复更频繁。由于滚动软件更新，操作系统问题和非磁盘系统故障等问题，瞬态错误占数据中心故障的90％[19] [22,24]。在这些情况下，不需要实际修复，但由于客户端请求可能在瞬态故障期间发生，因此降级读取是不可避免的。此外，许多实际系统延迟了修复操作，以避免启动昂贵的瞬态错误修复[44]。
PPR引入了一种负载平衡方法，可在多个请求同时进行时进一步缩短重构时间。我们将此方法称为m-PPR。当从（k m）个可用服务器中选择k个服务器进行重构时，PPR会选择那些已经将数据缓存在内存中的服务器，从而避免这些服务器在磁盘IO上耗费时间。m-PPR协议尝试以这样的方式调度多个条带同时重构，使得网络流量均匀地分布在现有服务器之间。 我们在第6节中介绍了m-PPR的更多细节。
我们在Quantcast文件系统（QFS）[30]之上实现了PPR，它支持基于RS的纠删码存储。对于表1中描述的典型纠删编码参数，我们的原型可以使修复时间减少高达59％，其中57％来自单独网络传输的减少。在不降低数据可靠性或增加存储开销的情况下实现了重构时间的显著减少。
本文做出了以下贡献：
我们介绍了一种新颖的分布式重构技术PPR，它可以显着缩短网络传输时间，从而将基于纠删码存储系统的整体重构时间缩短高达59％。
我们提出了额外的优化方法以进一步减少重构时间：a）用于减少IO读取时间的缓存方案和b）针对多个重构操作同时进行的调度方案。
我们证明我们的技术可以很容易地覆盖在除里德-所罗门以外的其他的复杂编码上，例如LRC和旋转RS，它们旨在减少修复时间。除了这些编码之外，PPR还使重构时间分别减少了19％和35％。
本文的其余部分安排如下。在第2节中，我们给出了RS编码背后的数学原理。第3节描述了动机，第4节详细描述了主要的PPR技术。在第5节中，我们讨论使用PPR处理多个重构操作。第6节提供了设计方案和实现细节。在第7节中，我们评估了PPR w.r.t传统修复方法和其他提出的解决方案。在第8节中，我们讨论相关的工作，最后在第9节我们得出结论。
2.里德-所罗门编码入门
纠删码存储很有吸引力，主要是因为它对于给定的可靠性水平只要求较少的存储开销。在许多可用的纠删编码技术中，里德-所罗门（RS）码[39]是最广泛使用的编码方式。RS代码属于最大距离可分离（MDS）码类[27]，它为给定的存储开销提供最大可靠性。对于（k，m）RS码大小为N的可用数据项被分成k个相等的数据块，每个块的大小为N / k。然后从原始k个数据块计算另外的奇偶校验块。术语条带指的是从原始数据创建的这组（k m）块。基于其创建奇偶校验块的数学属性，确保可以使用剩余块中的任何k个数据块来重构任何丢失的块（数据块或奇偶校验块）。在重构过程之后，托管重构数据的服务器被称为修复站点。
RS编码：RS编码操作可以表示为矩阵向量乘法，其中k个数据块的向量乘以大小为（k m）times;k的特定矩阵G，如图3a所示是（4，2）RS代码。 该矩阵G称为生成矩阵，由范德蒙矩阵[13]构成元素aij等根据伽罗华域（GF）算法[39]计算。在GF算术中，加法相当于异或操作; 因此，使用块B添加块A将涉及按位异或操作。通过标量（例如G的元素）乘以块相当于将每个GF字组件乘以常量。
RS重构：在图3a中，当一个块丢失时，可以使用一些线性代数运算来重构它，其中G和条带中剩余的块集。 例如，在图3b中，如果丢失了奇偶校验块（例如，P2），则可以通过将对应的行（在示例中的最后一行）乘以数据块向量来重新计算它。另一方面，如果数据块（例如，D3）丢失，则重构涉及两个步骤：第一步通过采用使用任何k创建的矩阵的逆（即，我们中的四个）来计算解码矩阵H. 例如）G的幸存行。我们将H的元素称为解码系数。第二步将先前选择的k个幸存块（数据和奇偶校验的组合）乘以对应于丢失块（即图中的第3行）的解码矩阵的行。因此，解码过程是求解一组独立的线性方程。
3. EC存储的致命弱点：重构时间
对于常规修复和降级读取，重构路径包括三个主要步骤：多个服务器从其自己的磁盘读取相关块（通常在每个服务器上并行完成），每个服务器通过网络将读取块发送到修复站点 最后在修复站点执行一些计算以重构丢失的块。 对于常规修复，重构的块最终写回磁盘，而对于降级读取，数据由用户请求直接使用。 因此，（k，m）RS编码的重构时间可以近似如下
（1）
从图1中可以看出，网络传输和IO读取是两个最耗时的步骤，而计算时间相对不重要。 其中，网络传输时间是最主要的因素，因为每次重构需要k个块传输。通常，这种巨大的数据传输会在维修站点附近造成网络瓶颈。 例如，Facebook [42]使用RS（10,4）代码，数据块大小为256MB。在这种情况下，为了修复单个块，需要将超过20Gbits汇集到一个服务器中。在许多实际情况下，已发现该数据量压倒了网络资源，导致极长的重构时间。尽管网络技术最近取得了进展，但随着网络繁重应用的快速增长，网络仍然是数据中心中最稀缺的资源，我们预计网络传输时间将继续成为EC存储重构操作的瓶颈。
如果重构很少，那么如此长的重构时间仍不是问题。然而，大型数据中心的故障痕迹[35,42]表明，情况并非如此。分析Facebook数据中心的故障，Rashmi等人[35] 在一台拥有几千台机器的数据中心内，平均每天报告50台机器不可用事件（机器故障超过15分钟），每台机器的存储容量为24-36TB。为了保持数据的可靠性，这些事件最终会导致重构工作。此外，Sathiamoorthyet等人[42] 报告称，没有永久性数据丢失的瞬态错误对应于90％的数据中心故障事件。这些情况经常导致降级读取，其中重构操作发生在用户读取请求的关键路径中。
因此，较长的重构时间是大规模采用分布式纠删码存储的主要障碍，并且预计网络
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
