Axton

计算机学报'11 云计算环境下的大规模图数据处理技术

· Axton

1.引言

图是计算机科学中最常用的一类抽象数据结构，在结构和语义方面比线性表和树更为复杂，更具一般性表示能力。

大规模图数据处理问题

以搜索引擎中常用的PageRank计算1为例，一个网页的 PageRank得分根据网页之间相互的超链接关系计算而得到。将网页用图顶点表示，网页之间的链接关系用有向边表示，按邻接表形式存储100亿个图顶 点和600亿条边，假设每个顶点及出度边的存储空间占100字节，那么整个图的存储空间将超过1TB

如此大规模的图，对其存储、更新、查找等处理的时间开销和空间开销远远超出了传统集中式图数据管理的承受能力。针对大规模图数据的高效管理，如存储、索引、更新、查找等,已经成为急需解决的问题.

采用云计算环境处理大规模图的优势

云计算是网格计算、分布式计算、并行计算、效用计算、网络存储、虚拟化等先进计算机技术和网络技术发展融合的产物，具有普遍适用性。

依靠云计算环境对大规模图数据进行高效处理，是一个非常有发展潜力的方向，主要优势表现在

  • 海量的图数据存储和维护能力
  • 强大的分布式并行处理能力
  • 良好的可伸缩性和灵活性

关键技术挑战

云环境下的大规模图处理主要面临两大挑战

  • 图计算的强耦合性
    • 在一个图中，数据之间都是相互关联的，图的计算也是相互关联的。
    • 在预处理阶段，进行合适的图分割时，尽可能地降低子图之间的耦合性；
    • 在执行阶段，应选取合适的图计算模型，避免迭代过程中反复启动任务和读写磁盘，降低任务调度开销和IO开销。
  • 云计算节点的低可靠性
    • 需要考虑有效的容错管理机制，减少大规模图处理过程中的故障恢复开销，尽量避免重复计算，提高大规模图处理的运算效率和稳定性。
  • 为了解决云计算环境下的大规模图处理问题, 可从图数据管理和图处理机制两方面加以考虑：
    • 在图数据管理上，需要解决图数据的分割、图数据的存储、图数据索引的建立、图查询处理等问题
    • 在图处理机制上，需要解决处理过程中图计算模型选取、同步控制、消息通信、容错管理和可伸缩性等问题

2.图数据模型与存储管理

图数据模型

按照图中节点的复杂程度分为简单节点图模型和复杂节点图模型2

按照一条边可以连接的顶点数目分为简单图模型和超图模型

不论是简单图模型、超图模型、简单节点模型还是复杂节点模型,它们的顶点和边都可以带有属性

  • 简单图模型
    • 简单图中,一 条边只能连接两个顶点允许存在环路
    • 简单图的存储和处理都比较容易，对于一般的应用，简单图的表达能力完全可以胜任，如PageRank计算、最短路径查询等
    • Pregel、Hama等系统均采用简单图模型来组织存储和处理大规模图数据
  • 超图模型
    • 一条边可以连接任意数目的图顶点，此模型中图的边称为超边
    • 基于这种特点，超图比上述简单图的适用性更强，保留的信息更多

图数据的存储方式

简单图和超图两种数据模型都可以处理有向图和无向图，默认情况是有向图。

简单图模型的常用存储结构包括邻接矩阵、邻接表、十字链表和邻接多重表等多种方式

从大规模图处理的应用需求和维护的复杂程度考虑，邻接矩阵和邻接表是最常用的两种结构

  • 采用邻接矩阵表示图的拓扑结构，直观简洁，便于快速查找顶点之间的关系，但是邻接矩阵的存储代价高昂，对于大规模图数据,这个问题尤为严重。
  • 邻接表的应用更加广泛，像PageRank计算、最短路径计算等应用，并不需要频繁查找两个图顶点之间的连通性，邻接表完全可以满足计算需求。邻接表的存储开销小，逻辑简单，便于分割处理，是一种比较理想的图组织方式，Pregel3、Hama4和HaLoop5等系统均采用邻接表的形式组织图数据。

超图模型的组织方式主要是关系矩阵。

云环境下的存储系统分为两种

  • 以GFS6、HDFS为代表的分布式文件系统，对于邻接矩阵和邻接表等结构，可以直接存放
  • 以BigTable7、Hbase为代表的NoSQL(Not Only SQL)分布式数据库。
    • NoSQL数据库采用的数据模型主要有
      • 文档存储模型
        • CouchDB和MongoDB采用这种存储模型
        • 不太适合以邻接矩阵或邻接表组织的图数据
      • 列式存储模型
        • BigTable、Hbase、Cassandra采用这种存储模型
      • Key Value 存储模型
        • 较为适合存储大规模图数据
        • Dynamo8和SimpleDB采用这种存储模型
      • 图存储模型
        • Neo4j采用这种模型存储图数据

