MapReduce工作原理与工作流程

MapReduce工作原理与工作流程

文章目录

• 一、背景
• 二、工作原理和流程
• • 2.1 核心函数 Map & Reduce
  • 2.2 流程
  • 2.3 任务调配
  • 2.4 容灾问题
  • • Worker Failure
    • Master Failure
    • 确定性
  • 2.5 效率提升
  • • Combiner
    • Reader
    • straggler
    • 本地调试
    • 状态监控

一、背景

在大型网站系统，尤其是搜索网站中，系统常常需要处理海量数据，譬如在我关于搜索引擎的博客中提到的倒排索引，TF-IDF矩阵，PageRank ，数据的量级通常是TB甚至PB级别的，单机无法在短时间完成任务。

博客传送门

• 搜索引擎（一）-- Vector Space Model 和 倒排索引
  
• 搜索引擎（三）-- PageRank和HITS算法

论文传送门

• MapReduce: Simplified Data Processing on Large Clusters

为了解决该问题，Google公司提出了一种面向大规模数据处理的并行计算模型和方法 MapReduce。

MapReduce 的开发和维护十分简单。系统原生支持并行（parallelization）、容灾（fault-tolerance）、存储（data distribution）和负载均衡（load balancing），使用者只需要设计开发Map函数和Reduce函数使得其符合业务逻辑即可。

与此同时，MapReduce 还提供了配套的监控系统，程序员可以观察到任务执行的情况和工作节点状态，这进一步优化了开发流程。

二、工作原理和流程 2.1 核心函数 Map & Reduce

MapReduce 的核心流程为 Map 函数和 Reduce 函数。下面我会用经典的统计词频为例解释这两个函数的作用。

Map 函数负责将输入的数据，通过一系列处理，转化为多个中间值键值对。

在统计词频的例子中，Map函数的作用是将各个单词的词频以 的形式输出，如文章片段 A 内容为 “aa bb aa”, 那么该片段经过Map函数处理后得到的中间结果为：" , "

Reduce 函数负责整合多个 Map 函数的输出，它根据键值和用户自定义逻辑聚合结果，然后将结果输出到文件系统中。

在统计词频的例子中，Reduce 函数的作用是将多个相同 word 的 count 累加，如A片段中单词 aa 的个数为2，在B片段中 aa 的词频为1，那么键值为 aa 的 Reduce 函数将得到词频之和 1 + 2 = 3 作为最终结果。

这里给出论文中的示例代码

map(String key, String value):
	// key: document name
	// value: document contents
	for each word w in value:
		EmitIntermediate(w, "1");
reduce(String key, Iterator values):
	// key: a word
	// values: a list of counts
	int result = 0;
	for each v in values:
		result += ParseInt(v);
	Emit(AsString(result));

2.2 流程

MapReduce 采用了 Master/Slave 架构，包含一个负责协调各节点的 Master 和多个工作机器 Worker。

流程如下：

1. 系统将输入文件分为 M M M 片， M M M 大小应远大于 Worker 数量，分片大小通常为16MB~64MB。
2. Master 节点将分片分发到各个 Worker 节点，Worker 节点执行相同的Map代码。最终 M M M 个输入会转化为 R R R 个中间结果。
3. Worker 执行完毕 Map 任务得到中间键值对，将键值对写入临时缓存。
4. 临时缓存中的 K/V 键值对会被定时写入磁盘，分为 R R R 堆，这些键值对的位置会被反馈到 Master 节点。
5. Master 节点将这些键值对的位置通知给各个 Reducer，Reducer 通过 RPC 进行读取，读取完毕后根据键值 Key 进行排序，如果内存不够，可能需要借助外部排序。
6. Reducer 对各个排序后的键值对结果进行遍历后，交给自定义Reducer函数进行处理，并将最终结果写入文件系统 （论文引用的是Google File System）。
7. Reducer 任务结束，状态置为 completed，并通知 Master 节点，最后 Master 节点通知应用程序任务完成。

一般来说，MapReduce 不仅只执行一次 Map 和 Reduce *** 作，而是一个链式的 workflow，即一个 Reduce 的结果，可以作为另一个 MapReduce 过程的输入。后续推出的 Spark 也是为了简化 MapReduce workflow 而开发的。

