2015年6月4日
第13卷，第5期

Hadoop 超线性可扩展性

并行性能的永动机

Neil Gunther，性能动力学
Paul Puglia
Kristofer Tomasette，康卡斯特

“我们经常看到超过 100% 的加速效率！” 这是在一次关于如何用加速比指标量化计算机系统可扩展性的演示中，软件工程师对“你不可能拥有超过 100% 的任何东西”这一善意提醒的反驳。但这只是软件工程师们的第一轮攻势，在随后的不同场合，这种反驳似乎变成了一种合唱，不仅超线性加速是常见的现象，而且过去 20 年来用于量化可扩展性的模型——USL（通用可扩展性定律）——在应用于超线性加速数据时也失效了。

实际上，超线性加速是一种真实存在且可测量的现象，随着新的应用程序部署到分布式架构上，预计在实践中会越来越常见。然而，正如本文使用 Hadoop MapReduce 所展示的那样，USL 不仅能够以一种令人惊讶的简单方式容纳超线性加速，而且还揭示了超线性，尽管诱人，但与永动机一样虚幻。

为了详细说明，图 1 从概念上展示了线性加速（虚线）是您在扩展应用程序时通常可以期望达到的最佳效果。线性意味着您的容量投入得到了等值的回报，因为可用容量以 100% 的效率被消耗。然而，更常见的是，部分容量被各种形式的开销（红色区域）消耗。这对应于应用程序可用容量的不断增长的损失，因此加速以亚线性的方式扩展（红色曲线）。另一方面，超线性加速（蓝色曲线）似乎来自某种隐藏的容量提升（绿色区域）。

超线性是真正可测量的效果^{4,12,14,21,22,23,24,25}，因此，为了在为可扩展性调整分布式系统大小时解决它，理解它究竟代表什么非常重要。据我们所知，以前没有人这样做过。

尽管可测量性是毋庸置疑的，但超线性让人联想到永动机的说法。永动机之所以吸引人，是因为它被认为能够产生比消耗更多的工作或能量²⁶。在计算机性能方面，超线性等同于加速比超过了可用于支持它的计算机容量。对于本次讨论更重要的是，当涉及到永动机时，困难的部分不是决定该说法是否违反了能量守恒定律；困难的部分是调试机器以找出逻辑上的缺陷。有时，这种努力甚至可能被证明是致命的⁵。

如果初步看来，超线性类似于永动机，那么为什么一些软件工程师会宣称它的普遍存在，而不是对其进行调试呢？这种兴高采烈来自于对性能数据的过度信任。公平地说，这种错位的信任很可能源于性能数据的呈现方式，没有任何测量误差的指示。我们所知的任何开源或商业性能工具都没有显示测量误差，即使所有测量都包含误差。简而言之，所有测量在定义上都是“错误”的：唯一的问题是，您可以容忍多少“错误”？如果不量化测量误差，就无法回答这个问题。（本文稍后，表 2 量化了 Hadoop 的测量误差。）

除了确定测量误差之外，所有性能数据都应在验证方法的背景下进行评估。一种这样的方法是性能模型。在超线性加速的背景下，USL 以一种相对简单的方式履行了这一角色^{6,7,8,9,10,19,20}。下一节将介绍 USL 性能模型，为将其应用于超线性数据做准备。在附录 A 中，我们还展示了 USL 如何用于验证具有更正统可扩展性特征的应用程序。

通用可扩展性模型

为了更正式地量化可扩展性，我们首先在公式 1 中定义经验加速比指标

其中 Tp 是在 p = 1, 2, 3, ... 处理器或集群节点上测量的运行时¹⁴。由于多节点运行时 T_p 预计会比单节点运行时 T₁ 短，因此加速比通常是 p 的凹离散函数。可以识别出以下特殊情况。

• 线性加速。 如果对于每个集群配置 T_p = T₁ / p，则加速比将分别为每个 p 具有值 S_p = 1, 2, 3, ...。加速比函数表现出线性可扩展性（图 1 中的虚线）。

• 亚线性加速。 如果对于每个集群配置 T_p > T₁ / p，则连续的加速比值将低于图 1 中的线性可扩展性界限——换句话说，亚线性加速（红色曲线）。例如，如果 p = 2 且 T₂ = 3 T₁ / 4,，则 S₂ = 1.33。由于这小于 S₂ = 2，因此加速比是亚线性的。红色曲线是在单体和分布式系统上观察到的最常见的可扩展性形式。

• 超线性加速。 如果 T_p < T₁ / p，则连续的加速比值将高于线性界限，如图 1 中的蓝色曲线所示——换句话说，超线性加速。例如，如果 p = 2 且 T₂ = T₁ / 3，则 S₂ = 3，这大于线性加速。

重要的是要注意，公式 1 中加速比的定义是基于测量值，而不是理论值。任何计算机系统的可扩展性都可以通过将测量的加速比与以下部分中定义的理论预期加速比进行比较来验证。

可扩展性的组成部分

可扩展性，作为计算机硬件和软件的聚合，可以被认为是几个物理因素的结果

• 理想的并行性或最大并发性

• 共享资源的争用

• 主要瓶颈资源导致的饱和

• 非本地资源之间的数据交换，以达到一致性或数据相干性

这尚未考虑超线性。图 2 以示意图方式显示了这些因素中的每一个对可扩展性的影响，由公式 1 中的加速比指标衡量。

这些扩展效应中的每一个都可以表示为分析性能模型 USL 中的单独项^8,9,19。理论加速比在公式 2 中显示为

其中系数 σ 代表系统中的争用程度，系数 κ 代表分布式数据中相干性的缺乏。

公式 2 中的争用项随集群节点数 p 线性增长，因为它代表了等待共享资源的成本，例如消息排队。相干性项随 p 二次增长，因为它代表了通过分布式资源（例如，处理器缓存）之间的成对交换使分布式数据一致（或相干）的成本。

解释系数

