5.1快乐学习time

图计算

图计算简介

传统图计算算法存在的典型问题

  • 表现出比较差的内存访问局部性
  • 针对单个顶点的处理工作过少
  • 计算过程中伴随着并行度的改变

针对大型图的计算问题的解决方案和不足

  • 为特定的图应用定制相应的分布式实现;不足之处通用性不好,在面对新的图算法或者图表示方式时,需要做大量的重复开发
  • 基于现有的分布式计算平台进行图计算,比如 MapReduce 作为一个优秀的大规模数据处理框架,有时也能够用来对大规模图对象进行挖掘;在性能和易用性方面无法达到最优
  • 使用单机的图算法库,如 BGL、LEAD 等;不足之处是这种单机方式在可以解决的问题规模方面具有很大的局限性
  • 使用已有的并行图计算系统;不足之处是对大规模分布式系统非常重要的一些方面(如容错)无法提供较好的支持

图计算通用软件

  • 针对大型图的计算通用的图处理软件

    • 基于遍历算法的、实时的图数据库

      • Neo4j、OrientDB、DEX、InfiniteGraph
    • 以图顶点为中心的、基于消息传递批处理的并行引擎

      • Hama、GoldenOrb、Giraph、Pregel
      • 基于 BSP 模型实现的并行图处理系统

BSP=>Bulk Synchronous Parallel Computing Model 整体同步并行计算模型,又称桥模型

  • 一个 BSP 模型通过大量的网络相互连接的处理器构成,每个处理器都有快速的本地内存和不同的计算内存
  • 一次 BSR 计算过程包括一系列全局超步(计算中的一次迭代),每个超步主要包括三个组件

每个超步的组件

  • 局部计算

    • 每个参与的处理器都有自身的计算任务,它们只读取存储在本地内存中的值,不同处理器的计算任务都是异步且独立的
  • 通信

    • 处理器群相互交换数据,交换的形式是:由一方发起推送(Put)和获取(Get)操作
  • 栅栏同步(Barrier Synchronization)

    • 当一个处理器遇到“路障”(栅栏),会等其他所有处理器完成它们的计算步骤,每一次同步也是一个超步的完成和下一个超步的开始

后 Hadoop 时代的新“三驾马车”

Caffeine

  • 主要为谷歌网络搜索引擎提供支持,使谷歌能够更迅速地添加新的链接到自身大规模的网站索引系统中

Pregel

  • 一种可扩展的、交互式的实时查询系统,用于只读嵌套数据的分析

Pregel

  • 一种基于 BSP 模型实现的并行图处理系统

Pregel 图计算模型

有向图和顶点

  • Pregel 计算模型以有向图作为输入
  • 有向图的每个顶点都有一个 String 类型的顶点 ID
  • 每个顶点都有一个可修改的用户自定义值与之关联
  • 每条有向边都和其源顶点相关联,并记录了其目标顶点的 ID
  • 边上有一个可修改的用户自定义值与之关联

计算模式

  • 在每个超步 S 中,图中的所有顶点都会并行执行相同的用户自定义函数
  • 每个顶点可以接收前一个超步(S-1)中发给他它的消息,修改其自身及其出射边的状态,并发送小心给其他顶点,甚至是修改整个图的拓扑结构
  • 在这种计算模式中,边并不是核心对象,在边上面不会运行相应的计算,只有定点才会执行用户自定义函数进行相应计算

顶点之间的消息传递

  • 采用纯消息传递模型
  • 原因

    • 消息传递具有足够的表达能力,没有必要使用远程读取或共享内存的方式
    • 有助于提升系统整体性能

      • 大型图计算通常是由一个集群完成的,集群环境中执行远程数据读取会有较高的时间延迟;Pregel 的消息模式通常采用异步和批量的方式传递信息,因此可以缓解远程读取的延迟

