哈巴狗

Google MapReduce阅读笔记

摘要：
MapReduce不是一个产品，它是一种基于分治思想，一种解决问题的思路。Google MapReduce是Google产出的一个编程模型，算法模型，当然Google也有其相关实现，提供给了用户相关函数接口：
（1）Map函数接口处理一个基于key/value（后简称kv）的成对（pair）数据集合，同时也输出基于kv的数据集合；
（2）Reduce函数接口用来合并Map输出的kv数据集合；
现实中有许多应用需求都能用这种模型处理，许多应用都能用这种方法解决。

MapReduce架构的程序能在大规模普通PC集群上实现并行处理，整个集群系统在程序运行时需要关心：
（1）如何分割数据；
（2）集群调度；
（3）集群错误处理；
（3）集群通信；
用户仅仅提供Map函数接口，Reduce函数接口即可，在MapReduce架构下，能让那些没有分布式计算处理程序开发经验的程序也有效的利用分布式集群的资源。

1.介绍
现实中有许多基于分治的应用需求：
（1）网页抓取；
（2）日志处理；
（3）索引倒排；
（4）查询请求汇总；
（5）…
单机的计算容易理解与完成，但在输入数据量巨大（TB级别）的情况下，如何能够在短时间内完成处理呢，只有将这些计算分布在成百上千的主机上，但此时，并行计算、数据分发、错误处理、集群通讯等等问题综合到一起，就成为了一个困难的问题。
为了解决这个问题，抽象出一个计算模型：该模型下，不必关心并行、容错、数据分布、负载均衡等细节，而只需提供Map和Reduce函数。

2.编程模型
MapReduce编程模型原理：
（1）Map函数接受一个kv输入数据集合，输出一个中间kv数据集合；
（2）Reduce函数接受Map输出的kv数据集合，再进行汇聚。

2.1例子
以统计大量文档中单词出现的个数为例，以下是一段伪代码，
Map(string $key_doc_name, string $value_doc_content) // 文件名=>文件内容
foreach(string $word in $value_doc_content) // 文件中的单词
array[$word] ++; // 单词计数增加

Reduce(string $word, iterator $value) // 单词=>计数链表
int $count = 0;
foreach(int $count in $value) // 计数合并
$count += $value;
emit($word, $count)

很多应用的例子都适合上述MapReduce模型，例如：
（1）分布式grep：Map输出匹配行，Reduce直接输出；
（2）URL访问频率计算：Map输出(URL, 1)，Reduce累加，产生(URL, count)；

2.2类型
用户定义的Map和Reduce函数相关类型：
map(k1, v1) => list (k2, v2)
reduce(k2, list(v2)) => list(v2)