如果公式 2 中系数 σ 和 κ 都为零，则加速比将简单地简化为 S_p = p，这对应于图 2a。如果 σ 非零，即使在节点配置相对较小时，加速比也开始偏离线性，如图 2b 所示。随着节点数量的持续增长，加速比接近上限 S_ceiling = 1/σ，如图 2c 中的水平虚线所示。图 2c 中的两个三角形表明这是一个收益递减的区域，因为两个三角形具有相同的宽度，但右侧三角形的垂直增益小于左侧三角形。

如果 κ 也非零，则加速比最终将像 1/p 一样向 x 轴方向退化。这意味着连续的可扩展性曲线必须通过最大值或峰值，如图 2d 所示。虽然两个三角形是全等的，但峰值右侧的三角形是反向的，表明斜率已变为负值。因此，这不仅是收益递减的区域，而且是负收益的区域。

从数学的角度来看，USL 是一个基于有理函数的参数模型⁹，并且可以想象继续在公式 2 的分母中添加连续的 p 多项式项，每个项都有其相关的系数。然而，对于非零的 κ 系数，最大值存在，并且通常很少有优点来分析地描述可扩展性如何在该点之后退化。首选目标是尽可能完全消除最大值——因此使用了“通用”一词。

本文通篇使用的中心思想是将公式 1 中基于测量的加速比定义与公式 2 中的性能模型定义相匹配。对于给定的节点配置 p，只有通过调整系数 σ 和 κ 的值才能实现这一点。在实践中，这是使用非线性统计回归来实现的^8,19,。

在本文末尾的附录 A 中，读者可以看到 USL 如何应用于不表现出超线性可扩展性的应用程序——例如 Varnish、Memcached 和 ZooKeeper。这些示例还说明了 USL 模型如何用于预测和解释。性能模型用于预测是广为人知和假设的；然而，解释通常不被认为是将性能模型应用于数据的原因，但这主要是我们在此处使用 USL 的方式。

云中的 Hadoop TeraSort

为了在受控环境中探索超线性，我们使用了众所周知的工作负载 TeraSort 基准测试^16,17，它在 Hadoop MapReduce 框架^3,27上运行。然而，我们没有使用物理集群，而是将其安装在 AWS（Amazon Web Services）上，以提供重新配置足够多节点的灵活性，以及以物理系统相应成本的一小部分并行运行多个实验的能力。

附录 B 提供了 Hadoop 框架及其术语²⁷的高级概述，重点介绍了与本文稍后的性能分析相关的组件。

值得注意的是，图 3 中描绘的 shuffle-exchange 过程涉及 Map 和 Reduce 任务之间的交互，这通常会导致数据在不同的物理节点上减少。由于这种交换发生在 MapReduce 对之间，因此它随集群节点数呈二次方扩展，这与公式 2 中的 USL 相干性项 p(p - 1) 完全对应（与图 2d 比较）。这一点对于稍后对超线性加速的性能分析非常重要。此外，尽管排序代表了最坏情况的 MapReduce 工作负载，但类似相干性阶段可能会以不同的量级发生在不同的 Hadoop 应用程序中。物理相干性效应的实际大小由 USL 分析 Hadoop 性能数据得出的系数 κ 的值决定。

在 AWS 上运行 TeraSort

TeraSort 是一种合成工作负载，最近被用于基准测试 Hadoop MapReduce 的性能，方法是测量排序 1 TB 随机生成数据所花费的时间——因此得名。输入数据由一个名为 TeraGen 的单独程序生成，由 100 字节的记录组成，前 10 个字节用作键。TeraSort 中的输出数据的复制因子为 1，而不是 Hadoop 中的默认因子 3。TeraSort 是探索超线性的一个不错的选择，因为在 Hadoop 集群上设置它的脚本很容易获得。

TeraSort 依赖于 MapReduce 框架在执行 Reduce 任务之前对 Map 任务的输出进行排序这一事实。在 Map 阶段，TeraSort 只是输出它从输入文件中读取的每个键值对。然后 MapReduce 框架对键进行排序（图 3 中的 Sort 框）。自定义分区算法将键分解为排序的子集（图 3 中的 Partition 框）。每个分区都分配给一个 Reduce 任务，然后 shuffle-exchange 过程将分配给给定 Reduce 任务的所有分区收集到其 Input 框中（如图 3 所示）。Reduce 任务将其结果（图 3 中的 Output 框）写入 HDFS（Hadoop 分布式文件系统）目录。这确保了该目录中的文件，总体而言，是完全有序的。

重要的是要强调，这里的目标是使用 TeraSort 检查超线性加速的现象，而不是调整集群以产生最短的运行时间，正如竞争性基准测试所要求的那样^16,17,。

为了保持运行多个实验的时间和成本可控，我们将 TeraGen 生成的数据量限制为仅 100 GB，并将 Amazon EC2（Elastic Compute Cloud）配置限制为少于 200 个节点。这种选择模拟了实践中可能看到的典型配置。表 1 总结了用于我们的 Hadoop 测量的特定 EC2 集群配置。它们使用本地实例存储，而不是 Elastic Block 存储。

EC2 实例类型 m2.2xlarge 和 c1.xlarge 的区别在于前者具有五倍的内存，但只有一个硬盘，一半的内核数量和更高的网络延迟，而后者有四个硬盘和更低的网络延迟。我们没有遵循晦涩的 Amazon 实例类型命名法，而是分别使用更具描述性的名称 BigMem 和 BigDisk（见表 1）来指代 m2.2xlarge 和 c1.xlarge，以强调关键的容量差异，这将对稍后的性能分析非常重要。

Amazon EC2 支持快速且廉价地配置具有各种实例类型和大小的集群，例如表 1 中的那些。我们需要一种方法来引导 EC2 集群，安装 Hadoop，准备和运行 TeraSort，以及收集性能指标。我们还希望以易于重复的方式操作参数，例如集群大小和实例类型。这是通过 Apache Whirr¹ 和一些自定义 bash 脚本完成的。

