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

设计要素
nutch包含以下几个部分：
辅助类
Log:记载运行信息；
Time:记载时间信息；
协议类
目的：各种进程之间的通信协议
Client和M/R系统通信协议：完成客户端和M/R系统的通信；
Job和Task系统通信协议：由于一个任务要分布完成，所以需要任务和子任务之间的通信协议；
MapTask和ReduceTask通信协议：由于MAP和REDUCE是一个任务的顺序执行过程，所以需要两者之间的通信协议来对两个步骤进行协调，主要是文件输入输出协调；
进程通信协议：子进程和父进程通信协议；
 任务管理
      3.1任务定义与管理(JOB)：运行，状态管理，JOB和GOOGLE的MASTER是一个概念么？好像不一样；JOB应当等价于MapReduceSpecification类，那么nutch的master在哪里呢？
      3.2map管理；（运行，状态管理）
      3.3Reduce管理；（运行，状态管理）
      3.4map和Reduce协调管理；
      3.5.任务文件切割以及记录读写等管理；（文件由记录组成，切割时候注意边界）；输入输出文件读写等管理；  
关系定义：
一个M/R系统同时并行处理若干个JOB，每个JOB需要记载其运行状态等；
每个JOB对应一个大型输入文件，通过文件切割，建立若干个TASK分布在不同机器上处理切割过的文件片段，达到并行处理的目的；
每个TASK可以分为顺序执行的两部分：MAP/REDUCE，MAP阶段分布在M个机器执行，负责把输入文件的《KEY,VALUE>转换为《key1,value1>形式，不负责数据整理，只负责数据形式转换；REDUCE阶段分布在K个机器执行，负责对MAP阶段的输出结果进行排序和统计等整理，形成《key1,list(value1)>输出形式；
 
Nutch和GOOGLE的区别与联系：
大体上Nntch是按照GOOGLE的论文做的，但是有几点区别，总体感觉Nntch在完整性和复杂性方面还不如GOOGLE的系统；
GOOGLE更像一个软件框架，客户在这个框架下写自己的程序，而nutch更像一个固定功能的系统，当然之所以nutch的mapper和reducer类基本只起到一个接口的作用，也是为了体现框架的意图，由用户继承并定义新类来使用框架完成自己的任务，但是nutch的 jobclient和jobsubmission使得它更像一个静态的功能而非框架；
GOOGLE的实现版本框架，其中的变化点在于
用户自定义mapper;
用户自定义reducer;
用户可以对输入文件格式解析进行自定义；
用户通过一个类来设定系统参数并将map/reduce类和输入文件绑定起来；
用户自定义partition类，该类主要由reducer调用，功能是通过HASH(KEY)使得同一个KEY的能够映射到一台机器上，这样方便统计处理；
 
其中的不变点，也就是框架本身提供的功能:
    a.系统运行流程：首先将输入文件切割，然后分布到不同机器执行map运算，运算结果通知master,master通知reducer去累计结果输出；这个基本上是固定的；
    b.系统通信协议：master通过周期性的ping workers来判断是否该进程还有效；map运算结果要传送给master; master通知reducer输入数据所在位置；reducer通过RPC调用来获得输入数据等；
    c.容错处理：自动发现硬件错误并提供补偿措施，主要的补偿措施是如果发现某个任务失效，则将任务调配到另外一台机器重新计算；
    d.master记载控制信息并承担控制工作：比如记录任务分配信息；每个子任务（map/reduce）状态信息；轮询子任务获得状态信息；负责通信工作（类似于设计模式中的“中介者”模式）；发现错误的话进行调整工作（放置到一台好的机器重新运行）；
GOOGLE的方案有一些优化工作，比如计数器的实现，backup（就是往往最后完成的几个子任务拖整个任务的后腿，GOOGLE的策略是：当发现一个任务接近完成时候，启动几个后备子任务，哪个先完成算哪个，可以有效提高速度），partition函数；master的 checkpoint为了恢复master的工作等；这些工作nutch还没有实现；
GOOGLE方案的一些类：
    Counter:累计计数器；
    MapReduceSpecification:参数设定等；方法见论文；
    MapReduceInput:输入文件参数设定以及mapper绑定；
    MapReduceOutput:输出文件参数设定以及reducer 类绑定；
    Mapper:抽象类，用户继承进行自定义；Emit()函数
    Reducer: 抽象类，用户继承进行自定义；Emit()函数
    MapReduceResult:存放结果的类；
    MapReduce(MapReduceSpecification, MapReduceResult)方法，是启动整个MAPREDUCE的控制流程函数；