検索
連載

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

Hadoopをはじめ、Java言語を使って構築されることが多い「ビッグデータ」処理のためのフレームワーク／ライブラリを紹介しながら、大量データを活用するための技術の常識を身に付けていく連載

[木村幸敏，TIS株式会社 先端技術センター] PC用表示 関連情報
Share
Tweet
LINE
Hatena
前のページへ | 　　　　　　

処理コード

　GiraphはGithubからソースコードをダウンロードできます。

　GiraphにはSSSP問題のサンプルコード「src/main/java/org/apache/giraph/examples/SimpleShortestPathsVertex.java」が付属します。以下、コードの本質部分（BSPのsuperstepにおけるConcurrent Computation処理）を抜粋します（GiraphのWikiも参照ください）。

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

  1. 前Superstepで送信されたメッセージ（隣接都市よりの最短時間の候補）が引数
  2. メッセージ内の最短時間の最小値を見つける。新たな最短時間の候補
  3. 【2】での最小値がいままでの最短時間より小さいときに【4】の処理を実施
  4. 始点からの最短時間を更新し、隣接都市に次のメッセージを送信する（この都市の現在の最短時間＋隣接都市への時間）

　このように、GiraphでSSSP問題を解決するための実装コードは、非常に簡単です。

Giraphの何が優れているのか

　GiraphはPregelの実装なので、SSSP問題を解決するには「compute()」処理に十数行のコードを記述するだけで行えます。このcompute()処理は、「org.apache.hadoop.mapred.MapTask#run」の中で繰り返し実行され、以下のような特徴を持ちます。

  • MapReduceの繰り返しではなく、1回のMap処理内で完結
  • メッセージの送受信はHadoopのRPC機能を用いるのでHDFSアクセスが不要
  • Superstepの繰り返しの収束判断はGiraphが行う

　このため、MapReduceでの単純な解決方法と比較しますと、その欠点がすべて解決され、大規模なグラフ問題も効率的に取り扱えることになります。

Giraphのサンプルを動かしてみよう

　Giraphに付属のSSSP問題のサンプルコードを稼働させる手順を示します。

　まず、「hadoop-1.0.0」の実行間環境を整えて、Hadoopを稼働させます（手順は省略します）。次に、Giraphのソースコードを入手し（ここでは、Subversionを使用）、Mavenを用いてコンパイルします。

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

　都市のグラフ構造を表すデータは、以下のようなJSON形式で用意します。

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

　この際に都市名は、数値で表現するので、次のようなデータになります（最短時間の<vertex value>の初期値は、ここでは有り得ない最大値として、仮に「10000」を用いています）。

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

　このデータをディレクトリ「shortestPathsInputGraph」内のファイルに保存し、HDFSにコピーします。

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

　SSSP問題のサンプルSimpleShortestPathsVertexを実行します。

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

　実行結果はディレクトリ「shortestPathsOutputGraph」に出力されるので、その内容を確認します。

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

　次のように、<vertex value>の欄に最短時間が求まった結果が得られます。

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

実業務のグラフ問題はGiraphで解決

　本稿では、グラフ問題を効率的に解くためのソリューションとしてHadoop上で稼働するGiraphを紹介しましたが、いかがでしたでしょうか。

　グラフ問題は机上レベルでは何も工夫しない単純なMapReduceでも解決できますが、処理効率を考えると、実業務への適応は困難です。グラフ問題を解決するのに、問題の特性にマッチした専用のソリューションGiraphを試してみてはいかがでしょうか。

著者紹介

木村幸敏（きむら ゆきとし）

大規模案件での性能問題にかかわり、アプリのボトルネック特定／解消にかかわる。

また各種FWの適用による生産性向上に取り組む。

TIS先端技術センターでは、採れたての検証成果や知見などをWebサイトで発信中


「次回」へ


「ビッグデータ処理の常識をJavaで身につける」バックナンバー

Copyright © ITmedia, Inc. All Rights Reserved.

前のページへ | 　　　　　　
ページトップに戻る