閱讀筆記：PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs

PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs 這篇論文講的是一種新的分散式圖計算的框架。

在論文開頭，作者們回顧了兩種圖計算框架，其中一種是Pregel，另一種是GraphLab。雖然這兩種框架的實現不同，但是文章用GAS結構統一的對這兩個框架進行了描述，因而在論文作者眼裡這兩種框架是一樣的。

先分別談談兩個圖計算的框架。這兩個框架解決的都是給定一個圖 G = {V, E}，進行某種圖演算法的計算，而圖演算法的計算一般牽扯到結點和邊的值的計算和更新。

Pregel

Pregel允許用戶定義結點計算規則和邊值傳遞規則。以PageRank為例，Pregel所寫的代碼如下：

PageRank需要知道鄰結點給當前結點的權重，也需要把更新過的當前節點的權重發給鄰結點。因此Pregel定義了信息，信息用來傳送一個結點想傳播給另一個結點的值。對於迭代式的演算法而言，每一輪迭代，都要處理完當前輪的信息（設置一個barrier），才能進入一下輪。用戶使用Pregel，要提供兩個函數，一個是信息傳遞，一個是結點計算。

GraphLab

GraphLab的不同之處在於，對於一個結點，其鄰結點和鄰邊的狀態直接可見可改，因此GraphLab不需要通過信息這種方式傳遞值。例如PageRank在GraphLab中的實現如下：

如上文所提到，論文中提出了一個GAS理論，來描述這兩種框架。G是Gather，收集；A是Apply，計算；S是Scatter，分散。這兩種框架都是先收集一些值，在本節點進行計算，在對鄰邊進行對應的值更新。

論文介紹完了兩種先驅框架後，開始列舉這兩種框架的不足之處，這些不足和實際要解決的圖問題的特性是緊密相關的。

實際的圖問題的Degree Distribution (度分布？）遵從冪定律。所謂冪定律，可以理解為「二八原則」，也就是少數的部分貢獻了大部分的產出。實際圖問題的度分布遵從公式：

P(d)是結點的度為d的概率，而alpha是一個常數。一言以蔽之，度值越大的概率越小。在log-log scale下的一個度分布的圖例為：

由於這個度分布的特性，從直覺上來說，我們可以想到：不是所有的結點的計算量都是相當的。有少數結點的計算量可能非常大。具體的問題有以下幾點：

負載均衡。如上面所說，有的結點的度非常大，那麼如果將10000個結點分給10台機，那麼隨機平均分是不合理的。

分片。這個問題和負載均衡類似。從查到的資料和論文來看（其實我還是不確定）：Pregel的圖的分散式置放方式是基於節點的。簡單地說就是結點要平均分散到機群上，要求跨機群的邏輯上的圖的邊總數最少。回憶，Pregel是消息傳遞模式，邊意味著有消息發送和接收的成本。GraphLab的分散式置放方式是基於節點的邊的，也就是隨機的把邊分布到不同機器上。回憶，由於GraphLab是鄰結點狀態共享，所以結點間的更新是鄰結點可見的。對於分散式環境來說，例如有一個圖是b--a---c，然後有兩台機，b--a，a---c就分別分散到兩台機上，那麼在實現中有a的幽靈結點存在，也就是說兩台機各有一個a。當一台機的a的狀態改變時，會通過網路更新其幽靈結點的信息。所以基於邊的分散式置放和GraphLab自己的狀態共享模型簡直是完美貼合。在這裡貼一個伊利諾伊大學香檳分校2013年春季cs525圖分析課件里的圖：

在這裡GraphLab的集群通信代價是最小的。下面在談到具體的分散式圖置放演算法也會提到為什麼即使GraphLab和PowerGraph都採用類似的置放邊的Vertex-cut的演算法，但是GraphLab比PowerGraph通訊代價低（複雜性上GraphLab的通訊代價是O(幽靈結點數量)，而PowerGraph是O(2 * 鏡像結點數量)，這裡幽靈結點和鏡像結點是類似的概念）。

通訊。因為是分散式框架，必然要涉及到多節點的通訊。對於Pregel來說，某一個度值很大的結點可能會產生上萬條內容重複的信息（例如上文的PageRank，某個結點向數萬個鄰結點各發送一條包含了一個一樣值的信息）。

內存存儲。運行中必要的數據要緩存在內存中，但是度值高的結點存的數據可能會超過內存大小。

計算量。雖然不同結點可能並行計算，但是以上兩種框架並不並行結點內的計算。

說了這麼多，論文算是曆數了Pregel和GraphLab的所有罪過，然後提出了自己的解決方案：PowerGraph。

PowerGraph

PowerGraph自己的編程介面設計為：

這一設計也遵從上面提到的GAS。不過它自己多了一個SUM，和Gather結合起來使用。這一介面也可以用來表達GraphLab和Pregel（畢竟都遵從GAS)。

