Chaer廈門大學(xué)林子雨大數(shù)據(jù)技術(shù)原理與應(yīng)用第九章圖計算

廈門大學(xué)計算機科學(xué)系2015年版

第九章圖計算

（PPT版本號：2015年6月第1.0版）

《大數(shù)據(jù)技術(shù)原理與應(yīng)用》溫馨提示：編輯幻燈片母版，可以修改每頁PPT的廈大?；蘸偷撞课淖痔峋V9.1 圖計算簡介9.2 Pregel簡介9.3 Pregel圖計算模型9.4 Pregel的C++API9.5 Pregel的體系結(jié)構(gòu)9.6 Pregel的應(yīng)用實例9.7 Pregel和MapReduce實現(xiàn)PageRank算法的對比歡迎訪問《大數(shù)據(jù)技術(shù)原理與應(yīng)用》教材官方網(wǎng)站：本PPT是如下教材的配套講義：21世紀(jì)高等教育計算機規(guī)劃教材《大數(shù)據(jù)技術(shù)原理與應(yīng)用——概念、存儲、處理、分析與應(yīng)用》（2015年6月第1版）廈門大學(xué)林子雨編著，人民郵電出版社ISBN:978-7-115-39287-99.1 圖計算簡介9.1.1 傳統(tǒng)圖計算解決方案的不足之處9.1.2 圖計算通用軟件9.1.1 傳統(tǒng)圖計算解決方案的不足之處很多傳統(tǒng)的圖計算算法都存在以下幾個典型問題：（1）常常表現(xiàn)出比較差的內(nèi)存訪問局部性；（2）針對單個頂點的處理工作過少；（3）計算過程中伴隨著并行度的改變。針對大型圖（比如社交網(wǎng)絡(luò)和網(wǎng)絡(luò)圖）的計算問題，可能的解決方案及其不足之處具體如下：為特定的圖應(yīng)用定制相應(yīng)的分布式實現(xiàn)：通用性不好基于現(xiàn)有的分布式計算平臺進行圖計算：在性能和易用性方面往往無法達到最優(yōu)使用單機的圖算法庫：在可以解決的問題的規(guī)模方面具有很大的局限性使用已有的并行圖計算系統(tǒng)：對大規(guī)模分布式系統(tǒng)非常重要的一些方面（比如容錯），無法提供較好的支持9.1.2 圖計算通用軟件一次BSP計算過程包括一系列全局超步（所謂的超步就是計算中的一次迭代），每個超步主要包括三個組件：局部計算：每個參與的處理器都有自身的計算任務(wù)，它們只讀取存儲在本地內(nèi)存中的值，不同處理器的計算任務(wù)都是異步并且獨立的通訊：處理器群相互交換數(shù)據(jù)，交換的形式是，由一方發(fā)起推送(put)和獲取(get)操作柵欄同步(BarrierSynchronization)：當(dāng)一個處理器遇到“路障”（或柵欄），會等到其他所有處理器完成它們的計算步驟；每一次同步也是一個超步的完成和下一個超步的開始。圖9-1是一個超步的垂直結(jié)構(gòu)圖圖9?1一個超步的垂直結(jié)構(gòu)圖9.2 Pregel簡介Pregel是一種基于BSP模型實現(xiàn)的并行圖處理系統(tǒng)為了解決大型圖的分布式計算問題，Pregel搭建了一套可擴展的、有容錯機制的平臺，該平臺提供了一套非常靈活的API，可以描述各種各樣的圖計算Pregel作為分布式圖計算的計算框架，主要用于圖遍歷、最短路徑、PageRank計算等等9.3 Pregel圖計算模型9.3.1 有向圖和頂點9.3.2 頂點之間的消息傳遞9.3.3 Pregel的計算過程9.3.4 實例9.3.1 有向圖和頂點Pregel計算模型以有向圖作為輸入，有向圖的每個頂點都有一個String類型的頂點ID，每個頂點都有一個可修改的用戶自定義值與之關(guān)聯(lián)，每條有向邊都和其源頂點關(guān)聯(lián)，并記錄了其目標(biāo)頂點ID，邊上有一個可修改的用戶自定義值與之關(guān)聯(lián)在每個超步S中，圖中的所有頂點都會并行執(zhí)行相同的用戶自定義函數(shù)。每個頂點可以接收前一個超步(S-1)中發(fā)送給它的消息，修改其自身及其出射邊的狀態(tài)，并發(fā)送消息給其他頂點，甚至是修改整個圖的拓撲結(jié)構(gòu)。需要指出的是，在這種計算模式中，邊并不是核心對象，在邊上面不會運行相應(yīng)的計算，只有頂點才會執(zhí)行用戶自定義函數(shù)進行相應(yīng)計算9.3.2 頂點之間的消息傳遞圖9?2純消息傳遞模型圖采用消息傳遞模型主要基于以下兩個原因：（1）消息傳遞具有足夠的表達能力，沒有必要使用遠程讀取或共享內(nèi)存的方式（2）有助于提升系統(tǒng)整體性能9.3.3 Pregel的計算過程圖9?3一個簡單的狀態(tài)機圖Pregel的計算過程是由一系列被稱為“超步”的迭代組成的。在每個超步中，每個頂點上面都會并行執(zhí)行用戶自定義的函數(shù)，該函數(shù)描述了一個頂點V在一個超步S中需要執(zhí)行的操作。該函數(shù)可以讀取前一個超步(S-1)中其他頂點發(fā)送給頂點V的消息，執(zhí)行相應(yīng)計算后，修改頂點V及其出射邊的狀態(tài)，然后沿著頂點V的出射邊發(fā)送消息給其他頂點，而且，一個消息可能經(jīng)過多條邊的傳遞后被發(fā)送到任意已知ID的目標(biāo)頂點上去。這些消息將會在下一個超步(S+1)中被目標(biāo)頂點接收，然后像上述過程一樣開始下一個超步(S+1)的迭代過程在Pregel計算過程中，一個算法什么時候可以結(jié)束，是由所有頂點的狀態(tài)決定的，當(dāng)圖中所有的頂點都已經(jīng)標(biāo)識其自身達到“非活躍（inactive）”狀態(tài)時，算法就可以停止運行實實例圖9?4一一個求最大值值的Pregel計算過過程圖9.4 Pregel的的C++APIPregel已經(jīng)預(yù)先定義義好一個基類類——Vertex類：template<typenameVertexValue,typenameEdgeValue,typenameMessageValue>classVertex{public: virtualvoidCompute(MessageIterator*msgs)=0; conststring&vertex_id()const; int64superstep()const; constVertexValue&GetValue(); VertexValue*MutableValue(); OutEdgeIteratorGetOutEdgeIterator(); voidSendMessageTo(conststring&dest_vertex, constMessageValue&message); voidVoteToHalt();};在Vetex類中，定義了了三個值類型型參數(shù)，分別別表示頂點、、邊和消息。。每一個頂點點都有一個給給定類型的值值與之對應(yīng)編寫Pregel程序時，需要要繼承Vertex類，并且覆寫寫Vertex類的虛函數(shù)Compute()9.4 Pregel的的C++API消息傳遞機制制拓撲改變輸入和輸出消消息傳遞機機制頂點之間的通通訊是借助于于消息傳遞機機制來實現(xiàn)的的，每條消息息都包含了消消息值和需要要到達的目標(biāo)標(biāo)頂點ID。用戶可以通通過Vertex類的模板參數(shù)數(shù)來設(shè)定消息息值的數(shù)據(jù)類類型在一個超步S中，一個頂點點可以發(fā)送任任意數(shù)量的消消息，這些消消息將在下一一個超步（S+1）中被其他頂頂點接收一個頂點V通過與之關(guān)聯(lián)聯(lián)的出射邊向向外發(fā)送消息息，并且，消消息要到達的的目標(biāo)頂點并并不一定是與與頂點V相鄰的頂點，，一個消息可可以連續(xù)經(jīng)過過多條連通的的邊到達某個個與頂點V不相鄰的頂點點U，U可以從接收的的消息中獲取取到與其不相相鄰的頂點V的IDPregel計算框架在消消息發(fā)出去之之前，Combiner可以將發(fā)往同同一個頂點的的多個整型值值進行求和得得到一個值，，只需向外發(fā)發(fā)送這個“求求和結(jié)果”，，從而實現(xiàn)了了由多個消息息合并成一個個消息，大大大減少了傳輸輸和緩存的開開銷在默認情況況下，Pregel計算框架并并不會開啟啟Combiner功能，因為為，通常很很難找到一一種對所有有頂點的Compute()函數(shù)都合適適的Combiner當(dāng)用戶打算算開啟Combiner功能時，可可以繼承Combiner類并覆寫虛虛函數(shù)Combine()此外，通常常只對那些些滿足交換換律和結(jié)合合律的操作作才可以去去開啟Combiner功能，因為為，Pregel計算框架無無法保證哪哪些消息會會被合并，，也無法保保證消息傳傳遞給Combine()的順序和合合并操作執(zhí)執(zhí)行的順序序圖9-5Combiner應(yīng)用的例子子9.4.3 AggregatorAggregator提供了一種種全局通信信、監(jiān)控和和數(shù)據(jù)查看看的機制在一個超步步S中，每一個個頂點都可可以向一個個Aggregator提供一個數(shù)數(shù)據(jù)，Pregel計算框架會會對這些值值進行聚合合操作產(chǎn)生生一個值，，在下一個個超步（S+1）中，圖中中的所有頂頂點都可以以看見這個個值A(chǔ)ggregator的聚合功能能，允許在在整型和字字符串類型型上執(zhí)行最最大值、最最小值、求求和操作Pregel計算框架預(yù)預(yù)定義了一一個Aggregator類，編寫程程序時需要要繼承這個個類，并定定義在第一一次接收到到輸入值后后如何初始始化，以及及如何將接接收到的多多個值最后后聚合成一一個值為了保證得得到正確的的結(jié)果，Aggregator操作也應(yīng)該該滿足交換換律和結(jié)合合律9.4.4 拓撲改改變Pregel計算框架允允許用戶在在自定義函函數(shù)Compute()中定義操作作，修改圖圖的拓撲結(jié)結(jié)構(gòu)，比如如在圖中增增加（或刪刪除）邊或或頂點Pregel采用兩種機機制來解決決這類沖突突：局部有有序和Handler（1）局部有序序：拓撲改改變的請求求是通過消消息發(fā)送的的，在執(zhí)行行一個超步步時，所有有的拓撲改改變會在調(diào)調(diào)用Compute()函數(shù)之前完完成（2）Handler：對于“局局部無序””機制無法法解決的那那些操作沖沖突，就需需要借助于于用戶自定定義的Handler來解決，包包括解決由由于多個頂頂點刪除請請求或多個個邊增加請請求（或刪刪除請求））而造成的的沖突9.4.5 輸入和和輸出在Pregel計算框架中中，圖的保保存格式多多種多樣，，包括文本本文件、關(guān)關(guān)系數(shù)據(jù)庫庫或鍵值數(shù)數(shù)據(jù)庫等在Pregel中，“從輸輸入文件生生成得到圖圖結(jié)構(gòu)”和和“執(zhí)行圖圖計算”這這兩個過程程是分離的的，從而不不會限制輸輸入文件的的格式對于輸出，，Pregel也采用了靈靈活的方式式，可以以以多種方式式進行輸出出9.5Pregel的體系系結(jié)構(gòu)9.5.1 Pregel的執(zhí)行過程程容錯性9.5.3 Worker9.5.4 Master9.5.5 Aggregator9.5.1 Pregel的的執(zhí)行過程程圖9-6圖的劃分圖圖在Pregel計算框架中中，一個大大型圖會被被劃分成許許多個分區(qū)區(qū)，每個分分區(qū)都包含含了一部分分頂點以及及以其為起起點的邊一個頂點應(yīng)應(yīng)該被分配配到哪個分分區(qū)上，是是由一個函函數(shù)決定的的，系統(tǒng)默默認函數(shù)為為hash(ID)modN，其中，N為所有分區(qū)區(qū)總數(shù)，ID是這個頂點點的標(biāo)識符符；當(dāng)然，，用戶也可可以自己定定義這個函函數(shù)這樣，無論論在哪臺機機器上，都都可以簡單單根據(jù)頂點點ID判斷出該頂頂點屬于哪哪個分區(qū)，，即使該頂頂點可能已已經(jīng)不存在在了9.5.1 Pregel的的執(zhí)行過程程圖9-7Pregel的執(zhí)執(zhí)行過程圖圖在理想的情情況下（不不發(fā)生任何何錯誤），，一個Pregel用戶程序序的執(zhí)行過過程如下：：（1）選擇擇集群中的的多臺機器器執(zhí)行圖計計算任務(wù)，，每臺機器器上運行用用戶程序的的一個副本本，其中，，有一臺機機器會被選選為Master，，其他機器器作為Worker（2）Master把一個圖圖分成多個個分區(qū)，并并把分區(qū)分分配到多個個Worker（3）Master會把用戶戶輸入劃分分成多個部部分，通常常是基于文文件邊界進進行劃分（4）Master向每個Worker發(fā)送指令，，Worker收到指令后后，開始運運行一個超超步。當(dāng)當(dāng)完成以后后，Worker會通知Master，并把自己己在下一個個超步還處處于“活躍躍”狀態(tài)的的頂點的數(shù)數(shù)量報告給給Master。上述步驟驟會被不斷斷重復(fù)，直直到所有頂頂點都不再再活躍并且且系統(tǒng)中不不會有任何何消息在傳傳輸，這時時，執(zhí)行過過程才會結(jié)結(jié)束（5）計算過程程結(jié)束后，，Master會給所有的的Worker發(fā)送指令，，通知每個個Worker對自己的計計算結(jié)果進進行持久化化存儲9.5.2 容錯性性Pregel采用檢查點點機制來實實現(xiàn)容錯。。在每個超超步的開始始，Master會通知所有有的Worker把自己管轄轄的分區(qū)的的狀態(tài)（包包括頂點值值、邊值以以及接收到到的消息）），寫入到到持久化存存儲設(shè)備Master會周期性地地向每個Worker發(fā)送ping消息，Worker收到ping消息后會給給Master發(fā)送反饋消消息。如果果Master在指定時間間間隔內(nèi)沒沒有收到某某個Worker的反饋消息息，就會把把該Worker標(biāo)記為“失失效”。同同樣地，如如果一個Worker在指定的時時間間隔內(nèi)內(nèi)沒有收到到來自Master的ping消息，該Worker也會停止工工作每個Worker上都保存了了一個或多多個分區(qū)的的狀態(tài)信息息，當(dāng)一個個Worker發(fā)生故障時時，它所負負責(zé)維護的的分區(qū)的當(dāng)當(dāng)前狀態(tài)信信息就會丟丟失。Master監(jiān)測到一個個Worker發(fā)生故障““失效”后后，會把失失效Worker所分配到的的分區(qū)，重重新分配到到其他處于于正常工作作狀態(tài)的Worker集合上，然然后，所有有這些分區(qū)區(qū)會從最近近的某超步步S開始時寫出出的檢查點點中，重新新加載狀態(tài)態(tài)信息。很很顯然，這這個超步S可能會比失失效Worker上最后運行行的超步S1要早好幾個個階段，因因此，為了了恢復(fù)到最最新的正確確狀態(tài)，需需要重新執(zhí)執(zhí)行從超步步S到超步S1的所有操作作9.5.3 Worker在一個Worker中，它所管管轄的分區(qū)區(qū)的狀態(tài)信信息是保存存在內(nèi)存中中的。分區(qū)區(qū)中的頂點點的狀態(tài)信信息包括：：頂點的當(dāng)前前值以該頂點為為起點的出出射邊列表表，每條出出射邊包含含了目標(biāo)頂頂點ID和邊的值消息隊列，，包含了所所有接收到到的、發(fā)送送給該頂點點的消息標(biāo)志位，用用來標(biāo)記頂頂點是否處處于活躍狀狀態(tài)在每個超步步中，Worker會對自己所所管轄的分分區(qū)中的每每個頂點進進行遍歷，，并調(diào)用頂頂點上的Compute()函數(shù)，在調(diào)調(diào)用時，會會把以下三三個參數(shù)傳傳遞進去：：該頂點的當(dāng)當(dāng)前值一個接收到到的消息的的迭代器一個出射邊邊的迭代器器9.5.4 MasterMaster主要負責(zé)協(xié)協(xié)調(diào)各個Worker執(zhí)行任務(wù)，，每個Worker會借助于名名稱服務(wù)系系統(tǒng)定位到到Master的位置，并并向Master發(fā)送自己的的注冊信息息，Master會為每個Worker分配一個唯唯一的IDMaster維護著關(guān)于于當(dāng)前處于于“有效””狀態(tài)的所所有Worker的各種信息息，包括每每個Worker的ID和地址信息息，以及每每個Worker被分配到的的分區(qū)信息息一個大規(guī)模模圖計算任任務(wù)會被Master分解到多個個Worker去執(zhí)行，如如果參與任任務(wù)執(zhí)行的的多個Worker中的任意一一個發(fā)生了了故障失效效，Master就會進入恢恢復(fù)模式Master在內(nèi)部運行行了一個HTTP服務(wù)器來顯顯示圖計算算過程的各各種信息，，用戶可以以通過網(wǎng)頁頁隨時監(jiān)控控圖計算執(zhí)執(zhí)行過程各各個細節(jié)9.5.5 Aggregator每個用戶自自定義的Aggregator都會采用聚聚合函數(shù)對對一個值集集合進行聚聚合計算得得到一個全全局值每個Worker都保存了一一個Aggregator的實例集，，其中的每每個實例都都是由類型型名稱和實實例名稱來來標(biāo)識的在執(zhí)行圖計計算過程的的某個超步步S中，每個Worker會利用一個個Aggregator對當(dāng)前本地地分區(qū)中包包含的所有有頂點的值值進行歸約約，得到一一個本地的的局部歸約約值在超步S結(jié)束時，所所有Worker會將所有包包含局部歸歸約值的Aggregator的值進行最最后的匯總總，得到全全局值，然然后提交給給Master在下一個超超步S+1開始時，Master就會將Aggregator的全局值發(fā)發(fā)送給每個個Worker9.6Pregel的應(yīng)用用實例單源最短路路徑二分匹配9.6.1 單源最最短路徑Pregel非常適合用用來解決單單源最短路路徑問題，，實現(xiàn)代碼碼如下：classShortestPathVertex:publicVertex<int,int,int>{voidCompute(MessageIterator*msgs){intmindist=IsSource(vertex_id())?0:INF;for(;!msgs->Done();msgs->Next())mindist=min(mindist,msgs->Value());if(mindist<GetValue()){*MutableValue()=mindist;OutEdgeIteratoriter=GetOutEdgeIterator();for(;!iter.Done();iter.Next())SendMessageTo(iter.Target(),mindist+iter.GetValue());}VoteToHalt();}};9.6.2 二分匹匹配程序的執(zhí)行行過程是由由四個階段段組成的多多個循環(huán)組組成的，當(dāng)當(dāng)程序執(zhí)行行到超步S時，Smod4就可以得到到當(dāng)前超步步處于循環(huán)環(huán)的哪個階階段。每個個循環(huán)的四四個階段如如下：（1）階階段段0：對對于于左左集集合合中中的的任任意意頂頂點點V，如如果果V還沒沒有有被被匹匹配配，，就就發(fā)發(fā)送送消消息息給給它它的的每每個個鄰鄰居居頂頂點點請請求求匹匹配配，，然然后后，，頂頂點點V會調(diào)調(diào)用用VoteToHalt()進入入““非非活活躍躍””狀狀態(tài)態(tài)。。如如果果頂頂點點V已經(jīng)經(jīng)找找到到了了匹匹配配，，或或者者V沒有有找找到到匹匹配配但但是是沒沒有有出出射射邊邊，，那那么么，，頂頂點點V就不不會會發(fā)發(fā)送送消消息息。。當(dāng)當(dāng)頂頂點點V沒有有發(fā)發(fā)送送消消息息，，或或者者頂頂點點V發(fā)送送了了消消息息但但是是所所有有的的消消息息接接收收者者都都已已經(jīng)經(jīng)被被匹匹配配，，那那么么，，該該頂頂點點就就不不會會再再變變?yōu)闉椤啊盎罨钴S躍（（active）””狀狀態(tài)態(tài)（2）階階段段1：對對于于右右集集合合中中的的任任意意頂頂點點U，如如果果它它還還沒沒有有被被匹匹配配，，則則會會隨隨機機選選擇擇它它接接收收到到的的消消息息中中的的其其中中一一個個，，并并向向左左集集合合中中的的消消息息發(fā)發(fā)送送者者發(fā)發(fā)送送消消息息表表示示接接受受該該匹匹配配請請求求，，然然后后給給左左集集合合中中的的其其他他請請求求者者發(fā)發(fā)送送拒拒絕絕消消息息；；然然后后，，頂頂點點U會調(diào)調(diào)用用VoteToHalt()進入入““非非活活躍躍””狀狀態(tài)態(tài)（3）階階段段2：左左集集合合中中那那些些還還未未被被匹匹配配的的頂頂點點，，會會從從它它所所收收到到的的、、右右集集合合發(fā)發(fā)送送過過來來的的接接受受請請求求中中，，選選擇擇其其中中一一個個給給予予確確認認，，并并發(fā)發(fā)送送一一個個確確認認消消息息。。對對于于左左集集合合中中已已經(jīng)經(jīng)匹匹配配的的頂頂點點而而言言，，因因為為它它們們在在階階段段0不會會向向右右集集合合發(fā)發(fā)送送任任何何匹匹配配請請求求消消息息，，因因而而也也不不會會接接收收到到任任何何來來自自右右集集合合的的匹匹配配接接受受消消息息，，因因此此，，是是不不會會執(zhí)執(zhí)行行階階段段2的（4）階階段段3：右右集集合合中中還還未未被被匹匹配配的的任任意意頂頂點點U，會會收收到到來來自自左左集集合合的的匹匹配配確確認認消消息息，，但但是是，，每每個個未未匹匹配配的的頂頂點點U，最最多多會會收收到到一一個個確確認認消消息息。。然然后后，，頂頂點點U會調(diào)調(diào)用用VoteToHalt()進入入““非非活活躍躍””狀狀態(tài)態(tài)，，完完成成它它自自身身的的匹匹配配工工作作9.7Pregel和和MapReduce實實現(xiàn)現(xiàn)PageRank算算法法的的對對比比9.7.1PageRank算法法算法法在在Pregel中的的實實現(xiàn)現(xiàn)算法法在在MapReduce中的的實實現(xiàn)現(xiàn)算法法在在Pregel和MapReduce中實實現(xiàn)現(xiàn)的的比比較較PageRank是一一個個函函數(shù)數(shù)，，它它為為網(wǎng)網(wǎng)絡(luò)絡(luò)中中每每個個網(wǎng)網(wǎng)頁頁賦賦一一個個權(quán)權(quán)值值。。通通過過該該權(quán)權(quán)值值來來判判斷斷該該網(wǎng)網(wǎng)頁頁的的重重要要性性該權(quán)權(quán)值值分分配配的的方方法法并并不不是是固固定定的的，，對對PageRank算法法的的一一些些簡簡單單變變形形都都會會改改變變網(wǎng)網(wǎng)頁頁的的相相對對PageRank值（（PR值））PageRank作為為谷谷歌歌的的網(wǎng)網(wǎng)頁頁鏈鏈接接排排名名算算法法，，基基本本公公式式如如下下：：對于于任任意意一一個個網(wǎng)網(wǎng)頁頁鏈鏈接接，，其其PR值為為鏈鏈入入到到該該鏈鏈接接的的源源鏈鏈接接的的PR值對對該該鏈鏈接接的的貢貢獻獻和和，，其其中中，，N表示示該該網(wǎng)網(wǎng)絡(luò)絡(luò)中中所所有有網(wǎng)網(wǎng)頁頁的的數(shù)數(shù)量量，，Ni為第第i個源源鏈鏈接接的的鏈鏈出出度度，，PRi表示示第第i個源源鏈鏈接接的的PR值PageRank算法法PageRank算法法網(wǎng)絡(luò)絡(luò)鏈鏈接接之之間間的的關(guān)關(guān)系系可可以以用用一一個個連連通通圖圖來來表表示示，，下下圖圖就就是是四四個個網(wǎng)網(wǎng)頁頁（（A,B,C,D）互互相相鏈鏈入入鏈鏈出出組組成成的的連連通通圖圖，，從從中中可可以以看看出出，，網(wǎng)網(wǎng)頁頁A中包含指向網(wǎng)網(wǎng)頁B、C和D的外鏈，網(wǎng)頁頁B和D是網(wǎng)頁A的源鏈接在Pregel計算模型中，，圖中的每個個頂點會對應(yīng)應(yīng)一個計算單單元，每個計計算單元包含含三個成員變變量：頂點值（Vertexvalue）：頂點對應(yīng)應(yīng)的PR值出射邊（Outedge）：只需要表表示一條邊，，可以不取值值消息（Message）：傳遞的消消息，因為需需要將本頂點點對其它頂點點的PR貢獻值，傳遞遞給目標(biāo)頂點點每個計算單元元包含一個成成員函數(shù)Compute()，該函數(shù)定義義了頂點上的的運算，包括括該頂點的PR值計算，以及及從該頂點發(fā)發(fā)送消息到其其鏈出頂點PageRank算法在Pregel中的實現(xiàn)PageRank算法在Pregel中的實現(xiàn)classPageRankVertex:publicVertex<double,void,double>{public:virtualvoidCompute(MessageIterator*msgs){ if(superstep()>=1){ doublesum=0; for(;!msgs->Done();msgs->Next()) sum+=msgs->Value(); *MutableValue()= 0.15/NumVertices()+0.85*sum; } if(superstep()<30){ constint64n=GetOutEdgeIterator().size(); SendMessageToAllNeighbors(GetValue()/n); }else{ VoteToHalt(); } }};PageRank算法在Pregel中的實現(xiàn)PageRankVertex繼承自Vertex類，頂點值類類型是double，用來保存PageRank中間值，消息息類型也是double，用來傳輸PageRank值，邊的value類型是void，因為不需要要存儲任何信信息這里假設(shè)在第第0個超步時，圖圖中各頂點值值被初始化為為1/NumVertices()，其中，NumVertices()表示頂點數(shù)目目在前30個超步中，每每個頂點都會會沿著它的出出射邊，發(fā)送送它的PageRank值除以出射邊邊數(shù)目以后的的結(jié)果值。從從第1個超步開始，，每個頂點會會將到達的消消息中的值加加到sum值中，同時將將它的PageRank值設(shè)為0.15/NumVertices()+0.85*sum到了第30個超步后，就就沒有需要發(fā)發(fā)送的消息了了，同時所有有的頂點停止止計算，得到到最終結(jié)果MapReduce也是谷歌公司司提出的一種種計算模型，，它是為全量量計算而設(shè)計計采用MapReduce實現(xiàn)PageRank的計算過程包包括三個階段段：第一階段：解解析網(wǎng)頁第二階段：PageRank分配第三階段：收收斂階段PageRank算法在MapReduce中的實現(xiàn)PageRank算法在MapReduce中的實現(xiàn)該階段的任務(wù)務(wù)就是分析一一個頁面的鏈鏈接數(shù)并賦初初值。一個網(wǎng)頁可以以表示為由網(wǎng)網(wǎng)址和內(nèi)容構(gòu)構(gòu)成的鍵值對對<URL，pagecontent>，作為Map任務(wù)的輸入。。階段1的Map任務(wù)把<URL，pagecontent>映射為<URL，<PRinit，url_list>>后進行輸出，，其中，PRinit是該URL頁面對應(yīng)的PageRank初始值，url_list包含了該URL頁面中的外鏈鏈所指向的所所有URL。Reduce任務(wù)只是恒等等函數(shù)，輸入入和輸出相同同。對右圖，每個個網(wǎng)頁的初始始PageRank值為1/4。它在該階段段中:Map任務(wù)的輸入為為：<AURL，Acontent><BURL，Bcontent><CURL，Ccontent><DURL，Dcontent>Map任務(wù)的輸出為為：<AURL，<1/4，<BURL，CURL，DURL>>><BURL，<1/4，<AURL，CURL>>><CURL，<1/4，DURL>><DURL，<1/4，<AURL，BURL>>>1.階段1：解析網(wǎng)頁PageRank算法在MapReduce中的實現(xiàn)該階段的任務(wù)務(wù)就是多次迭迭代計算頁面面的PageRank值。在該階段中，，Map任務(wù)的輸入是是<URL，<cur_rank，url_list>>，其中，cur_rank是該URL頁面對應(yīng)的PageRank當(dāng)前值，url_list包含了該URL頁面中的外鏈鏈所指向的所所有URL。對于url_list中的每個元素素u，Map任務(wù)輸出<u，<URL,cur_rank/|url_list|>>（其中，|url_list|表示外鏈的個個數(shù)），并輸輸出鏈接關(guān)系系<URL，url_list>。每個頁面的PageRank當(dāng)前值被平均均分配給了它它們的每個外外鏈。Map任務(wù)的輸出會會作為下面Reduce任務(wù)的輸入。。對下圖第一一次迭代Map任務(wù)的輸入輸輸出如下：輸入為：<AURL，Acontent><BURL，Bcontent><CURL，Ccontent><DURL，Dcontent>輸出為：<BURL，<AURL，1/12>><CURL，<AURL，1/12>><DURL，<AURL，1/12>><AURL，<BURL，CURL，DURL>><AURL，<BURL，1/8>><CURL，<BURL，1/8>><BURL，<AURL，CURL>><DURL，<CURL，1/4>><CURL，DURL><AURL，<DURL，1/8>><BURL，<DURL，1/8>><DURL，<AURL，BURL>>2.階段2：PageRank分配PageRank算法在MapReduce中的實現(xiàn)然后，在該階階段的Reduce階段，Reduce任務(wù)會獲得<URL，url_list>和<u，<URL,cur_rank/|url_list|>>，Reduce任務(wù)對于具有有相同key值的value進行匯總，并并把匯總結(jié)果果乘以d，得到每個網(wǎng)網(wǎng)頁的新的PageRank值new_rank，然后輸出<URL，<new_rank，url_list>>，作為下一次次迭代過程的的輸入。Reduce任務(wù)把第一次次迭代后Map任務(wù)的輸出作作為自己的輸輸入，經(jīng)過處處理后，階段段2的Reduce輸出為：<AURL，<0.2500，<BURL，CURL，DURL>>><BURL，<0.2147，<AURL，CURL>>><CURL，<0.2147，DURL>><DURL，<0.3206，<AURL，BURL>>>經(jīng)過本輪迭代代，每個網(wǎng)頁頁都計算得到到了新的PageRank值。下次迭代代階段2的Reduce輸出為：<AURL，<0.2200，<BURL，CURL，DURL>>><BURL，<0.1996，<AURL，CURL>>><CURL，<0.1996，DURL>><DURL，<0.3808，<AURL，BURL>>>2.階段2：PageRank分配（Reduce階段）PageRank算法在MapReduce中的實現(xiàn)Mapper函數(shù)的偽碼：：input<PageN,RankN>->PageA,PageB,PageC...//PageN外鏈指向PageA,PageB,PageC...beginNn:=thenumberofoutlinksforPageN;foreachoutlinkPageKoutputPageK-><PageN,RankN/Nn>outputPageN->PageA,PageB,PageC...//同時輸出鏈接接關(guān)系，用于于迭代end/**************************Mapper輸出如下（已已經(jīng)排序，所所以PageK的數(shù)據(jù)排在一一起，最后一一行則是鏈接接關(guān)系對）：：PageK-><PageN1,RankN1/Nn1>PageK-><PageN2,RankN2/Nn2>...PageK-><PageAk,PageBk,PageCk>Reducer函數(shù)的的偽碼碼：inputmapper'soutputbeginRankK:=(1-beta)/N;//N為整個個網(wǎng)絡(luò)絡(luò)的網(wǎng)網(wǎng)頁總總數(shù)foreachinlinkPageNiRankK+=RankNi/Nni*beta//輸出PageK及其新新的PageRank值用于于下次次迭代代output<PageK,RankK>-><PageAk,PageBk,PageCk...>end該階段段是一個個多次迭迭代過過程，，迭代代多次次后，，當(dāng)PageRank值趨于于穩(wěn)定定時，就就得出出了較較為精精確的的PageRank值。PageRank算法在在MapReduce中的實實現(xiàn)該階段段的任任務(wù)就就是由由一個個非并并行組組件決決定是是否達達到收收斂，，如果果達到到收斂斂，就就寫出出PageRank生成的的列表表。否否則，，回退退到PageRank分配階階段的的輸出出，作作為新新一輪輪迭代代的輸輸入，，開始始新一一輪PageRank分配階階段的的迭代代一般判判斷是是否收收斂的的條件件是所所有網(wǎng)網(wǎng)頁的的PageRank值不再再變化化，或或者運運行30次以后后我們們就認認為已已經(jīng)收收斂了了3.階段3：收斂斂階段段PageRank算法在在Pr