這篇文章主要是對(duì)Pregel論文的翻譯，還可能夾雜一點(diǎn)自己的思考。需要注意的是，本文只是在看Pregel論文的時(shí)的記錄并不是全文翻譯，所以你應(yīng)該僅以此作參考。文章中Vertex被翻譯為頂點(diǎn)，節(jié)點(diǎn)(Pregel說法為Worker)則表示分布式系統(tǒng)中的執(zhí)行機(jī)。
1.?介紹
現(xiàn)在很多都要求對(duì)大規(guī)模圖數(shù)據(jù)的處理，諸如網(wǎng)頁圖和社交網(wǎng)絡(luò)圖，那么如何高效地在圖上做計(jì)算就變成了一個(gè)大的挑戰(zhàn)，在此背景下，Pregel出世。圖上的算法常見的如最短路徑、PageRank等變種算法。在圖處理中還有一些其他的挑戰(zhàn)如圖的最小切分問題，關(guān)聯(lián)組件問題(譯者注：應(yīng)該是指分布式環(huán)境下節(jié)點(diǎn)通信的花銷問題。)
圖上的算法經(jīng)常面臨的問題就是內(nèi)存訪問有很差的局部性，每個(gè)頂點(diǎn)所做的工作又相當(dāng)之少。在分布式環(huán)境下，局部性會(huì)更加惡化，每個(gè)計(jì)算節(jié)點(diǎn)面臨更高的宕機(jī)風(fēng)險(xiǎn)。盡管現(xiàn)在大圖無處不在而且商用價(jià)值很高，但我們發(fā)現(xiàn)市面上沒有任何可擴(kuò)展的通用的分布式系統(tǒng)可運(yùn)行任何圖計(jì)算算法。(譯者注：google發(fā)布這篇論文已經(jīng)是2010的事了，前面這句話對(duì)于現(xiàn)在已經(jīng)不適用了。)
Pregel是一個(gè)可擴(kuò)展、具有容錯(cuò)并且提供了可以靈活表示各種圖算法的AP的分布式系統(tǒng)I。Pregel受BSP模型的啟發(fā)，也有超級(jí)步的概念，每個(gè)超級(jí)步內(nèi)部對(duì)每個(gè)頂點(diǎn)執(zhí)行用戶定義的函數(shù)。關(guān)于BSP模型，這里不做介紹，請(qǐng)自行了解。通過每個(gè)頂點(diǎn)的出邊發(fā)送其消息到鄰接頂點(diǎn)。
BSP模型的大同步概念使得我們無需花費(fèi)精力去考慮每一個(gè)超級(jí)步內(nèi)頂點(diǎn)的執(zhí)行順序問題，對(duì)于其上的算法實(shí)現(xiàn)也能更容易推倒其語義(semantics)。正因?yàn)槿绱?，Pregel也無需考慮加鎖和數(shù)據(jù)競(jìng)爭(zhēng)等問題。在設(shè)計(jì)原則上，Pregel和異步模型比也應(yīng)當(dāng)具有競(jìng)爭(zhēng)力。?
2.?計(jì)算模型
Pregel的圖數(shù)據(jù)：
? ? 1.Pregel的輸入是有向圖，每個(gè)頂點(diǎn)有一個(gè)唯一的string類型的標(biāo)識(shí)符和用戶定義的可更改的值；
? ? 2.每條邊連接其源頂點(diǎn)和目標(biāo)頂點(diǎn)，每條邊有用戶定義的可更改的值；
Pregel的計(jì)算模型包含
? ? 1.圖的輸入；
? ? 2.當(dāng)圖的初始化完成后，則是一系列由同步點(diǎn)劃分的超級(jí)步，直至算法停止；
? ? 3.輸出；
在每個(gè)超級(jí)步內(nèi)，那些頂點(diǎn)并行執(zhí)行相同的由用戶定義的函數(shù)，而這些函數(shù)代表給定算法的邏輯拓?fù)?。一個(gè)頂點(diǎn)可以更改其值和其出邊的值，可以接收上一個(gè)超級(jí)步發(fā)送給它的消息，也可以發(fā)送消息給其他頂點(diǎn)（會(huì)在下一個(gè)超級(jí)步被接收），甚至可以轉(zhuǎn)換圖的拓?fù)?。在此模型中，邊并非是最被關(guān)心的（first-class citizens），邊沒有相關(guān)的算法。
在每個(gè)超級(jí)步內(nèi)，活躍狀態(tài)的頂點(diǎn)都會(huì)參與計(jì)算；
頂點(diǎn)在一個(gè)超級(jí)步中voting to halt使其自己變?yōu)榉腔钴S狀態(tài)，除非有外力激活，否則非活躍頂點(diǎn)不會(huì)再有任何動(dòng)作。在后面的超級(jí)步中也不會(huì)處理這個(gè)頂點(diǎn)，除非頂點(diǎn)收到消息。如果頂點(diǎn)被消息重新激活，那么它需要顯示地再次讓自己變?yōu)榉腔钴S態(tài)；
算法的結(jié)束條件是每個(gè)頂點(diǎn)都voting to halt，從活躍狀態(tài)變?yōu)榉腔钴S狀態(tài)，并且沒有消息再需傳送；
下圖是一個(gè)簡(jiǎn)單的例子，說明Pregel框架中頂點(diǎn)的狀態(tài)機(jī)變遷。
此例子中，每個(gè)頂點(diǎn)的起始狀態(tài)都為活躍狀態(tài)，然后在超級(jí)步0中每個(gè)頂點(diǎn)執(zhí)行相同的操作：通過出邊向其鄰接頂點(diǎn)發(fā)送消息。消息中攜帶的是自己的頂點(diǎn)值。為了便于說明，將四個(gè)頂點(diǎn)從左到右命名為a、b、c、d。
然后在超級(jí)步1中，b頂點(diǎn)接收到來自a和c的消息。經(jīng)過比較，b頂點(diǎn)自身的值最大，那么b頂點(diǎn)不會(huì)做改變，于是b頂點(diǎn)自己主動(dòng)voting to halt讓自己變?yōu)榉腔钴S態(tài)，下圖以陰影表示。c頂點(diǎn)接收到d頂點(diǎn)的消息，無更改，則讓自己變?yōu)榉腔钴S狀態(tài)。在超級(jí)步1內(nèi)，這兩個(gè)變?yōu)榉腔钴S態(tài)的頂點(diǎn)不會(huì)再發(fā)送消息。知道最后所有頂點(diǎn)都變?yōu)榉腔钴S態(tài)，算法結(jié)束。
Pregel選用BSP模型即消息傳遞模型而不是遠(yuǎn)程讀(remote reads)或者其他共享內(nèi)存的方法(譯者注：這里的意思是Pregel為什么用消息推送而不是去拉取消息模型)，基于以下兩個(gè)原因：
? ? 1.消息推送模型足夠高效地代表圖模型，沒有遠(yuǎn)程讀的必要；
? ? 2.消息推送模型性能更好
在一個(gè)集群中，遠(yuǎn)程讀延時(shí)太高。在消息推送中，我們可以用分批次的異步發(fā)送消息而解決這個(gè)問題。
在Pregel中，頂點(diǎn)和其邊都存在一個(gè)機(jī)器上，那么網(wǎng)絡(luò)傳輸?shù)膬?nèi)容就僅僅是消息，而不會(huì)再有頂點(diǎn)的狀態(tài)或者邊的信息等等。Pregel用BSP模型讓這一切變得不再復(fù)雜。
3. C++ API
上面這幅圖就是系統(tǒng)提供的API。這是一個(gè)模板類，編寫Pregel程序時(shí)需要引入此作為基類。用戶需要覆蓋其Compute()函數(shù)，定義好的Vertex方法允許Compute()獲取其頂點(diǎn)和邊的值，發(fā)送消息?？梢垣@取鄰接頂點(diǎn)的值通過GetValue()，可以通過MultableValue()更改其值。通過迭代器訪問和修改邊的值。類模板的參數(shù)都是可定制的，比如用PB。
3.1 消息傳遞
每個(gè)頂點(diǎn)通過傳送消息直接和其他頂點(diǎn)通信，消息包含消息內(nèi)容和目標(biāo)頂點(diǎn)。消息的格式用戶自定義。
每個(gè)頂點(diǎn)可以發(fā)送任意數(shù)量的消息。每個(gè)頂點(diǎn)通過迭代器訪問其接收的所有消息，在此，保證消息不會(huì)重復(fù)但不保證消息的順序。頂點(diǎn)可以通過鄰接頂點(diǎn)而獲知其非鄰接點(diǎn)的信息(圖遍歷)。
3.2?聚合器
這個(gè)Combiners是為了減少開銷而提出的。當(dāng)某個(gè)頂點(diǎn)需要給其他機(jī)器上的頂點(diǎn)發(fā)送消息，而消息的內(nèi)容僅僅是一個(gè)整形值，并且這個(gè)算法只關(guān)心消息的和。所以為了減小開銷，可以將消息整合之后再發(fā)出去。
這個(gè)Combiners不是系統(tǒng)系統(tǒng)的，因?yàn)橄到y(tǒng)并不清楚算法具體的執(zhí)行，所以這個(gè)是由用戶自己定義的。系統(tǒng)只是提供了Combiner()的基類，用戶可以繼承此基類。要注意的是系統(tǒng)提供的Combiner并不保證這個(gè)集合的順序等，所以在實(shí)現(xiàn)的時(shí)候，能集合的消息一定要是可交換順序的。
3.3? 放大器
Pregel的Aggregator可以用于全局通信，監(jiān)管和數(shù)據(jù)。
Pregel定義了一系列的Aggregator，比如sum、max、min等，可以用于統(tǒng)計(jì)。實(shí)際用于諸如統(tǒng)計(jì)每個(gè)頂點(diǎn)的出邊數(shù)量。
Pregel還可以用于全局協(xié)同。比如一個(gè)超級(jí)步中Compute()的一個(gè)分支被執(zhí)行直到and操作符確定所有頂點(diǎn)都滿足某個(gè)條件，然后另外的分支繼續(xù)執(zhí)行直到算法結(jié)束。
用戶要想實(shí)現(xiàn)自己的Aggregator則需要繼承Aggregator基類，然后實(shí)現(xiàn)所有輸入數(shù)值怎么被歸結(jié)到一個(gè)數(shù)值。Aggregators也必須滿足可交換性質(zhì)。
默認(rèn)的Aggregator都是只能接收同一個(gè)超級(jí)步的數(shù)值，你也可以定義接收所有超級(jí)步數(shù)值的Aggregator。
3.4?拓?fù)滢D(zhuǎn)換
有的圖算法需要對(duì)圖的拓?fù)渥鲛D(zhuǎn)化，比如聚類算法會(huì)將一個(gè)劃分用一個(gè)頂點(diǎn)代替。此部分略過。
3.5?輸入和輸出
圖數(shù)據(jù)組織的的形式是多樣的，比如txt，關(guān)系數(shù)據(jù)集合，Bigtable的數(shù)據(jù)。Pregel的數(shù)據(jù)的輸出都可以是任意的，可以將不同組織形式的數(shù)據(jù)轉(zhuǎn)換為Pregel的數(shù)據(jù)組織形式，也可以將Pregel產(chǎn)生的輸出轉(zhuǎn)換為不同的數(shù)據(jù)組織形式。Pregel提供了Reader和Writer的基類，如用戶想實(shí)現(xiàn)其他數(shù)據(jù)組織的讀寫，需自己繼承實(shí)現(xiàn)。
4.?實(shí)現(xiàn)
Pregel是為了Google的集群框架為設(shè)計(jì)，每個(gè)集群包含上千臺(tái)普通PC機(jī)，集群之間可通信但在物理上是分離的。應(yīng)用產(chǎn)生的粗腰持久化數(shù)據(jù)是保存在GFS或者BigTable上，臨時(shí)數(shù)據(jù)則保存在本地磁盤。
4.1?基本框架
Pregel將圖分區(qū)，每個(gè)分區(qū)保存一部分頂點(diǎn)和頂點(diǎn)所有的出邊。圖的劃分僅僅根據(jù)頂點(diǎn)的Id，我們可以根據(jù)頂點(diǎn)的Id就知道頂點(diǎn)被劃分到哪臺(tái)機(jī)器上，也就是對(duì)頂點(diǎn)Id進(jìn)行哈希，默認(rèn)哈希函數(shù)為 Id mod N，N為分片值（譯者注：G*?graph Database也是這么干的)。當(dāng)然具體的哈希也可以由用戶自定義。
不考慮容錯(cuò)的話，一個(gè)Pregel應(yīng)用程序的執(zhí)行包含以下幾個(gè)步驟：
????1.一個(gè)集群的所有機(jī)器都運(yùn)行同一個(gè)應(yīng)用程序，其中有一臺(tái)機(jī)器充當(dāng)master，負(fù)責(zé)任務(wù)協(xié)調(diào)。其他Worker機(jī)器根據(jù)系統(tǒng)提供的名字服務(wù)找到Master的地址進(jìn)行注冊(cè)。
? ? 2.圖數(shù)據(jù)被劃分為多少個(gè)分區(qū)，每個(gè)Worker機(jī)器保存多少個(gè)分區(qū)都是都master控制的，這個(gè)控制權(quán)也提供給了用戶。一臺(tái)Worker保存多于一份的分區(qū)數(shù)據(jù)會(huì)有更好的并行性和負(fù)載均衡，通常來講會(huì)提升性能。每個(gè)Worker負(fù)責(zé)記錄分區(qū)的狀態(tài)，執(zhí)行Compute()，接收和發(fā)送消息。每個(gè)Worker都有一份全局圖數(shù)據(jù)的劃分情況表。
? ? 3.master將用戶輸入的數(shù)據(jù)劃分到集群里。輸入數(shù)據(jù)被當(dāng)作記錄的集合，每個(gè)記錄包含任意數(shù)量的頂點(diǎn)和邊。對(duì)輸入數(shù)據(jù)的劃分僅僅根據(jù)文件的邊界，而和圖本身的屬性無關(guān)。數(shù)據(jù)加載完成之后，所有頂點(diǎn)處于活躍狀態(tài)。
? ? 4.Worker的超級(jí)步的執(zhí)行由master驅(qū)動(dòng)。對(duì)于每個(gè)分區(qū)，每個(gè)Worker用一個(gè)線程循環(huán)遍歷其所有活躍頂點(diǎn)。每個(gè)Worker負(fù)責(zé)執(zhí)行Compute()，結(jié)束之后向master報(bào)告其還有多少活躍頂點(diǎn)，直至所有頂點(diǎn)變?yōu)榉腔钴S態(tài)。
? ? 5.?在計(jì)算停止之后，master可能會(huì)讓所有Worker保存其分區(qū)數(shù)據(jù)。
4.2?容錯(cuò)
Pregel的容錯(cuò)是用檢查點(diǎn)實(shí)現(xiàn)的。每一個(gè)超級(jí)步之前都要先持久化其當(dāng)前狀態(tài)，包括頂點(diǎn)，邊和消息等。master分別保存aggregator的值。
Worker機(jī)器的失效由master保持的心跳來檢測(cè)。當(dāng)Worker失效之后，master會(huì)將其分區(qū)數(shù)據(jù)重新分配到其他可用的機(jī)器上。然后新Worker機(jī)器加載數(shù)據(jù)之后根據(jù)檢查點(diǎn)和保存的狀態(tài)數(shù)據(jù)重新執(zhí)行恢復(fù)到上次失效的位置。不用說，檢查點(diǎn)技術(shù)開銷是很大的，檢查點(diǎn)持久化狀態(tài)數(shù)據(jù)的頻率需要綜合考慮存儲(chǔ)開銷和恢復(fù)的開銷。
Pregel實(shí)現(xiàn)一種叫有限恢復(fù)(confined recovery)的概念以提升其恢復(fù)的延時(shí)和花銷。在數(shù)據(jù)載入和每個(gè)超級(jí)步中都會(huì)保存其出邊的消息，然后依據(jù)這些恢復(fù)到Worker失效前的上一個(gè)狀態(tài)。這個(gè)辦法通過僅執(zhí)行分區(qū)的數(shù)據(jù)來進(jìn)行恢復(fù)而節(jié)省資源并且降低延時(shí)。保存出邊消息會(huì)帶來花銷，但一般來講這部分的I/O不會(huì)成為瓶頸。
4.3 Worker實(shí)現(xiàn)
在內(nèi)存存一個(gè)map表，以頂點(diǎn)Id為鍵，值為頂點(diǎn)值和其出邊信息和狀態(tài)標(biāo)志位。然后遍歷頂點(diǎn)執(zhí)行Compute()，有一個(gè)接收的消息的迭代器和一個(gè)所有出邊的迭代器。
4.4?Master實(shí)現(xiàn)
Master主要負(fù)責(zé)協(xié)調(diào)各個(gè)Worker，每個(gè)Worker在注冊(cè)時(shí)會(huì)被分配唯一的標(biāo)識(shí)符。Master會(huì)保留活躍Worker的狀態(tài)，包含了其標(biāo)識(shí)符，地址信息，和它被分配的分區(qū)。Master這部分的數(shù)據(jù)體量跟分區(qū)數(shù)量成比例而不是跟圖的頂點(diǎn)和邊的數(shù)量成比例。
Master給所有活躍的Worker發(fā)送相同的請(qǐng)求，然后等著Worker的返回。Master的所有操作如輸入、輸出、計(jì)算、保存、恢復(fù)都是在Barriers?同步點(diǎn)這個(gè)地方停下。如果這個(gè)同步點(diǎn)成功master再開始下一個(gè)階段。在computation barrier中，這個(gè)同步點(diǎn)就是每個(gè)超級(jí)步之間的那個(gè)同步點(diǎn)。
4.5?放大器
每個(gè)Worker都有一個(gè)Aggregator實(shí)例的集合，每個(gè)以類型和實(shí)例名唯一標(biāo)識(shí)。當(dāng)一個(gè)Worker在圖的分區(qū)上執(zhí)行超級(jí)步時(shí)，Worker收集所有傳給Aggregator的值然后產(chǎn)生一個(gè)值在本地。一個(gè)Aggregator部地簡(jiǎn)化分區(qū)上的頂點(diǎn)。最后在一個(gè)超級(jí)步結(jié)束時(shí)Worker生成一個(gè)執(zhí)行樹來簡(jiǎn)化之前部分簡(jiǎn)化的Aggregator生成全局的值然后發(fā)送給Master。Master在下一個(gè)超級(jí)步開始時(shí)將這個(gè)全局值發(fā)送給Worker。用一個(gè)樹狀的簡(jiǎn)化模式而不是流水線時(shí)為了提高并行性。
5.應(yīng)用
Pregel論文中跑了很多的算法，這里只翻譯PageRank算法。
實(shí)現(xiàn)的PageRankVertex類繼承自基類Vertex，并實(shí)現(xiàn)Compute()接口。每個(gè)Worker都執(zhí)行類的Compute()。需要注意的是超級(jí)步0負(fù)責(zé)發(fā)送消息，這相當(dāng)于是初始化步驟，所以會(huì)看到代碼直接判斷是否處于超級(jí)步1及以上。
具體實(shí)現(xiàn)是：
? ? 1.如果大于超級(jí)步0則讀取消息迭代器里面所有的消息，求總和然后更改頂點(diǎn)值。
? ? 2.如果超級(jí)步小于30，則讀取所有出邊，然后向所有出邊發(fā)送消息，否則變?yōu)榉腔钴S態(tài)。
最后由Master判斷是否所有頂點(diǎn)都變?yōu)榉腔钴S態(tài)且沒有消息被傳送，進(jìn)而結(jié)束算法。
謝謝大家，只是做了一點(diǎn)微小的貢獻(xiàn)。
