行者无疆 始于足下 - 行走，思考，在路上

闲谈MapReduce(1): Hadoop初探

1 缘起

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

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

我第一次听说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道习题左右，不过即便如此，也令我受益匪浅4。半年Lisp的学习让我搞明白了MapReduce中，Map和Reduce的来龙去脉。这个问题我Google了很久，但是始终没有一个满意的答案，现如今，我自己找到了满意的答案。

2 抽象漏洞（兼谈数学和计算机工程）

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

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

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

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

3 Let's Go

以上，废话了这么多，所要强调的无非就是，了解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!

4 Hadoop

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

--

Footnotes:

1 第29次中国互联网络发展状况统计报告显示，2012年初，中国网民共计5.13亿。

2 关于这个定义的出处可以参考弯曲评论上一篇非常好的关于云计算的科普文章“云里雾里云计算”，本文不打算探讨云计算的社会意义、产业变革、安全等过于宏大的主题（其实我对这些一点都不了解）。

3 MapReduce的第一篇论文"MapReduce: Simplified Data Processing on Large Clusters"曾写到："Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages."可见，MapReduce的思想来自于古老的Lisp语言。

4 广告一下，在我有限的阅读经历中，《SICP》是我读过的计算机书籍中最棒的一本，没有之一。如果能认真做完这本书里面的356道题目，绝对会让你对编程本质的理解有一个脱胎换骨般的提高。这里有我个人的部分习题解答代码和学习笔记。

5 关于这一点，刘未鹏的《知其所以然》系列文章里有更好的解读，我就不再重复了。

6 参考程序员的自我修养。

7 参考费马大定理 : 一个困惑了世间智者358年的谜。

8 据《Unix编程艺术》的序言里的脚注：“从1969年到2003年，35年世间并不短。以这期间众多Unix站点数量的历史曲线来估算，人们在Unix系统的开发方面投入了约5000万人年”。

9 这原本是Brooks's Law的一种观点。

 

CloudComputing Scheme MapReduce lisp Hadoop Comments(4) Wed, 15 Feb 2012 00:47:51 +0800

Learning SICP: (sqrt 2.0)

接触计算机也算四年有余，对自己的所学所知却毫无信心。回头看了看以前写过的很多文章，诸如配置IDE环境啦、配置Linux操作系统啦、零零散散的小程序啦，等等诸如此类，不成体系，都是在小打小闹。因此我决定，在可以预见的几年内，一方面做好百度份内的工作，赚一点养家糊口的钱；另一方面也要从基础做起，一点一点地夯实自己的技术实力。技术是基础，无论是以后创业，还是继续在程序员的行业里面模爬滚打，扎实的技术都是一个必备的条件。Google的创始人曾经说过，要成为一个企业家，需要“Be an expert in all aspects”，而一个公司赖以生存的基础，除了良好的营销、管理，最最基本的还是需要有能拿的出手的产品，而产品的基础就是技术。所以我从来不赞成“码农没有前途”等等诸如此类的说法，这样说的人，多半自己不是一个合格的码农，又或是对IT互联网本身就没有深刻的理解，信口雌黄罢了。

人类生存于世的一大乐趣就是自己制造工具，能否制造工具也是人类之所以成为万物之灵的根本。而学计算机的一大好处就是可以方便地、随心所欲地制造自己想要的工具，没有想不到，只有做不到，工具的级别取决于程序员的技术能力。譬如Fabrice Bellard就用JavaScript写了一个PC模拟器，可以在浏览器里面跑Linux，而此君的其他作品，诸如ffmpeg、qemu、tinycc，在开源社区几乎是无人不知无人不晓。

学计算机的一大好处就是经典教材诸如SICP、CSAPP、TAOCP、龙书、虎书等等数不胜数，思忖再三，决定还是以MIT经典的那本SICP开始。关于SICP的具体内容我不再多言，Wikipedia一查便知。让我沉思的两点是，这本书是MIT大一新生学习计算机的第一门课，也就是计算机的导论课程，而这样一门大一新生的导论课程，在两百多页的教材中，确涉及到了图灵机理论、递归算法、lambda算子等等诸多关于编程本质的知识，不得不感叹MIT课程的高质量，同样作为国内高校翘楚的浙江大学，大一新生恐怕还都在背诵C语言各种符号的优先级，还在古老的Turbo C 2.0上写着古老的graphics.h程序呢；第二，这本书长盛不衰几十年，被数百所大学选为计算机系的教材，并且对计算机教育产生了深远的影响，国内有那本教材能够达到这样的境界？谭浩强的？严尉敏的？都不是。除了教材本身，作者的态度，还有配套的相关资料，以及由此推动的深入挖掘和研究才是最重要的。SICP的作者Gerald J. Sussman同时也是Scheme语言的发明人之一。

利用晚上和周末空余的时间，断断续续地看完了SICP第一章的大半部分，还有前面的几段讲义和视频。讲义中的有一个求方根的程序：

#!/usr/bin/guile -s
!#

(define square
  (lambda (x)
    (* x x)))

(define average 
  (lambda (x y)
    (* (+ x y) 0.5)))

(define close-enuf?
  (lambda (guess x)
    (< (abs (- (square guess) x)) 0.001)))

(define improve
  (lambda (guess x)
    (average guess (/ x guess))))

(define sqrt-loop 
  (lambda (G X)
    (if (close-enuf? G X)
      G
      (sqrt-loop (improve G X) X))))

(define sqrt
  (lambda (x)
    (sqrt-loop 1.0 x)))

;;(display (sqrt 2))
;;(newline)

短短几行，几乎涵盖了二分法的精髓。程序就是数据，函数本身可以当数据来操作，本身就蕴涵着深刻的和谐统一的数学美。

其实学习这个东西就像武侠小说里的武功，公式技巧编程语言都是花拳秀腿，对整个学科体系的理解、数学的功底才是精深的内功，是一切上乘武功的根基。由此我又想到一个人的工作的价值。私以为，一个人的价值（也可以说是薪水），是以这个人的不可替代性来衡量的。如果你现在走掉，而你的老板随随便便就能找一个人来顶替你的岗位，那么你做的工作是可替代性非常高的工作，自然薪水也不会太高；反之亦然。

ps：写博客写到一半的时候is-programmer忽然挂掉，所以出现了半截文章。看来我也该考虑考虑租一个独立的虚拟主机或者VPS了。

Lisp Scheme SICP Comments(16) Tue, 30 Aug 2011 23:46:27 +0800




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee