Dayu -- Fast and Low-interference Data Recovery in Very-large Storage Systems

原文链接：[Dayu: Fast and Low-interference Data Recovery in Very-large Storage Systems | USENIX](https://www.usenix.org/conference/atc19/presentation/wang-zhufan

摘要

​ 本文试图在对前台流量干扰最小的情况下，加速大规模存储系统中的数据恢复。通过研究现实世界的大型存储系统的I/O和故障跟踪，我们发现，由于系统的规模和不平衡的动态前台流量，现有的恢复协议不能在短时间内生成高质量的恢复策略。为了解决这一问题，本文提出了一种基于时点的恢复协议 —— Dayu，它只安排了预期在一个时点内完成的任务的子集，这种方法减少了计算开销，自然能够应对动态的前台流量。在每个时间段，Dayu 整合了四个关键算法，通过我们的跟踪分析激发启发式来增强现有的解决方案。我们在1,000个节点的真实集群和25,000个节点的模拟中进行的评估都证实，Dayu 能够比现有的恢复协议表现得更好，实现高速度和高质量。

介绍

​ 本文描述了我们在盘古中加速数据恢复的经验和方法，盘古是一个现实世界的大型存储系统，拥有10K个节点，每个节点有几十TB的存储空间。作为云存储提供商，盘古的所有者阿里云需要向客户承诺数据的持久性（即数据丢失的几率小于阈值）。出于营销方面的原因，所有者有足够的理由来提高数据的持久性，因此与竞争对手相比，它的承诺更有吸引力。这促使我们研究盘古数据恢复是否有可能加速，因为恢复速度是决定数据持久性的因素之一。

​ 类似于之前的工作，盘古将数据分成块（通常是几十MB），复制这些数据块，并将这些复制分布到不同的节点上。当一个节点发生故障时，盘古会重新复制它的数据块，由于这些数据块的副本分布在不同的节点上，盘古要求所有这些节点并行复制数据块。为了重新复制故障节点的数据块，恢复协议需要为每个数据块调度源、目标和带宽。一个理想的调度算法至少应该实现以下两个目标：

​ 第一，算法应该生成一个高质量的策略，该策略应该允许在对前台流量影响最小的约束下尽快完成数据的再复制

​ 其次，调度算法本身的速度要足够高，以免成为数据恢复的瓶颈。

​ 为了了解现有调度算法的质量和速度，我们分析了盘古实际部署的失败和I/O轨迹。我们发现现有的算法都无法达到可接受的质量和可接受的速度，因为存在以下挑战：

• 非常大的规模：盘古最大的部署有超过 10K 个节点和高达 72TB 的存储（约150万个块）每个节点。因此，当一个节点失效时，算法需要决定如何恢复所有这些数据块，每个数据块大约有 10K 个节点作为候选目的地。
• 时间限制：考虑到系统的规模，故障节点的数据块可以以高度并行的方式进行重新复制。我们的仿真表明，如果能充分利用空闲带宽，恢复可以在十秒内完成，这意味着调度算法本身应该在几秒内完成。
• 不平衡的前台流量和可用数据：我们发现一个双重的不平衡，这对调度的质量提出了挑战。
  • 首先，一些节点的前台流量可能比其他节点要大得多
  • 其次，一些节点可以有更多的数据块用于重新复制。
• 动态前台流量：前台流量可以随着时间的推移而显著变化。为了应对这种动态流量，恢复协议需要在前台流量发生显著变化时调整其计划，这再次需要快速调度。

​ 我们对现有调度算法的模拟表明，一方面，简单和分散的算法，如随机选择或两种最佳的随机，可以快速完成调度（即高速），但它们经常导致少量节点过载，增加恢复时间，损害前台流量的性能（即低质量）。另一方面，复杂和集中的算法，如混合整数线性规划，可以有效地利用可用带宽并避免节点过载（即高质量），但考虑到我们的目标系统的规模（即低速度），它们可能需要非常长的时间来计算一个计划。

​ 本文提出了一种适用于大规模、不平衡、动态存储系统的高速、高质量恢复协议“大禹”。大禹的核心理念来源于观察，为了应对动态的前台流量，我们需要定期监控前台流量并调整恢复计划：在这种设计中，对故障节点的所有数据块进行调度不仅计算量大，而且没有必要，因为计划可能在以后进行调整。根据这一观察，大禹整合了一个基于时隙的解决方案：

1. 它将时间划分为多个槽，槽的长度由底层存储系统监视和报告空闲带宽的频率决定
2. 根据这样的报告，大禹试图安排一个子集的块，以便它们可以在当前的时间段内重新复制
3. 如果由于某种原因，某些块的实际复制时间比预期的长，那么大禹将在下一个时间段重新安排它们

这种方法有两个好处：首先，它减少了调度的计算开销，因为在每个时间段，算法只需要调度一个任务子集（在我们的实验中平均约三分之一）。其次，这个解决方案可以很自然地应对动态的前台流量，因为大禹的决策是基于每个时间段开始时收集的信息。

为了实现这一想法，大禹整合了四项关键技术，根据我们的观察，对现有算法进行了改进：

• 斗式凸壳优化的贪心算法调度任务：大禹利用贪心算法迭代选择利用率最高的候选项作为每个任务的源和目标，直到找到足够的任务来填满一个时间段。为了减少计算开销，大禹引入了凸壳优化[，并进一步提出了桶近似来减小候选集的大小。
• 优先考虑具有高空闲带宽但很少可用块的节点：我们的观察表明，如果调度算法决定从其他节点复制它们的块，这样的节点很可能没有得到充分利用。因此，大禹对前面提到的贪心算法进行了改进，采用了以下启发式算法：如果要重新复制的块在该优先级节点上有副本，大禹将该节点指定为源。
• 迭代WSS为每个任务分配带宽：为了最小化所选任务的完成时间，大禹对加权洗牌调度算法（WSS）进行了改进：在每次迭代中，大禹使用WSS来识别剩余任务中的瓶颈，并相应地为每个任务分配加权公平的带宽份额，消除瓶颈任务并分配带宽。
• 重新调度Straggler：由于对前台流量的错误预测或意外的硬件故障，不可避免地会出现Straggler任务，因此大禹不得不在下一个时间段重新调度它们。Straggler任务不同于新任务，因为我们喜欢保持它们的目的地不变，否则，我们将失去它们现有的进度。大禹首先估计是否值得改变它们的目的地，然后重新计算它们的源并分配带宽。

​ 我们在实际部署1000个节点的情况下对大禹进行的评估表明，与盘古相比，大禹的恢复速度提高了2.96倍，并且在恢复过程中，前台流量的p90延迟（即90个百分点的尾部延迟)仅提高了3.7%。我们的仿真结果表明，大禹的性能优于现有的各种解决方案，可以扩展到25K个节点的集群。

背景与观察

2.1 盘古的背景

​ 盘古是阿里云的底层存储系统，阿里云是亚洲最大的公共云提供商之一。盘古继承了GFS、HDFS、Cosmos和Azure等经典的分布式文件系统架构。它将数据分割成多个块（最常见的块大小为64MB），并将数据块存储在称为块服务器的大量数据服务器上。一个名为 Meta Server 的元数据服务器维护分布式文件系统的元数据，例如数据块的位置。由于盘古的规模非常大，盘古整合了多个元服务器，每个元服务器负责元数据的一个子集。此外，盘古整合了一个 Root Server 将客户端路由到相应的 Meta Server。为了实现数据的均匀分布，盘古使用随机或加权随机机制将数据放置在不同的 Chunk Server上。

​ 像大多数现有系统一样，盘古复制数据块（大多数数据块有三个副本），所以如果一个节点故障，盘古可以通过从其他副本复制来恢复它的数据块。对于每个要恢复的数据块，盘古需要为数据复制选择一个源和一个目的地：根据副本的数量，通常有几个候选源和大量的候选目的地。当前版本的盘古随机为每个要恢复的数据块选择一个源和一个目的地。在盘古当前的部署中，我们观察到网络带宽通常是进行此类数据恢复的瓶颈：大多数盘古节点配置1GB或10GB以太网，其带宽小于磁盘的总带宽；由于成本原因，高速设备（如Infiniband）的部署受到限制。盘古的核心网络交换机采用CLOS拓扑或胖树拓扑组织，因此不会出现超额订阅。根据配置的不同，从核心到机架的链路可能会被过度订阅：如果链路被过度订阅，机架交换机通常是瓶颈；否则，终端主机的网卡就是瓶颈。

​ 在数据恢复期间，盘古仍在为前台应用服务，这些应用可能会争夺网络带宽。为了减少数据恢复对前台流量的干扰，盘古提供了一种机制来限制节点上一条或一组链路的带宽利用率。通过这种机制，我们可以根据愿意容忍的干扰程度和前台流量的带宽，对恢复流量的带宽设置一个限制。在大禹，我们将每个节点上的恢复流量的带宽限制为 \[ B_{recover}=max(α×B_{total}−B_{foreground},B_{min}) \] ​ 式中，\(B_{total}\) 是节点的总带宽；\(B_{foreground}\) 是前台流量的带宽；\(α\) 是控制恢复业务对前台业务干扰的参数。我们将 \(α\) 设置为75%，我们的实验表明，使用这个设置将对前台流量的p90延迟产生微不足道的影响。作为一个主要为大文件设计的存储系统，盘古的目标不是优化极端的尾部延迟（例如99.9%），所以这个设置可以满足我们的要求，如果一个人的目标是更小的干扰，他/她可以进一步降低\(α\)。\(B_{min}\) 是节点为恢复分配的最小带宽，这是为了确保恢复不会太慢。盘古和大禹都将\(B_{min}\)设置为30MB/s。

2.2 观察

​ 在本小节中，我们分析盘古部署的工作负载和数据放置，以了解它们如何影响数据恢复。我们从大约3500个节点的数据中心获取这些信息，每个节点有两个1G网卡和11个2TB硬盘。此时，硬盘的总带宽将大于网卡的总带宽。存储系统主要提供ODPS （online data processing service，联机数据处理）服务，包括MapReduce和数据查询。我们分析的内容包括：（1）2018年4月一个 MetaServer 的检查点，记录与数据块大小和分布相关的元数据；（2）未来一周前台流量和后台恢复流量的跟踪。除非另有说明，我们的模拟实验在本文中都是在这个3500个节点的集群上进行的。在第5.2节中，我们研究了在3500个节点之外，大禹的可扩展性。

我们通过分析得出以下结论：

​ 观察1：每个节点存储了数十万块数据

​ 图1(a) 显示了每个节点上块数量的 CDF。我们可以观察到，大多数节点每个节点大约有250K块。这个观察结果说明了两件事：首先，恢复协议需要安排如何在节点故障时恢复如此多的块。其次，当一个节点发生故障时，剩余的每个节点将平均参与大约70个块的复制（250K/3500）。

​ 观察2：前台流量平均消耗不到带宽的一半

​ 如果所有可用带宽（使用Equation1计算）都可以用于恢复，系统平均可以在51秒内恢复250K块。

​ 我们计算了50种不同情况下的最佳恢复时间，假设所有可用带宽都可以利用，并在图1(b)中给出了恢复时间的CDF。该观察结果表明，尽管每个节点故障都有大量的块需要恢复，但大规模系统中的高度并行恢复可以在短时间内恢复这些块，这要求在恢复协议期间进行快速调度。然而，实际的恢复往往需要2-4分钟，是理想恢复时间的2.35 ~ 4.70倍，这促使我们进行进一步的研究。

​ 观察3：前台流量短期内负载严重失衡

​ 我们分析的跟踪记录每15秒每个节点的前台带宽。为了了解前台流量是否平衡，我们计算每个时隙中前台带宽的变异系数（CoV，标准差作为平均值的百分比），这是衡量值变化的标准度量。然后在图1(c)和图1(d)中绘制不同时间段 CoV 的分布。如图所示，大部分时间段的 CoV 在0.4 - 0.6之间，这是非常显著的。有趣的是，如果我们以更粗的粒度（如1小时和1天）衡量这种不平衡，这种不平衡会变得更小。

​ 这样的结果表明，系统在长期内是相对负载均衡的，但在短期内更加不平衡，这给数据恢复带来了挑战：传统的负载均衡技术，如数据迁移，主要针对长期不平衡，因为它们不能经常运行；但数据恢复主要受短期不平衡的影响，因为它可以在几十秒到几百秒内完成。这个观察结果表明，我们的恢复协议必须考虑到这种短期的不平衡，而不依赖于负载平衡技术。

​ 观察4：一个给定节点上的块副本不均匀地分布在其他节点上

​ 为了理解给定节点上的块的副本如何在其他节点之间分布，我们定义 \(SC_i^j\) 为 \(node_i\) 和 \(node_j\) 所持有的块的大小，这表明如果 \(node_i\) 失败，在恢复过程中 \(node_j\) 可以作为源提供多少数据。

​ 我们首先抽样一个特定的 \(node_i=100\)。图1(e)显示了不同 \(j\) 值下 \(SC_{100}^j\)的分布。我们可以看到，分布的直方图符合钟形曲线：如果我们假设块的放置是随机的，这实际上是可以在数学上证明的（即中心极限定理）。为了理解整个集群中的这种不平衡，对于每个 \(node_i\)，我们计算所有 \(SC_i^j\) 值的 CoV，然后在图1(f)中绘制所有节点CoV的CDF。

​ 可以观察到，对于大部分节点，\(SC_i^j\) 的分布是不平衡的。为了理解这种不平衡是如何影响恢复的，我们使用盘古的随机节点选择策略（图1(g)）模拟节点100的故障，发现节点 \(J\) 和 \(SC_{100}^j\) 的输出恢复流量大小之间有很强的相关性。这意味着一个具有少量（很多）公共块的节点在恢复过程中只会做很少（很多）的工作，但是如果该节点有很多（很少）可用带宽，它将得不到充分利用（过载）。

​ 观察5：前台流量通常在最大带宽的14.4%范围内波动，但有时会发生巨大的变化

​ 图1(h) 显示了一个节点的前台流量在5小时内的变化情况。差带宽是两个相邻时隙中平均带宽利用率的差值。我们可以观察到，在95%以上的情况下（在图1(h)中的“p2.5”和“p97.5”之间），绝对增量带宽低于 36MB/s，这是最大带宽的14.4%（由于每个节点有两个 1Gb 网卡，所以为 250mb/s）。然而，在剩下的 5% 的情况下，增量带宽可以达到最大带宽的三分之二。尽管这种极端情况的百分比很小，但它们经常发生在恢复中，因为高度并行的恢复通常涉及许多节点。仿真结果表明，它们在恢复过程中会产生掉队现象，是恢复速度不理想的主要原因之一。

大禹的概述

​ 在本文的其余部分中，我们将一个数据块的重新复制称为“恢复任务”。大禹通过引入一个名为 ObServer 的集中调度程序，实现了快速的数据恢复和低应用干扰，该调度程序基于时点进行恢复任务调度。Dayu 假设所有的数据服务器定期向观察者报告他们的数据块放置和网络使用情况，所有的元数据服务器将恢复任务的信息发送给观察者。本文的其余部分给出了 ObServer 的调度算法，该算法决定了恢复任务的源、目的和带宽。为了实现高速、高质量的调度，大禹的关键思想是分批调度恢复任务，而不是将所有恢复任务一起调度。这种设计选择有以下几个原因：首先，每个节点通常涉及数十个恢复任务（由观察一得到），多批调度任务仍然允许每个节点充分参与每批任务，从而充分利用其可用带宽；其次，分批调度任务可以很自然地应对动态的前台流量和罕见的测量误差，因为大禹在观察到前台流量的任何变化时，都可以在下一批进行调整；最后，分批调度可以很自然地减少调度算法的计算开销，因为对于每批，算法只需要调度任务的一个子集。

​ 为了实现这个想法，如图2所示，大禹将整个恢复时间划分为多个固定长度的时间片（在本文中称为时隙）。在时隙开始时，obServer收集数据服务器的最新状态。使用获得的状态，obServer选择并调度该时隙中的恢复任务子集，包括那些在最后一个时隙中调度但尚未完成的恢复任务。为了充分利用可用带宽，大禹将多个时间段进行重叠，以便在n−1时间段结束前对n号槽位进行信息收集和任务调度。时间段的长度由底层存储系统收集和报告状态的频率决定。如2.1节所述，数据恢复的瓶颈不是终端主机的网卡就是机架交换机的网卡，为了简化描述，本文假设终端主机的网卡是瓶颈，可以很容易地扩展到支持瓶颈机架交换机。表1列出了本文使用的表示法。

3.1 目标

​ 大禹努力实现以下目标

• 目标1：尽可能多地利用可用带宽。这是一个自然的目标，以减少整体恢复时间。如果我们充分利用一个时隙中的可用带宽，在该时隙中可以复制的块的总大小(S)为： \[ S=min(∑_{i∈Nodes}B^i_{recover\_in} , ∑_{i∈Nodes} B^i_{recover\_out}) × T_{timeslot} \]

• 目标2：在目标时隙中完成尽可能多的任务。我们希望调度的任务能够在目标时间段内实际完成：否则，我们必须重新调度它们，这增加了计算开销。这个目标可能看起来和第一个目标相似，但它不是：第一个目标建议我们超额订阅网络带宽（即调度比带宽所能处理的更多的任务），这样，如果前台流量下降，我们仍然可以利用这些额外的可用带宽；然而，第二个目标建议我们少订阅网络带宽，这样即使前台流量增加，我们仍然可以完成预定的任务。因此，大禹不得不在这两个目标之间进行权衡。

• 目标3：最小化明显掉队的机会。由于我们无法准确预测未来的前台流量，因此不可避免地会出现掉队现象。我们更喜欢许多小的掉队者而不是一些重要的掉队者，因为许多小的掉队者可以被重新安排并并行执行，从而最小化恢复时间。但是，这个目标和第二个目标显然是矛盾的，所以大禹也需要权衡。

3.2 大禹算法概述

​ 为了实现这些目标，大禹整合了四种关键技术，通过基于我们观察的启发式和近似算法来增强现有算法：

• 一种贪婪算法，通过桶凸壳优化来选择每个恢复任务的源和目的地

• 基于启发式算法的节点优先级与少数公共块与失败节点，但高可用带宽

• 为每个任务分配带宽的迭代WSS算法

• 一种基于启发式的算法，以最小化重新调度掉队任务的代价

大禹

4.1 选择源和目的

​ 大余反复扫描所有任务，确定每个任务的源和目的，直到找到足够的任务来填充（公式2）。一个任务的候选源包括所有持有相应块副本的节点；任务的候选目的地包括不在其源的同一机架中的所有节点。为了实现第三节给出的目标，大禹采用了贪婪算法：

​ 对于每个任务，大禹在其候选源和目标中选择利用率最高的节点；

​ 如果大禹发现即使是最没有被充分利用的候选也会饱和，大禹就会跳过这个任务。我们需要回答的第一个问题是如何定量地度量节点的利用率。我们已经尝试几个选项,通过模拟,我们决定使用预期的任务完成 \(\frac{c_{in/out}}{B_{recover\_in/out}}\) (\(c_{in/out}\) 是传入/传出的总大小任务分配给该节点）作为指标来评估一个节点的利用率，因为这个指标达到前两个目标之间的平衡。

​ 因此，在为任务 t 选择源时，大禹扫描其所有候选节点，并选择 \(\frac{s_t+c_{out}}{B_{recover\_out}}\) 最小的节点作为源。这种扫描在计算上并不昂贵，因为大多数块有三个副本，其中一个已经丢失了。之后，Dayu会检查分配任务给源是否会使源饱和，即它的 \(\frac{s_t+c_{out}}{B_{recover\_out}} > T_{timeslot}\) ：如果是，Dayu将会丢弃任务t，因为这意味着在这个时间段没有办法完成任务。

​ 同样，当为任务 t 选择目的地时，大禹选择 \(\frac{s_t+c_{in}}{B_{recover\_in}}\) 最小的节点。但是，由于候选目的地的数量很大，简单地扫描所有候选目的地的计算量很大。更糟糕的是，贪心算法不能并行化，因为每次迭代都依赖于前一次迭代的结果。我们在一个3500节点的集群上的模拟表明，简单地扫描每个任务的所有候选目的地的速度只能达到每秒不到30000个任务。根据我们的统计，在一个时间段内，大余通常可以完成6万-15万项任务，这意味着单纯的扫描本身需要2-5秒，这并不理想。为了解决这个问题，我们结合了动态凸包优化来加速计算。

​ 凸包优化的形式化描述可以参考，这里我们给出了一个直观的描述。对于每个幸存的 \(node_i\)，我们在笛卡尔坐标系中绘制一个点\((B^i_{recover\_in},c^i_{in})\)，如图3(a)所示。然后，对于大小最大的task，我们在图3(a)中绘制另一个点\((0,−s_t)\)。然后，我们从 \((0,−s_t)\) 到彼此的点画一条线：由于每条线的斜率为\(\frac{c^i_{in}+s_t}{B^i_{recover\_in}}\)，为任务 t 找到目标节点等同于找到斜率最低的线。我们可以保持一个动态凸包来快速搜索斜率最低的直线。在二维空间中，凸壳就像一根橡皮筋，将所有的点紧紧地包裹起来，下面的凸壳就是这个凸壳的下部。

​ 我们可以保持一个动态凸包来快速搜索斜率最低的直线。在二维空间中，凸壳就像一根橡皮筋，将所有的点紧紧地包裹起来，下面的凸壳就是这个凸壳的下部。我们将下凸壳的点集称为 \(H\)（这里我们将 \(H\) 中的点连接在一起，形成图3(a)所示的下凸壳）。\(H\) 中的点是逆时针连接的。那么对于在集合 \(H\) 中有前导点和后继点的点 \(p_h\)，直线 \(p_{h−1}→p_h\) 的斜率必须小于或等于直线 \(p_h→p_{h+1}\) 的斜率。利用二分搜索的时间复杂度为 \(O(log|H|)\)，我们可以找到与点 \((0, −s_t)\) 的连接斜率最小的节点集 \(H\)。

​ 在大禹分配任务到 \(node_i\) 后，它的 \(c^i_{in}\) 增加 \(s_t\)。因此，大禹需要调整节点 \(i\) 的点以及下凸壳 \(H\)：当点 \(p_h\) 向上移动时，大禹识别原始 \(H\) 中 \(p_h\) 的前体 \(p_{h−1}\) 和后续 \(p_{h+1}\)，并扫描它们之间的所有点，以找到 \(H\) 的新成员。凸包优化将目标节点的扫描复杂度由线性降低为次线性，且不影响贪心算法的结果。

​ 我们进一步提出了一个近似解来减少下凸壳的候选集，从而提高了算法的速度。如图3(b)所示，我们将可用的传入带宽范围划分为多个相等的桶。如果 \(node_i\) 和 \(node_j\) 在同一个桶中，则认为它们具有近似相同的可用带宽，即 \(B^i_{recover\_in} ≈ B^j_{recover\_in}\)。不失一般性，我们设 \(c_i>c_j\)。那么，\(node_i\) 不可能是下凸壳的成员。因此，只有同一桶内的最低节点才能成为下凸壳的成员。所有这些最低的节点（图3(b)中的空心圆）形成一个简化的候选集，记为 \(C\)。我们可以用这个简化的候选集\(C\) 构造凸壳\(H\)，而不是从节点的全部集合。大禹给一个节点分配任务后，会对该节点的点和减少的候选集进行调整。

​ 桶的大小决定桶近似的还原程度。在我们的实验中，我们使用 1 MB/s 作为的桶大小，我们的模拟显示平均减少因子为 22.8，因此，大禹可以在一秒内完成约21万个块的源和目的地的选择，这比普通扫描快7倍。

​ 这样的桶近似当然会给贪心算法带来不准确性，但由于测量误差和前台流量的波动，这种不准确性已经存在。因此，只要桶的大小很小，我们的近似就不会显著增加这种不准确性。

4.2 未充分利用节点的优先级排序

​ 我们对贪婪算法的模拟揭示了与我们的观察3和4相同的问题：具有高可用带宽的节点，但只有少量可用块可能没有得到充分利用，这违背了我们的第一个目标。在本文的其余部分，我们称之为未充分就业节点。例如，假设节点A有一个可用的输出带宽 50MB/s，它可以是任务 1 和任务 2 的源；节点B的可用输出带宽为 60MB/s，可以作为任务 1-4 的源；所有任务的大小相同。在这个例子中，最佳的调度应该让A是任务1和2的源，而B是任务 3 和 4 的源。但是，如果贪心算法先扫描任务1，它会将任务1分配给节点B，因为此时B比A有更多可用带宽。

​ 这个观察结果表明，对于在未充分利用的节点中拥有副本的块，最好使用未充分利用的节点作为源。为了实现这个目标，我们结合了一个分布式驱动的优先排序策略：obServer首先根据可用的输出带宽降序排序所有节点，然后根据公共块的总大小升序排序所有节点。然后，obServer从这两个节点列表中分别选取第一个β（在我们的典型设置中为5%)节点组成两个集合，并通过计算这两个集合的交集得到未充分利用的节点集。接下来，observer选择在未充分利用的节点中具有副本的所有恢复任务，并将它们放入一个称为“优先队列”的队列中；theobserver把剩下的任务放到另一个叫做“正常队列”的队列中。

​ 我们修改了贪心算法(§4.1)，以结合这种启发式：观察者将首先扫描优先队列中的任务，并直接使用相应的未充分利用的服务器作为源，而不是使用最未充分利用的候选服务器。有两种极端情况：

• 一个优先级任务可能在多个未充分利用的服务器中拥有副本。在这种情况下，观察者选择其中最没有得到充分利用的一个
• 虽然很少，但有可能未充分就业的服务器是饱和的。在这种情况下，观察者将优先级排序的任务降级到正常队列中，这样以后我们仍然可以尝试它的非优先级候选任务

​ 开销：在搜索未充分利用的节点时，大禹维护两个堆，其键分别为可用的输出带宽和公共块的总大小，其值为节点的 id。obServer首先构建这两个堆，这是 \(O(n)\) 操作（n是节点数），然后从这两个堆中弹出 5% 的条目，每个弹出一个 \(O(logn)\) 操作。我们的实验表明，堆积10,000个条目，然后弹出其中的 5% 只需要几毫秒。

4.3 为每个任务分配带宽

​ 给定每个恢复任务的源和目的地，我们需要回答每个任务应该以多快的速度进行。一个简单的解决方案是使用 \(B_{recover\_in/out}\) 对一个节点内的所有任务设置一个粗粒度限制，并让它们竞争带宽。然而，我们的实验揭示了这种方法的两个问题：第一，当源的输出限制大于目的的输入限制时，这种方法可能会导致拥塞。虽然TCP最终可以解决这种拥塞，但它会导致数据包丢失，恢复速度变慢。

​ 其次，竞争可能会导致一个任务比其他任务明显慢，导致明显的掉队和违反我们的第三个目标。因此，在这一步中，大禹试图为一个时隙中的每个任务设置一个恒定的速率，以最大限度地利用带宽。回想一下，我们假设终端主机的网卡是瓶颈，所以这个步骤只考虑终端主机的带宽利用率。即便如此，这仍然是一个具有挑战性的问题，因为为一个任务分配带宽将消耗两边的带宽。

​ Dayu的解决方案是基于加权洗牌调度（WSS），这是一种成熟的网络调度算法，用于在MapReduce 中调度像数据洗牌这样的大数据流。WSS 的关键思想是，为了在同一时间完成所有的成对传输，它保证：

• 传输速率与每次传输的数据大小成比例
• 至少有一个链路被充分利用

​ 使用 WSS 时，只有瓶颈链接(相当少数)得到充分利用，而其他所有链接都有剩余的带宽。在我们的场景中，然而，WSS 并不理想：当考虑不可预测的增长前台流量,这可能会导致一个non-bottleneck链接成为瓶颈的一个时隙，WSS可能导致浪费带宽，因为大禹可以利用更多的带宽这个链接的开始。

​ 为此，大禹引入了一个迭代的 WSS 解决方案，为每个任务分配带宽。其核心思想是在不延迟瓶颈任务的情况下，尽早完成其他任务，从而减少其完成时间，提高带宽利用率。按照这个思路，如果运行一次 WSS 迭代后还有剩余带宽，大禹就会使用另一次 WSS 迭代来识别下一个瓶颈，并分配剩余带宽。

​ 具体来说，Dayu为每个节点维护剩余的传入和传出带宽 \(B^i_{remain\_in}\) 和 \(B^i_{remain\_out}\)，其初始值为 \(B^i_{recover\_in}\) 和 \(B^i_{recover\_out}\)。在每次迭代中，大余首先找到 \(\frac{c^i_{in}}{B^i_{remain\_in}}\) 或 \(\frac{c^i_{out}}{B^i_{remain\_out}}\) 最长的节点，记为 \(T^*\)：相应的任务是瓶颈。然后，Dayu为每个任务分配 \(T^*\) 带宽，表示为了最小化完成时间，必须为瓶颈任务分配一个加权的公平带宽份额，使份额的权重与 \(s_t\) 成比例。之后，大禹对于每个\(node_i\) 将剩余带宽更新为 \(B^i_{remain\_in} −= \frac{c^i_{in}}{T^∗}\) 和 \(B^i_{remain\_out} −= \frac{c^i_{out}}{T^∗}\)，从它们对应的节点中移除瓶颈任务，并更新这些节点的 \(c_{in/out}\) 值。然后Dayu带着剩余的任务移动到下一个迭代，直到没有剩余的任务或者剩余的任务在分配的带宽下有一个可接受的传输时间（即小于或等于一个时隙的长度)。注意，如果一个任务经历多次迭代，那么它分配的带宽就是每次迭代中分配的带宽的总和。

