????????今天要講的文章是PVLDB 2012年的一篇文章，Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud。本文主要解決的問題是：指數(shù)增長(zhǎng)的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘(MLDM，即Machine Learning and Data Mining)問題和日益成熟的MLDM技術(shù)，越來越需要一個(gè)能夠在大型集群并行執(zhí)行MLDM算法的系統(tǒng)。不幸的是，設(shè)計(jì)、實(shí)施和調(diào)試分布式MLDM算法，需要充分利用云平臺(tái)，可能是非常具有挑戰(zhàn)性的。這些需要MLDM專家去解決競(jìng)爭(zhēng)、死鎖、分布式狀態(tài)和通信協(xié)議等問題，同時(shí)提出復(fù)雜的數(shù)學(xué)模型和算法。所以在當(dāng)時(shí)這樣的情況下，作者提出了高級(jí)分布式抽象概念，異步的，動(dòng)態(tài)的，并行圖計(jì)算：GraphLab。

1.BackGround

????? ? 在指數(shù)增長(zhǎng)的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘問題和日益成熟的MDLM技術(shù)的發(fā)展，我們?cè)絹碓叫枰粋€(gè)能夠在大型集群并行執(zhí)行MLDM算法的系統(tǒng)。那么我們?nèi)绾稳ピO(shè)計(jì)和實(shí)現(xiàn)一個(gè)并行機(jī)器學(xué)習(xí)系統(tǒng)呢？實(shí)現(xiàn)一個(gè)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘系統(tǒng)存在很大的挑戰(zhàn)。因?yàn)槟阈枰?span style="background-color:rgb(255,255,255);">去解決競(jìng)爭(zhēng)、死鎖、分布式狀態(tài)和通信協(xié)議等問題，同時(shí)提出復(fù)雜的數(shù)學(xué)模型和算法。所以要解決這個(gè)問題，就需要提出另一個(gè)高級(jí)分布式抽象系統(tǒng)。

????? ? 現(xiàn)有的工作采用一種數(shù)據(jù)并行的做法，具體來說就是MapReduce計(jì)算框架，其中Map階段的計(jì)算任務(wù)是獨(dú)立的，可以獨(dú)立運(yùn)行，并且可以在沒有任何交流的情況下在不同的機(jī)器上運(yùn)行。然后Reduce階段通過Shuffle操作將不同的數(shù)據(jù)經(jīng)過網(wǎng)絡(luò)傳輸和磁盤溢寫，發(fā)送到Reduce Task中。在Reduce Task中進(jìn)行reduce階段。但是MapReduce計(jì)算框架對(duì)于機(jī)器學(xué)習(xí)來說是不適合的，因?yàn)闄C(jī)器學(xué)習(xí)框架一般都是采用一種迭代計(jì)算模型。計(jì)算任務(wù)要不斷的迭代計(jì)算，直到算法收斂為止，計(jì)算任務(wù)才停止計(jì)算。MapReduce計(jì)算框架需要將中間結(jié)果寫入到磁盤中，并且下次計(jì)算需要從磁盤中讀取數(shù)據(jù)。這種做法對(duì)于迭代任務(wù)來說需要大量的額外開銷。所以MLDM不適合用MapReduce計(jì)算框架來執(zhí)行。?框架基于批量數(shù)據(jù)處理，如MapReduce [9]和Dryad [19]，沒有被設(shè)計(jì)應(yīng)用于迭代計(jì)算，最近的項(xiàng)目如Spark [38]擴(kuò)展了MapReduce和其他數(shù)據(jù)并行框架的迭代設(shè)置。然而，這些框架仍然不支持異步計(jì)算。

????? ? 為了解決實(shí)現(xiàn)一個(gè)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘系統(tǒng)存在很大的挑戰(zhàn)。作者提出了一種利用Graph-Parallel 的機(jī)器學(xué)習(xí)系統(tǒng)。作者提出了利用Graph-Parallel Abstraction抽象。

2. Graph Compution： Synchronous VS ASynchronous

