MAP/REDUCE:Google和Nutch实现异同及其他

/*版权声明：可以任意转载，转载时请务必标明文章原始出处和作者信息 .*/

张俊林
timestamp:2006年11月26日

设计要素

nutch包含以下几个部分：

1. 辅助类

Log:记载运行信息；

Time:记载时间信息；

1. 协议类

目的：各种进程之间的通信协议

1. Client和M/R系统通信协议：完成客户端和M/R系统的通信；
2. Job和Task系统通信协议：由于一个任务要分布完成，所以需要任务和子任务之间<wbr></wbr>的通信协议；
3. MapTask和ReduceTask通信协议：由于MAP和REDUCE是一个任务的顺序执行过程，所以需要两者之间的通信协议来对两个步<wbr></wbr>骤进行协调，主要是文件输入输出协调；
4. 进程通信协议：子进程和父进程通信协议；

1. 任务管理

3.1任务定义与管理(JOB)：运行，状态管理，JOB和GOOGLE的MASTER是一个概念么？好像不一样；JOB应当等价于MapReduceSpecification类，那么nutch的master在哪里呢？

3.2map管理；（运行，状态管理）

3.3Reduce管理；（运行，状态管理）

3.4map和Reduce协调管理；

3.5.任务文件切割以及记录读写等管理；（文件由记录组成<wbr></wbr>，切割时候注意边界）；输入输出文件读写等管理；

关系定义：

1. 一个M/R系统同时并行处理若干个JOB，每个JOB需要记载其运行状态等；
2. 每个JOB对应一个大型输入文件，通过文件切割，建立若干个TASK分布在不同机器上处理切割过的文件片段，达到并行处理的目的；
3. 每个TASK可以分为顺序执行的两部分：MAP/REDUCE，MAP阶段分布在M个机器执行，负责把输入文件的《KEY,VALUE>转换为《key1,value1>形式，不负责数据整理，只负责数据形式转换；REDUCE阶段分布在K个机器执行，负责对MAP阶段的输出结果进行排序和统计等整理，形成《key1,list(value1)>输出形式；

Nutch和GOOGLE的区别与联系：

1. 大体上Nntch是按照GOOGLE的论文做的，但是有几点区别，总体感觉Nntch在完整性和复杂性方面还不如GOOGLE的系统；
2. GOOGLE更像一个软件框架，客户在这个框架下写自己的程序，而nutch更像一个固定功能的系统，当然之所以nutch的mapper和reducer类基本只起到一个接口的作用，也是为了体现框架的意图<wbr></wbr>，由用户继承并定义新类来使用框架完成自己的任务，但是nutch的 jobclient和jobsubmission使得它更像一个静态的功能而非框架；
3. GOOGLE的实现版本框架，其中的变化点在于
1. 用户自定义mapper;
2. 用户自定义reducer;
3. 用户可以对输入文件格式解析进行自定义；
4. 用户通过一个类来设定系统参数并将map/reduce类和输入文件绑定起来；
5. 用户自定义partition类，该类主要由reducer调用，功能是通过HASH(KEY)使得同一个KEY的能够映射到一台机器上，这样方便统计处理；

其中的不变点，也就是框架本身提供的功能:

a.系统运行流程：首先将输入文件切割，然后分布到不同机器执行map运算，运算结果通知master,master通知reducer去累计结果输出；这个基本上是固定的；

b.系统通信协议：master通过周期性的ping workers来判断是否该进程还有效；map运算结果要传送给master; master通知reducer输入数据所在位置；reducer通过RPC调用来获得输入数据等；

c.容错处理：自动发现硬件错误并提供补偿措施，主要的补偿措施是如果<wbr></wbr>发现某个任务失效，则将任务调配到另外一台机器重新计算；

d.master记载控制信息并承担控制工作：比如记录任务分配信息；每个子任务（map/reduce）状态信息；轮询子任务获得状态信息；负责通信工作<wbr></wbr>（类似于设计模式中的“中介者”模式）；发现错误的话进行调整工作<wbr></wbr>（放置到一台好的机器重新运行）；

1. GOOGLE的方案有一些优化工作，比如计数器的实现，backup（就是往往最后完成的几个子任务拖整个任务的后腿，GOOGLE的策略是：当发现一个任务接近完成时候，启动几个后备子任务<wbr></wbr>，哪个先完成算哪个，可以有效提高速度），partition函数；master的 checkpoint为了恢复master的工作等；这些工作nutch还没有实现；
2. GOOGLE方案的一些类：

Counter:累计计数器；

MapReduceSpecification:参数设定等；方法见论文；

MapReduceInput:输入文件参数设定以及mapper绑定；

MapReduceOutput:输出文件参数设定以及reducer 类绑定；

Mapper:抽象类，用户继承进行自定义；Emit()函数

Reducer: 抽象类，用户继承进行自定义；Emit()函数

MapReduceResult:存放结果的类；

MapReduce(MapReduceSpecificatio<wbr></wbr>n, MapReduceResult)方法，是启动整个MAPREDUCE的控制流程函数；