​ 迭代 WSS 克服了 WSS 的缺点：由于迭代 WSS 试图分配所有的带宽，当有任务可以利用这些带宽时，系统不可能浪费带宽。

​ 我们的实验表明，对于一个3500节点的集群，每次迭代的时间最多为 15ms。由于动态凸包节点选择算法保持大多数节点的 \(\frac{c}{B}\) 值接近，迭代的 WSS 算法通常可以在5次迭代（即75ms)内完成，这是可以接受的。

4.4 重新调度分散任务

​ 由于工作量估计不准确、调度不佳、硬件异常等原因，在一个时隙结束时，有些任务无法完成。Dayu必须在下一个时隙重新调度这样的straggler任务，但不能简单地将其视为新任务，因为改变一个straggler任务的目的地需要从头重新传输任务，造成带宽的浪费。因此，如果可能的话，大禹应该避免改变目标——这是新任务没有的约束。

​ 识别掉队。回想一下，Dayu重叠了不同的时隙，因此当前时隙的调度阶段发生在最后一个时隙结束之前的一小段时间（表示为 \(T_{schedule}\) ）（图2）。因此，大禹必须预测哪些任务会成为掉队者：对于一个未完成的任务，大禹利用它目前的速度来估计它到最后一个时间段结束时的速度；如果在估计的速度下不能完成任务，大禹就把这些任务放到散列集合中。

