分布式并行编程

用Hadoop进行分布式并行编程,第1部分基本概念与安装部署曹羽中(mailto:[e-mail]?subject=用Hadoop进行分布式并行编程,第1部分),软件工程师,IBM中国开发中心2008年5月22日Hadoop是一个实现了MapReduce计算模型的开源分布式并行编程框架，借助于Hadoop,程序员可以轻松地编写分布式并行程序，将其运行于计算机集群上，完成海量数据的计算。本文将介绍MapReduce计算模型，分布式并行计算等基本概念，以及Hadoop的安装部署和基本运行方法。Hadoop简介Hadoop是一个开源的可运行于大规模集群上的分布式并行编程框架，由于分布式存储对于分布式编程来说是必不可少的，这个框架中还包含了一个分布式文件系统HDFS(HadoopDistributedFileSystem)。也许到目前为止，Hadoop还不是那么广为人知，其最新的版本号也仅仅是0.16，距离1.0似乎都还有很长的一段距离，但提及Hadoop一脉相承的另外两个开源项目Nutch和Lucene(三者的创始人都是DougCutting),那绝对是大名鼎鼎。Lucene是一个用Java开发的开源高性能全文检索工具包，它不是一个完整的应用程序，而是一套简单易用的API。在全世界范围内，已有无数的软件系统，Web网站基于Lucene实现了全文检索功能，后来DougCutting又开创了第一个开源的Web搜索引擎()Nutch,它在Lucene的基础上增加了网络爬虫和一些和Web相关的功能，一些解析各类文档格式的插件等，此外，Nutch中还包含了一个分布式文件系统用于存储数据。从Nutch0.8.0版本之后，DougCutting把Nutch中的分布式文件系统以及实现MapReduce算法的代码独立出来形成了一个新的开源项Hadoop。Nutch也演化为基于Lucene全文检索以及Hadoop分布式计算平台的一个开源搜索引擎。基于Hadoop,你可以轻松地编写可处理海量数据的分布式并行程序，并将其运行于由成百上千个结点组成的大规模计算机集群上。从目前的情况来看，Hadoop注定会有一个辉煌的未来：云计算是目前灸手可热的技术名词，全球各大IT公司都在投资和推广这种新一代的计算模式，而Hadoop又被其中几家主要的公司用作其云计算环境中的重要基础软件，如:雅虎正在借助Hadoop开源平台的力量对抗Google,除了资助Hadoop开发团队外，还在开发基于Hadoop的开源项目Pig,这是一个专注于海量数据集分析的分布式计算程序。Amazon公司基于Hadoop推出了AmazonS3(AmazonSimpleStorageService)，提供可靠，快速，可扩展的网络存储服务，以及一个商用的云计算平台AmazonEC2(AmazonElasticComputeCloud)。在IBM公司的云计算项目--蓝云计划中，Hadoop也是其中重要的基础软件。Google正在跟IBM合作，共同推广基于Hadoop的云计算。迎接编程方式的变革在摩尔定律的作用下，以前程序员根本不用考虑计算机的性能会跟不上软件的发展，因为约每隔18个月，CPU的主频就会增加一倍，性能也将提升一倍，软件根本不用做任何改变，就可以享受免费的性能提升。然而，由于晶体管电路已经逐渐接近其物理上的性能极限，摩尔定律在2005年左右开始失效了，人类再也不能期待单个CPU的速度每隔18个月就翻一倍，为我们提供越来越快的计算性能。Intel,AMD,IBM等芯片厂商开始从多核这个角度来挖掘CPU的性能潜力，多核时代以及互联网时代的到来，将使软件编程方式发生重大变革，基于多核的多线程并发编程以及基于大规模计算机集群的分布式并行编程是将来软件性能提升的主要途径。许多人认为这种编程方式的重大变化将带来一次软件的并发危机，因为我们传统的软件方式基本上是单指令单数据流的顺序执行，这种顺序执行十分符合人类的思考习惯，却与并发并行编程格格不入。基于集群的分布式并行编程能够让软件与数据同时运行在连成一个网络的许多台计算机上,这里的每一台计算机均可以是一台普通的PC机。这样的分布式并行环境的最大优点是可以很容易的通过增加计算机来扩充新的计算结点，并由此获得不可思议的海量计算能力,同时又具有相当强的容错能力，一批计算结点失效也不会影响计算的正常进行以及结果的正确性。Google就是这么做的，他们使用了叫做MapReduce的并行编程模型进行分布式并行编程，运行在叫做GFS(GoogleFileSystem)的分布式文件系统上，为全球亿万用户提供搜索服务。Hadoop实现了Google的MapReduce编程模型，提供了简单易用的编程接口，也提供了它自己的分布式文件系统HDFS,与Google不同的是，Hadoop是开源的，任何人都可以使用这个框架来进行并行编程。如果说分布式并行编程的难度足以让普通程序员望而生畏的话，开源的Hadoop的出现极大的降低了它的门槛，读完本文，你会发现基于Hadoop编程非常简单，无须任何并行开发经验，你也可以轻松的开发出分布式的并行程序，并让其令人难以置信地同时运行在数百台机器上，然后在短时间内完成海量数据的计算。你可能会觉得你不可能会拥有数百台机器来运行你的并行程序，而事实上，随着云计算的普及，任何人都可以轻松获得这样的海量计算能力。例如现在Amazon公司的云计算平台AmazonEC2已经提供了这种按需计算的租用服务，有兴趣的读者可以去了解一下，这篇系列文章的第三部分将有所介绍。掌握一点分布式并行编程的知识对将来的程序员是必不可少的，Hadoop是如此的简便好用，何不尝试一下呢？也许你已经急不可耐的想试一下基于Hadoop的编程是怎么回事了，但毕竟这种编程模型与传统的顺序程序大不相同，掌握一点基础知识才能更好地理解基于Hadoop的分布式并行程序是如何编写和运行的。因此本文会先介绍一下MapReduce的计算模型，Hadoop中的分布式文件系统HDFS,Hadoop是如何实现并行计算的，然后才介绍如何安装和部署Hadoop框架，以及如何运行Hadoop程序。MapReduce计算模型MapReduce是Google公司的核心计算模型，它将复杂的运行于大规模集群上的并行计算过程高度的抽象到了两个函数，Map和Reduce,这是一个令人惊讶的简单却又威力巨大的模型。适合用MapReduce来处理的数据集(或任务)有一个基本要求:待处理的数据集可以分解成许多小的数据集，而且每一个小数据集都可以完全并行地进行处理。图1.MapReduce计算流程图一说明了用MapReduce来处理大数据集的过程,这个MapReduce的计算过程简而言之，就是将大数据集分解为成百上千的小数据集，每个(或若干个)数据集分别由集群中的一个结点(一般就是一台普通的计算机)进行处理并生成中间结果，然后这些中间结果又由大量的结点进行合并,形成最终结果。计算模型的核心是Map和Reduce两个函数，这两个函数由用户负责实现，功能是按一定的映射规则将输入的key,value对转换成另一个或一批key,value对输出。表一Map和Reduce函数函数输入输出说明Mapk1,v1List(k2,v2)1.将小数据集进一步解析成一批key,value对，输入Map函数中进行处理。2.每一个输入的k1,v1会输出一批k2,v2。k2,v2是计算的中间结果。Reducek2,List(v2)k3,v3输入的中间结果k2,List(v2)中的List(v2)表示是一批属于同一个k2的value以一个计算文本文件中每个单词出现的次数的程序为例，k1,v1可以是行在文件中的偏移位置,文件中的一行，经Map函数映射之后，形成一批中间结果单词，出现次数,而Reduce函数则可以对中间结果进行处理，将相同单词的出现次数进行累加，得到每个单词的总的出现次数。基于MapReduce计算模型编写分布式并行程序非常简单，程序员的主要编码工作就是实现Map和Reduce函数，其它的并行编程中的种种复杂问题，如分布式存储，工作调度，负载平衡，容错处理，网络通信等，均由MapReduce框架(比如Hadoop)负责处理，程序员完全不用操心。四集群上的并行计算MapReduce计算模型非常适合在大量计算机组成的大规模集群上并行运行。图一中的每一个Map任务和每一个Reduce任务均可以同时运行于一个单独的计算结点上，可想而知其运算效率是很高的，那么这样的并行计算是如何做到的呢？数据分布存储Hadoop中的分布式文件系统HDFS由一个管理结点(NameNode)和N个数据结点(DataNode)组成，每个结点均是一台普通的计算机。在使用上同我们熟悉的单机上的文件系统非常类似，一样可以建目录，创建，复制，删除文件，查看文件内容等。但其底层实现上是把文件切割成Block，然后这些Block分散地存储于不同的DataNode上，每个Block还可以复制数份存储于不同的DataNode上，达到容错容灾之目的。NameNode则是整个HDFS的核心，它通过维护一些数据结构，记录了每一个文件被切割成了多少个Block，这些Block可以从哪些DataNode中获得，各个DataNode的状态等重要信息。如果你想了解更多的关于HDFS的信息，可进一步阅读参考资料：TheHadoopDistributedFileSystem:ArchitectureandDesign分布式并行计算Hadoop中有一个作为主控的JobTracker，用于调度和管理其它的TaskTracker,JobTracker可以运行于集群中任一台计算机上。TaskTracker负责执行任务，必须运行于DataNode上，即DataNode既是数据存储结点，也是计算结点。JobTracker将Map任务和Reduce任务分发给空闲的TaskTracker,让这些任务并行运行，并负责监控任务的运行情况。如果某一个TaskTracker出故障了，JobTracker会将其负责的任务转交给另一个空闲的TaskTracker重新运行。本地计算数据存储在哪一台计算机上，就由这台计算机进行这部分数据的计算，这样可以减少数据在网络上的传输，降低对网络带宽的需求。在Hadoop这样的基于集群的分布式并行系统中，计算结点可以很方便地扩充，而因它所能够提供的计算能力近乎是无限的，但是由是数据需要在不同的计算机之间流动，故网络带宽变成了瓶颈，是非常宝贵的，“本地计算”是最有效的一种节约网络带宽的手段，业界把这形容为“移动计算比移动数据更经济”。图2.分布存储与并行计算任务粒度把原始大数据集切割成小数据集时，通常让小数据集小于或等于HDFS中一个Block的大小(缺省是64M)，这样能够保证一个小数据集位于一台计算机上，便于本地计算。有M个小数据集待处理，就启动M个Map任务，注意这M个Map任务分布于N台计算机上并行运行，Reduce任务的数量R则可由用户指定。Partition把Map任务输出的中间结果按key的范围划分成R份(R是预先定义的Reduce任务的个数)，划分时通常使用hash函数如:hash(key)modR，这样可以保证某一段范围内的key，一定是由一个Reduce任务来处理，可以简化Reduce的过程。Combine在partition之前，还可以对中间结果先做combine，即将中间结果中有相同key的key,value对合并成一对。combine的过程与Reduce的过程类似，很多情况下就可以直接使用Reduce函数，但combine是作为Map任务的一部分，在执行完Map函数后紧接着执行的。Combine能够减少中间结果中key,value对的数目，从而减少网络流量。Reduce任务从Map任务结点取中间结果Map任务的中间结果在做完Combine和Pa