[PVLDB 12] GraphLab : 分散式機器學習大規模圖處理系統 學習總結

來自專欄圖計算5 人贊了文章

今天要講的文章是PVLDB 2012年的一篇文章，Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud。本文主要解決的問題是：指數增長的機器學習和數據挖掘(MLDM，即Machine Learning and Data Mining)問題和日益成熟的MLDM技術，越來越需要一個能夠在大型集群並行執行MLDM演算法的系統。不幸的是，設計、實施和調試分散式MLDM演算法，需要充分利用雲平台，可能是非常具有挑戰性的。這些需要MLDM專家去解決競爭、死鎖、分散式狀態和通信協議等問題，同時提出複雜的數學模型和演算法。所以在當時這樣的情況下，作者提出了高級分散式抽象概念，非同步的，動態的，並行圖計算：GraphLab。

1.BackGround

在指數增長的機器學習和數據挖掘問題和日益成熟的MDLM技術的發展，我們越來越需要一個能夠在大型集群並行執行MLDM演算法的系統。那麼我們如何去設計和實現一個並行機器學習系統呢？實現一個機器學習和數據挖掘系統存在很大的挑戰。因為你需要去解決競爭、死鎖、分散式狀態和通信協議等問題，同時提出複雜的數學模型和演算法。所以要解決這個問題，就需要提出另一個高級分散式抽象系統。

現有的工作採用一種數據並行的做法，具體來說就是MapReduce計算框架，其中Map階段的計算任務是獨立的，可以獨立運行，並且可以在沒有任何交流的情況下在不同的機器上運行。然後Reduce階段通過Shuffle操作將不同的數據經過網路傳輸和磁碟溢寫，發送到Reduce Task中。在Reduce Task中進行reduce階段。但是MapReduce計算框架對於機器學習來說是不適合的，因為機器學習框架一般都是採用一種迭代計算模型。計算任務要不斷的迭代計算，直到演算法收斂為止，計算任務才停止計算。MapReduce計算框架需要將中間結果寫入到磁碟中，並且下次計算需要從磁碟中讀取數據。這種做法對於迭代任務來說需要大量的額外開銷。所以MLDM不適合用MapReduce計算框架來執行。 框架基於批量數據處理，如MapReduce [9]和Dryad [19]，沒有被設計應用於迭代計算，最近的項目如Spark [38]擴展了MapReduce和其他數據並行框架的迭代設置。然而，這些框架仍然不支持非同步計算。

為了解決實現一個機器學習和數據挖掘系統存在很大的挑戰。作者提出了一種利用Graph-Parallel 的機器學習系統。作者提出了利用Graph-Parallel Abstraction抽象。

2. Graph Compution： Synchronous VS ASynchronous

Bulk Synchronous Parallel Model: Pregel (Giraph)：同步批量模型，每個任務做完之後要等待，等待所有任務都做完之後才能進入下一輪迭代。同步不批量模型一般採用Message-Passing的方式批量發送消息來提高系統整體性能。每輪迭代到下一輪迭代之間存在很明顯的Barrier的限制。由於同步批量模型存在明顯的Barrier的限制，每輪迭代到下一輪迭代之間存在嚴重的Barrier的開銷。並且整個處理任務由最慢的任務佔主導，也就是經常說到的水桶效應。

所以同步批量模型對於機器學習來說是低效的。

ASynchronous Parallel Model：非同步執行模式就是每個頂點的計算任務互不干擾，當這輪迭代計算完成之後頂點任務可以馬上進入到下一輪迭代計算中。這種計算模式極大的提高了系統整體性能，系統的整體並行性能得到大大提高，整個圖處理模式不再受到最慢的頂點計算任務的限制。非同步執行模式可以是更加有效率的。

所以對於機器學習和數據挖掘來說，我們需要一個新的計算抽象，能夠支持非同步動態的計算抽象。所以作者就提出了分散式機器學習計算框架：GraphLab。GraphLab設計目標是專門為機器學習和數據挖掘考慮的。它利用了圖數據的依賴、支持非同步、迭代計算和動態計算特性。下面我們來介紹GraphLab的設計。

3. System Desgin

3.1 DataGraph

GraphLab框架存儲單向圖的程序狀態叫做數據圖。數據圖G =(V，E，D)是一個容器，用來管理我們用戶定義的數據D。如下圖所示：

3.2 Update Functions

計算方式被編碼在GraphLab框架的更新函數中。一個更新函數是一個無狀態的過程，這個過程修改一個頂點作用域內的數據和調度未來執行在其他頂點上的更新函數。一個頂點v的作用域(用Sv表示)是存儲在v上的數據，以及數據存儲的所有相鄰點和相鄰邊(圖2(a))。