​ 预测当然是不准确的。如果大禹将一个任务标记为straggler，而实际上该任务在最后一个时间隔完成，那么相应的节点就会简单地忽略大禹安排的新的传输计划。反之，如果未标记为straggler的任务在最后一个时间隔内无法完成，则相应的节点将无法得到新的传输计划，因此将坚持原来的计划。这两种情况都可能导致效率低，但由于 \(T_{schedule}\) 比 \(T_{timeslot}\) 小得多，这两种错误的识别在我们的实验中影响不大。

​ 调度掉队。首先，Dayu将检查散列集本身是否会使当前时隙中的某些节点饱和。如果有，那么obServer 迭代地从每个饱和的节点中驱逐完成最少的任务，直到它不再饱和。那些被驱逐的任务被分为两组：从它们的来源驱逐的任务和从它们的目的地驱逐的任务。它们以不同的方式重新安排。

• 对于第一组中的每一个straggler任务，观察者选择一个源和一个传输速率（与一个新任务相同)，同时保持目标不变，这意味着任务可以从当前的进度恢复。

• 对于第二组中的每个straggler任务，观察者将其重新调度为一个新任务。

​ 对于未驱逐的straggler任务，大禹保持其源和目的地不变，并使用迭代 WSS 算法分配带宽。他们可以从当前的进程中恢复。