????? ??Bulk Synchronous Parallel Model: Pregel (Giraph)：同步批量模型，每個(gè)任務(wù)做完之后要等待，等待所有任務(wù)都做完之后才能進(jìn)入下一輪迭代。同步不批量模型一般采用Message-Passing的方式批量發(fā)送消息來提高系統(tǒng)整體性能。每輪迭代到下一輪迭代之間存在很明顯的Barrier的限制。由于同步批量模型存在明顯的Barrier的限制，每輪迭代到下一輪迭代之間存在嚴(yán)重的Barrier的開銷。并且整個(gè)處理任務(wù)由最慢的任務(wù)占主導(dǎo)，也就是經(jīng)常說到的水桶效應(yīng)。

????? ? 所以同步批量模型對(duì)于機(jī)器學(xué)習(xí)來說是低效的。

????????ASynchronous Parallel Model：異步執(zhí)行模式就是每個(gè)頂點(diǎn)的計(jì)算任務(wù)互不干擾，當(dāng)這輪迭代計(jì)算完成之后頂點(diǎn)任務(wù)可以馬上進(jìn)入到下一輪迭代計(jì)算中。這種計(jì)算模式極大的提高了系統(tǒng)整體性能，系統(tǒng)的整體并行性能得到大大提高，整個(gè)圖處理模式不再受到最慢的頂點(diǎn)計(jì)算任務(wù)的限制。異步執(zhí)行模式可以是更加有效率的。

????? ? 所以對(duì)于機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘來說，我們需要一個(gè)新的計(jì)算抽象，能夠支持異步動(dòng)態(tài)的計(jì)算抽象。所以作者就提出了分布式機(jī)器學(xué)習(xí)計(jì)算框架：GraphLab。GraphLab設(shè)計(jì)目標(biāo)是專門為機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘考慮的。它利用了圖數(shù)據(jù)的依賴、支持異步、迭代計(jì)算和動(dòng)態(tài)計(jì)算特性。下面我們來介紹GraphLab的設(shè)計(jì)。

3. System Desgin

3.1 DataGraph

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

3.2 Update Functions

????????計(jì)算方式被編碼在GraphLab框架的更新函數(shù)中。一個(gè)更新函數(shù)是一個(gè)無狀態(tài)的過程，這個(gè)過程修改一個(gè)頂點(diǎn)作用域內(nèi)的數(shù)據(jù)和調(diào)度未來執(zhí)行在其他頂點(diǎn)上的更新函數(shù)。一個(gè)頂點(diǎn)v的作用域(用Sv表示)是存儲(chǔ)在v上的數(shù)據(jù)，以及數(shù)據(jù)存儲(chǔ)的所有相鄰點(diǎn)和相鄰邊(圖2(a))。

????????GraphLab更新函數(shù)把一個(gè)點(diǎn)v和作用域Sv作為輸入，并返回作用域內(nèi)數(shù)據(jù)的新版本——頂點(diǎn)的集合T。

????????在執(zhí)行更新函數(shù)后，在Sv上的修改數(shù)據(jù)會(huì)被寫回到數(shù)據(jù)圖。頂點(diǎn)集T的每個(gè)頂點(diǎn)u最終更新執(zhí)行為函數(shù)f(u，Su)依據(jù)執(zhí)行語義描述。

4. GraphLab Execution Model

????????GraphLab框架的輸入包括數(shù)據(jù)圖G =(V，E，D)， 一個(gè)更新函數(shù)，一個(gè)將被執(zhí)行初始頂點(diǎn)集合。當(dāng)有頂點(diǎn)在T，該算法選擇(第1行)和執(zhí)行(第2行) 頂點(diǎn)，添加任何新的頂點(diǎn)回到T(第3行)。重復(fù)的頂點(diǎn)被忽略。最后數(shù)據(jù)圖和全局值在完成后返回給用戶。

