一周一論文（翻譯）—— [PVLDB 12] Distributed GraphLab A Framework for Machine Learning

來自專欄圖計算

摘要

雖然高級別數據並行框架，像MapReduce，簡化了大規模數據處理的設計和實現的系統，他們沒有自然或有效地支持許多重要數據挖掘和機器學習演算法並且導致學習系統效率低下。為了幫助填補這一重要空白，我們介紹了GraphLab框架，它自然表達非同步的， 動態的，並行圖計算，同時在共享內存設置上確保數據一致性和實現高度的並行性能。在本文中，我們擴展GraphLab框架到更具挑戰性的分散式環境中，在保持健壯的數據一致性。

我們開發了基於圖的擴展，用線性管道鎖定和數據控制來減少網路擁塞和減弱網路延遲的影響。我們也介紹GraphLab容錯，這個容錯使用了經典的抽象Chandy-Lamport快照演算法，並展示它如何能輕易利用實現的GraphLab抽象本身。最後，我們評估我們的分散式GraphLab框架，在Amazon EC2部署和展示1 - 2個數量級在Hadoop-based實現收益的性能。

1簡介

指數增長的機器學習和數據挖掘(MLDM，即Machine Learning and Data Mining)問題和日益成熟的MLDM技術，越來越需要一個能夠在大型集群並行執行MLDM演算法的系統。同時，雲計算服務的可用性，比如Amazon EC2，提供按需獲得可以負擔的服務的承諾，這樣就沒有實質性的大規模計算和存儲資源在前期投資上。不幸的是，設計、實施和調試分散式MLDM演算法，需要充分利用雲平台，可能是非常具有挑戰性的。這些需要MLDM專家去解決競爭、死鎖、分散式狀態和通信協議等問題，同時提出複雜的數學模型和演算法。

然而，大規模計算和存儲資源的需求，推動許多人[2、14、15，27，30，35]去開發新的並行和分散式針對單個模型和應用程序的MLDM系統。這通常需要耗費大量的時間和多餘的精力，減緩了不同研究領域的進展在反覆解決相同的並行/分散式計算的問題上。因此， MLDM社區需要一個高級分散式抽象概念，非同步的，動態的，並行圖計算中發現許多MLDM應用程序而隱藏並行/分散式系統設計的複雜性。不幸的是，現有高級並行抽象(如MapReduce[8、9]，Dryad[19]和Pregel[25])不支持這些關鍵屬性。為了幫助填補這一空白，我們引入了[24] GraphLab抽象， 在共享內存設置情況下實現非同步的，動態的，並行圖計算的目標。

在本文中，我們擴展了多核GraphLab系統來適用分散式環境和提供了一個分散式的正式描述執行模型。然後，我們探索幾種方法來實現一個高效的、嚴格的滿足一致性要求的分散式執行模型。為達到這一目標，我們用數據控制來減少網路擁塞和用線性分散式鎖減輕網路延遲的影響。為解決數據本地化和入口的挑戰，我們引入了原子圖（atom），迅速把圖結構數據放到分散式環境中。我們還對GraphLab框架添加容錯通過調整經典的Chandy-Lamport[6]快照演算法和證明如何簡單在GraphLab系統實現。

我們進行一個全面的性能分析在優化的c++實現上，通過亞馬遜彈性雲計算服務(EC2)。結果表明，應用程序創建使用GraphLab可以等效Hadoop / MapReduce[9]實現和匹配的性能構造的MPI實現。我們的主要貢獻有下面幾個：:

?一個概要有關MLDM演算法的常見屬性以及現有的大型框架的局限性。(第2節) 　　

?一個修改版本有關在分散式環境中GraphLab理論和執行模型。(第3節) 　　

?兩種截然不同的方法實現分散式執行模型(第4節):

染色引擎:使用圖著色達到一致高效按順序執行的靜態表。

　鎖定引擎:使用管道線性分散式鎖和隱藏延遲，支持動態優先執行

?通過兩個快照的容錯方案。(第4.3節)

?三個先進的機器學習演算法在分散式GraphLab的高層實現。(第5節) 　　

?一個廣泛評估分散式GraphLab使用512處理器(64節點)EC2集群，包括比較Hadoop，Pregel，MPI的實現。(第5節)

2MLDM演算法性能