计算过程

  • Pregel 的计算过程是由一系列的超步组成的
  • 在每个超步中,每个顶点上面都会并行执行用户自定的函数,该函数描述了一个顶点 V 在一个超步 S 中需要执行的操作
  • 该函可以读取前一个 超步(S-1) 中其他顶点发送给顶点 V 的消息,执行相应计算后,修改顶点 V 及其出射边的专改,然后沿着顶点 V 的出射边发送消息给其他顶点,一个消息可能经过多条变得传递后被发送到任意已知 ID 的目标顶点上
  • 这些消息将会在下一个超步 (S+1) 中被目标顶点接收,然后像上述过程一样开始下一个超步 (S+1) 的迭代过程

顶点的活跃和非活跃

  • 当图中所有的顶点已经标识自身达到“非活跃(Inactive)”状态时,算法就可以停止运行
  • 在第0个超步时,图中所有的顶点都处于“活跃(Active)”状态,这些顶点都会参与对应超步的计算过程
  • 当一个顶点不需要继续执行进一步计算时,就会调用 VoteToHalt() 把自己的状态设置为“停机”,表示自己不再是活跃顶点
  • Pregel 计算过程后续的超步中不会在非活跃定点上执行计算,除非其他顶点给该顶点发送消息再次把它激活
  • 当一个非活跃顶点再次接受来自其他顶点的消息时,Pregel 必须根据条件判断来决定是否将该节点显式唤醒进入活跃状态
  • 当所有顶点都达到非活跃且没有消息在传送时,整个计算过程就宣告结束

Pregel 的 C++ API

Vertex

  • Pregel 中一个已经预先定义好的基类
  • 在 Vetex 类中,定义了3个值类型参数

    • 顶点
    • 消息

消息传递机制

  • 顶点之间的通信时借助于消息传递机制来实现的,每条消息包含了消息值和需要到达的目标顶点 ID ,用户可以通过 Vertex 类的模板来设定消息值的数据类型

Combiner

  • 在执行大规模图计算时,一个大图会被分区成多个较小的子图,分布到多台机器上,因此消息的发送者和接收者有时并不在同一台机器上时,会产生一些开销,想要降低这些开销,就要借助 Combiner 功能
  • 通常只对满足交换律和结合律的操作才去开启 Combiner 功能,因为 Pregel 计算框架无法保证那些消息会被合并,也无法保证消息传递给 Combine()的顺序和合并操作执行的顺序

Aggregator

  • Aggregator 提供了一种全局通信、监控和数据查看的机制
  • 在一个超步 S 中,每一个顶点都可以向一个 Aggregator 提供一个数据,Pregel 计算框架会对这些值进行聚合操作产生一个值,在下一个超步 (S+1) 中,图中的所有顶点都可以看见这个值

拓扑改变

  • 在图计算中,经常需要修改拓扑的全局结构
  • Pregel 计算框架允许用户在自定义函数 Compute() 中定义操作,修改图的拓扑结构,比如在途中增加(或删除)边和顶点
  • 在同一个超步中,多个顶点的操作请求可能会存在冲突,比如两个请求都要求在途中增加同一个顶点,但是给出的初始值却不一样,Pregel 采用两种机制来解决这类冲突

    • 局部有序

      • 拓扑改变的请求是通过消息发送的,在执行一个超步时,所有的拓扑改变回在调用 Compute( ) 函数之前完成。在处理拓扑改变时,会首先执行删除操作,先删除边,后删除顶点,因为删除顶点就意味着删除了所有与之关联的出射边,然后执行增加操作,先增加顶点,后增加边,因为出射边必须与一个顶点相关联
    • Handler

      • 对于局部有序机制无法解决的那些操作冲突,就需要借助用户自定义的 Handler 来解决,包括解决由于多个顶点删除请求或多个边增加请求(或删除请求)而造成的冲突
  • 对于全局拓扑改变,Pregel 采用了惰性协调机制,在改变请求发出时,Pregel 不会对这些操作进行协调,只有当这些改变请求的消息到达目标顶点并被执行时,Pregel 才会对这些操作进行协调,这样所有针对某个顶点 V 的拓扑修改操作所引发的冲突都会由 V 自己来处理
  • 对于本地局部拓扑改变,是不会引发冲突的

