Google圖算法引擎Pregel介紹
【前言：有一種說法[1]是Google的程序里面80%用的是MapReduce，20%用的是Pregel。今天就來介紹一下這個Pregel。想要深入研究的同志們，可以參考最新的SIGMOD 2010 ppt[2]。】
簡介
Pregel是一個用于分布式圖計算的計算框架，主要用于圖遍歷（BFS）、最短路徑（SSSP）、PageRank計算等等。共享內存的運行庫有很多，但是對于google來說，一臺機器早已經放不下需要計算的數據了，所以需要分布式的這樣一個計算環境。沒有Pregel之前，你可以選擇用 MapReduce來做，但是效率很低；你也可以用已有的并行圖算法庫Parallel BGL或者CGMgraph來做，但是這兩者又沒有容錯。所以google就自己開發了這個新的計算框架。
（八卦一下：Pregel的名字來歷很有意思。是為了紀念歐拉的七橋問題[7]，七座橋就位于Pregel這條河上。）
核心概念
從高層次看，Pregel是BSP[8]模型，就是“計算”-“通信”-“同步”的模式，參看圖1。
- 輸入輸出為有向圖
- 分成超步
- 以節點為中心計算，超步內每個節點執行自己的任務，執行節點的順序不確定
- 兩個超步之間是通信階段
圖1: BSP Model
在Pregel中，以節點為中心計算。Step 0時每節點都活動著，每個節點主動“給停止投票”進入不活動狀態。如果接收到消息，則激活。沒有活動節點和消息時，整個算法結束。
圖2: Vetex State Machine（參考2）
容錯是通過檢查點來做的。在每個超步開始的時候，對主從節點分別備份。
核心的概念就是這些，其他還有一些消息聚集(combiner)等優化。有興趣可以看看Lixiang的閱讀筆記[6]和Pregel Slides[2]。
類似開源實現
人人都喜歡免費。跟Pregel最像的是Hama[5]，也是基于BSP，但是，開源的Hama還未成氣候。筆者原來打算拿它來做些實驗，結果還不能運行。
國內似乎還沒有類似Pregel的計算引擎，不知道百度和淘寶這些公司有沒有需求。淘寶最近9月份開源了他們的文件系統TFS[3][4]，很敬仰。不知道上面的運行環境是不是在開發中。大宋的開源軟件也要有自己的創新，不能老是拿老外的改改就用了。
參考資料
1. Pregel: Google’s other data-processing infrastructure, http://www.royans.net/arch/pregel-googles-other-data-processing-infrastructure/
2. Pregel: A System for Large-Scale Graph Processing, SIGMOD 2010的ppt, http://www.slideshare.net/shatteredNirvana/pregel-a-system-for-largescale-graph-processing
3. 淘寶文件系統TFS開源代碼，http://code.taobao.org/project/view/366/
4. 淘寶文件系統TFS介紹，http://rdc.taobao.com/blog/cs/?p=128
5. Hama homepage, http://incubator.apache.org/hama/
6. 論文閱讀筆記：Google的圖模型分布式計算框架Pregel
7. Seven Bridges of Königsberg, http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
8. http://en.wikipedia.org/wiki/Bulk_synchronous_parallel
轉自：http://www.tektalk.org/2010/12/03/google%E5%9B%BE%E7%AE%97%E6%B3%95%E5%BC%95%E6%93%8Epregel%E4%BB%8B%E7%BB%8D/