第二章笔记

这里是第二章~~~

2.2图查询处理遍历模式

1.顶点为中心

  • 基本思想:遍历图顶点。
  • 实现:顶点设置激活位,判断是否应当跳过。

    2.以边为中心

  • 基本思想:扫描出边。
  • 实现步骤:1.scatter:顺序扫描出边,获取对应原顶点值及其激活标志位。2.gather:顺序扫描消息数据,更新对应的原顶点值。

    3.以子图为中心

  • 基本思想:图数据划分若干partition/block.
  • 实现步骤:同一个子图内的顶点首先进行计算,然后子图间进行消息交换。

    2.3消息通信

    集中式通信

  • 计算完毕统一发送
  • 问题:发送瞬间的通信堵塞及消息存储开销。

    异步式通信

  • 计算处理与消息发送并发执行

    消息交换模式

    以原顶点为中心
  • 基本思想:遍历原顶点,完成顶点更新,按照出边广播消息给目的顶点。
  • 缺点:储存成本。
    以目的顶点为中心
  • 基本思想:遍历目的顶点,根据入边向对应原顶点请求数据,执行更新。
  • 缺点:需要发送消息的原顶点被忽略。

2.4 同步控制

1.同步模式

  • 显式控制:BFS系统,中控节点统一协调的主从式架构。
  • 隐式控制:MapReduce系统,相邻作业顺序执行。
  • 主要弊端:水桶效应

    2.异步模式

  • 主要弊端:大量冗余消息传播

    3.混合模式

  • 基于同步模式的改进
  • 主要问题:只适合个别算法,如:最短路径查询。

    2.5容错管理

  • 正常的作业执行过程中
  • 故障恢复期间

    恢复方法

  • 硬盘读写,冗余备份:任务中间增加备份,纪录原始数据处理偏移量。
  • 作业副本:同时提交多个作业副本,一个副本完成,终止其他。