在本節中，我們描述了幾個關鍵有效的屬性有關大規模並行通過GraphLab解決的MLDM系統 [24]以及其他並行框架無法解決這些屬性。這些屬性和並行框架的概要在表1中可以找到。

圖的結構計算:許多在MLDM上最新進展都集中在依據數據的依賴關係建模上。通過數據依賴建模，我們能夠提取更多的信號從非結構化的數據。例如，根據依賴關係的建模，類似於購物者允許我們做出產品推薦比孤立地對待顧客要更好。不幸的是，像MapReduce一樣的數據並行[9]一般不適合通常需要更先進MLDM演算法的依賴計算。雖然它通常是可能的映射演算法與計算依賴MapReduce概念，由此產生的轉換可以挑戰和可能會引入大量的低效率。

因此，圖並行框架最近成為一個趨勢，比如Pregel[25]和GraphLab[24] ，能夠自然地表達計算依賴關係。這些框架採用以點為中心的模型，計算被定義在運行每個頂點的內核上。例如，Pregel批量同步消息傳遞抽象，通過消息傳遞進行頂點溝通。另一方面，GraphLab順序共享內存框架，每個頂點可以讀和寫在相鄰的頂點和邊的數據。GraphLab運行狀態是負責確保一致性的並行執行。因此， GraphLab通過釋放用戶集中在線性計算而不是並行移動的數據(例如，消息傳遞)，簡化了設計和實現圖並行演算法。

非同步迭代計算:許多重要MLDM演算法迭代更新大量的參數，因為潛在的圖結構，參數更新(在頂點或邊)取決於(通過圖鄰接結構) 其他參數的值。同步更新使用以前的時間步的參數值作為輸入，更新所有參數(並行)，跟同步系統對比，非同步系統使用最新更新的參數值作為輸入。因此，非同步系統為許多MLDM演算法提供了便利。例如，線性系統(常見的許多MLDM演算法)已被證明，通過非同步計算，收斂會更快解決 [4]。此外，還有很多其他的情況下(比如置信傳播[13]，期望最大化[28]，和隨機優化[35，34])，非同步的程序被經驗性的顯著表現同步過程。在圖1(a)，我們演示如何非同步的計算可以大大加快收斂網頁排名PageRank。

同步計算會導致昂貴的性能損失，因為每個階段的運行時是取決於最慢的機器。最慢的機器的表現不佳可能由多種因素引起:包括負載和網路失衡，硬體變化和多租戶(關注云服務)。即使是在典型的集群設置里，每個計算節點也可以提供其他服務(如分散式文件系統)。在利用這些服務的失衡問題將導致大量的其他服務性能損失，如果使用同步計算的話。

此外，在複雜性上的轉變和單個頂點內核的收斂在執行過程中可能產生額外的變化，即使是均勻分區圖。舉個例子，自然圖形中遇到現實世界的應用——冪律分布圖從而導致高度傾斜的運行時間，即使是隨機分區[36]。此外，實際工作所需的每個頂點可能依賴於數據特定的方式(如局部收斂速度)。

雖然框架基於批量數據處理，如MapReduce [9]和Dryad [19]，沒有被設計應用於迭代計算，最近的項目如Spark [38]擴展了MapReduce和其他數據並行框架的迭代設置。然而，這些框架仍然不支持非同步計算。模塊同步並行(BSP)框架如Pregel[25]， Piccolo [33]，BPGL[16]不自然地表達非同步性。另一方面，共享內存GraphLab框架被設計成有效自然地表達對於常見的先進的MLDM演算法的非同步迭代。

動態計算:在許多MLDM演算法，迭代計算的收斂不對稱。例如，在參數優化上，往往很快就會大量的參數在幾個迭代中收斂，而其餘的參數在許多迭代收斂中非常緩慢[11,10]。在圖1(b)，我們繪製了需要收斂的PageRank的分散式更新的描述。令人驚訝的是，大多數所需的頂點一個更新，只有約3%的頂點需要超過10次以上更新。另外，優先計算可以進一步加速收斂(Zhang et al [39])各種各樣的圖演算法包括PageRank。如果我們平等且經常更新所有參數，我們浪費大量時間在對已經有效收斂的參數的重複計算上。相反，通過早期計算在更具挑戰性的參數，我們可以加速收斂。在圖1(c)，我們實證證明動態調度在暴力的信息傳播中(一個流行MLDM演算法)如何加速收斂。