图数据的索引结构

索引是传统关系数据库中的关键技术，包括B+树索引、Hash索引、位图索引等。

  • 从使用目的和实际效果的角度，索引可分为两大类
    • 一种是为支持普通查询而在云计算环境下建立索引，有助于提高数据查找效率，主要在分布式图数据库中使用
    • 另一种是为加快计算处理而建立的索引，主要在图的计算处理应用中使用，如最短路径计算、PageRank计算、聚类分析等

目前的云环境下用于数据管理的索引结构可以分为适用于P2P网络结构的索引以及适用于Shared-nothing集群结构的索引

  • Neo4j的索引分为两类
    • 数据库本身就是一个树形结构的索引，可用于提高查询效率；
    • 还可以使用独立的Lucene索引，提供全文索引和索引命中率排序功能。

3.图数据的分割策略

图分割原则

在云计算环境下，实现大图分割并取得较好的分割效果，是一项挑战性很大的工作

  • 将一个大图分割为若干子图，有两个主要原则
    • 一是提高子图内部的连通性，降低子图之间的连通性，这种特点尤其适合云计算的分布式并行处理机制。
    • 二是考虑子图规模的均衡性，尽量保证各子图的数据规模均衡，不要出现较大的偏斜，从数据规模方面防止各并行任务的执行时间相差过大，降低任务同步控制过程中“水桶效应”的影响。

单指标分割技术

如果只考虑数据负载均衡这一单项指标，最简单的图分割技术，就是Hash方式。

如果只考虑子图内敛性这一单项指标，即增大子图内部的关联性，降低子图之间的关联性，可采用聚类技术。

多指标分割技术

同时考虑子图数据规模均衡和子图内敛性等多项指标，也有很多研究。

GBASE系统9利用现有的METIS、Disco等划分算法，对存储图数据的邻接矩阵进行聚类，将行和列重新排序，把一个大矩阵聚集为多个均匀区域，形成分块，保证块内的子图联系紧密，块间联系松散，将若干个块作为一个网格，分给一个任务进行处理，在一定程度上解决了数据均衡问题。

Kernighan-Lin算法既考虑了聚类技术的特点，同时又可以保证分割后的子图在数据规模上的均衡性，主要用于网络节点的分割。

Horton系统10中提出，对于需要长期存储的图数据，采用静态处理和动态处理相结合的技术实现图分割。

4.图计算模型与典型系统结构

MapReduce模型和BSP模型

MapReduce模型11：一个并行处理作业由多个map任务和多个reduce任务组成

  • 作业的执行分为Map阶段和Reduce阶段
    • 在Map阶段，每个map任务对分配给它的数据(通常是本地的数据)进行计算，然后按照map的输出key值将结果数据映射到对应的reduce任务中；
    • 在Reduce阶段，每个reduce任务对接收到的数据做进一步聚集处理，得到输出结果。数据通常保存在分布式文件系统中，如HDFS。

BSP(Bulk Synchronous Parallel model)模型是 2010年图灵奖得主Valiant在1990年提出来的一 种基于消息通信的并行执行模型12

一个BSP作业由若干个顺序执行的超步(superstep)组成：\(S_1, S_2,...,S_n\)，对应于n次迭代处理。

并行任务按照超步组织，在超步\(S_i\)内，各任务异步接受来自\(S_{i-1}\)的消息，执行本地计算并发送消息给下一个超步\(S_{i+1}\)。在超步之间，通过显式地同步控制，确保所有任务均已完成超步\(S_i\)的工作。这种同步方式可避免死锁和数据竞争问题。

典型系统结构

关于云计算环境下的大规模图数据管理系统，大致可以分为3类

  • 基于MapReduce模型的分布式并行处理系统
    • Hadoop以及改进版本HOP系统13
    • 适应需要多次迭代的图处理应用：HaLoop、Twister14、Prlter
  • 基于BSP模型的分布式并行处理系统
    • Googel的Pregel、Yahoo!的Giraph和开源的Hama系统
  • 分布式图数据库系统
    • 分布式图数据库系统集数据存储、维护、查询于 一体,继承了传统数据库的事务、一致性控制等特 点,有的甚至支持较为复杂的管理
    • HyperGraphDB、Trinity、Neo4j、Infinite Graph
    • 图处理平台和图管理系统
      • Dryad15、DryadLINQ16分布式执行引擎
      • Orleans处理平台
      • Horton支持对大规模图的在线查询优化
      • GBASE系统是一个可伸缩的通用图数据管理系统
        • 采用邻接矩阵存储图数据

5.图数据处理的执行机制

消息通信

