MIT 6.824 分布式系统笔记 — MapReduce

最近抽空学了下 MIT 的著名分布式系统课 6.824。这次 MIT 终于加上了课堂录像。有兴趣的同学可以去学下,熟悉的国外计算机的味道。读论文,上课,写 Lab,每个 Lab 还有详细的测试。让我不经回忆起刚开始学算法公开课的时候,在被虐中成长。

刚学到第三节课,做下笔记。我最近越发发现,写了笔记的不容易忘,正是好记性不如烂笔头。即使笔记写得有种给自己看的意思,还是尽量写写看。

前三节课主要讲了分布式的一些基本概念,比如容错性、性能和一致性的矛盾,Go 相关知识,还有两个 Case Study,MapReduce 和 GFS。MapReduce 和 GFS 都是 Google 大数据的三驾马车,这让我对这门课充满了敬意,刚开始就学这个。后来读了论文之后,发现确实没想象中的难。

MapReduce 是为了解决大规模数据的计算问题。简单来讲你要处理大量的数据,而这已经超出了单机的承载能力,所以你必须先将数据分块,然后使用大量的机器进行并行计算,最后再汇总结果。但你作为个开发者,不想每次都考虑任务的分发和调度的问题,只想处理和数据有关的逻辑,而把其他的事情都交给框架处理,而这就是 MapReduce。
MapReduce 将过程分成两部,第一步 Map,对数据进行处理得出中间结果。第二部 Reduce,对中间结果进行汇总。

1
2
3
4
5
6
7
8
9
Abstract view of a MapReduce job
input is (already) split into M files
Input1 -> Map -> a,1 b,1
Input2 -> Map -> b,1
Input3 -> Map -> a,1 c,1
| | |
| | -> Reduce -> c,1
| -----> Reduce -> b,2
---------> Reduce -> a,2

其实 MapReduce 本质是分治的分布式应用,隐藏了使用者不需要关心的分发调度、容错等细节。接下来来看下它是怎么实现的。
MapReduce 流程总览
该图来自于 MapReduce 论文,显示了 MapReduce 是如何工作的。我们先不关注任何细节,最简单地讲下它的流程。
有一个 master 节点,它负责将 map 或者 reduce 的任务分发给 worker,worker 执行完任务后将结果提交给 master,之后再进行分发-执行-提交的循环,直至所有任务都完成。在这过程中,worker 不需要知道其他信息,只需要完成 master 分发的任务即可。而 master 是统筹一切的关键,它需要分配任务,保存提交结果,记录每个任务的状态,判断整个任务的完成情况。
接下来我们讨论下 master 的一些细节。master 将 map 或者 reduce 的任务分发给空闲的 worker 去执行,具体是 map 或者 reduce 由整个任务的完成情况来决定。若是所有 map 任务都已经完成,那么就会分发 reduce 任务。master 会通过探活来监控 worker 的运行情况,如果发现 worker 无法响应,则会把分配给该 worker 的任务重新进行分配。这增强了容错性,因为在大量机器的情况下单一机器出错几乎是个必然事件。但这同时会导致一个任务被执行多次。 MapReduce 通过提交结果的原子性来避免该影响。如果之前已经有 worker 提交了该任务,那么之后的提交将被忽略。
除此之外,还有很多细节的优化,比如 master 在分配任务时会考虑输入数据与 worker 之间的距离,来减少数据传输的时间以及对中心路由器的压力。当临近 map 或 reduce 阶段结束的时候,为了减少个别任务未完成的影响,master 会对未完成的任务进行再分配。更多细节还是看论文来得实在,我就不多讲了。

从上面的分析可以看出 MapReduce 其实并不复杂,Lab1 就是要求你用 go 来实现一个简易的 MapReduce。代码难度不高,需要注意的有几点,一是分发任务、提交任务时注意原子性,master 可以通过加锁来保证这点。二是分发任务时需要判断整个任务的阶段,是 map 还是 reduce。有一个 corner case,是所有 map 都已分发完成但有部分未完成的情况下,如果开始 reduce 会导致最后结果不完整,我在这边就踩了坑。三是需要定时去刷下任务的状态,如果某个任务超过一定时间没有完成的话,需要重新将该任务的状态变为可分发。master 可以通过 channel 定时刷新来解决这点。写完了还是很有成就感的。

上面讲了 MapReduce 的优点,但 MapReduce 还是有一定的局限性的。像是工作中对大数据的处理大多是多个阶段的,因此需要用户使用多次 MapReduce 自行串联。此外,MapReduce 也不支持基于实时数据流的数据处理。

参考