大規模なグラフ・データの処理: 最新テクノロジーへのガイド

グラフ構造のビッグ・データを処理するための Apache Giraph、GraphLab、およびその他のオープンソース・システムについて学ぶ

この記事では、Apache Giraph と GraphLab フレームワークを重点に、大規模なグラフ・データを処理するためのオープンソースのソリューションを紹介し、比較します。ソーシャル・ネットワークやナレッジ・ベースなどを扱う最近のアプリケーションでは、グラフ構造のデータが増加しているため、データをまとめて大量に処理することができるスケーラブルなプラットフォームと並列アーキテクチャーが不可欠です。MapReduce はビッグ・データ・アナリティクスで大きな役割を果たすものの、グラフを処理するには最適なプログラミング・モデルではありません。この記事ではその理由を説明した後、グラフの処理という難題に対処するために開発中のシステムを探ります。

Sherif Sakr, Senior Research Scientist, National ICT Australia

Photo of Sherif SakrDr. Sherif Sakr は、オーストラリア・シドニー所在の NICTA (National ICT Australia) のソフトウェア・システム・グループに所属する上級科学研究員です。また、ニューサウス・ウェールズ大学 (UNSW) の The School of Computer Science and Engineering (CSE) で共同上級講師も勤めています。彼は 2007年にドイツのコンスタンツ大学でコンピューター・サイエンスの博士号を取得しており、同じくコンピューター・サイエンスの学士号と修士号は、エジプトのカイロ大学で取得しました。2011年には、米国ワシントン州レドモンドにある Microsoft Research の eXtreme Computing Group (XCG) で客員研究科学者として迎えられました。Dr.Sakr は 2012年にアルカテル・ルーセント社ベル研究所の技術研究スタッフとなりました。



2013年 7月 11日

コンピューター・サイエンスと数学の分野における「グラフ」とは、オブジェクト間の構造的な関係をモデル化する抽象データ構造です。グラフは現在、関係パターンや、ルール、異常を識別することが有効なアプリケーション・ドメインにおいて、データをモデル化するために広く使用されています。これらのドメインには、例えば Web グラフ、ソーシャル・ネットワーク、セマンティック Web、ナレッジ・ベース、タンパク質間相互作用ネットワーク、書誌ネットワークなどがあります。これらのアプリケーションのグラフ構造のデータ・サイズが増大し続けるなか、大量のデータを効率的に処理することができるスケーラブルなシステムが不可欠となっています。

用語解説

隣接リスト (adjacency list): グラフ・データ構造において、グラフの頂点ごとに隣接する頂点の集合を 1 つの順不同リストに記述し、それらのリストをすべての頂点に対して 1 つにまとめて表現したもの。

直径 (diameter): 逆行経路、迂回経路、ループ経路を考慮に入れずに、ある頂点から別の頂点に移動するために横断しなければならない頂点の最大数。

辺 (edge): グラフ内の任意の 2 つの (頂点) の間を接続するもの。

自然グラフ (natural graph): 多数の節の間に接続がほとんどないグラフ、および少数の節の間に多数の接続があるグラフ。

>節 (node): グラフのオブジェクトの 1 つ (頂点と同義)。

PageRank: Google Web 検索エンジンで使用されているリンク分析アルゴリズム。このアルゴリズムでは、ハイパーリンクされた Web グラフの文書セットの各要素に対し、数値による重みを割り当てることにより、セット内での各要素の相対的な重要性を測定することを目的としています。

最短経路アルゴリズム (shortest-path algorithm): グラフ内の 2 つの節 (頂点) 間の経路 (接続) を構成する辺の数が最小となるような経路を検出するプロセス。

頂点 (vertex): グラフのオブジェクトの 1 つ (と同義)。

頂点次数 (vertex degree): 頂点に接続しているの数。

Web グラフ (Web graph): World Wide Web のページ、およびページ間の直接リンクを表現するグラフ。

