为什么需要用到Hadoop

Hadoop是Apache开源基金会下的一个项目，针对处理大数据的特性设计的分布式编程模型工具。Hadoop的核心思想来源于Google的MapReduce和Google File System（GFS）。通俗来讲，就是将处理的问题分为两个子问题，一个负责将问题分割成一个一个小的部分，另一个负责将前一个步骤的每一部分都合并在一起。

最常见的例子就是单词统计。假设我们需要统计一个文档里的单词，最简单的方式就是用一个dictionary或者map来存储一个key-value对。一旦发现一个新的单词，我们就在这个dictionary里面添加一个条目，value设为1。如果这个单词已经存在，那么取出这个key对应的value，将其加1。这种方式对于一个小的文档来说固然合适，但如果我们处理的是一个TB，PB级别的数据呢？如果我们想在1秒钟之内就处理完这些数据？这就需要用到分布式处理了，也就是多台机器同时运算。对于数单词这样一个简单的工作，要解决的就是如何分配任务，每一台机器需要处理文档的哪个部分，以及如何将这些结果整合在一起。有了这样的思想，我们可以给这两个部分的工作分配给两个模块，一个是mapper，一个是reducer。mapper负责把问题分割成很小的一部分，每一部分都会产生一个问题的输出；reducer负责把所有若干个mapper产生的输出汇总，再计算出所需的输出。由于这种模型涉及到的数据量都比较大，而建立在大数据上的数据处理一般来说都相对比较简单，因此将这种模型一般化，使用户只需要关注mapper和reducer的具体实现，而不用考虑异常处理，问题分割等等细节问题，这就是Hadoop需要解决的问题。

但是，并不是所有问题都适合用MapReduce模型解决，比如说PageRank。当问题涉及到图结构的时候，一个很普遍的现象就是活跃节点和不活跃节点差异非常明显。比如说Yahoo网页的PageRank值要计算很多次才能收敛，因为它链接的网页实在是太多了。而小一点的网站可能一下子就收敛了，因为其本身链接的网站并不多，也并没有很高的影响力。而且在图问题中，绝大部分的节点都是不活跃的，也就是说可能整个MapReduce计算一次，只有少数几个节点的值发生了变化，这严重影响到了处理时间。Google针对这个问题提出了Pregel模型，GraphLab就是参考这个模型实现的，相关的论文里面可以看出在PageRank和三角形计数算法上GraphLab完胜基于MapReduce的Hadoop。

理解Mapper和Reducer

如果只从输入输出来看，mapper和reducer的输入输出都是一个key-valud对。当然，具体实现来说key和value并不是必须的，比如说统计所有文档的单词数，mapper的输入就可以是key：文件名，value：文件内容，文件名在这里不需要用到。

对于数单词这个问题，mapper需要做的就是把自己负责的那部分文档的单词都统计出来，输出key-value对。这里的key就是单词，value就是1，代表的含义就是在这部分的文档中这个单词出现了1次。当然，也可以在mapper里面就把所有重复的单词都统计一次，汇总之后再设为这个单词key的value。而reducer就会收到mapper的单词key-value对。假如一开始mapper输入的文档内容是这样的：

foo other more data foo

那么mapper的输出就是如下形式：

foo 1
other 1
more 1
data 1
foo 1

此时reducer接收到的输入是按照key排列号的，因此实际上reducer的输入是如下的顺序输入的：

data 1
foo 1
foo 1
more 1
other 1

于是reducer可以这么写，这里用伪代码实现：

let reduce(k, values) = 
    sum = 0
    foreach int i in vals:
        sum += i
    emit(k, sum)

这样得到的最终reducer的输出应该是这样的：

data 1
foo 2
more 1
other 1

具体实现

鉴于网上hadoop的教程都比较多，就不在这里写出来了，用Python实现的可以参考Writing an Hadoop MapReduce Program in Python，还有用Java实现的例子：Hadoop集群（第9期）_MapReduce初级案例。