笔记:Pregel – 基于BSP的大规模图处理系统

图计算 Quarterback 84℃ 0评论

本文主要讨论这几个问题:

  1. 大图处理面临的问题
  2. 大图处理关键技术问题
  3. 大图分布式处理计算模型和框架:MapReduce、GAS、BSP
  4. Pregel:基于BSP的大规模图处理系统
  5. Spark GraphX中的Pregel API
  6. 大图处理常见图算法

1. 大图处理面临的问题

  • 图数据强耦合性
    • 图数据之间的关联性,使得计算过程具有强耦合性,增大了并行处理过程中消息通信的开销
    • 数据访问局部性差,加剧了并行处理过程的“水桶效应”,即整个查询的完成,依赖与执行最慢的子任务完成
    • 解决方向:合理划分和组织数据,优化消息处理,适应性地调整数据分布,以提高局部性,维护负载均衡。
  • 图数据动态性
    • 新数据不断增加,以及对已有关系的更新和删除,导致图数据是动态演化的,因此面向图数据流的内存实时更新和处理框架,并不适合,而是需支持离线迭代分析任务的框架
    • 解决方向:需要探索低成本高时效的批处理更新方法,需要设计可高效增量维护的划分、存储、索引和概要等关键技术,避免重新组织数据。还需要在针对连续查询的任务时,研究增量计算方法,避免重复处理
  • 图查询处理的复杂迭代
    • 复杂的图算法在计算时通常需要多次迭代处理,即从起始顶点出发进行迭代,直到搜索到所有顶点,然后收敛到最终结果。相邻迭代之间,会产生大量中间结果,因此消息通信和磁盘操作代价会非常高昂。
    • 解决方向:一个处理任务的迭代频次通常跟图数据的规模有关,对于超大图,并行迭代处理任务往往需要很多个迭代周期才能收敛。不同的迭代任务在不同迭代周期的激活顶点数目和变化规律不同,具有明显的状态差异,考虑到不同顶点在不同阶段状态的迭代周期有着不均衡的计算和消息负载,需要有效地建模和监控迭代周期的非线性变化,有针对性地调整本地计算和数据交互的策略。因此,应该充分利用迭代过程中图的状态转换,进行查询优化。选择合适的图计算模型,避免迭代过程中反复启动任务,降低中间结果的规模。同时,需进行有效的同步控制和消息通信优化,减少通信开销,减轻“水桶效应”
  • 图计算任务的可调可控性
    • 大规模图处理,需要消耗大量时间和资源,需要大规模集群来处理,随着集群数目的增加,系统的可用性和可靠性成为关键问题,需要研究富有弹性的资源管理机制和高效的容错控制机制,以便能够在图计算处理过程中,动态调整优化集群的资源分配,使整个集群实现动态负载均衡,并降低故障探测和故障恢复开销。
    • 解决方向:设计高效的采样、概要、压缩以及提前终止迭代等近似处理方法,同时满足高精度的准确性保证

2. 大图处理关键技术问题

  • 计算方法
    • 大规模图处理,处理框架必须具备高可靠性、高灵活性、高效率和高可伸缩性的执行机制,包括消息通信、同步控制、容错管理、任务调度、扩展性保证等关键技术
  • 数据组织
    • 主要包括图数据的划分(低耦合)、图数据的存储和索引
  • 特定处理任务的优化
    • 大图计算任务主要有:最短路径查询、Pagerank、k-means聚类、SimRank等
    • 几种典型的大图复杂查询、分析和挖掘算法的优化技术:三角形查询、最大k边连通子图查询、最小生成树搜索、频繁子图挖掘、重叠社区发现
  • 系统实现技术
    • 不同的图库或图计算引擎采用了不同的计算模型,数据组织和优化技术,功能和适应性也不尽相同