大規模なグラフの極端な一例として挙げられるのは、Web グラフです。Google の推定では、Web ページの総数は 1 兆を超えており、World Wide Web の実験的なグラフには 200 億の節 (ページ) と1600 億の辺 (ハイパーリンク) が含まれます。別の例としては、ソーシャル・ネットワークのグラフもあります。伝えられるところによると、2012年時点での Facebook のユーザーは 10 億人 (節) を超え、1400 億を超える友達関係 (辺) があります。LinkedIn ネットワークは約 800 万の節と 6000 万の辺で構成されています (ソーシャル・ネットワーク・グラフは急速に拡大しています。Facebook のユーザー数は、2004年には 100 万人ぐらいでしたが、2012年には 10 億人にまで急増しました)。セマンティック Web のコンテキストでは、(ウィキペディアから派生した) DBpedia のオントロジーには、現在 370 万のオブジェクト (節) と 4 億のファクト (辺) が含まれています。

グラフ・データのオンライン・トランザクション処理のワークロードをサポートするグラフ・データベース・システムは、いくつかありますが、そのなかで最も傑出しているのが Neo4j です (「参考文献」を参照)。しかし、Neo4j ではデータの局所性を考慮せずに、グラフのデータにアクセスするメソッドを利用することから、グラフの処理にはほとんどの場合にランダム・データ・アクセスが必要になります。メモリー内に保管できない大きなグラフの場合には、ランダム・ディスク・アクセスがパフォーマンスのボトルネックになります。しかも、Neo4j は、集中型のシステムであり、分散並列システムの計算処理を行う能力はありません。大規模なグラフの場合、グラフを複数のパーティションに分割して複数のマシンに分散しなければ、スケーラブルな処理を実現することは不可能です。

Google の MapReduce フレームワークを使用すれば、汎用的なコンピューター・クラスターが大規模なデータの処理を単一パスで実行するようにプログラミングすることができます。Neo4j とは異なり、MapReduce はオンライン・クエリー処理をサポートするようには設計されていません。MapReduce は、パーティション化された大規模なデータを数百台のマシンで分析するように最適化されています。大規模なデータ・セットを分散処理するためのオープンソースのフレームワークとして、この MapReduce 実装が組み込まれた Apache Hadoop は、その単純さとスケーラビリティーにより、産業界および学界でよく使用されています。

けれども、Hadoop とその関連するテクノロジー (Pig や Hive など) は、グラフ構造のデータのスケーラブルな処理をサポートすることを主な目的として設計されているわけではありません。この目的に MapReduce (または Hadoop) フレームワークを適応させるために提案されているプロジェクトはいくつかあります。この記事ではまず、その中の 2 つを見ていくことから始めます。大規模なグラフ処理に利用できる最も堅牢なテクノロジーは、MapReduce 以外のプログラミグ・モデルをベースとしています。そのようなシステムとして、記事の残りでは次の 2 つのシステムについて詳しく説明し、これらの比較を行います。

  • Giraph: この耐障害性を備えた分散システムは、バルク同期並列プログラミング・モデルを採用し、並列アルゴリズムを実行して大規模なグラフ・データの処理を行います。
  • GraphLab: C++ で作成された、グラフ・ベースのハイパフォーマンス分散コンピューティグ・フレームワークです。

この記事の最後では、グラフ・データ処理を目的とした他のオープンソース・プロジェクトについても簡単に説明します。記事では、読者がグラフの概念と用語を十分理解していることを前提とします。そうではない読者のために、用語の解説を記載しておきます。

MapReduce と大規模なグラフの処理

Surfer と GBASE