好幾個最近的框架已經可以建立動態計算的表單。例如，Pregel[25]支持有限形式動態計算，通過允許一些頂點在每個超級步上跳過計算。另一些框架比如Pearce [32]和GraphLab允許用戶自適應優化計算。雖然Pregel和GraphLab支持動態計算，只有GraphLab允許優先順序以及從相鄰的頂點拉取信息的自適應的能力 (詳細信息見3.2節)。在本文中，我們簡化一些原始GraphLab[24]中描述的調度需求，使有效的分散式FIFO和優先順序調度。

可串列性:通過確保所有並行執行的方式保證等價的順序執行，可串列性消除了許多挑戰，這些挑戰與設計、實現和測試MLDM演算法有關。此外，許多演算法收斂更快，如果能保證可串列性，有些甚至需要保證可串列的正確性。例如，動態ALS(5.1節)是不穩定的當允許競爭時(圖1(d))。Gibbs抽樣，一個流行的MLDM演算法，就需要可串列性統計的正確性。

一個執行序列化計算的框架消除了並髮帶來的複雜性，使MLDM專家集中在演算法和模型設計上。在帶有骯髒數據造成數據競爭的並發程序中調試數學代碼是困難和費時的。令人驚訝的是，許多非同步框架喜歡[32] 　　確保可串列性，或者像Piccolo[33]，只提供從數據競爭中恢復的基本機制。GraphLab支持範圍廣泛的一致性設置，允許一個程序選擇需要正確性的一致性的級別。在第4節，我們描述了幾個我們開發的在分散式配置下的可串列性技術。

3Graphlab框架的組成部分

GraphLab框架由三個主要部分組成，數據圖，更新函數和同步操作。數據圖(第3.1節)代表用戶修改的程序狀態，和提供用戶定義的可變數據和稀疏編碼的計算依賴關係（邊）。更新函數(第3.2節)代表了用戶在數據圖上的計算和操作，通過在作用域上轉換數據。最後，同步操作(第3.5節)同時維護全局變數。為了更全面的認識GraphLab框架在一個具體的問題上的應用，我們將PageRank演算法[31]作為一個運行的例子。

示例1(PAGERANK)。PageRank演算法遞歸定義網頁的排名v:

依據權重wu，v的排名 R(u) 的頁面 u 鏈接到 v作為隨機跳到這個頁面的概率。這個PageRank演算法會收斂到一個值直到收斂的改變非常小為止。

3.1數據圖

GraphLab框架存儲單向圖的程序狀態叫做數據圖。數據圖G =(V，E，D)是一個容器，用來管理我們用戶定義的數據D。我們使用術語data引用模型參數，演算法的狀態，甚至統計數據。用戶可以關聯任意數據作為在圖上的每個點和邊。然而，如果GraphLab框架不是依賴在邊的方向，我們也使用Du v表示數據在雙向邊。最後，圖數據是可變的，D的數據結構是靜態的，在執行過程中不能改變。

示例2(PAGERANK:例1)。數據圖是直接的從網上獲得的圖，每個點對應一個網頁，每個邊代表一個鏈接。頂點數據Dv存儲R(v)，當前估計的PageRank，和邊的數據Wu，v表達單向的鏈接權重。

3.2更新函數

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

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

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

GraphLab允許用戶定義更新功能，而不是採用消息傳遞或數據流模型[19，25],完全自由地來讀和寫任何相鄰的點和邊。這簡化了用戶代碼並且消除了用戶的移動數據的需求。通過控制所返回在T中的接著要執行的頂點，GraphLab更新函數可以有效地表達自適應計算。舉個例子，一個更新函數可以選擇返回(調度) 鄰接的點，只有當這些點做出了對本地數據實質性改變。

有一個重要的區別在Pregel和GraphLab之間，動態計算是如何表達的。GraphLab從數據的移動中分離了未來計算的調度。作為結果，GraphLab更新函數可以訪問數據在相鄰的頂點，即使相鄰頂點沒有調用當前的更新。相反，Pregel更新函數通過消息初始化並且只能訪問在消息中的數據，限制了所能表達的內容。例如，動態PageRank是很困難的表達在Pregel上， 計算給定頁面PageRank值需要的所有相鄰的PageRank值，即使所有相鄰的頁面最近的一些相鄰的頁面並沒有改變。因此，發送數據 (PageRank值)給相鄰的頂點的決定不能由發送頂點來做出(根據Pregel的要求)，但必須由接收頂點決定。GraphLab，自然表示了抽取模型，由於相鄰頂點只負責調度和更新函數，可以直接讀取相鄰定點的值，即使他們沒有改變頂點值。

