首页 > 代码库 > 十分钟了解分布式计算:GraphLab

十分钟了解分布式计算:GraphLab

GraphLab是一个面向大规模机器学习/图计算的分布式内存计算框架,由CMU在2009年开始做,这里的内容是基于论文

Low, Yucheng, et al. "Distributed GraphLab: A Framework for Machine Learning in the Cloud" Proceedings of the VLDB Endowment 5.8 (2012)[ppt]

后续会介绍GraphLab加强版PowerGraph (v. 2.2)的内容

Graph计算的背景

NewImage

  1. Graph可以刻画的范围是很广的,用户和商品之间的关系是一个典型的二部图,pagerank的random walk也是一张图
  2. Graph database(Neo4j,Titan,flockdb)是用于图数据的存储检索,而涉及到复杂的Graph Processing,就适合用graphlab做。
Graph计算的特点

NewImage

  1. Dependency Graph:MapReduce对于大的data并行任务(Feature Extraction/Cross Validation)是适用的,但data并行系统很难刻画data之间的依赖关系,而这一点在机器学习(Gibbs Sampling,变分法,PageRank,CoEM,Collaborative Filtering等)中非常重要。NewImage
  2. Local Updates:在Graph并行系统中,一个结点的值只受相邻结点的影响,因此可以根据局部值就可以做更新。而在data并行系统中是没有Local Updates的概念的,local信息可以加快计算,不同local之间可以做并行。
  3. Iterative Computation:和普通Map-reduce任务不同,图计算天然涉及到迭代计算。更新结点a的时候,对其所有邻居(包括邻居结点b)map,再reduce所有邻居的结果,用得到的值来update结点a的值。然后就可以用结点a的最新值去更新他的结点b了。
?
GraphLab框架

NewImage

  1. Graph Based Data Representation:GraphLab将图切成若干子图分布式存储,其中ghost vertex是子图之间的边界点,其上存储了邻接结构以及remote数据的副本,子图之间也是有通信的,因此disk数据共享做备份很困难。
  2. Update Functions:采用的是Asynchronously Dynamic Update,这种动态计算的主要思想是根据vertex的priority更新,每台机器上都有一个优先队列,每次迭代中如果当前vertex变化量不大的话就不再将该点的scope(一步可达的点)入队了,ghost顶点不需要入队。改进空间:可以用排队论优化。NewImage
  3. Data consistency:需要保证Race-Free Code,如果计算overlap发生抢跑,就会产生一致性问题。GraphLab在data consistency这方面是最灵活的框架。Edge consistency的思想是one vertex apart的Update Functions才可以并行,而Overlapping regions是只读的。NewImage
    此外还可以定制Full consistency(Stronger)和Vertex consistency(Weaker)这两种一致性级别。NewImage
    Distributed Consistency问题有两种解决办法
    1) 图着色(算法复杂,并且可能有些颜色的patirion比较小影响效率)
    2) Distributed Locking with pipelining(高效,Latency Hiding)
    NewImage
  4. Fault tolerance:GraphLab在这方面做的还不是很好,主要是Chandy-Lamport的asynchronous snapshotting algorithm。NewImage