??Pregel是Google提出的大規(guī)模分布式圖計算平臺，專門用來解決網(wǎng)頁鏈接分析倒彰、社交數(shù)據(jù)挖掘等實際應(yīng)用中涉及的大規(guī)模分布式圖計算問題待讳。目前的圖計算模型基本上都遵循BSP計算模式。在詳細(xì)介紹Pregel模型之前痴晦，我們先簡單了解一下BSP模式的相關(guān)概念誊酌。

1. BSP模式

??BSP(Bulk Synchronous Parallel露乏，整體同步并行)是一種并行計算模式瘟仿，由英國計算機(jī)科學(xué)家Viliant在上世紀(jì)80年代提出。BSP計算模式入下圖所示驹止。

BSP模型

BSP計算模式中以下幾個概念需要了解一下：

1. Processors：并行計算進(jìn)程幢哨，它對應(yīng)到集群中的多個結(jié)點，每個結(jié)點可以有多個Processor闸与；
2. LocalComputation：單個Processor的計算岸售，每個Processor都會切分一些結(jié)點作計算凸丸；
3. Communication：Processor之間的通信。接觸的圖計算往往需要做些遞歸或是使用全局變量咽块，在BSP模型中腻惠，對圖結(jié)點的訪問分布到了不同的Processor中集灌，并且往往哪怕是關(guān)系緊密具有局部聚類特點的結(jié)點也未必會分布到同個Processor或同一個集群結(jié)點上，所有需要用到的數(shù)據(jù)都需要通過Processor之間的消息傳遞來實現(xiàn)同步腌零；
4. BarrierSynchronization：柵欄同步益涧。每一次同步也是一個超步的完成和下一個超步的開始驯鳖；
5. Superstep：超步，這是BSP的一次計算迭代嘹裂，拿圖的廣度優(yōu)先遍歷來舉例寄狼，從起始結(jié)點每往前步進(jìn)一層對應(yīng)一個超步。
6. 任務(wù)結(jié)束伊磺，一個作業(yè)可以選出一個Proceessor作為Master删咱，每個Processor每完成一個Superstep都向Master反饋完成情況痰滋，Master在N個Superstep之后發(fā)現(xiàn)所有Processor都沒有計算可做了，便通知所有Processor結(jié)束并退出任務(wù)团搞。

2. Pregel模型

??在BSP模式的基礎(chǔ)上逻恐，我們詳細(xì)解釋一下Pregel模型的原理峻黍。Pregel在概念模型上遵循BSP模式姆涩。整個計算過程由若干順序運行的超級步（Super Step）組成，系統(tǒng)從一個“超級步”邁向下一個“超級步”轻局，直到達(dá)到算法的終止條件样刷。一個典型的Pregel計算過程如下：

• 讀取圖數(shù)據(jù)并對圖初始化置鼻；
• 當(dāng)圖被初始化完畢蜓竹，執(zhí)行一系列的超步（SuperStep）直到整個計算結(jié)束俱济，這些SuperStep之間通過一些全局的同步點分隔;
• 輸出計算結(jié)果。

??在每個SuperStep中聂喇，頂點上的計算都是并行的希太，每個頂點執(zhí)行相同的用于表達(dá)指定邏輯的用戶自定義函數(shù)。每個頂點都可以需修改自身以及出邊的狀態(tài)矾湃，接收前一個SuperStep發(fā)送給它的消息堕澄，并將計算的結(jié)果或信息發(fā)送給其他頂點蛙紫，這些信息會在下一個SuperStep中被目標(biāo)頂點接收。邊在這種計算模式中并不是核心對象丽涩，只用于表明消息傳遞的方向矢渊，沒有相應(yīng)的計算運行在其上枉证。詳細(xì)過程可以參考下圖，顯示了兩個SuperStep之間的內(nèi)容毡鉴。

SuperStep

2.1 Pregel模型狀態(tài)機(jī)

??算法結(jié)束的時機(jī)取決于所有的頂點是否均已經(jīng)達(dá)到halt狀態(tài)猪瞬。首先在剛開始的時候陈瘦，所有的頂點都處于active狀態(tài)潮售，所有的active頂點都會參與到SuperStep中的相應(yīng)計算酥诽。頂點通過將其自身的status設(shè)置成inactive來表示它已不再active，以此表明在下一次的SuperStep中咖驮，該頂點不再需要執(zhí)行相應(yīng)的計算。除非該頂點接收到其他頂點傳送的消息饰抒，否則Pregel框架不會再接下來的SuperStep中執(zhí)行該頂點的計算袋坑。如果頂點在接收到消息后進(jìn)入active狀態(tài)眯勾，那么在隨后的計算中該頂點必須顯式的deactive吃环。整個計算在所有頂點都達(dá)到inactive狀態(tài)，并且沒有消息傳送時結(jié)束翅娶。整個狀態(tài)轉(zhuǎn)換如下圖所示好唯。

