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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,云计算环境下的大规模图数据处理技术,*,PPT,文档演模板,Office,PPT,云计算环境下的大规模图数据处理技术,2026/11/12,云计算环境下的大规模图数据处理技术,摘 要,随着社交网络分析、语义 Web 分析、生物信 息网络分析等新兴应用的快速增长,对亿万个顶点级别大规模图的处理能力的需求愈加迫切,这是当前高性能计算领域的研究和开发热点.文中结合云计算的特点,从图数据管理与图数据处理机制两个方面,综述了云计算 环境下进行大规模 图数据处理的关 键问题,包括图数据的存储方式、图索引结构、图分割策略、图计算模型、消息通信机制、容 错管理、可伸缩性、图查询处理 等.全 面总结了当前的研究现状和进展,详细分析了存在的挑战性问题,并深入探讨了未来的研究方向.,云计算环境下的大规模图数据处理技术,Abstract,With the rapid growth of emerging applications like,social network ana-nalysis,semantic Web analysis,and,bioinformatics network analysis,it is urgent to require the,processing capability,on large scale graphs with billi-ons of vertices,which is the hot topic of t he research and development in the current high performance computing field.With the features of cloud computing and from the aspects of,graph management,and,graph process-sing mechanisms,this paper surveys the key issues of large scale graph processing on cloud computing environments,including,graph data storage scheme,index structure of graph data,graph partitioning strategy,graph computing model,message communication mechanism,fault-tolerance management,scalability,and,graph query processing,.This paper sum-arizes the state-of-art of current research works completely,analyzes t he existing challenge problems in detail,and deeply explores the research di-rections in future.,云计算环境下的大规模图数据处理技术,目 录,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)简单图模型.,这里所说的简单图,并不是图论中的简单图,是相对于超图而言的.简单图中,一条边只能连接两个顶点允许存在环路.简单图的存储和处理都比较容易,对于一般的应用,简单图的表达能力完全可以胜任,如 Page Rank 计算、最短路径查询等.Pregel、Hama 等系统均采用简单图模型来组织存储和处理大规模图数据.,云计算环境下的大规模图数据处理技术,2.1.2 超图模型,(2)超图模型.,一条边可以连接任意数目的图顶点.此模型中图的边称为超边.基于这种特点,超图比上述简单图的适用性更强,保留的信息更多.,云计算环境下的大规模图数据处理技术,2.1.2 超图模型,(2)超图模型.,例如,以图顶点代表文章,每条边代表两个顶点(文章)享有同一个作者.现有 3 篇文章 V 1(作者 A、B)、V2(作者 A、C)、V3(作者 A、D),3 篇文章的作者都有A.图 1(a)表示了简单图存储模式,3 条独立的边e1,e2,e3=v1,v 2,v1,v 3,v2,v3 ,无法直接保留作者 A 同时是 3 篇文章 V1、V2、V3 的作者这一信息.图 1(b)代表了超图存储模式,超边 e1=v1,v2,v3 直接保留了 A 是 3 篇文章 V1、V 2、V3 的作者这一信息.对于具有复杂联系的应用,可以使用超图模型建模,例如社交网络、生物信息网络等.Trinity 等图数据库系统支持超图模型来管理大规模图数据.,云计算环境下的大规模图数据处理技术,2.2 图数据的存储方式,在目前的大规模图数据管理应用中主要采用,简单图,和,超图,两种数据模型 二者的组织存储格式略有不同.这两种模型都可以处理有向图和无向图，默认情况是有向图，而无向图中的边可以看作是两条有向边，即有向图的一种.在之后的讨论中不再强调图中边的方向.,简单图模型的常用存储结构包括,邻接矩阵,、,邻接表,、,十字链表,和,邻接多重表,等多种方式.从大规模图处理的应用需求和维护的复杂程度考虑,邻接矩阵和邻接表,是最常用的两种结构.采用邻接矩阵表示图的拓扑结构,直观简洁,便于快速查找顶点之间的关系,但是邻接矩阵的存储代价高昂,对于大规模图数据,这个问题尤为严重.,云计算环境下的大规模图数据处理技术,2.2 图数据的存储方式,GBASE 系统以邻接矩阵的形式组织存储图,考虑到邻接矩阵的存储开销,GBASE 对矩阵进行了聚簇分割,尽量将矩阵中的非零值集中存储并采用 Zip 技术压缩编码,减少矩阵的存储代价.与邻接矩阵相比,邻接表的应用范围更加广泛.像 Page Rank 计算、最短路径计算等应用,并不需要频繁查找两个图顶点之间的连通性,邻接表完全可以满足计算需求.邻接表的存储开销小,逻辑简单,便于分割处理,是一种比较理想的图组织方式,Pregel、Hama和 HaLoop 等系统均采用邻接表的形式组织图数据.超图模型的组织方式主要使用关系矩阵.从形式上讲,关系矩阵和邻接矩阵较为相似,但是矩阵的行和列分别表示图顶点编号和超边的编号.,云计算环境下的大规模图数据处理技术,2.2 图数据的存储方式,大规模的图数据存储需要依赖云计算环境的分布式存储系统.云计算环境的存储系统分为两种:一种是以 GFS、HDFS为代表的分布式文件系统,对于邻接矩阵、邻接表等结构,可以直接存放;另一种是以 BigTable、Hbase为代表的 NoSQL(Not Only SQL)分布式数据库.,云计算环境下的大规模图数据处理技术,2.2 图数据的存储方式,NoSQL 数据库采用的数据模型主要有,文档存储(Document Store)模型,、,列族存储(Column Family Store)模型,、,Key-Value 存储模型,、,图存储模型,等几大类.文档存储模型在存储格式方面十分灵活,比较适合存储系统日志等非结构 化数据,CouchDB 和 MongoDB 是采用这种存储模型的典型系统.但是,文档存储模型不太适合以邻接矩阵或邻接表组织的图数据.此外,文档存储模型为支持灵活性所导致的处理效率的降低也会成为大规模图数据管理的性能瓶颈.列族存储模型比较适合对某一列进行随机查询处理,但是对于穷举式遍历,反而不如传统的面向行的存储模式.采用该存储模型的典型系统有 BigTable、Hbase、Cassandra 等.图存储模型的相关研究目前还不完善,只有少数分布式图数据库,如 Neo4j 等采用这种模型存储图数据.,云计算环境下的大规模图数据处理技术,2.2 图数据的存储方式,与上述 3 种存储模型相比,Key-Value存储模型较为适合存储大规模图数据.Key-Value存储模型的存储模式简单,支持海量数据存储和高并发查询操作,非常适合通过主键进行查询或遍历,但对复杂的条件查询支持度不佳.采用该模型的典型系统有 Dynamo 和 SimpleDB.从图处理的角度出发,像 PageRank 计算等,并不需要复杂查询,Key-Value 模型完全可以胜任.若图数据采用邻接表组织,可以将图的源顶点作为 Key,将源顶点值、出边及边信息作为 Value.文献 21 结合语义 Web 和传统的 Key-Value 存储模型,提出 Key-Key-Value 存储模型.,以社交网络为例,Key-Key-Value 模型将Alice 和 Bob 之间的好友关系组织为一个三元组.该模型存储的信息比传统的Key-Value 模型更加丰富,可以据此进行数据迁移和合并,以提高空间局部性,使得在查询处理时能减少远程读取数据的次数,因而可以提高数据读取效率.,云计算环境下的大规模图数据处理技术,2.2 图数据的存储方式,此外,对于分布式图数据库,当图数据更新时,需要提供事务功能,解决在分布式环境下的一致性控制问题.HyperGraphDB和Trinity 等人都宣称自己支持事务机制和一致性控制.如果图数据存储在H DFS 类型的分布式文件系统上,因其不支持更新和随机插入操作,也就不存在一致性维护问题.,前面讨论了 NoSQL 数据库的 4 种主要存储模型.,文献 23 从管理数据的规模和模型的复杂性两个维度比较了这 4 种基本存储模型,见图 2.,云计算环境下的大规模图数据处理技术,2.3 图数据的索引结构,索引是传统关系数据库中的关键技术,包括B+树索引、H ash 索引、位图索引等,技术较为成熟,可以提高数据查询处理效率,尤其是在查询结果的数据量远小于原始数据的情况下.对于一个大规模图,云计算的分布式并行处理机制,可以根据查询条件遍历所有的子图数据,如果查询结果的数据量较大,这种处理方式的性能是比较好的,但是如果查询结果的数量很小,则会访问很多无用的数据,造成计算资源的浪费和查询效率的低下,而通过建立合适的索引,可以有效解决这一问题.,云计算环境下的大规模图数据处理技术,2.3 图数据的索引结构,目前用于云计算环境下的索引技术,很少有专门针对图数据的.但是,这些索引技术大都是可以被图数据存储所利用.目前的云环境下用于数据管理的索引结构可以分为,适用于 P2P 网络结构的索引以及适用于 Shared-nothing 集群结构的索引,.,文献 24 针对云计算环境下的大规模数据查询处理,提出了,二级索引技术 CG-index,.它首先在每一个数据分片上建立本地 B+tree 形成索引分片,后将计算节点组织成 Overlay 结构,接下来基于 Overlay 的路由协议把各个计算节点上 B+tree分片发布到 Overlay 上,建立全局索引 CG-index.这种索引具有自适应性和可扩展性.,文献 25 建立了,多维索引机制 RT-CAN,集成 CAN 协议和 R 树的特点,在云计算环境下提供高效查询服务.,文献 26也针对 P2P 环境,在分布式 KD-tree 基础上提出,多维索引 MIDAS,用以支持多维查询、范围查询和 k最近邻查询等应用.,文献 27 提出了一个通用的、灵活的、容错的、且可扩展的,分布式 B-tree 索引结构,.,文献 28 将 R-tree 和 KD-tree 结合起来组织数据记录,提出了用于云数据管理的,多维索引 EMINC,可以提供快速的查询处理和有效的索引维护.,云计算环境下的大规模图数据处理技术,2.3 图数据的索引结构,云计算环境下的通用索引机制,没有考虑图结构的特点,在图查询处理方面,效果不明显.而分布式图数据库,无论是数据存储还是索引结构,都针对图数据进行了优化.,云计算环境下的大规模图数据处理技术,2.3 图数据的索引结构,Neo4j 的索引分为两类:数据库本身就是一个树形结构的索引,可用于提高查询效率,此外,还可以使用独立的Lucene索引,提供全文索引和索引命中率排序功能.Neo4j 可以对图顶点和边分别建立索引,通过对索引的缓存,可进一步加快查找速度.索引的维护操作(如删除、更新)则必须在事务管理机制下进行.对于更新,必须先删除旧的索引值,然后才能添加新索引值,代价较高.,InfiniteGraph与Neo4j类似,也提供内建索引和Lucene索 引.在 HyperGraph-DB的两层 存储 架构中,索引是存储层必备的组成部分,一个 Key可对应多个已排序的 Value,并支持 Value 共享;在模型层,Key 采用 U UID 编号并排序,在 Key 上建立索引.索引文件以 B-tree 格式存储并具有缓存功能,可以为查询等操作提供持久化的元数据信息.Trinity 数据库提供 Trie 树和 H ash 两种索引结构来访问图顶点、边的名字以及相关的其它信息,可减少有公共前缀的字符串的匹配次数.,云计算环境下的大规模图数据处理技术,2.3 图数据的索引结构,支持图计算处理的索引,主要是在云计算平台中体现.,文献 30 针对 Hadoop 系统中的 Shuffle 过程和 Reduce 过程进行了改进,采用动态增量式H ash 索引和缓存技术降低 Shuffle 过程的磁盘 IO代价,提高 CPU 利用率.HaLoop 则对 Map 任务的输入、Reduce 任务的输入和输出进行缓存并建立索引,在一定程度上提高了 Hadoop 迭代处理的效率.,文献 31 针对 MapReduce 的连接操作,提出Trojan 索引技术,通过对分片信息和 Key 值的重新构造,建立索引,使需要连接的数据位于同一个分片上,减少连接操作的网络通信量.由于MapReduce模型是一个通用计算模型,Hadoop 处理平台的索引也是通用性的,对于大规模图的迭代处理的针对性并不强.,云计算环境下的大规模图数据处理技术,目 录,1.引 言,2.图数据模型与存储管理,5.图数据处理的执行机制,4.图计算模型与典型系统结构,3.图数据的分割策略,6.图查询处理,7.结束语,云计算环境下的大规模图数据处理技术,3.图数据发分割策略,云计算环境下的通用索引机制,没有考虑图结构的特点,在图查询处理方面,效果不明显.而分布式图数据库,无论是数据存储还是索引结构,都针对图数据进行了优化.,在云计算环境下,对于一个大规模图的处理,必须进行分布式并行处理.由于图数据本身固有的连通性和图计算表现出强耦合性的特点,为了实现高效的并行处理,尽可能降低分布式处理的各子图之间的耦合度是非常重要的.有效的图分割就是实现解耦的重要手段.这首先要将一个逻辑上完整的大图分割成若干部分,分别放置到分布式存储系统的各工作节点上.其后对图的处理,就是针对已经分布式存放的每一个子图,启动一个计算任务,进行相同的处理操作,当所有子图处理结束,则完成整个大图的一次处理了.,云计算环境下的大规模图数据处理技术,3.1 图分割策略,在云计算环境下,实现大图分割并取得较好的分割效果,是一项挑战性很大的工作.将一个大图分割为若干子图,有两个主要原则:,一是,提高子图内部的连通性,降低子图之间的连通性,这种特点尤其适合云计算的分布式并行处理机制;,二是,考虑子图规模的均衡性,尽量保证各子图的数据规模均衡,不要出现较大的偏斜,从数据规模方面防止各并行任务的执行时间相差过大,降低任务同步控制过程中“水桶效应”的影响.,当然,大图分割的时间复杂度必须控制在可以忍受的范围内.图3对比了3种不同的图分割效果,如果单纯考虑子图的数据均衡或子图之间的连通性,其效果均不理想,只有同时考虑着两个因素,才能显著提高分布并行式处理效率.,云计算环境下的大规模图数据处理技术,3.2 单指标分割技术,如果只考虑数据负载均衡这一单项指标最简单的图分割技术就是 H ash 方式，即在设定了分片数目之后对图顶点 ID 进行 H ash 将数据划分成给定数目的分片.这种分割方法效率很高时间复杂度为 O(n)，可以在图数据的载入过程中或图处理之前完成分片操作.,在一定条件下设计良好的 Hash 方式可以避免数据偏斜使各子图的数据规模接近相同.但是 H ash 方式没有考虑图数据的局部性甚至连原始数据的局部性 也无法得到保留.H ash 方式虽然在云计算环境下容易实现 但是负责各子图处理的任务之间消息通信频繁会造成较大的网络通信开销.,云计算环境下的大规模图数据处理技术,3.2 单指标分割技术,如果只考虑子图内敛性这一单项指标,即增大子图内部的关联性,降低子图之间的关联性,可采用聚类技术,效果十分明显.关于在云计算环境下实现分布式聚类的方法,在 Apache开源项目Mahout中有详细介绍.但是,聚类操作一般都是一 个迭代处理的过程,时间开销不容忽视.另外,聚类技术一般不考虑各聚簇之间的数据规模偏斜问题,很可能导致分割后的各子图的数据规模相差较大,增大了图处理过程中的水桶效应.,在改善子图分割的时间复杂度方面,Yahoo 研究院发现,即便图数据的原始规模很大,最终得到的聚簇仍然要小得多.基于这一发现,Yahoo 研究院开发出 Local Partition算法,该算法的运行时间与最终输出结果的聚簇大小成正比,而与图的原始输入数据规模无关,从而可以对更大规模的图进行分割处理.,云计算环境下的大规模图数据处理技术,3.2 单指标分割技术,此外,还有很多研究者从其它方面对分布式环境下的图分割技术进行了探索.,文献 35 采用随机森林(SF)方法,进行图分割.,文献 36 提出确定性和非确定性的分布式图分割算法 SyncPart、Fast_Part 和 Elect_Part.,文献 37 在使用 Hadoop 进行图的迭代处理时,通过设置Partitioner函数来不断调整图的分布.将一个 Reduce 任务处 理的图数据视 为一个 子图,通 过 Map 阶段和 Reduce 阶段的Shuffle 处理,使连通性较强的图顶点分布到同一个Reduce 任务并作为输出结果存储为一个单独的文件,在下一个 Map 阶段中加以利用,以减少通信量.以 PageRank应用为例,可以 针对顶点URL的内容,设计 Hash函数,使得关联较大的图顶点能够分配到同一个Reduce任务中.,后两种方 法虽然实现了子图之间的有效解耦,但由于子图的个数不确定和大小不均匀,导致并行处理的负载不平衡.,云计算环境下的大规模图数据处理技术,3.3 多指标分割技术,同时考虑子图数据规模均衡和子图内敛性等多项指标,也有很多研究者进行了尝试.,文献 38 针对分布式 P2P 网络,提出了一种基于图顶点度序列和广度优先搜索的 k-图 分割技术,能够 将一个 大型P2P 网络分割成 k 个子网络并且能够做到各子网络的任务负载均衡.,文献 39 通过 3 步处理来实现大规模图的分割:,(1)建立带权重的深度优先搜索树;,(2)将大 图分割成若干个 均衡的子图;,(3)迭代处理,尽量减少子图之间的关联.,GBASE系统利用现有的METIS、Disco等划分算法,对存储图数据的邻接矩阵进行聚类,将行和列重新排序,把一个大矩阵聚集为多个均匀区域,形成分块,保证块内的子图联系紧密,块间联系松散,将若干个块 作为一个网格,分给一个任务进行处理,在一定程度上解决了数据均衡问题.,云计算环境下的大规模图数据处理技术,3.3 多指标分割技术,同时考虑子图数据规模均衡和子图内敛性等多项指标,也有很多研究者进行了尝试.,文献 38 针对分布式 P2P 网络,提出了一种基于图顶点度序列和广度优先搜索的 k-图 分割技术,能够 将一个 大型P2P 网络分割成 k 个子网络并且能够做到各子网络的任务负载均衡.,文献 39 通过 3 步处理来实现大规模图的分割:,(1)建立带权重的深度优先搜索树;,(2)将大 图分割成若干个 均衡的子图;,(3)迭代处理,尽量减少子图之间的关联.,GBASE系统利用现有的METIS、Disco等划分算法,对存储图数据的邻接矩阵进行聚类,将行和列重新排序,把一个大矩阵聚集为多个均匀区域,形成分块,保证块内的子图联系紧密,块间联系松散,将若干个块 作为一个网格,分给一个任务进行处理,在一定程度上解决了数据均衡问题.,云计算环境下的大规模图数据处理技术,3.3 多指标分割技术,云计算环境下的大规模图数据处理技术,3.3 多指标分割技术,此外,Horton 系统中提出,对于需要长期存储的图数据采用静态处理和动态处理相结合的技术实现图分割.,在图数据载入分布式存储系统的过程中采用静态处理方法使用Evolving Sets技术将大图分割存储.新的图数据加入或更新时采用动态方法使用基于消息通信的 Affinity propagation 算法对已有的子图进行增量式分割和维护.,这种分割技术既能降低子图计算之间的耦合性又能保证负载平衡.,云计算环境下的大规模图数据处理技术,目 录,1.引 言,2.图数据模型与存储管理,5.图数据处理的执行机制,4.图计算模型与典型系统结构,3.图数据的分割策略,6.图查询处理,7.结束语,云计算环境下的大规模图数据处理技术,4.图计算模型与典型系统结构,本节介绍典型的云计算环境下大规模图数据处理的计算模型和一些典型的图处理系统.,计算模型决定了分布式并行执行方式是进行,解耦处理,和,提高可靠性,的基础.,云计算环境下的大规模图数据处理技术,4.1 MapReduce 模型和 BSP 模型,在云计算环境 中,最广泛使用的就是 MapReduce 模型.一个并行处理作业由多个 map任务和多个 reduce 任务组成.,作业的执行分为 Map 阶段和 Reduce 阶段：,在 Map 阶段,每个 map 任务对分配给它的数据(通常是本地的数据)进行计算,然后按照 map 的输出 key 值将结果数据映射 到对应的 reduce 任务中;,在 Reduce 阶段,每个 reduce 任务对接收到的数据做进一步聚集处理,得到输出结果.数据通常保存在分布式文件系统中,如 HDFS.,云计算环境下的大规模图数据处理技术,4.1 MapReduce 模型和 BSP 模型,BSP(Bulk Synchronous Parallel model)模型是2010 年图灵奖得主 Valiant 在 1990 年提出来的一种基于消息通信的并行执行模型.,一个 BSP 作业由若干个顺序执行的超步(super step)组成:S 1,S2,S n,对应于 n 次迭代处理.并行任务按照超步组织,在超步 S i 内,各任务异步接受来自S i-1 的消息,执行本地计算并发送消息给下一个超步 S i+1.在超步之间,通过显式地同步控制,确保所有任务均已完成超步 S i的工作.,这种同步方式可避免死锁和数据竞争问题.,云计算环境下的大规模图数据处理技术,4.1 MapReduce 模型和 BSP 模型,在云环境下实现大规模图的处理,主要采用这两种模型,下面将对比它们在图处理方面的特点.,在执行机制方面；,MapReduce 是一个数据流模型,每个任务只是对输入数据进行处理,产生的输出数据作为另一个任务的输入数据,并行任务之间独立地进行,串行任务之间以磁盘和数据复制作为交换介质和接口.,而 BSP 是一个状态模型,各个子任务在本地的子图数据上进行计算、通信、修改图的状态等操作.并行任务之间通过消息通信交流中间计算结果,不需要像MapReduce 那样对全体数据进行复制.,云计算环境下的大规模图数据处理技术,4.1 MapReduce 模型和 BSP 模型,在云环境下实现大规模图的处理,主要采用这两种模型,下面将对比它们在图处理方面的特点.,在执行机制方面；,在迭代处理方面；,MapReduce 模型理论上需要连续启动若干作业才可以完成图的迭代处理,相邻作业之间通过分布式文件系统交换全部数据.,BSP模型仅需启动一个作业,利用多个超步就可以完成迭代处理,两次迭代之间通过消息传递中间计算结果.由于减少了作业启动、调度开销和磁盘存取开销,BSP 模型的迭代执行效率较高.,云计算环境下的大规模图数据处理技术,在云环境下实现大规模图的处理,主要采用这两种模型,下面将对比它们在图处理方面的特点.,在执行机制方面；,在迭代处理方面；,在数据分割方面；,基于BSP的图处理模型,需要对加载后的图数据进行一次再分布的过程,以确定消息通信时的路由地址.例如,各任务并行加载数据过程中,根据一定的映射策略,将读入的数据重新分发到对应的计算任务上(通常是存放在内存中),既有磁盘 IO又有网络通信,开销很大.但是一个BSP作业仅需一次数据分割,在之后的迭代计算过程中除了消息通信之外,不再需要进行数据的迁移.,而基于MapReduce 的图处理模型,一般情况下,不需要专门的数据分割处理，但是 Map 阶段和 educe阶段存在中间结果的,Shuffle 过程,增加了磁盘 IO和网络通信开销.,4.1 MapReduce 模型和 BSP 模型,云计算环境下的大规模图数据处理技术,4.1 MapReduce 模型和 BSP 模型,MapReduce 模型的商业化应用已经开始推广,其良好的可伸缩性和容错管理能力受到了业界推崇,在大规模数据处理方面的表现也值得称赞.但是作为通用计算模型,在图处理方面,连续的作业调度和任务分配,代价较高,对于图拓扑结构信息的反复磁盘读取,尤其是从分布式文件系统上读取,也增大了 IO 开销.此外,在迭代处理方面,需要用户编程控制,较为繁琐.相对而言,BSP 模型是一个比较适合迭代处理的计算模型,为用户提供了简单易用的编程接口,Google,的 Pregel、Yahoo!的 Giraph和开源的 Hama系统,都是基于 BSP 模型开发的.,云计算环境下的大规模图数据处理技术,4.1 MapReduce 模型和 BSP 模型,从原理上讲,BSP 模型避免了 MapReduce 模型在多次迭代时的数据反复迁移和作业连续调度,其特有的超步和全局同步机制,使迭代处理的控制更加灵活,在大规模图处理方面很有开发前景.,但目前上述系统还处于研究开发阶段,所处理的数据放置于内存,未考虑索引问题,数据处理规模也受到极大的制约,需要进一步开发基于磁盘的系统并对I/O操作进行优化.,此外,BSP 模型中各任务之间的消息通信也是难以消除的效率瓶颈,而在容错管理等方面,尚无完善的理论和方法.,云计算环境下的大规模图数据处理技术,4.2 典型系统结构,目前,关于云计算环境下的大规模图数据管理系统,大致可以分为 3 类:基于 MapReduce模型的分布式并行处理系统、基于BSP 模型的分布式并行处理系统和分布式图数据库系统.,基于 MapReduce 模型的分布式并行处理系统,大部分是通用处理平台,如Hadoop 以及改进版本HOP 系统,可以应用于各种大规模数据处理,为了适应需要多次迭代的图处理应用,很多研究者对Hadoop 原有处理平台进行了优化改进,如 HaLoop、Twister、Prlter、HaLoop 使用缓存、索引技术来减少不必要的磁盘 IO,改进原有的任务调度模块使连续作业的调度和迭代条件的控制变得较为容易,具备一定的实用价值.,Twister 系统对 Hadoop进行了较大的改动,全部处理数据驻留内存,采用第3 方消息通信机制,使用任务池来避免多次作业调度.但是驻留内存的限制使其难以实用,目前只是供研究使