Giraph 简介

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

前言

本文主要阐述了 Giraph 由来及其作用，并根据 Giraph 的系统架构和计算模型简要介绍了 Giraph 的运行流程。

什么是 Giraph

Giraph 是 Google 于 2010 年发布的论文 Pregel: a system for large-scale graph processing 的开源实现。Giraph 是以 Hadoop 为基础开发的上层应用，其系统架构和计算模型与 Pregel 保持了一致。同时也在 Pregel 模型上增加了一些新的特性，如：out-of-core computation、edge-oriented input 等。Giraph 的目的是为了解决大规模图的分布式计算问题。通过隐藏分布式和并行计算的细节以及提供一套用于描述图算法的 API，Giraph 不仅拥有了很好的可扩展性，还降低了分布式图计算的使用门槛。

系统架构

上图蓝色部分标识了 Giraph 的系统架构，可以看到 Giraph 实质上还是一个 Master/Slave 的架构，主要由三个部分构成：

  • Master

    Master 实质上运行在 Hadoop 的 MapTask 上， 其主要作用是对输入图进行分区、协调 Worker 的活动、维护一份存活的 Worker 列表（包括 Worker 的标识符、地址信息等）以及更新 Job 的状态。

  • Worker

    与 Master 一样，Worker 也运行在 Hadoop 的 MapTask 上，其主要作用是维护已分配图的状态。

  • Zookeeper

    在 Giraph 中 Zookeeper 的主要作用是 Master 选举、命名服务以及协调服务。图中显示的 Zookeeper 是外置状态，但实际上如果不给 Giraph 提供外置 Zookeeper，那么 Giraph 将会在 Master 所在节点上自行启动一个 Zookeeper 来提供服务。

计算模型

上图显示了 Giraph 的整个计算模型，主要由输入、一系列 Superstep 迭代计算、输出构成，其中这些 Superstep 被称之为 BSP(Bulk Synchronous Parallelism) 模型。

BSP 模型

BSP 模型是一个块同步并行模型，其由许多个 Superstep 组成。对于 BSP 模型而言，其在 Superstep 内的操作是并行的，但在两个 Superstep 之间则是由一个同步操作进行隔离的。也就是说 Superstep(N + 1) 会等待 Superstep(N) 执行完成之后才会开始。

上图显示了 Superstep 的结构图，一个 Superstep 由局部计算、通讯、栅栏同步 三个部分构成。可以看到即使有部分的计算比较快，但最终还是会在栅栏同步这里停下等待其余的计算完成。在图计算中应用这种模型的好处是：可以解决图计算的同步问题，同步模型有利于推断程序语义（即利于编程），并且消除了死锁和数据竞争的问题。

计算过程

上图展示了一个计算图中顶点最大值的过程，其中深色的顶点表示本次 Superstep 结束之后将自己标记为不活跃状态（即不再需要进行计算），当所有顶点均处于不活跃状态的时候即表明计算结束。下面针对各个 Superstep 进行分析：

  • Superstep0

    Superstep0 时所有的顶点处于活跃状态并沿出边发送其顶点值

  • Superstep1

    Superstep1 时每个顶点处理 Superstep0 发来的顶点值，第一、四个顶点[从左往右计数]发现有更大的顶点值 6，所以更新其顶点值为 6 ，并沿出边发送更新之后的顶点值。而第二、三个顶点发现并没有比它们顶点值更大的顶点值，因此两个顶点将自身标记为不活跃状态。

  • Superstep2

    Superstep2 时由于第二个顶点收到了 Superstep1 发送过来的顶点值，所以系统会将第二个顶点标记为活跃状态然后去处理接收到的顶点值，但第二个顶点依旧发现没有比它更大的顶点值，所以会再次标记自己为不活跃状态。第一、四个顶点由于没有接收到 Superstep1 发来的顶点值，所以会将其标记为不活跃状态。第三个顶点在处理 Superstep1 发来的顶点值时，发现了比它更大的顶点值 6，所以会进行更新然后沿出边发送更新之后的顶点值。

  • Superstep3

    Superstep3 阶段只有第二、四顶点接收到了 Superstep2 发来的顶点值，所以跟 Superstep2 中处理方式一致，系统先标记为这两个顶点为活跃状态，顶点比较接收的顶点值之后将自身标记为不活跃状态。至于第一、四顶点因为处于不活跃状态且没有收到上一个超步接收到的顶点值，所以不会进行处理从而依旧保持不活跃状态。至此整个计算过程就结束了。

运行流程

在了解了 Giraph 的系统架构和计算模型之后，这里简单介绍一下 Giraph 的整个运行流程：

  1. Giraph 向 Hadoop 提交 Job 之后，Zookeeper 将会选出一个 MapTask 作为 Giraph 的 Master，其余的 MapTask 则作为 Worker。然后这些 Worker 会通过 Zookeeper 命名服务找到 Master，并向 Master 进行注册。
  2. Master 将会对输入图进行分区，并发送分区信息给 Worker，Woker 会对分区进行读取，期间可能会发生 Worker 之间的分区交换。
  3. 之后 Master 会开始协调 Worker 迭代执行 Superstep，Worker 将会在 Superstep 中完成顶点的计算过程，直到所有的顶点处于不活跃状态之后结束计算。
  4. 在计算结束之后，Giraph 将会根据用户指定的格式输出结果。

总结

上述简要介绍了 Giraph 的核心知识，即架构和计算模型。但除此之外，Giraph 中还有重要的优化和容错机制尚未介绍，这些都需要后续学习的时候进行整理分析。

Thanks

  1. Pregel: a system for large-scale graph processing
  2. Pregel（图计算）技术原理
  3. BSP模型的相关讲解
  4. 从BSP模型到Apache Hama
  5. Introduction to Apache Giraph