基于MapReduce的单源最短路径算法研究.doc

1.2 相关数据结构定义为了减少数据冗余, 本文对于图的表示方法采用邻接表的 方式进行存储,以各顶点为中心,每一行代表图中的一个顶点,各顶点数据结构描述如下:其中,ID 为顶点标识;distance 表示从源点到顶点的距离,除 到本身的距离为 0 外,其余初始值皆为无穷大 MAX;Flag 为标志 位, 其值可分别取 0、1、2,0 表示未处理的顶点,1 表示正待处理 的顶点,2 表示已经处理了的顶点,源点的初始值为 1,其余顶点 皆为 0;Adjacent information 代表邻接信息,包括顶点的邻接点及 其权值。如图 1 用邻接表表示的数据结构如图 2 所示:图 1 带权有向图 G图 2 用邻接表表示图 1 的数据结构图 3 基于 MapReduce 的单源最短路径算法的执行过程文章编号:1008-0570(2011)12-0097-03基于的单源最短路径算法研究MapReduceResearch on the Single Source Shortest Path Algorithm Using MapReduce(湖南大学) 杨玲 李仁发 唐 卓YANG Ling LI Ren-fa TANG Zhuo摘要: 通 过 对 MapReduce 模型执行过程的分析 ,针 对 单 源最短路径算法难以随着云计算的产生和发展而应用及提高搜索效 率 的 问 题, 本文设计和实现了一种基于 MapReduce 架构的并行单源最短路径算法 。 并 基 于 Hadoop 平台集群环境进行了研究 与 实 验, 结 果 表 明, 文中算法可以有效地找出整个图结构中的单源最短路径 , 且验证了算法性能的优越性 。关键词: MapReduce; 并行; 最短路径; hadoop中图分类号: TP393.0文献标识码: AAbstract: Via the analysis to implementation process of mapreduce, aimming at the problem that single source shortest path algorithmis hard to be used with the appearance and development of cloud computing and the problem of searching efficiency,a parallel single source shortest path algorithm based on mapreduce framework is designed and implemented .research and experiment are done based on hadoop platform.As shown by the experimental results,the proposed algorithm can search the single source shortest path efficiently in the whole graphic structure,and its good performance is testified.Key words: MapReduce; Parallel; Shortest path; Hadoop引言计算机网络的飞速发展促进了云计算的产生。MapReduce 并行编程模型是云计算的核心技术之一,2005 年 4 月 6 日, Google 实 验 室 的 Jeffrey Dean 和 Sanjay Ghemawat 提 出 了 MapReduce 模型并进行了详细地阐述, 它为并行系统的数据处 理提供了一个简单、优雅的解决方案。Apache 基金会基于 Java 开发了一个分布式基础架构 Hadoop, 实现了 MapReduce 模型, 并提供了分布式计算平台。在通信网络与交通网络中, 并行问题和最短路径问题一直 是研究的热点, 有着极其重要的作用。在处理实际问题的过程 中, 通常将现实问题转化为图的网状形式来研究最短路径。而 MapReduce 并行计算模型的出现, 为解决大规模数据处理问题 提供了一种新的途径, 也为最短路径的并行计算带来了一种新 的解决方法,有效提高了计算效率。本文提出了基于 MapReduce 的单源最短路径算法。首先利 用 MapReduce 架构来形成算法的并行化思想,分析并设计了算法的过程,然后通过 Hadoop 平台来实现算法,最后对实验结果 进行了分析。算法及其数据结构的定义11.1 单源最短路径算法单源最短路径是指给定一个带权有向图 G=(V,E,W),其中 V 为顶点集,E 为有向边集,W 为权集且每条边的权是一个非负实 数。另外,还给定 V 中的一个顶点,称为源,计算从源到所有其他 各顶点的最短路径长度。这里的长度是指各边权之和,根据不同 的实际情况,边上权值的长度可以表示成时间、距离、成本、损失、损耗或其它任何沿一条路径的相加累积量,且为最小值。杨 玲: 硕士研究生邮局订阅号：82-946 120 元 / 年 - 97 -PLC 技术应用 200 例2 基 于 MapReduce 的 单 源 最 短 路 径算法的设计与实现MapReduce 用户用两个函数表达这个计算:map 和 reduce。 在 MapRedcue 模型中,用户指定一个 map 函数来处理一个输入 的 key/value 对,产生中间结果 key/value 对集,再通过 reduce 函 数来处理中间结果中具有相同 key 值的 value。基于 MapReduce 的单源最短路径算法的执行过程如图 3所示。(1)输入数据的切分:MapReduce 对输入文件按行(每行代表 图中的一个顶点) 进行自动切分, 并将数据分发到每个 Map 任务, 其中 key 值为 ID,value 值为 distance、flag 和 Adjacent infor图 5 Map 算法过程mation;(2)Map 任务的执行:接收 key/value 对,当 value 中的 flag 的 值为 1 时,则处理当前顶点,主要处理当前顶点的邻接点,并将其邻接点的 flag 也置为 1,最后产生临时的 key/value 对集;图 6 Reduce 过程的输入和输出(3)临时结果的分组:MapReduce 框架对 Map 执行过程输出 的临时结果进行分组, 将相同的 key 值即 ID 号合并成同一组,并将其分发给空闲的 Reduce;(4)Reduce 任务的执行:接收 key/value 对,对相同 ID 的 value进行合并,找到当前的最短路径;(5)MapReduce 的迭代:如图 3 所示,每次 Reduce 后的结果 又分发给下一轮的 Map 过程,通过多次迭代寻找到最终的最短 路径。当没有发现更好的距离时,节点间的遍历会停止,本文中是以 flag 位来判断的, 即当 reduce 中所有记录的 flag 位都不为1 时,则停止迭代,算法结束。2.1 Map 过程Map 函数对整个图的结构进行遍历,采用 BFS 算法(即广度优先算法)思路,按层依次遍历整个图。Map 函数根据所接到的图 7 Reduce 算法过程key/value 对(即每个顶点的相关信息)来产生相关的输出。输出 主要分两种,一种是本身结点的信息,在处理完后,仅对信息的标志位进行更改;一种是对本结点的邻接点进行遍历。具体如图 4所示。图 4 Map 过程的输入和输出本文将图 1 中的有向图 G 的顶点 V0 的基本信息作为 Map 图 8 基于 MapReduce 的有向图 G 的第一次迭代过程 的输入,其输入值为<0,<0 1 2,10,4,30,5,100>>,经过 Map 函数2.3 MapReduce 的迭代过程执行后,其输出结果为<0,<0 2 2,10,4,30,5,100>>、<2 10 1>、<迭代方法主要是采用作业链来实现。前一个 MapReduce 作4 30 1>、<5 100 1>,详细过程可参见图 3。业的 Reduce 输出作为下一个 MapReduce 作业的 Map 输入,这Map 算法过程如图 5 所示。样就形成了整个工作链。当某个作业的输出中所有的节点都没2.2 Reduce 过程有标志位为 1 的节点时,则停止迭代,算法终结。具体可参见图 3Reduce 过程对从各个 Map 对各顶点的处理结果进行聚集中所示的整个算法执行过程,图 8 给出了基于 MapReduce 的有运算,取相同 ID 中最小的距离,修改标志位,并加上邻接点信息,向图 G 的第一次迭代过程。具体如图 6 所示。对于图 1 中的有向图 G 的顶点 V2,其 Reduce 的输入值为<3 实验及其结果分析2 10 1>、<2 Max 0 3,50>,经过 Reduce 过程处理后,其输出结Hadoop 是由雅虎资助的开源项目, 是一个类似于 Google 果为<2 10 1 3,50>,详细过程可参见图 3。“云计算”的技术平台,专注于海量数据存储、处理的分布式系 Reduce 算法过程如图 7 所示:统,同时提供了基于 Java 的 MapReduce 框架,能够将分布式应网 络 与 通 信微计算机信息2011 年第 27 卷第 12 期- 98 -120 元 / 年 邮局订阅号：82-946现场总线技术应用 200 例用部署到大型廉价集群上。Hadoop 能够实现高效计算,存储的核心在于其可运行于大规模集群上的分布式文件系统 HDFS (Hadoop Distributed File System)以及 MapReduce 分布式并行编程框架。文中的实验采用的是 Hadoop 完全分布式集群环境,整个基 于 MapReduce 的单源最短路径算法的程序编写由 Java 语言来 实现。采用 8 台实体机进行完全分布式集群的搭建,每个节点的 运行环境如下:WindowsXP、JDK、Cygwin 和 Hadoop。且每台机器 的配置为:Intel (R) Pentium (R) 4 CPU 3.0GHz、1 GB RAM 及80GB 可用硬盘空间。其中一台机器作 jobTracker,namenode 为 Master,其余机器皆作 datanode,TaskTracker 为 slave。对上述算法 描述的图 1 的每次迭代结果片段数据如表 1 所示:实验中, 根据所给数据量较小的情况下, 采用多节点的Hadoop 计算速度明显不如采用 Hadoop 单节点的速度快, 也比 Hadoop 并行技术的方式慢很多。因此,对于小规模的运算,不适 宜采用 Hadoop。为了能进一步地比较实验结果, 在实验中分别测试了图的 顶点个数为 10000 和 90000 来做了测试, 表 2 给出了不同节点数下基于 MapReduce 的单源最短路径算法的并行加速比的测 试与比较,且在图 9 中作出了曲线比较。图 9 加速比测试比较由图 9 中的数据可以看出, 在数据规模即顶点数 n 相同的 情况下,并不是横轴上集群中节点数目越多,纵轴上的加速比就会增加,而是有一个峰值,达到一定的峰值后,加速比反而会下 降。我们分析原因是由于 map 数和 reduce 数的增加会导致节 点间通信量和同步的增加,另外,局域网内部的网络吞吐量也会 导致并行性能的下降。因此,在实际的应用过程中,应该采用恰 当数目的节点机,选择合适的 Map 和 Reduce 数目,以避免资源的浪费。表 1 有向图 1 的每一次迭代结果表 2 并行加速比测试数据从实验的过程中,基于 MapReduce 的单源最短路径算法模 型的使用较方便,对于大型的计算需求也可以较轻松地完成。事 实上,也可从实验中推导出,通过 Hadoop,应用程序也可以在超 大型集群上运行,也就是说系统的易扩展性较高。结语4文中实现了一种基于 MapReduce 的单源最短路径算法。研究表明,在云计算环境中,文中算法可以有效地找出整个图结构 中的单源最短路径。同时本算法也存在着一定的缺点:在某种极 端的情况下, 其所花费的时间可能会与 Dijkstra 算法差不多,这是因为算法会导致浪费一定的扩展路径。 尽管如此,基于MapReduce 的应用正被越来越多人所关注和使用,随着 MapReduce 的不断发展,它将会得到更多人的关注与应用。在今后的 研究工作中,我们将进一步研究基于 MapReduce 的单源最短路 径算法的应用,将侧重于以边为中心去处理图结构的遍历。本文作者创新点:在基于 MapReduce 的单源最短路径算法 的研究与应用之上,对其进行理论分析,并对其加速比进行了研究,且验证了其性能的优越性。作者对本文版权全权负责,无抄袭。参考文献1Dean J, Ghemawat S.MapReduce:Simplified Data Processing on Large Clusters C/Proc. of the 6th Symposium on Operating Sys tems Design and Implementation. San Francisco,USA:s.n.,2004.2Cutting D.Scalable Computing with MapReduceC /Proc. of OReilly Open Source Convention. Poland:s.n., 2005.3Tan G Z, Ping X H. A Parallel Algorithm for Computing Shortest Paths In Large-Scale Networks C/Proc. of The 5th International Conference on Computational Science. Atlanta,GA,USA: s.n.,2005.4Tan G Z, Li D, Ping X H, et al.Network-Tree Routing Model for Large Scale Networks:Theories and Algorithms/Proc. of The 4th International Conference on Networking.Reunion Island,France: s. n.,2005.5陈国良. 并行算法的设计与分析M. 北京: 高等教育出版社,2002.6Dean J. Experiences with mapreduce,an abstraction for large - scale computation C /Proc. of PACT06. Washington D.C.,USA: s.n.,2006.7Yang H C, Dasdan A, Hsiao R L,et al.Map -reduce -merge:simplified relational data processing on large clusters C /Proc. of2007 ACM SIGMOD Conference,2007.8Cohen J. Graph Twiddling in a MapReduce WorldJ. Computing in Science & Engineering,2009,11(4):29-41.9Borthakur D. The Hadoop Distributed File System:Architecture and DesignEB/OL. http:/hadoop.apache.org/common/docs/r0.18.0/ hdfs_design.pdf, 2007.10杨代庆,张智雄.基于 Hadoop 的海量共现矩阵生成方法J.现代图书情报技术,2009(4):23-26.作者简介:杨玲(1984-),女,硕士研究生,主要研究领域为云计算;李仁发(1956-),男,教授,主要研究领域为嵌入式系统、云计算;唐 卓(1981-),男,博士,主要研究领域为云计算。(下转第 101 页)邮局订阅号：82-946 120 元 / 年 - 99 -PLC 技术应用 200 例2 RUDP 的应用2.1 .通信中间件 中间件是一种独立的系统软件或服务程序, 分布式应用软件借助这种软件在不同的技术之间共享资源。中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。是连 接两个独立应用程序或独立系统的软件。相连接的系统,即使它 们具有不同的接口,但通过中间件相互之间仍能交换信息。执行 中间件的一个关键途径是信息传递。通过中间件,应用程序可以 工作于多平台或 OS 环境。而通信中间件就是管理网络通信的 消息通讯平台。2.2. 基于消息的 MsgMidWare 体系MsgMidWare 体系是指基于 UDP 协议, 采用 C/S 与分布式 结构相结合的方式, 即将通讯模块分成通信管理服务器模块和 通信客户模块两类模块, 而通信管理服务器之间作为对等的通 信实体,为各客户模块提供一定程度的分布式处理功能,实现在同一台机器内模块间采用 IPC 及共享内存通信, 而在不同机器 间采用 UDP 的连接的通信。如图 2 所示。图 22.3. MsgMidWare 的工作原理MsgMidWare 的工作原理上由通信管理服务和通信客户模 块两部分组成, 通信管理器主要目的是管理通信客户模块和实现本机通信客户模块间的消息通信。结合这种工作原理 MsgMidWare 的通信层次结构图如图 3 所示。图 3通信客户端模块(应用层):采用消息驱动机制,用户看到的 是自行定义的消息内容。通信管理层:相对通信客户模块是透明的。通过 RUDP 协议 实现消息的高效可靠传输机制,管理通信客户模块,将包在通信客户模块间传递,沟通不同的进程。UDP 层:实现数据的传递,沟通不同的机器和操作系统,为 不同机器上的模块之间通信的透明管道。之前介绍了 MsgMidWare 的体系, 它是一种消息通信中间 件, 每一个通信客户模块都维护一个接收消息队列和一个发送消息队列,自动具备与通信服务器端的交互能力,每个通信客户模块在启动时向通信服务器注册本模块,在退出是注销本模块。下图 4 是通信客户模块在通信时的消息传送图。图 4网 络 与 通 信结论3以往的通信中间件很多都是基于 TCP 的, 通过改进基于UDP 的协议融入到中间件技术,形成一种高性能、安全、可靠的 消息传输系统,很好地支持 C/S 模式和分布式系统的开发、集成 和运行, 为跨越不同操作系统和网络平台的多层结构应用系统的开发、部署及运行,提供了灵活易用的消息通讯平台基础。本文作者创新点:改进基于 UDP 的协议应用到通信中间件 当中。作者对本文版权全权负责,无抄袭。参考文献1GU Yunhong,Hong Xinwei,Grosman R.Experiences in design and implementation of a high performance Transport Protocol C/ Proceedings of the ACM/IEEE SC2004 Conference,2004.2Bova T, Krivoruchka T. Reliable UDP Protocal draft -ietf -sigtranreliable-udp-00.txt. Cisco Systems, 1999-02 3黄远峰,宗平.基于 UDP 的滑动窗口协议的设计与实现J.南 京邮电大学学报,2007,27(4):80-84. 4谭宁,常毅等.一种网络拥塞控制体系的设计J.微计算机信息.2007,4-3:P142-1435王海军, 刘彩霞, 程东年.一种基于 UDP 的可靠传输协议分析 与研究J.计算机应用研究.2005,11(3) :181-183作者简 介:张良春(1986-),男(汉族),湖南省长沙市人,长沙理工 大学,硕士,2008 年在长沙理工大学研修,主要从事计算机通信研究。Biography: ZHANG Liang - chun (1986 - ), male (Han People), Hunan, Changsha University of Science and Technology, comput- er communication research.(410004 湖南 长沙 长沙理工大学 计算机与通信工程学院)张良春 龙鹏飞(School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha410004, China) ZHANG Liang-chun LONG Peng-fei通讯 地 址:(410004 湖 南 长 沙 长 沙 理 工大 学 计 算 机 与 通 信 工 程学院) 张良春(收稿日期:2011.03.01)(修稿日期:2011.06.20)(上接第 99 页)Biography: YANG Ling, femail, master, Major Research Field: Cloud Computing.(410082 长沙 湖 南 大 学 信 息 科 学 与 工 程 学 院) 杨唐 卓玲 李 仁 发(Department of Information Science and Engineering, HunanUniversity, Changsha 410082, China) YANG Ling LI Ren-faTANG Zhuo通讯地址:(412008 湖南大学 15 舍 218 室) 杨玲(收稿日期:2011.03.01)(修稿日期:2011.06.20)邮局订阅号：82-946 120 元 / 年 - 101 -PLC 技术应用 200 例P LC 技术应用 2 0 0 例将出版，每册定价 55 元(含邮费)，汇至地址: 北京市海淀区中关村南大街乙 12 号天作 1 号 楼 B 座 812 室 微计算机信息 邮编:100081 电话:010-62132436 010-82168297(T/F)您的论文得到两院院士关注