[OSDI 12] PoweGraph: 分散式圖並行計算框架 學習總結

[OSDI 12] PoweGraph: 分散式圖並行計算框架 學習總結

來自專欄圖計算4 人贊了文章

今天要講的文章是OSDI 2012年的一篇文章，PowerGraph：Distributed Graph-Parallel Computation on Natural Graphs。本文主要想解決的問題就是：現有的圖數據，如社交網路、Web網頁等都是一種Power-law冪律圖的特徵。所謂Power-law冪律圖就是指在圖數據中頂點的度數分配不均勻。有的圖頂點的度數很高，有的頂點度數很低。並且頂點度數呈現著冪律分布的特徵，對於這種Power-law的圖數據，會存在很大的計算分配不均勻的特徵。針對這個問題：PowerGraph分析了在冪律圖的特徵情況下，採用vertex-cut劃分的策略。採用vertex-cut，切分成若干個Mirror頂點。利用Mirror頂點減少了高度頂點計算任務繁重的問題，並且採用vertex-cut劃分策略產生很少一部分的Mirror。

1. Graphs are ubiquitous

我們都知道，圖在我們生活中是無所不在的。

社交媒體、科學中分子結構關係、電商平台的廣告推薦、網頁信息。圖是能夠將人、產品、想法、事實、興趣愛好之間的關係進行編碼，轉成一種結構進行存儲。圖的一個特點是：Big，數十億的點和邊以及豐富的元數據。各種場景下的信息都能轉成圖來表示，同時我們可以利用圖來進行數據挖掘和機器學習，比如 ，識別出有影響力的人和信息、社區發現、尋找產品和廣告的投放用戶、給有依賴關係的複雜數據構建模型等等這些都可以使用圖來完成。

2. Natural Graphs

從不同平台或實際應用中產生的圖我們稱為：Natural Graphs。面對各種應用中如此海量的Natural Graphs，現有分散式的圖處理平台處理性能還是比較低效的。作者選用Twitter數據集測試目前幾個主流分散式平台在處理這種Natural Graph的性能，這裡是利用PageRank演算法每次迭代的時間作為橫軸，縱坐標是不同的分散式平台，可以看到Hadoop和原生態的GraphLab的處理時間還是很長的，性能最好的是Piccolo，這裡舉一個明星效應的例子，比如這裡表示社交網路中的一個子圖，中間紅色點表示某個用戶，旁邊黑點表示的是所有的粉絲，比如這裡我們一個黑點表示100w的用戶，那麼這個人可能就是obama，但像obama這樣擁有這麼多粉絲的人是非常少的，大部分人粉絲只有大黑點中的一個點，幾百或者多者上千。這就是我們說的密率度分布圖的特點。它是Google的Pregel的C++實現 。

現有的分散式圖處理系統在自然圖中的處理性能都很差。這是為什麼會造成這個原因呢？下面我們來看一下自然圖到底有什麼特徵。

2.1 Power-Law Degree Distribution

下面我們來看一下，Natural Graph這種圖到底有什麼特點，為什麼大部分分散式處理系統性能都比較低效，PowerGraph在Natural Graph有如此好的性能。Natural Graphs的屬性特點是滿足密率度分布。下面我們來看下什麼叫冪律度分布。

簡單來說，冪律有兩個通俗的解釋，一個是「長尾」理論，只有少數明星是有很多人關注的，但是還有大部分人只有少部分人關注。長尾理論就是對冪律通俗化的解釋。 另外一個通俗解釋就是馬太效應，窮者越窮富者越富。 從這幅圖可以看出，只有一個鄰居的點的數目有超過10的8次方個，而僅有那1%的點卻佔了整個圖50%的邊。這些點被稱為高緯度點。

這裡舉一個明星效應的例子，比如這裡表示社交網路中的一個子圖，中間紅色點表示某個用戶，旁邊黑點表示的是所有的粉絲，比如這裡我們一個黑點表示100w的用戶，那麼這個人可能就是obama，但像obama這樣擁有這麼多粉絲的人是非常少的，大部分人粉絲只有大黑點中的一個點，幾百或者多者上千。這就是我們說的密率度分布圖的特點。

現有的大部分研究表明，對於這樣的冪律圖來說：Power-law 是很難去分區的。傳統的圖劃分方法對於Power-law 圖來說，執行圖演算法會造成性能很差。比如書傳統的圖劃分方法：隨機劃分和edge-cut邊劃分。

3. PowerGraph Main Idea

PowerGraph中在計算時會切分高緯度點，被切分的點形成了一個新的抽象。但是在節點切分策略下要解決的一個問題是如何運行節點程序？在之前的邊切分策略下節點是單一的、完整的，節點擁有所有鄰居的信息，可以獨立完成節點程序的運算。但是在節點切分策略下，每個節點看到的只是部分的鄰居，無法完成整個計算。在節點切分策略下，分布在不同的CPU或者機器上的節點如何對其進行編程？下面將介紹兩種目前最具代表性的圖計算方法是如何對圖進行並行化抽象計算的。

4. Graph-Parallel Abstraction

圖並行化抽象目前流行的兩種方法是 ：

