1. 区别在什么地方?

在第一节里也介绍了GraphLab也是一种分布式图计算的实现, 它是基于Bulk Synchronous Parallel Model的魔改版, 它的论文认为自己是全新的计算模型. 和BSP之间的关系类似于LRU和clock-pro这种级别的魔改.

现在的商用版本版本是Turi公司维护的.背后是卡内基梅隆的大牛们.

感觉谷歌家的论文都是藏东西的, 以前搞过一个邮件分类, 谷歌家的论文指出了正确的方向, 然后隐藏了99%的细节

GraphLab后续有PowerGraph, 以及现在的Graph Create多个魔改.
http://cacs.usc.edu/education/cs653/Low-GraphLab-VLDB12.pdf

最大的不同是这个玩意是支持异步迭代的, 前面提到了Pregel的潜在问题是每个superstep执行速度取决于最慢的那个. 而非同构集群, 图中有super star node是无法避免的, 所以Pregel虽然是个分布式计算模型, 但是不一定就快.

GraphLab支持异步superstep, 就像我们做即时终止的冒泡排序的思路, 运气好的话, 在一部分图里能直接得到答案

计算模型比较

2. GraphLab的抽象计算模型

2.1 图数据存储抽象

G = (V, E, D) 抽象为一个图
用户可以定义数据Data在vertex {Dv : v ∈ V } 或者edge {Du→v : {u, v} ∈ E}.

由于GraphLab的实现中可以不考虑方向, 所以在实际使用中, 任何边都可以看成是双向的, 实际上GraphLab可以处理无向图.

2.2 图数据计算抽象

类似pregel的compute()计算, GraphLab实现的计算时update()
Update : f(v, Sv) → (Sv, T )
Update的语义是, 给定一个vertex, 以及它的scope, 也就是和它的边和点, 用户可以更改这些边和点上的数据, 并且返回一个集合T
T中的所有点会继续执行Update操作, 直到所有update操作返回的T都为null为止.

Scope
如上图, vertext 1执行update操作的scope就是图中阴影部分, 这个update操作可以修改阴影部分的任何数据, 不管是edge的数据还是vertex的数据. 修改完后新的数据被下刷到图上, 同时返回下一步操作的集合T, T里面全部都是等待执行update的点. 重复这个操作.

执行模型
Input: Data Graph G = (V, E, D)
Input: Initial vertex set T = {v1, v2, ...}
while T is not Empty do
  v ← RemoveNext(T )
  (T′, Sv) ← f(v, Sv)
  T ← T ∪ T ′
Output: Modified Data Graph G = (V, E, D′)
由于很多机器学习的算法需要一些步骤比其它更早执行, 所以返回的T里可以带优先级

这里可以看到和Pregel一个非常大区别是每一步update操作决定了下一步哪些点继续执行update, 这样可以避免很多无用操作. 像pagerank算法中, 如果有一些非联通的孤岛子图, 在一次迭代后就可以不再参与直接输出结果了. 而在pregel的superstep模型中要一遍一遍无谓的计算.

2.3 一致性保证

了解完计算方法后, 第一个问题是如何保证并发一致性. 如果我们需要计算pagerank, 那么所有的点同时向其它关联点发送信息, 继而所有点全部进入T等待下一轮执行, 这样一个点可能同时被好多个update方法操作, 一致性如何保证呢?
下图是模型提供的锁方案, 锁的越多, 并发度越低. 左边是暗中锁的细节, 右边是并发度(灰色色块覆盖部分)

一致性
这里GraphLab提供了三种一致性模型, full consistency, edge consistency, vertex consistency. 帮助用户锁住该锁的数据, 保证数据每次都只会被一个update操作影响. 这样整个计算模型就非常类似数据库, 要求使用人员有一定的锁知识来决策应该使用哪种锁来获得最高的并发度和数据一致性.

3. GraphLab的实现

3.1 分片策略

Graph Lab有一个基本的抽象叫Atom, 每个Atom内部保存了一个尽可能联通的子图, Atom与Atom之间的边保存了子图与子图连接的数量.

基于各种算法, 整个图被抽象成了比较小的meta-graph管理起来, 这样master端把一个非常大的图抽象成了更少vertex和边的图.

atom
由于整个graph被抽象成了一个非常小的meta graph, 这样有很多算法可以fast balance, 这样后续每个worker节点保存一个atom, 在master维护atom与atom之间的关系, 保证整个分布环境的平衡.
切分
实际使用中分布式存储HDFS里每个atom文件内部是这个atom包括的所有vertex, 以及它们到另外一个atom的直接相连的部分, 这个边界部分称之为ghost.
如上图中的Atom 1里保存了Vertex2和Vertex7两个ghost, 它不需要保存Vertex5, 因为其和Atom1的任何一个vertex都没有边连接.

3.2 计算策略

• Chromatic Engine 负责update的执行部分
• Distributed Locking Engine 并发执行的顺序问题, 也就是上面提到的一致性问题

Chromatic Engine 这里GraphLab使用了经典的图着色策略, 首先给整张图所有的vertex着色, 然后每次都在一种颜色上并发执行update()操作. 相对于superstep, 这种执行策略叫colorstep

虽然没有严格的数学证明, 但在 greedy color着色策略下, 4种颜色可以让图中任何相连的vertex都是异色的. 这样就实现了edge lock!

Note: 如果greedy color下运行graph lab抛出concurrent modify exception, 请立即保存整个图. 因为如果这不是一个bug, 那么恭喜你, 你发现了地图4色的反例, 足以名垂数学史, 并且让一堆在读博士毕不了业!

3.3 分布式锁策略

Pipeline lock

3.4 Fault Tolerance 策略

相对于Pregel挂掉了只能大家一起调回checkpoint重算的策略.

GraphLab使用了经典的Chandy-Lamport来对分布式计算过程做snapshot.

论文: http://lamport.azurewebsites.net/pubs/chandy.pdf

在这个策略下, snapshot被看成是一种特殊的update操作. 可以想象一个被四色 (RED BLUE GREEN BLCAK)标记的地图里.我们从某个颜色开始, 立即开始一轮update, 从而保存了一个全局RED的snapshot.

这样我们获得了一个快照链接 RED->BLUE->GREEN->BLCAK->RED2.0->....

任何一个环节的atom挂掉了, 我都可以恢复到上一个颜色的状态