MapReduce是这几年IT界很热的一个名词，从某种意义上讲，MapReduce引领了当代海量数据处理的趋势和潮流。与IT界的其他名词一样，MapReduce听起来也是个很玄乎的名词，MapReduce？Map？Reduce？如果你是一名初级Coder，那么你可能从某处知道，Map的翻译是映射，Reduce的翻译是归约。MapReduce就是映射归约，是一种数据并行处理的一种编程模型。如果很不幸，你不是一名光荣的Coder，只是中国网民大军中的五万万分之一¹，那么没关系，MapReduce离你并不遥远，有一个名词你一定很熟悉，那就是——云计算。关于云计算，互联网上有一个经典笑话，“中国一留学生去美国打工的当过报童，不带计算器，习惯动作抬头望天时心算找零。顾客大为惊讶，纷纷掏出计算器验证，皆无误，也抬头望天，惊恐问：“云计算？”不过云计算的真正含义，用工程师的语言，准确地定义，应当是“超大规模的，可扩展的，低成本，但是高可靠性的服务器集群系统”²。

从大的层面上来讲，云计算并不仅仅是MapReduce，MapReduce只是云计算的一个技术性开端，或者说，是互联网的发展需求推动技术的发展进步，最后由Google临门一脚创造出来的一种处理海量数据的并行编程模型。真正的云计算包含诸如IDC建设、海量存储、网络规划、商业模式、网络安全等等诸多技术的难题，还有很多被一些所谓的专家炒作起来的社会意义。不过本系列文章并不打算探讨这些过于宏大的主题，我本人也没有这样的水准和资格来说三到四。本系列文章的目的只有一个，那就是搞明白，MapReduce中的Map和Reduce，到底源自何处³？

我第一次听说MapReduce这个名词，是在2010年9月，那时百度来浙大宣讲，顺带开了一个技术讲座，主讲人徐串曾是Google中国编程挑战赛冠军。当然，讲座内容我是听不懂的，随心记下来的几个技术名词，至今为止，还能记住的，只剩下MapReduce了。后来面试百度运维部，期间和面试官聊到我暑期实习在华数淘宝做的一个视频转码入库系统，面试官大概觉得这个系统有点分布式的意思，因此题目结束的时候给了我一个建议，就是让我学习下MapReduce。再后来，阴差阳错，我进入了百度的分布式运维小组学习Hadoop运维，学习MapReduce就成了一个身不由己的任务。

在百度的半年，我初步接触了大规模Hadoop集群（3000个节点的规模）的运维工作。但比较讽刺的是，运维Hadoop集群的我，自身并没有写过多少真正的MapReduce程序，对Hadoop的理解也浅尝辄止。而我也始终没有搞明白，好端端的一个程序，为什么要按照MapReduce这样别扭的模型重构运行？

大概是看了Paul Graham的《黑客与画家》后，我开始正式认真学习Lisp这门语言，至今已有小半年时间，这期间我利用业余时间，和最近一个月的休假时间，基本上看完了Paul Graham的《ANSI Common Lisp》和《On Lisp》，《SICP》太难，我穷尽脑力至今也只窥得前面三章，做了100道习题左右，不过即便如此，也令我受益匪浅⁴。半年Lisp的学习让我搞明白了MapReduce中，Map和Reduce的来龙去脉。这个问题我Google了很久，但是始终没有一个满意的答案，现如今，我自己找到了满意的答案。

在正式开始我们的探险之旅前，我们还面临这一个问题，那就是，这次探险的必要性在哪里？既然MapReduce已然为我们提供了成熟的理论编程模型，Hadoop生态圈也给我们提供了一整套成熟的工程实现，我们为什么还要纠缠这些学究般的历史问题？我的解答是， 一个学科的历史往往就是这个学科的本身 。无论是一门编程语言、编程范式、编程模型，或者IT业的任何一项新技术新名词，在学习的过程中，一定要搞明白：