Whirr 是一组用于运行云服务的 Java 库。由于它支持 Amazon EC2，因此是自然的选择。我们配置 Whirr 创建一个由运行 Linux CentOS 5.4 的 EC2 实例组成的集群，并安装了 Cloudera CDH 4.7.0 发行版的 Hadoop 1.0³。该发行版中包含 Hadoop-examples.jar 文件，其中包含 TeraGen 数据生成和 TeraSort MapReduce 作业的代码。Whirr 可以从属性文件中读取所需的配置，也可以从命令行传递属性。这允许永久存储不更改的参数（例如，操作系统版本和 Amazon 凭据）。然后，我们可以将集群大小和实例作为命令行参数进行操作。

收集了三组指标

• TeraSort 作业的经过时间（不包括 TeraGen 作业）

• Hadoop 生成的作业数据文件

• Linux 性能指标

其中，最重要的是 TeraSort 作业的经过时间，它使用 Posix 时间戳以毫秒为单位记录（因为 EC2 硬件支持它），通过 shell 命令

BEFORE_SORT='date +%s%3N' hadoop jar $HADOOP_MAPRED_HOME/hadoop-examples.jar terasort /user/hduser/terasort-input/user/hduser/terasort-output AFTER_SORT='date +%s%3N' SORT_TIME='expr $AFTER_SORT -$BEFORE_SORT' echo "$CLUSTER_SIZE, $SORT_TIME" >> sort_time

运行时性能指标，例如内存使用率、磁盘 I/O 指标和处理器利用率，是使用常驻 Linux 性能工具 uptime、vmstat 和 iostat 为每个 EC2 节点实例捕获的。性能数据被解析，并作为逗号分隔值输出，每两秒附加到一个文件。

永动机的迹象

图 4 显示了 TeraSort 加速比数据（点）以及 USL 预测的可扩展性曲线（蓝色）。线性界限（虚线）已包含在内以供参考。数据全部位于或高于线性界限的事实立即提供了视觉证据，表明加速比确实是超线性的。USL 回归曲线不是线性拟合²³，而是在原点附近表现出凸趋势，这与图 1 中的通用超线性轮廓一致。

USL 回归分析完全出乎意料的结果是，争用系数发展为负值，σ = -0.0288，这与附录 A 中 Varnish 和 Memcached 等应用程序看到的传统正值不同。它也（表面上）与关于 σ 和 κ 都必须为正值才能保持物理一致性的断言相矛盾^{8 §5.5.4}。这很可能是本文开头提出的批评的来源，即 USL 在应用于超线性加速数据时失败了。

如前所述，σ 的正值与共享资源的争用有关。例如，执行用户级任务的同一处理器可能还需要容纳系统级任务，例如 I/O 请求。从这个意义上讲，相同的处理器容量可能被应用程序本身以外的工作消耗。因此，应用程序需要更长的时间才能完成，并且吞吐量小于容量投入的预期线性回报。

这种容量消耗解释了图 2b 中的亚线性可扩展性组成部分。相反，σ 的负值可以被识别为某种容量提升，其来源必须确定。这种解释将在稍后解释。

此外，USL 回归分析产生的相干性系数为正值 κ = 0.000447。如图 2d 所示，这意味着加速比必须有一个峰值，USL 预测峰值为 S_max = 73.48，发生在 p = 48 个节点处。更重要的是，这也意味着可扩展性曲线必须穿过线性界限并进入图 5 所示的回报区域。在那里，您将为（显然）免费获得超线性体验付出代价。

USL 模型预测，从超线性区域到回报区域的这种交叉必须发生，原因如下。虽然 σ 的幅度很小，但它在公式 2 中乘以 (p - 1)。因此，随着节点数量的增加，公式 2 分母中的差值 1 - σ (p - 1) 变得越来越小，以至于 S_p 最终由分母中的二次相干性项 κ p (p - 1) 主导。

图 6 包括额外的加速比测量值（正方形）。拟合的 USL 系数现在明显小于图 4 中的系数。因此，最大加速比 S_max 比基于图 4 中数据预测的值高约 30%，现在发生在 p = 95 个节点处。测量的加速比值与原始 USL 预测不同，不是因为 USL 是错误的，而是因为现在可用的信息比以前更多。此外，这证实了 USL 的关键预测，即超线性加速将达到最大值，然后迅速下降到回报区域。

根据 USL 回归系数，可扩展性曲线预计在公式 3 中给出的 p_× 个节点处穿过线性界限

对于图 6 中的虚线曲线，交叉发生在 p_x = 65 个节点处，而对于实线曲线，交叉发生在 p_× = 99 个节点处。与 S_max 一样，两个 p_× 预测的差异来自两组测量中包含的信息量的差异。

追捕超线性 Snark

在针对 USL 模型验证 TeraSort 数据后，需要进行更深入的性能分析，以确定超线性的原因。让我们从更仔细地检查每个 EC2 集群配置的实际运行时测量值开始。

运行时数据分析

在典型的负载测试或性能测试环境中，图 9-11 等图中的每个负载点都代表单次运行的时间序列平均值。不进行多次运行的常见借口是缺乏时间，这更多地是对特定内部工程理念的谴责，而不是调度约束。更糟糕的是，无法从单次运行中确定测量误差。如果您不知道测量误差，您怎么知道何时出现问题？

为了对我们的运行时测量中的误差进行统计确定，我们对每个节点配置执行了十几次重复运行。从该样本大小中，可以基于标准误差或相对误差（r.e.）计算出不确定性的合理估计，后者更直观。

对于表 2 中每个运行时，± 符号之前的数字是样本均值，而 ± 符号之后的误差项来自样本方差。相对误差是标准误差与平均值的比率，以百分比表示。

从这种数值分析中立即明显的是，相对误差的显着变化，范围从 3%（名义值）到 9%（可能需要进一步关注）。测量误差的这种变化并不意味着测量技术不可靠；相反，这意味着运行时数据的离散度或方差更高，原因在本分析级别上无法辨别。

运行时变化的现象并非我们 EC2 测量的特有现象。Yahoo TeraSort 基准测试团队也注意到他们测量的执行时间存在显着变化，尽管他们没有量化这些变化：“虽然我主要自己使用了 910 个节点，但网络核心与另一个活跃的 2000 节点集群共享，因此时间变化很大，具体取决于其他活动。”¹⁶

