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

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

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

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

BSPの概念

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

処理の流れ

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

Step1：始点「東京」は隣接する「名古屋」「大阪」「福岡」へ時間を送信

Step2：名古屋では、現在値∞とメッセージの1より時間を「1」にし、隣接する大阪、福岡へ「1＋それぞれへの時間」を送信。大阪では、現在値∞とメッセージの9より時間を「9」に。福岡では、現在値∞とメッセージの8より時間を「8」にし、隣接する那覇へ「6＋そこへの時間」を送信

Step3：大阪では、現在値「9」とメッセージの2より時間を「2」に。福岡では、現在値「6」とメッセージの4より時間を「6」にし、隣接する那覇へ「4＋そこへの時間」を送信。那覇では、現在値∞とメッセージの8より時間を「8」に

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の実装も検討されているようです。

Hama - a Bulk Synchronous Parallel computing framework on top of Hadoop via kwout

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

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

Welcome To Apache Incubator Giraph via kwout

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

2011.10.14 Apache Giraph - Hortonworks from Avery Ching

View more PowerPoint from Avery Ching

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