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

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

処理コード

　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サイトで発信中

「次回」へ

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

• 管理が困難―分散処理の常識はZooKeeperで変わる
• Hadoopの現実解「バッチ処理」の常識をAsakusaで体得
• リアルタイム分散処理の常識をApache S4で身につける
• グラフ問題とバルク同期並列の常識をGiraphで体得
• 試すのが難しい―機械学習の常識はMahoutで変わる
• いまさら聞けないKVSの常識をHbaseで身につける
• 並列分散処理の常識をHadoopファミリから学ぶ
• 検索エンジンの常識をApache Solrで身につける