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

» 2012年03月22日 00時00分 公開
[木村幸敏TIS株式会社 先端技術センター]
前のページへ 1|2|3       

処理コード

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

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

    public void compute(Iterator<DoubleWritable> msgIterator) { //…… 【1】
        if (getSuperstep() == 0) {
            setVertexValue(new DoubleWritable(Double.MAX_VALUE));
        }
        double minDist = isSource() ? 0d : Double.MAX_VALUE;
        while (msgIterator.hasNext()) {
            minDist = Math.min(minDist, msgIterator.next().get()); //…… 【2】
        }
        if (minDist < getVertexValue().get()) { //…… 【3】
            setVertexValue(new DoubleWritable(minDist));
            for (Edge<LongWritable, FloatWritable edge> : getOutEdgeMap().values()) {
                sendMsg(edge.getDestVertexId(),
                        new DoubleWritable(minDist + edge.getEdgeValue().get())); //…… 【4】
            }
        }
        voteToHalt();
    }

  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を用いてコンパイルします。

svn  checkout  http://svn.apache.org/repos/asf/incubator/giraph  giraph

mvn  package

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

JSONArray(<vertex id>, <vertex value>, JSONArray(JSONArray(<dest vertex id>, <edge value>), ...))

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

  [1,10000,[[2,1],[3,9],[4,6]]]
  [2,10000,[[3,1],[4,3]]]
  [3,10000,[]]
  [4,10000,[[5,2]]]
  [5,10000,[]]

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

hadoop dfs -copyFromLocal shortestPathsInputGraph shortestPathsInputGraph

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

hadoop jar giraph-0.2-SNAPSHOT-jar-with-dependencies.jar org.apache.giraph.examples.SimpleShortestPathsVertex shortestPathsInputGraph shortestPathsOutputGraph 1 1

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

hadoop dfs -cat  shortestPathsOutputGraph/part-m-00001

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

  [1,0,[[2,1],[3,9],[4,6]]]
  [2,1,[[3,1],[4,3]]]
  [3,2,[]]
  [4,4,[[5,2]]]
  [5,6,[]]

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

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

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

著者紹介

木村幸敏(きむら ゆきとし)

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

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

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



前のページへ 1|2|3       

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

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

メールマガジン登録

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