示例3(PAGERANK:例1)。PageRank的更新函數計算了當前相鄰頂點的加權和，和分配它作為當前頂點的排名。該演算法自適應: 鄰居被調度更新只有在當前頂點的值變化超過一個預定義的閾值。

3.3GraphLab執行模型

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

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

3.4確保可串列性

GraphLab框架提供了一個豐富的序列化模型，這個模型通過允許多個處理器上對相似的圖執行相同的循環操作，可以同時刪除和操作不同的頂點的方式實現自動轉換為並行執行。為了保留順序執行的語義，我們必須確保重疊計算並不是同時運行的。我們介紹幾個一致性模型，允許運行時優化並行執行，同時保持可串列性。

GraphLab運行時確保序列化執行。一個序列化執行意味著存在一個類似的串列執行的更新函數的調度，並且更新函數在數據圖上產生相同的值。通過確保可串列性， GraphLab簡化了在分散式計算環境下有關高非同步的動態計算的演算。

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

3.5同步操作和全局值

在許多MLDM演算法中，需要保證全局統計的數據存儲在數據圖上。例如，許多統計推斷演算法要求跟蹤全局收斂性的評估值。為了解決這種需求，GraphLab框架定義了全局值，這個值通過更新函數讀，但都使用同步操作寫。類似於Pregel的聚集值，同步操作是一個關聯交換的和:

在所有的範圍定義圖。與Pregel不同的是，同步操作引入了一個終結階段， Finalize (·)，來支持任務，如標準化，在MLDM演算法中相當常見。與Pregel的聚合值在超級步後運行相比，GraphLab的同步操作能夠連續運行在保持更新的全局值的背景上。

由於每個更新函數可以訪問全局值，確保同步操作的可串列性對更新函數是費資源的，一般會需要同步和停止所有計算。正如GraphLab有多個一致性水平更新函數，我們同樣提供一致和不一致的同步計算的選擇。

4．分散式GRAPHLAB設計

在本節中，我們擴展了共享內存系統GraphLab框架的設計到更具挑戰性的分散式的環境，並且討論實現這一目標所需的技術。分散式設計的概述被展示在圖5(a)。由於固有的隨機內存訪問模仿了常見的動態非同步圖演算法，我們關注分散式內存設定，整個圖的需求和所有駐留在RAM中的程序狀態。我們的分散式實現是用c++寫的，擴展了原始開源共享內存GraphLab的實現。

4.1分散式數據圖

有效地實現分布環境的數據圖需要平衡計算、通信和存儲。因此，我們需要構建平衡數據的分區圖，保證最小化的邊的數量介於機器之間。因為雲環境可以使用不同預算和性能要求的集群，我們必須能夠迅速載入數據圖在不同大小的雲部署上。為了解決這些挑戰，我們開發了一個可以在任意的集群大小有效負載平衡的基於雙相分塊的圖表示法。

數據圖使用指定作用域的方法被初始化為覆蓋分區 (如平面嵌入)，或者通過使用一個分散式圖分區探索式(如ParMetis[21]，隨機散列)分成k個部分，這k個部分遠遠大於機器的數量。每一個部分，稱為一個原子，在分散式存儲系統中存儲作為一個單獨的文件(如HDFS，Amazon S3)。每個原子文件是一個簡單的二進位壓縮圖，包含生成加點和加邊的命令。此外，每個原子存儲關於虛擬點的信息: 與分區邊界相鄰的頂點和邊的集合。這k個原子連接的結構和文件位置存儲為一個原子索引文件中，作為與k 個頂點(對應原子)和邊通過連接原子的編碼的標籤圖。

分布載荷是通過物理機器的數量執行一個快速平衡分區的標籤圖。每台機器然後構造其本地圖，通過從每個原子的分配的記錄來回放。回放過程還實例化的在內存中的本地分區虛擬點。虛擬點在網路上被用作緩存。緩存一致性被安排使用一個簡單版本控制系統，消除了不變或常量數據的傳播(如邊的權重)。

