大數(shù)據(jù)圖數(shù)據(jù)庫之離線挖掘計算模型

  對于離線挖掘類圖計算而言，目前已經(jīng)涌現(xiàn)出眾多各方面表現(xiàn)優(yōu)秀而各具特點的實際系統(tǒng)，典型的比如Pregel、Giraph、Hama、PowerGraph、GraphLab、GraphChi等。通過對這些系統(tǒng)的分析，我們可以歸納出離線挖掘類圖計算中一些常見的計算模型。

    本節(jié)將常見的計算模型分為兩類，一類是圖編程模型，另一類是圖計算范型。編程模型更多地面向圖計算系統(tǒng)的應用開發(fā)者，而計算范型則是圖計算系統(tǒng)開發(fā)者需要關(guān)心的問題。在本節(jié)中，關(guān)于編程模型，主要介紹以節(jié)點為中心的編程模型及其改進版本的GAS編程模型；關(guān)于計算范型，則重點介紹同步執(zhí)行模型和異步執(zhí)行模型。這幾類模型已經(jīng)被廣泛采用在目前的大規(guī)模圖挖掘系統(tǒng)中。

14.4.1  以節(jié)點為中心的編程模型

     以節(jié)點為中心的編程模型（Vertex-Centered ProgrammingModel）首先由Pregel系統(tǒng)提出，之后的絕大多數(shù)離線挖掘類大規(guī)模圖計算系統(tǒng)都采用這個模型作為編程模型。

     對圖G=(V,E)來說，以節(jié)點為中心的編程模型將圖節(jié)點vertex?V看作計算的中心，應用開發(fā)者可以自定義一個與具體應用密切相關(guān)的節(jié)點更新函數(shù)Function(vertex)，這個函數(shù)可以獲取并改變圖節(jié)點vertex及與其有關(guān)聯(lián)的邊的權(quán)值，甚至可以通過增加和刪除邊來更改圖結(jié)構(gòu)。對于所有圖中的節(jié)點都執(zhí)行節(jié)點更新函數(shù)Function(vertex)來對圖的狀態(tài)（包括節(jié)點信息和邊信息）進行轉(zhuǎn)換，如此反復迭代進行，直到達到一定的停止標準為止。

     典型的圖節(jié)點更新函數(shù)Function(vertex)基本遵循如下邏輯。

      即首先從vertex的入邊和出邊收集信息，對這些信息經(jīng)過針對節(jié)點權(quán)值的函數(shù)f()變換后，將計算得到的值更新vertex的權(quán)值，之后以節(jié)點的新權(quán)值和邊原先的權(quán)值作為輸入，通過針對邊的函數(shù)g()進行變換，變換后的值用來依次更新邊的權(quán)值。通過vertex的節(jié)點更新函數(shù)，來達到更新部分圖狀態(tài)的目的。

     以節(jié)點為中心的編程模型有很強的表達能力。研究表明，很多類型的問題都可以通過這個編程模型來進行表達，比如很多圖挖掘、數(shù)據(jù)挖掘、機器學習甚至是線性代數(shù)的問題都可以以這種編程模型來獲得解決。這也是為何以圖節(jié)點為中心的編程模型大行其道的根本原因。

14.4.2  GAS編程模型

      GAS模型可以看作是對以節(jié)點為中心的圖計算編程模型的一種細粒度改造，通過將計算過程進一步細分來增加計算并發(fā)性。GAS模型明確地將以節(jié)點為中心的圖計算模型的節(jié)點更新函數(shù)Function(Vertex)劃分為三個連續(xù)的處理階段：信息收集階段（Gather）、應用階段（Apply）和分發(fā)階段（Scatter）。通過這種明確的計算階段劃分，可以使原先的一個完整計算流程細分，這樣在計算過程中可以將各個子處理階段并發(fā)執(zhí)行來進一步增加系統(tǒng)的并發(fā)處理性能。

     這里假設(shè)當前要進行計算的節(jié)點是u，并以此為基礎(chǔ)來說明GAS模型。

      在信息收集階段，將u節(jié)點的所有鄰接節(jié)點和相連的邊上的信息通過一個通用累加函數(shù)收集起來：

      通過以上三個階段的操作，可以定義以圖節(jié)點為中心的高度抽象的GAS計算模型。在GAS模型中，節(jié)點的入邊和出邊在信息收集和分發(fā)階段如何使用取決于具體的應用，比如，在PageRank計算中，信息收集階段只考慮入邊信息，分發(fā)階段只考慮出邊信息，但是在類似于Facebook的社交關(guān)系圖中，如果邊表達的語義是朋友關(guān)系，那么在信息收集和分發(fā)階段則是所有邊的信息都會納入計算范圍。

