Hadoop系统背后的数学

原文地址: http://nathanmarz.com/blog/hadoop-mathematics/

我希望我在一年前就知道这些。现在，通过一些简单的数学我终于可以回答下面的问题：

• 当机器的处理能力加快一倍, 为什么整个系统运行的速度没有增加一倍?
• 如果故障率增加10%,为什么整体的运行时间增加了300%?
• 为了得到最优的性能和容错表现, 一个计算机群应该部署多少机器？

一个简单的数学公式可以巧妙的回答所有这些问题:

运行时间=系统开销/（1 - （1小时数据量的处理时间) ）

我们将在稍后证明这个等式。首先，让我们简要地讨论一下“Hadoop为基础的系统。(分布式系统)”¹ Hadoop的一个常规应用是处理一个连续输入的数据流。这种工作流运行在一个“while(true)”循环当中，每一次处理的数据是上一次的运行结果。

接下来的分析可以归纳为一个简单的例子。假设你有一个工作流程需要12小时运行，因此，它每运行一次需要处理数据12小时。现在让我们假设需要做一些额外的计算工作，估计将在现有的工作流上增加两小时处理时间。问题来了。整个系统的运行增加的时间可能会远远多于两小时。它可能会增加10个小时，几百个小时，或者可能失去控制并且每一轮运行越来越慢。

为啥呢？

关键是你将系统需要12小时处理的数据运行时间增加到了14小时。这意味着下一次运行的工作流程，将有14小时的数据需要处理。由于下一个迭代有更多的数据，将需要更长的时间运行。这意味着下一次迭代会有更多的数据，等等。

要确定怎么让运行稳定，让我们做一些简单的数学。首先，让我们写了一个系统运行一次的公式：

运行时间=系统开销+（单机处理1小时数据的运行时间）*（总数据量/单击处理1小时的数据量）

系统开销是指任何常数时间的消耗。例如，启动一个程序的开销。任何运行时间同数据量无关的开销将属于这个“系统开销”这个类别。

“单击处理1小时数据的运行时间”指的是系统中的动态处理数据时间 。这是处理的实际数据量花费的时间，去掉了固定的系统时间开销。如果每个小时数据在系统中需要运行半小时，这个值为0.5。如果每个小时数据需要运行两小时，这个值为2。

为了简洁，让我们重写上面的公式中使用的变量：

T = O + P * H

要确定系统的稳定运行时间，我们需要找出系统运行时间和需要处理的数据量之间的关系。为了做到这一点，我们只需假设T = H：

T = O + P * T
T = O /（1 - P）

这就是之前提到的公式。正如你所看到的，系统的运行时间同系统开销是线性相关的。所以，如果你能减少25％的系统开销，你的系统运行时间也将减少25％。然而，系统运行时间同动态处理时间”P”是非线性相关的。这方面的一个直接体会是，随着机器数量的增加, 系统性能提升效果是不断缩小的。

有了这个公式，我们可以回答所在本文开头提出的问题。让我们一个一个的解决他们：

当机器的处理能力加快一倍, 为什么整个系统运行的速度没有增加一倍?

机器加倍将减少你的“处理一个小时数据的时间”（P的50％）。2 3 整个系统的提升效果，完全依赖于增加机器前P的取值。让我们把增大机群大小前的系统运行时间称为“T1”，增加之后的称为“T2”。我们得到两个等式：

T1 = O /（1 - P）
T2 = O /（1 - P / 2）

T2 / T1表示的就是提升的效率, 新系统运行效率比旧系统提升的比例。于是有了：

T2 / T1 =（1 - P）/（1 - P / 2）
T2 / T1 = 1 - P /（2 - P）

通过公式我们得到如下图，x轴表示P, y轴表示加速的比例⁴：

该图说明了一切。如果您的P非常高，比如1小时数据需要需系统运行54分钟，那么机群加大一倍将导致新的运行时间为原运行时间的18%, 效率提高了82％！这是一个非常反直观的结果-我强烈建议读者仔细思考产生这样效果的原因。

如果你以前的P不高（如1小时数据系统只需运行6分钟），那么机群加大一倍对运行时间的影响几乎没有-只有约6％左右。这是有道理的，因为运行时占主导地位的是系统开销. 实际处理数据占总运行时间的比例非常小.

如果故障率增加10%,为什么整体的运行时间增加了300%?

这个问题说明了系统稳定性的重要性。在一个大的机器集群中，将会一直碰到各种机械故障，因此重要的是失败率峰值不会影响到系统核心任务的运行。对于这个问题的分析，看起来同上一个问题非常相似，但这个时候，我们在降低，而不是提高它的处理效率。10％的故障率意味着数据处理的时间增加了11%⁵。这意味着我们的“处理一个小时数据的时间” （P）将增加11％。和上一个问题一样，让我们把没有故障发生的运行时间称为T1, 而发生失败后运行时间称为T2：

T1 = O /（1 - P）
T2 = O /（1 - 1.11 * P）
T2 / T1 =（1 - P）/（1 - 1.11 * P）

我们得到下图：

正如你所看到的，系统机群的规模越小, 故障率对运行时间的影响越剧烈。因此，让系统的P保持在低水平非常重要。⁶

为了得到最优的性能和容错表现, 一个计算机群应该部署多少机器？

这是一个非常典型的成本效益分析实例。我们已经看到，通过增加机器机群的大小，提高系统效率的效果逐渐减小的，一旦P（“一小时数据的处理时间”）低于30分钟（0.5），增加机器获得性能提升将小于线性比例。⁸ 我们也看到保持P值在低水平是多重要，否则在故障率提升或者利用群集进行其他工作时可能会明显增加系统运行时间。因此，你需要为你的系统计算出公式中的数字，以确定最佳的机器数量。9 10