​ 与将掉队者视为新任务相比，大禹试图减少重传数据，因为它只改变了第二组掉队者（相当少数)的目的地，并重传他们的数据。

​ 实验结果表明，与让失速者继续进行原计划相比，引入失速者调整使总体恢复速度提高了15.6%。还应该注意的是，如何检测和报告慢硬件是一个正交问题[25-27]。大禹假设系统有一些机制来测量和报告每个节点的实际带宽。

评估

我们的评估试图回答以下问题：

1. 大禹多快可以完成一次典型的全节点恢复，大禹在后台和前台之间引入了多少干扰？——负面影响(§5.1)
2. 大禹能发展成更大的系统吗？—— 可扩展性 (§5.2)
3. 在大禹，每一项关键技术带来多少效益？(§5.3)
4. 参数的设置对大禹的性能有何影响？(§5.4)

实施

​ 我们通过修改盘古的MetaServers、RootServer 和 ChunkServers，并将大余的 ObServer 引入盘古，在盘古上实现大余，如图4所示。ObServer能够感知所有恢复任务的信息，以及RootServer提供的全局信息，比如每个 ChunkServer 上的块位置和网络利用率。盘古每15秒监视和报告ChunkServer 的状态，此实现的时隙长度设置为15秒。在盘古中检测到一个节点故障时，MetaServers 会将故障节点的所有数据块报告给观察者，观察者会安排如何重新复制这些数据块。然后，ObServer 指示 Chunkservers 执行恢复任务（即重新复制数据块)。最后，在恢复任务完成后，observer 更新 Metaservers 以反映新重新复制的块的位置。

