这里是第二章~~~
2.2图查询处理遍历模式
1.顶点为中心
- 基本思想:遍历图顶点。
- 实现:顶点设置激活位,判断是否应当跳过。
2.以边为中心
- 基本思想:扫描出边。
- 实现步骤:1.scatter:顺序扫描出边,获取对应原顶点值及其激活标志位。2.gather:顺序扫描消息数据,更新对应的原顶点值。
3.以子图为中心
- 基本思想:图数据划分若干partition/block.
- 实现步骤:同一个子图内的顶点首先进行计算,然后子图间进行消息交换。
2.3消息通信
集中式通信
- 计算完毕统一发送
- 问题:发送瞬间的通信堵塞及消息存储开销。
异步式通信
- 计算处理与消息发送并发执行
消息交换模式
以原顶点为中心
- 基本思想:遍历原顶点,完成顶点更新,按照出边广播消息给目的顶点。
- 缺点:储存成本。
以目的顶点为中心
- 基本思想:遍历目的顶点,根据入边向对应原顶点请求数据,执行更新。
- 缺点:需要发送消息的原顶点被忽略。
2.4 同步控制
1.同步模式
- 显式控制:BFS系统,中控节点统一协调的主从式架构。
- 隐式控制:MapReduce系统,相邻作业顺序执行。
- 主要弊端:水桶效应
2.异步模式
- 主要弊端:大量冗余消息传播
3.混合模式
- 基于同步模式的改进
- 主要问题:只适合个别算法,如:最短路径查询。
2.5容错管理
- 正常的作业执行过程中
- 故障恢复期间
恢复方法
- 硬盘读写,冗余备份:任务中间增加备份,纪录原始数据处理偏移量。
- 作业副本:同时提交多个作业副本,一个副本完成,终止其他。