分散式圖計算同步非同步綜述

本文主要介紹：

以Pregel為代表的同步計算模型

以GraphLab為代表的非同步計算模型

先導知識：

1. 在圖計算中，具有邊數據（Edge Data ），點數據（Vertex Data ）。不同的圖計算模型中，邊未必會存有數據。

2. 圖計算的切分方法：點切割（主流），邊切割

現在普遍學術界使用的是點切割方式，在上交陳海波教授的一篇文章後又有提及點切割與邊切割結合的方法。

以下是介紹Pregel的同步模型：

Pregel //同步的機制，每個節點向外傳播信息，每個節點根據自身收到的信息進行ra

http://blog.csdn.net/zk_j1994/article/details/70184938

http://makaidong.com/pelick/1/328343_12272816_2.htm 中文論文

缺點：發送過多信息，導致網路交通擁堵。同步的機制也容易丟失信息

同步計算會導致昂貴的性能損失，因為每個階段的運行時是取決於最慢的機器。

GrapthLab //非同步的機制，利用共享內存，共享其他鄰接點

http://www.360doc.com/content/16/0629/22/30344733_571767159.shtml

https://wenku.baidu.com/view/3e6e0591fab069dc5022016e.html中文論文

缺點：節點過多的對周邊信息調用，非同步過程，其他鄰接點也必須上鎖，效率降低

1)Gather階段 工作頂點的邊 (可能是所有邊，也有可能是入邊或者出邊)從領接頂點和自身收集數據，記為gather_data_i，各個邊的數據graphlab會求和，記為sum_data。這一階段對工作頂點、邊都是只讀的。

使用了Cache機制。PowerGraph引擎為每一個節點之前的Gather步驟維持一個累加器a，每當收節點收到一個信息。Scatter功能就會自動地將原來a的值加上這個信息里附加的新值，只要這個a值存在，那麼就可以繞過Gather這個步驟，節省很多計算量。

2)Apply階段 Mirror將gather計算的結果sum_data發送給master頂點，master進行匯總為total。Master利用total和上一步的頂點數據，按照業務需求進行進一步的計算，然後更新master的頂點數據，並同步mirror。Apply階段中，工作頂點可修改，邊不可修改。

