持续更新的数据集。 表1-1.关系型数据库和MapReduce的比较 传统的关系型数据库 MapReduce 数据大小 GB PB 数据存取 交互式和批处理 批处理 更新 多次读/写 一次写人，多次读取 结构 静态模式 动态模式 完整性 高 低 横向扩展 非线性的 线性的 MapReduce和关系型数据库之间的另一个区别在于它们所操作的数据集的 结构化程度。结构化数据(structured data)是具有既定格式的实体化数据，如 XML文档或满足特定预定义格式的数据库表。这是RDBMS包括的内容。 另一方面，半结构化数据(semi-structured data)比较松散，虽然可能有格 式，但经常被忽略，所以它只能作为对数据结构的一般性指导。例如电子 表格，它在结构上是由单元格组成的网格，但是每个单元格内可以保存任 何形式的数据。非结构化数据(unstructured data)没有什么特别的内部结构， 例如纯文本或图像数据。MapReduce对非结构化或半结构化数据非常有 效，因为它是在处理数据时才对数据进行解释。换句话说，MapReduce输 入的键和值并不是数据固有的属性，而是由分析数据的人来选的。 关系型数据往往是规范的(normalized),以保持其数据的完整性且不含冗 余。规范给MapReduce带来了问题，因为它使记录读取成为非本地操作， 而MapReduce的核心假设之一偏偏就是可以进行（高速的）流读写操作。 Wb服务器日志是典型的非规范化数据记录（例如，每次都需要记录客户端 主机全名，这会导致同一客户端的全名可能多次出现)，这也是MapReduce 非常适用于分析各种日志文件的原因之一。 MapReduce是一种线性的可伸缩编程模型。程序员要写两个函数，分别为 map函数和reduce函数，每个函数定义从一个键值对集合到另一个键值对 集合的映射。这些函数不必关注数据集及其所用集群的大小，可以原封不 动地应用于小规模数据集或大规模的数据集。更重要的是，如果输入的数 据量是原来的两倍，那么运行时间也需要两倍。但如果集群是原来的两 倍，作业的运行速度却仍然与原来一样快。SQL查询一般不具备该特性。 6 第1章
但是，在不久的将来，关系型数据库系统和MapReduce系统之间的差异很 可能变得模糊。关系型数据库都开始吸收MapReduce的一些思路（如Aster Data的数据库和GreenPlum的数据库)，另一方面，基于MapReduce的高 级查询语言（如Pig和Hive)使传统数据库的程序员更容易接受MapReduce 系统。① 1.3.2网格计算 高性能计算(High Performance Computing,HPC)和网格计算(Grid Computing) 组织多年以来一直在研究大规模数据处理，主要使用类似于消息传递接口 (Message Passing Interface,MPI)的API。从广义上讲，高性能计算采用的 方法是将作业分散到集群的各台机器上，这些机器访问存储区域网络(SAN) 所组成的共享文件系统。这比较适用于计算密集型的作业，但如果节点需 要访问的数据量更庞大（高达几百GB,MapReduce开始施展它的魔法）， 很多计算节点就会因为网络带宽的瓶颈问题不得不闲下来等数据。 MapReduc尽量在计算节点上存储数据，以实现数据的本地快速访问。⑧数 据本地化(data locality)特性是MapReduce的核心特征，并因此而获得良好 的性能。意识到网络带宽是数据中心环境最珍贵的资源（到处复制数据很容 易耗尽网络带宽)之后，MapReduce通过显式网络拓扑结构来保留网络带 宽。注意，这种排列方式并没有降低MapReduce对计算密集型数据进行分 析的能力。 ①2007年1月，数据库理论专家David J.DeWitt和Michael Stonebraker发表的论文引 发一场激烈的口水大战，论文标题为“MapReduce:A major step backwards” (MapReduce:一个巨大的倒退)，原文可参见http:/∥databasecolumn,vertica.com/ database-innovation/napreduce a-major-siep-backwards,中文版可参考http:/hwap. oschina.net/question/1779331108)。在文中，他们认为MapReduce不宜取代关系型 数据库。许多评论认为这是一种错误的比较，详情可参见Mark C.Chu-Carroll的 文章“Databasesare hammers;MapReduce is a screwdriver'”(如果说数据库是锤子， MapReduce则是螺丝刀)，英文版网址为http://scienceblogs.com/goodmath/2008/0i databases_are_hammers_mapreduc..php,中文版可以参考http:/blog.csdn.net/ wanghai/article/details/.5g54IO8。DeWitt与Stonebraker以“再说MapReduce”一文 对其他人的观点进行了阐述，原文可参见htp:da1 abasecolumn.vertica.com/database- innovation/mapreduce-ii,他们对其他人的主要观点进行了阐述。 ②1998年图灵奖得主Jim Gray在2003年3月发表的“Distributed Computing Economics'”(分布式计算经济学)一文中，率先提出这个结论：数据处理应该在离数 据本身比较近的地方进行，因为这样有利于降低成本，尤其是网络带宽消费所造成 的成本。原文网址为htip://research.microsoft.com/apps/pubs/default..aspx?id=7000l。 初识Hadoop
虽然MPI赋予程序员很大的控制权，但需要程序员显式控制数据流机制， 包括用C语言构造底层的功能模块（例如套接字）和高层的数据分析算法。 而MapReduce则在更高层次上执行任务，即程序员仅从键值对函数的角度 考虑任务的执行，而且数据流是隐含的。 在大规模分布式计算环境下，协调各个进程的执行是一个很大的挑战。最 困难的是合理处理系统的部分失效问题一在不知道一个远程进程是否挂了 的情况下一同时还需要继续完成整个计算。有了MapReduce,程序员不必 操心系统部分失效的问题，因为它自己的系统实现能够检测到并重新执行 那些失败的map或reduce任务。正因为采用的是无共享(shared-nothing)框 架，MapReduce才能够实现失败检测，这意味着各个任务之间是彼此独立 的。因此，从程序员的角度来看，任务的执行顺序无关紧要。相比之下， MPI程序必须显式管理自己的检查点和恢复机制，虽然赋予程序员的控制 权加大了，但编程的难度也增加了。 MapReduce听起来似乎是一个相当严格的编程模型，而且在某种意义上看 的确如此：限定用户使用有特定关联的键值对，mapper和reducer彼此间的 协调非常有限（每个mapper将键值对传给reducer)。由此，我们自然联想到 一个问题：能用这个编程模型做一些有用或实际的事情吗？ 答案是肯定的。MapReduce由谷歌的工程师开发，用于构建搜索引擎的索 引，而且，事实已经证明它能够一次又一次地解决这个问题(MapReduce的 灵感来自于传统的函数式编程、分布式计算和数据库社区)，但此后，该模 型在其他行业还有着很多其他的应用。我们欣喜地发现，有很多算法都可 以用MapReduce来表达，从图像图形分析到各种各样基于图像分析的问 题，再到机器学习算法。“当然，它也不是包治百病的灵丹妙药，不能解决 所有问题，但它真的是一个很通用的数据处理工具。 我们将在第16章介绍Hadoop的一些典型应用。 ①这里讲得太简单了一点，因为MapReduce系统本身控制着mapper输出结果传给 reducer的过程，所以在这种情况下，重新运行reducer比重新运行mapper更要小 心，因为reducer需要获取必要的mapper输出结果，如果没有，必须再次运行对应 的mapper,.重新生成输出结果。 ②Apache Mahout(http:/∥nahout..apache.org/是一个在Hadoop上运行的机器学习类库 (例如分类和聚类算法)。 8 第1章
1.3.3 志愿计算 人们第一次听说Hadoop和MapReduce的时候，经常会问这个问题：“它们和 SETI@home有什么不同？”SETI全称为Search for Extra-Terrestrial Intelligence(搜 索外星智能)，项目名称为SETI@home(http://setiathome.berkeley.ed,)。在该 项目中，志愿者把自己计算机CPU的空闲时间贡献出来分析无线天文望远 镜的数据，借此寻找外星智慧生命信号。SETI@home因为拥有庞大的志愿 者队伍而非常出名，其他还有“搜索大素数”(Great Internet Mersenne Prime Search)项目与Folding(@home项目（了解蛋白质构成及其与疾病之间的 关系)。 志愿计算项目将问题分成很多块，每一块称为一个工作单元(work unit),发 到世界各地的计算机上进行分析。例如，SETI@home的工作单元是0.35 MB无线电望远镜数据，要对这等大小的数据量进行分析，一台普通计算机 需要几个小时或几天时间才能完成。完成分析后，结果发送回服务器，客 户端随后再获得另一个工作单元。为防止欺骗，每个工作单元要发送到3 台不同的机器上执行，而且收到的结果中至少有两个相同才会被接受。 从表面上看，SETI@home与MapReduce好像差不多（将问题分解为独立的 小块，然后并行进行计算)，但事实上还是有很多明显的差异。SETI@home 问题是CPU高度密集的，比较适合在全球成千上万台计算机上运行，因 为计算所花的时间远远超过工作单元数据的传输时间。也就是说，志愿者 贡献的是CPU周期，而不是网络带宽。 MapReduce有三大设计目标：(I)为只需要短短几分钟或几个小时就可以完 成的作业提供服务；(2)运行于同一个内部有高速网络连接的数据中心内： (3)数据中心内的计算机都是可靠的、定制的硬件。相比之下，SETI@home 则是在接入互联网的不可信的计算机上长时间运行，这些计算机的网络带宽 不同，对数据本地化也没有要求。 ①2008年1月，SETI@home发表评论说每天使用320000台计算机处理300GB数 据，同时他们也在做其他的一些数据计算，原文参见http://www.planetary.org/programs/. projects/setiathome/setiathome_20080115. 初识Hadoop 9
1.4 Hadoop发展简史 Hadoop是Apache Lucene创始人Doug Cutting创建的，Lucene是一个应用 广泛的文本搜索系统库。Hadoop起源于开源的网络搜索引擎Apache Nutch,它本身也是Lucene项目的一部分。 Hadoop的得名 Hadoop不是缩写，它是一个生造出来的词。Hadoop之父Doug Cutting 这样解释Hadoop的来历： “这个名字是我的小孩给他的毛绒象玩具取的。我的命名标准 是好拼读，含义宽泛，不会被用于其他地方。小孩子是这方面 的高手。G00g0l就是小孩子起的名字。” Hadoop的子项目及后续模块所使用的名称也往往与其功能不相关，通常 也以大象或其他动物为主题取名（例如Pg)。较小一些的组件，名称通常 都有较好的描述性（因此也更流俗）。这个原则很好，意味着我们可以望文 知义，例如jobtracker",一看就知道它是用来跟踪MapReduce作业的。 从头打造一个网络搜索引擎是一个雄心勃勃的计划，不只是因为写爬虫程 序很复杂，更因为必须有一个专职团队来实现一项目中包含许许多多需要随 时修改的活动部件。同时，构建这样的系统代价非常高一据Mike Cafarella 和Doug Cutting估计，一个支持10亿网页的索引系统，单是硬件上的投入 就高达50万美元，另外还有每月高达3万美元的运维费用。①不过，他们 认为这个工作仍然值得投入，因为它开创的是一个优化搜索引擎算法的 平台。 Nutch项目开始于2002年，一个可以运行的网页爬取工具和搜索引擎系统 很快面试。但后来，开发者认为这一架构的灵活性不够，不足以解决数十 亿网页的搜索问题。一篇发表于2003年的论文为此提供了帮助，文中描述 ①在本书中我们使用小写的jobtracker来代表实体（泛称），用驼峰体JobTracker来表 示对Java类的实现。 ②Mike Cafarella和Doug Cutting在2004年4月发表在ACM Queue上的文章“Building Nutch::Open Source Search”,网址为http:/queue.acm.org/detail..cfim?id=988408。 10 第1章