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

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

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

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

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

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

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

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

     以節(jié)點(diǎn)為中心的編程模型有很強(qiáng)的表達(dá)能力。研究表明，很多類型的問(wèn)題都可以通過(guò)這個(gè)編程模型來(lái)進(jìn)行表達(dá)，比如很多圖挖掘、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)甚至是線性代數(shù)的問(wèn)題都可以以這種編程模型來(lái)獲得解決。這也是為何以圖節(jié)點(diǎn)為中心的編程模型大行其道的根本原因。

14.4.2  GAS編程模型

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

     這里假設(shè)當(dāng)前要進(jìn)行計(jì)算的節(jié)點(diǎn)是u，并以此為基礎(chǔ)來(lái)說(shuō)明GAS模型。

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

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

14.4.3  同步執(zhí)行模型

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

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

14.4.4  異步執(zhí)行模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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