Yahoo 团队的一些可变性来源可能与我们的不同（例如，大 10 倍的集群大小可能是 Yahoo 变化的一些原因）。“请注意，在任何大型集群和分布式应用程序中，都有很多移动部件，因此我们看到了执行时间的广泛变化。”¹⁷

一个令人惊讶的假设

Yahoo 基准测试团队使用的物理集群配置由具有两个四核 Xeon 处理器的节点组成（即，每个节点总共八个内核）和四个 SATA 磁盘¹⁷。这与表 1 中的 BigDisk EC2 配置非常相似。因此，我们在 BigDisk 集群上重复了 TeraSort 可扩展性测量。图 7 比较了 p = 2、3、5 和 10 集群的结果。

与图 4 一致，图 7a 中的 BigMem 加速比值是超线性的，而图 7b 中的 BigDisk 节点出乎意料地表现出线性或亚线性的加速比值。通过将每个集群节点的本地主轴数量从一个增加到四个，超线性效应基本上被消除了。换句话说，增加节点 I/O 带宽导致了违反直觉的结果，即可扩展性从超线性降级为亚线性。

为了解释为什么超线性效应减弱，我们通过识别 BigMem 和 BigDisk 配置之间的关键性能差异，提出了一个工作假设。

BigMem 具有更大的内存配置，这可能为 TeraSort 数据提供了更多的 CentOS 缓冲缓存，这可能是与前面描述的 USL 负争用系数相关的容量提升的来源。与集群大小成比例的内存增量增长是超线性加速的常见解释^4,14。然而，在 Hadoop-TeraSort 的情况下，增加内存大小可能不是容量提升的来源。

如果缓冲区缓存填充到需要写入磁盘的程度，则需要更长的时间，因为 BigMem 配置中每个节点只有一个本地磁盘。图 3 中的单磁盘 DataNode 意味着所有磁盘 I/O 都是串行的。从这个意义上讲，当磁盘写入（包括复制）发生时，TeraSort 是 I/O 绑定的——尤其是在单节点情况下。随着集群配置变得更大，这种潜在的 I/O 约束变得不那么严重，因为每个节点必须写入磁盘的数据量与节点数量成比例地减少。因此，连续的集群配置表现出的运行时比单节点情况短，这导致了图 7a 中显示的超线性加速值。

相反，虽然 BigDisk 配置每个节点的物理内存量较小，但每个 DataNode 有四个磁盘，这意味着每个节点都具有更大的磁盘带宽来容纳更多的并发 I/O。因此，TeraSort 不太可能变成 I/O 绑定的。由于没有潜在的单节点 I/O 约束，因此不可能存在任何容量提升。结果，加速比值更加正统，并落入图 7b 的亚线性区域。

请注意，由于 Yahoo 基准测试团队使用了每个节点四个 SATA 磁盘的集群配置，他们可能没有观察到任何超线性效应。此外，他们专注于测量基准测试竞赛的经过时间，而不是加速比，因此超线性只能作为执行时间 T_p 比 1/p 下降得更快才能观察到。

控制台堆栈跟踪

下一步是尝试根据在每次运行期间收集的 Hadoop 指标来验证 I/O 瓶颈假设。当 TeraSort 在某些 BigMem 配置上运行时，在与 Hadoop JobTracker 通信的 Hadoop JobClient 控制台中观察到任务失败（参见附录 B）。以下是失败任务状态的缩写形式，其中显示了显着的标识符，以粗体显示。

14/10/01 21:53:41 INFO mapred.JobClient: Task Id : attempt_201410011835_0002_r_000000_0, Status : FAILED java.io.IOException: All datanodes 10.16.132.16:50010 are bad. Aborting... ... at org.apache.hadoop.hdfs.DFSOutputStream$DataStreamer.run(DFSOutputStream.java:463)

由于 TeraSort 作业继续进行，并且所有任务最终都成功完成，因此我们最初忽略了这些失败报告。后来，考虑到早期的 I/O 瓶颈假设，我们意识到这些失败似乎仅在 Reduce 阶段发生。同时，当控制台中出现失败时，Reduce 任务的 %Complete 值立即降低。换句话说，Reduce 任务的进度变成了倒退。此外，鉴于上面堆栈跟踪中的失败涉及 Java 类 DFSOutputStream，我们推测错误发生在尝试写入 HDFS 时。这建议检查服务器端 Hadoop 日志，以确定 Reduce 失败与 HDFS 写入相关联的原因。

Hadoop 日志分析

在 Hadoop 集群日志中搜索最初在 JobClient 日志中看到的相同失败的 TASK ATTEMPT ID，揭示了相应的记录

ReduceAttempt TASK_TYPE="REDUCE" TASKID="task_201410011835_0002_r_000000" TASK_ATTEMPT_ID="attempt_201410011835_0002_r_000000_0" TASK_STATUS="FAILED" FINISH_TIME="1412214818818" HOSTNAME="ip-10-16-132-16.ec2.internal" ERROR="java.io.IOException: All datanodes 10.16.132.16:50010 are bad. Aborting ... ... at org.apache.hadoop.hdfs.DFSOutputStream$DataStreamer.run(DFSOutputStream.java:463)

此记录表明 Reduce 任务实际上在 Hadoop 集群上失败了，而不是在 JobClient 上失败。由于失败发生在 DFSOutputStream 的调用期间，因此进一步表明在物理写入数据到 HDFS 时存在问题。此外，日志中具有相同任务 ID 的后续记录，

ReduceAttempt TASK_TYPE="REDUCE" TASKID="task_201410011835_0002_r_000000 TASK_ATTEMPT_ID="attempt_201410011835_0002_r_000000_1" TASK_STATUS="SUCCESS"

具有更新的 TASK ATTEMPT ID（即，尾随 1 而不是尾随 0），该任务已成功。

