GraphLab 是由CMU（卡内基梅隆大学）的Select 实验室在2010 年提出的一个基于图像处理模型的开源图计算框架，框架使用C++语言开发实现。该框架是面向机器学习（ML）的流处理并行计算框架，可以运行在多处理机的单机系统、集群或是亚马逊的EC2 等多种环境下。框架的设计目标是，像MapReduce一样高度抽象，可以高效执行与机器学习相关的、具有稀疏的计算依赖特性的迭代性算法，并且保证计算过程中数据的高度一致性和高效的并行计算性能。该框架最初是为处理大规模机器学习任务而开发的，但是该框架也同样适用于许多数据挖掘方面的计算任务。在并行图计算领域，该框架在性能上高出很多其他并行计算框架（例如，MapReduce、Mahout）几个数量级。GraphLab 自成立以来就是一个发展很迅速的开源项目，其用户涉及的范围也相当广泛，全球有2 000 多个企业、机构使用GraphLab。
1. 背景
GraphLab 的设计目标是在集群或者多处理机的单机系统上实现大规模的机器学习算法。一般的机器学习类算法有以下两个特性。
● 数据依赖性很强。运算过程中参与计算的各个机器之间经常需要交换大量的数据。
● 流处理复杂。主要表现在整个处理过程需要反复地迭代计算，数据处理分支很多，很难实现真正的并行。
在GraphLab 出现之前，针对这些机器学习的算法，普遍的编程方法是采用MPI 和PThread 这些已有的底层开发库来完成这类计算问题。采用这种编程模型的开发应用，针对具体的应用，需要开发者实现相应的算法来完成计算过程中集群计算节点之间主机通信和数据同步等底层操作。这种开发方法的优势在于，可以针对具体的应用对代码进行深度的优化，以达到很高的性能。但是对于不同的应用，需要重写代码实现底层的数据分配、数据通信等细节，这就导致了代码重用率很低，可拓展性差，对编程人员要求高。这种编程模型显然不适合当前敏捷的互联网开发。而当前被广泛使用的MapReduce 计算框架，在并行执行多任务的时候，要求各个任务之间相互独立，任务执行期间不需要相互之间进行数据通信，所以MapReduce 不适合数据依赖性强的任务，而且MapReduce 并行计算模型也不能高效表达迭代型算法。这种计算模型在处理如日志分析、数据统计等数据独立性的任务时具有明显的优势，但是在机器学习领域，MapReduce 框架并不能很好地满足机器学习计算任务。
为了实现机器学习算法通用性的目标，CMU 的Select 实验室开发出了GraphLab。
GraphLab 的出现不是对MapReduce 算法的替代，相反，GraphLab 借鉴了MapReduce 的思想，将MapReduce 并行计算模型推广到了对数据重叠性、数据依赖性和迭代型算法适用的领域。本质上，GraphLab 填补了高度抽象的MapReduce 并行计算模型和底层消息传递、多线程模型（如MPI 和PThread）之间的空隙。
当前流行的并行计算框架MapReduce 将并行计算过程抽象为两个基本操作，即map 操作和reduce 操作，在map 阶段将作业分为相互独立的任务在集群上进行并行处理，在reduce 阶段将map 的输出结果进行合并得到最终的输出结果。GraphLab 模拟了MapReduce 中的抽象过程。对MapReduce 的map 操作，通过称为更新函数（Update Function）的过程进行模拟，更新函数能够读取和修改用户定义的图结构数据集。用户提供的数据图代表了程序在内存中和图的顶点、边相关联的内存状态，更新函数能够递归地触发更新操作，从而使更新操作作用在其他图节点上进行动态的迭代式计算。GraphLab 提供了强大的控制原语，以保证更新函数的执行顺序。GraphLab 对MapReduce 的reduce 操作也通过称为同步操作（Sync Operation）的过程进行模拟。同步操作能够在后台计算任务进行的过程中执行合并（Reductions），和GraphLab 提供的更新函数一样，同步操作能够同时并行处理多条记录，这也保证了同步操作能够在大规模独立环境下运行。
GraphLab 作为一个基于图处理的并行计算框架，能够高效地执行机器学习相关的数据依赖性强，迭代型算法，其设计具有如下特点和优点。
● 统一的API 接口。对于多核处理器和分布式环境，采用统一的API 接口，一次编写程序即可高效地运行在共享内存环境或者分布式集群上。
● 高性能。优化C++执行引擎，在大量多线程操作和同步I/O 操作之间进行了很好的平衡。
● 可伸缩性强。GraphLab 能够智能地选择存储和计算的节点，原因是GraphLab 对于数据的存储与计算都使用了精心设计的优良算法。
● 集成HDFS。GraphLab 内置对HDFS 的支持，GraphLab 能够直接从HDFS中读数据或者将计算结果数据直接写入到HDFS 中。
● 功能强大的机器学习类工具集。GraphLab 在自身提供的API 接口之上实现了大量的开箱即用的工具集。
GraphLab 项目包括一个用C++实现的核心开发库以及一个高性能的机器学习和数据挖掘工具集。这些工具集都建立在GraphLab API 之上，例如，计算可视化、协同过滤等，如图1所示。GraphLab 项目组正在开发新的编程接口以支持用其他编程语言和技术来开发GraphLab 应用。
GraphLab所有的API都使用C++编写，程序在内部使用TCP/IP通信。GraphLab底层使用MPI 来创建、管理GraphLab 程序。每个GraphLab 程序都被设计成多线程的，以最大化利用集群节点上多核处理器的计算资源。除此之外，GraphLab 还支持读写Posix 和HDFS 文件系统。GraphLab 已经有相关的项目用来支持使用Java、Python、Javascript 等语言开发GraphLab 应用，并且保证较高的程序执行性能。
GraphLab 将数据抽象成Graph 结构，将算法的执行过程抽象为Gather、Apply、Scatter 三个步骤（类似于MapReduce 中的map 和reduce 阶段），其并行的核心思想是对图的顶点的划分，如图2 所示。
例如，在图2 所示的例子中，需要对和V0 相邻的6 个顶点的数据进行求和计算，在传统的处理方法中，采用图2-16 左侧的处理方法，对所有和V0相邻的节点进行一次遍历，然后对结果进行累加，得到最终求和的结果。在GraphLab 处理模型中，为了达到并行处理的目的，采用的方法是对顶点V0 进行切分，如图2 右侧所示。切分后，将V0 的边关系和对应的邻点部署到两台处理机上，这样原来的一张图变成了两张子图，然后在两台处理机上分别对两张子图，然后在两台处理机上分别对两张子图并行地进行部分求和运算，得到中间结果V00 和V01，最后通过中心节点和周围顶点间的通信完成最终的计算。
在GraphLab 处理模型中，顶点是计算过程中最小的并行粒度和通信粒度。图中的边是机器学习算法中数据依赖性的表现形式。对于每个顶点，都有可能被部署到多台机器上。在GraphLab 集群上，和其他很多分布式集群相似，有一台机器作为主节点Master，其余机器作为从节点，在GraphLab 中称为Mirror节点。主节点是所有从节点的管理者，主要负责计算任务的分配和监控等，从节点作为任务的执行者，需要与主节点保持数据的同步。
对于图中的边，GraphLab 将每一条边唯一部署到集群的某个节点上，对于图中的顶点则进行多份存储，这种处理方式可以有效解决图中边的数据量过大的问题。
同一台机器上的所有边和顶点构成local graph，在每台机器上存在本地id到全局id 的映射表。顶点是一个进程上所有线程共享的，在并行计算过程中，各个线程分摊进程中所有顶点的gather→apply→scatter 操作。
2012 年CMU 发布了GraphLab2，GraphLab2 在GraphLab1 的基础上对程序并行执行的性能有了较大的提升，GraphLab2 将程序的执行过程抽象为3 个基本的操作，即G（gather）、A（apply）、S（scatter），每个顶点每一轮迭代都要按照顺序经过gather→apply→scatter 这3 个阶段。
（1）gather 阶段
工作顶点从邻接顶点收集信息，对从邻接点收集的数据被GraphLab 进行求和运算。该阶段所有的顶点和边数据都是只读的。
（2）apply 阶段
各个从节点将gather 节点计算得到的求和值发送到master 节点上，master进行汇总得到总的和，然后Master 再根据业务需求执行一系列计算，更新工作顶点的值。该阶段顶点可修改，边不可修改。
（3）scatter 阶段
工作顶点更新了自己的值后，根据需要可以更新顶点相邻的边信息，并且通知依赖该工作顶点的顶点更新自己的状态。该阶段顶点只读，边数据可写。
Apache Mahout 也是一个很成功的建立在Hadoop 集群之上的机器学习框架，GraphLab 最佳的应用场景是多核处理器环境并且待处理的问题适合使用图像模型来处理。在这种情况下，GraphLab 算法的执行速度比Mahout 快50 倍左右。但是，Mahout 对于不能一次放入内存的大数据集的处理有更好的可扩展性（受低层Hadoop 支持），而且，Mahout 在设计之初就考虑到了很强的错误容忍性，而GraphLab 却没有提供错误容忍的功能。
（1）GraphLabCli
GraphLabCli 是一个基于磁盘的大规模计算框架，是GraphLab 的一个分支。GraphLabCli 的设计特点是能够在单机上运行大规模的图形计算，从而可以让用户在单台PC或是笔记本电脑上运行大规模的基于Web 的图形分析。GraphChi借鉴 GraphLab 和 Pregel 两个项目，采用基于以顶点为中心的计算模型。GraphChi 的核心是名为 Parallel Sliding Windows（并行式滑动窗口，PSW）的模型，它能够异步处理存储在硬盘上的可变图数据。
（2）Intel GraphBuilder
GraphLab 项目组联合Intel 正在开发一个新的图形处理库，其目标是提供一套工具集帮助构造在Apache Hadoop 上运行大规模的图形计算任务。