GoogleMapReduce有啥巧妙优化？

搞架构的人&＃xff0c;Google的架构论文是必看的&＃xff0c;但好像大家都不愿意去啃英文论文。故把自己的读书笔记&＃xff0c;加入自己的思考&＃xff0c;分享给大家。

《MapReduce到底解决什么问题&＃xff1f;》做了简介&＃xff0c;这是第二篇&＃xff0c;Google MapReduce优化启示&＃xff08;中&＃xff09;。

什么是MapReduce&＃xff1f;

MapReduce这个编程模型解决什么问题&＃xff1f;

Google MapReduce是Google产出的一个编程模型&＃xff0c;同时Google也给出架构实现。它能够解决“能用分治法解决的问题”。

同时&＃xff0c;前文以“统计大量文档中单词出现的个数”为例&＃xff0c;例举了如何“先分再合”的撰写map与reduce来解决实际问题。

画外音&＃xff0c;强烈建议回顾一下前情提要&＃xff1a;

《MapReduce到底解决什么问题&＃xff1f;》。

MapReduce的核心思路是&＃xff1a;

• 并行

• 先分再合

下图简述了MR计算“词频统计”的过程。

从左到右四个部分&＃xff0c;分别是&＃xff1a;

• 输入文件

• 分&＃xff1a;M个并行的map计算实例

• 合&＃xff1a;R个并行的reduce计算实例

• 输出结果

先看最后一步&＃xff0c;reduce输出最终结果。

可以看到&＃xff0c;R个reduce实例并发进行处理&＃xff0c;直接输出最后的计数结果。

实例1输出&＃xff1a;(a, 256)(able, 128)(emacs, 1)

实例2输出&＃xff1a;(f*ck, 32768) (coding, 65535)

实例3输出&＃xff1a;(vim,65535)(x, 16)(zero, 258)

画外音&＃xff1a;这就是总结果&＃xff0c;可以看到vim比emacs受欢迎很多。

需要理解的是&＃xff0c;由于这是业务计算的最终结果&＃xff0c;一个单词的计数不会出现在两个实例里。即&＃xff1a;如果(a, 256)出现在了实例1的输出里&＃xff0c;就一定不会出现在其他实例的输出里。

画外音&＃xff1a;否则的话&＃xff0c;还需要合并&＃xff0c;就不是最终结果了。

再看中间步骤&＃xff0c;map到reduce的过程。

可以看到&＃xff0c;M个map实例的输出&＃xff0c;会作为R个reduce实例的输入。

潜在问题一&＃xff1a;每个map都有可能输出(a, 1)&＃xff0c;而最终结果(a, 256)必须由一个reduce输出&＃xff0c;那如何保证每个map输出的同一个key&＃xff0c;落到同一个reduce上去呢&＃xff1f;

这就是“分区函数”的作用。

什么是分区函数&＃xff1f;

分区函数&＃xff0c;是使用MapReduce的用户需所实现的&＃xff0c;决定map输出的每一个key应当落到哪个reduce上的函数。

画外音&＃xff1a;如果用户没有实现&＃xff0c;会使用默认分区函数。

以词频统计的应用为例&＃xff0c;分区函数可能是&＃xff1a;

(1) 以[a-g]开头的key落到第一个reduce实例&＃xff1b;

(2) 以[h-n]开头的key落到第二个reduce实例&＃xff1b;

(3) 以[o-z]开头的key落到第三个reduce实例&＃xff1b;

画外音&＃xff1a;有点像数据库水平切分的“范围法”。

分区函数实现要点是什么&＃xff1f;

为了保证每一个reduce实例都能够差不多时间结束工作任务&＃xff0c;分区函数的实现要点是&＃xff1a;尽量负载均衡。

画外音&＃xff1a;即数据均匀分摊。

上述词频统计的分区函数&＃xff0c;就不是负载均衡的&＃xff0c;有些reduce实例处理的单词多&＃xff0c;有些reduce处理的单词少&＃xff0c;这样就可能出现&＃xff0c;所有reduce实例都处理结束&＃xff0c;最后等待一个长尾reduce的情况。

对于词频统计&＃xff0c;负载更为均衡的分区函数为&＃xff1a;

hash(key) % 3

画外音&＃xff1a;有点像数据库水平切分的“哈希法”。

潜在问题二&＃xff1a;每个map都有可能输出多个(a, 1)&＃xff0c;这样无形中增大了网络带宽资源&＃xff0c;以及reduce的计算资源&＃xff0c;有没有办法进行优化呢&＃xff1f;

这就是“合并函数”的作用。

什么是合并函数&＃xff1f;

有时&＃xff0c;map产生的中间key的重复数据比重很大&＃xff0c;可以提供给用户一个自定义函数&＃xff0c;在一个map实例完成工作后&＃xff0c;本地就做一次合并&＃xff0c;这样网络传输与reduce计算资源都能节省很多。

合并函数在每个map任务结束前都会执行一次&＃xff0c;一般来说&＃xff0c;合并函数与reduce函数是一样的&＃xff0c;区别是&＃xff1a;

• 合并函数执行map实例本地数据合并

• reduce函数执行最终的合并&＃xff0c;会收集多个map实例的数据

对于词频统计应用&＃xff0c;合并函数可以将&＃xff1a;

一个map实例的多个(a, 1)合并成一个(a, $count)输出。

最后看第一个个步骤&＃xff0c;输入文件到map的过程。

潜在问题三&＃xff1a;如何确定文件到map的输入呢&＃xff1f;

随意即可&＃xff0c;只要负载均衡&＃xff0c;均匀切分输入文件大小就行&＃xff0c;不用管分到哪个map实例。

画外音&＃xff1a;无论分到那个map都能正确处理。

结论

Google MapReduce实施了一系列的优化。

• 分区函数&＃xff1a;保证不同map输出的相同key&＃xff0c;落到同一个reduce里

• 合并函数&＃xff1a;在map结束时&＃xff0c;对相同key的多个输出做本地合并&＃xff0c;节省总体资源

• 输入文件到map如何切分&＃xff1a;随意&＃xff0c;切分均匀就行

希望大家对MapReduce的优化思路有一个了解&＃xff0c;思路比结论更重要。

下章&＃xff0c;讲Google MapReduce的工程架构实现。

架构师之路-分享可落地的技术文章

相关推荐&＃xff1a;

《GFS架构启示》

《Google MapReduce到底解决什么问题&＃xff1f;》