论文部分内容阅读
摘 要： MapReduce是一种高效的分布式并行计算架构，但对于大规模图数据的处理来说它并不是有效的解决方案。本文结合图数据的特点，对MapRedue基本架構进行调整与改进，用于对大规模图数据的计算与处理，并取得了良好的效果。
关键词： MapReduce；图数据；并行计算；云计算
【中图分类号】 TP391. 4 【文献标识码】 A【文章编号】 2236-1879（2018）09-0012-01
1. 引言
Google提出了一种实现分布式计算的并行框架MapReduce，它基于由通用机器组成的大规模集群，进行数据处理任务，可以将用户的业务程序和集群的分布式处理机制进行隔离，使用户只关注自己的应用程序设计即可，而并行任务的数据切割、调度、节点通信、系统容错等功能均有框架来完成，通过它处理海量数据，是一种非常有效的方式。但是对于需要进行多次迭代的算法，例如图的最短路径算法、PageRank算法等，如果使用MapReduce框架来处理，由于在两次迭代之间是以分布式文件作为数据传递接口，所以效率很低[1，2]。因此，为了提高图数据算法等大数据量的迭代处理效率，需要对MapReduce框架进行调整与改进。
2. 系统总体架构
整个系统基于Hadoop集群环境运行，即在基于通用机器节点和普通磁盘的集群环境下，利用其分布式文件系统HDFS，或者是Hbase数据库系统存储待处理海量图数据。
其中，为了增加系统的普适性，设计支持多种方式的数据存储。例如，基于单个文件的、基于分布式文件系统（如HDFS）、以及基于数据库（关系的或非关系的）的存储。存储在外部存储介质上的数据通过并行数据加载模块（Parallel Data Loader）将数据加载到各个计算节点。整个系统的核心是计算引擎部分，负责实现数据划分、任务调度、集群通信、容错控制、集群维护、以及对外接口等。
3. 系统计算引擎
计算引擎是整个系统的核心，它由任务调度、数据划分、集群通信、集群维护、Barrier同步、容错控制等模块组成。
（1）任务调度。平台支持多用户操作模式，任务调度模块对多个用户提交的各个Job进行调度执行。系统设计提供几种默认的调度策略，包括FIFO、公平调度、计算能力调度等调度算法。系统提供调度策略设置接口，用户可以根据自己的实际需求类型，设置适合自己应用的调度策略。
（2）数据划分。经过数据输入输出模块将待处理的数据从HDFS、HBase等读取出来以后，数据划分模块将待处理的数据按照一定的规则进行划分并生成多个partition数据分片，并且分配到集群的每一个Worker节点之上，每一个partition数据分片由一个任务来处理。在对图数据的每一个partition进行迭代处理的时候，为了方便地查找每一个图顶点所在的partition位置，以便在消息通信阶段快速查找每一个图顶点的出度顶点所属的partition，数据划分模块需要将待处理的数据进行有效划分并对partition进行有效的管理。系统默认实现基于Hash和Range的图顶点划分方式，另外提供可扩展的接口支持用户自定义的顶点划分方式。
（3）集群通信。消息通信机制是模型中必不可少的部分。在任务进行中，每一个worker都可以与其他的任意个worker进行通信，向它们发送消息和接收由其他worker发来的消息。并且，发送和接收消息的数量也是任意的。消息通信机制主要涉及的问题包括消息的表示、消息的缓存机制、消息的发送接收机制等。
（4）Barrier同步。同步处理是图数据处理中的一个关键步骤。系统模型由一系列的超步组成，在每个超步中，各个Worker并行的进行本地计算处理和通信，由于各个Worker的执行速度不统一，所以最后需要通过Barrier同步，确保所有的Worker都完成了当期的超步，然后由模型的主节点启动下一个超步。在本系统模型中，一个作业被分成多个Task，这些Task被分配到各个Worker上执行，一个Worker可能被分配0至多个Task。所以严格来讲，在本模型中，Barrier同步的最小单位是Task，而不是Worker。
（5）容错控制。在大规模集群中，节点的失效是常有的，包括CPU的故障和磁盘故障。因此如何能够容忍这些失效的出现，并能够及时地采取补救措施，是模型实现中需要解决的问题。MapReduce模型采用磁盘文件暂存Map的计算结果，就是考虑到故障恢复容易实现。而本文系统模型的一大特点，就是处理结果常驻内存，从而减少磁盘IO，提高迭代性能。在不通过磁盘保存上一次迭代结果的情况下，快速地处理故障就成为一个很有挑战性的问题，关系到系统的稳定性和实用性。
4. 图数据云平台的实现
本文提出的大规模图数据云计算平台基于Hadoop平台实现。Hadoop是由Apache开源社区基于Java语言开发出的一个MapReduce并行架构实现，它提供了由通用计算设备组成的大规模集群上执行分布式应用的并行框架。本文基于Hadoop集群对图数据云计算平台进行了实现，平台的测试运行环境是：实验集群包含20个服务器节点，每个节点为4个2.00GHz Intel Xeon（R） CPU、8G内存的服务器，操作系统为Linux Red Hat 5.1操作系统，Java开发包为JDK8版本，Hadoop版本为2.5.0。
5. 结束语
本文通过对基本的MapReduce架构进行调整与改进，研究并实现了用于大规模图数据处理的云计算解决方案，并基于此建立了图数据云计算平台，为大规模图数据的并行处理探索了有效的道路，具有一定的实际应用意义和理论研究价值。
参考文献
[1] 于戈. 云计算环境下的大规模图数据处理技术[J]. 计算机学报， 2011， 10：1753-1767.
[2] 廖松博. GCPR：一种在MapReduce平台上基于图划分的PageRank加速方法[J]. 小型微型计算机系统， 2012， 6：1195-1201.
关键词： MapReduce；图数据；并行计算；云计算
【中图分类号】 TP391. 4 【文献标识码】 A【文章编号】 2236-1879（2018）09-0012-01
1. 引言
Google提出了一种实现分布式计算的并行框架MapReduce，它基于由通用机器组成的大规模集群，进行数据处理任务，可以将用户的业务程序和集群的分布式处理机制进行隔离，使用户只关注自己的应用程序设计即可，而并行任务的数据切割、调度、节点通信、系统容错等功能均有框架来完成，通过它处理海量数据，是一种非常有效的方式。但是对于需要进行多次迭代的算法，例如图的最短路径算法、PageRank算法等，如果使用MapReduce框架来处理，由于在两次迭代之间是以分布式文件作为数据传递接口，所以效率很低[1，2]。因此，为了提高图数据算法等大数据量的迭代处理效率，需要对MapReduce框架进行调整与改进。
2. 系统总体架构
整个系统基于Hadoop集群环境运行，即在基于通用机器节点和普通磁盘的集群环境下，利用其分布式文件系统HDFS，或者是Hbase数据库系统存储待处理海量图数据。
其中，为了增加系统的普适性，设计支持多种方式的数据存储。例如，基于单个文件的、基于分布式文件系统（如HDFS）、以及基于数据库（关系的或非关系的）的存储。存储在外部存储介质上的数据通过并行数据加载模块（Parallel Data Loader）将数据加载到各个计算节点。整个系统的核心是计算引擎部分，负责实现数据划分、任务调度、集群通信、容错控制、集群维护、以及对外接口等。
3. 系统计算引擎
计算引擎是整个系统的核心，它由任务调度、数据划分、集群通信、集群维护、Barrier同步、容错控制等模块组成。
（1）任务调度。平台支持多用户操作模式，任务调度模块对多个用户提交的各个Job进行调度执行。系统设计提供几种默认的调度策略，包括FIFO、公平调度、计算能力调度等调度算法。系统提供调度策略设置接口，用户可以根据自己的实际需求类型，设置适合自己应用的调度策略。
（2）数据划分。经过数据输入输出模块将待处理的数据从HDFS、HBase等读取出来以后，数据划分模块将待处理的数据按照一定的规则进行划分并生成多个partition数据分片，并且分配到集群的每一个Worker节点之上，每一个partition数据分片由一个任务来处理。在对图数据的每一个partition进行迭代处理的时候，为了方便地查找每一个图顶点所在的partition位置，以便在消息通信阶段快速查找每一个图顶点的出度顶点所属的partition，数据划分模块需要将待处理的数据进行有效划分并对partition进行有效的管理。系统默认实现基于Hash和Range的图顶点划分方式，另外提供可扩展的接口支持用户自定义的顶点划分方式。
（3）集群通信。消息通信机制是模型中必不可少的部分。在任务进行中，每一个worker都可以与其他的任意个worker进行通信，向它们发送消息和接收由其他worker发来的消息。并且，发送和接收消息的数量也是任意的。消息通信机制主要涉及的问题包括消息的表示、消息的缓存机制、消息的发送接收机制等。
（4）Barrier同步。同步处理是图数据处理中的一个关键步骤。系统模型由一系列的超步组成，在每个超步中，各个Worker并行的进行本地计算处理和通信，由于各个Worker的执行速度不统一，所以最后需要通过Barrier同步，确保所有的Worker都完成了当期的超步，然后由模型的主节点启动下一个超步。在本系统模型中，一个作业被分成多个Task，这些Task被分配到各个Worker上执行，一个Worker可能被分配0至多个Task。所以严格来讲，在本模型中，Barrier同步的最小单位是Task，而不是Worker。
（5）容错控制。在大规模集群中，节点的失效是常有的，包括CPU的故障和磁盘故障。因此如何能够容忍这些失效的出现，并能够及时地采取补救措施，是模型实现中需要解决的问题。MapReduce模型采用磁盘文件暂存Map的计算结果，就是考虑到故障恢复容易实现。而本文系统模型的一大特点，就是处理结果常驻内存，从而减少磁盘IO，提高迭代性能。在不通过磁盘保存上一次迭代结果的情况下，快速地处理故障就成为一个很有挑战性的问题，关系到系统的稳定性和实用性。
4. 图数据云平台的实现
本文提出的大规模图数据云计算平台基于Hadoop平台实现。Hadoop是由Apache开源社区基于Java语言开发出的一个MapReduce并行架构实现，它提供了由通用计算设备组成的大规模集群上执行分布式应用的并行框架。本文基于Hadoop集群对图数据云计算平台进行了实现，平台的测试运行环境是：实验集群包含20个服务器节点，每个节点为4个2.00GHz Intel Xeon（R） CPU、8G内存的服务器，操作系统为Linux Red Hat 5.1操作系统，Java开发包为JDK8版本，Hadoop版本为2.5.0。
5. 结束语
本文通过对基本的MapReduce架构进行调整与改进，研究并实现了用于大规模图数据处理的云计算解决方案，并基于此建立了图数据云计算平台，为大规模图数据的并行处理探索了有效的道路，具有一定的实际应用意义和理论研究价值。
参考文献
[1] 于戈. 云计算环境下的大规模图数据处理技术[J]. 计算机学报， 2011， 10：1753-1767.
[2] 廖松博. GCPR：一种在MapReduce平台上基于图划分的PageRank加速方法[J]. 小型微型计算机系统， 2012， 6：1195-1201.