14.4.3  同步執(zhí)行模型

      同步執(zhí)行模型是相對于異步執(zhí)行模型而言的。我們知道，圖計算往往需要經(jīng)過多輪迭代過程，在以節(jié)點為中心的圖編程模型下，在每輪迭代過程中對圖節(jié)點會調(diào)用用戶自定義函數(shù)Function(vertex)，這個函數(shù)會更改vertex節(jié)點及其對應邊的狀態(tài)，如果節(jié)點的這種狀態(tài)變化在本輪迭代過程中就可以被其他節(jié)點看到并使用，也就是說變化立即可見，那么這種模式被稱為異步執(zhí)行模型；如果所有的狀態(tài)變化只有等到下一輪迭代才可見并允許使用，那么這種模式被稱為同步執(zhí)行模型。采用同步執(zhí)行模型的系統(tǒng)在迭代過程中或者連續(xù)兩輪迭代過程之間往往存在一個同步點，同步點的目的在于保證每個節(jié)點都已經(jīng)接受到本輪迭代更新后的狀態(tài)信息，以保證可以進入下一輪的迭代過程。

      在實際的系統(tǒng)中，兩種典型的同步執(zhí)行模型包括BSP模型和MapReduce模型。關(guān)于BSP模型的介紹及其與MapReduce模型的關(guān)系，可以參考本書“機器學習：范型與架構(gòu)”一章，這里不再贅述。下面介紹圖計算中的MapReduce計算模型，總體而言，由于很多圖挖掘算法帶有迭代運行的特點，MapReduce計算模型并不是十分適合解決此類問題的較佳答案，但是由于Hadoop的廣泛流行，實際工作中還有一些圖計算是采用MapReduce機制來進行的。

14.4.4  異步執(zhí)行模型

      異步執(zhí)行模型相對于同步執(zhí)行模型而言，因為不需要進行數(shù)據(jù)同步，而且更新的數(shù)據(jù)能夠在本輪迭代即可被使用，所以算法收斂速度快，系統(tǒng)吞吐量和執(zhí)行效率都要明顯高于同步模型。但是異步模型也有相應的缺點：其很難推斷程序的正確性。因為其數(shù)據(jù)更新立即生效，所以節(jié)點的不同執(zhí)行順序很可能會導致不同的運行結(jié)果，尤其是對圖節(jié)點并發(fā)更新計算的時候，還可能產(chǎn)生爭用狀況（Race Condition）和數(shù)據(jù)不一致的問題，所以其在系統(tǒng)實現(xiàn)的時候必須考慮如何避免這些問題，系統(tǒng)實現(xiàn)機制較同步模型復雜。

     下面以GraphLab為例講解異步執(zhí)行模型的數(shù)據(jù)一致性問題，GraphLab比較適合應用于機器學習領(lǐng)域的非自然圖計算情形，比如馬爾科夫隨機場（MRF）、隨機梯度下降算法（SGD）等機器學習算法。

