大數據圖數據庫之離線挖掘計算模型

/* .*/ author:張俊林 節選自《大數據日知錄：架構與算法》十四章，書籍目錄在此 對于離線挖掘類圖計算而言，目前已經涌現出眾多各方面表現優秀而各具特點的實際系統，典型的比如Pregel、Giraph、Hama、PowerGraph、GraphLab、GraphChi等。通過對這些系統的

/* .*/
author: 張俊林

節選自《大數據日知錄：架構與算法》十四章，書籍目錄在此

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

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

14.4.1 以節點為中心的編程模型

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

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

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

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

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

14.4.2 GAS編程模型

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

這里假設當前要進行計算的節點是u，并以此為基礎來說明GAS模型。

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

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

14.4.3 同步執行模型

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

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

14.4.4 異步執行模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com