/*?版權(quán)聲明：可以任意轉(zhuǎn)載，轉(zhuǎn)載時請務必標明文章原始出處和作者信息?.*/
??????????? author:?張俊林? ? ? ? ? ? ? ? ? ??

節(jié)選自《大數(shù)據(jù)日知錄：架構(gòu)與算法》十四章，書籍目錄在此

?? Pregel是Google提出的大規(guī)模分布式圖計算平臺，專門用來解決網(wǎng)頁鏈接分析、社交數(shù)據(jù)挖掘等實際應用中涉及的大規(guī)模分布式圖計算問題。

1．計算模型

??? Pregel在概念模型上遵循BSP模型，整個計算過程由若干順序執(zhí)行的超級步（Super Step）組成，系統(tǒng)從一個“超級步”邁向下一個“超級步”，直到達到算法的終止條件（見圖14-13）。

??? Pregel在編程模型上遵循以圖節(jié)點為中心的模式，在超級步S中，每個圖節(jié)點可以匯總從超級步S-1中其他節(jié)點傳遞過來的消息，改變圖節(jié)點自身的狀態(tài)，并向其他節(jié)點發(fā)送消息，這些消息經(jīng)過同步后，會在超級步S+1中被其他節(jié)點接收并做出處理。用戶只需要自定義一個針對圖節(jié)點的計算函數(shù)F(vertex)，用來實現(xiàn)上述的圖節(jié)點計算功能，至于其他的任務，比如任務分配、任務管理、系統(tǒng)容錯等都交由Pregel系統(tǒng)來實現(xiàn)。

典型的Pregel計算由圖信息輸入、圖初始化操作，以及由全局同步點分割開的連續(xù)執(zhí)行的超級步組成，最后可將計算結(jié)果進行輸出。

?????? 每個節(jié)點有兩種狀態(tài)：活躍與不活躍，剛開始計算的時候，每個節(jié)點都處于活躍狀態(tài)，隨著計算的進行，某些節(jié)點完成計算任務轉(zhuǎn)為不活躍狀態(tài)，如果處于不活躍狀態(tài)的節(jié)點接收到新的消息，則再次轉(zhuǎn)為活躍，如果圖中所有的節(jié)點都處于不活躍狀態(tài)，則計算任務完成，Pregel輸出計算結(jié)果。

??? 下面以一個具體的計算任務來作為Pregel圖計算模型的實例進行介紹，這個任務要求將圖中節(jié)點的最大值傳播給圖中所有的其他節(jié)點，圖14-14是其示意圖，圖中的實線箭頭表明了圖的鏈接關(guān)系，而圖中節(jié)點內(nèi)的數(shù)值代表了節(jié)點的當前數(shù)值，圖中虛線代表了不同超級步之間的消息傳遞關(guān)系，同時，帶有斜紋標記的圖節(jié)點是不活躍節(jié)點。

??

???? 從圖中可以看出，數(shù)值6是圖中的最大值，在第0步超級步中，所有的節(jié)點都是活躍的，系統(tǒng)執(zhí)行用戶函數(shù)F(vertex)：節(jié)點將自身的數(shù)值通過鏈接關(guān)系傳播出去，接收到消息的節(jié)點選擇其中的最大值，并和自身的數(shù)值進行比較，如果比自身的數(shù)值大，則更新為新的數(shù)值，如果不比自身的數(shù)值大，則轉(zhuǎn)為不活躍狀態(tài)。

???? 在第0個超級步中，每個節(jié)點都將自身的數(shù)值通過鏈接傳播出去，系統(tǒng)進入第1個超級步，執(zhí)行F(vertex)函數(shù)，第一行和第四行的節(jié)點因為接收到了比自身數(shù)值大的數(shù)值，所以更新為新的數(shù)值6。第二行和第三行的節(jié)點沒有接收到比自身數(shù)值大的數(shù)，所以轉(zhuǎn)為不活躍狀態(tài)。在執(zhí)行完函數(shù)后，處于活躍狀態(tài)的節(jié)點再次發(fā)出消息，系統(tǒng)進入第2個超級步，第二行節(jié)點本來處于不活躍狀態(tài)，因為接收到新消息，所以更新數(shù)值到6，重新處于活躍狀態(tài)，而其他節(jié)點都進入了不活躍狀態(tài)。Pregel進入第3個超級步，所有的節(jié)點處于不活躍狀態(tài)，所以計算任務結(jié)束，這樣就完成了整個任務，最大數(shù)值通過4個超級步傳遞給圖中所有其他的節(jié)點。算法14.1是體現(xiàn)這一過程的Pregel C++代碼。