3. 大图分布式处理计算模型和框架:MapReduce、GAS、BSP

  • 基于MapReduce的计算框架
    • 可以将每个MapReduce作业看成,例如单源最短路径等迭代图算法的一次迭代,而MapReduce的最终输出是一次迭代产生的中间结果,那么可以在用户提交程序中控制多个MapReduce作业串行链接起来,将每次作业的结果作为下一作业的输入数据,最终实现利用MapReduce实现图算法的目的。可以利用Hadoop的扩展性和容错能力,实现大图的迭代处理。
    • 但是Hadoop MapReduce是为处理“单趟”“易并行”应用而开发的通用数据处理平台,面对具有强耦合性的高频迭代图处理算法,存在如下缺点:
      • 1)Warm-Up开销:Hadoop采用“申请式”任务调度机制,各计算节点申请需要处理的任务,开销较大,加上作业初始化、任务初始化等预处理工作,即使是一个空负载的Hadoop作业,也需要25~30s的开销,因此高频迭代的Hadoop作业将引入巨大的Warm-Up开销。
      • 2)静态数据操作开销:所谓静态数据,即迭代过程中状态保持不变的数据,比如PageRank算法中的图拓扑结构信息,在MapReduce中,这部分数据需要反复与HDFS交互并在Shuffle阶段进行网络传输和本地存取,引入极大的数据存取开销和网络通信代价。
      • 3)数据的存储依赖于HDFS,难以设计高效的磁盘索引。
      • 4)Shuffle阶段的默认排序操作,增加了额外开销。
      • 5)编程接口差:MapReduce是通用计算框架,图迭代计算过程中的收敛性检测,图算法的表达,均需要转化为Map和Reduce函数,不易实现
    • 基于Hadoop MapReduce的改进:

      • HOP,Priter,HaLoop,Twister,Scalable Graph processing Class (SGC)
  • 基于BSP的计算框架与GAS模型
    • BSP(Bulk Synchronous Parallel),即整体同步并行模型,是一种异步的MIMD-DM多指令流多数据流-分布式内存)模型,提供块间同步处理,块内异步并行的计算
    • BSP模型的计算逻辑由一系列迭代步组成,其中每一步迭代称为一个“超步”。每个超步分为三个阶段:
      • 本地计算:应用计算逻辑的独立计算过程。计算单元在这一阶段互相独立平行计算,计算的数据在本地的内存中存储。
      • 消息通信:在本地计算阶段完成后,各个计算单元要通过消息通信交换各自的数据信息。
      • 路障同步:保证每个计算单元在下一超级步开始时,当前超级步中的处理全部结束,即块间的同步。这虽然会因各个处理单元负载及实际处理情况而导致的进度参差不齐的短板现象,但同时也避免了因异步造成的死锁问题。
    • BSP模型是目前进行分布式大图处理的主流模型,Google的Pregel就是最出名的基于BSP模型的分布式并行处理系统。基于BSP的系统,还有开源的Hama,Giraph,以及X-Pregel,Pregelix,Giraph++等
    • GAS模型
      • 从本质上,BSP框架实现的是一种由Gather, Apply和Scatter组成的GAS模型。Gather负责提取消息,Apply负责基于收集的消息进行本地处理,Scatter负责发送新的消息。BSP在每个超步内实现一次GAS的过程,之后进行路障的同步
      • 根本上看,目前大部分代表性的分布式图计算系统,包括基于MapReduce和基于BSP的系统都使用了类似GAS的处理流程,但不同的系统在消息管理,同步控制,磁盘数据组织方式等方面进行了不同角度的优化处理。
  • MPI模型不适合大图分布式处理:
    • MPI模型比较复杂和繁琐,用户需要通过编程来实现许多系统层面的细节,例如不合理的通信次序会产生死锁。
    • 另外,系统的扩展性很难保证,而且在容错性方面存在比较严重的问题

4. Pregel:基于BSP的大规模图处理系统

  • Pregel是Google提出的基于BSP的大规模图处理系统,论文发表于2010年的SIGMOD(SIGMOD、VLDB、ICDE是国际三大顶级数据库会议)。
  • Pregel名字是为了纪念欧拉,其提出的哥尼斯堡七桥问题,桥所在的河名字就叫Pregel。

5. Spark GraphX中的Pregel API

  • 图数


/* 本文属于原创文章,转载请注明作者和出处 quarterback.cn,请勿用于任何商业用途 */




喜欢 (0)or分享 (0)
Quarterback.cn 打赏作者
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址