图处理的消息，主要产生在图顶点的计算过程中，但是消息发送方式，则可以根据不同的通信策略分为异步式和集中式。

异步式通信，图顶点的计算处理与消息通信并发执行，在计算过程中就可以发送消息，将大规模消息的发送分散在不同的时间段，避免瞬时网络通信阻塞，但是接收端需要额外空间，存储临时接收到的消息，相当于用空间换取时间。目前，Pregel、 HOP系统等采用异步通信方式

对于集中式通信，图顶点的计算处理与消息通信串行进行，在计算完毕后，统一发送消息，控制和 实现方式简单，可在发送端对消息进行最大程度优化，但容易造成瞬间的网络通信阻塞以及增加发送 端的消息存储开销。

针对具体应用，采用消息合并机制，也可以减少网络通信量和存储量，如 Pregel和Hadoop系统；此外，通过消息缓存和批量发送机制，可以减少网络通信的次数，降低通信，链接的维护开销。至于消息通信的实现方式，Hadoop、Hama和Giraph等采用基于Http协议的RPC通信机制。

同步控制

同步控制是所有分布式计算处理框架都必须面对的问题，只不过有的框架显式地提供同步控制，如采用BSP模型的Pregel系统、Hama系统；有的处理框架提供隐式的同步过程，如采用MapReduce模型的Hadoop系统，在Map阶段和Reduce阶段存在隐式的同步控制。

  • 同步控制的设计方案有两种：主从式控制和分散式协同控制
    • 前者由主控节点统一协调各任务的同步，完成收敛条件判断以及中间状态信息统计查询功能，便于集中管理，结构清晰，可维护性好，不容易产生死锁。但是当数据量较大、任务数量很多时，主控节点会成为处理瓶颈，多作业并发运行以及图处理应用的多次迭代，更加剧了这种瓶颈效应。
    • 后者的同步过程由各任务自己协调，无主控节点，避免了单点处理瓶颈，可伸缩性很好。但是不便于集中管理，一旦各任务开始运行，就难以在迭代过程中加以人工控制，灵活性差。

容错管理

在云计算领域，当前容错管理的主流设计思想是通过硬盘读写和冗余备份来提供保障，容错管理需要考虑的内容主要包括：冗余备份的写入时机、冗余备份的存放位置、故障侦测、故障恢复等，其中故 障的侦测，目前均是采用“心跳”报告的方法完成。

可伸缩性

云计算环境下的可伸缩性，应该从两个方面考虑

  • 硬件方面，即动态添加、删除节点来实现云平台 处理能力的伸缩性
  • 软件方面，系统处理框架应该尽 量避免单点处理瓶颈

6.图查询处理

查询语义的角度考虑，将大规模图查询分为两大类：

  • 一类是基本的图查询计算，如特定图顶点或边的查询、好友关系查询等；
  • 另一类是复杂查询计算与图挖掘，如RWR(Random Walk with Restart)计算、子图挖掘等。

基本的图查询计算

图的简单查询，一般不需要多次迭代，用户可以对大规模图进行查找，查询自己感兴趣的信息。查找过程中，对于某些应用，通过建立合适的索引、调整查询顺序和查询复用等技术，可以避免对整个图顶点的遍历，有效提高查找效率。

云计算环境下，对于大规模图的简单查询，在考虑分布式环境和图结构特点的同时，也应该尽量提供类似的功能。

复杂查询与图挖掘

目前比较通用的图查询处理系统，主要包括基于BSP模型的Pregel和基于Hadoop的GBASE。Pregel对于最短路径计算、PageRank计算、聚类等操作都可以支持。但是，Pregel仅支持稀疏图，且全部数据驻留内存，需要进一步的改进以支持更复杂的应用。

图查询处理的实现模式

虽然图查询处理的种类很多，但在云计算的分布式环境下，支持图查询处理的底层图遍历操作主要有两种驱动模式：

  • 一种是以图顶点驱动的主动遍历模式
  • 另一种是以消息驱动的被动遍历模式

这两种遍历模式仅是驱动不同，但是遍历操作的对象仍为图顶点，即处理操作的核心始终是图顶点。

在云计算环境下，以图顶点驱动的主动遍历计算模式，需要每个任务在计算时，主动遍历其所负责的全部图顶点，对于每一个图顶点，进行计算处理和消息收发.这种处理模式适用性强，可以支持所有的图应用场景，Hama系统就采用这种遍历模式。但是对于某些特定的应用，可能造成资源浪费。

作为改进，在以消息驱动的被动遍历模式中，各任务仅需对有消息需要处理的图顶点，进行遍历计算。这样，对于PageRank这种具有收敛性的大规模图迭代处理应用，可以有效减少不必要的顶点调用处理开销。

Pregel系统采用的遍历模式介于两者之间。