兩級分區技術允許相同的圖分區計算可以被不同數量的機器重用，而不需要一個完整的實現步驟。兩級分區方案的質量研究超出了本文的範圍，但使用圖表的簡單實驗獲得[23]性能與直接分區。

4.2分散式GraphLab引擎

分散式GraphLab引擎模擬執行模型(定義在3.3節)，並負責執行更新功能和同步操作，維護調度頂點集T，並對適當的一致性模型確保可串列性(參見3.4節)。在3.3節，已經討論了精確的順序T中頂點到實現以及如何影響性能和表現力。為了評估權衡我們建立的低開銷染色引擎，這個引擎部分非同步地執行T集合，更富有表現力的鎖定引擎是完全非同步的，支持頂點的優先事項。

4.2.1染色引擎準備

一個來實現一個可序列化的並行執行相關的任務(圖中表示為頂點)的典型技術是構建一個頂點著色，每個頂點分配一個顏色，這樣沒有相鄰的頂點共享相同的顏色。給定一個數據圖的頂點著色情況，我們可以滿足邊一致性模型，通過執行所有在頂點集T中相同的顏色頂點進行到下一個顏色的同步操作。我們使用術語染色步，在類比的超級步 BSP模型中，描述在單獨的顏色和溝通所有的變化的情況下，更新所有的頂點的過程。同步操作就可以安全地運行染色步。

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

在染色引擎運行同步的染色步時，虛擬點和虛擬邊的改變是非同步通信。因此，染色引擎有效地在每個染色步使用網路帶寬和處理器時間。然而，我們必須確保所有的修改在改變到下一個顏色之前能夠被連接起來，因此我們需要一個在染色步之間的完整的通信界限。

4.2.2分散式鎖引擎

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

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

因為圖是分區的，我們限制每台機器只能更新本地頂點。虛擬頂點/邊更新直接訪問內存所有信息的範圍。每個工作線程在每台機器上評估中所描述的迴路（Alg.3），直到調度器是空的。終止評估使用分散式一致演算法[26]。

由於遠程鎖獲取和數據同步的延遲，在（Alg。3）樸素的實現將表現不佳。因此我們依靠幾個技術來降低延遲和隱藏它的影響[17]。首先，虛擬點系統提供緩存功能，消除了沒有改變的遠程數據傳輸或等待的需要。第二，所有的鎖請求和同步調用是線性的，允許每台機器同時請求鎖和數據，然後評估作用域已經準備好了的更新函數。

線式鎖定和預讀:每台機器維護線性的擁有鎖請求的頂點，但是沒有得到執行的。完成的鎖獲取和數據同步的頂點執行離開線性管道和工作線程。本地的調度程序確保管道總是滿足使用的。管線式鎖定引擎的迴路概述被展示在(Alg.4)。

為了實現流水線系統，常規的讀寫鎖不能被使用在將停止的爭用管道線程的數據上。因此，我們實現了一個非阻塞的通過回調操作的讀寫鎖變種。鎖請求和獲取一個回調指針，這就叫做請求被實現。這些回調指針被鏈接成一個分散式擴展傳遞理論，這個理論在機器間的鎖請求被批准。既然鎖請求依從之前的描述的順序（線性），無死鎖操作就能被保證。為了進一步減少延遲，在每台機器完成其本地鎖後，數據同步鎖應該立即執行。

例4。為了獲得一個分散式邊一致的作用域下的一個頂點v，這個頂點在機器2上，虛擬點在機器1和5上，系統首先發送一個消息到機器1，獲取機器1上的邊一致性的作用域(在v寫鎖，在鄰接點讀鎖)。一旦鎖被請求了，消息被傳遞到機器2，再次獲得本地邊一致作用域。最後，在返回主機信號完成之前，消息發送到機器5。

評估分散式管線（管道線性）系統的性能， 我們構建了一個三維網格的300×300×300 = 27，000，000個頂點。每個頂點26個連接(直接相鄰的頂點沿軸方向，以及所有對角線)， 生產超過3.75億的邊緣。圖使用Metis [21]被分成512個原子。我們表示圖作為二進位Markov隨機文件[13]和評估運行10次迭代的置信傳播[13]，從不同長度100至10000的管道，EC2集群計算實例的數量(cc1.4xlarge)4機(32個處理器)到16機(128個處理器)。我們看到在（圖3(a)）分散式鎖系統提供了強有力的、幾乎線性，可伸縮性的性能。我們在圖3(b) 通過增加的管道長度來評估管道系統的有效性。我們發現增加長度從100到1000導致運行時減少三倍。