——使用Message-Passing Pregel

——使用Shared-Memory GraphLab

但對於我們前面提到的冪律圖，Pregel和GraphLab都不能很好地處理這種節點。最大的挑戰就是如何來處理這些高維度的點。最簡單也最低效的方法是順序處理這些邊，說白了就是遍歷所有點。第二種方法就是剛才提到的Pregel，它處理高緯度點的缺陷是單個worker要發送大量消息給鄰居節點。GraphLab的方法的缺點是會觸到圖的大部分（GraphLab）並且對於單台機器邊的元數據太大，GraphLab共享狀態是非同步執行，需要大量鎖 。Pregel同步執行但容易產生straggler，straggler可以理解為執行比較慢的節點（木桶的短板效應）。導致這些系統中存在這些問題主要原因是他們對圖的切分策略是採用邊分割的方式。下面我們來比較

一下邊劃分和點劃分的區別。下面對比了Pregel、GraphLab和PowerGraph在運行PageRank演算法上通信開銷和執行的時間，可以看出PowerGraph不僅通信開銷小而且運行時間短，對高緯度點有很強的健壯性。這時在人工合成的數據集上的一個性能。

5. Edge-Cut and Vertex-Cut

還有一種是點切分的方式，下面我們看下邊切分的方式和點切分方式有什麼不同， 我們現在要將一個有4個頂點的圖存儲到3台機器上，這三台機器分別叫1，2，3。那麼按照邊切分的方式，這且邊被切人後在3台機器的分布如右邊圖。 從圖中可以看出，切分的過程中，總共有AB,BC,CD三條邊被切開，保存到3台機器後，邊的總數目由原來的3條，變成了6條，多了一倍，外加5個節點副本。第二種方式是點切分方式，同樣是4個節點的圖，我們將B、C節點切分開來。存儲到3台機器後，得到右邊這個圖，可以看出我們的邊的數目還是3台，只多了兩個節點的副本。所以當邊的數量比節點數量大很多的情況下，這種兩種切分方式差異會更加明顯。

圖的切分問題又叫著圖分區。圖並行抽象的性能要依賴於圖的分區方式， 而我們的目標是

——最小化通信

——權衡圖計算和存儲開銷

而前面提到的兩種流行的圖處理框架GraphLab和Pregel採用的都是邊切分方式的隨機Hash分區策略這種策略只保證了節點均勻分布在整個集群中，邊被切分成雙份分散在整個集群中。對於一般圖來說，邊的數量是要遠大於點的數量，因此按邊分區會帶來存儲和計算上的不均衡。 論文中總結了這種邊切分方式帶來的影響，給出了一個公式用來求被切的邊除以總的邊的均值，p表示隨機被分的機器數目，當p等於10時有90%的邊被切分，當p等於100時，有99%的邊會被切。 可以看出，當我們集群規模越大，按照邊來切分方式進行分區是非常划不來的，圖中大部分邊會變切分開來。所以作者提出了PowerGraph：一種基於點劃分的分散式圖處理系統。

6. PowerGraph

這裡總結一下目前對於專門的圖處理框架GraphLab和Pregel是不適合處理這種natural graphs。主要的兩大挑戰是高緯度的點和低質量的分區策略。本文提出的PowerGraph即是為了解決這2個問題而設計的，其中Power的意思就是冪律分布的意思。

下面就來介紹PowerGraph的詳細設計細節，PowerGraph的主要貢獻或者說創新點可歸結為以下兩點：

第一，提出了GAS計算模型，將高維度的點進行並行化

第二是採用點切分策略，來保證整個集群的均衡性，該策略對大量密率圖分區是非常高效的。

6.1 GAS Decomposition

下面以PageRank為例，頂點程序的通用模板大致如圖所示，第一步收集鄰居節點信息，第二步更新節點權值，如果還沒有收斂，觸發節點鄰居再次運行頂點程序。 這是一種通用的處理模板 。

PowerGraph提出了自己的一套計算模型，叫GAS分解。G是Gather的意思，A是Apply的意思，S是Scatter的意思。GAS分解過程如下，

Gather：收集鄰居信息

先收集同一台機器的信息，然後對不同主機收集的信息進行匯總。得到最後的求和信息。

Apply：對中心點應用收集點的值，得到y一撇

Scatter（分散）：更新鄰居點和邊，並且激活鄰居頂點，觸發鄰居點進行下一輪迭代。

那麼就PowerGraph的GAP模型應用到RageRank演算法中，是什麼樣的過程？該公式中i表示目標節點，我們需要對這個節點求PageRank值，wij表示從j點到i點的權值，Gather階段，先求i所有鄰居節點的權值，用戶自定義一個sum操作，統計所有鄰居節點的權值之和。Apply階段更新i點的權值，利用上一階段的sum值加上一個偏置值，計算得到i的新的權值；Scatter階段如果i值被修改，就觸發相應的鄰居節點j重新計算。

