GraphLab是一個面向大規模機器學習/圖計算的分布式內存計算框架，由CMU在2009年開始的一個C++項目，這里的內容是基于論文

Low, Yucheng, et al. "Distributed GraphLab: A Framework for Machine Learning in the Cloud" Proceedings of the VLDB Endowment 5.8 (2012)[ppt]

后續會介紹GraphLab加強版PowerGraph (v. 2.2)的內容，并介紹其在Spark平臺上的克隆GraphX。

Graph計算的背景

Graph可以刻畫的范圍是很廣的，用戶和商品之間的關系是一個典型的二部圖，pagerank的random walk也是一張圖

Graph database(Neo4j，Titan，flockdb)是用于圖數據的存儲檢索，而涉及到復雜的Graph Processing，就適合用graphlab做。

Graph計算的特點

Dependency Graph：MapReduce對于大的data并行任務（Feature Extraction/Cross Validation）是適用的，但data并行系統很難刻畫data之間的依賴關系，而這一點在機器學習（Gibbs Sampling，變分法，PageRank，CoEM，Collaborative Filtering等）中非常重要。

Local Updates：在Graph并行系統中，一個結點的值只受相鄰結點的影響，因此可以根據局部值就可以做更新。而在data并行系統中是沒有Local Updates的概念的，local信息可以加快計算，不同local之間可以做并行。

Iterative Computation：和普通Map-reduce任務不同，圖計算天然涉及到迭代計算。更新結點a的時候，對其所有鄰居(包括鄰居結點b)map，再reduce所有鄰居的結果，用得到的值來update結點a的值。然后就可以用結點a的最新值去更新他的結點b了。

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是只讀的。
此外還可以定制Full consistency(Stronger)和Vertex consistency(Weaker)這兩種一致性級別。
Distributed Consistency問題有兩種解決辦法?
1) 圖著色(算法復雜，并且可能有些顏色的patirion比較小影響效率)?
2) Distributed Locking with pipelining(高效，Latency Hiding)

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

from:　http://www.cnblogs.com/wei-li/p/GraphLab.html

總結

以上是生活随笔為你收集整理的十分钟了解分布式计算:GraphLab的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。