总而言之，此日志分析表明，如果 Reduce 任务未能完成其当前到磁盘的写入操作，则必须通过重写相同的数据来重新开始，直到成功为止。实际上，可能存在多次失败和重试（参见表 3）。Reduce 重试导致的运行时潜在差异被前面提到的运行时测量中的变化所掩盖，运行时测量中的变化也在 10% 左右。

表 3 有 12 行，对应于 12 个 TeraSort 作业，每个作业都在其自己的 BigMem 单节点集群上运行。一组指示每次运行执行情况的指标存储在 Hadoop 作业历史日志中。其中最重要的指标是通过使用 Hadoop 日志工具解析日志来提取的¹³。

如前所述，第一列中的 840 个 Map 任务是由 TeraSort 作业将 100 (二进制) GB 的数据分区到 128 (十进制) MB 的 HDFS 块中决定的。没有发生 Map 失败。第四列显示，Reduce 任务的总数设置为集群节点数的 3 倍（在本例中为 p = 1）。第五列揭示，失败的 Reduce 任务数量在 0 到 4 个之间随机变化。相比之下，相应的 BigDisk 情况没有 Reduce 失败。最后一列中的作业运行时用于确定平均运行时。

对于单个 BigMem 节点，T₁ = 13057078.67 毫秒与表 2 中的数据一致。额外的统计分析揭示了 Reduce 任务重试次数与更长的运行时之间存在很强的相关性。如果平均单节点运行时 T₁ 长于连续的 p T_p 值，则根据本文前面定义的加速比，将是超线性的。

Reduce 失败的原因是什么？

表 3 中失败的 Reduce 数量表明，Reduce 任务中的写入失败会导致它重试写入操作——可能多次。此外，由于这些额外的重试，失败的 Reduce 任务往往会产生更长的运行时。唯一剩下的问题是，写入失败的根本原因是什么？我们已经知道，故障期间涉及到写入操作，这表明应该检查 HDFS 接口。

仔细审查早期失败的 Reduce 堆栈跟踪，可以发现以下几行，重要的关键词以粗体显示

ReduceAttempt TASK_TYPE="REDUCE" ... TASK_STATUS="FAILED" ... ERROR="java.io.IOException: All datanodes are bad. Aborting ... ... .setupPipelineForAppendOrRecovery(DFSOutputStream.java:1000)

“All datanodes are bad” Java IOException 意味着图 8 中的 HDFS DataNode 管道已达到某种状态，即 DFSOutputStream Java 类上的 setupPipelineForAppendOrRecovery 方法无法恢复写入操作，并且 Reduce 任务无法完成。

当管道平稳运行时，Reduce 任务会调用 HDFSClient，然后 HDFSClient 会启动 HDFS DataNode 管道的创建（参见图 8）。HDFSClient 打开一个 DFSOutputStream 并使其准备好写入（图 8 中的“1. Write”），方法是在 DataNode 上分配一个 HDFS 数据块。然后，DFSOutputStream 将数据流分解成更小的数据包。在将每个数据包传输到 DataNode 以进行写入之前（图 8 中的“2. Write packet”），它会将该数据包的副本推送到队列中。DFSOutputStream 将数据包保留在队列中，直到它收到来自每个 DataNode 的确认（图 8 中的“3. ACK packet”），表明写入操作已成功完成。

当抛出异常时（例如，在堆栈跟踪中），DFSOutputStream 会尝试通过重新处理数据包来补救这种情况，以完成 HDFS 写入操作。DFSOutputStream 最多可以进行比复制因子少一次的额外补救尝试。然而，在 TeraSort 的情况下，由于复制因子设置为 1，因此缺少单个 HDFS 数据包确认将导致整个 DFSOutputStream 写入操作失败。

DFSOutputStream 努力以不受阻碍的方式处理其数据，并假设 DataNode 将能够跟上并响应确认。但是，如果 DataNode 上的底层 I/O 子系统无法跟上这种需求，则未完成的数据包可能会长时间未被确认。由于在 TeraSort 的情况下只有一个复制因子，因此不进行补救。相反，DFSOutputStream 会立即将未完成的写入数据包视为 AWOL（擅离职守）。

DFSOutputStream 抛出一个 I/O 异常，该异常会传播回图 8 中的 Reduce 任务。由于 Reduce 任务不知道如何处理这个 I/O 异常，因此它以 TASK_STATUS="FAILED" 完成。MapReduce 框架最终将重试整个 Reduce 任务，可能不止一次（参见表 3），这将反映在拉伸的 T₁ 值中，而这最终是导致观察到的超线性加速比的原因。

为了简要说明 HDFS 数据包如何 AWOL，一种可能性是 TeraSort 尝试通过 32 GB 的缓冲区缓存写入 100 GB 的数据。前 32 GB 的数据可能非常快速地写入内存，而 CentOS 正在异步地将该数据写入磁盘。但是，如果 TeraSort 写入缓冲区缓存的速度快于将写入提交到磁盘的速度，则 CentOS 将耗尽缓冲区缓存。此时，写入变成同步的，这使得它们相对于内存操作而言速度似乎降低了几个数量级。如果由于较慢的同步写入导致太多 HDFS 数据包排队，则某些 HDFS 数据包可能会超时。

鉴于基于 AWOL HDFS 写入数据包的 Reduce 失败机制，我们可以将这种操作见解转化为构建一个简单的策略列表，以处理相关的重试和运行时拉伸

• 调整缓冲区缓存大小。

• 调整内核参数以提高 I/O 吞吐量。

• 重新配置 Hadoop 默认超时。

如果维护 BigMem 类型集群是由非工程要求（例如，预算限制）决定的，那么这些步骤中的任何一个都可能有助于减轻超线性效应。

结论

在 Amazon EC2 上运行 Hadoop TeraSort 时执行的大量受控测量暴露了超线性的根本原因，否则这些原因在实际应用中很难解决。将我们的加速比数据拟合到 USL 性能模型产生了负的争用系数 (σ < 0)，这是 BigMem 集群上存在超线性的明显迹象。