试验设备

​ 我们已经在一个1000节点的集群上部署了基于盘古的大禹实现。每个节点有2个12核Intel E5-2630处理器、96GB DDR4内存、2个10Gbps网卡、10 或 112TB硬盘和Linux 3.10.0。由于我们的跟踪是从具有1Gbps网卡的集群中收集的，但是我们的测试床配备了10Gbps网卡，所以我们在测试床中添加了流量控制，以便每个网卡只能使用1Gbps带宽。我们还搭建了一个模拟环境，在3500个节点以上的规模下测试大禹。我们在具有两个16核Intel E5-2620处理器、64GB DDR4内存和Linux 3.10.0的服务器上运行模拟。

方法

​ 对于真实系统上的实验，我们通过关闭一个 ChunkServers 来触发数据恢复。当执行恢复时，我们回放从真实集群系统收集的跟踪(§2.2)。由于我们的测试集群小于跟踪所来自的集群，我们通过调整或重定向一些请求来重塑跟踪以适应集群大小，同时保持读和写的比例、每个节点上的压力以及节点之间的不平衡程度。我们记录恢复时间以及前台和恢复流量之间的干扰，这是通过比较有和没有恢复流量的前台请求的p90延迟（即90%的尾部延迟）来测量的

​ 在仿真实验中，我们通过将chunk信息发送给Dayu来模拟chunkserver的故障。因为我们没有实际运行系统，所以我们需要模拟前台和恢复流量之间的干扰。由于系统的规模，请求级仿真需要很长时间，所以我们使用流级仿真，如[29,30]。它模拟每个链路的带宽利用率，并根据前台和恢复流量信息定期更新利用率。我们将干扰因子定义为过载流量大小与链路带宽的比值，如下所示： \[ B^i_{overload} = max(B^i_{recover}+B^i_{foreground} −75\%×B^i_{total},0) \]

