2.1　设计基础

2.1.1　MapReduce 1.0及其局限性

除了自动实现分布式并行计算、支持大规模海量数据处理、借鉴函数式编程思路、简洁易用等基本特点外，MapReduce 1.0还具备如下特征。

（1）以主从结构的形式运行。MapReduce集群分为两个角色——Master和Worker，较好地实现了数据流和控制流的分离。

（2）map（）函数与reduce（）函数之间的数据处理。对map（）函数的返回值进行一定的处理后才传给reduce（）函数，其中的处理主要包括：

•shuffle处理。为了确保每个reduce（）函数的输入都按键（key）排序，MapReduce系统的执行过程需要一个特殊的过程——shuffle，即对map（）函数的数据结果进行排序。

•combine（）函数。为了降低map（）函数与reduce（）函数之间的数据传递量，一般采用combine（）函数对map（）函数的数据结果进行合并处理。

•partition（）函数。MapReduce对map（）函数输出的中间键使用partition（）函数进行分区处理，为每个Reduce任务创建一个分区。

（3）＜key，value＞类型的输入输出。MapReduce模型的输入和输出均为＜key，value＞集，其中map（）函数的输出为reduce（）函数的输入，这两种函数的输入和输出也均为＜key，value＞集。MapReduce框架中数据处理函数的输入输出如下：

map（K1，V1）→list（K2，V2）

combine（K2，list（V2））→list（K2，V2）

partition（K2，V2）→integer

reduce（K2，list（V2））→list（K3，V3）

（4）故障处理及容错机制。MapReduce故障可分为Master故障和Worker故障两类，并分别给出了不同的故障处理及容错机制。通常，Master通过将数据周期性地写入磁盘，并启动另一个Master进程和利用检查点技术实现故障恢复。然而，当某个Worker发生故障时，正在运行或尚未运行完毕的任务的状态将重置为空闲状态，并将重新调度到其他Worker节点。

（5）数据存储位置的多样性。MapReduce中的数据存储位置具有多样性，具体如下：

•源文件：GFS。

•Map处理结果：本地存储。

•Reduce处理结果：GFS。

•日志：GFS。

（6）任务粒度大小的重要性。为了更好地支持负载均衡和故障恢复，MapReduce需要对Map任务和Reduce任务进行拆分处理。如何将Map任务（或Reduce任务）拆分成若干个片段是MapReduce的一个重要机制。通常，拆分后的片段个数为集群中的Worker节点的整数倍。

（7）慢节点的处理及任务备份机制的必要性。由于MapReduce是在分布式集群环境中运行的，个别慢节点往往成为影响整个程序的运行速度的主要因素。在MapReduce中，慢节点的处理通常采用任务备份机制，如推测性的执行（speculative execution）。

除了上述特征之外，MapReduce还采用了一些关键技术：跳过损坏记录、本地执行、状态信息、计数器等。