4.3容錯

我們為GraphLab框架引入容錯分散式，使用一個分散式檢查點機制。在一個事件發生失敗後，系統從最後一個檢查點恢復過來。我們評估兩個策略去構建分散式快照:一個同步的方法——暫停所有計算當構造快照，和一個非同步方法——逐步構造快照沒有暫停執行。

同步快照通過暫停更新功能來執行，沖洗所有的溝通渠道，然後從最後次快照保存所有修改數據。變化都寫在分散式文件系統日誌文件里，可以用來在任何以前的快照上重新啟動執行。

不幸的是，同步快照暴露了GraphLab引擎一樣效率低下的同步計算 (第2節) GraphLab試圖解決的。因此我們設計了一個完全非同步的基於Chandy-Lamport[6] 替代快照。對於使用GraphLab框架，我們設計並實現了的一種Chandy-Lamport的變體，專門為GraphLab 數據圖和執行模型定製的快照。由此產生的演算法(Alg。5)表示為一個更新功能和保證一致的快照，在下列所示:

?邊緣一致性是用於所有更新功能，

?在作用域未鎖之前完成調度，

?其他更新函數比更新快照優先，

對GraphLab引擎實現最小的改變。正確性的證明遵循自然的原始證據在[6]中，機器和渠道取而代之的是頂點與邊和消息對應作用域的修改。

同步和非同步快照都在固定的間隔啟動。啟動的時間間隔必須平衡構建檢查點和從失敗的檢查點恢復的花費。Young et al. [37]派生一個一階近似最優檢查點間隔：

當T（checkpoint）是構建檢查點的時間和T（MTBF）集群的平均故障間隔時間。例如，使用一個集群的64台機器，每台機器平均1年，一個檢查點2分鐘時間導致最優檢查點間隔是3小時。因此，對於部署考慮在我們的實驗中，即使把T（MTBF）悲觀的假設，導致檢查點間隔，遠遠超過我們的實驗和事實上的運行時也超過了Hadoop實驗運行時。這引入了在Hadoop強大的容錯問題。更好的表現可以通過平衡容錯性能成本實現對工作的重新啟動。

評價: 對前一節中的相同的網片問題，我們評估快照的性能演算法，16個機器上運行(128處理器)。我們配置實現問題的一個快照第二次迭代。在圖4(a)，我們標記隨時間更新完成的數量。同步快照和非同步快照的效果可以清楚地被觀察到:同步快照停止執行，而非同步的快照只減慢執行。

當系統性能的變化加劇同步操作的成本的時候，非同步快照在多租戶的設定的好處更加明顯。我們模擬了Amazon EC2在快照開始了15秒後停止的一個過程。在圖4(b)，我們再次標記隨時間更新完成的數量後，我們觀察到非同步快照是受模擬故障的影響最小(只有3秒添加到運行時)，而同步快照經歷一個完整的運行時增加到15秒。

4.4系統設計

在圖5中(a)，我們提供GraphLab系統的高級概述。用戶首先在一個分散式文件系統(DFS)構建原子圖表示。如果使用hash分區，構造過程是Map-Reduceable過程，執行對每個頂點和邊map，每個reduce聚集一個原子文件。原子格式允許將來的改變，通過附加圖數據，而不會再操作所有數據。

圖5(b)提供了一個高水平的概述GraphLab鎖定引擎的實現。一個集群上GraphLab啟動時，每台機器上執行GraphLab程序的一個實例。GraphLab過程是同步的，並且使用一個自定義非同步基於TCP / IP的RPC協議直接溝通。第一個進程是一個額外的責任主/監控機器。

主進程在啟動時會根據原子序列計算原子的位置，所有進程執行一個被指派給他們的原子進行並行載入。每個流程負責管理分區的本地圖存儲的分散式圖，並提供分散式鎖。一個緩存用於提供對遠程圖數據的訪問。

每個進程也包含一個調度程序，管理已經分配給進程的頂點。在運行時，每台機器的當地調度器將頂點放入預取管道，收集所需的數據和頂點的鎖執行。一旦所有數據和鎖已經獲得，頂點操作由一個工作線程池完成。頂點調度被分散到每個機器，管理本地頂點的調度和轉發請求遠程頂點的調度。最後，一個分散式共識演算法[26]用於確認所有調度器是否為空。由於分散式運行時的對稱設計，沒有集中的瓶頸。