负 σ 的减法效应在凸超线性曲线中引入了一个拐点，导致它最终变成凹形，从而在方程 3 中的 p_× 处越过线性边界。在那一点上，Hadoop TeraSort 超线性可扩展性恢复为投资回报区域中的亚线性。集群大小 p_× 提供了缓解 BigMem 集群上超线性加速比所需的最小节点容量的估计值。

虽然超线性是一种可重复测量的现象，但就像永动机一样，它最终是一种性能幻觉。对于 BigMem 上的 TeraSort，明显的容量提升——由 USL 中的负 σ 识别——可以追溯到随着集群大小的增长，逐渐放松每个节点的潜在 I/O 带宽约束。这种 I/O 瓶颈导致 Reduce 任务中 HDFS 管道的随机故障。这导致 Hadoop 框架重新启动 Reduce 任务文件写入，从而延长了测得的运行时。如果运行时拉伸对于 T₁ 是最大的（在最简单的情况下），那么连续的加速比测量将是超线性的。增加每个节点的 I/O 带宽（就像我们在 BigDisk 集群中所做的那样）通过减少 T₁ 拉伸来减少或消除超线性加速比。

USL 分析表明，超线性可扩展性并非 TeraSort 在 Hadoop 上独有，而是可能出现在任何 MapReduce 应用程序中。据报道，超线性加速比也发生在关系数据库系统中。² 然而，对于高性能计算应用程序，超线性加速比可能具有与此处介绍的不同的原因。^4,14,22

抛开超线性不谈，对于许多读者来说，更重要的收获可能是以下几点。与大多数软件工程项目不同，Hadoop 应用程序只需要固定的开发工作量。一旦应用程序被证明可以在少量集群节点上工作，Hadoop 框架就可以将其扩展到任意数量的节点，而无需额外的努力。对于 MapReduce 应用程序，扩展可能更多地是由磁盘存储的需求驱动，而不是计算能力，因为数据量的增长需要更多的 Map 任务。不幸的是，扁平可扩展性 这个术语已被用于描述这种效应。²⁸

虽然扁平可扩展性可能是初始开发过程的合理假设，但它并不能保证在没有额外且可能不断增加的努力的情况下，性能目标（例如，批处理窗口、流量容量或服务级别目标）能够得到满足。扁平可扩展性原则背后的未声明的假设是 Hadoop 应用程序呈线性（图 2a）或接近线性（图 2b）扩展。然而，任何 shuffle-exchange 处理都将在可扩展性曲线中引起峰值（图 2d）。可以通过将 USL 应用于小集群测量来预测峰值出现的 Hadoop 集群大小。缓和该峰值所需的性能工程工作通常会远远超出扁平可扩展性假设（参见附录 A 中的 Memcached）。USL 为想要分析 Hadoop 可扩展性的软件工程师提供了一个有价值的工具。

致谢

我们感谢 Comcast 公司为获取本文中使用的 Hadoop 数据提供的支持。

附录 A：亚线性可扩展性示例

为了与本文中讨论的超线性可扩展性分析进行比较，本附录介绍了三个主题应用程序的 USL 分析，这些应用程序表现出正统的可扩展性：Varnish、Memcached 和 ZooKeeper。

Varnish 可扩展性

第一个示例量化了 Varnish HTTP 加速器的可扩展性。图 9a 中的加速比数据（点）来自 HTTP GET 操作。¹⁸ 它们非常引人注目地证实，Varnish 是一个罕见的应用程序示例，它表现出接近线性的可扩展性。

这里需要做一个警示性的说明。在整篇文章中，我们将加速比 S_p 视为 p（分布式集群节点或处理器的数量）的函数。在图 9 和稍后的图 10 中，p 代表进程的数量，而不是处理器的数量。收集数据的平台（例如，HTTP 服务器）对于所有加速比测量都具有固定数量的处理器。这是在 QA/负载测试环境中发现的典型情况。值得注意的是，方程 2 中的同一个 USL 容纳了两种观点。⁹

对 p ≤ 400 个进程的 Varnish 加速比数据进行 USL 回归分析（图 9a 中的红色曲线）得出的争用系数值为 σ = 0.000169。虽然它不是零，但它确实非常小，并且解释了接近线性的可扩展性，因为它来自于资源的最小共享（与图 2b 比较）。95% 的置信区间以蓝色显示。

同样，相干性系数值为 κ = 0，因此无法形成图 2d 中所示类型的最大值。虽然从图 9a 中的测量值中看不出来，但 USL 预测接近线性的可扩展性不能期望无限期地扩展，因为加速比的理论上限为 S_ceiling = 1/σ = 5917（未显示）。图 9b 中的红色曲线更明显地表明了这一点，其中图 9a 中的 USL 曲线已投影到 p = 4000 个进程。由于 USL 对 Varnish 数据的拟合产生了非常小的 σ 值和 κ 为零，因此测量值和模型是一致的，这提供了本文第一节中提到的类型的数据验证。

Memcached 可扩展性

Memcached¹¹ 提供了第二个也是更典型的正统可扩展性示例，Memcached 是旨在通过将对象作为键值对存储在内存中来减少后端数据库负载的缓存守护程序。加速比测量值（点）来自键值检索操作，如图 10 所示。同样，p 代表进程，而不是处理器。

将 USL 回归分析应用于数据验证了加速比的最大值出现在 Memcached 1.2.8 版本中大约六个线程进程处。图 10 中的 USL 模型（红色曲线）是对图 2d 中示意性描绘的缩放特性的经验性表达，其中两个系数 σ 和 κ 的值均不为零。

预测超过 p = 6 个线程的可扩展性意义不大。相反，激励应该是消除峰值，而不是更精确地表征它。对于 Memcached，第一步是根据 σ 和 κ 系数的回归值来解释峰值发生的位置。然后，该解释可能会为改善情况提供一些工程方面的见解。事实上，Sun Microsystems 在 Solaris SPARC 多核平台上为 Memcached 1.3.2 开发了一个软件补丁，将峰值移到了大约 p = 50 个线程。¹¹

