Giraph

Giraph是一个迵天代的圖計算系統。 Apache Giraph 是一个 Apache 項目，用佇咧對大數據執行的圖形來處理。Giraph 的目的是為著欲解決大規模圖樣的分布式計算問題，會當通過隱藏分佈式佮並行計算的細節佮提供一套用佇咧描述圖算法的 API，總的來講，Giraph 毋但擁有了相對好的擴展性，嘛會當一定程度降低分布式圖計算的使用門坎。

概述

Giraph 計算的輸入是由點佮兩點之間直連的邊所組成的圖，比如講，點會當表示講人，那會當表示朋友請求。每一个頂點來保存一个值，逐家邊仔嘛會保存一个值。輸入毋但取決於圖的拓邏輯，嘛攏著愛決定佮邊仔的初期值。

算過程由一序列迵天的進行，佇咧 BSP 中叫做 supersteps。每一个頂點攏 active。佇每一个 superstep 中，彼每一个 active 的上點觸發用戶提供的計算方法。遮的方法實現將欲輸入的圖中執行的圖算法。直觀講，咧設計 Giraph 算法的時陣愛像頂點仝款思考。算方法如下：

-接受頂一个 superstep 發送予頂點的消息；

-用消息、定點佮伸出的邊仔的值，可能致使值予人修改，發送消息予其他頂點；

計算方法並無直接接提其他頂點的值閣有𪜶的伸出來的邊仔。頂點之間通過傳消息來通信。

佇咱的單源上短路徑的例中，一个計算方法是：

（ 一）對所有收著的消息共算上細的值；

（ 二）確定逐个點節的彼个進前值大細；

（ 三）上細的值予人接受做頂點的值；

（ 四）值和邊仔的值沿每一个出外的邊仔發送。

` ` ` public void compute ( Iterable < DoubleWritable > messages ) { double minDist=Double . MAX _ VALUE ; for ( DoubleWritable message  : messages ) { minDist=Math . min ( minDist , message . get ( ) ) ; } if ( minDist < getValue ( ) . get ( ) ) { setValue ( new DoubleWritable ( minDist ) ) ; for ( Edge < LongWritable , FloatWritable > edge  : getEdges ( ) ) { double distance=minDist + edge . getValue ( ) . get ( ) ; sendMessage ( edge . getTargetVertexId ( ) , new DoubleWritable ( distance ) ) ; } } voteToHalt ( ) ; } ` ` `

系統架構

系統的架構包括 Master、Worker、以及 Zookeeper。

-Master

Master 實質上運行佇 Hadoop 的 MapTask 上，其主要的作用是對輸入圖進行分區、協調 Worker 的活動、維護一份存活的 Worker 列表（包括講 Worker 的標識符、地址信息等等）閣較新 Job 的狀態。

-Worker

Worker 嘛仝款運行佇咧 Hadoop 的 MapTask 上，其主要的作用是維護已經分配圖的狀態。

-Zookeeper

Zookeeper 佇咧 Giraph 中的主要的作用是 Master 選舉、號名服務猶閣有協調服務。

基礎原理

Giraph 是因為 Hadoop 啊若起，將 MapReduce 中 Mapper 進行封裝，沒使用 reducer。佇咧 Mapper 現中進行迵天代，逐改迵天代等價數 BSP 模型中的 SuperStep。一个 Hadoop Job 等價數佇一改 BSP 作業。

外部連結

官方網站

Giraph 基礎介紹-Hama White 的博客

Giraph 簡介-Ikroal 的博客