3)Scatter階段 工作頂點更新完成之後，更新邊上的數據，並通知對其有依賴的鄰結頂點更新狀態。這scatter過程中，工作頂點只讀，邊上數據可寫。(本機）

在執行模型中，graphlab通過控制三個階段的讀寫許可權來達到互斥的目的。在gather階段只讀，apply對頂點只寫，scatter對邊只寫。並行計算的同步通過master和mirror來實現，mirror相當於每個頂點對外的一個介面人，將複雜的數據通信抽象成頂點的行為。

兩種方式都容易出現使單個機子出現太多邊

1.平衡度：現在的演算法會導致各個機器的數據分布不平衡，也就是有的機器數據信息很多，有的機器很少。

2.分割：因為Pregel跟GraphLab都是用哈希函數隨機分配，所以會導致很多節點被分配到很差的位置。

3.通信：以上兩種方法會導致大量的通信。

4.存儲：單個機器的存儲容量可能會不夠用。

5.計算：可擴展性比較差。

採用點分割，能夠減少通信量

在PowerGraph中通信的方式也有變化，如下圖所示，所有的Gather計算均在本地機器上進行計算，然後每一台機器的計數器的值都會一起被發送到主機器上面，主機器進行Apply的運算，然後將所有修改過的節點值發送給各個副機器，最後Scatter階段而是在各個本地機器上進行通信，這樣就減少了很多通信量。

1.Gather階段：用戶自定義一個sum操作，用於各個vertex，將vertex的相鄰vertex和對應edge的信息收集起來；

2.Apply階段：各個vertex利用上一階段的sum值進行計算更新原始值；（主機，需要修改的發送給子機）

3.Scatter階段：利用第二階段的計算結果更新vertex相連的edge值。（子機器

也就是說，先子機收集點與點的信息，之後所有子機一起上交到總機器，最後由總機器一起計算。在Scatter階段將結果數據分發給各個子機

點切分的方法

隨機邊分配

貪婪協同邊分配 （如果有共同的點，那麼哪裡邊點少就放哪邊）

1.協同邊放置策略，維護一張全局的表，用於查詢更新。特點：慢，但切分質量高

非貪婪邊分配（Oblivious遺忘）

2.不做全局表，只做單機版的表，快，切分質量低

存在的問題：點存在的機器的數量

如果數量過多，就存在通訊過多問題

在鏡像中，如果存在點的多個副本，隨機取一個為主體，其他的設置成只讀許可權

https://www.2cto.com/kf/201604/501492.html

頂點更新：可串列化

使多個處理器同時對多個頂點進行更新，直觀的方法就是計算不重疊的多個範圍同時運行

完全一致模型：

在這種模式下同時進行更新的範圍完全不重合。如下圖所示，這時候更新函數對頂點3範圍內的所有頂點和邊都有完全的讀寫許可權。然而在許多ML&DM演算法中，並不要求對範圍內的所有數據都有完全的讀寫許可權，例如PageRank只需要讀取鄰接邊和頂點的數值。因此，完全一致模型就限制了該演算法潛在的並行度

邊一致模型：

在這種模式下，相鄰範圍內的鄰接頂點允許重合。如下圖所示，這時候更新函數對中心頂點以及鄰接邊有完全的讀寫許可權，而對鄰接頂點只有讀許可權。它略微提高了更新函數的並行性。

頂點一致模型：

在這種模式下，範圍內的鄰接頂點和鄰接邊都允許重合。如下圖所示，更新函數只對中心頂點有讀寫的許可權，對鄰接邊只有讀的許可權，對鄰接頂點無讀寫許可權。所以，該一致性模型允許圖中的所有頂點同時更行。

Graph-parallel 基於每個節點有一個鄰節點去最大化並行度，有效分區的減少節點間的聯繫

BUT 社交圖和網路圖通常是冪律分布，這意味著一個小節點連接著圖的很大一部分。因此，冪律分布的圖很難切分在分散式系統中（二八定律）

Powergraph使用同步加非同步

同步在於PowerGraph一直執行vertex-program，直到沒有vertex-program。非同步在於在scatter階段可以能夠激活邊兩端的vertex-program

同步：gather,apply,scatter每個階段叫aminor-step.整個流程叫super-step。完成每個階段都會有個障礙在等待。類似pregel

非同步：當非同步運行時，PowerGraph引擎會在處理器和網路資源可用時執行活動頂點。在應用和散射函數期間對頂點和邊緣數據所做的更改立即提交給圖形，並在相鄰頂點的後續計算中可見。通過在處理器和網路資源變得可用並對數據圖進行任何更改時對其進行計算

非同步的解決：可能出現結果不確定性。GraphLab自動實施可串列化：頂點程序具有相應的順序執行。為了實現可串列化，GraphLab使用細粒度的鎖定協議來防止相鄰的頂點程序同時運行，該協議要求在所有相鄰的頂點上鎖定連續的鎖。此外，GraphLab使用的鎖定方案對高度頂點不公平。 PowerGraph保留了GraphLab強大的可串列性保證，同時解決了它的局限性。我們通過引入一個對高度頂點公平的新並行協議（在7.4節中描述）來解決順序鎖定的問題。此外，PowerGraph抽象揭示了更多的細粒度（邊緣級）並行性，允許整個集群支持單個頂點程序的執行

1. 全局同步與Pregel類似，Superstep之間設置全局同步點，用以同步對所有edge以及vertex的修改；
2. 全局非同步類似GraphLab，所有Apply階段和Scatter階段對edge或vertex的修改立即更新到圖中；
3. 全局非同步會使得演算法設計和調試變得很複雜，對某些演算法效率可能比全局同步還差，因此有全局非同步加可串列化結合的方式。

推薦閱讀：