技术开发 频道

Hadoop并行计算原理与分布式并发编程

        【IT168 技术】我们通常说的分布式系统其实是分布式软件系统,即支持分布式处理的软件系统,它是在通信网络互联的多处理机体系结构上执行任务的,包括分布式操作系统、分布式程序设计语言及其编译(解释)系统、分布式文件系统和分布式数据库系统等。Hadoop是分布式软件系统中文件系统这一层的软件,它实现了分布式文件系统和部分分布式数据库的功能。Hadoop中的分布式文件系统HDFS能够实现数据在计算机集群组成的云上高效的存储和管理,Hadoop中的并行编程框架MapReduce能够让用户编写的Hadoop并行应用程序运行更加简化。下面简单介绍一下基于Hadoop进行分布式并发编程的相关知识:

  Hadoop上的并行应用程序开发是基于MapReduce编程框架的。MapReduce编程模型的原理是:利用一个输入的key/value 对集合来产生一个输出的key/value 对集合。MapReduce库的用户用两个函数来表达这个计算:Map和Reduce。

  用户自定义的map函数接收一个输入的key/value 对,然后产生一个中间key/value 对的集合。MapReduce把所有具有相同key值的value集合在一起,然后传递给reduce函数。

  用户自定义的reduce函数接收key和相关的value集合。reduce函数合并这些value值,形成一个较小的value集合。一般来说,每次reduce函数调用只产生0或1个输出的value值。通常我们通过一个迭代器把中间的value值提供给reduce 函数,这样就可以处理无法全部放入内存中的大量的value值集合了。

  下图是MapReduce的数据流图,这个过程简而言之就是将大数据集分解为成百上千个小数据集,每个(或若干个)数据集分别由集群中的一个节点(一般就是一台普通的计算机)进行处理并生成中间结果,然后这些中间结果又由大量的节点合并,形成最终结果。下图也指出了MapReduce框架下并行程序中的三个主要函数:map、reduce、main。在这个结构中,需要用户完成的工作仅仅是根据任务编写map和reduce两个函数。

Hadoop与分布式开发
▲图 MapReduce的数据流图

  MapReduce计算模型非常适合在大量计算机组成的大规模集群上并行运行。上图中的每一个map 任务和每一个reduce 任务均可以同时运行于一个单独的计算节点上,可想而知,其运算效率是很高的,那么这样的并行计算是如何做到的呢?下面将简单介绍一下其原理。

  1.数据分布存储

  Hadoop分布式文件系统(HDFS)由一个名称节点(NameNode )和N个数据节点 (DataNode)组成,每个节点均是一台普通的计算机。在使用方式上HDFS与我们熟悉的单机文件系统非常类似,它可以创建目录,创建、复制和删除文件,以及查看文件的内容等。但HDFS底层把文件切割成了Block,然后这些 Block 分散地存储于不同的 DataNode 上,每个 Block 还可以复制数份数据存储于不同的 DataNode 上,达到容错容灾的目的。NameNode 则是整个 HDFS 的核心,它通过维护一些数据结构来记录每一个文件被切割成了多少个 Block、这些 Block 可以从哪些 DataNode 中获得,以及各个 DataNode 的状态等重要信息。

  2. 分布式并行计算

  Hadoop 中有一个作为主控的 JobTracker,用于调度和管理其他的 TaskTracker,JobTracker 可以运行于集群中的任意一台计算机上。TaskTracker则负责执行任务,它必须运行于 DataNode 上,也就是说DataNode 既是数据存储节点,也是计算节点。 JobTracker 将 map 任务和 reduce 任务分发给空闲的 TaskTracker,让这些任务并行运行,并负责监控任务的运行情况。如果某一个 TaskTracker 出了故障,JobTracker 会将其负责的任务转交给另一个空闲的 TaskTracker 重新运行。

  3. 本地计算

  数据存储在哪一台计算机上,就由哪台计算机进行这部分数据的计算,这样可以减少数据在网络上的传输,降低对网络带宽的需求。在 Hadoop 这类基于集群的分布式并行系统中,计算节点可以很方便地扩充,它所能够提供的计算能力近乎无限,但是由于数据需要在不同的计算机之间流动,故网络带宽变成了瓶颈,“本地计算”是一种最有效的节约网络带宽的手段,业界把这形容为“移动计算比移动数据更经济”。

  4. 任务粒度

  把原始大数据集切割成小数据集时,通常让小数据集小于或等于 HDFS 中一个 Block 的大小(默认是64MB),这样能够保证一个小数据集是位于一台计算机上的,便于本地计算。有 M 个小数据集待处理,就启动 M 个 map 任务,注意这 M 个map 任务分布于 N 台计算机上,它们会并行运行,reduce 任务的数量 R 则可由用户指定。

  5. 数据分割(Partition)

  把 map 任务输出的中间结果按 key 的范围划分成R份(R是预先定义的reduce 任务的个数),划分时通常使用 hash 函数(如:hash(key) mod R),这样可以保证某一范围内的 key一定是由一个 reduce 任务来处理的,可以简化 Reduce 的过程。

  6. 数据合并(Combine)

  在数据分割之前,还可以先对中间结果进行数据合并(Combine),即将中间结果中有相同 key的 对合并成一对。Combine 的过程与reduce 的过程类似,很多情况下可以直接使用reduce 函数,但 Combine 是作为map 任务的一部分,在执行完map函数后紧接着执行的。Combine 能够减少中间结果中 对的数目,从而降低网络流量。

  7. Reduce

  Map 任务的中间结果在做完 Combine 和 Partition 之后,以文件形式存于本地磁盘上。中间结果文件的位置会通知主控 JobTracker,JobTracker 再通知 reduce 任务到哪一个 DataNode 上去取中间结果。注意,所有的map 任务产生的中间结果均按其key 值用同一个 hash 函数划分成了R份,R个reduce 任务各自负责一段key 区间。每个reduce 需要向许多个map 任务节点取得落在其负责的key 区间内的中间结果,然后执行reduce函数,形成一个最终的结果文件。

  8. 任务管道

  有 R 个 reduce 任务,就会有 R 个最终结果,很多情况下这 R 个最终结果并不需要合并成一个最终结果,因为这 R 个最终结果又可以作为另一个计算任务的输入,开始另一个并行计算任务,这也就形成了任务管道。

  这里简要介绍了在并行编程方面Hadoop中MapReduce编程模型的原理、流程、程序结构和并行计算的实现,MapReduce程序的详细流程、编程接口、程序实例等请参见后面章节。

  作者简介

  陆嘉恒,《Hadoop实战》作者,中国人民大学副教授,新加坡国立大学博士,美国加利福尼亚大学尔湾分校(University of California, Irvine) 博士后。

0
相关文章