MaxCompute Graph は反復グラフ計算のための処理フレームワークです。 MaxCompute Graph ジョブは、グラフを使用してモデルを構築します。 グラフは Vertex と Edge で構成されており、値を含みます。

MaxCompute Graph は以下のグラフ編集操作をサポートします。
  • Vertex または Edge の値の変更
  • Vertex の追加と削除
  • Edge の追加と削除
注 Vertex と Edge を編集する場合、両者の関係を維持しなければなりません。

このプロセスは、反復グラフ編集と進化を実行した後に最終的な結果を出力します。 典型的なアプリケーションには、PageRank、SSSP アルゴリズム、Kmeans アルゴリズムなどがあります。 MaxCompute Graph が提供するインターフェイスである Java SDK を使用して、グラフ計算プログラムをコンパイルします。

グラフのデータ構造

MaxCompute Graph が処理するグラフは Vertex と Edge で構成される有向グラフでなければなりません。 MaxCompute は 2 次元のストレージ構造のみを提供するため、グラフデータを 2 次元テーブルに変換して MaxCompute に保存する必要があります。

グラフ計算と分析の間に、カスタム Graphloader を使用して、MaxCompute Graph エンジン上の 2 次元のテーブルデータを Vertex と Edge に変換します。 サービスシナリオに基づいてどのようにグラフデータを 2 次元のテーブルに変換するかを決定できます。 サンプルコードでは、テーブル書式はさまざまなグラフデータ構造に対応します。

Vertex 構造は、< ID, Value, Halted, Edges > と表現でき、それぞれ順に ID (vertex ID)、Value (値)、Halted (ステータス。反復を終了するかどうか)、および Edges (Edge セット。Vertex を起点とするすべての Edge のリスト) を示します。Edge 構造は、< DestVertexID, Value > と表現でき、それぞれ宛先の DestVertexID (Vertex) とValue (値) を示します。

たとえば、上のグラフは次の Vertex で構成されています。
Vertex <ID, Value, Halted, Edges>
v0 <0, 0, false, [ <1, 5 >, <2, 10 > ] >
v1 <1, 5, false, [ <2, 3>, <3, 2>, <5, 9>]>
v2 <2, 8, false, [<1, 2>, <5, 1 >]>
v3 <3, Long.MAX_VALUE, false, [<0, 7>, <5, 6>]>
v5 <5, Long.MAX_VALUE, false, [<3, 4 > ]>

Graph プログラムのロジック

グラフのロード

フレームワークはカスタム GraphLoader を呼び出し、入力テーブルのレコードを Vertex または Edge に変換します。

分散アーキテクチャ: フレームワークはカスタム Partitioner を呼び出し、Vertix をパーティション化しそれぞれに対応する Worker へ送信します。 デフォルトのパーティション化ロジック: vertex ID のハッシュ値を計算し Worker 数に対しモジュロ演算を行います。

たとえば、上の図で Worker 数は 2 であるとします。Iv0 と v2 は ID を 2 で割った余りが 0 であるため Worker 0 に割り当てられ、v1、v3、v5 は ID を 2 で割った余りが 1 となるので Worker 1 に割り当てられます。

反復計算
  • 反復のことをスーパーステップと呼びます。 これは、すべての未停止状態 (halted の値が false) の Vertex、またはメッセージを受け取った Vertex (メッセージを受け取った後、停止状態の Vertex は自動的に有効化される) を走査し、compute (ComputeContext context, Iterable messages) メソッドを呼び出します。
  • 実装された compute (ComputeContext context, Iterable messages) メソッドでは、以下の手順に従います。
    • 直前のスーパーステップから現在の Vertex に送信されたメッセージを処理します。
    • 必要に応じてグラフを編集します。
      • Vertex と Edge の値の変更
      • 特定の Vertex にメッセージ送信
      • Vertex または Edge の追加と削除
    • Aggregator を使用してグローバル情報を更新するための情報を収集します。
    • 現在の Vertex を停止または未停止のステータスに設定します。
    • 反復の間、フレームワークは対応する Worker へは非同期でメッセージを送信し、次のスーパーステップでは一切の介入なしでメッセージを処理します。

反復の終了

以下のいずれかの条件に一致した場合、反復を終了します。

  • すべての vertex が停止状態 (Halted の値が true) で、新たなメッセージが生成されていない場合
  • 反復の最大数に達した場合
  • Aggregator の終了メソッドが true を返した場合
擬似コードは次のとおりりです。
// 1. load
for each record in input_table {
  GraphLoader.load();

// 2. setup
WorkerComputer.setup();
for each aggr in aggregators {
  aggr.createStartupValue();

for each v in vertices {
  v.setup();

// 3. superstep
for (step = 0; step < max; step ++) {
  for each aggr in aggregators {
    aggr.createInitialValue();
  
  for each v in vertices {
     v.compute();
   

// 4. cleanup
for each v in vertices {
  v.cleanup();

WorkerComputer.cleanup();