下面用一個動畫演示PowerGraph是如何執行頂點程序。當頂點按點切分方式被分到4台機器之後，在多個節點上指派一個為Master,其餘的為Mirror。Mirror上可以運行Gather程序來收集所有鄰居的信息，並進行聚合計算(sum)後發送給Master。Master上的Gather程序收集這些結果，最終將這個結果應用到Apply程序上，得到新的節點狀態。然後通過Scatter程序將新的節點狀態廣播給各個Mirror，Mirror進而廣播給各個鄰居。

6.2 Constructing Vertex-Cuts

PowerGraph提出了一種均衡圖劃分方案，在減少計算中通信量的同時保證負載均衡。實際上通信開銷是和節點所跨的機器數目成線性關係，但點切分的方式可以最小化每個頂點所跨的機器數目。PowerGraph使用的不是邊切分，邊切分前面已經提到會同步大量的邊的信息。而是採用點切分，點切分只要同步一個點的節點信息。

論文中給出了一個新的理論（定理）：對於任何邊切分我們都可以直接構造一個點切分，能夠嚴格減少通信和存儲開銷。下面將介紹該論文是如何來構造這個點分割。

論文提出了3種分配方式

隨機邊分配

貪婪協同邊分配

非貪婪邊分配（Oblivious遺忘）

6.2.1 隨機的邊分配策略

第一種策略是隨機的邊放置策略，按照點切分的方式，隨機放置邊 。

下面分析邊這種隨機邊放置策略的性能 這裡數據集選用的是Twitter數據集，有410w個頂點，14億條邊 。橫坐標是實際集群中機器的數目，縱坐標表示1個頂點期望跨了機器數目，關於這兩者的數量關係公式，作者在論文中給出了一個定理。藍色的線表示表示理論推測期望值，紅線是實際隨機邊放置的曲線圖。可以看出期望值和理論值之間基本是能夠match上的。所以針對隨即邊放置策略，就可以做到精確的估計內存和通信開銷。

6.2.2 貪婪的點切分策略

第二種是貪婪的點切分方式，由於隨機切分下，儘管各個子圖基本均衡，但是子圖內部聯通性很差。因此PowerGraph提出的啟發式的貪婪演算法，基本原理如下：

如果新加進來的邊，它的某個節點已經存在於某台機器上，就將該邊分到對應的機器上，比如在1號機器上已經存在AB這條邊，2號機器上已經存在BC這條邊，那門當一條新的邊AD在要加進來時，發現A節點已經在1號機器上，所以就將該邊放置到1號機器上。如果再來一條邊BE，發向兩台機器上都存有B節點，這時候貪婪策略會選擇機器中分配的邊最少的機器進行分配。所以會將BE分配到2號機器，這裡只是簡單的舉了個例子，論文中是用集合的表示方式將這種貪婪策略歸納了4種case，這裡不詳細介紹，具體可以參考論文第8頁相關內容。 上面提到的貪婪策略，作者論文中稱之為De-randomiztion。de的含義這裡因該是去除，與隨機化剛好是反義詞。De-randomization就是Greedy的含義，貪婪點切分能夠最小化機器所跨的機器數目。實際的貪婪的放置策略性能要比隨即放置策略要好。關於貪婪邊切分策略，作者給出了兩種實現方式：

第一種是協同邊放置策略，這需要維護一張全局u頂點放置的歷史紀錄表，在執行貪心切分之前都要去查詢這張表，在執行的過程中需要更新這張表。協同點切分的策略，它的特點是慢但點切分的質量高 ，

第二種方式是Oblivious的貪婪策略，它是一種近似的貪婪策略，不需要做全局的協同。貪婪演算法的運行不依賴每一台機器，不需要維護全局的記錄表，而是每台機器自己維護這張表，不需要做機器間的通信。這種策略速度快，但切分質量比較低。關於這種方式，論文只用了一段話來描述，具體如何操作明白。

6.2.3 對比三種分區策略的性能

下面是對比這三種分區策略的性能，對比的是平均的機器跨度和構建時間。

協同的貪婪分區演算法平局機器跨度最小，但構建時間最長。而隨機策略構建時間短，但平局的機器跨度最大。而Oblivious的貪婪分區策略能夠在平局機器跨度和構建時間上獲得一個折中的性能。

7. System Desgin

整個PowerGraph的架構是這樣一個結構，最上層是PowerGraph 系統，它和GraphLab集成到一起，實現的介面是C++，利用HDFS進行數據的輸入和輸出，利用檢查點來實現容錯。

在這個系統上實現了許多經典演算法，比如：

Alternating Least Squares 交替最小二乘法

Stochastic Gradient Descent隨機梯度下降

SVD（Singular Value Decomposition）奇異值分解

Statistical Inference統計推斷

Loopy Belief Propagation（LBP）循環信度傳播演算法

Gibbs Sampling吉布斯採樣

Image stitching圖像拼接

LDA（Latent Dirichlet Allocation）隱含狄利克雷分布文檔主題生成模型

下面對比了Pregel、GraphLab和PowerGraph在運行PageRank演算法上通信開銷和執行的時間，可以看出PowerGraph不僅通信開銷小而且運行時間短，對高緯度點有很強的健壯性。這時在人工合成的數據集上的一個性能。

7. Summary

推薦閱讀：