GraphLab

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 上運行大規模的圖形計算任務。