這一個是PowerGraph執行引擎的流程示意代碼：

基本邏輯引擎限制性一個結點代碼的Gather和Sum，然後執行Apply，最後做Scatter。至於結點之間的執行順序（也就是如何進行結點間並發），論文里沒有提及。

那麼PowerGraph有什麼特點呢？

Delta緩存（Delta Caching）。從上面的流程示意代碼可以看見，對於每一個結點，引擎自身有一個au的緩存值，而且在每一輪結束後，針對當前的結點的更新的偏移會被直接加到鄰結點上。也就是在一下輪的計算中，鄰結點不用做Gather（上一輪順便做了，這也是共享狀態模型的好處）。

同步和非同步執行。這裡的同步和非同步不是並行編程里的概念。PowerGraph按Gather和Sum，Apply，Scatter，把一次迭代分成三部分。同步是指只有在同一次迭代某一部分的所有結點都完成了對應的操作（例如在第一部分所有的Gather和Sum都執行完畢了），下一部分才能看到狀態的更新。其實這也就是一定要一個部分全部執行完，才能執行一下部分。非同步就是下一部分不必等上一部分全部執行完，只要單個的Primitive（例如Apply）執行完，那麼它的對應的下一步就能執行（例如Scatter）。非同步有點像處理器的流水線。直覺上來看，非同步有利於演算法加速運算和收斂。但是我覺的這個和具體演算法有關。有的演算法只靠同步是沒法收斂的；有的演算法可能非同步出來雖然收斂的快，但是結果不對。

最後在寫寫一個很重要的問題：圖的分散式置放

圖的分散式置放（Distributed Graph Placement）

圖的分散式值的是將數據圖（Data Graph）進行切割，放置在不同機器上，已進行分散式計算，從而解決大規模圖的計算問題。圖的切割對實際運算的效率影響很大。由於分散式會帶來網路和存儲的額外成本，好的圖的切割能顯著降低網路通訊的成本。另外，對於遵從冪定律的圖來說，它的切割需要別出心裁的想法。以下是幾種圖的切割法：

1. 按點來切分（Edge-cut）。按點切分是指將點分散在不同機器上，那麼通訊的成本就被跨機器的邊數所限制。點可以隨機進行分配（性能差），也可以做一個線性規劃，要求分配的點滿足跨機器的邊最小。這種切分法和信息傳遞模型想匹配。一條邊就代表迭代中的一條信息。

2. 按邊切分（vertex-cut）。按邊切分是指將邊分散在不同機器上。這種劃分和狀態共享模型相匹配。為了進行通訊來更新結點值，一般有幽靈結點或者鏡像結點，代表著不同機器上的一個結點。通訊的成本的限制來自跨機器的結點。

3. 貪心的按邊切分 （Greedy vertex-cut）。這種切分法是2的改進型，就是在已分n的邊的情況下，第n+1條邊要分給某一天符合特定規則的機器。例如分給一個機器，此機器應有某一個結點，其度比邊的另一個結點大。

PowerGraph採用的是共享狀態模型，不需要進行消息傳遞，所以使用了按邊切分的演算法。其跨機器結點的設定是主從模式，有一個隨機選擇的主結點，和其它鏡像結點（從結點）。鏡像結點只讀。因此做完Gather和Sum後，鏡像結點先把值發回主結點，然後主結點Apply，然後再傳播回鏡像結點。這也是為什麼通訊複雜度是O(2 * 鏡像結點數量)，上面的性能示意圖中PowerGraph也可以解釋了。

但是。。在論文里，PowerGraph是比GraphLab要好的。。。

可能的原因是數據集和機群的大小。論文的實驗只在32個機器上做。上面的圖裡最高有250台機器。可能GraphLab的Scalability更好。但是在某些數據集和少一點的機器上，PowerGraph表現更優。
推薦閱讀：