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。
- 2. GraphLab和MapReduce的區別
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 提供的更新函式一樣，同步操作能夠同時並行處理多條記錄，這也保證了同步操作能夠在大規模獨立環境下運行。
- 3. GraphLab的優點
GraphLab 作為一個基於圖處理的並行計算框架，能夠高效地執行機器學習相關的數據依賴性強，疊代型算法，其設計具有如下特點和優點。
● 統一的API 接口。對於多核處理器和分散式環境，採用統一的API 接口，一次編寫程式即可高效地運行在共享記憶體環境或者分散式集群上。
● 高性能。最佳化C++執行引擎，在大量多執行緒操作和同步I/O 操作之間進行了很好的平衡。
● 可伸縮性強。GraphLab 能夠智慧型地選擇存儲和計算的節點，原因是GraphLab 對於數據的存儲與計算都使用了精心設計的優良算法。
● 集成HDFS。GraphLab 內置對HDFS 的支持，GraphLab 能夠直接從HDFS中讀數據或者將計算結果數據直接寫入到HDFS 中。
● 功能強大的機器學習類工具集。GraphLab 在自身提供的API 接口之上實現了大量的開箱即用的工具集。
- GraphLab的軟體棧結構
GraphLab 項目包括一個用C++實現的核心開發庫以及一個高性能的機器學習和數據挖掘工具集。這些工具集都建立在GraphLab API 之上，例如，計算可視化、協同過濾等，如圖1所示。GraphLab 項目組正在開發新的編程接口以支持用其他程式語言和技術來開發GraphLab 套用。
圖1 GraphLab 的軟體棧GraphLab所有的API都使用C++編寫，程式在內部使用TCP/IP通信。GraphLab底層使用MPI 來創建、管理GraphLab 程式。每個GraphLab 程式都被設計成多執行緒的，以最大化利用集群節點上多核處理器的計算資源。除此之外，GraphLab 還支持讀寫Posix 和HDFS 檔案系統。GraphLab 已經有相關的項目用來支持使用Java、Python、Javascript 等語言開發GraphLab 套用，並且保證較高的程式執行性能。
- GraphLab並行化的基本思想
GraphLab 將數據抽象成Graph 結構，將算法的執行過程抽象為Gather、Apply、Scatter 三個步驟（類似於MapReduce 中的map 和reduce 階段），其並行的核心思想是對圖的頂點的劃分，如圖2 所示。
圖2 GraphLab 的並行思想例如，在圖2 所示的例子中，需要對和V0 相鄰的6 個頂點的數據進行求和計算，在傳統的處理方法中，採用圖2-16 左側的處理方法，對所有和V0相鄰的節點進行一次遍歷，然後對結果進行累加，得到最終求和的結果。在GraphLab 處理模型中，為了達到並行處理的目的，採用的方法是對頂點V0 進行切分，如圖2 右側所示。切分後，將V0 的邊關係和對應的鄰點部署到兩台處理機上，這樣原來的一張圖變成了兩張子圖，然後在兩台處理機上分別對兩張子圖，然後在兩台處理機上分別對兩張子圖並行地進行部分求和運算，得到中間結果V00 和V01，最後通過中心節點和周圍頂點間的通信完成最終的計算。
- 6. 數據模型
在GraphLab 處理模型中，頂點是計算過程中最小的並行粒度和通信粒度。圖中的邊是機器學習算法中數據依賴性的表現形式。對於每個頂點，都有可能被部署到多台機器上。在GraphLab 集群上，和其他很多分散式集群相似，有一台機器作為主節點Master，其餘機器作為從節點，在GraphLab 中稱為Mirror節點。主節點是所有從節點的管理者，主要負責計算任務的分配和監控等，從節點作為任務的執行者，需要與主節點保持數據的同步。
對於圖中的邊，GraphLab 將每一條邊唯一部署到集群的某個節點上，對於圖中的頂點則進行多份存儲，這種處理方式可以有效解決圖中邊的數據量過大的問題。
同一台機器上的所有邊和頂點構成local graph，在每台機器上存在本地id到全局id 的映射表。頂點是一個進程上所有執行緒共享的，在並行計算過程中，各個執行緒分攤進程中所有頂點的gather→apply→scatter 操作。
- 7. 執行模型
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 階段
工作頂點更新了自己的值後，根據需要可以更新頂點相鄰的邊信息，並且通知依賴該工作頂點的頂點更新自己的狀態。該階段頂點唯讀，邊數據可寫。
- 8. GraphLab和Mahout的區別
Apache Mahout 也是一個很成功的建立在Hadoop 集群之上的機器學習框架，GraphLab 最佳的套用場景是多核處理器環境並且待處理的問題適合使用圖像模型來處理。在這種情況下，GraphLab 算法的執行速度比Mahout 快50 倍左右。但是，Mahout 對於不能一次放入記憶體的大數據集的處理有更好的可擴展性（受低層Hadoop 支持），而且，Mahout 在設計之初就考慮到了很強的錯誤容忍性，而GraphLab 卻沒有提供錯誤容忍的功能。
- 9. 相關子項目
（1）GraphLabCli
GraphLabCli 是一個基於磁碟的大規模計算框架，是GraphLab 的一個分支。GraphLabCli 的設計特點是能夠在單機上運行大規模的圖形計算，從而可以讓用戶在單台PC或是筆記本電腦上運行大規模的基於Web 的圖形分析。GraphChi借鑑 GraphLab 和 Pregel 兩個項目，採用基於以頂點為中心的計算模型。GraphChi 的核心是名為 Parallel Sliding Windows（並行式滑動視窗，PSW）的模型，它能夠異步處理存儲在硬碟上的可變圖數據。
（2）Intel GraphBuilder
GraphLab 項目組聯合Intel 正在開發一個新的圖形處理庫，其目標是提供一套工具集幫助構造在Apache Hadoop 上運行大規模的圖形計算任務。
