[转载] Hadoop MapReduce

转载自http://blog.****.net/yfkiss/article/details/6387613和http://blog.****.net/yfkiss/article/details/6387461

Hadoop MapReduce是一个用于处理海量数据的分布式计算框架。这个框架解决了诸如数据分布式存储、作业调度、容错、机器间通信等复杂问题，可以使没有并行处理或者分布式计算经验的工程师，也能很轻松地写出结构简单的、应用于成百上千台机器处理大规模数据的并行分布式程序。

Hadoop MapReduce基于“分而治之”的思想，将计算任务抽象成map和reduce两个计算过程，可以简单理解为“分散运算—归并结果”的过程。一个MapReduce程序首先会把输入数据分割成不相关的若干键/值对（key1/value1）集合，这些键/值对会由多个map任务来并行地处理。MapReduce会对map的输出（一些中间键/值对key2/value2集合）按照key2进行排序，排序是用memcmp的方式对key在内存中字节数组比较后进行升序排序，并将属于同一个key2的所有value2组合在一起作为reduce任务的输入，由reduce任务计算出最终结果并输出key3/value3。作为一个优化，同一个计算节点上的key2/value2会通过combine在本地归并。基本流程如下：

Hadoop和单机程序计算流程对比：

常计算任务的输入和输出都是存放在文件里的，并且这些文件被存放在Hadoop分布式文件系统HDFS（Hadoop Distributed File System）中，系统会尽量调度计算任务到数据所在的节点上运行，而不是尽量将数据移动到计算节点上，减少大量数据在网络中传输，尽量节省带宽消耗。

应用程序开发人员一般情况下需要关心的是图中灰色的部分，单机程序需要处理数据读取和写入、数据处理；Hadoop程序需要实现map和reduce，而数据读取和写入、map和reduce之间的数据传输、容错处理等由Hadoop MapReduce和HDFS自动完成。

MapReduce是一种编程模型，始于：Dean, Jeffrey & Ghemawat, Sanjay (2004). "MapReduce: Simplified Data Processing on Large Clusters"。主要应用于大规模数据集的并行运算。其将并行计算简化为Map和reduce过程，极大地方便了编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上。程序员只需要指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，然后指定并发的Reduce（化简）函数，用来保证所有映射的键值对中的每一个共享相同的键组。

MapReduce 的根源是函数性编程中的 map 和 reduce 函数。它由两个可能包含有许多实例（许多 Map 和 Reduce）的操作组成。Map 函数接受一组数据并将其转换为一个键/值对列表，输入域中的每个元素对应一个键/值对。Reduce 函数接受 Map 函数生成的列表，然后根据它们的键（为每个键生成一个键/值对）缩小键/值对列表。其流程概念图如下：

一个典型的Map-Reduce过程如下：

Input->Map->Patition->Reduce->Output

Input Phase
输入的数据需要以一定的格式传递给Mapper的，格式有多种，数据一般分布在多台机器。

Map Phase
对输入的数据进行处理，输出的是key、value的集合。

Partition Phase
把Mapper任务输出的中间结果按key的范围划分成R份（R是预先定义的Reduce任务的个数），默认的划分算法是"(key.hashCode() & Integer.MAX_VALUE) % numPartitions"，这样保证了某一范围的key一定是由某个Reducer来处理。

Reduce Phase
Reducer获取Mapper输出的中间结果，作为输入对某一key范围区间进行处理。

Output Phase
Reducer的输出格式和Mapper的输入格式是相对应的，当然Reducer的输出还可以作为另一个Mapper的输入继续进行处理。

MapReduce的优点：
主要有两个方面： 
1. 通过MapReduce这个分布式处理框架，不仅能用于处理大规模数据，而且能将很多繁琐的细节隐藏起来，比如，自动并行化、负载均衡和灾备管理等，这样将极大地简化程序员的开发工作;
2. MapReduce的伸缩性非常好，也就是说，每增加一台服务器，其就能将差不多的计算能力接入到集群中，而过去的大多数分布式处理框架，在伸缩性方面都与MapReduce相差甚远。而 MapReduce最大的不足则在于，其不适应实时应用的需求