• 它解决了什么样的技术问题？当时的历史背景是什么？还有没有类似的（可能没有流行起来的）解决方案？
• 它的引入带来了哪些新的问题？
• 它的优点是什么？什么样的问题一定会手到禽来？
• 它的不足是什么？什么样的问题是它解决不了的？

这就好比解一道很难数学题，如果光告诉你一个正确的数字，那么这个数字对你来说一点意义都没有；如果进一步，告诉你标准的解题过程，那么你可能会对这个题目有一个粗浅的认识；如果有那么一个白痴，不但告诉你正确的答案和解题过程，还把他的演算纸送给了你，并热切地给你讲解他在解题过程中碰到了哪些问题和陷阱，是怎样解决怎样解决问题怎样规规避这些陷阱的，那么你对这道题目的理解则会大大加深，日后再碰到同样类型的问题就会轻车熟路，手到拈来。 从某种意义上而言，一个完整的解题的探寻过程才是一个题目所具有的全部信息价值，扔掉这些而仅仅记住一个解题结果或者一个标准的解题证明，无疑是买椟还珠 ⁵ 。但是比较可悲的是，计算机是一个年轻的学科，所以专门讲述计算机历史的书籍并不像数学史书籍一般汗牛充栋。

从另一个角度上讲，计算机和数学的都是一座不断分层的抽象大厦。数学是从基本的整数，到数系的扩充，到微积分的诞生，到非欧几何等等宏大的诗篇；而计算机则是从最基本的与非门，到bit、byte、word，到汇编、c、高级语言，到设计模式、分布式等等现代工业的大厦和基础。“计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决⁶”，不过很不幸， 计算机的抽象和数学的抽象有一个本质的不同，那就是计算机的抽象是有漏洞的 ，这就是抽象漏洞法则：All non-trivial abstractions, to some degree, are leaky。在数学领域，我们从来不用担心说某个定理“因为空调故障的原因宕机了，或者因为内存吃紧运行特别缓慢，似乎是发生内存泄漏了”，等等诸如此类的各种各样令人头疼的问题。这条法则深刻的影响了计算机软件和数学定理的生产过程——在计算机中，我们不可能找到一个能困惑世间智者358年的谜⁷；在数学领域，我们也不可能找到一个耗费人类5000万人年人力的定理⁸。 如果说，基于抽象的数学，考验的是人类大脑思考深度的极限，那么同样是基于抽象，并且脱胎于数学的计算机工程，挑战的就是人类大脑思考广度的极限 ——软件工程中瓶瓶罐罐的细节太多了，所以大凡软件开发，走的都是兵团作战的策略；而数学就不一样，“10个产妇无法在一个月内生出孩子⁹”，数学领域中辉煌定理的产出，往往依靠少数几个，甚至单个天才数学家的苦苦思索和灵感涌现。

以上，废话了这么多，所要强调的无非就是，了解MapReduce的来龙去脉，对于写出更好的MapReduce程序，甚至将来拨开层层抽象，解决MapReduce的底层问题，乃至改善MapReduce，都是大有裨益的。不过，在正式踏上我们的探险旅程之前，我们需要检查一下手头的“装备”是否合格，很简单：

• 你需要一台*nix系统，最好是GNU Linux，苹果也行，如果实在不方便，Windows下装个Cygwin也还能凑合；
• 你需要有一定的编程经验，包括但不仅限于C、Java、Bash、Python，如果再对Lisp或者Scheme有一定了解就更好了（别急，本系列文章对Lisp做一个简要的介绍）；
• 你需要了解一些常见的*nix软件开发工具，包括但不限于Vim的使用、Ant和Make构建工具、Git和SVN版本控制软件；
• 你需要对POSIX系统标准有一定了解，包括但不限于*nix的文件系统结构、用户属组、文件权限、管道等等。

Now, Let's Go!

