一.圖計算簡介

1.1 圖計算是專門針對圖結構數據的處理．

• 許多大數據都是以大規模圖或網絡的形式呈現；
• 許多非圖結構的大數據，也常常被轉換為圖模型后進行分析；
• 圖結構很好地表達了數據之間的關聯性；
• 關聯性計算是大數據計算的核心------通過獲得數據的關聯性，可以從噪音很多的海量數據中抽取有用的信息；

1.2 傳統的圖計算算法存在典型問題

• 常常表現出比較差的內存訪問局部性；
• 針對單個節點的處理工作過少；
• 計算過程中伴隨著并行度的改變；

1.3 解決方案

• 為特定的圖應用定制相應的分布式實現，通用性不好；
• 基于現有的分布式計算平臺進行圖計算；
• 使用單機的圖算法庫：BGL,LEAD,NetworkX,JDSL,Standford GraphBase 和FGL等，對于大規模計算能力有限．
• 使用已有的并行圖計算系統：Parallel BGL 和CGM Graph ,實現了很多并行圖算法，存在容錯性問題；

1.4 MapReduce 是分布式計算平臺．

• MapReduce 在圖計算方面的性能和易用性不好，是粗粒度的計算，以塊為單位進行數據分析；

1.5 通用的圖計算軟件

• 基于遍歷算法的，實時的圖數據庫；如，Neo4j,OrientDB,DEX,Infinite Graph;
• 以圖頂點為中心的，基于消息傳遞批處理的并行引擎；如,GoldenOrb,Giraph,Pregel,Hama;
• 共同特點：BSP 模型；
  • BSP(Bulk Synchronous Parallel Computing Mode) 模型叫整體同步并行計算模型或者簡稱為大同步模型．
    　　
    

二. Pregel

2.1 簡介

1.Pregel 是谷歌公司發布的一款商業圖計算產品；

• Caffeine:快速用于大規模網頁索引的構建；
• Dremel:實時性的交互分析產品，是一種只讀嵌套數據的分析，支持分析PB 級別的數據；
• Pregel:基于BSP 模型實現的并行圖計算系統；

2.2 Pregel 圖計算模型

1.有向圖和頂點

2.傳遞消息的基本方法

• 遠程讀取；
• 基于共享內存；
• 基于消息傳遞模型；

3.Pergel 采用消息傳遞模型主要基于以下兩個原因：

• 遠程讀取具有較高的延遲，如MapReduce；
• 消息傳遞采用的是異步的批量的方式傳遞，延遲低；

4.Pregel 的計算過程


5.頂點的狀態

6.Pregel 實例

2.3 Pregel C++ API

• 定義基類Vertex
  

• 消息傳遞機制和Combiner
  頂點之間的通訊是通過消息傳遞機制來實現的，每條消息包含了消息值和需要到達的目標頂點ID.
  在一個超步S 中，一個頂點可以發送任意數量的消息，這些消息將在下一個超步(s+1)中被其他頂點接收．
  Combiner:
  
  
  

• Aggregator，拓撲改變和輸入輸出
  

  • 可以通過Aggregator實現全局協調功能；

  拓撲改變：

  
  輸入輸出:
  

2.3 Pregel體系結構

1.Pregel執行過程

• 用戶程序的執行過程:
  
  • 選擇集群中的多臺機器執行圖計算任務，有一臺及其會被選為Master 其他機器作為Worker;
  • Master把一個圖分成多個分區，并把分區分配到多個Worker,一個Worker會領到一個或多個分區，每個Worker知道所有其他Worker所分配到的分區情況;
    
    
    
    

2.容錯性

3.Worker,Master和Aggregator

• worker　:　一般在執行過程中它的信息保存在內存當中，頂點當前的值，出射邊列表，消息隊列，標志位；worker會對自己所管轄的分區中的每個頂點進行遍歷，并調用頂點上的Compute() 函數，Computer 函數接收頂點當前值，消息迭代器和出射邊迭代器三個參數；
  
  保存兩份，一份用于當前超步，一份用于下一個超步．
  
  

• Master:
  
  
  
  

4.Pregel的應用實例------單源最短路徑

三.Hama的安轉使用

3.1 Hama 簡介

總結

以上是生活随笔為你收集整理的图计算-Pregel-Hama的全部內容，希望文章能夠幫你解決所遇到的問題。

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