Pregel 的体系结构

Pregel 的执行过程

  • 选择集群中的多台机器执行图计算任务,每台机器上运行用户程序的一个副本,其中有一台辑器会被选为 Master,其他机器作为 Worker。

    • Master 只负责协调多个 Worker 执行任务,系统不会把图的任何分区分配给它
    • Worker 借助于名称服务系统可以定位到 Master 的位置,并向 Master 发送自己的注册信息
  • Master 把一个图分成多个分区,并发粉去分配到多个 Worker,一个 Worker 会分配到一个或多个分区,每个 Worker 知道所有其他 Worker 所分配到的分区情况

    • 每个 Worker 负责维护分配给自己的那些分区的状态(顶点及边的增删),对分配给自己的分区中的顶点执行 Compute() 函数,向外发送消息,并管理接收到的消息
  • Master 会把用户输入划分成多个部分,通常是基于文件边界进行划分。划分后,每个不见坟都是一系列记录的集合,每条记录都包含一定数量的顶点和边。然后 Master 会为每个 Worker 分配用户输入的一部分。

    • 如果一个 Worker 从输入内容中加载到的顶点刚好时自己所分配到的分区中的顶点,就会立刻更新相应的数据结构;否则该 Worker 会根据加载到的顶点 ID 把它发送到其所属的分区所在的 Worker 上
    • 当所有的输入都被加载后,图中的所有顶点都会被标记为活跃状态
  • Master 向每个 Worker 发送指令,Worker 收到指令后,开始运行一个超步

    • Worker 会为自己管辖的每个分区分配一个线程,对于分区中的每个顶点,Worker 会把来自上一个超步的、发给该顶点的消息传递给它,并调用处于活跃状态的顶点上的 Compute() 函数,在执行计算过程中,顶点可以向外发送消息,但所有消息的发送工作必须在本超步结束之前完成
    • 当所有这些工作都完成后,Worker 会通知 Master,并把自己在下一个超步还处于活跃状态的顶点数量报告给 Master
    • 上述步骤会被不断重复,直到所有的顶点都不再活跃且系统中不会有任何消息在传递
  • 计算过程结束后,Master 会给所有的 Worker 发送指令,通知每个 Worker 对自己的计算结果进行持久化存储

容错性

  • Pregel 采用检查点机制来实现容错。在每个超步的开始,Master 会通知所有的 Worker 把自己管辖的分区的状态(包括顶点值、边值以及接收到的消息)写入持久化设备

Worker

  • 在一个 Worker 中,它所管辖的分区的状态信息是保存在内容中的,分区的顶点状态信息有:

    • 顶点当前的值
    • 以该顶点为起点的出射边列表,每条出射边包含了目标顶点 ID 和边的值
    • 消息队列,包含了所有接收到的、发送给该顶点的消息
    • 标志位,用来标记顶点是否处于活跃状态
  • 在每个超步中,Worker 会对自己所管辖的分区中的每个顶点进行遍历,并调用定点上的 Compute() 函数,在调用时会传入三个三个参数

    • 该顶点的当前值
    • 一个接收到的消息的迭代器
    • 一个出射边的迭代器

Master

  • Master 主要负责协调各个 Worker 执行任务,每个 Worker 会借助于名称服务系统定位到 Master 的位置,并向 Master 发送自己的注册信息,Master 会为每个 Worker 分配一个唯一 ID
  • Master 维护者关于当前处于“有效”状态的所有 Worker 的各种信息,包括每个 Worker 的 ID 和地址信息,以及每个 Worker 被分配到的分区信息,虽然在集群中只有一个 Master,但是他能承担起一个大规模图计算的协调任务,这是因为 Master 中保存这些信息的数据结构的大小只与分区的数量有关,而与顶点和边的数量无关

Aggregator

  • 每个用户自定义的 Aggregator 都会采用聚合函数对一个值得集合进行聚合计算得到一个全局值
Last modification:May 5th, 2020 at 04:05 pm
如果觉得我的文章对你有用,请随意赞赏