実験的な大規模グラフ処理エンジンである Surfer は、プログラマーに「MapReduce」と「伝搬」という 2 つのプリミティブを提供します。MapReduce は、複数のキーと値のペアを並列処理します。伝搬は、グラフ内の頂点から辺に沿って隣接する頂点に情報を転送する反復型計算パターンです。MapReduce はフラットなデータ構造 (頂点を主体とするタスクなど) の処理に適している一方、伝搬はパーティション化されたグラフでの辺を主体とするタスクに合わせて最適化されています。Surfer は、ネットワーク・トラフィックのボトルネックを解決する手段として、Hadoop 分散環境の特性に適応させたグラフ・パーティショニング手法を用いています。Surfer ではまた、グラフ・パーティショニング・プロセスの可変帯域幅要件を、一様ではないネットワーク帯域幅に適応させる、帯域幅認識メカニズムを適用します。

提案されている MapReduce 拡張には、GBASE もあります。GBASE は、ブロック圧縮と呼ばれるグラフ・ストレージ・メソッドを使用して、グラフの同質領域を効率的に保管します。その上で、GZip などの標準圧縮メカニズムによって、空でないすべてのブロックを圧縮します。そして最後に、圧縮されたブロックをメタ情報と一緒にグラフ・データベースに保管します。

GBASE の主要な機能は、節ベースのクエリーと辺ベースのクエリーをクエリー・ベクトルとして統合し、隣接行列と接続行列での、行列とベクトルの乗算によって、グラフに対する各種の操作を統合するというものです。この機能により、GBASE はさまざまなタイプのグラフ・クエリーをサポートすることができます。クエリーは、グラフ全体を横断しなければならないグローバル・クエリーと、通常はグラフの一部のみにアクセスするターゲット指定クエリーに分類されます。GBASE は行列とベクトルの乗算を実行する前に、入力クエリーに関係するブロックが含まれるグリッドを選択します。したがって、GBASE が実行する Hadoop ジョブにフィードされるのは、選択されたグリッドに対応するファイルだけです。

MapReduce プログラミング・モデルでは、Map 関数がキーと値のペアを入力として取り、一連の中間キー/値ペアを生成します。MapReduce フレームワークは、同じ中間キーに関連付けられたすべての中間値をグループ化して Reduce 関数に渡します。すると、Reduce 関数は受け取った中間キーとその値一式を 1 つにマージします。

実装レベルでは、中間キー/値ペアがメモリー内のバッファーに入れられます。バッファーに入れられたペアは、定期的にローカル・ディスクに書き込まれ、パーティショニング関数によって複数の領域にパーティション化されます。バッファーに入れられたペアがローカル・ディスク上に書き込まれている場所は、指定のマスター・プログラム・インスタンスに渡されます。マスター・プログラム・インスタンスの役割は、これらのペアの場所を reduce ワーカーに転送することです。reduce ワーカーは、ペアの場所を知らされると、バッファーに入れられたデータを map ワーカーのローカル・ディスクから読み取ります。その後、バッファーに入れられたデータは、中間キーを基準にソートされて、同じキーのすべてのオカレンスがグループ化されます。reduce ワーカーは、キーとそれに対応する中間値の一式をユーザーの Reduce 関数に渡します。この Reduce 関数の出力は、該当する reduce パーティションの最終出力ファイルに追加されます。

MapReduce を使用することで、アプリケーション開発者は、分散プログラムを実行する上での詳細 (データ分配、スケジューリング、耐障害性などの問題) を気にする必要がなくなりますが、グラフ処理の観点では、基本的な MapReduce プログラミング・モデルは適切ではありません。それは、ほとんどのグラフ・アルゴリズムは反復型であり、何らかの方法でグラフを横断するためです。したがって、グラフ構造がネットワークで何度も繰り返し送信されることから、グラフ計算の効率はプロセッサー間の帯域幅に大幅に依存します。例えば、基本的な MapReduce プログラミング・モデルは、反復型データ分析アプリケーションを直接はサポートしません。反復型プログラムを実装するには、プログラマーは手動で複数の MapReduce ジョブを発行して、これらのジョブの実行をドライバー・プログラムによってオーケストレーションすることになるかもしれません。実際には、MapReduce での反復型プログラムの手動によるオーケストレーションには、以下の 2 つの重要な問題があります。

  • ある反復と次の反復との間でほとんどのデータが変更されないとしても、反復のたびにデータをリロードして再処理しなければならないため、I/O、ネットワーク帯域幅、プロセッサー・リソースが無駄に使用されます。
  • 終了条件には、修正ポイントに達したことを検出することが含まれるかもしれません。条件自体にも、反復のたびに追加の MapReduce ジョブが必要になるかもしれません。したがって、追加タスクのスケジューリング、ディスクからの追加データの読み取り、ネットワーク全体でのデータの移動という点でも、リソースの使用が増加します。