2．系統(tǒng)架構(gòu)

??? Pregel采用了“主從結(jié)構(gòu)”來實現(xiàn)整體功能，圖14-15是其架構(gòu)圖，其中一臺服務器充當“主控服務器”，負責整個圖結(jié)構(gòu)的任務切分，采用“切邊法”將其切割成子圖（Hash(ID)=ID mod n ，n是工作服務器個數(shù)），并把任務分配給眾多的“工作服務器”，“主控服務器”命令“工作服務器”進行每一個超級步的計算，并進行障礙點同步和收集計算結(jié)果。“主控服務器”只進行系統(tǒng)管理工作，不負責具體的圖計算。

??? 每臺“工作服務器”負責維護分配給自己的子圖節(jié)點和邊的狀態(tài)信息，在運算的最初階段，將所有的圖節(jié)點狀態(tài)置為活躍狀態(tài)，對于目前處于活躍狀態(tài)的節(jié)點依次調(diào)用用戶定義函數(shù)F(Vertex)。需要說明的是，所有的數(shù)據(jù)都是加載到內(nèi)存進行計算的。除此之外，“工作服務器”還管理本機子圖和其他“工作服務器”所維護子圖之間的通信工作。

??

??? 在后續(xù)的計算過程中，“主控服務器”通過命令通知“工作服務器”開始一輪超級步的運算，“工作服務器”依次對活躍節(jié)點調(diào)用F（Vertex），當所有的活躍節(jié)點運算完畢，“工作服務器”通知“主控服務器”本輪計算結(jié)束后剩余的活躍節(jié)點數(shù)，直到所有的圖節(jié)點都處于非活躍狀態(tài)為止，計算到此結(jié)束。

??? Pregel采用“檢查點”（CheckPoint）作為其容錯機制。在超級步開始前，“主控服務器”可以命令“工作服務器”將其負責的數(shù)據(jù)分片內(nèi)容寫入存儲點，內(nèi)容包括節(jié)點值、邊值以及節(jié)點對應的消息。

??? “主控服務器”通過心跳監(jiān)測的方式監(jiān)控“工作服務器”的狀態(tài)，當某臺“工作服務器”發(fā)生故障時，“主控服務器”將其負責的對應數(shù)據(jù)分片重新分配給其他“工作服務器”，接收重新計算任務的“工作服務器”從存儲點讀出對應數(shù)據(jù)分片的最近“檢查點”以恢復工作，“檢查點”所處的超級步可能比現(xiàn)在系統(tǒng)所處的超級步慢若干步，此時，所有的“工作服務器”回退到與“檢查點”一致的超級步重新開始計算。

???? 從上述描述可以看出，Pregel是一個消息驅(qū)動的、遵循以圖節(jié)點為中心的編程模型的同步圖計算框架。考慮到“主控服務器”的功能獨特性和物理唯一性，很明顯，Pregel存在單點失效的可能。

??? 請思考：在容錯周期選擇方面，每一輪超級步都可以進行一次，也可以選擇相隔若干超級步進行一次，那么這兩種做法各自有何優(yōu)缺點？

??? 解答：如果選擇較短周期的容錯措施，在完成任務的過程中，需要的額外開銷會較多，但是好處在于如果機器發(fā)生故障，整個系統(tǒng)回退歷史較近，有利于任務盡快完成；較長周期的容錯措施正好相反，因為頻次低，所以平常開銷小，但是如果機器發(fā)生故障，則需要回退較多的超級步，導致拉長任務的執(zhí)行過程。所以這里也有一個總體的權(quán)衡。

