圖數據庫之Pregel

/* .*/ author:張俊林 節選自《大數據日知錄：架構與算法》十四章，書籍目錄在此 Pregel是Google提出的大規模分布式圖計算平臺，專門用來解決網頁鏈接分析、社交數據挖掘等實際應用中涉及的大規模分布式圖計算問題。 1．計算模型 Pregel在概念模型上遵循BSP

/* .*/
author: 張俊林

節選自《大數據日知錄：架構與算法》十四章，書籍目錄在此

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

1．計算模型

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

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

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

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

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

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

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

2．系統架構

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

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

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

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

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

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

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

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

3．Pregel應用

本節通過若干常見的圖計算應用，來說明Pregel框架下如何構造具體的應用程序。

（1）PageRank計算

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

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

（2）單源最短路徑

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

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

（3）二部圖最大匹配

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

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

算法運行經過以下四個階段。

階段一：對于二部圖中左端尚未匹配的節點，向其鄰接節點發出消息，要求進行匹配，之后轉入非活躍狀態。

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

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

階段四：右端尚未匹配的節點至多選擇一個階段三發過來的請求，然后寫入匹配節點ID以表明已經匹配。

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

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com