原文：Improving MapReduce Performance in Heterogeneous Environments
TL;DR
这篇文章讲的是如何优化Hadoop在异构环境下的任务调度性能。
任务调度的关键在于如何让长尾任务尽快完成。MapReduce会在最后阶段冗余运行长尾任务，Google的数据显示这么做能提升44%的任务响应速度。
Hadoop的调度策略是冗余运行最慢的任务，而这篇文章提出的LATE（Longest Approximate Time to End)策略则是找最可能最慢结束的任务。在异构环境下LATE可以让任务响应速度达到Hadoop原有策略的2倍。
Hadoop的探测运行机制
Hadoop会给每个任务打一个0-1的分。map任务的分数就是它读取的input file的比例。reduce任务的分数分为三部分：copy、sort、reduce，每部分占1/3，乘上各自完成比例，最后累加起来。
之后Hadoop会统计所有任务的平均分，小于这个平均分减一个阈值（默认0.2）的任务会被认为是慢任务，调度器同时最多探测运行一个慢任务。同构环境中任务通常是一波一波开始结束的，因此这种调度策略运行结果很好。
但它做了几个假设：
- 各节点执行速度差不多。
- 任务的分数随运行时间线性增长。
- 在空闲的节点上启动一个探测任务是没有开销的。
- 任务的分数就代表着它的完成度，尤其对于reduce任务，它的copy、sort、reduce三阶段工作量是相同的。
- 任务倾向于一波一波结束，因此分数低的任务很可能是慢任务。
- 同类型（map或reduce）的任务间工作量差不多。
异构环境下1和2不一定成立，即使是同构环境下3、4、5也不一定成立，还会拖慢Hadoop，Yahoo因此就在某些任务上关掉了探测执行。Facebook不对reduce任务启用探测执行。
3在资源共享情况下不成立，不同任务间可能竞争网络和磁盘，且如果同时有多个作业执行，作业之间也会有资源竞争。
4的问题是reduce任务的不同阶段工作量往往差别很大，典型的MapReduce任务的copy阶段工作量最大，因为它需要所有map任务的输出。可能出现的场景，30%的reduce任务完成了copy后迅速完成了后2阶段，分数从1/3直接变成了1，此时平均分是0.53，所有其它reduce任务都落后于平均分0.2，都变成了慢任务。实际场景中可以有80%的reduce任务被探测运行了。
5的问题是分数低的任务可能刚刚启动。
6取决于任务切分策略，理想情况下是的，但即使工作量分配不均匀，只要能找准慢任务，多探测运行几个慢任务也不坏。
最后，0.2的阈值意味着只要分数过了0.8的任务都不会被认为是慢任务。
异构环境
- 大型数据中心的机器难以保证配置相同（逐次更新换代）。
- 软硬件问题导致不同机器执行速度不同。
- 虚拟化。
LATE
LATE仍然统计各任务的分数，之后计算得到速度progress rate = progress score / T（T是任务已运行时间）和完成所需时间(1 - progress score) / progress rate。
LATE还会统计各节点的分数（节点上所有运行过的任务的分数之和），从而找出慢节点，避免调度探测任务到这些慢节点上。
LATE有两个关键参数：
- SpeculativeCap，同时最多有多少个探测任务运行。
- SlowTaskThreshold，速度慢于此值的任务才是慢任务。
LATE会拒绝分配探测任务给慢节点，并在适当时候找出可能最晚结束的任务分配给快节点探测运行。
LATE分配探测的map任务时不考虑局部性，作者假设map阶段正常的任务都是读本地盘的，这些探测任务的网络竞争应该很小。
这种策略可能导致的一个问题：任务A的分数更高，但进入了运行较慢的阶段，任务B还没进入这个阶段，分数更低但速度更快，按前面的公式任务B会先执行完。但我们知道B到了下一阶段也会慢下来。这篇文章没有考虑解决这个问题。
想要解决这一问题可能需要历史统计数据。
反过来，如果后面阶段快于前面阶段则没有问题。