MapReduce 最近几年越来越热——其实它被发明出来也就几年而已——现在写一个简要的介绍，主要素材来源于 Eugene Ciurana 发表在 TheServerSide.com 的一篇 Why Should You Care About MapReduce，以及 Wikipedia 上的 MapReduce 条目。可以的话最好去读原文。
MapReduce 是一种用于在大规模集群环境下处理海量数据的分布式编程框架(distributed programming model)，最早由 Google 的工程师 Jeffrey Dean 和 Sanjay Ghemawat 开发，他们的实现是用 C++ 做的，同时提供了 Python 和 Java 的接口供 Google 的各种应用系统使用。 MapReduce 框架的核心是应用要实现的两个函数：
Map，即“映射”，对一个集合的所有元素应用某个函数，并将返回的结果组成另一个集合。比如一个集合里全是表示数字的字符串，那么我们可以定义一个“字符串→数字”转换函数，然后用 Map 把这个集合变成完全由数字组成的另外一个集合。
Reduce，即“化简”，这是另一种针对数据集合进行的操作，它逐个的检查集合的元素，通过某种函数来得到一个相对简单的结果。比如我们可以定义一个求和的函数，把集合里的元素一个个加起来。
通过这两个函数，我们可以做到“分而治之”（Divide and Conquer），Google 的工程师们成功的把分布式业务逻辑拆成为两种高度抽象和优化的操作，在这两种操作中，Map 是高度可并行的，Reduce 虽然并行能力差于 Map ，但是属于并行业务逻辑中不可或缺的一部分，而且只要选择那些可以实现“简化”的操作函数，那么在高度并行的计算环境中，这也是很有用的操作。
事实上 MapReduce 框架还涉及另外几个函数，包括（为了明了其逻辑次序，Map 和 Reduce 也列于其中）：
- Input Reader: 读取输入，进行拆分，然后分发给多个并发的 Map。
- Map function: 大规模并发的 Map 处理将计算最耗时的部分在最短时间内完成，同时通过某些机制来保证其可靠性（这一点我们下面还会提到）。
- Partition function: Reduce 函数往往是需要特定范围的 Map 结果集合的，Partition 就是用来定位对应的 Reduce 的函数。
- Comparison function: 提供给 Reduce 运算的集合一般是已排序的，这个排序工作由 Comparison 函数完成。
- Reduce function: 执行特定范围的 Reduce 操作；可能是多级的，例如有一个大的 Master Reduce 来再次化简第一级 Reduce 得到的结果（必要的话可以同样经过 Partition 和 Comparison）。
- Output writer: 把 Reduce 结果输出到可靠的持久存储上。
为了提高分布式计算的可靠性，MapReduce 会把对数据集的大规模操作（Map）分发给网络上的多个节点，每个节点会周期性的把完成的工作和状态更新报告传回主节点（类似于 Google File System 中的主服务器）。如果一个节点保持沉默超过一个预设的时间间隔，主节点标记该节点状态为死亡，并把分配给这个节点的数据发到别的节点。每个操作使用命名文件的原子操作以确保不会发生并行线程间的冲突；当文件被改名的时候，系统可能会把他们复制到任务名以外的另一个名字上去以避免副作用。化简操作（Reduce）工作方式很类似，但是由于化简操作的并行能力较差，主节点会尽量把化简操作调度在一个节点上，或者离需要操作的数据尽可能进的节点上，这个设计可以满足 Google 的需求，因为他们有足够的带宽，他们的内部网络没有那么多的机器。
MapReduce 使用 Google File System 上的中间文件作为 Map 和 Reduce 的输入输出，这样也显著的降低了应用编写的难度，避免了各种不同应用之间纷繁的进程间、机器间通信方式。看似简单粗暴，却很有效。另外 MapReduce 也把分布式计算的很多技术细节屏蔽在应用之后，除了上面列出的函数需要应用去编写，其它诸如分布、调度、容错、通信等都由 MapReduce 框架完成。
MapReduce 的两位作者在论文（见上链接）中承认，这一设计很大程度上受到了经典函数编程语言中的映射和化简操作的启发（在Ruby中这两个操作叫做 map 和 inject，对任何可枚举类型都有效），其实，这两个原语几乎囊括了80%以上的常用信息操作，例如孟岩在他的的介绍文章 Map Reduce – the Free Lunch is not over? 中提到的，Unix系统中的大部分 pipe 操作要么类似于 Map（如 grep more cat 等），要么类似于 Reduce（如 sort uniq wc 等）。
MapReduce 在 Google 内部的地位很重要，被定位为“分布式计算架构”，与 Google Cluster（集群管理）、GFS（分布式文件系统），BigTable（分布式结构化存储）一起组成了支撑整个 Google 帝国的大规模并行处理架构。
传统的并行计算（或者网格计算）框架往往关注于任务的分发、通信、状态等，对于“如何切分业务逻辑以使其适合于并行处理”这个关键问题较少涉及（或者说讳莫如深？），MapReduce 正是应运而生，它的思想不仅简单易行而且血统高贵，秉承从图灵-丘奇理论以来的深刻背景，又在 Google 这样拥有顶级数据吞吐量的真实世界业务中实际运行并沿革至今，取得理论和实践双重成功就不足为奇了（当然也有人唱反调）。目前已经有了很多 MapReduce 的克隆产品，其中有大企业内部采用的，M$ 和 IBM 都有自己的解决方案，只是利用没有 Google 那么广泛；也有开源社区活跃的项目，其中比较耳熟能详的，一个是隶属于 Apache Lucene 一支的 Hadoop，由 Lucene 的创始人 Doug Cutting 亲自操刀，Nutch 力图凭借这一技术继续保持其在开源搜索引擎中的领先地位；另一个就是Ruby社区有着吓人名字的 Skynet 框架，由 Geni.com 的 Adam Pisoni 设计开发，和 Hadoop 这类从后到前完整的实现不一样，Skyney 更关注的是接口和框架，而把各种可能的后端交给用户去实现。这两个开源实现至少证明了一点，MapReduce 真的很简单很好写，并行计算就此从科学研究殿堂走进寻常百姓家。当然，这个理论和这些开源的实现都还非常新，基本上还在原型试验完毕、寻求大规模 reference 的阶段——至少大部分人都相信，前景是无限光明的。
[UPDATE on 2/20/2008] Yahoo! Launches World’s Largest Hadoop Production Application