行文至此，相信众位读者已经知晓了云计算的一些基础概念，最起码知道了所谓Google技术的三驾马车是什么，如果能看过Hadoop代码中WordCount的例子并能看懂的话，那你简直是太天才了。为了保证我们的探险顺利进行，我们需要一套开源的MapReduce平台实现来验证我们的学习成果，Hadoop是不二选择。关于Hadoop本身有太多太多的资料，因此我在这里就不再劳心劳力的copy别人的劳动成果了。推荐以下三本书，作为Hadoop的入门：

• 《Hadoop: The Definitive Guide》
• 《Hadoop in Action》
• 《Pro Hadoop》

我们所要做的，就是在本机的*nix系统下，搭建一个demo的伪分布式运行的Hadoop平台。我采用的Hadoop版本是Hadoop 0.20，这个版本比较稳定，最新的Hadoop 1.0添加了很多新的特性，这些特性对于我们的探险并没有特别的作用，而且我也不甚了解。当然，本文的重点并不是Hadoop，所以我并不会带你去分析HDFS的源代码，告诉你如何打Patch（我也不会，嘿嘿）。本文的重点在于MapReduce的来龙去脉。

• 首先本机*nix上存在jdk和ssh，并找到相应的$JAVA_HOME
• 首先是建立本机用户到自身的ssh信任关系，步骤大致如下：

➜  ~  ssh-keygen 
Generating public/private rsa key pair.
Enter file in which to save the key (/home/lox/.ssh/id_rsa): 
/home/lox/.ssh/id_rsa already exists.
Overwrite (y/n)? y
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /home/lox/.ssh/id_rsa.
Your public key has been saved in /home/lox/.ssh/id_rsa.pub.
The key fingerprint is:
19:3f:55:84:99:d2:1e:c6:42:d0:39:6f:3e:83:84:21 lox@lox-pad
The key's randomart image is:
+--[ RSA 2048]----+
|        .+.+ =o  |
|      E . * O.   |
|       ..o B..   |
|        .+..+    |
|        S.o+     |
|          ..+    |
|             o   |
+-----------------+
➜  ~  cp .ssh/id_rsa.pub .ssh/authorized_keys 
➜  ~  chmod 700 .ssh 
➜  ~  chmod 600 .ssh/authorized_keys 
➜  ~  ssh lox@localhost

• 下载hadoop v0.20，解压缩到一个目录，我的目录结构如下，其中tmp/hadoop-data作为hdfs数据存放目录（包括伪分布式运行的namenode和datanode的数据），tmp/hadoop-v20作为$HADOOP_HOME

➜  ~  tree -L 1 tmp/hadoop-data tmp/hadoop-v20 
tmp/hadoop-data
tmp/hadoop-v20
├── bin
├── build.xml
├── CHANGES.txt
├── conf
├── conf.origin
├── conf.pseudo
├── conf.standalone
├── contrib
├── docs
├── hadoop-0.20.3-dev-ant.jar
├── hadoop-0.20.3-dev-core.jar
├── hadoop-0.20.3-dev-examples.jar
├── hadoop-0.20.3-dev-streaming.jar
├── hadoop-0.20.3-dev-test.jar
├── hadoop-0.20.3-dev-tools.jar
├── ivy
├── ivy.xml
├── lib
├── LICENSE.txt
├── logs
├── NOTICE.txt
├── README.txt
├── src
└── webapps

• 修改hadoop的配置文件分别如下：
  • hadoop-env.sh，重点修改下$JAVA_HOME，指向SUN JDK或者OpenJDK的目录，Hadoop官方建议采用SUN（现在是Oracle啦）的JDK。
  • core-site.xml
  • hdfs-site.xml
  • mapred-site.xml

hadoop-env.sh

...
...

# The java implementation to use.  Required.
# export JAVA_HOME=/opt/java
export JAVA_HOME=/usr/lib/jvm/java-7-openjdk

...
...

core-site.xml

<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>

<!-- Put site-specific property overrides in this file. -->

<configuration>
    <property>
        <name>fs.default.name</name>
        <value>hdfs://localhost:9000</value>
    </property>
    <property>
        <name>fs.trash.interval</name>
        <value>1440</value>
    </property>
    <property>
        <name>hadoop.tmp.dir</name>
        <value>/home/lox/tmp/hadoop-data/tmp</value>
    </property>
