MapReduce 论文

简介

2004 年发表了 MapReduce 的论文，是一个分布式计算的框架。
当你仔细了解 MapReduce 的框架之后，你会发现 MapReduce 的设计哲学和 Unix 是一样的，叫做“Do one thing, and do it well”，也就是每个模块只做一件事情，但是把这件事情彻底做好。

数据处理

作为一个框架，MapReduce 设计的一个重要思想，就是让使用者意识不到“分布式”这件事情本身的存在。从设计模式的角度，MapReduce 框架用了一个经典的设计模式，就是模版方法模式。而从设计思想的角度，MapReduce 的整个流程，类似于 Unix 下一个个命令通过管道把数据处理流程串接起来。
MapReduce 的数据处理设计很直观，并不难理解。Map 帮助我们解决了并行在很多台机器上处理互相之间没有依赖关系的数据；而 Reduce 则用来处理互相之间有依赖关系的数据，我们可以通过 MapReduce 框架自带的 Shuffle 功能，通过排序来根据设定好的 Key 进行分组，把相同 Key 的数据放到同一个节点上，供 Reduce 处理。
而作为 MapReduce 框架的使用者，你只需要实现 Map 和 Reduce 两个函数，并且指定输入输出路径，MapReduce 框架就会帮助你完成整个数据处理过程，不需要你去关心整个分布式集群的存在。另外，不仅仅是 MapReduce 的用户，只需要考虑“单一职责”，实现自己的 Map 和 Reduce 函数就好了。即使作为 MapReduce 的框架实现，也能够把数据读取、数据输出、网络传输、数据混洗等模块单独拆出来，实现起来也很容易。
Map 和 Reduce 这两个函数虽然非常简单，但是对于输入输出的格式，以及内部具体的逻辑代码没有任何限制，是完全灵活的，足以完成从日志分析、网页处理、数据统计，乃至于搜索引擎的索引生成工作。
事实上，我们在论文中也可以看到，谷歌在多种不同的场景中，都使用了 MapReduce，包括：

• 大规模的机器学习问题；
• 谷歌新闻和 Froogle 商品的聚类；
• 抽取数据生成热门搜索的报表；
• 大规模的图计算。
  这些复杂的问题，都可以通过一个或者多个 MapReduce 的任务的串联来实现。

计算框架失败处理

MapReduce 的实现是比较简单的，就是一个典型的单 master 多 worker 组成的主从架构。在分布式系统容错上，MapReduce 也采取了简单的重新运行、再来一次的方案。对于 master 这个单点可能出现的故障，谷歌在最早的实现里，根本就没有考虑失效恢复，而是选择了任由 master 失败，让开发人员重新提交任务重试的办法。
还有一点也和 GFS 一样，MapReduce 论文发表时的硬件，用的往往是 100MB 或者 1GB 的网络带宽。所以 MapReduce 框架对于这一点，就做了不少性能优化动作。通过尽量让各个 worker 从本地硬盘读取数据，以及通过 Combiner 合并本地 Map 输出的数据，来尽可能减少数据在网络上的传输。
而为了方便开发人员去 debug 程序，以及监控程序的执行，MapReduce 框架通过 master 内嵌的 Web 服务器，展示了所有 worker 的运行情况和日志。你还可以通过自定义的计数器，统计更多你觉得有价值的信息。
当然，MapReduce 里还有备用任务（Backup Tasks）、自定义的 Partitioner 等更多的细节值得你去探索。这些就留给你去仔细研读论文，好好琢磨了。

遗憾与缺陷

尽管 MapReduce 框架已经作出了很多努力，但是今天来看，整个计算框架的缺陷还是不少的。在我看来，主要的缺陷有两个：

• 第一个是还没有 100% 做到让用户意识不到“分布式”的存在，无论是 Combiner 还是 Partitioner，都是让开发者意识到，它面对的还是分布式的数据和分布式的程序。
• 第二个是性能仍然不太理想，这体现在两个方面，一个是每个任务都有比较大的 overhead，都需要预先把程序复制到各个 worker 节点，然后启动进程；另一个是所有的中间数据都要读写多次硬盘。map 的输出结果要写到硬盘上，reduce 抓取数据排序合并之后，也要先写到本地硬盘上再进行读取，所以快不起来。

不过，随着时间的变迁，会有更多新一代的系统，像是 Dremel 和 Spark 逐步取代 MapReduce，让我们能更容易地写出分布式数据处理程序，处理起数据也比原始的 MapReduce 快上不少。

参考
http://nathanmarz.com/blog/the-mathematics-behind-hadoop-based-systems.html