5.CONCLUSIONS AND FUTRUE WORK

最近MLDM研究的進展已經強調，在大規模MLDM問題中稀疏計算依賴性，非同步計算，動態調度和可串列化。 我們描述了最近的分散式抽象如何不能支持所有三個關鍵屬性。 為了解決這些屬性，我們引入了Distributed GraphLab，一種圖形並行分散式框架，它針對MLDM應用的這些重要屬性。分散式GraphLab通過改進執行模型，放寬調度需求以及引入新的分散式數據圖，執行引擎和容錯系統，將共享內存GraphLab抽象擴展到分散式設置。

我們設計了一個基於兩階段分區方案的分散式數據圖形格式，該格式允許在可變大小的集群部署中實現高效的負載平衡和分散式入口。我們設計了兩個GraphLab引擎：部分同步並假定存在圖著色的一個色引擎，以及完全非同步的鎖引擎，支持通用圖結構，並依賴於一種基於圖形的新型流水線鎖定系統來隱藏網路潛伏。 最後，我們引入了兩種容錯機制：基於Chandy-Lamport快照的同步快照演算法和完全非同步快照演算法，可以使用常規GraphLab基元表示。

我們使用C++實現分散式GraphLab，並使用真實數據在三種最先進的MLDM演算法上對其進行評估。評估是在Amazon EC2上使用64台HPC機器中的512個處理器執行的。 我們證明Distributed GraphLab的性能比Hadoop高出20-60倍，並且與定製的MPI實現相競爭。 我們比較了PageRank，LoopyBP和ALS的BSP（Pregel）實現，並展示了如何支持動態非同步計算可顯著提高收斂性。

未來的工作包括擴展抽象和運行時，以支持圖形資料庫中動態演化的圖形和外部存儲。這些功能將使Distributed GraphLab能夠連續存儲和處理在許多真實世界的應用程序（例如社交網路和推薦系統）中常見的時間演進數據。最後，我們認為動態非同步圖並行計算將成為大規模機器學習和數據挖掘系統的關鍵組件，因此對這些技術的理論和應用的深入研究將有助於定義新興的大學學習領域。

參考文獻

[1] R. Angles and C. Gutierrez. Survey of graph database models.ACM Comput.Surv., 40(1):1:1–1:39,2008.

[2] A. Asuncion, P. Smyth, and M. Welling. Asynchronous distributedlearning of topic models. In NIPS, pages 81–88.2008.

[3] D. Batra, A. Kowdle, D. Parikh, L. Jiebo, and C. Tsuhan.iCoseg:Interactive co-segmentation with intelligent scribble guidance. In CVPR, pages 3169 –3176, 2010.

[4] D. P. Bertsekas and J. N. Tsitsiklis. Parallel and distributed computation:numerical methods. Prentice-Hall, Inc., 1989.

[5] A. Carlson, J. Betteridge, B. Kisiel, B. Settles, E. R. H. Jr.,and T.M. Mitchell. Toward an architecture for never-ending language learning. In AAAI, 2010.

[6] K. M. Chandy and L. Lamport. Distributed snapshots:determining globalstates of distributed systems. ACM Trans.Comput. Syst., 3(1):63–75, 1985.

[7] R. Chen, X. Weng, B. He, and M. Yang. Large graph processing in thecloud. In SIGMOD, pages 1123–1126, 2010.

[8] C.-T. Chu, S. K. Kim, Y.-A. Lin, Y. Yu, G. Bradski, A. Y. Ng,and K.Olukotun. Map-reduce for machine learning on multicore. In NIPS, pages 281–288. 2006.

[9] J. Dean and S. Ghemawat. Mapreduce: simplified data processing onlarge clusters. In OSDI, 2004.

[10] B. Efron, T. Hastie, I. M. Johnstone, and R. Tibshirani. Least angleregression. Annals ofStatistics, 32(2):407–499,2004.

[11] G. Elidan, I. McGraw, and D. Koller. Residual Belief Propagation:Informed scheduling for asynchronous message passing. In UAI, pages 165–173, 2006.

[12] J. Gonzalez, Y. Low, A. Gretton, and C. Guestrin. Parallel gibbssampling: From colored fields to thin junction trees. In AISTATS, volume 15, pages 324–332, 2011.