Zookeeper 可扩展性

作为最后一个相当特殊的示例，USL 模型应用于图 11 中的 Apache ZooKeeper 可扩展性数据¹⁵。加速比测量值（点）基于读取和写入操作的混合。请注意，所有加速比数据不仅是亚线性的（即，在虚线指示的线性边界的右侧），而且还在以与纯粹的负可扩展性一致的方式递减（与图 2d 比较）。

在这种分布式协调应用程序中，必须在至少三个分布式服务器之间交换投票，以便确定多数。由于工作负载几乎完全由服务器对之间的数据交换组成，因此相干性惩罚非常高，系数为 κ = 0.1635，而争用系数 σ 相对较小。因此，USL 模型（虚线曲线）中出现了严重的峰值，最佳情况下的加速比数据从 USL 最大值的“下坡”侧开始（红色曲线）。换句话说，纯粹的逆行可扩展性对于 ZooKeeper 来说是最佳的。

这个例子有力地提醒我们，所有计算机系统性能都是关于权衡的。有时，最佳意味着在原本被认为是完全不利的约束下可以实现的最不坏 的情况。

附录 B：Hadoop 框架概述

Hadoop 框架旨在促进编写大规模、数据密集型、分布式应用程序，这些应用程序可以在商品硬件的多节点集群上以可靠、容错的方式运行。这是通过为应用程序开发人员提供两个编程库来实现的

• MapReduce：一个分布式处理库，使应用程序能够被编写成易于适应并行执行，方法是将整个作业分解为一组独立的任务。

• HDFS：一个分布式文件系统，允许数据存储在任何节点上，并可由 Hadoop 集群中的任何任务访问。

使用 MapReduce 库编写的应用程序组织为一组独立的任务，这些任务可以并行执行。这些任务分为两类

• Map 任务。Map 任务的功能是获取整个输入数据集的一个切片，并将其转换为键值对，在 MapReduce 的上下文中通常表示为 <key,value>。（参见图 3 的节点 1 中详细的 Map 任务数据流，其中 Map 任务示意性地表示为一个过程 Map(k,v)。）除了执行此转换之外，Map 还按键对数据进行排序，并存储已排序的 <k,v> 对象，以便可以轻松地与 Reduce 任务交换。

• Reduce 任务。Reduce 任务的功能是收集特定键的所有 <k,v> 对象，并将它们转换为新的 <k,v> 对象，其中键的值是特定键，而 v 的值是所有值的列表 [v1,v2, ...]，这些值是 <k, [v1,v2, ...]> 对象，其键是整个输入数据集中的特定键。（参见图 3 的节点 1 中详细的 Reduce 任务数据流。）

MapReduce 应用程序使用以下工作流程处理其输入数据集

1. 在启动时，应用程序为输入数据集的每个切片创建一个 Map 任务并进行调度，并创建用户定义的 Reduce 任务数量。

2. 然后，这些 Map 任务并行处理输入数据的每个切片，有效地对其进行排序和分区，形成一组文件，其中所有具有相等键值的 <k,v> 对象都分组在一起。

3. 一旦所有 Map 任务完成，就会向 Reduce 任务发出信号，开始读取分区，以转换和组合这些中间数据，形成新的 <k, [v1,v2,...]> 对象。这被称为shuffle exchange 过程，在图 3 中示意性地显示为跨越物理节点 1, 2, ..., p 的箭头。

为了方便以分布式方式运行应用程序，MapReduce 库提供了一个分布式执行服务器，该服务器由一个称为 JobTracker 的中央执行服务和多个称为 TaskTracker 的从属服务组成。²⁷

JobTracker 负责调度任务并将任务传输到驻留在每个集群节点上的 TaskTracker。JobTracker 的另一个功能是它可以检测和重启可能失败的任务。它为应用程序执行提供了一定程度的容错能力。用户通过 JobClient 组件（例如 TeraSort）与 Hadoop 框架交互，JobClient 组件提供 MapReduce 作业的监控和控制。

为了支持 MapReduce 任务的执行，Hadoop 框架包括 HDFS，HDFS 被实现为使用主从架构的存储集群。它为开发人员提供了一个可靠的分布式文件服务，允许 Hadoop 应用程序以高吞吐量向集群中固定大小的块（在 TeraSort³ 的情况下为 128 MB）读取和写入非常大的数据文件。HDFS 集群中的主节点是 NameNode，它负责管理客户端对文件的访问，以及通过将文件块映射到其存储位置来管理文件系统命名空间，该存储位置可以驻留在 DataNode 上（即，NameNode 的从属节点）。HDFS 的一个关键特性是其内置的节点或磁盘故障恢复能力，这是通过跨多个 DataNode 复制块来实现的。默认复制因子为 3，但对于 TeraSort 工作负载，此值设置为 1。

参考文献

1. Apache Whirr; https://whirr.apache.org。

2. Calvert, C., Kulkarni, D. 2009. Essential LINQ. Boston, MA: Pearson Education Inc.

3. Cloudera Hadoop; http://www.cloudera.com/content/cloudera/en/downloads/cdh/cdh-4-7-0.html。

4. Eijkhout, V. 2014. Introduction to high-performance scientific computing. Lulu.com。

5. Feynman, R. P. The Papp perpetual motion engine; http://hoaxes.org/comments/papparticle2.html。

6. Gunther, N. J. 1993. A simple capacity model of massively parallel transaction systems. In Proceedings of International Computer Measurement Group Conference; http://www.perfdynamics.com/Papers/njgCMG93.pdf。

7. Gunther, N. J. 2001. Performance and scalability models for a hypergrowth e-commerce Web site. In Performance Engineering, State of the Art and Current Trends. (Eds.) Dumke, R. R., Rautenstrauch, C., Schmietendorf, A., Scholz, A. Lecture Notes in Computer Science 2047: 267-282. Springer-Verlag。

8. Gunther, N. J. 2007. Guerrilla Capacity Planning: A Tactical Approach to Planning for Highly Scalable Applications and Services. Springer;
http://www.springer.com/computer/communication+networks/book/978-3-540-26138-4.

