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

书书书 第３４卷　第１０期２０１１年１０月 计　　算　　机　　学　　报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｖｏｌ．３４Ｎｏ．１０Ｏｃｔ．２０１１　 收稿日期：２０１１０８１２；最终修改稿收到日期：２０１１０９１５．本课题得到国家自然科学基金（６１０３３００７，６１００３０５８）、中央高校基本科研业务 费专项资金（Ｎ０９０１０４００１）资助．于　戈，男，１９６２年生，博士，教授，博士生导师，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为数据 库理论和技术、分布与并行系统等．Ｅｍａｉｌ：ｙｕｇｅ＠ｍａｉｌ．ｎｅｕ．ｅｄｕ．ｃｎ．谷　峪，男，１９８１年生，博士，副教授，主要研究方向为ＲＦＩＤ、空间数 据管理、云计算．鲍玉斌，男，１９６８年生，博士，教授，主要研究领域为海量数据管理等．王志刚，男，１９８７年生，硕士研究生，主要研究方向 为数据库系统与云计算． 云计算环境下的大规模图数据处理技术 于　戈　谷　峪　鲍玉斌　王志刚 （东北大学信息科学与工程学院　沈阳　１１０８１９） （医学影像计算教育部重点实验室（东北大学）　沈阳　１１０８１９） 摘　要　随着社交网络分析、语义Ｗｅｂ分析、生物信息网络分析等新兴应用的快速增长，对亿万个顶点级别大规 模图的处理能力的需求愈加迫切，这是当前高性能计算领域的研究和开发热点．文中结合云计算的特点，从图数据 管理与图数据处理机制两个方面，综述了云计算环境下进行大规模图数据处理的关键问题，包括图数据的存储方 式、图索引结构、图分割策略、图计算模型、消息通信机制、容错管理、可伸缩性、图查询处理等．全面总结了当前的 研究现状和进展，详细分析了存在的挑战性问题，并深入探讨了未来的研究方向． 关键词　图处理；云计算；数据管理；分布式计算 中图法分类号ＴＰ３１１　　　犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１１．０１７５３ 犔犪狉犵犲犛犮犪犾犲犌狉犪狆犺犇犪狋犪犘狉狅犮犲狊狊犻狀犵狅狀犆犾狅狌犱犆狅犿狆狌狋犻狀犵犈狀狏犻狉狅狀犿犲狀狋狊 ＹＵＧｅ　ＧＵＹｕ　ＢＡＯＹｕＢｉｎ　ＷＡＮＧＺｈｉＧａｎｇ （犆狅犾犾犲犵犲狅犳犐狀犳狅狉犿犪狋犻狅狀犛犮犻犲狀犮犲犪狀犱犈狀犵犻狀犲犲狉犻狀犵，犖狅狉狋犺犲犪狊狋犲狉狀犝狀犻狏犲狉狊犻狋狔，犛犺犲狀狔犪狀犵　１１０８１９） （犓犲狔犔犪犫狅狉犪狋狅狉狔狅犳犕犲犱犻犮犪犾犐犿犪犵犲犆狅犿狆狌狋犻狀犵狅犳犕犻狀犻狊狋狉狔狅犳犈犱狌犮犪狋犻狅狀（犖狅狉狋犺犲犪狊狋犲狉狀犝狀犻狏犲狉狊犻狋狔），犛犺犲狀狔犪狀犵　１１０８１９） 犃犫狊狋狉犪犮狋　Ｗｉｔｈｔｈｅｒａｐｉｄｇｒｏｗｔｈｏｆｅｍｅｒｇｉｎｇａｐｐｌｉｃａｔｉｏｎｓｌｉｋｅｓｏｃｉａｌｎｅｔｗｏｒｋａｎａｌｙｓｉｓ，ｓｅｍａｎｔｉｃ Ｗｅｂａｎａｌｙｓｉｓ，ａｎｄｂｉｏｉｎｆｏｒｍａｔｉｃｓｎｅｔｗｏｒｋａｎａｌｙｓｉｓ，ｉｔｉｓｕｒｇｅｎｔｔｏｒｅｑｕｉｒｅｔｈｅｐｒｏｃｅｓｓｉｎｇｃａｐａｂｉｌｉ ｔｙｏｎｌａｒｇｅｓｃａｌｅｇｒａｐｈｓｗｉｔｈｂｉｌｌｉｏｎｓｏｆｖｅｒｔｉｃｅｓ，ｗｈｉｃｈｉｓｔｈｅｈｏｔｔｏｐｉｃｏｆｔｈｅｒｅｓｅａｒｃｈａｎｄｄｅｖｅｌ ｏｐｍｅｎｔｉｎｔｈｅｃｕｒｒｅｎｔｈｉｇｈｐｅｒｆｏｒｍａｎｃｅｃｏｍｐｕｔｉｎｇｆｉｅｌｄ．Ｗｉｔｈｔｈｅｆｅａｔｕｒｅｓｏｆｃｌｏｕｄｃｏｍｐｕｔｉｎｇ ａｎｄｆｒｏｍｔｈｅａｓｐｅｃｔｓｏｆｇｒａｐｈｍａｎａｇｅｍｅｎｔａｎｄｇｒａｐｈｐｒｏｃｅｓｓｉｎｇｍｅｃｈａｎｉｓｍｓ，ｔｈｉｓｐａｐｅｒｓｕｒｖｅｙｓ ｔｈｅｋｅｙｉｓｓｕｅｓｏｆｌａｒｇｅｓｃａｌｅｇｒａｐｈｐｒｏｃｅｓｓｉｎｇｏｎｃｌｏｕｄｃｏｍｐｕｔｉｎｇｅｎｖｉｒｏｎｍｅｎｔｓ，ｉｎｃｌｕｄｉｎｇｇｒａｐｈ ｄａｔａｓｔｏｒａｇｅｓｃｈｅｍｅ，ｉｎｄｅｘｓｔｒｕｃｔｕｒｅｏｆｇｒａｐｈｄａｔａ，ｇｒａｐｈｐａｒｔｉｔｉｏｎｉｎｇｓｔｒａｔｅｇｙ，ｇｒａｐｈｃｏｍｐｕｔｉｎｇ ｍｏｄｅｌ，ｍｅｓｓａｇｅｃｏｍｍｕｎｉｃａｔｉｏｎｍｅｃｈａｎｉｓｍ，ｆａｕｌｔｔｏｌｅｒａｎｃｅｍａｎａｇｅｍｅｎｔ，ｓｃａｌａｂｉｌｉｔｙ，ａｎｄｇｒａｐｈ ｑｕｅｒｙｐｒｏｃｅｓｓｉｎｇ．Ｔｈｉｓｐａｐｅｒｓｕｍｍａｒｉｚｅｓｔｈｅｓｔａｔｅｏｆａｒｔｏｆｃｕｒｒｅｎｔｒｅｓｅａｒｃｈｗｏｒｋｓｃｏｍｐｌｅｔｅｌｙ， ａｎａｌｙｚｅｓｔｈｅｅｘｉｓｔｉｎｇｃｈａｌｌｅｎｇｅｐｒｏｂｌｅｍｓｉｎｄｅｔａｉｌ，ａｎｄｄｅｅｐｌｙｅｘｐｌｏｒｅｓｔｈｅｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎｓｉｎ ｆｕｔｕｒｅ． 犓犲狔狑狅狉犱狊　ｇｒａｐｈｐｒｏｃｅｓｓｉｎｇ；ｃｌｏｕｄｃｏｍｐｕｔｉｎｇ；ｄａｔａｍａｎａｇｅｍｅｎｔ；ｄｉｓｔｒｉｂｕｔｅｄｃｏｍｐｕｔｉｎｇ １　引　言 图是计算机科学中最常用的一类抽象数据结 构，在结构和语义方面比线性表和树更为复杂，更具 有一般性表示能力．现实世界中的许多应用场景都 需要用图结构表示，与图相关的处理和应用几乎无 所不在．传统应用如最优运输路线的确定、疾病爆发 路径的预测、科技文献的引用关系等；新兴应用如社 交网络分析、语义Ｗｅｂ分析、生物信息网络分析等． 虽然图的应用和处理技术已经发展了很长时 间，理论也日趋完善，但是随着信息化时代的到来， 各种信息以爆炸模式增长，导致图的规模日益增大， 如何对大规模图进行高效处理，成为一个新的挑战． １１　大规模图数据处理问题 以互联网和社交网络为例，近十几年来，随着互 联网的普及和Ｗｅｂ２．０技术的推动，网页数量增长 迅猛，据ＣＮＮＩＣ统计，２０１０年中国网页规模达到 ６００亿，年增长率７８．６％，而基于互联网的社交网络 也后来居上，如全球最大的社交网络Ｆａｃｅｂｏｏｋ，已 有约７亿用户，国内如ＱＱ空间、人人网等，发展也 异常迅猛． 真实世界中实体规模的扩张，导致对应的图数 据规模迅速增长，动辄有数十亿个顶点和上万亿条 边．本文所指的大规模强调的就是单个图的大规模 性，通常包含１０亿个以上顶点．面对这样大规模的 图，对海量数据处理技术提出了巨大挑战．以搜索引 擎中常用的ＰａｇｅＲａｎｋ计算［１］为例，一个网页的 ＰａｇｅＲａｎｋ得分根据网页之间相互的超链接关系计 算而得到．将网页用图顶点表示，网页之间的链接关 系用有向边表示，按邻接表形式存储１００亿个图顶 点和６００亿条边，假设每个顶点及出度边的存储空 间占１００字节，那么整个图的存储空间将超过１ＴＢ． 如此大规模的图，对其存储、更新、查找等处理的时 间开销和空间开销远远超出了传统集中式图数据管 理的承受能力．针对大规模图数据的高效管理，如存 储、索引、更新、查找等，已经成为急需解决的问题． １２　采用云计算环境处理大规模图的优势 云计算是网格计算、分布式计算、并行计算、效 用计算、网络存储、虚拟化等先进计算机技术和网络 技术发展融合的产物，具有普遍适用性．云计算技术 的发展，一直与大规模数据处理密切相关．因此，依 靠云计算环境对大规模图数据进行高效处理，是一 个非常有发展潜力的方向，其主要优势表现在： （１）海量的图数据存储和维护能力．大规模图 的数据量可达几百ＧＢ甚至ＰＢ级别，难以在传统文 件系统或数据库中存储，而云计算环境提供分布式 存储模式，可以汇聚成百上千普通计算机的存储能 力和计算能力，提供高容量的存储服务，完全能够存 放和处理大规模的图数据．云计算环境下的并发控 制、一致性维护、数据备份和可靠性等控制策略，可 以为大规模图数据的维护提供保障． （２）强大的分布式并行处理能力．利用云计算 分布平行处理的特点，可以将一个大图分割成若干 子图，把针对一个大图的处理分割为若干针对子图 的处理任务．云计算分布式并行运算能力，能够显著 提高对大规模图的处理能力． （３）良好的可伸缩性和灵活性．从技术角度和 经济角度讲，云计算环境具有良好的可伸缩性和灵 活性，非常适合处理数据量弹性变化的大规模图问 题．云计算环境通常由廉价的普通计算机构成．随着 图数据规模的不断增大，可以向云中动态添加节点 来扩展存储容量和计算资源，而无需传统并行机模 式的巨大投资． １３　关键技术挑战 虽然云计算环境对于大规模图数据的管理有诸 多优势，但是由于云计算只是一个通用的处理框架， 而且其本身也正处于发展阶段，如何在云计算环境 下进行大规模图数据处理，仍有很多关键技术难题 需要解决．图计算及其分布式并行处理通常涉及复 杂的处理过程，需要大量的迭代和数据通信，针对联 机事务处理等应用的传统技术很难直接应用到图数 据处理中．云计算环境下的大规模图处理主要面临 两大挑战： （１）图计算的强耦合性．在一个图中，数据之间 都是相互关联的，图的计算也是相互关联的．图计算 的并行算法中对内存的访问表现出很低的局部 性［２］．对于几乎每一个顶点之间都是连通的图来讲， 难以分割成若干完全独立的子图以进行独立的并行 处理．并且，“水桶效应”问题加剧，即先完成的任务 需要等待后完成的任务，处理速度最慢的任务，将成 为整个系统的效率制约瓶颈．为了提高执行效率，需 要采取多种优化技术．首先，在预处理阶段，进行合 适的图分割时，尽可能地降低子图之间的耦合性；其 次，在执行阶段，应选取合适的图计算模型，避免迭 代过程中反复启动任务和读写磁盘，降低任务调度 开销和ＩＯ开销；应充分利用迭代过程中的收敛特性 进行查询优化，同时进行有效的同步控制和消息通信 优化，减少通信开销，以达到降低水桶效应的目的． （２）云计算节点的低可靠性．大规模图处理，需 要相对较长的时间来完成计算任务，如ＰａｇｅＲａｎｋ 计算需要约３０次迭代处理，消耗大量的时间和资 源．而云计算节点通常是由普通的计算机组成，在这 种长时间的处理过程中，个别节点出现故障是难免 的．这时，不能简单地重新计算，而应该从断点或者 某个合适的位置接续执行．否则，将造成很大的浪 ４５７１ 计　　算　　机　　学　　报 ２０１１年 费，甚至一些大型的图计算根本就不能完成．另一方 面，由于图计算并行子任务之间的强耦合性，一个子 任务的失败可能导致其它子任务的失败，这又增加 了恢复处理的复杂性．因此，需要考虑有效的容错管 理机制，减少大规模图处理过程中的故障恢复开销， 尽量避免重复计算，提高大规模图处理的运算效率 和稳定性． 为了解决云计算环境下的大规模图处理问题， 可从图数据管理和图处理机制两方面加以考虑．在 图数据管理上，需要解决图数据的分割、图数据的存 储、图数据索引的建立、图查询处理等问题；在图处 理机制上，需要解决处理过程中图计算模型选取、同 步控制、消息通信、容错管理和可伸缩性等问题．本 文将针对上述内容，结合云计算的优势和存在的挑 战，综述云计算环境下的大规模图处理现有技术的 进展、解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 以及今后的发展趋势和研究方向． ２　图数据模型与存储管理 图数据的逻辑表达形式和物理存储结构是实现 图处理的基础．本节首先介绍图数据模型，然后，介 绍图的存储管理以及为了提高查找效率而为图数据 建立的索引结构． ２１　图数据模型 作为数学的一个重要分支，图论以图作为研究 对象，在简单图的基础上衍生出超图理论、极图理 论、拓扑图论等，使图可以从多方面表达现实世界． 当前大规模图数据管理，采用的数据模型有多种，按 照图中节点的复杂程度分为简单节点图模型和复杂 节点图模型［３］；按照一条边可以连接的顶点数目分 为简单图模型和超图模型．不论是简单图模型、超图 模型、简单节点模型还是复杂节点模型，它们的顶点 和边都可以带有属性．下面介绍简单图模型和超图 模型，其它模型请参考文献［４］． （１）简单图模型．这里所说的简单图，并不是图 论中的简单图，是相对于超图而言的．简单图中，一 条边只能连接两个顶点允许存在环路．简单图的存 储和处理都比较容易，对于一般的应用，简单图的表 达能力完全可以胜任，如ＰａｇｅＲａｎｋ计算、最短路径 查询等．Ｐｒｅｇｅｌ、Ｈａｍａ等系统均采用简单图模型来 组织存储和处理大规模图数据［５６］． （２）超图模型．一条边可以连接任意数目的图 顶点．此模型中图的边称为超边．基于这种特点，超 图比上述简单图的适用性更强，保留的信息更多．例 如，以图顶点代表文章，每条边代表两个顶点（文章） 享有同一个作者．现有３篇文章犞１（作者Ａ、Ｂ）、犞２ （作者Ａ、Ｃ）、犞３（作者Ａ、Ｄ），３篇文章的作者都有 Ａ．图１（ａ）表示了简单图存储模式，３条独立的边 犲１，犲２，犲３＝｛狏１，狏２｝，｛狏１，狏３｝，｛狏２，狏３｝，无法直接保留 作者Ａ同时是３篇文章犞１、犞２、犞３的作者这一信 息．图１（ｂ）代表了超图存储模式，超边犲１＝｛狏１，狏２， 狏３｝直接保留了Ａ是３篇文章犞１、犞２、犞３的作者这一 信息．对于具有复杂联系的应用，可以使用超图模型 建模，例如社交网络、生物信息网络等．Ｔｒｉｎｉｔｙ等图数 据库系统支持超图模型来管理大规模图数据［７］． 图１　简单图和超图 ２２　图数据的存储方式 在目前的大规模图数据管理应用中，主要采用 简单图和超图两种数据模型，二者的组织存储格式 略有不同．这两种模型都可以处理有向图和无向图， 默认情况是有向图，而无向图中的边可以看作是两 条有向边，即有向图的一种．在之后的讨论中不再强 调图中边的方向． 简单图模型的常用存储结构包括邻接矩阵、邻 接表、十字链表和邻接多重表等多种方式．从大规模 图处理的应用需求和维护的复杂程度考虑，邻接矩 阵和邻接表是最常用的两种结构．采用邻接矩阵表 示图的拓扑结构，直观简洁，便于快速查找顶点之间 的关系，但是邻接矩阵的存储代价高昂，对于大规模 图数据，这个问题尤为严重．ＧＢＡＳＥ系统以邻接矩 阵的形式组织存储图，考虑到邻接矩阵的存储开销， ＧＢＡＳＥ对矩阵进行了聚簇分割，尽量将矩阵中的 非零值集中存储并采用Ｚｉｐ技术压缩编码，减少矩 阵的存储代价［８］．与邻接矩阵相比，邻接表的应用范 围更加广泛．像ＰａｇｅＲａｎｋ计算、最短路径计算等应 用，并不需要频繁查找两个图顶点之间的连通性，邻 接表完全可以满足计算需求．邻接表的存储开销小， 逻辑简单，便于分割处理，是一种比较理想的图组织 方式，Ｐｒｅｇｅｌ、Ｈａｍａ和ＨａＬｏｏｐ等系统均采用邻接 表的形式组织图数据［５６，９］．超图模型的组织方式主 要使用关系矩阵［１０］．从形式上讲，关系矩阵和邻接 ５５７１１０期 于　戈等：云计算环境下的大规模图数据处理技术 矩阵较为相似，但是矩阵的行和列分别表示图顶点 编号和超边的编号． 大规模的图数据存储需要依赖云计算环境的分 布式存储系统．云计算环境的存储系统分为两种：一 种是以ＧＦＳ［１１］、ＨＤＦＳ［１２］为代表的分布式文件系 统，对于邻接矩阵、邻接表等结构，可以直接存放；另 一种是以ＢｉｇＴａｂｌｅ［１３］、Ｈｂａｓｅ［１２］为代表的ＮｏＳＱＬ （ＮｏｔＯｎｌｙＳＱＬ）分布式数据库． ＮｏＳＱＬ数据库采用的数据模型主要有文档存 储（ＤｏｃｕｍｅｎｔＳｔｏｒｅ）模型、列族存储（ＣｏｌｕｍｎＦａｍｉ ｌｙＳｔｏｒｅ）模型、ＫｅｙＶａｌｕｅ存储模型、图存储模型等 几大类［１４］．文档存储模型在存储格式方面十分灵 活，比较适合存储系统日志等非结构化数据， ＣｏｕｃｈＤＢ和ＭｏｎｇｏＤＢ是采用这种存储模型的典型 系统［１５１６］．但是，文档存储模型不太适合以邻接矩 阵或邻接表组织的图数据．此外，文档存储模型为支 持灵活性所导致的处理效率的降低也会成为大规模 图数据管理的性能瓶颈．列族存储模型比较适合对某 一列进行随机查询处理，但是对于穷举式遍历，反而 不如传统的面向行的存储模式．采用该存储模型的 典型系统有ＢｉｇＴａｂｌｅ、Ｈｂａｓｅ、Ｃａｓｓａｎｄｒａ等［２，１３，１７］． 图存储模型的相关研究目前还不完善，只有少数分 布式图数据库，如Ｎｅｏ４ｊ［１８］等采用这种模型存储图 数据． 与上述３种存储模型相比，ＫｅｙＶａｌｕｅ存储模 型较为适合存储大规模图数据．ＫｅｙＶａｌｕｅ存储模 型的存储模式简单，支持海量数据存储和高并发查 询操作，非常适合通过主键进行查询或遍历，但对复 杂的条件查询支持度不佳．采用该模型的典型系统 有Ｄｙｎａｍｏ和ＳｉｍｐｌｅＤＢ［１９２０］．从图处理的角度出 发，像ＰａｇｅＲａｎｋ计算等，并不需要复杂查询，Ｋｅｙ Ｖａｌｕｅ模型完全可以胜任．若图数据采用邻接表组 织，可以将图的源顶点作为Ｋｅｙ，将源顶点值、出边 及边信息作为Ｖａｌｕｅ．文献［２１］结合语义Ｗｅｂ和传 统的ＫｅｙＶａｌｕｅ存储模型，提出ＫｅｙＫｅｙＶａｌｕｅ存 储模型．以社交网络为例，ＫｅｙＫｅｙＶａｌｕｅ模型将 犃犾犻犮犲和犅狅犫之间的好友关系组织为一个三元组 〈犃犾犻犮犲，犅狅犫，犉狉犻犲狀犱犛犺犻狆〉．该模型存储的信息比传 统的ＫｅｙＶａｌｕｅ模型更加丰富，可以据此进行数据 迁移和合并，以提高空间局部性，使得在查询处理时 能减少远程读取数据的次数，因而可以提高数据读 取效率． 此外，对于分布式图数据库，当图数据更新时，需 要提供事务功能，解决在分布式环境下的一致性控制 问题．ＨｙｐｅｒＧｒａｐｈＤＢ和Ｔｒｉｎｉｔｙ等人都宣称自己支 持事务机制和一致性控制［７，２２］．如果图数据存储在 ＨＤＦＳ类型的分布式文件系统上，因其不支持更新 和随机插入操作［１２］，也就不存在一致性维护问题． 上面讨论了ＮｏＳＱＬ数据库的４种主要存储模 型．文献［２３］从管理数据的规模和模型的复杂性两 个维度比较了这４种基本存储模型，见图２． 图２　ＮｏＳＱＬ数据库的４种主要存储模型的比较 从图２可以看出ＫｅｙＶａｌｕｅ存储的复杂性最 低，存储数据的规模可以很高，而基于图存储模型的 图数据库的复杂性最高，且存储图数据的规模较低， 不过也可以管理１０亿个以上的顶点及其对应的边． ２３　图数据的索引结构 索引是传统关系数据库中的关键技术，包括 Ｂ＋树索引、Ｈａｓｈ索引、位图索引等，技术较为成 熟，可以提高数据查询处理效率，尤其是在查询结果 的数据量远小于原始数据的情况下．对于一个大规 模图，云计算的分布式并行处理机制，可以根据查询 条件遍历所有的子图数据，如果查询结果的数据量 较大，这种处理方式的性能是比较好的，但是如果查 询结果的数量很小，则会访问很多无用的数据，造成 计算资源的浪费和查询效率的低下，而通过建立合 适的索引，可以有效解决这一问题． 在云计算环境下，大规模图的原始数据保留在 分布式存储系统上，建立的索引也必然是分布式的． 如果图的原始数据规模很大，那么它的索引文件也 会很大．另外，分布式环境和数据更新的延迟，也加 剧了索引维护的难度．因此，云计算环境下的图数据 的索引，无论是存储还是维护都是十分棘手的问题． 从使用目的和实际效果的角度，索引可分为两 大类：一种是为支持普通查询而在云计算环境下建 立索引，有助于提高数据查找效率，主要在分布式图 数据库中使用；另一种是为加快计算处理而建立的 索引，主要在图的计算处理应用中使用，如最短路径 计算、ＰａｇｅＲａｎｋ计算、聚类分析等． 目前用于云计算环境下的索引技术，很少有专 ６５７１ 计　　算　　机　　学　　报 ２０１１年 门针对图数据的．但是，这些索引技术大都是可以被 图数据存储所利用．目前的云环境下用于数据管理 的索引结构可以分为适用于Ｐ２Ｐ网络结构的索 引［２４２６］以及适用于Ｓｈａｒｅｄｎｏｔｈｉｎｇ集群结构的索 引［２７２８］．文献［２４］针对云计算环境下的大规模数据 查询处理，提出了二级索引技术ＣＧｉｎｄｅｘ．它首先 在每一个数据分片上建立本地Ｂ＋ｔｒｅｅ形成索引分 片，然后将计算节点组织成Ｏｖｅｒｌａｙ结构，接下来基 于Ｏｖｅｒｌａｙ的路由 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 把各个计算节点上Ｂ＋ｔｒｅｅ 分片发布到Ｏｖｅｒｌａｙ上，建立全局索引ＣＧｉｎｄｅｘ．这 种索引具有自适应性和可扩展性．文献［２５］建立了 多维索引机制ＲＴＣＡＮ，集成ＣＡＮ协议和Ｒ树的 特点，在云计算环境下提供高效查询服务．文献［２６］ 也针对Ｐ２Ｐ环境，在分布式ＫＤｔｒｅｅ基础上提出多 维索引ＭＩＤＡＳ，用以支持多维查询、范围查询和犽 最近邻查询等应用．文献［２７］提出了一个通用的、灵 活的、容错的、且可扩展的分布式Ｂｔｒｅｅ索引结构． 文献［２８］将Ｒｔｒｅｅ和ＫＤｔｒｅｅ结合起来组织数据 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 ，提出了用于云数据管理的多维索引ＥＭＩＮＣ， 可以提供快速的查询处理和有效的索引维护． 云计算环境下的通用索引机制，没有考虑图结 构的特点，在图查询处理方面，效果不明显．而分布 式图数据库，无论是数据存储还是索引结构，都针对 图数据进行了优化．Ｎｅｏ４ｊ的索引分为两类［１８］：数据 库本身就是一个树形结构的索引，可用于提高查询 效率，此外，还可以使用独立的Ｌｕｃｅｎｅ索引，提供全 文索引和索引命中率排序功能．Ｎｅｏ４ｊ可以对图顶 点和边分别建立索引，通过对索引的缓存，可进一步 加快查找速度．索引的维护操作（如删除、更新）则必 须在事务管理机制下进行．对于更新，必须先删除旧 的索引值，然后才能添加新索引值，代价较高． ＩｎｆｉｎｉｔｅＧｒａｐｈ［２９］与Ｎｅｏ４ｊ类似，也提供内建索引和 Ｌｕｃｅｎｅ索引．在ＨｙｐｅｒＧｒａｐｈＤＢ的两层存储架 构［２２］中，索引是存储层必备的组成部分，一个Ｋｅｙ 可对应多个已排序的Ｖａｌｕｅ，并支持Ｖａｌｕｅ共享；在 模型层，Ｋｅｙ采用ＵＵＩＤ编号并排序，在Ｋｅｙ上建 立索引．索引文件以Ｂｔｒｅｅ格式存储并具有缓存功 能，可以为查询等操作提供持久化的元数据信息． Ｔｒｉｎｉｔｙ数据库提供Ｔｒｉｅ树和Ｈａｓｈ两种索引结构 来访问图顶点、边的名字以及相关的其它信息，可减 少有公共前缀的字符串的匹配次数［７］． 支持图计算处理的索引，主要是在云计算平台 中体现．文献［３０］针对Ｈａｄｏｏｐ系统中的Ｓｈｕｆｆｌｅ过 程和Ｒｅｄｕｃｅ过程进行了改进，采用动态增量式 Ｈａｓｈ索引和缓存技术降低Ｓｈｕｆｆｌｅ过程的磁盘ＩＯ 代价，提高ＣＰＵ利用率．ＨａＬｏｏｐ则对Ｍａｐ任务的 输入、Ｒｅｄｕｃｅ任务的输入和输出进行缓存并建立索 引，在一定程度上提高了Ｈａｄｏｏｐ迭代处理的效 率［９］．文献［３１］针对ＭａｐＲｅｄｕｃｅ的连接操作，提出 Ｔｒｏｊａｎ索引技术，通过对分片信息和犓犲狔值的重新 构造，建立索引，使需要连接的数据位于同一个分片 上，减少连接操作的网络通信量．由于ＭａｐＲｅｄｕｃｅ 模型是一个通用计算模型，Ｈａｄｏｏｐ处理平台的索 引也是通用性的，对于大规模图的迭代处理的针对 性并不强． ３　图数据的分割策略 在云计算环境下，对于一个大规模图的处理，必 须进行分布式并行处理．由于图数据本身固有的连 通性和图计算表现出强耦合性的特点，为了实现高 效的并行处理，尽可能降低分布式处理的各子图之 间的耦合度是非常重要的．有效的图分割就是实现 解耦的重要手段．这首先要将一个逻辑上完整的大 图分割成若干部分，分别放置到分布式存储系统的 各工作节点上．其后对图的处理，就是针对已经分布 式存放的每一个子图，启动一个计算任务，进行相同 的处理操作，当所有子图处理结束，则完成整个大图 的一次处理了． ３１　图分割原则 虽然并行处理可以提高效率，但是由于子图之 间的连通性，在任务执行过程中或执行结束时，各任 务之间需要进行消息通信，这个通信处理的代价很 大，是制约图处理效率的瓶颈．如果在大图存储或处 理之前，利用良好的图分割算法，将一个大图分割成 若干个适当大小的子图，且子图内部具有较高的连 通性，而子图之间的连通性较低，那么相当一部分消 息就不需要通过网络跨节点传输，而是直接本地处 理，可以极大地减少通信代价，提高整个系统的运行 效率． 在云计算环境下，实现大图分割并取得较好的 分割效果，是一项挑战性很大的工作．将一个大图分 割为若干子图，有两个主要原则：一是提高子图内部 的连通性，降低子图之间的连通性，这种特点尤其适 合云计算的分布式并行处理机制；二是考虑子图规 模的均衡性，尽量保证各子图的数据规模均衡，不要 出现较大的偏斜，从数据规模方面防止各并行任务 的执行时间相差过大，降低任务同步控制过程中“水 ７５７１１０期 于　戈等：云计算环境下的大规模图数据处理技术 桶效应”的影响．当然，大图分割的时间复杂度必须 控制在可以忍受的范围内．图３对比了３种不同的 图分割效果，如果单纯考虑子图的数据均衡或子图 之间的连通性，其效果均不理想，只有同时考虑着两 个因素，才能显著提高分布并行式处理效率． 图３　３种图分割效果 ３２　单指标分割技术 如果只考虑数据负载均衡这一单项指标，最简 单的图分割技术，就是Ｈａｓｈ方式，即在设定了分片 数目之后，对图顶点ＩＤ进行Ｈａｓｈ，将数据划分成给 定数目的分片．这种分割方法效率很高，时间复杂度 为犗（狀），可以在图数据的载入过程中或图处理之前 完成分片操作．在一定条件下，设计良好的Ｈａｓｈ方 式可以避免数据偏斜，使各子图的数据规模接近相 同．但是Ｈａｓｈ方式没有考虑图数据的局部性，甚至 连原始数据的局部性也无法得到保留．Ｈａｓｈ方式 虽然在云计算环境下容易实现，但是，负责各子图处 理的任务之间消息通信频繁，会造成较大的网络通 信开销． 如果只考虑子图内敛性这一单项指标，即增大 子图内部的关联性，降低子图之间的关联性，可采用 聚类技术，效果十分明显．关于在云计算环境下实现 分布式聚类的方法，在Ａｐａｃｈｅ开源项目Ｍａｈｏｕｔ中有详细介绍［３２］．但是，聚类操作一般都是一个迭代 处理的过程，时间开销不容忽视．另外，聚类技术一 般不考虑各聚簇之间的数据规模偏斜问题，很可能 导致分割后的各子图的数据规模相差较大，增大了 图处理过程中的“水桶效应”．在改善子图分割的时 间复杂度方面，Ｙａｈｏｏ研究院发现，即便图数据的原 始规模很大，最终得到的聚簇仍然要小得多［３３］．基 于这一发现，Ｙａｈｏｏ研究院开发出“ＬｏｃａｌＰａｒｔｉｔｉｏｎ” 算法［３４］，该算法的运行时间与最终输出结果的聚簇 大小成正比，而与图的原始输入数据规模无关，从而 可以对更大规模的图进行分割处理． 此外，还有很多研究者从其它方面对分布式环 境下的图分割技术进行了探索．文献［３５］采用随机 森林（ＳＦ）方法，进行图分割．文献［３６］提出了确定 性和非确定性的分布式图分割算法Ｓｙｎｃ＿Ｐａｒｔ、Ｆａｓｔ ＿Ｐａｒｔ和Ｅｌｅｃｔ＿Ｐａｒｔ．文献［３７］在使用Ｈａｄｏｏｐ进行 图的迭代处理时，通过设置Ｐａｒｔｉｔｉｏｎｅｒ函数来不断 调整图的分布．将一个Ｒｅｄｕｃｅ任务处理的图数据 视为一个子图，通过Ｍａｐ阶段和Ｒｅｄｕｃｅ阶段的 Ｓｈｕｆｆｌｅ处理，使连通性较强的图顶点分布到同一个 Ｒｅｄｕｃｅ任务并作为输出结果存储为一个单独的文 件，在下一个Ｍａｐ阶段中加以利用，以减少通信量． 以ＰａｇｅＲａｎｋ应用为例，可以针对顶点ＵＲＬ的内 容，设计Ｈａｓｈ函数，使得关联较大的图顶点能够分 配到同一个Ｒｅｄｕｃｅ任务中．后两种方法虽然实现 了子图之间的有效解耦，但由于子图的个数不确定 和大小不均匀，导致并行处理的负载不平衡． ３３　多指标分割技术 同时考虑子图数据规模均衡和子图内敛性等多 项指标，也有很多研究者进行了尝试．文献［３８］针对 分布式Ｐ２Ｐ网络，提出了一种基于图顶点度序列和 广度优先搜索的犽图分割技术，能够将一个大型 Ｐ２Ｐ网络分割成犽个子网络并且能够做到各子网络 的任务负载均衡．文献［３９］通过３步处理来实现大 规模图的分割：（１）建立带权重的深度优先搜索树； （２）将大图分割成若干个均衡的子图；（３）迭代处 理，尽量减少子图之间的关联．ＧＢＡＳＥ系统［８］利用 现有的ＭＥＴＩＳ、Ｄｉｓｃｏ等划分算法，对存储图数据的 邻接矩阵进行聚类，将行和列重新排序，把一个大矩 阵聚集为多个均匀区域，形成分块，保证块内的子图 联系紧密，块间联系松散，将若干个块作为一个网 格，分给一个任务进行处理，在一定程度上解决了数 据均衡问题． ＫｅｒｎｉｇｈａｎＬｉｎ算法［４０］既考虑了聚类技术的特 点，同时又可以保证分割后的子图在数据规模上的 均衡性，主要用于网络节点的分割．其主要思想是首 先将一个网络图分割成两个大小相等的顶点集合犃 和犅，在集合犃和犅中的顶点，除了和本集合内的 顶点有边连接外，还可能和另外一个集合内的顶点 有边连接．对于后者，用犜表示所有这种连接边的 权重之和，作为衡量集合犃和犅之间连通性的指 标．ＫＬ算法在执行过程中，不断调整集合犃和犅 内的顶点，直到犜值最小．但是，ＫＬ算法的时间复 杂度过高，是犗（狀２ｌｏｇ狀），其中狀是图顶点的数量， 随着图顶点数据规模的增大，将超出目前的计算处 理能力．为降低时间复杂度．文献［４１］提出基于 Ｑｕｉｃｋ＿Ｃｕｔ技术的ＫＬ算法，利用“邻居搜索”的特 点，避免了不必要图顶点的遍历，达到时间复杂度为 犗（ｍａｘ（犲犱，犲ｌｏｇ狀）），其中，犲是边的数量，犱是图顶 点的最大出度值． ８５７１ 计　　算　　机　　学　　报 ２０１１年 此外，Ｈｏｒｔｏｎ系统［４２］中提出，对于需要长期存 储的图数据，采用静态处理和动态处理相结合的技 术实现图分割．在图数据载入分布式存储系统的过 程中，采用静态处理方法，使用“ＥｖｏｌｖｉｎｇＳｅｔｓ”技 术［４３］，将大图分割存储．新的图数据加入或更新时， 采用动态方法，使用基于消息通信的Ａｆｆｉｎｉｔｙｐｒｏｐ ａｇａｔｉｏｎ算法［４４］对已有的子图进行增量式分割和维 护．这种分割技术既能降低子图计算之间的耦合性， 又能保证负载平衡． ４　图计算模型与典型系统结构 本节介绍典型的云计算环境下大规模图数据处 理的计算模型和一些典型的图处理系统．计算模型 决定了分布式并行执行方式，是进行解耦处理和提 高可靠性的基础． ４１　犕犪狆犚犲犱狌犮犲模型和犅犛犘模型 在云计算环境中，最广泛使用的就是ＭａｐＲｅ ｄｕｃｅ模型［４５］．一个并行处理作业由多个ｍａｐ任务 和多个ｒｅｄｕｃｅ任务组成．作业的执行分为Ｍａｐ阶 段和Ｒｅｄｕｃｅ阶段．在Ｍａｐ阶段，每个ｍａｐ任务对 分配给它的数据（通常是本地的数据）进行计算，然 后按照ｍａｐ的输出犽犲狔值将结果数据映射到对应 的ｒｅｄｕｃｅ任务中；在Ｒｅｄｕｃｅ阶段，每个ｒｅｄｕｃｅ任务 对接收到的数据做进一步聚集处理，得到输出结果． 数据通常保存在分布式文件系统中，如ＨＤＦＳ． ＢＳＰ（ＢｕｌｋＳｙｎｃｈｒｏｎｏｕｓＰａｒａｌｌｅｌｍｏｄｅｌ）模型是 ２０１０年图灵奖得主Ｖａｌｉａｎｔ在１９９０年提出来的一 种基于消息通信的并行执行模型［４６］．一个ＢＳＰ作业 由若干个顺序执行的超步（ｓｕｐｅｒｓｔｅｐ）组成：犛１， 犛２，…，犛狀，对应于狀次迭代处理．并行任务按照超步 组织，在超步犛犻内，各任务异步接受来自犛犻－１的消 息，执行本地计算并发送消息给下一个超步犛犻＋１． 在超步之间，通过显式地同步控制，确保所有任务均 已完成超步犛犻的工作．这种同步方式可避免死锁和 数据竞争问题． 在云环境下实现大规模图的处理，主要采用这 两种模型，下面将对比它们在图处理方面的特点． 在执行机制方面，ＭａｐＲｅｄｕｃｅ是一个数据流模 型，每个任务只是对输入数据进行处理，产生的输出 数据作为另一个任务的输入数据，并行任务之间独 立地进行，串行任务之间以磁盘和数据复制作为交 换介质和接口．而ＢＳＰ是一个状态模型，各个子任 务在本地的子图数据上进行计算、通信、修改图的状 态等操作．并行任务之间通过消息通信交流中间计 算结果，不需要像ＭａｐＲｅｄｕｃｅ那样对全体数据进行 复制． 在迭代处理方面，ＭａｐＲｅｄｕｃｅ模型理论上需要 连续启动若干作业才可以完成图的迭代处理，相邻 作业之间通过分布式文件系统交换全部数据．ＢＳＰ 模型仅需启动一个作业，利用多个超步就可以完成 迭代处理，两次迭代之间通过消息传递中间计算结 果．由于减少了作业启动、调度开销和磁盘存取开 销，ＢＳＰ模型的迭代执行效率较高． 在数据分割方面，基于ＢＳＰ的图处理模型，需 要对加载后的图数据进行一次再分布的过程，以确 定消息通信时的路由地址．例如，各任务并行加载数 据过程中，根据一定的映射策略，将读入的数据重新 分发到对应的计算任务上（通常是存放在内存中）， 既有磁盘ＩＯ又有网络通信，开销很大．但是一个 ＢＳＰ作业仅需一次数据分割，在之后的迭代计算过 程中除了消息通信之外，不再需要进行数据的迁移． 而基于ＭａｐＲｅｄｕｃｅ的图处理模型，一般情况下，不需 要专门的数据分割处理．但是Ｍａｐ阶段和Ｒｅｄｕｃｅ 阶段存在中间结果的Ｓｈｕｆｆｌｅ过程，增加了磁盘ＩＯ 和网络通信开销． ＭａｐＲｅｄｕｃｅ模型的商业化应用已经开始推广， 其良好的可伸缩性和容错管理能力受到了业界推 崇，在大规模数据处理方面的表现也值得称赞．但是 作为通用计算模型，在图处理方面，连续的作业调度 和任务分配，代价较高，对于图拓扑结构信息的反复 磁盘读取，尤其是从分布式文件系统上读取，也增大 了ＩＯ开销．此外，在迭代处理方面，需要用户编程控 制，较为繁琐．相对而言，ＢＳＰ模型是一个比较适合迭 代处理的计算模型，为用户提供了简单易用的编程 接口，Ｇｏｏｇｅｌ的Ｐｒｅｇｅｌ［５］、Ｙａｈｏｏ！的Ｇｉｒａｐｈ［４７］和开 源的Ｈａｍａ系统［６］，都是基于ＢＳＰ模型开发的． 从原理上讲，ＢＳＰ模型避免了ＭａｐＲｅｄｕｃｅ模型 在多次迭代时的数据反复迁移和作业连续调度，其 特有的超步和全局同步机制，使迭代处理的控制更 加灵活，在大规模图处理方面很有开发前景．但目前 上述系统还处于研究开发阶段，所处理的数据放置 于内存，未考虑索引问题，数据处理规模也受到极大 的制约，需要进一步开发基于磁盘的系统并对Ｉ／Ｏ 操作进行优化．此外，ＢＳＰ模型中各任务之间的消 息通信也是难以消除的效率瓶颈，而在容错管理等 方面，尚无完善的理论和方法． ９５７１１０期 于　戈等：云计算环境下的大规模图数据处理技术 ４２　典型系统结构 目前，关于云计算环境下的大规模图数据管理 系统，大致可以分为３类：基于ＭａｐＲｅｄｕｃｅ模型的 分布式并行处理系统、基于ＢＳＰ模型的分布式并行 处理系统和分布式图数据库系统． 基于ＭａｐＲｅｄｕｃｅ模型的分布式并行处理系统， 大部分是通用处理平台，如Ｈａｄｏｏｐ以及改进版本 ＨＯＰ系统［４８］，可以应用于各种大规模数据处理，为 了适应需要多次迭代的图处理应用，很多研究者对 Ｈａｄｏｏｐ原有处理平台进行了优化改进，如ＨａＬｏｏｐ、 Ｔｗｉｓｔｅｒ、Ｐｒｌｔｅｒ［９，４９５０］，ＨａＬｏｏｐ使用缓存、索引技术 来减少不必要的磁盘ＩＯ，改进原有的任务调度模块 使连续作业的调度和迭代条件的控制变得较为容 易，具备一定的实用价值．Ｔｗｉｓｔｅｒ系统对Ｈａｄｏｏｐ 进行了较大的改动，全部处理数据驻留内存，采用第 ３方消息通信机制，使用任务池来避免多次作业调 度．但是驻留内存的限制使其难以实用，目前只是供 研究使用．Ｐｒｌｔｅｒ是在Ｈａｄｏｏｐ和ＨＯＰ基础上开发 的，支持带优先级的迭代计算，可以确保迭代处理的 快速收敛，尤其适合在线查询，如ｔｏｐ犽查询． 基于ＢＳＰ模型的分布式并行处理系统，最著名 的就是Ｇｏｏｇｌｅ提出的Ｐｒｅｇｅｌ平台．Ｐｒｅｇｅｌ对于图 的分割、计算处理、消息通信优化、同步控制和容错 管理都提出了可行的解决方案，是目前较为完善的 专门针对大规模图处理应用的系统［５］．Ｈａｄｏｏｐ的 开发商Ｙａｈｏｏ！提出了开源项目Ｇｉｒａｐｈ．Ｇｉｒａｐｈ可 以视为在Ｈａｄｏｏｐ平台上运行的一个大规模图算法 库，在原有ＭａｐＲｅｄｕｃｅ模型基础上，只启动ｍａｐ任 务，在ｍａｐ任务里面参考Ｐｒｅｇｅｌ的设计，嵌套了 ＢＳＰ模型，实现多次循环迭代，以支持大规模图处 理应用［４７］．开源项目Ｈａｍａ同Ｐｒｅｇｅｌ一样，也是一 个独立的分布式并行处理系统，适合需要多次迭代 的图处理．但是Ｈａｍａ目前很不完善，尚无可稳定 运行的发布版本［６］． 无论是ＭａｐＲｅｄｕｃｅ模型还是ＢＳＰ模型，上述 提及的处理平台都是分布式并行处理系统，它们的 优势是完成复杂的图处理任务，如ＰａｇｅＲａｎｋ计算、 最短路径查询、社交网络分析和图挖掘等，但是对于 图数据的一般性存储、更新维护等，则不如分布式图 数据库系统． 分布式图数据库系统集数据存储、维护、查询于 一体，继承了传统数据库的事务、一致性控制等特 点，有的甚至支持较为复杂的管理．ＨｙｐｅｒＧｒａｐｈＤＢ 是一种基于ＫｅｙＶａｌｕｅ模型的分布式Ｐ２Ｐ数据库， 采用超图作为数据模型，利用ＵＵＩＤ技术在分布式 环境下实现Ｋｅｙ编号的唯一，支持海量图数据的高 速存储；在查询方面，依靠索引的帮助支持快速图遍 历和集合查询，而基于ＳＰＡＲＱＬ语言的模式查询正 在开发中［２２］．Ｔｒｉｎｉｔｙ是微软研究院开发的基于内 存的分布式图数据库系统，该系统采用超图作为 数据模型，支持满足ＡＣＩ特性的事务机制、一致性 控制和索引，能满足高并发查询请求．Ｔｒｉｎｉｔｙ提供 良好的图分割算法，以减少查询时的网络延迟，支 持同步、异步两种模式的批处理计算［７］．其它著名 的分布式图数据库系统还有Ｎｅｏ４ｊ和Ｉｎｆｉｎｉｔｅ Ｇｒａｐｈ等［１８２９］． 此外，也有很多研究团队开发了自己独特的图 处理平台和图管理系统．如微软针对云计算环境开 发的Ｄｒｙａｄ、ＤｒｙａｄＬＩＮＱ分布式执行引擎［５１５２］，提 供完善的输入输出、任务调度、容错管理机制，支持 ＳＱＬ查询；Ｏｒｌｅａｎｓ处理平台［５３］支持异步消息通信 和索引，采用新的消息机制，避免ＲＰＣ通信的应答 阻塞，采用随机分配方法实现负载均衡，支持任务迁 移；Ｈｏｒｔｏｎ［４２］则支持对大规模图的在线查询优化． ＧＢＡＳＥ系统是一个可伸缩的通用图数据管理系 统，具有完整的图数据分块、压缩、索引和存储机制 以及一系列能够支撑复杂图挖掘应用的原语操作． ＧＢＡＳＥ底层采用邻接矩阵存储图数据，所有的图 处理操作最终都转化为Ｈａｄｏｏｐ作业执行［８］． ５　图数据处理的执行机制 本节介绍实现云计算环境下大规模图数据处理 的基本执行机制，包括消息通信、同步控制、容错管 理，并讨论可伸缩性问题．其中消息通信和同步控制 是针对图计算强耦合性进行优化处理的重要内容， 容错管理旨在解决可靠性方面的挑战，可伸缩性是 云计算灵活性的重要体现． ５１　消息通信 在图处理应用中，每一个图顶点都需要向邻居 节点发送消息或从邻居节点接收消息，而图的边，可 以理解为消息收发的通道．对于一般的图而言，边的 数目要远大于图顶点的数目．当一个图的顶点数达 到百亿级别后，边的数据规模更为巨大，如此大规模 的消息通信，如果处理不当，很容易成为整个图处理 过程的瓶颈． 图处理的消息，主要产生在图顶点的计算过程 中．但是消息发送方式，则可以根据不同的通信策略 ０６７１ 计　　算　　机　　学　　报 ２０１１年 分为异步式和集中式． 对于异步式通信，图顶点的计算处理与消息通 信并发执行，在计算过程中就可以发送消息，将大规 模消息的发送分散在不同的时间段，避免瞬时网络 通信阻塞，但是接收端需要额外空间，存储临时接收 到的消息，相当于用空间换取时间．目前，Ｐｒｅｇｅｌ、 ＨＯＰ系统等采用异步通信方式［５，４８］． 对于集中式通信，图顶点的计算处理与消息通 信串行进行，在计算完毕后，统一发送消息，控制和 实现方式简单，可在发送端对消息进行最大程度优 化，但容易造成瞬间的网络通信阻塞以及增加发送 端的消息存储开销． 鉴于大规模图数据处理过程中的网络通信瓶 颈，需要对通信次数和通信的数据量加以优化控制 以降低耦合代价．利用图分割，可以降低子图之间的 连通性，使大部分消息的目的图顶点均位于同一个 任务的处理范围中，将网络通信变为本地通信，从根 本上减少任务之间的消息发送；针对具体应用，采用 消息合并机制，也可以减少网络通信量和存储量，如 Ｐｒｅｇｅｌ［５］和Ｈａｄｏｏｐ系统［１２］；此外，通过消息缓存和 批量发送机制，可以减少网络通信的次数，降低通信 链接的维护开销．至于消息通信的实现方式， Ｈａｄｏｏｐ、Ｈａｍａ和Ｇｉｒａｐｈ等采用基于Ｈｔｔｐ协议的 ＲＰＣ通信机制［６，１２，４７］．作为Ｈａｄｏｏｐ的改进版本， Ｔｗｉｓｔｅｒ系统直接使用第３方消息通信管理插件来 完成通信控制，Ｔｗｉｓｔｅｒ系统目前支持ＮａｒａｄａＢ ｒｏｋｉｎｇ和ＡｃｔｉｖｅＭＱ等基于发布—订阅架构的通信 插件［４９］． ５２　同步控制 同步控制是所有分布式计算处理框架都必须面 对的问题，只不过有的框架显式地提供同步控制，如 采用ＢＳＰ模型的Ｐｒｅｇｅｌ系统、Ｈａｍａ系统［５６］；有的 处理框架提供隐式的同步过程，如采用ＭａｐＲｅｄｕｃｅ 模型的Ｈａｄｏｏｐ系统，在Ｍａｐ阶段和Ｒｅｄｕｃｅ阶段 存在隐式的同步控制．如果使用ＭａｐＲｅｄｕｃｅ模型进 行大规模图迭代处理，相邻作业之间也存在同步控 制的过程．在需要多次迭代的图处理应用中，同步控 制还应该提供图中间状态信息统计查询功能和收敛 条件判断功能．同步控制的优化可以减少图计算强 耦合性带来的影响． 目前，同步控制的 设计方案 关于薪酬设计方案通用技术作品设计方案停车场设计方案多媒体教室设计方案农贸市场设计方案 有两种：主从式控制 和分散式协同控制．前者由主控节点统一协调各任 务的同步，完成收敛条件判断以及中间状态信息统 计查询功能，便于集中管理，结构清晰，可维护性好， 不容易产生死锁．但是当数据量较大、任务数量很多 时，主控节点会成为处理瓶颈，多作业并发运行以及 图处理应用的多次迭代，更加剧了这种瓶颈效应．后 者的同步过程由各任务自己协调，无主控节点，避免 了单点处理瓶颈，可伸缩性很好．但是不便于集中管 理，一旦各任务开始运行，就难以在迭代过程中加以 人工控制，灵活性差． 在同步控制中，由于任务处理速度不一致，当各 任务负责处理的数据规模或数据内部的复杂程度不 同时，会导致任务处理速度相差很大，因此造成了水 桶效应．为降低水桶效应，Ｈａｄｏｏｐ系统采用“任务 推测式执行方式”［１２］，希望“纠正”执行缓慢的任务， 降低Ｍａｐ阶段和Ｒｅｄｕｃｅ阶段的水桶效应．文献 ［３０］提出动态增量Ｈａｓｈ技术来弱化Ｍａｐ阶段和 Ｒｅｄｕｃｅ阶段之间的同步，实现计算过程的部分重 叠，减少Ｒｅｄｕｃｅ任务等待时间．另外，在图处理应 用中，传统Ｈａｄｏｏｐ平台难以解决相邻作业之间的 水桶效应，ＨＯＰ系统的“ｐｉｐｅｌｉｎｅ”技术，可以在一定 程度上缓解该问题［４８］． ５３　容错管理 对于一个大规模图的处理，任务的执行时间会 很长．而云计算平台通常由普通廉价计算机构成，故 障率很高，在大规模图处理过程中，出现不可预知的 故障导致作业无法继续运行，是十分常见的现象．对 于图处理这种需要多次迭代的应用，如果每次作业 失败，都重新启动，会导致昂贵的重复处理代价，甚 至作业根本无法正常结束． 在云计算领域，当前容错管理的主流设计思想 是通过硬盘读写和冗余备份来提供保障．容错管理 需要考虑的内容主要包括：冗余备份的写入时机、冗 余备份的存放位置、故障侦测、故障恢复等．其中故 障的侦测，目前均是采用“心跳” 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 的方法完成． 针对图处理一般是多次迭代的特点，备份的写 入时机应该在两次相邻迭代之间，但这又提出了备 份生成频率的问题：迭代多少次进行一次备份是合 适的．较高的备份频率会导致作业运行速度缓慢，较 低的备份频率又会导致故障恢复时重复处理的代价 增高．目前对于这个问题，并没有定论．一种可能的 解决方案是统计特定云计算节点的故障率，根据不 同图处理作业的迭代步数来动态设定备份频率． 借鉴ＨＯＰ的容错思想［４８］，可以在一个ｍａｐ任 务的中间增加备份同时记录原始数据的处理偏移 量，当故障发生后，重启的ｍａｐ任务直接从偏移量 处开始计算．也可以在一次图处理迭代过程中，设置 １６７１１０期 于　戈等：云计算环境下的大规模图数据处理技术 中间备份并记录处理偏移量，这可以减少故障恢复 时的重复处理，提高恢复效率，但是增大了备份生成 频率和磁盘开销，也增大了容错管理的复杂度． 故障恢复时，如果各并行任务之间完全独立，则 重启故障任务即可，Ｈａｄｏｏｐ系统就采用这种恢复 策略［１２］．在图处理过程中，可以直接利用Ｈａｄｏｏｐ 系统自身的容错机制，但是由于Ｈａｄｏｏｐ的容错是 以ＭａｐＲｅｄｕｃｅ作业为单位，而一个迭代的图处理作 业一般需要多个ＭａｐＲｅｄｕｃｅ作业，多个ＭａｐＲｅｄｕｃｅ 作业间的容错管理就不是Ｈａｄｏｏｐ所能解决的了， 需要用户自己编码实现，较为繁琐．如果各并行任务 之间耦合度很高，如基于ＢＳＰ模型开发的Ｐｒｅｇｅｌ系 统，就需要使所有任务回归到同一个检查点．作为改 进，Ｐｒｅｇｅｌ提出“检查点加消息记录”的容错管理方 案［５］，将图顶点状态备份后，还需要将每个超步内各 任务间收发的消息写入磁盘．在故障发生时，仅需恢 复故障任务，不必全部回滚，减少因任务耦合度过高 导致的高昂的恢复代价，但是对消息的记录增大了 磁盘存储开销，在一定程度上也影响了作业的正常 运行效率． ５４　可伸缩性 云计算环境下的可伸缩性，应该从两个方面考 虑：硬件方面，即动态添加、删除节点来实现云平台 处理能力的伸缩性；软件方面，系统处理框架应该尽 量避免单点处理瓶颈． 从硬件方面考虑，应该允许在运行期间，动态添 加物理机器以扩充整个云计算平台的可用资源．云 计算平台可用资源的伸缩性，一方面是指新提交的 作业可以利用新添加的资源，其实现比较容易，不同 云计算系统的实现方式较为统一，都是通过注册方 式将新机器添加到可用工作节点集合；另一方面也 包括正在运行的作业可以利用新添加的资源，不同 的处理框架对其实现方式是不同的，而且对于大规 模图处理应用，更有意义．假设目前正在运行一个大 规模图处理作业，由于云平台处理资源的限制导致 运行缓慢，此时考虑动态添加一批工作节点，如果正 在运行的作业能够利用新添加的计算资源，就可以 加快处理速度． Ｈａｄｏｏｐ系统中，由于任务之间是完全独立的， 通过“任务推测式执行”技术［１２］，可以轻松利用新加 入资源．但是新启动的任务必须从头开始运行，除非 原任务所在的物理机器负载很重导致运行速度极其 缓慢，否则新启动任务的完成时间通常晚于正在运 行的任务．因而，导致这种任务的“推测式执行”，在 很多情况下是一种资源的浪费，并不适用．Ｐｒｅｇｅｌ系 统和Ｈａｍａ系统目前还不支持正在处理的作业可 以利用新添加的计算资源．由于ＢＳＰ模型以超步实 现大规模图数据的迭代处理，每个超步中，各任务耦 合度很高，所以不能像ＭａｐＲｅｄｕｃｅ模型那样，通过 “任务推测式执行”来利用新资源．对此，一种可能的 方案是“任务迁移”，通过计算任务的迁移代价，决定 是否将导致整个作业处理缓慢的任务迁移到新工作 节点上运行． 从数据存储能力方面考虑，基于ＢＳＰ模型的图 处理框架，具有较高的内存资源要求，最理想方法是 将所有的图数据都驻留在内存中，这样不需要进行 内外存交换，否则计算速度将显著下降．但这提高了 对硬件配置的要求，在一定程度上也制约了数据处 理的规模．基于ＭａｐＲｅｄｕｃｅ的图数据处理系统，只 要计算的中间结果能够存储在磁盘上，系统就可以 运行，而对节点的配置没有过高的要求． 从理论上讲，云计算环境的伸缩能力应该是没 有上限的，即加入的物理机器越多，平台中可用资源 越多，处理性能越好．但是，从实际来看，并不是这样 的．以Ｈａｄｏｏｐ为例，Ｙａｈｏｏ发现，当计算节点的规 模达到４０００台时，Ｈａｄｏｏｐ系统遭遇到伸缩性壁 垒［５４］，新加入的计算资源不能被云平台充分利用． 造成这种问题的根源，是由于目前的云计算环境主 要依赖于主从式控制模式，存在单点处理瓶颈，当整 个云平台规模过大，主控节点的处理能力成为提高 系统性能的制约瓶颈． ６　图查询处理 图数据管理的最终目的是支持查询处理，这里 的查询是指广义的查询，既包括简单的查询，如好友 关系查询，