[13] J. Gonzalez, Y. Low, and C. Guestrin. Residual splash for optimallyparallelizing belief propagation. In AISTATS,volume 5, pages 177–184, 2009.

[14] J. Gonzalez, Y. Low, C. Guestrin, and D. O』Hallaron.Distributed parallelinference on large factor graphs. In UAI,2009.

[15] H. Graf, E. Cosatto, L. Bottou, I. Dourdanovic, and V.Vapnik.Parallel support vector machines: The cascade SVM. In NIPS,pages 521–528, 2004.

[16] D. Gregor and A. Lumsdaine. The parallel BGL: A generic library fordistributed graph computations. POOSC, 2005.

[17] A. Gupta, J. Hennessy, K. Gharachorloo, T. Mowry, and W.-D.Weber.Comparative evaluation of latency reducing and tolerating techniques. SIGARCHComput. Archit. News,19(3):254–263, 1991.

[18] B. Hindman, A. Konwinski, M. Zaharia, and I. Stoica. A commonsubstrate for cluster computing. In HotCloud, 2009.

[19] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly.Dryad:distributed data-parallel programs from sequential building blocks. In EuroSys, pages 59–72, 2007.

[20] U. Kang, C. E. Tsourakakis, and C. Faloutsos. Pegasus: A peta-scalegraph mining system implementation and observations. In ICDM, pages 229 –238, 2009.

[21] G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregulargraphs. J. ParallelDistrib. Comput.,48(1):96–129, 1998.

[22] S. Lattanzi, B. Moseley, S. Suri, and S. Vassilvitskii. Filtering:amethod for solving graph problems in mapreduce. In SPAA,pages 85–94, 2011.

[23] J. Leskovec. Stanford large network datasetcollection.http://snap.stanford.edu/data/index.html, 2011.

[24] Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M.Hellerstein. Graphlab: A new parallel framework for machine learning. In UAI, pages 340–349, 2010.

[25] G. Malewicz, M. H. Austern, A. J. Bik, J. Dehnert, I. Horn, N.Leiser, and G. Czajkowski. Pregel: a system for large-scale graph http://processing.In SIGMOD, pages 135–146, 2010.

[26] J. Misra. Detecting termination of distributed computations usingmarkers. In PODC, pages 290–294, 1983.

[27] R. Nallapati, W. Cohen, and J. Lafferty. Parallelized variational EMfor latent Dirichlet allocation: An experimental evaluation of speed andscalability. In ICDM Workshops, pages 349–354, 2007.

[28] R. Neal and G. Hinton. A view of the EM algorithm that justifiesincremental, sparse, and other variants. In Learning in graphical models, pages 355–368. 1998.

[29] Neo4j. http://neo4j.org, 2011.

[30] D. Newman, A. Asuncion, P. Smyth, and M. Welling.Distributedinference for latent dirichlet allocation. In NIPS,pages 1081–1088, 2007.

[31] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citationranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab,1999.

[32] R. Pearce, M. Gokhale, and N. Amato. Multithreaded Asynchronous GraphTraversal for In-Memory and Semi-External Memory. In SC, pages 1–11, 2010.

[33] R. Power and J. Li. Piccolo: building fast, distributed programs withpartitioned tables. In OSDI, 2010.

[34] A. G. Siapas. Criticality and parallelism in combinatorial optimization. PhD thesis, Massachusetts InstituteofTechnology, 1996.

[35] A. J. Smola and S. Narayanamurthy. An Architecture for Parallel TopicModels. PVLDB, 3(1):703–710, 2010.

[36] S. Suri and S. Vassilvitskii. Counting triangles and the curse of thelast reducer. In WWW, pages 607–614,2011.

[37] J. W. Young. A first order approximation to the optimum checkpointinterval. Commun. ACM, 17:530–531, 1974.

[38] M. Zaharia, M. Chowdhury, M. Franklin, S. Shenker, and I. Stoica.Spark: cluster computing with working sets. In HotCloud, 2010.

[39] Y. Zhang, Q. Gao, L. Gao, and C. Wang. Priter: a distributed frameworkfor prioritized iterative computations. In SOCC, pages 13:1–13:14, 2011.

[40] Y. Zhou, D. Wilkinson, R. Schreiber, and R. Pan. Large-scale parallelcollaborative filtering for the netflix prize. In AAIM,pages 337–348, 2008.