MapReduce精髓

67次阅读

共计 1443 个字符,预计需要花费 4 分钟才能阅读完成。

虽然 Google 的 MapReduce 论文很老了(十多年),但只要还没看,就值得一看。
概要
MapReduce 是一种重视容错性的分布式并行计算模式,它把分布式并行计算分为 map 和 reduce 两个阶段:

map: 把输入数据集切分成很多份(1 份可包含很多 records),传给 map 函数做转换处理(每次处理 1 条 record,得出 1 条结果),结果集被输出到文件
reduce: 读取 map 的结果集,传给 reduce 函数做归约处理(每次处理 1 条 record,更新一条共享的结果),结果集被输出到文件

每台机器是一个 node。map 和 reduce 都可以在很多 worker node 上运行。1 个任务 = 1 个函数 + 1 组输入数据,任务被分配到 worker node 上运行。有一个中央的调度器,叫做 master node,来进行全局调度,给 worker node 分配任务。
示意图就不贴了,到处可见的 WordCount 例子也不写了,别人写过的我一般不写。请参考网络资料。
参考好了吗?继续吧!
优化
论文指出它是为大量廉价机器组成的环境而设计的,环境特点是:机器特别多,机器性能参差不齐,有的机器会突然坏掉。论文的很多优化都是在解决这种环境所特有的问题,这在当时是开创性的,因为一般的分布式并行技术都还在研究一组性能均等的高性能机器,不能容忍某台机器变慢或故障。现在工业界都是用 MapReduce 的方式在搞,因为多数企业的环境都是论文里说的这种。
Google 推出 MapReduce 论文时已经考虑周密了,给出了很多优化点:Map 阶段:

一开始先把输入数据集切分成 M 片,每片一般 16~64MB
map 完成时通知 master,master 记录所有 map 的完成情况和文件位置
map tasks 要切得小而多,建议远大于机器数,容易负载均衡(3 个 task 分给 2 个 node,均衡度肯定不如 13 个 task 分给 2 个 node)
map tasks 尽量分配到靠近数据的 node,以节省带宽
用 combine 函数做本地预合并,以减小 map 的输出结果集

Reduce 阶段:

reducer 从 mapper node 下载输入文件
reduce 先写临时文件,完成时用原子的文件重命名操作
reduce 用 lazy iterator 读取输入,以节省内存

全阶段:

map 输出到本地文件,reduce 输出到全局文件
map 和 reduce 都可有多个副本同时重复执行,谁快就用谁的结果(即使有个副本突然变慢,也有别的副本在跑)
总有一些落后进程,增加百分之几的备用资源,就能加速扫除长尾,节省百分之几十的时间
调度器尽量把任务分配给空闲的 worker,因此速度快的 worker 自然会处理更多 tasks
遇到错误的 record,写标记到 master,再有 task 遇到时跳过它

注释:这种“总有一些落后进程”的现象叫做尾部延迟放大 (tail delay amplification),分布式数据库执行查询的 scatter/gatter 模式也有此问题。Google 的解法相当于 task rebalance,来个比喻:让先进员工帮助落后员工完成积压的任务,以保证全团队的项目按时完成。我们要知道,“计算易移动,数据难移动”,我们总是倾向于把计算移动到另一处,而不是把数据移过去。MapReduce 就是移动了计算,并且把计算尽可能移动到数据附近。task rebalance 只移动计算,无需移动数据,所以才管用。而分布式数据库在执行查询时,把计算分发到 data node 上,如果有的 data node 反应慢,就没有办法,因为数据不好移。

正文完
 0