/*?版權聲明：可以任意轉載，轉載時請務必標明文章原始出處和作者信息?.*/
???????????????? CopyMiddle:?張俊林? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ???

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

1.使用Mapreduce進行圖計算

????????? 使用MapReduce框架來針對大規模圖數據進行計算的研究工作相對較少，這主要歸結于兩方面原因：一方面，將傳統的圖計算映射為MapReduce任務相對其他類型的很多任務而言不太直觀；另一方面，從某種角度講，使用該分布計算框架解決圖計算任務也并非最適宜的解決方案。

???? 盡管有上述缺點，但很多圖算法還是可以轉換為Mapreduce框架下的計算任務。下面以PageRank計算為例講述如何在該框架下進行圖計算。PageRank的計算原理在前面已有介紹，本節重點分析如何在Mapreduce框架下對算法進行改造，使得可以用多機分布方式對大規模圖進行運算。

????? Mapreduce框架下的輸入往往是key-value數據對，其中，value可以是簡單類型，比如數值或字符串，也可以是復雜的數據結構，比如數組或者記錄等。對于圖數據來說，其內部表示方式以鄰接表為宜，這樣，輸入數據的key為圖節點ID，對應的value為復雜記錄，其中記載了鄰接表數據、key節點的PageRank值等。

????? 對很多圖算法來說，Mapreduce內部計算過程中的Shuffle和Sort操作起到類似于通過圖中節點出邊進行消息傳播的效果。從圖14-7的PageRank偽碼中可見此技巧的運用。

?????? 在該例的Map操作中，輸入數據的key是圖節點ID，value是圖節點數據結構N，其中包括鄰接表AdjacencyList信息以及節點對應的當前PageRank值。第3行代碼計算當前節點傳播到鄰接節點的PageRank分值，第5、6行代碼將這些分值轉換為新的key1-value1，以鄰接節點ID作為新的key，而從當前節點傳播給鄰接節點的分值作為新的value1。除此之外，還需要將當前節點的節點信息繼續保留，以便進行后續的迭代過程，所以第4行代碼將輸入記錄本身再次原封不動地傳播出去。

?????? 通過MapReduce內部的Shuffle和Sort操作，可以將相同key1對應的系列value1集中到一起，即將ID為key1的圖節點從其他節點傳入的PageRank部分分值聚合到一起，這起到了類似于消息傳播的作用。圖14-7示例里的Reduce操作中，其對應的輸入數據包括圖節點ID以及對應的PageRank部分分值列表，偽碼第4行到第8行累積這部分分值形成新的PageRank值，同時判斷某個value1是否是節點信息（第5行代碼）。第9行代碼則更新節點信息內的PageRank值，而第10行代碼輸出更新后的節點信息。這樣就完成了一輪PageRank迭代過程，而本次Reduce階段的輸出結果可以作為下一輪迭代Map階段的輸入數據。如此循環往復，直到滿足終止條件，即可輸出最終的計算結果。

?

?????? Mapreduce計算框架在Map操作后會通過網絡通信將具有相同key值的中間結果記錄映射到同一臺機器上，以滿足后續Reduce階段操作的要求。一般情況下，這種網絡傳輸數據量非常大，往往會嚴重影響計算效率，而Combine操作即為減少網絡傳輸以優化效率而提出。Combine操作在本地機器Map操作后，首先將具有相同key值的Map結果數據value部分進行本地聚合，這樣本來應該分別傳輸的項目即被合并，大大減少了網絡傳輸量，加快了計算速度。對于圖計算，同樣可以采用這種優化手段改善效率，圖14-8展示了相應的Combine操作，其運行流程與Reduce操作大體相似，第4行到第8行代碼累加相同key的本地value數據，第9行代碼將這種累加數據傳播出去，key保持不變，value成為聚合數據s，這樣就大量減少了網絡傳輸量。

?????? 上面介紹了如何在Mapreduce框架下進行PageRank計算，很多其他圖算法也可用近似的思路處理，其關鍵點仍然是通過上述的Shuffle和Sort操作，將同一節點的入邊聚合到一起，而Reduce操作可以類似例中的部分數值求和，也可能是取邊中的Max/Min等其他類型的操作，這依據應用各異，但基本思想無較大的區別。