グラフの処理を効率化するために提案されている MapReduce 拡張の例には、Surfer と GBASE があります (技術的な要約については、「Surfer と GBASE」を参照してください。「参考文献」には、これらの拡張を提案する完全な論文へのリンクが記載されています)。ただし、この 2 つの提案に見込まれている成功には限りがあります。

  • (主に、辺を主体とするタスクで) ターゲット・アプリケーションのアクセス・パターンと伝搬のアクセス・パターンが一致していれば、Hadoop のユーザー定義関数と比べ、Surfer の伝搬ベースの実装はプログラムで制御しやすく、より効率的です。一方、(例えば、頂点を主体とするタスクで) タスクと伝搬のアクセス・パターンが一致していない場合、伝搬によるターゲット・アプリケーションの実装は大変な作業になります。
  • ほとんどの開発者にとって、GBASE は直観的とは言えないため、行列の観点でグラフ処理を考えるのは難解だと思うかもしれません。さらに、各反復は別個の Hadoop ジョブとしてスケジューリングされるため、ワークロードが増大します。グラフ構造がディスクから読み取られる場合、ディスクに対して map 出力がはき出され、中間結果が HDFS (Hadoop Distributed File System) に書き込まれてしまいます。

このように、水平スケーリング可能な汎用マシンのクラスター上で大規模なグラフ・データのスケーラブルな処理を実質的にサポートできる分散システムが、相変わらず不可欠です。このニーズに対応するために提案されているのが、Giraph と GraphLab という 2 つのプロジェクトです。


Giraph

2010年、Google はグラフ・アルゴリズムを実装するためのスケーラブルなプラットフォームとして、Pregel システムを導入しました (「参考文献」を参照)。頂点主体の手法を利用する Pregel は、バルク同期並列 (BSP) モデル (「参考文献」を参照) から発想を得ています。2012年には、Pregel の概念をそっくりそのまま模造した Apache Giraph がオープンソース・プロジェクトとして立ち上がりました。Giraph は、Hadoop クラスター・インフラストラクチャーを使用する標準的な Hadoop ジョブとして実行することができます。

Giraph が動作する仕組み

Giraph でのグラフ処理プログラムは、「スーパーステップ」と呼ばれる反復のシーケンスとして表現されます。スーパーステップでは、各頂点に対してユーザー定義関数が (概念上は並列に) 実行されます。ユーザー定義関数は、頂点 V におけるスーパーステップ S での振る舞いを指定します。この関数は、スーパーステップ S-1 で V に送信されたメッセージを読み取ったり、スーパーステップ S+1 で受信される他の頂点へのメッセージを送信したり、V とその出力辺の状態を変更したりすることができます。通常、メッセージは出力辺に沿って送信されますが、既知の ID を持つ頂点であれば、どの頂点にでもメッセージを送信することができます。各スーパーステップは、並列計算のアトミック単位を表します。図 1 に、BSP プログラミング・モデルの実行メカニズムを図解します。

図 1. BSP プログラミング・モデル
BSP プログラミング・モデルの図

このプログラミング・モデルでは、実行プログラムのスーパーステップ 1 で、すべての頂点がアクティブ状態に設定されます。すべてのアクティブな頂点は、それぞれのスーパーステップで compute() ユーザー関数を実行します。