GraphLab更新函數把一個點v和作用域Sv作為輸入，並返回作用域內數據的新版本——頂點的集合T。

在執行更新函數後，在Sv上的修改數據會被寫回到數據圖。頂點集T的每個頂點u最終更新執行為函數f(u，Su)依據執行語義描述。

4. GraphLab Execution Model

GraphLab框架的輸入包括數據圖G =(V，E，D)， 一個更新函數，一個將被執行初始頂點集合。當有頂點在T，該演算法選擇(第1行)和執行(第2行) 頂點，添加任何新的頂點回到T(第3行)。重複的頂點被忽略。最後數據圖和全局值在完成後返回給用戶。

為了更有效的分散式執行，我們降低了執行共享內存GraphLab框架的要求，並且允許GraphLab運行時確定最佳的頂點執行順序。例如，RemoveNext(T) 可以選擇返回依照最小化網路溝通或延遲的順序來執行頂點(見第4.2.2節)。GraphLab框架允許用戶指定優先順序對在T中的頂點，所以許多MLDM應用程序從優先順序受益。GraphLab運行時可能會使用這些優先順序結合系統級目標來優化頂點的執行順序。

4.1 可串列化執行

GraphLab為了防止數據競爭以及方便程序的調試、運行。GraphLab支持頂點程序的可串列化執行，也就是說防止相鄰頂點同時運行頂點程序。

一個實現可串列性的簡單方法是確保同時執行的更新函數作用域不重疊。在[24]我們稱之為完全一致性模型(見圖2(b))。然而，完全一致性同時限制了潛在的並行性，執行更新函數必須至少兩個頂點(見圖2(c))。然而，對於許多機器學習演算法，更新功能不需要完整的讀/寫訪問所有的數據作用域的許可權。例如，PageRank更新只需要讀訪問邊和相鄰的頂點的許可權。為了提供更大的並行性，同時保留可串列性，GraphLab 定義了邊一致性模型。邊一致性模型確保每個更新函數獨佔讀寫訪問頂點和相鄰的邊，但只讀訪問相鄰的點（圖2(b))。因此，邊緣一致性模型也在不斷增加並行性，通過允許更新函數使用少量重疊作用域來安全並行運行(見圖2(c))。最後，點一致性模型允許並行運行，所有更新功能提供最大的並行性。

4.2 染色引擎

為了實現可串列執行，就必須要確定一種機制，來防止相鄰頂點程序同時運行。這樣如何去調度頂點程序來防止相鄰頂點同時運行成為了一種挑戰。染色引擎就是用來解決這個問題的：每個頂點分配一個顏色，這樣沒有相鄰的頂點共享相同的顏色。給定一個數據圖的頂點著色情況，我們可以通過同步執行頂點集合T中相同顏色的所有頂點，然後繼續下一個顏色，來滿足邊緣一致性模型。

我們可以僅通過改變頂點的顏色，滿足其他一致性模型。完整的一致性模型是滿意的通過構造一個二階頂點著色(即沒有頂點分享相同的顏色在任何兩個鄰居的之間)。頂點的一致性模型是通過設定所有頂點為相同的顏色來實現的。而最優圖著色是NP難題，一個合理的高質量著色使用啟發式方法圖形著色可以快速構建(如貪心的著色)。此外，許多MLDM問題生成帶有瑣碎的顏色的圖表。例如，許多優化問題在MLDM自然表達為雙邊(two-colorable)圖表，而基於模板模型的程序可以很容易的使用模板[12]。

4.3 分散式鎖引擎

當染色引擎滿足分散式GraphLab框架（第3節），它不提供足夠的調度靈活性為許多有趣的應用程序。此外，它是以圖著色的可用性為先決條件，這可能並非總是有效的。為了克服這些限制，我們介紹擴展了用於共享內存引擎的技術的分散式互斥鎖引擎。

我們通過實現分散式互斥讀寫鎖關聯每個頂點。不同的一致性模型可以使用不同的鎖協議實現。頂點　　的一致性是通過獲取每個請求中心頂點作用域的寫鎖來完成的。邊一致性是通過在中央頂點獲取寫鎖，在相鄰的頂點獲取讀鎖。最後，完全一致性是通過獲取中央頂點和相鄰頂點的寫鎖來實現。通過依照有順序的規範秩序的方式獲取鎖而避免死鎖。我們依照頂點id的機器id來引用(所有者(v)，v)，因為這允許在一個遠程的機器的所有鎖可以被請求通過單個消息。