GraphLab介紹
GraphLab 是由CMU（卡內基梅隆大學）的Select 實驗室在2010 年提出的一個基于圖像處理模型的開源圖計算框架芥吟，框架使用C++語言開發(fā)實現(xiàn)。該框架是面向機器學習（ML）的流處理并行計算框架专甩，可以運行在多處理機的單機系統(tǒng)钟鸵、集群或是亞馬遜的EC2 等多種環(huán)境下〉佣悖框架的設計目標是棺耍，像MapReduce一樣高度抽象，可以高效執(zhí)行與機器學習相關的种樱、具有稀疏的計算依賴特性的迭代性算法蒙袍，并且保證計算過程中數(shù)據的高度一致性和高效的并行計算性能。該框架最初是為處理大規(guī)模機器學習任務而開發(fā)的缸托，但是該框架也同樣適用于許多數(shù)據挖掘方面的計算任務左敌。在并行圖計算領域瘾蛋，該框架在性能上高出很多其他并行計算框架（例如俐镐，MapReduce、Mahout）幾個數(shù)量級哺哼。GraphLab 自成立以來就是一個發(fā)展很迅速的開源項目佩抹，其用戶涉及的范圍也相當廣泛叼风，全球有2 000 多個企業(yè)、機構使用GraphLab棍苹。
GraphLab的優(yōu)點
GraphLab 作為一個基于圖處理的并行計算框架无宿，能夠高效地執(zhí)行機器學習相關的數(shù)據依賴性強，迭代型算法枢里，其設計具有如下特點和優(yōu)點孽鸡。
- 統(tǒng)一的API 接口。對于多核處理器和分布式環(huán)境栏豺，采用統(tǒng)一的API 接口彬碱，一次編寫程序即可高效地運行在共享內存環(huán)境或者分布式集群上。
- 高性能奥洼。優(yōu)化C++執(zhí)行引擎巷疼，在大量多線程操作和同步I/O 操作之間進行了很好的平衡。
- 可伸縮性強灵奖。GraphLab 能夠智能地選擇存儲和計算的節(jié)點嚼沿，原因是GraphLab 對于數(shù)據的存儲與計算都使用了精心設計的優(yōu)良算法。
- 集成HDFS瓷患。GraphLab 內置對HDFS 的支持骡尽，GraphLab 能夠直接從HDFS中讀數(shù)據或者將計算結果數(shù)據直接寫入到HDFS 中。
- 功能強大的機器學習類工具集擅编。GraphLab 在自身提供的API 接口之上實現(xiàn)了大量的開箱即用的工具集爆阶。
GraphLab在Windows下的安裝
GraphLab現(xiàn)在還不支持Windows，暫時只能通過VMware Player運行l(wèi)inux的虛擬機沙咏，官方給出了已經配置好的GraphLab Create的VM文件辨图，可以免去編譯等步驟。下載GraphLab Create肢藐，并按照要求配置安裝
- 首先下載GraphLab Create VM文件
- 然后安裝VMware Player故河，導入GraphLab Create VM文件詳見文檔
- 最后通過ipython查看是否能正常導入graphlab庫詳見文檔
GraphLab和MapReduce的對比
一般的機器學習類算法有以下兩個特性:
- 數(shù)據依賴性很強。運算過程中參與計算的各個機器之間經常需要交換大量的數(shù)據吆豹。
- 流處理復雜鱼的。主要表現(xiàn)在整個處理過程需要反復地迭代計算，數(shù)據處理分支很多痘煤，很難實現(xiàn)真正的并行凑阶。
在GraphLab 出現(xiàn)之前，針對這些機器學習的算法衷快，普遍的編程方法是采用MPI 和PThread 這些已有的底層開發(fā)庫來完成這類計算問題宙橱。采用這種編程模型的開發(fā)應用，針對具體的應用，需要開發(fā)者實現(xiàn)相應的算法來完成計算過程中集群計算節(jié)點之間主機通信和數(shù)據同步等底層操作师郑。這種開發(fā)方法的優(yōu)勢在于环葵，可以針對具體的應用對代碼進行深度的優(yōu)化，以達到很高的性能宝冕。但是對于不同的應用张遭，需要重寫代碼實現(xiàn)底層的數(shù)據分配、數(shù)據通信等細節(jié)地梨，這就導致了代碼重用率很低菊卷，可拓展性差，對編程人員要求高宝剖。這種編程模型顯然不適合當前敏捷的互聯(lián)網開發(fā)的烁。而當前被廣泛使用的MapReduce 計算框架，在并行執(zhí)行多任務的時候诈闺，要求各個任務之間相互獨立渴庆，任務執(zhí)行期間不需要相互之間進行數(shù)據通信，所以MapReduce 不適合數(shù)據依賴性強的任務雅镊，而且MapReduce 并行計算模型也不能高效表達迭代型算法襟雷。這種計算模型在處理如日志分析、數(shù)據統(tǒng)計等數(shù)據獨立性的任務時具有明顯的優(yōu)勢仁烹，但是在機器學習領域耸弄，MapReduce框架并不能很好地滿足機器學習計算任務。
GraphLab 的出現(xiàn)不是對MapReduce 算法的替代卓缰，相反计呈，GraphLab 借鑒了MapReduce 的思想，將MapReduce 并行計算模型推廣到了對數(shù)據重疊性征唬、數(shù)據依賴性和迭代型算法適用的領域捌显。本質上，GraphLab 填補了高度抽象的MapReduce 并行計算模型和底層消息傳遞总寒、多線程模型（如MPI 和PThread）之間的空隙扶歪。
當前流行的并行計算框架MapReduce 將并行計算過程抽象為兩個基本操作，即map 操作和reduce 操作摄闸，在map 階段將作業(yè)分為相互獨立的任務在集群上進行并行處理善镰，在reduce階段將map的輸出結果進行合并得到最終的輸出結果。GraphLab 模擬了MapReduce 中的抽象過程年枕。對MapReduce的map操作炫欺，通過稱為更新函數(shù)（Update Function）的過程進行模擬，更新函數(shù)能夠讀取和修改用戶定義的圖結構數(shù)據集熏兄。用戶提供的數(shù)據圖代表了程序在內存中和圖的頂點品洛、邊相關聯(lián)的內存狀態(tài)树姨，更新函數(shù)能夠遞歸地觸發(fā)更新操作，從而使更新操作作用在其他圖節(jié)點上進行動態(tài)的迭代式計算毫别。GraphLab 提供了強大的控制原語，以保證更新函數(shù)的執(zhí)行順序典格。GraphLab對MapReduce的reduce操作也通過稱為同步操作（Sync Operation）的過程進行模擬岛宦。同步操作能夠在后臺計算任務進行的過程中執(zhí)行合并（Reductions），和GraphLab 提供的更新函數(shù)一樣耍缴，同步操作能夠同時并行處理多條記錄砾肺，這也保證了同步操作能夠在大規(guī)模獨立環(huán)境下運行。
GraphLab并行框架
GraphLab將數(shù)據抽象成Graph結構防嗡，將算法的執(zhí)行過程抽象成Gather变汪、Apply、Scatter三個步驟蚁趁。其并行的核心思想是對頂點的切分裙盾。
上圖示例中，需要完成對V0鄰接頂點的求和計算他嫡，串行實現(xiàn)中番官，V0對其所有的鄰接點進行遍歷，累加求和钢属。而GraphLab中徘熔，將頂點V0進行切分，將V0的邊關系以及對應的鄰接點部署在兩臺處理器上淆党，各臺機器上并行進行部分求和運算酷师，然后通過master頂點和mirror頂點的通信完成最終的計算。
Graph的構造
頂點是其最小并行粒度和通信粒度染乌，邊是機器學習算法中數(shù)據依賴性的表現(xiàn)方式山孔。
對于某個頂點，其被部署到多臺機器荷憋，一臺機器作為master頂點饱须，其余機器上作為mirror。Master作為所有mirror的管理者台谊，負責給mirror安排具體計算任務;mirror作為該頂點在各臺機器上的代理執(zhí)行者蓉媳，與master數(shù)據的保持同步。
對于某條邊锅铅，GraphLab將其唯一部署在某一臺機器上酪呻，而對邊關聯(lián)的頂點進行多份存儲，解了邊數(shù)據量大的問題盐须。
同一臺機器上的所有edge和vertex構成local graph,在每臺機器上玩荠，存在本地id到全局id的映射表。vertex是一個進程上所有線程共享的，在并行計算過程中阶冈，各個線程分攤進程中所有頂點的gather->apply->scatter操作闷尿。
GraphLab的執(zhí)行模型
每個頂點每一輪迭代經過gather->apple->scatter三個階段。
- Gather階段
工作頂點的邊 (可能是所有邊女坑，也有可能是入邊或者出邊)從領接頂點和自身收集數(shù)據填具，記為gather_data_i，各個邊的數(shù)據graphlab會求和匆骗，記為sum_data劳景。這一階段對工作頂點、邊都是只讀的碉就。 - Apply階段
Mirror將gather計算的結果sum_data發(fā)送給master頂點盟广，master進行匯總為total。Master利用total和上一步的頂點數(shù)據瓮钥，按照業(yè)務需求進行進一步的計算筋量，然后更新master的頂點數(shù)據，并同步mirror碉熄。Apply階段中毛甲，工作頂點可修改，邊不可修改具被。 - Scatter階段
工作頂點更新完成之后玻募，更新邊上的數(shù)據，并通知對其有依賴的鄰結頂點更新狀態(tài)一姿。這scatter過程中七咧，工作頂點只讀，邊上數(shù)據可寫叮叹。
在執(zhí)行模型中艾栋，graphlab通過控制三個階段的讀寫權限來達到互斥的目的。在gather階段只讀蛉顽，apply對頂點只寫蝗砾，scatter對邊只寫。并行計算的同步通過master和mirror來實現(xiàn)携冤，mirror相當于每個頂點對外的一個接口人悼粮，將復雜的數(shù)據通信抽象成頂點的行為。
參考資料
GraphLab:新的面向機器學習的并行框架
GraphLab百度百科
輕松搞定TB級數(shù)據曾棕，開源GraphLab突破人類圖計算“極限值”
GraphLab：將大數(shù)據分析從理念運用到生產
轉載請注明作者Jason Ding及其出處
GitCafe博客主頁(http://jasonding1354.gitcafe.io/)
Github博客主頁(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
百度搜索jasonding1354進入我的博客主頁