7.结束语

目前的研究重点主要集中在以下5个方面

  1. 大规模图分割

    云计算环境下的大图分割，需要提高子图内部的连通性，降低子图之间的连通性，维持子图之间数据规模和图拓扑结构的均衡性，同时应该有较小的时间复杂度。良好的图分割算法，是在云计算环境下降低图并行计算强耦合性的基础，但是目前的图分割技术，难以在连通性、均衡性和时间复杂度等方面同时达到较好的性能。

  2. 大规模图索引结构

    大规模图的数据管理，虽然依靠云计算环境的分布式并行处理机制，可以提高效率，但是索引的加入，无疑将使管理效率有一个大幅度的提升。目前关于分布式图数据的索引机制，已经有成型的产品，但是仍处在不断探索和研究过程中。而针对图处理的索引，只有部分图处理进行了云计算环境下的索引研究，如最短路径计算等，相当一部分图处理方法尚未考虑索引机制。

  3. 查询处理与磁盘存储

    在云计算环境下的大规模图查询处理，正处于开发阶段，还有很大的性能提升空间，而且像子图挖掘、图模式匹配查询等复杂应用，尚没有得到很好的解决方案。

    此外，基于BSP模型Pregel、Hama和Giraph等大规模图处理系统，目前均基于内存，限制了数据处理规模，将硬盘存储融入BSP模型并对磁盘IO进行有针对性的优化，是急需解决的问题。

  4. 消息通信优化

    在云计算环境下进行大规模图处理时，制约系统效率的重要瓶颈就是消息通信，特别是由于存在任务间的耦合性，大量的网络通信使云计算的效率大打折扣。Google、Yahoo、微软等开发机构对于网络通信的优化都进行了探索并取得了一定的效果，但目前仍只是缓解而没有从根本上解决瓶颈问题。

    对图处理应用，结合图分割技术以及图数据结构的特点，若能进一步降低网络通信开销，甚至解决瓶颈问题，会极大地提高大规模图处理效率。

  5. 容错管理

    虽然云计算系统本身拥有较为完备的容错管理机制，但是针对需要多次迭代、运行时间过长的大规模图处理而言，故障恢复的代价仍然十分昂贵。而且，冗余备份与系统处理效率之间的矛盾，没有得到明确的解决

  1. Sergey Brin, Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Comput. Networks 30(1-7): 107-117 (1998) ↩︎

  2. Rania Soussi, Marie-Aude Aufaure, Hajer Baazaoui Zghal. Graph Database for Collaborative Communities. Community-Built Databases 2011: 205-234 ↩︎

  3. Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik et al. Pregel: a system for large-scale graph processing. SIGMOD Conference 2010: 135-146 ↩︎

  4. Welcome to Hama Project. http://incubator.apache.org/hama/, 2011-7-13 ↩︎

  5. Yingyi Bu, Bill Howe, Magdalena Balazinska et al. HaLoop: Efficient Iterative Data Processing on Large Clusters. Proc. VLDB Endow. 3(1): 285-296 (2010) ↩︎

  6. Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google file system. SOSP 2003: 29-43 ↩︎

  7. Fay Chang, Jeffrey Dean, Sanjay Ghemawat et al. Bigtable: A Distributed Storage System for Structured Data (Awarded Best Paper!). OSDI 2006: 205-218 ↩︎

  8. Giuseppe DeCandia, Deniz Hastorun, Madan Jampani et al. Dynamo: amazon’s highly available key-value store. SOSP 2007: 205-220 ↩︎

  9. U Kang, Hanghang Tong, Jimeng Sun et al. GBASE: a scalable and general graph management system. KDD 2011: 1091-1099 ↩︎

  10. Mohamed Sarwat, Sameh Elnikety, Yuxiong He et al. Horton: Online Query Execution Engine for Large Distributed Graphs. ICDE 2012: 1289-1292 ↩︎

  11. Jeffrey Dean, Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Commun. ACM 51(1): 107-113 (2008) ↩︎

  12. Leslie G. Valiant. A Bridging Model for Parallel Computation. Commun. ACM 33(8): 103-111 (1990) ↩︎

  13. Tyson Condie, Neil Conway, Peter Alvaro et al. MapReduce Online. NSDI 2010: 313-328 ↩︎

  14. Jaliya Ekanayake, Hui Li, Bingjing Zhang et al. Twister: a runtime for iterative MapReduce. HPDC 2010: 810-818 ↩︎

  15. Michael Isard, Mihai Budiu, Yuan Yu et al. Dryad: distributed data-parallel programs from sequential building blocks. EuroSys 2007: 59-72 ↩︎

  16. Yuan Yu, Michael Isard, Dennis Fetterly et al. DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language. OSDI 2008: 1-14 ↩︎