MaxCompute:Graph overview

How it works

Graph algorithms are inherently iterative: the property of a vertex depends on the properties of its neighbors, which in turn depend on their neighbors. MaxCompute Graph captures this by repeatedly modifying a graph until a convergence condition is met. Each iteration is called a superstep.

A graph program runs in three phases:

1. Graph loading — A custom GraphLoader reads records from an input table and converts them into vertices and edges. A custom Partitioner then distributes vertices across workers. By default, MaxCompute Graph partitions vertices by hashing each vertex ID modulo the number of workers.

2. Iterative computing — Each superstep traverses all non-halted vertices and any halted vertices that received messages, then calls compute(ComputeContext context, Iterable messages) on each of them. Inside compute(), each vertex can:

   • Process messages sent by the previous superstep.

   • Change the values of vertices or edges.

   • Send messages to other vertices.

   • Add or remove vertices or edges.

   • Use an Aggregator to collect and update global information. For details, see Aggregator implementation mechanism.

   • Set itself to halted or non-halted.

   MaxCompute Graph asynchronously sends messages to the related workers in each superstep. The messages are then processed in the next superstep.

3. Iteration termination — The computation stops when any of the following conditions is true:

   • All vertices are halted (Halted = true) and no new messages have been generated.

   • The maximum number of iterations is reached.

   • The terminate() method of an aggregator returns true.

The following pseudocode shows the full execution flow:

// 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();

Key concepts

Graph data structure

MaxCompute Graph processes directed graphs. Because MaxCompute uses a two-dimensional table storage structure, you must convert graph data into two-dimensional tables before storing it.

During computation, a custom GraphLoader converts the table records back into vertices and edges.

Vertex structure: <ID, Value, Halted, Edges>

Edge structure: <DestVertexID, Value>

The graph above maps to the following two-dimensional table:

The following figure shows how vertices are distributed across two workers during graph loading. Vertex IDs are hashed modulo 2: v0 and v2 (ID modulo 2 = 0) go to Worker 0; v1, v3, and v5 (ID modulo 2 = 1) go to Worker 1.

When you edit a vertex or edge, use code to maintain the relationships between vertices and edges.

What's next

• PageRank

• Single-source shortest path (SSSP) algorithm

• k-means algorithm

• Aggregator implementation mechanism