3．Pregel應用

??? 本節(jié)通過若干常見的圖計算應用，來說明Pregel框架下如何構(gòu)造具體的應用程序。

（1）PageRank計算

?? PageRank是搜索引擎排序中重要的參考因子，其基本思路和計算原理在本章前面有所說明，此處不再贅述。下面是利用Pregel進行PageRank計算的C++示例代碼。

???? Compute()函數(shù)即為前面介紹的針對S超級步中圖節(jié)點的計算函數(shù)F（Vertex），用戶通過繼承接口類Vertex并改寫Compute(MessageIterator* msgs)接口函數(shù)，即可快速完成應用開發(fā)，其中MessageIterator* msgs是S-1超級步傳遞給當前節(jié)點的消息隊列。該計算函數(shù)首先累加消息隊列中傳遞給當前節(jié)點的部分PageRank得分，之后根據(jù)計算公式得到圖節(jié)點當前的PageRank得分，如果當前超級步未達循環(huán)終止條件30次，則繼續(xù)將新的PageRank值通過邊傳遞給鄰接節(jié)點，否則發(fā)出結(jié)束通知，使得當前節(jié)點轉(zhuǎn)為不活躍狀態(tài)。

（2）單源最短路徑

??? 在圖中節(jié)點間查找最短的路徑是非常常見的圖算法。所謂“單源最短路徑”，就是指給定初始節(jié)點StartV，計算圖中其他任意節(jié)點到該節(jié)點的最短距離。下面是如何在Pregel平臺下計算圖節(jié)點的單源最短路徑的C++代碼示例。

??? 從代碼中可看出，某個圖節(jié)點v從之前的超級步中接收到的消息隊列中查找目前看到的最短路徑，如果這個值比節(jié)點v當前獲得的最短路徑小，說明找到更短的路徑，則更新節(jié)點數(shù)值為新的最短路徑，之后將新值通過鄰接節(jié)點傳播出去，否則將當前節(jié)點轉(zhuǎn)換為不活躍狀態(tài)。在計算完成后，如果某個節(jié)點的最短路徑仍然標為INF，說明這個節(jié)點到源節(jié)點之間不存在可達通路。

（3）二部圖最大匹配

?? 二部圖最大匹配也是經(jīng)典的圖計算問題，下面給出Pregel利用隨機匹配思想解決該問題的一個思路。

上面的Pregel程序采用隨機匹配的方式來解決二部圖最大匹配問題，每個圖節(jié)點維護一個二元組：（'L/R'，匹配節(jié)點ID），'L/R'指明節(jié)點是二部圖中的左端節(jié)點還是右端節(jié)點，以此作為身份識別標記。二元組的另一維記載匹配上的節(jié)點ID。

算法運行經(jīng)過以下四個階段。

?? 階段一：對于二部圖中左端尚未匹配的節(jié)點，向其鄰接節(jié)點發(fā)出消息，要求進行匹配，之后轉(zhuǎn)入非活躍狀態(tài)。

?? 階段二：對于二部圖中右端尚未匹配的節(jié)點，從接收到的請求匹配消息中隨機選擇一個接收，并向接收請求的左端節(jié)點發(fā)出確認信息，之后主動轉(zhuǎn)入非活躍狀態(tài)。

?? 階段三：左端尚未匹配的節(jié)點接收到確認信息后，從中選擇一個節(jié)點接收，寫入匹配節(jié)點ID以表明已經(jīng)匹配，然后向右端對應的節(jié)點發(fā)送接收請求的消息。左端節(jié)點已經(jīng)匹配的節(jié)點在本階段不會有任何動作，因為這類節(jié)點在第一階段中根本就沒有發(fā)送任何消息。

?? 階段四：右端尚未匹配的節(jié)點至多選擇一個階段三發(fā)過來的請求，然后寫入匹配節(jié)點ID以表明已經(jīng)匹配。

通過上述類似于兩次握手的四個階段的不斷迭代，即可獲得一個二部圖最大匹配結(jié)果。

總結(jié)

以上是生活随笔為你收集整理的图数据库之Pregel的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。