MapReduce是Google提出的一个编程框架,用于大规模海量数据处理,其主要思想就是分治(divide and conquer)。我们希望程序有并行处理能力,于是就可以使用多台机器同时处理加快速度。

然而,怎样分派任务给不同的计算机?如果任务单元的数量大于可执行任务的计算机的数量怎么办?计算需要使用到一些中间结果怎样处理?如果某些计算机在处理任务时中途死掉了呢?怎样才能知道任务已经处理完毕?问题主要来自于任务处理节点的交流(比如状态信息),以及对共享资源(数据)的访问。要解决这些棘手的问题,我们需要有一套完整的同步机制:同步锁信号量、条件变量(等待、通告、广播)等等。

现有的一些编程模型有共享内存(pthread)、消息传递(MPI)等,架构的设计模式有主从式(Master-Slaves)、生产者消费者流式(Producer-consumer flows)等。Map Reduce结合了函数式编程语言的思想,使用key-value对作为输入和输出。开发者只需要实现map(key, value)和reduce(key, value)两个功能。map()会产生中间结果作为输出,而这正是reduce()的输入。中间结果经过reduce()产生最终结果。类似以下模型:

map (in_key, in_value) ->
(out_key, intermediate_value) list

reduce (out_key, intermediate_value list) ->
out_value list

具体的原理可以参看Google发表的关于MapReduce的论文。从应用开发的角度,本站的MapReduce分类下有一些python示例,可以作为初步入门学习。最简单的方法就是利用管道来进行代码测试,例如:

./mapper.py < input.txt | sort | ./reducer.py

或者也可以自己搭个虚拟机在Hadoop里面跑跑,企业级的实际应用可以前往Amazon AWS EMR

向想深入学习MapReduce分布式程序设计的同学推荐这本书:Data-Intensive Text Processing with MapReduce。如果所在学校购买了数据库,应该可以直接下载电子版阅读。书是马里兰大学一个华人教授写的,这教授很牛B,简直就是算法帝啊……语言方面通俗易懂,像我这种英语烂人都毫无障碍。重点看2、3、4章,讲得深入浅出,从最基本的word count程序开始,各种版本的word count写法以及如何逐步的优化。书里还讲到了MapReduce在搜索引擎中的应用。之前还顺带介绍了distributed system的一些基础,例如GFS以及开源实现HDFS。后面的Graph还有EM算法什么的比较高深了,我还没看。。。

现在突然感到有点绝望了,自己对分布式系统架构云计算什么的还是蛮有兴趣,最后却发现基础性工作全是大公司做出来的。因为他们才有最迫切的需求,看看那些论文作者不是google就是yahoo,国内的taobao也在这方面有些贡献。在实验室完全没有那种亿万级别的环境,如何做simulation呢?或者,根本就没有人带我入门。。。

科研是条清苦路。