2．MapReduce在圖計算中存在的問題

??????? MapReduce盡管已經成為主流的分布式計算模型，但有其適用范圍，對于大量的機器學習數據挖掘類科學計算和圖挖掘算法來說，使用Mapreduce模型盡管經過變換也可以得到解決，但往往并非解決此類問題的最佳技術方案。根本原因在于：很多科學計算或者圖算法內在機制上需要進行多輪反復迭代，而如果采用Mapreduce模型，每一次迭代過程中產生的中間結果都需要反復在Map階段寫入本地磁盤，在Reduce階段寫入GFS/HDFS文件系統中，下一輪迭代一般是在上一輪迭代的計算結果的基礎上繼續進行，這樣需要再次將其加載入內存，計算得出新的中間結果后仍然寫入本地文件系統以及GFS/HDFS文件系統中。如此反復，且不必要的磁盤輸入/輸出嚴重影響計算效率。除此之外，每次迭代都需要對任務重新進行初始化等任務管理開銷也非常影響效率。

?????? 下面以Mapreduce模型計算圖的單源最短路徑的具體應用實例來說明此問題的嚴重性。所謂“單源最短路徑”，就是對于圖結構G<N,E>（N為圖節點集合，E為圖中邊集合且邊具有權值，這個權值代表兩個節點間的距離），如果給定初始節點V，需要計算圖中該節點到其他任意節點的最短距離是多少。這個例子的圖結構如圖14-9所示，圖的內部表示采用鄰接表方案。假設從源節點A出發，求其他節點到節點A的最短距離，在初始化階段，設置源節點A的最短距離為0，其他節點的最短距離為INF（足夠大的數值）。

????? 對Mapreduce模型來說，計算分為兩個階段，即Map階段和Reduce階段。針對上述問題，Map階段的最初輸入即為稍加改造的圖G的鄰接表，除了節點的鄰接表信息外，還需要額外記載節點當前獲得的最小距離數值。以常見的key-value方式表示為：key=節點ID，value=<節點到源節點A的當前最小距離Dist，鄰接表>。以源節點A為例，其Map階段的輸入為：<A, <0, <(B, 10),(D, 5)>>>，其他節點輸入數據形式與此類似。

????? Map階段對輸入數據的轉換邏輯為：計算key節點的鄰接表中節點到源節點A的當前最短距離。即將key-value轉換為key1-value1序列，這里key1是key節點的鄰接表中節點ID，value1為key1節點到源節點A的當前最短距離。以源節點A為例，其輸入為<A, <0, <(B, 10), (D, 5)>>>，經過Map轉換后，得到輸出<B,10>和<D,5>，<B,10>的含義是：B節點到A節點的當前最短距離是10（由A節點到源節點A距離0加上B節點到A節點距離10獲得），<D,5>的含義與之類似。通過此步可以完成Map階段計算，圖14-10展示了原始輸入轉換為Map階段輸出結果對應的KV數值。

?????? 在Map階段產生結果后，系統會將臨時結果寫入本地磁盤文件中，以作為Reduce階段的輸入數據。Reduce階段的邏輯為：對某個節點來說，從眾多本節點到源節點A的距離中選擇最短的距離作為當前值。以節點B為例，從圖14-10中Map階段的輸出可以看出，以B為key有兩項：<B,10>和<B,inf>，取其最小值得到新的最短距離為10，則可輸出結果<B,<10,<(C,1),(D,2)>>>。圖14-11展示了Reduce階段的輸出。

????? 在Reduce階段結束后，系統將結果寫入GFS/HDFS文件系統中，這樣完成了單源最短路徑的一輪計算。使得圖節點B和圖節點D的當前最短路徑獲得了更新。而為了能夠獲得最終的結果，還需要按照上述方式反復迭代，以本輪Reduce輸出作為下一輪Map階段的輸入。由此可見，如果完成計算，則需要多次將中間結果往文件系統輸出，這會嚴重影響系統效率。這是為何Mapreduce框架不適宜做圖應用的主要原因。

總結

以上是生活随笔為你收集整理的大数据图数据库之MapReduce用于图计算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。