????????為了更有效的分布式執(zhí)行，我們降低了執(zhí)行共享內(nèi)存GraphLab框架的要求，并且允許GraphLab運(yùn)行時(shí)確定最佳的頂點(diǎn)執(zhí)行順序。例如，RemoveNext(T) 可以選擇返回依照最小化網(wǎng)絡(luò)溝通或延遲的順序來執(zhí)行頂點(diǎn)(見第4.2.2節(jié))。GraphLab框架允許用戶指定優(yōu)先級(jí)對(duì)在T中的頂點(diǎn)，所以許多MLDM應(yīng)用程序從優(yōu)先級(jí)受益。GraphLab運(yùn)行時(shí)可能會(huì)使用這些優(yōu)先級(jí)結(jié)合系統(tǒng)級(jí)目標(biāo)來優(yōu)化頂點(diǎn)的執(zhí)行順序。

4.1 可串行化執(zhí)行

????? ? GraphLab為了防止數(shù)據(jù)競(jìng)爭(zhēng)以及方便程序的調(diào)試、運(yùn)行。GraphLab支持頂點(diǎn)程序的可串行化執(zhí)行，也就是說防止相鄰頂點(diǎn)同時(shí)運(yùn)行頂點(diǎn)程序。

????????一個(gè)實(shí)現(xiàn)可串行性的簡(jiǎn)單方法是確保同時(shí)執(zhí)行的更新函數(shù)作用域不重疊。在[24]我們稱之為完全一致性模型(見圖2(b))。然而，完全一致性同時(shí)限制了潛在的并行性，執(zhí)行更新函數(shù)必須至少兩個(gè)頂點(diǎn)(見圖2(c))。然而，對(duì)于許多機(jī)器學(xué)習(xí)算法，更新功能不需要完整的讀/寫訪問所有的數(shù)據(jù)作用域的權(quán)限。例如，PageRank更新只需要讀訪問邊和相鄰的頂點(diǎn)的權(quán)限。為了提供更大的并行性，同時(shí)保留可串行性，GraphLab 定義了邊一致性模型。邊一致性模型確保每個(gè)更新函數(shù)獨(dú)占讀寫訪問頂點(diǎn)和相鄰的邊，但只讀訪問相鄰的點(diǎn)（圖2(b))。因此，邊緣一致性模型也在不斷增加并行性，通過允許更新函數(shù)使用少量重疊作用域來安全并行運(yùn)行(見圖2(c))。最后，點(diǎn)一致性模型允許并行運(yùn)行，所有更新功能提供最大的并行性。

4.2 染色引擎

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

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

4.3 分布式鎖引擎

????????當(dāng)染色引擎滿足分布式GraphLab框架（第3節(jié)），它不提供足夠的調(diào)度靈活性為許多有趣的應(yīng)用程序。此外，它是以圖著色的可用性為先決條件，這可能并非總是有效的。為了克服這些限制，我們介紹擴(kuò)展了用于共享內(nèi)存引擎的技術(shù)的分布式互斥鎖引擎。

????????我們通過實(shí)現(xiàn)分布式互斥讀寫鎖關(guān)聯(lián)每個(gè)頂點(diǎn)。不同的一致性模型可以使用不同的鎖協(xié)議實(shí)現(xiàn)。頂點(diǎn)　　的一致性是通過獲取每個(gè)請(qǐng)求中心頂點(diǎn)作用域的寫鎖來完成的。邊一致性是通過在中央頂點(diǎn)獲取寫鎖，在相鄰的頂點(diǎn)獲取讀鎖。最后，完全一致性是通過獲取中央頂點(diǎn)和相鄰頂點(diǎn)的寫鎖來實(shí)現(xiàn)。通過依照有順序的規(guī)范秩序的方式獲取鎖而避免死鎖。我們依照頂點(diǎn)id的機(jī)器id來引用(所有者(v)，v)，因?yàn)檫@允許在一個(gè)遠(yuǎn)程的機(jī)器的所有鎖可以被請(qǐng)求通過單個(gè)消息。

總結(jié)

以上是生活随笔為你收集整理的[PVLDB 12] GraphLab : 分布式机器学习大规模图处理系统 学习总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。