連載
» 2012年03月22日 00時00分 公開

グラフ問題とバルク同期並列の常識をGiraphで体得ビッグデータ処理の常識をJavaで身につける(5)(2/3 ページ)

[木村幸敏,TIS株式会社 先端技術センター]

グラフ問題に特化したバルク同期並列「Pregel」

 「Pregel」はグラフ問題に特化したソリューションとしてグーグル社で開発され、「Bulk Synchronous ParallelBSPバルク同期並列)」の概念を用います。PregelでSSSP問題をどのように解決できるかを見ていきます。

BSPの概念

 BSPは並列アルゴリズムを実行するための計算モデルで、「superstep」という処理単位を繰り返し実施し、分散環境で問題を解決する概念です。

処理の流れ

 Pregelの考えで、SSSP問題を解決する際の都市間でのデータ授受の流れ(BSPの各superstepにおける処理)を示します(分散環境では、各都市の処理は異なったプロセッサで処理され、スケーラブルな構成になります)。

Step1:始点「東京」は隣接する「名古屋」「大阪」「福岡」へ時間を送信 Step1:始点「東京」は隣接する「名古屋」「大阪」「福岡」へ時間を送信
Step2:名古屋では、現在値∞とメッセージの1より時間を「1」にし、隣接する大阪、福岡へ「1+それぞれへの時間」を送信。大阪では、現在値∞とメッセージの9より時間を「9」に。福岡では、現在値∞とメッセージの8より時間を「8」にし、隣接する那覇へ「6+そこへの時間」を送信 Step2:名古屋では、現在値∞とメッセージの1より時間を「1」にし、隣接する大阪福岡へ「1+それぞれへの時間」を送信。大阪では、現在値∞とメッセージの9より時間を「9」に。福岡では、現在値∞とメッセージの8より時間を「8」にし、隣接する那覇へ「6+そこへの時間」を送信
Step3:大阪では、現在値「9」とメッセージの2より時間を「2」に。福岡では、現在値「6」とメッセージの4より時間を「6」にし、隣接する那覇へ「4+そこへの時間」を送信。那覇では、現在値∞とメッセージの8より時間を「8」に Step3:大阪では、現在値「9」とメッセージの2より時間を「2」に。福岡では、現在値「6」とメッセージの4より時間を「6」にし、隣接する那覇へ「4+そこへの時間」を送信。那覇では、現在値∞とメッセージの8より時間を「8」に
Step4:那覇では、現在値「8」とメッセージの6より時間を「6」に Step4:那覇では、現在値「8」とメッセージの6より時間を「6」に

 単純なMapReduceでのデータ授受の流れと比較しますと、同じような考え方に基づきますが、都市間のグラフ構造に関するデータの授受および繰り返し処理の収束判断の実装が不要となり、処理が効率的に行われることが期待できます。

Pregelを使うには

 では、このPregelは、どのように使えばいいいのでしょうか? 残念ながらPregelは非公開ですので、使用はできません。しかし、この考えを実装したオープンソースとして、以下の2つが存在します。

  1. Giraph:Hadoop環境上で稼働:Hadoop環境上で稼働
  2. JPregel:独自の分散環境で稼働

 このうち今回は、Hadoop環境上で稼働するGiraphに着目します。

コラム 汎用のBSPなら「Hama」もある

ほかに興味深いソリューションとしては、「Hama」があります。Hamaは汎用のBSPを実装し、グラフ問題に特化していないので、今回は紹介の対象から外しています

なお、「[#HAMA-409] Add Pregel-like API - ASF JIRA」によればPregelの実装も検討されているようです。



グラフ問題の現実解「Giraph」

 GiraphでのSSSP問題の解決を見ていくことにより、グラフ問題を効率的に取り扱えることを示します。


 なおGiraphについては、Hadoop Summit 2011の「Giraph:Large-scale graph processing infrastructure on Hadoop」で紹介されているので、参照してみてください。

 次ページでは、いよいよGiraphの処理をコードで見たり、実際に動かします。

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。