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

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

第九章圖計(jì)算

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

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