2.3 任务调配

Worker 节点一般有 idle，in-progress，completed 三种状态。Master 一般会将工作分配给 idle 的 Worker（为了节约带宽，Master 一般会倾向于把任务就近派发，将任务派发给距离最近的 idle 节点。），对于 in-progress 的 Reduce Worker，Master 会定期将键值对的位置信息推送给这些 Worker，而如果任务完成，Worker 会被标记为 completed。

2.4 容灾问题

一个健壮的分布式系统应该容许一小部分机器失灵，同时能继续进行工作。MapReduce 通过多种内部机制，对容灾问题交出了一份优雅的答卷。

Worker Failure

• 心跳：Master 节点定时对每个 Worker 节点发送 ping，如果 worker 没有回应或回应不正常，则认为节点失灵。失灵节点被发现后，所有 worker 节点都会被重置到 idle 状态，任务重新执行。
• Re-execute：如果 Map Worker 崩溃发生，即使状态为 completed 的节点也要 re-execute 所有任务。因为部分存在缓存的中间结果可能会丢失。而 completed Reducer 崩溃无需 re-execute，因为数据被持久化。在 Map Worker 崩溃情况下，所有 Reducer 都会收到崩溃节点 re-execute 的通知，如果有 Reducer 在读取某个宕机的 Worker 数据，收到通知后它会去读取另一个 re-execute Worker 的数据。

Master Failure

作为整个系统的灵魂（论文中用 conduit 这个词来形容，我觉得很形象），Master 挂了系统所有工作都执行不下去，所有 MapReduce 工作都将中断。

为了避免数据丢失，Master定期保存checkpoints，宕机重启后恢复工作状态，然后就可以继续工作了（恢复中MapReduce也是无法进行的）。

确定性

如果 Map 和 Reduce 函数都是确定性函数（即输入一致的情况输出也是一致的），MapReduce 能保证re-execute后最终结果是确定的。但如果 Map 和 Reduce 函数是不确定函数，最终函数本身就是不确定的，也不必关心最终结果的确定性了。

2.5 效率提升

在 Google 长期实践中，他们研发了不少可以改进效率的机制，这些机制值得我们学习。

Combiner

在某些场景下，一部分的热 key 值经常被各个 map 函数处理，如词频统计中的 “the”，几乎每个 worker 都会接收，而大量重复的 key 在网络中传输既浪费了网络带宽，也容易压倒 Reducer。对于这部分任务，MapReduce 提出使用一个可选的 Combiner 函数，在使用网络传输给 Reducer 之前执行。

Combiner 的执行过程跟 Reducer 一模一样，唯一不同的是，Combiner 将结果输出到中间缓存，而 Reducer 将结果输出到文件系统。

Reader

MapReduce 通过 reader 接口的实现来定义读取数据方式，使用者可以自行定义，这使得数据的输入和输出更为灵活。

straggler

有一部分 Worker，虽然没有崩溃，但由于各种原因（比如磁盘坏了），执行任务的速度非常慢，就会影响到整个 MapReduce 的执行速度，这种现象也被称为 Straggler。论文提出了一个叫 backup tasks 的方法，Master会定时将尚未完成的任务分配给其余的Worker，如果特别慢的任务没有执行完，那这个任务极有可能会被另一个 Worker 抢先完成并汇报给 Master（无论哪个Worker完成 Master 都会认为任务已经完成），这样就可以摆脱 Straggler 的影响快速推进流程。

本地调试

MapReduce 接口中允许开发者使用调试工具（如gdb）在本地进行调试，以避免需要进行复杂的多机调试。

状态监控

Master 节点会运行一个内部的 HTTP 服务，并根据 Worker 反馈的数据输出一系列指标。一般这些指标包含了一些任务执行情况，如 completed 的任务数，in-progress 的任务数，input 数据大小， 中间数据大小，output 数据大小，处理的速度等；还有些更顶层的数据，如 failed 的 worker 的等。开发者能以直观的方式观察系统，及时纠错和提升性能。