\[ F_{interference} = \frac{∑_{i∈Nodes}B^i_{overload}}{∑_{i∈Nodes}B^i_{total}} \]

​ 我们定义这样一个干扰因素的原因是，如果总带宽利用率超过NIC带宽的75%，前台延迟将显著增加。为了定量地理解这个模拟的干扰因素，我们将它们映射到现实世界实验中的p90延迟(§5.4)：简短的结论是，小于2%的干扰因素表示非常小的干扰，接近或大于6.5%的干扰因素表示非常大的干扰。

​ 在模拟实验中，我们随机选取50对失效节点及其失效时间，模拟了50种失效案例。对于每个算法，我们在所有50种情况下模拟其性能，并报告其平均性能数。

​ 在我们接下来的实验中，图5展示了来自真实系统的结果，其他的图展示了来自模拟实验的结果。

比较

​ 在真实系统上的实验中，我们将大余复制策略与盘古原始的复制策略进行了比较。盘古原始复制策略采用磁盘利用率感知的随机数据放置和静态速率控制。我们使用三种配置spangui -slow（将恢复流量限制为30MB/s，这是生产系统中的默认配置)、Pangumid（90MB/s）和 Pangu -fast （150MB/s）作为基线。

​ 在仿真实验中，我们比较了大余与先进系统(表2)中使用的不同调度算法，但MCMF除外，因为它的优化求解器不是开源的。为了公平起见，我们保留了大禹的节点优先排序和散差调整部分，并插入了不同的节点选择和带宽分配算法。

