热门问题
时间线
聊天
视角
Giraph
来自维基百科，自由的百科全书
Remove ads
Giraph 是一個迭代的圖計算系統。 Apache Giraph 是一個Apache項目，用於對大數據執行圖形處理。 Giraph 的目的是為了解決大規模圖的分布式計算問題，能夠通過隱藏分布式和並行計算的細節以及提供一套用於描述圖算法的 API。總的來說，Giraph 擁有了相對好的可擴展性，能夠一定程度降低分布式圖計算的使用門檻。
 |
Remove ads
概述
Giraph 計算的輸入是由點和兩點之間直連的邊所組成的圖，例如，點可以表示人，邊可以表示朋友請求。每個頂點保存一個值，每個邊也保存一個值。輸入不僅取決於圖的拓撲邏輯，也取決於定點和邊的初始值。
計算過程由一序列的迭代進行，在BSP中叫做supersteps。每個頂點都active。在每個superstep中，每個active的頂點觸發用戶提供的計算方法。這些方法實現了將要輸入的圖中執行的圖算法。簡單來說，在設計Giraph算法的時候要像頂點一樣思考。計算方法如下：
- 接受上一個superstep發送給頂點的消息;
- 用消息、定點和伸出的邊的值，可能導致值被修改，發送消息給其它頂點;
計算方法並沒有直接獲取其它頂點的值以及他們的伸出的邊。頂點之間通過傳遞消息來通信。
在我們的單源最短路徑的例子中，一個計算方法是：
（1）從所有收到的消息中計算最小的值；
（2）確定各個節點的當前值大小；
（3）最小的值被接受作為頂點的值；
（4）值和邊的值沿着每一個外出的邊發送。
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();
}
Remove ads
系統架構
系統架構包括Master、Worker、以及Zookeeper。[2]
-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作業。[3]
參考資料
外部連結
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads