GraphLab介绍

GraphLab 是由CMU（卡内基梅隆大学）的Select 实验室在2010 年提出的一个基于图像处理模型的开源图计算框架。框架使用C++语言开发实现。

该框架是面向机器学习（ML）的流处理并行计算框架，可以运行在多处理机的单机系统、集群或是亚马逊的EC2 等多种环境下。框架的设计目标是，像MapReduce一样高度抽象。可以高效运行与机器学习相关的、具有稀疏的计算依赖特性的迭代性算法，并且保证计算过程中数据的高度一致性和高效的并行计算性能。该框架最初是为处理大规模机器学习任务而开发的，可是该框架也相同适用于很多数据挖掘方面的计算任务。在并行图计算领域，该框架在性能上高出非常多其它并行计算框架（比如，MapReduce、Mahout）几个数量级。GraphLab 自成立以来就是一个发展非常迅速的开源项目，其用户涉及的范围也相当广泛，全球有2 000 多个企业、机构使用GraphLab。

GraphLab的优点

GraphLab 作为一个基于图处理的并行计算框架，可以高效地运行机器学习相关的数据依赖性强，迭代型算法。其设计具有例如以下特点和长处。

1. 统一的API 接口。对于多核处理器和分布式环境，採用统一的API 接口，一次编敲代码就可以高效地运行在共享内存环境或者分布式集群上。
2. 高性能。优化C++运行引擎，在大量多线程操作和同步I/O 操作之间进行了非常好的平衡。
3. 可伸缩性强。GraphLab 可以智能地选择存储和计算的节点，原因是GraphLab 对于数据的存储与计算都使用了精心设计的优良算法。
4. 集成HDFS。GraphLab 内置对HDFS 的支持。GraphLab 可以直接从HDFS中读数据或者将计算结果数据直接写入到HDFS 中。
5. 功能强大的机器学习类工具集。GraphLab 在自身提供的API 接口之上实现了大量的开箱即用的工具集。

GraphLab框架

Graph Based Data Representation：GraphLab将图切成若干子图分布式存储，其中ghost vertex是子图之间的边界点，其上存储了邻接结构以及remote数据的副本，子图之间也是有通信的，因此disk数据共享做备份很困难。

Update Functions：采用的是Asynchronously Dynamic Update，这种动态计算的主要思想是根据vertex的priority更新，每台机器上都有一个优先队列，每次迭代中如果当前vertex变化量不大的话就不再将该点的scope（一步可达的点）入队了，ghost顶点不需要入队。改进空间：可以用排队论优先。

Data consistency：需要保证Race-Free Code，如果计算overlap发生抢跑，就会产生一致性问题。GraphLab在data consistency这方面是最灵活的框架。Edge consistency的思想是one vertex apart的Update Functions才可以并行，而Overlapping regions是只读的。

Fault tolerance：GraphLab在这方面做的还不是很好，主要是Chandy-Lamport的asynchronous snapshotting algorithm。