​ 具体来说，在选择恢复任务的目的地时，我们将大禹的桶动态凸壳算法（C）与以下两种算法进行了比较：

• Random（R），随机选择一个节点作为传输源和目的地；
• 双随机最佳（Best-of-two-random, B2R），首先随机选择两个 chunkserver，然后选择负载较轻的一个作为源或目的地；
• 加权随机（Weighted random, WR），以可用带宽作为权值，随机选择节点；
• Greedy1（G1），它扫描所有的候选 ChunkServers，然后在我们的场景中找到具有minimalc B.5 的 Greedy2（G2），它通过维护一个红黑树来选择负载最轻的 ChunkServer。

​ 所有贪心算法，包括Dayu，都是使用单个线程执行的；所有基于随机的算法都使用16个线程执行。注意，尽管随机算法可以通过分布来达到更高的速度，但在我们的实验中，我们发现它们的速度并不是瓶颈。我们还使用最先进的 MILP 求解器 Gurobi 测试了 MILP 算法，但发现它只能完成小规模集群的计算；对于一个3500节点且只有2000个任务的集群，它在125秒后无法完成计算，因此我们不报告其结果。当确定每个任务的速率时，我们将Dayu的迭代 WSS（W）与基于期限的分配（DA）进行比较，DA分配一个时间间隔任务的速率，以便一个任务可以在一个时间间隔内完成。

5.1 整体性能

​ 对现实世界系统的评估。图5显示了恢复期间前台请求的恢复时间和p90延迟。在这个测试中，我们关闭一个服务器以创建15TB的数据来恢复，大约有990个幸存的 ChunkServer负责恢复。为了比较，我们在图5中添加了一个“理想”条目，它估计了假设所有可用带宽（α=75%）都可以利用的最佳恢复时间，并且不引入对前台流量的干扰（即前台延迟与没有恢复的延迟相同）。