各頂点は、メッセージを受信すると、任意のスーパーステップで、停止を選択することにより自らを非アクティブにして、非アクティブ状態に遷移することができます。頂点は、後続のスーパーステップの実行中にメッセージを受信すると、アクティブ状態に復帰することができます。図 2 に示されているこのプロセスは、どの頂点にも送信するメッセージがなくなり、すべての頂点が非アクティブになるまで続きます。したがって、プログラムの実行が終了するのは、すべての頂点が非アクティブ状態になった時点です。

図 2. 頂点での停止の選択
頂点での停止の選択を示す図

図 3 に、頂点の最大値を計算するために一連のグラフの頂点間で受け渡されるメッセージの例を示します。

図 3. 頂点の最大値を計算する BSP の例
頂点の最大値を計算する BSP の例を示す図

図 3 のスーパーステップ 1 で、各頂点はそれぞれが持つ値を隣接する頂点に送信します。スーパーステップ 2 では、各頂点がそれぞれの値を、隣接する頂点から受信した値と比較します。受信した値が頂点の値より大きい場合、その頂点は値を大きいほうの値で更新し、更新した新しい値を隣接する頂点に送信します。受信した値が頂点の値より小さい場合には、頂点は現在の値を維持して停止を選択します。したがって、スーパーステップ 2 では、値 1 を持つ頂点だけがその値を、受信した値 (5) へと更新して、その新しい値を送信します。このプロセスは、スーパーステップ 3 で値 2 を持つ頂点に対しても行われますが、スーパーステップ 4 ではすべての頂点が停止を選択して、プログラムが終了します。

Hadoop フレームワークと同様に、Giraph は、何千もの汎用コンピューターで構成されるクラスター上での、効率的かつスケーラブルで耐障害性を備えた実装です。しかも、分散関連の詳細は抽象化の背後に隠されます。計算を実行するマシン上で、Giraph は頂点と辺をメモリー内に保持し、メッセージにのみネットワーク転送を使用します。このモデルは、スーパーステップ内の実行順序を検出するメカニズムを見せないこと、そしてすべての通信はスーパーステップ S からスーパーステップ S+1 に対して行われることから、分散実装には最適です。プログラムの実行中、グラフの頂点はパーティション化されて、ワーカーに割り当てられます。デフォルトのパーティショニング・メカニズムは、ハッシュによるパーティショニングですが、カスタムのパーティショニングもサポートされます。

Giraph が適用するマスター/ワーカー・アーキテクチャーを図 4 に示します。

図 4. Giraph のマスター/ワーカーの実行ステップ
Giraph のマスター/ワーカーの実行ステップを説明する図

マスター・ノードはパーティションを各ワーカーに割り当て、同期化の調整を行い、チェック・ポイントを要求して、ヘルス・ステータスを収集します。Giraph は Hadoop と同じく、同期化のために Apache ZooKeeper を使用します。頂点の処理はワーカーが行います。ワーカーは、アクティブな頂点に対して compute() 関数を実行します。また、他の頂点に対するメッセージの送信、受信、割り当ても行います。実行中に、ワーカーが処理対象以外の頂点に対する入力を受信した場合には、その入力を転送します。

Giraph の実際の動作

Giraph プログラムを実装するには、アルゴリズムを Vertex として設計します。各 Vertex は、数多くの既存のクラス (BasicVertexMutableVertexEdgeListVertexHashMapVertex、および LongDoubleFloatDoubleVertex など) の 1 つのインスタンスにすることができます。グラフの読み取りには、VertexInputFormat を定義しなければなりません (例えば、隣接リストのテキスト・ファイルを読み取る場合は、(vertex, neighbor1, neighbor2) のようなフォーマットになります)。また、結果を書き込むための VertexOutputFormat を定義する必要もあります (例えば、(vertex, pageRank) など)。

リスト 1 の Java コードは、compute() 関数を使用して PageRank アルゴリズムを実装する例です。