image.png

2.2 Pregel模型示例

??接下來展示一個以Pregel計算最大值的例子骑篙。假設(shè)圖中存在A/B/C/D四個頂點靶端，其中每個頂點的數(shù)據(jù)表示當(dāng)前頂點的值。在計算的每個SuperStep中）脏榆，每個頂點將接收其他頂點傳過來的值（初始SuperStep除外）姐霍，并判斷當(dāng)前頂點的值是否小于傳遞過來的值典唇。若小于介衔，更新當(dāng)前頂點的值骂因，并將該頂點狀態(tài)設(shè)置為active狀態(tài)，同時將當(dāng)前頂點的最新值傳遞出去乘盼；若不小于绸栅，則什么都不做，并將當(dāng)前頂點的狀態(tài)設(shè)置為inactive蓖柔。直到所有的頂點狀態(tài)均變成inactive况鸣，計算結(jié)束竹观。整個過程入下圖所示。

image.png

以上圖為例，我們詳細(xì)介紹一下Pregel模型的執(zhí)行過程速址。

• SuperStep0：初始SuperStep芍锚，不接收信息，只負(fù)責(zé)將當(dāng)前頂點的值傳遞出去默刚，并設(shè)置所有頂點狀態(tài)為active荤西。
• SuperStep1: 頂點A接收的信息為6伍俘，將當(dāng)前頂點的值設(shè)置為6癌瘾，狀態(tài)設(shè)置為active，并將6作為消息發(fā)送給頂點B（頂點B下一輪迭代的時候會收到妇萄，當(dāng)前輪次并不會收到）冠句；頂點B接收的信息為3和2，均小于當(dāng)前頂點值6放典，不更新當(dāng)前頂點值基茵，并將頂點的狀態(tài)設(shè)置為inactive拱层；頂點C接收的信息為1，小于當(dāng)前頂點值2径缅，不更新當(dāng)前頂點值纳猪，并將頂點的狀態(tài)設(shè)置為inactive桃笙；頂點D接收信息為2和6搏明，將當(dāng)前頂點的值更新為6，狀態(tài)設(shè)置為active购笆，并將6作為消息發(fā)送給頂點C虚循；
• SuperStep2:頂點A未接收到信息横缔，且狀態(tài)為inactive，什么都不做娃循；頂點B接收到頂點A上一個輪次發(fā)送的消息捌斧，由于當(dāng)前頂點值為6泉沾，不小于接收到的消息6跷究，因此不更新當(dāng)前頂點值，并將頂點的狀態(tài)設(shè)置為inactive丁存；頂點C接收到的消息為6解寝，當(dāng)前頂點值為2艘儒，將當(dāng)前頂點的值更新為6界睁，狀態(tài)設(shè)置為active翻斟，并將6作為消息發(fā)送給頂點B和D；頂點D未接收到信息敞斋，且狀態(tài)為inactive疾牲，什么都不做阳柔；
• SuperStep3:頂點A未接收到信息，且狀態(tài)為inactive济锄，什么都不做荐绝；頂點B接收到頂點C上一個輪次發(fā)送的消息避消，由于當(dāng)前頂點值為6，不小于接收到的消息6监憎，因此不更新當(dāng)前頂點值婶溯，并將頂點的狀態(tài)設(shè)置為inactive迄委；頂點C未接收到任何信息，因此將狀態(tài)設(shè)置為inactive渔扎；頂點D接收到頂點C上一個輪次發(fā)送的消息赞警，由于當(dāng)前頂點值為6虏两，不小于接收到的消息6定罢，因此不更新當(dāng)前頂點值祖凫，并將頂點的狀態(tài)設(shè)置為inactive；
• 所有頂點的狀態(tài)均為inactive遭庶，迭代停止稠屠，輸出結(jié)果权埠。

??以上就是圖計算模型Pregel的全部內(nèi)容攘蔽，以后有時間還會再詳細(xì)介紹其他幾種常見的圖計算模型，如GAS转捕。具體實現(xiàn)可以參見Flink Gelly提供的迭代計算模式瓜富。

2.3 Pregel框架的缺點

??Pregel模型雖然簡單降盹，那就是對于鄰居數(shù)很多的頂點蓄坏，它需要處理的消息非常龐大，所以對于符合冪律分布的自然圖结蟋，對于那些關(guān)聯(lián)關(guān)系非常多的頂點嵌屎，這種模型在計算的時候很容易崩潰恍涂。