​ 从图中可以看出，大余达到了接近最佳的恢复速度，且干扰小。首先，大宇正在接近理想的恢复速度，因为它的恢复时间比“理想”长1.19倍：分别比 Pangu-slow （默认）和 Pangu-mid 配置快2.96倍和1.24倍。与 Pangu-fast 配置相比，虽然大余恢复速度略慢（0.93倍），但对前台流量的干扰要小得多。考虑到恢复流量对前台流量的干扰，大宇的p90延迟仅比“理想”长1.04倍：Pangu-slow对p90延迟的干扰略低，与“理想”几乎相同；Pangu-mid 和 Pangu-fast 的p90延迟比“理想”高4.23-48.14倍，产生了不可接受的干扰。由于 Pangu-mid 和 Pangu-fast 对前台流量的干扰较大，在生产集群中很少使用。综上所述，与盘古不同设置相比，大宇的恢复时间和干扰都接近最优。

仿真系统的评估

​ 图6为仿真实验结果。再次，与其他算法相比，大禹在恢复速度和干扰之间取得了很好的平衡。

​ 在恢复速度方面，大宇将动态凸包节点选择与迭代WSS (C+W）相结合，在所有算法中恢复时间最短，比理想恢复时间长1.14倍。与其他算法相比，动态凸包节点选择算法恢复速度最快，比排名第二的G1算法快1.12倍。需要注意的是，虽然G1在这个实验中接近于Dayu，但由于它的高计算开销，它并不能很好地扩展(§5.2)。对于大余等基于贪心的算法，迭代WSS略快于基于期限的分配，因为迭代WSS可以在任务较少的情况下提前完成最后一个时隙，而迭代WSS必须在最后一个时隙的末尾完成任务。对于基于随机的算法，这种影响是不明确的，因为恢复速度主要取决于源和目的地的选择。

​ 在前台干扰方面，大宇有可以接受的干扰因子（回忆一下，2%的干扰因子很小，大于6.5%的干扰因子是不能接受的）。在相同的带宽分配策略下，大余的节点选择算法和其他贪心算法的干扰比随机算法略大，因为贪心算法通常会占用更多的估计可用带宽。当对前台流量的估计存在一定误差时，干扰会稍微大一些。在相同的节点选择算法下，迭代WSS始终比基于期限的分配(DA)带来更小的干扰。

5.2 可扩展性

​ 我们评估了大禹超过3500个节点的可扩展性。为了衡量不同算法的全部能力，我们假设有无限多个恢复任务，并模拟每个算法在20个时间段内可以恢复多少数据。由于模拟聚类的规模大于我们观察到的聚类，我们根据收集到的痕迹的统计数据随机生成块放置；我们从一个真实节点随机选取一个模拟节点的前台轨迹。

​ 如图7所示，大禹可以扩展到25000个节点，至此，大禹的性能比其他算法都要高。我们不测试更大的规模，因为它们离我们的目标（10K节点）太远了。除了大禹之外，所有随机算法的扩展性都很好，这是意料之中的，尽管它们的性能没有大禹那么好。G1不能扩展到超过5,000个节点，因为它的计算开销很大。需要注意的是，作为贪婪算法，大禹和G2最终会在某一点停止缩放，因为它们的集中计算，但至少对于我们现在和不久的将来的目标规模，仿真表明，大禹足够快，可以提供更好的质量。

5.3 个别技术效果

​ 我们进一步研究了在第4.2和4.4节中描述的未充分利用节点的优先排序(P)和重新调度掉队节点(A)的影响。我们使用带有凸包节点选择(C)和迭代WSS带宽分配(W)的Dayu作为基线(C+W)，扫描没有优先级的任务，并按照原计划执行掉队者(即P和A被禁用)。请注意，在此基线中，Dayu知道这些掉队者，并将使用它们的信息来安排当前时间段，但不会重新安排掉队者。图8显示了Dayu在P和A情况下的调度结果，从图中可以看出，对掉队者的再调度对性能非常敏感:与基线(C+W)相比，对掉队者(C+W+A)的再调度减少了15.6%的恢复时间，同时也减少了干扰。虽然未充分利用的节点的优先级在不重新调度掉队者的情况下效果有限，但当已经配置掉队者重新调度时，它将恢复速度加快7.2%(将“All”与C+W+A的情况进行比较)。

5.4关键参数的影响

​ 最后，我们测量了大禹的关键参数的影响。第一个是方程1中的 \(α\)，它控制恢复流量对前台流量的干扰。图9(a)绘制了在步长为5%时，\(α\) 的恢复时间和干扰因子从65%增加到85%。可以看出，\(α\) 越大，恢复时间越短，但干扰因子越大。在这张图中，我们进一步将这些模拟干扰因素映射到现实世界中的p90延迟，以便我们可以定量地了解模拟干扰因素的值。我们决定使用75%的 \(α\) 值主要是基于这些p90潜伏期的现实世界的实验：当 \(α=75%\) 时，Dayu达到接近最佳的恢复时间和p90潜伏期(§5.1)；当 \(α=80%\) 时，尽管Dayu将恢复时间减少了9.1%，但它几乎将前台流量的p90延迟提高了三倍。

​ 下一个参数 \(β\) 表示在 Section4.2 中选择未充分利用的 ChunkServers 时，从两个排序列表中选择的节点的比例。我们将 \(β\) 由0%变为10%，步长为2.5%。如图9(b)所示，\(β\) 值对干扰因子的影响不显著，当 \(β\) 值为5%时恢复时间最短，这也是大宇将 \(β\) 值设为5%的原因。

​ 另一个重要的参数是时隙的长度(时间间隔)，但由于这个参数影响盘古的总体开销，我们不被允许在生产系统中更改它，因此我们无法记录和分析不同时隙的跟踪。总的来说，更短的时间间隔会让大宇受益，因为它可以更快地对前台波动做出反应，但会增加盘古的开销。