云计算环境下的大规模图数据处理技术

云计算环境下的大规模图数据处理技术QQ：747790141摘要随着社交网络分析、语义Web分析、生物信息网络分析等新兴应用的快速增长,对亿万个顶点级别大规模图的处理能力的需求愈加迫切,这是当前高性能计算领域的研究和开发热点.文中结合云计算的特点,从图数据管理与图数据处理机制两个方面,综述了云计算环境下进行大规模图数据处理的关键问题,包括图数据的存储方式、图索引结构、图分割策略、图计算模型、消息通信机制、容错管理、可伸缩性、图查询处理等.全面总结了当前的研究现状和进展,详细分析了存在的挑战性问题,并深入探讨了未来的研究方向.AbstractWiththerapidgrowthofemergingapplicationslikesocialnetworkana-nalysis,semanticWebanalysis,andbioinformaticsnetworkanalysis,itisurgenttorequiretheprocessingcapabilityonlargescalegraphswithbilli-onsofvertices,whichisthehottopicoftheresearchanddevelopmentinthecurrenthighperformancecomputingfield.Withthefeaturesofcloudcomputingandfromtheaspectsofgraphmanagementandgraphprocess-singmechanisms,thispapersurveysthekeyissuesoflargescalegraphprocessingoncloudcomputingenvironments,includinggraphdatastoragescheme,indexstructureofgraphdata,graphpartitioningstrategy,graphcomputingmodel,messagecommunicationmechanism,fault-tolerancemanagement,scalability,andgraphqueryprocessing.Thispapersum-arizesthestate-of-artofcurrentresearchworkscompletely,analyzestheexistingchallengeproblemsindetail,anddeeplyexplorestheresearchdi-rectionsinfuture.目录1.引言2.图数据模型与存储管理5.图数据处理的执行机制4.图计算模型与典型系统结构3.图数据的分割策略6.图查询处理7.结束语1.引言图是计算机科学中最常用的一类抽象数据结构,在结构和语义方面比线性表和树更为复杂,更具有一般性表示能力.现实世界中的许多应用场景都需要用图结构表示,与图相关的处理和应用几乎无所不在.传统应用如最优运输路线的确定、疾病爆发路径的预测、科技文献的引用关系等;新兴应用如社交网络分析、语义Web分析、生物信息网络分析等.虽然图的应用和处理技术已经发展了很长时间,理论也日趋完善,但是随着信息化时代的到来,各种信息以爆炸模式增长,导致图的规模日益增大,如何对大规模图进行高效处理,成为一个新的挑战.1.1大规模图数据处理问题以互联网和社交网络为例,近十几年来,随着互联网的普及和Web2.0技术的推动,网页数量增长迅猛,据CNNIC统计,2010年中国网页规模达到600亿,年增长率78.6%,而基于互联网的社交网络也后来居上,如全球最大的社交网络Facebook,已有约7亿用户,国内如QQ空间、人人网等,发展也异常迅猛.真实世界中实体规模的扩张,导致对应的图数据规模迅速增长,动辄有数十亿个顶点和上万亿条边.本文所指的大规模强调的就是单个图的大规模性,通常包含10亿个以上顶点.面对这样大规模的图,对海量数据处理技术提出了巨大挑战.1.1大规模图数据处理问题以搜索引擎中常用的PageRank计算为例,一个网页的PageRank得分根据网页之间相互的超链接关系计算而得到.将网页用图顶点表示,网页之间的链接关系用有向边表示,按邻接表形式存储100亿个图顶点和600亿条边,假设每个顶点及出度边的存储空间占100字节,那么整个图的存储空间将超过1TB.如此大规模的图,对其存储、更新、查找等处理的时间开销和空间开销远远超出了传统集中式图数据管理的承受能力.针对大规模图数据的高效管理,如存储、索引、更新、查找等,已经成为急需解决的问题.1.2采用云计算环境处理大规模图的优势依靠云计算环境对大规模图数据进行高效处理,是一个非常有发展潜力的方向,其主要优势表现在:(1)海量的图数据存储和维护能力.大规模图的数据量可达几百GB甚至PB级别,难以在传统文件系统或数据库中存储,而云计算环境提供分布式存储模式,可以汇聚成百上千普通计算机的存储能力和计算能力,提供高容量的存储服务,完全能够存放和处理大规模的图数据.云计算环境下的并发控制、一致性维护、数据备份和可靠性等控制策略,可以为大规模图数据的维护提供保障.1.2采用云计算环境处理大规模图的优势依靠云计算环境对大规模图数据进行高效处理,是一个非常有发展潜力的方向,其主要优势表现在:(1)海量的图数据存储和维护能力.(2)强大的分布式并行处理能力.利用云计算分布平行处理的特点,可以将一个大图分割成若干子图,把针对一个大图的处理分割为若干针对子图的处理任务.云计算分布式并行运算能力,能够显著提高对大规模图的处理能力.1.2采用云计算环境处理大规模图的优势依靠云计算环境对大规模图数据进行高效处理,是一个非常有发展潜力的方向,其主要优势表现在:(1)海量的图数据存储和维护能力.(2)强大的分布式并行处理能力.(3)良好的可伸缩性和灵活性.从技术角度和经济角度讲,云计算环境具有良好的可伸缩性和灵活性,非常适合处理数据量弹性变化的大规模图问题.云计算环境通常由廉价的普通计算机构成.随着图数据规模的不断增大,可以向云中动态添加节点来扩展存储容量和计算资源,而无需传统并行机模式的巨大投资.1.3关键技术挑战图计算及其分布式并行处理通常涉及复杂的处理过程,需要大量的迭代和数据通信,针对联机事务处理等应用的传统技术很难直接应用到图数据处理中.云计算环境下的大规模图处理主要面临两大挑战:(1)图计算的强耦合性.在一个图中,数据之间都是相互关联的,图的计算也是相互关联的.图计算的并行算法中对内存的访问表现出很低的局部性.对于几乎每一个顶点之间都是连通的图来讲,难以分割成若干完全独立的子图以进行独立的并行处理.并且,“水桶效应”问题加剧.1.3关键技术挑战图计算及其分布式并行处理通常涉及复杂的处理过程,需要大量的迭代和数据通信,针对联机事务处理等应用的传统技术很难直接应用到图数据处理中.云计算环境下的大规模图处理主要面临两大挑战:(1)图计算的强耦合性.为了提高执行效率,需要采取多种优化技术.首先,在预处理阶段进行合适的图分割时,尽可能地降低子图之间的耦合性;其次,在执行阶段应选取合适的图计算模型,避免迭代过程中反复启动任务和读写磁盘,降低任务调度开销和IO开销;应充分利用迭代过程中的收敛特性进行查询优化,同时进行有效的同步控制和消息通信优化,减少通信开销,以达到降低水桶效应的目的.1.3关键技术挑战图计算及其分布式并行处理通常涉及复杂的处理过程,需要大量的迭代和数据通信,针对联机事务处理等应用的传统技术很难直接应用到图数据处理中.云计算环境下的大规模图处理主要面临两大挑战:(1)图计算的强耦合性.(2)云计算节点的低可靠性.大规模图处理,需要相对较长的时间来完成计算任务,如PageRank计算需要约30次迭代处理,消耗大量的时间和资源.而云计算节点通常是由普通的计算机组成,在这种长时间的处理过程中,个别节点出现故障是难免的.这时不能简单地重新计算,而应该从断点或者某个合适的位置接续执行.否则,将造成很大的浪费,甚至一些大型的图计算根本就不能完成.1.3关键技术挑战图计算及其分布式并行处理通常涉及复杂的处理过程,需要大量的迭代和数据通信,针对联机事务处理等应用的传统技术很难直接应用到图数据处理中.云计算环境下的大规模图处理主要面临两大挑战:(1)图计算的强耦合性.(2)云计算节点的低可靠性.另一方面,由于图计算并行子任务之间的强耦合性,一个子任务的失败可能导致其它子任务的失败,这又增加了恢复处理的复杂性.因此,需要考虑有效的容错管理机制,减少大规模图处理过程中的故障恢复开销,尽量避免重复计算,提高大规模图处理的运算效率和稳定性1.3关键技术挑战图计算及其分布式并行处理通常涉及复杂的处理过程,需要大量的迭代和数据通信,针对联机事务处理等应用的传统技术很难直接应用到图数据处理中.云计算环境下的大规模图处理主要面临两大挑战:(1)图计算的强耦合性.(2)云计算节点的低可靠性.为了解决云计算环境下的大规模图处理问题,可从图数据管理和图处理机制两方面加以考虑.在图数据管理上,需要解决图数据的分割、图数据的存储、图数据索引的建立、图查询处理等问题;在图处理机制上,需要解决处理过程中图计算模型选取、同步控制、消息通信、容错管理和可伸缩性等问题.本文将针对上述内容,结合云计算的优势和存在的挑战,综述云计算环境下的大规模图处理现有技术的进展解决方案以及今后的发展趋势和研究方向.目录1.引言2.图数据模型与存储管理5.图数据处理的执行机制4.图计算模型与典型系统结构3.图数据的分割策略6.图查询处理7.结束语2.图数据模型与存储管理图数据的逻辑表达形式和物理存储结构是实现图处理的基础.本节首先介绍图数据模型,然后,介绍图的存储管理以及为了提高查找效率而为图数据建立的索引结构.作为数学的一个重要分支,图论以图作为研究对象,在简单图的基础上衍生出超图理论、极图理论、拓扑图论等,使图可以从多方面表达现实世界.当前大规模图数据管理,采用的数据模型有多种.按照图中节点的复杂程度分为简单节点图模型和复杂节点图模型;按照一条边可以连接的顶点数目分为简单图模型和超图模型.不论是简单图模型、超图模型、简单节点模型还是复杂节点模型,它们的顶点和边都可以带有属性.下面介绍简单图模型和超图模型,其它模型请参考文献[4].2.1.1简单图模型(1)简单图模型.这里所说的简单图,并不是图论中的简单图,是相对于超图而言的.简单图中,一条边只能连接两个顶点允许存在环路.简单图的存储和处理都比较容易,对于一般的应用,简单图的表达能力完全可以胜任,如PageRank计算、最短路径查询等.Pregel、Hama等系统均采用简单图模型来组织存储和处理大规模图数据.2.1.2超图模型(2)超图模型.一条边可以连接任意数目的图顶点.此模型中图的边称为超边.基于这种特点,超图比上述简单图的适用性更强,保留的信息更多.2.1.2超图模型(2)超图模型.例如,以图顶点代表文章,每条边代表两个顶点(文章)享有同一个作者.现有3篇文章V1(作者A、B)、V2(作者A、C)、V3(作者A、D),3篇文章的作者都有A.图1(a)表示了简单图存储模式,3条独立的边e1,e2,e3={v1,v2},{v1,v3},{v2,v3},无法直接保留作者A同时是3篇文章V1、V2、V3的作者这一信息.图1(b)代表了超图存储模式,超边e1={v1,v2,v3}直接保留了A是3篇文章V1、V2、V3的作者这一信息.对于具有复杂联系的应用,可以使用超图模型建模,例如社交网络、生物信息网络等.Trinity等图数据库系统支持超图模型来管理大规模图数据.2.2图数据的存储方式在目前的大规模图数据管理应用中主要采用简单图和超图两种数据模型二者的组织存储格式略有不同.这两种模型都可以处理有向图和无向图，默认情况是有向图，而无向图中的边可以看作是两条有向边，即有向图的一种.在之后的讨论中不再强调图中边的方向.简单图模型的常用存储结构包