リスト 1. Giraph での PageRank アルゴリズム
public class SimplePageRankVertex extends Vertex<LongWritable, DoubleWritable, 
                            FloatWritable, DoubleWritable> {
    public void compute(Iterator<DoubleWritable> msgIterator) {
        if (getSuperstep() >= 1) {
            double sum = 0;
            while (msgIterator.hasNext()) {
                sum += msgIterator.next().get();
            }
            setVertexValue(new DoubleWritable((0.15f / getNumVertices()) + 0.85f * sum);
        }
        if (getSuperstep() < 30) {

            long edges = getOutEdgeIterator().size();
            sentMsgToAllEdges(new DoubleWritable(getVertexValue().get() / edges));
        } else {
            voteToHalt();
        }
    }

リスト 2 には、compute() 関数を使用して最短経路アルゴリズムを実装する例を記載します。

リスト 2. Giraph での最短経路
public static class ShortestPathVertex extends Vertex<Text, IntWritable, IntWritable> {
     public void compute(Iterator<IntWritable> messages) throws IOException {
      int minDist = isStartVertex() ? 0 : Integer.MAX_VALUE;
      while (messages.hasNext()) {
         IntWritable msg = messages.next();
         if (msg.get() < minDist) {
            minDist = msg.get();
         }
      }
      if (minDist < this.getValue().get()) {
         this.setValue(new IntWritable(minDist));
         for (Edge<Text, IntWritable> e : this.getEdges()) {
            sendMessage(e, new IntWritable(minDist + e.getValue().get()));
         }
      } else {
         voteToHalt();
      }
   }
}

GraphLab

GraphLabは、C++ で作成されたグラフ・ベースの分散コンピューティグ・フレームワークです。このプロジェクトは 2009年にカーネギー・メロン大学で開始されました。GraphLab は、上位レベルのプログラミング・インターフェースを通じて、スパース反復型グラフ・アルゴリズムを対象とした並列プログラミングの抽象化を実現します。各 GraphLab プロセスは、最近のクラスター・ノードで使用可能なマルチコア・リソースをフル活用するためにマルチスレッド化されます。GraphLab は、Posix および HDFS ファイルシステムの両方に対する読み取りと書き込みをサポートしています。

GraphLab が動作する仕組み

非同期分散型共有メモリーの抽象化である GraphLab では、グラフの頂点はすべての頂点と辺に保管されるデータを使用して、分散グラフへのアクセスを共有します。このプログラミング抽象化では、各頂点が辺の方向に関係なく、現在の頂点、隣接する辺、および隣接する頂点に関する情報に直接アクセスすることができます。

GraphLab 抽象化を構成する主な 3 つの要素は、データ・グラフ、更新関数、同期操作です。データ・グラフは、ユーザーが変更可能なプログラムの状態を表し、可変のユーザー定義データの保管、およびスパース計算による依存関係のエンコードの両方を行います。更新関数は、ユーザーによる計算処理を表すとともに、重複する小さなコンテキスト (「スコープ」と呼ばれます) の中でデータを変換することによってデータ・グラフを操作します。

GraphLab 実行モデルは実行時に、効率的な分散実行を可能にするために、共有メモリーの実行順序の要件を緩和し、GraphLab ランタイム・エンジンが頂点の最適な実行順序を判断できるようにしています。例えば、ある関数は、ネットワーク通信または待ち時間が最小限になるような順序を選択して、頂点を返すかもしれません。GraphLab の抽象化が課す唯一の要件は、最終的にすべての頂点が実行されることです。メッセージを排除することにより、GraphLab はユーザー定義アルゴリズムをデータの移動から切り離し、システムがプログラムの状態を遷移させるタイミングと方法を選択できるようにします。GraphLab では、可変データを頂点と辺の両方に関連付けられるようにすることで、アルゴリズムの設計者が、隣接しているすべてのものの間で共有されるデータ (頂点データ) を、隣接している特定の 1 つのものとの間で共有されるデータ (辺データ) と、より正確に区別できるようにします。また、GraphLab 抽象化では、頂点データまたは辺データに加えられた変更が、隣接する頂点にも自動的に見えるようにすることで、収集フェーズおよび分散フェーズにおける通信の側面を暗黙的に定義します (次のセクション「GraphLab の実際の動作」を参照)。もう 1 つ重要な点として、GraphLab は辺の方向の違いを区別しません。

概して、非同期実行の振る舞いはマシンの数とネットワーク・リソースの可用性に依存することから、アルゴリズムの設計とデバッグを複雑にしがちな非決定性がもたらされます。しかし GraphLab 抽象化のシーケンシャル・モデルは、複数のプロセッサーが同じグラフの同じループを実行できるようにするとともに、複数の異なる頂点を同時に削除および実行できるようにすることによって、実際には自動的に並列実行に変換されます。シーケンシャルな実行動作を維持するには、GraphLab は、内容が重なる計算が同時に実行されることがないようにしなければなりません。この課題に対処するために、GraphLab では直列化が可能となるように自動的に強制することで、頂点を主体とするプログラムのすべての並列実行には、それに対応するシーケンシャルな実行が存在するようにします。直列化が可能となる状況を実現するために、GraphLab ではすべての隣接する頂点でシーケンシャルにロックを取得することを要件とするきめ細かいロック・プロトコルを使用することで、複数の隣接する頂点のプログラムが同時に実行されるのを防ぎます。さらに、GraphLab で使用されているロック・スキームは、次数の高い頂点については、他と同じように扱うことはしません。

GraphLab の実際の動作

GraphLab プログラムは、グラフの頂点で実行され、以下の 3 つの実行フェーズからなる小規模なプログラムであると考えてください。

  1. 収集フェーズ: 頂点クラスの gather() 関数が、頂点に隣接する各辺に対して呼び出され、各辺で収集した値を返します。
  2. 適用フェーズ: 収集関数によって返された一連の値が合計されて、頂点クラスの apply() 関数に渡されます。
  3. 分散フェーズ: 頂点クラスの scatter() 関数が、再び頂点に隣接する各辺に対して呼び出されます。

リスト 3 の C++ コードは、GraphLab で PageRank アルゴリズムを実装する例です。

リスト 3. GraphLab での PageRank アルゴリズム
class pagerank_program :
            public graphlab::ivertex_program<graph_type, double>,
            public graphlab::IS_POD_TYPE {
public:
  // we are going to gather on all the in-edges
  edge_dir_type gather_edges(icontext_type& context,
                             const vertex_type& vertex) const {
    return graphlab::IN_EDGES;
  }
  // for each in-edge, gather the weighted sum of the edge.
  double gather(icontext_type& context, const vertex_type& vertex,
               edge_type& edge) const {
    return edge.source().data().pagerank / edge.source().num_out_edges();
  }
  
  // Use the total rank of adjacent pages to update this page 
  void apply(icontext_type& context, vertex_type& vertex,
             const gather_type& total) {
    double newval = total * 0.85 + 0.15;
    vertex.data().pagerank = newval;
  }
  
  // No scatter needed. Return NO_EDGES 
  edge_dir_type scatter_edges(icontext_type& context,
                              const vertex_type& vertex) const {
    return graphlab::NO_EDGES;
  }
};

Giraph と GraphLab の比較

Pregel と GraphLab はいずれも、頂点を主体とするプログラムの 3 つの概念的フェーズを表す GAS (Gather (収集), Apply (適用), Scatter (分散)) を適用しますが、情報を収集して、それを広める方法については違いがあります。特に、Pregel と GraphLab は GAS プログラムをそれぞれに異なる方法で表現します。Pregel 抽象化の場合、収集フェーズはメッセージ・コンバイナーを使用して実装され、適用フェーズと分散フェーズは頂点クラスで表現されます。逆に、GraphLab は頂点主体のプログラムに隣接しているすべてのものを公開し、ユーザーがプログラム内に収集フェーズと適用フェーズを定義できるようにしています。GraphLab 抽象化では、頂点データまたは辺データに加えられた変更が自動的に隣接する頂点にも見えるようにすることで、収集フェーズおよび分散フェーズにおける通信の側面を暗黙的に定義します

Pregel と GraphLab には、動的計算を表現する方法に関しても違いがあります。GraphLab は、以降に行われる計算のスケジューリングを、データの移動から切り離します。例えば、GraphLab の更新関数は、隣接する頂点が最新の更新をスケジューリングしなかったとしても、その隣接する頂点のデータにアクセスします。それとは対照的に、Pregel の更新関数はメッセージによって開始され、そのメッセージ内のデータにだけアクセスできるため、表現できる内容が制限されます。

Pregel と GraphLab は、通信を最小限に抑えて確実に作業のバランスを取るために、グラフ・パーティショニングを利用するという点では共通しています。ただし、自然グラフの場合には、どちらもハッシュ・ベースの (ランダム) パーティショニングに頼らざるを得ず、局所性が損なわれる可能性があります。Pregel と GraphLab は、大規模グラフ処理システムの新たな波が到来する前触れの中心にあるものと見なされていますが、どちらのシステムにも、パフォーマンス改善の余地があります。大規模なグラフ・データ・セットのさまざまなアプリケーション・ドメインで、この 2 つのプロジェクトの長所と短所を評価および比較する真剣な取り組みは、まだ始まってはいません。


まとめ

Giraph と GraphLab は、グラフ・データのビッグ・データ・アナリティクスを実装するための新しいモデルを提供します。この 2 つのプロジェクトは、ビッグ・データ処理のエコシステムの中で、今後もかなり関心を持たれ続けるはずです。その一方で、以下のオープンソース・プロジェクトでも Pregel の概念が模造されているので、調べてみることをお勧めします (「参考文献」のリンクを参照)。

  • Apache Hama: Giraph と同じく、Hadoop インフラストラクチャーをベースに実行されるように設計されています。ただし、その重点は汎用 BSP 計算に置かれているため、グラフ専用ではありません (例えば、行列反転および線形代数のためのアルゴリズムが組み込まれています)。2013年 4月に Hama のバージョン 0.6.1 がリリースされました。
  • GoldenOrb: この比較的新しいプロジェクト (この記事を執筆している時点でのバージョンは 0.1.1) は、Pregel の API を提供しますが、既存の Hadoopインフラストラクチャーに追加ソフトウェアをデプロイする必要があります。
  • Signal/Collect: 同様の Pregel プログラミング・モデルの手法を適用する一方、Hadoop インフラストラクチャーからは切り離されています。

Pregel 以外の領域では、Hadoop をベースに実装されている大規模グラフ・マイニング・ライブラリー、PEGASUS もあります。PEGASUS は、グラフの直径や各節の半径を計算したり、行列とベクトルの乗算の生成によって連結されたコンポーネントを検出したりするなど、標準的なグラフ・マイニング・タスクをサポートします。

参考文献

学ぶために

製品や技術を入手するために

  • Giraph: Apache ミラー・サイトから Giraph をダウンロードしてください。
  • GraphLab: GraphLab をダウンロードしてください。
  • IBM ソフトウェア評価版を試し、次のオープンソース開発プロジェクトには開発者専用ソフトウェアを使って革新してください。IBM ソフトウェア評価版は、ダウンロードまたは DVD で入手できます。
  • IBM developer kits のダウンロード: システムを更新して、最新のツールとテクノロジーを入手してください。

議論するために

  • developerWorks コミュニティー: ここでは他の developerWorks ユーザーとのつながりを持てる他、開発者によるブログ、フォーラム、グループ、Wiki を調べることができます。

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Open source
ArticleID=936549
ArticleTitle=大規模なグラフ・データの処理: 最新テクノロジーへのガイド
publish-date=07112013