</configuratione>

hdfs-site.xml

<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>

<!-- Put site-specific property overrides in this file. -->

<configuration>
    <property>
        <name>dfs.replication</name>
        <value>1</value>
    </property>
    <property>
        <name>dfs.name.dir</name>
        <value>/home/lox/tmp/hadoop-data/name</value>
        <final>true</final>
    </property>
    <property>
        <name>dfs.data.dir</name>
        <value>/home/lox/tmp/hadoop-data/data</value>
        <final>true</final>
    </property>
</configuration>

mapred-site.xml

<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>

<!-- Put site-specific property overrides in this file. -->

<configuration>
    <property>
        <name>mapred.job.tracker</name>
        <value>localhost:9001</value>
    </property>
    <property>
        <name>mapred.tasktracker.map.tasks.maximum</name>
        <value>5</value>
    </property>
    <property>
        <name>mapred.tasktracker.reduce.tasks.maximum</name>
        <value>5</value>
    </property>
    <property>
        <name>mapred.child.java.opts</name>
        <value>-Xmx512m</value>
    </property>
</configuration>

• 启动hadoop，如果能用Hadoop FS Shell做一些常规的mkdir和ls操作，Hadoop搭建就算大功告成了：

➜  ~  hadoop namenode -format 
12/02/15 00:07:23 INFO namenode.NameNode: STARTUP_MSG: 
/************************************************************
STARTUP_MSG: Starting NameNode
STARTUP_MSG:   host = lox-pad/127.0.0.1
STARTUP_MSG:   args = [-format]
STARTUP_MSG:   version = 0.20.3-dev
STARTUP_MSG:   build = http://svn.apache.org/repos/asf/hadoop/common/tags/release-0.20.2 -r 916569; compiled by 'lox' on Wed Nov  9 23:40:01 CST 2011
************************************************************/
Re-format filesystem in /home/lox/tmp/hadoop-data/name ? (Y or N) y
Format aborted in /home/lox/tmp/hadoop-data/name
12/02/15 00:07:25 INFO namenode.NameNode: SHUTDOWN_MSG: 
/************************************************************
SHUTDOWN_MSG: Shutting down NameNode at lox-pad/127.0.0.1
************************************************************/
➜  ~  start-all.sh 
starting namenode, logging to /home/lox/tmp/hadoop-v20/bin/../logs/hadoop-lox-namenode-lox-pad.out
localhost: starting datanode, logging to /home/lox/tmp/hadoop-v20/bin/../logs/hadoop-lox-datanode-lox-pad.out
localhost: starting secondarynamenode, logging to /home/lox/tmp/hadoop-v20/bin/../logs/hadoop-lox-secondarynamenode-lox-pad.out
starting jobtracker, logging to /home/lox/tmp/hadoop-v20/bin/../logs/hadoop-lox-jobtracker-lox-pad.out
localhost: starting tasktracker, logging to /home/lox/tmp/hadoop-v20/bin/../logs/hadoop-lox-tasktracker-lox-pad.out
➜  ~  jps   
21061 JobTracker
20852 DataNode
21255 Jps
20977 SecondaryNameNode
20764 NameNode
21156 TaskTracker
➜  ~  hadoop fs -mkdir /tmp/this-is-a-test-dir
➜  ~  hadoop fs -ls /tmp
Found 1 items
drwxr-xr-x   - lox supergroup          0 2012-02-15 00:08 /tmp/this-is-a-test-dir
➜  ~  

好了。基础工作已经准备好，在接下来的旅程中，我会初步讲解一下Hadoop的基本概念和使用方法，进而转入Lisp（Scheme）函数式编程的美妙世界，带你逐本溯源，领略一下原生态的Map和Reduce到底是什么模样，并且会顺带谈到一些我在Lisp学习过程中领略到的别样风景，包括但不限于Java的反射、序列化等一些高级特性，XML、JSON的数据语言的特性特点等等。敬请期待！

--