在講解異步模型的數(shù)據(jù)一致性問題前，先來了解一下GraphLab論文提出的圖節(jié)點的作用域（Scope）概念。對于圖G中的某個節(jié)點v來說，其作用域S_v包括：節(jié)點v本身、與節(jié)點v關(guān)聯(lián)的所有邊，以及節(jié)點v的所有鄰接圖節(jié)點。之所以定義圖節(jié)點的作用域，是因為在以節(jié)點為中心的編程模型中，作用域體現(xiàn)了節(jié)點更新函數(shù)f(v)能夠涉及的圖對象范圍及與其綁定的數(shù)據(jù)。

     在并發(fā)的異步執(zhí)行模型下，可以定義三類不同強度的數(shù)據(jù)一致性條件（見圖14-12），根據(jù)其一致性限制條件的強度，由強到弱分別為：完全一致性（Full Consistency）、邊一致性（Edge Consistency）和節(jié)點一致性（Vertex Consistency）。

      完全一致性的含義是：在節(jié)點v的節(jié)點更新函數(shù)f(v)執(zhí)行期間，保證不會有其他更新函數(shù)去讀寫或者更改節(jié)點v的作用域S_v內(nèi)圖對象的數(shù)據(jù)。因此，滿足完全一致性條件的情形下，并行計算只允許出現(xiàn)在無公共鄰接點的圖節(jié)點之間，因為如果兩個圖節(jié)點有公共鄰接圖節(jié)點，那么兩者的作用域必有交集，若兩者并發(fā)執(zhí)行，可能會發(fā)生爭用狀況，而這違反了完全一致性的定義。

     比完全一致性稍弱些的是邊一致性條件，其含義為：在節(jié)點v的節(jié)點更新函數(shù)f(v)執(zhí)行期間，保證不會有其他更新函數(shù)去讀寫或者更改節(jié)點v，以及與其鄰接的所有邊的數(shù)據(jù)。即與完全一致性條件相比，放松了條件，允許讀寫與節(jié)點v鄰接的其他圖節(jié)點的數(shù)據(jù)。在滿足邊一致性條件下，并行計算允許出現(xiàn)在無公共邊的圖節(jié)點之間，因為只要兩個節(jié)點u和v不存在共享邊，則一定會滿足邊一致性條件。

     更弱一些的是節(jié)點一致性，其含義為：在節(jié)點v的節(jié)點更新函數(shù)f(v)執(zhí)行期間，保證不會有其他更新函數(shù)去讀寫或者更改節(jié)點v的數(shù)據(jù)。很明顯，最弱的節(jié)點一致性能夠允許最大程度的并發(fā)，之所以說其限制條件較弱，是因為除非應用邏輯可以保證節(jié)點更新函數(shù)f(v)只讀寫節(jié)點本身的數(shù)據(jù)，否則很易發(fā)生爭用狀況，使得程序運行結(jié)果不一致。

     選擇不同的一致性模型對于并行程序執(zhí)行的結(jié)果正確性有很大影響，所謂并行執(zhí)行的結(jié)果正確性，可以用其和順序執(zhí)行相比是否一致來進行判斷。因此，可以定義“序列一致性”如下：

     如果對所有可能的并發(fā)執(zhí)行順序總是存在與序列執(zhí)行完全一致的執(zhí)行結(jié)果，在此種情形下，我們可以將這個并發(fā)程序稱為是滿足序列一致性的。

      是否滿足序列一致性可以幫助我們驗證將一個順序執(zhí)行的程序改造為并行執(zhí)行程序后的正確性。在并行的異步圖計算環(huán)境下，以下三種情形是可以滿足序列一致性的。

情形一：滿足完全一致性條件。

情形二：滿足邊一致性條件，并且節(jié)點更新函數(shù)f(v)不會修改鄰接節(jié)點的數(shù)據(jù)。

情形三：滿足節(jié)點一致性條件，并且節(jié)點更新函數(shù)f(v)只會讀寫節(jié)點本身的數(shù)據(jù)。

     上面三種情形可供應用者在設(shè)計算法時參考，以在并發(fā)性和結(jié)果正確性之間做好權(quán)衡：一致性條件越弱，則并發(fā)能力越強，但是爭用狀況發(fā)生概率越高，即結(jié)果可能越難保障正確性。如果應用能夠明確節(jié)點更新函數(shù)的數(shù)據(jù)涉及范圍，就可以根據(jù)上述幾種情形來進行選擇，更好地做到在保證結(jié)果正確性的前提下提高并發(fā)性能。