9. Gunther, N. J. 2008. A general theory of computational scalability based on rational functions; http://arxiv.org/abs/0808.1431。

10. Gunther, N. J. 2012. PostgreSQL scalability analysis deconstructed;
http://perfdynamics.blogspot.com/2012/04/postgresql-scalability-analysis.html.

11. Gunther, N. J., Subramanyam, S., Parvu, S. 2010. Hidden scalability gotchas in Memcached and friends. VELOCITY Web Performance and Operations Conference;
http://velocityconf.com/velocity2010/public/schedule/detail/13046.

12. Haas, R. 2011. Scalability, in graphical form, analyzed;
http://rhaas.blogspot.com/2011/09/scalability-in-graphical-form-analyzed.html.

13. Hadoop Log Tools; https://github.com/melrief/Hadoop-Log-Tools。

14. Hennessy, J. L., Patterson, D. A. 1996. Computer Architecture: A Quantitative Approach. Second edition. Waltham, MA: Morgan Kaufmann。

15. Hunt, P., Konar, M., Junqueira, F. P., Reed, B. 2010. ZooKeeper: Wait-free coordination for Internet-scale systems. In Proceedings of the Usenix Annual Technical Conference;
https://www.usenix.org/legacy/event/usenix10/tech/full_papers/Hunt.pdf.

16. O'Malley, O. 2008. TeraByte Sort on Apache Hadoop;
http://sortbenchmark.org/YahooHadoop.pdf.

17. O'Malley, O., Murthy, A. C. 2009. Winning a 60 second dash with a yellow elephant; http://sortbenchmark.org/Yahoo2009.pdf。

18. Parvu, S. 2012. Private communication.

19. Performance Dynamics Company. 2014. How to quantify scalability (including calculator tools);
http://www.perfdynamics.com/Manifesto/USLscalability.html.

20. Schwartz, B. 2011. Is VoltDB really as scalable as they claim? Percona MySQL Performance Blog;
http://www.percona.com/blog/2011/02/28/is-voltdb-really-as-scalable-as-they-claim/.

21. sFlow. 2010. SDN analytics and control using sFlow standard—Superlinear;
http://blog.sflow.com/2010/09/superlinear.html.

22. Stackoverflow. Where does superlinear speedup come from?;
http://stackoverflow.com/questions/4332967/where-does-super-linear-speedup-come-from.

23. Sun Fire X2270 M2 super-linear scaling of Hadoop TeraSort and CloudBurst benchmarks. 2010;
https://blogs.oracle.com/BestPerf/entry/20090920_x2270m2_hadoop.

24. Sutter, H. 2008. Going superlinear. Dr. Dobb's Journal 33(3);
http://www.drdobbs.com/cpp/going-superlinear/206100542.

25. Sutter, H. 2008. Super linearity and the bigger machine. Dr. Dobb's Journal 33(4);
http://www.drdobbs.com/parallel/super-linearity-and-the-bigger-machine/206903306.

26. TechCrunch. 2015. AuroraTek tried to pitch us a gadget that breaks the laws of physics at CES;
http://techcrunch.com/2015/01/08/auroratek-tried-to-pitch-us-a-gadget-that-breaks-the-laws-of-physics-at-ces/.

27. White, T. 2012. Hadoop: The Definitive Guide. Storage and Analysis at Internet Scale, 3rd edition. O'Reilly Media, Inc.

28. Yahoo! Hadoop Tutorial; https://developer.yahoo.com/hadoop/tutorial/module1.html#scalability。

喜欢还是讨厌？请告诉我们

[email protected]

Neil J. Gunther，理学硕士，哲学博士，是 Performance Dynamics (www.perfdynamics.com) 的研究员和教师，他在那里创建了 PDQ 开源性能分析器和 USL，并撰写了一些基于这两者的书籍。他是的高级会员，并于 2008 年获得 A.A. Michelson 奖。博客 http://perfdynamics.blogspot.com 更新不定，但推文 @DrQz 更频繁。

Paul Puglia (http://comcast.github.io/sirius/)，一个分布式跟踪库，以及几个中间件应用程序。

最初发表于 Queue vol. 13, no. 5—
在数字图书馆中评论这篇文章

更多相关文章

David Collier-Brown - 你对应用程序性能一窍不通
每当您遇到性能或容量规划问题时，您都不需要进行全面的基准测试。一个简单的测量将提供您系统的瓶颈点：这个示例程序在每个 CPU 每秒八个请求后会显着变慢。这通常足以告诉您最重要的事情：您是否会失败。

Peter Ward, Paul Wankadia, Kavita Guliani - 在 Google 重塑后端子集化
后端子集化对于降低成本非常有用，甚至对于在系统限制内运行可能是必要的。十多年来，Google 一直使用确定性子集化作为其默认后端子集化算法，但尽管此算法平衡了每个后端任务的连接数，但确定性子集化的连接流失率很高。我们在 Google 的目标是设计一种连接流失率降低的算法，该算法可以取代确定性子集化作为默认后端子集化算法。

Noor Mubeen - 工作负载频率缩放定律 - 推导和验证
本文介绍了与每个 DVFS 子系统级别的工作负载利用率缩放相关的方程。建立了频率、利用率和缩放因子（缩放因子本身随频率变化）之间的关系。事实证明，这些方程的验证非常棘手，因为工作负载固有的利用率也在治理样本的粒度上以看似未指定的方式变化。因此，应用了一种称为直方图脊线追踪的新颖方法。当将 DVFS 视为构建块时，量化缩放影响至关重要。典型应用包括 DVFS 调速器和/或其他影响系统利用率、功耗和性能的层。

Theo Schlossnagle - DevOps 世界中的监控
监控似乎非常令人不知所措。最重要的是要记住，完美永远不应该是更好的敌人。DevOps 使组织内部能够进行高度迭代的改进。如果您没有监控，请获取一些；获取任何东西。有总比没有好，如果您已经接受了 DevOps，那么您已经注册了随着时间的推移使其变得更好。