Pages

Monday, April 29, 2013

Paper Reading "Mizan: A System for Dynamic Load Balancing in Large-scale Graph Processing" EuroSys 2013

Balanced computation and communication is fundamental to the efficiency of a Pregel system. Existing implementations primarily focus on efficient partitioning of input data as a pre-processing step.
(1) Provide simple graph partitioning schemes, like hash- or range- based partitioning (e.g., Giraph).
(2) Allow developers to set their own partitioning scheme or pre-partition the graph data (e.g., Pregel).
(3) Provide more sophisticated partitioning techniques (e.g., GraphLab, GoldenOrb and Surfer use min-cuts).
(4) Utilize distributed data stores and graph indexing on vertices and edges (e.g., GoldenOrb and Hama).
(5) Perform coarse-grained load balancing (e.g., Pregel).

The authors analyze these workload-balancing approaches when applied to a broad range of graph mining problems, and show that - especially when the graph mining algorithm has unpredictable communication needs, frequently changes the structure of the graph, or has a variable computation complexity - a single solution is not enough.

The authors are interested in building a system that is (1) adaptive, (2) agnostic to the graph structure, and (3) requires no a priori knowledge of the behavior of the algorithm.

In summary, the proposed system Mizan:
  • (1) Supports different schemes to pre-partition the input graph.
  • (2) Monitors runtime characteristics of all vertices (i.e.s, their execution time, and incoming and outgoing messages).
  • (3) Using above measurements, at the end of every superstep, Mizan constructs a migration plan that minimizes the variations across workers by identifying which vertices to migrate and where to migrate them to.
  • (4) Performs efficient vertex migration across workers, leveraging a DHT-based location service to track the movement of vertices as they migrate.
The authors firstly divide graph algorithms into two categories:
  • (1) Stationary graph algorithms: active vertices send and receive the same distribution of messages across supersteps, such as, PageRank, diameter estimation and finding weakly connected components. Represented by a matrix-vector multiplication. (PEGASUS shows).
  • (2) Non-stationary graph algorithms: the destination or size of its outgoing messages changes across supersteps, such as, distributed minimal spanning tree construction (DMST), graph queries, and various simulation on social network graphs.
Mizan works like SkewTune. SkewTune steals workload from overload task to other tasks, while Mizan reassigns vertices to workers between supersteps.

Monitoring: the key metrics for every vertex are (1) the number of outgoing messages to other (remote) workers, (2) total incoming messages, and (3) the response time (execution time) during the current superstep.
Migration Planning: Mizan's migration planner finds the strongest cause of workload imbalance among the above three metrics and plans the vertex migration accordingly.
STEP 1: Identify the source of imbalance. Compute the z-score for all workers, z-score = |x_i - x_max| / standard deviation, where x_i is the run time of worker i.
STEP 2: Select the migration objective. Each worker uses the summary statistics to compute the correlation between outgoing messages and response time, and also the correlation between incoming messages and response time. The correlation scores are used to select the objective to optimize for: to balance outgoing messages, balance incoming messages, or balance computation time.
STEP 3: Pair over-utilized workers with under-utilized ones.
STEP 4: Select vertices to migrate. Assume that w_x is a worker that needs to migrate out a number of vertices, and is paired with the receiver w_y. The load that should be migrated to the under-utilized worker equals to half the difference in statistics of the migration objective between the two workers.
STEP 5: Migrate vertices.

Future Work: Mizan's performance can degrade when processing extremely skewed graphs due to frequent migration of highly connected vertices. Vertex replication proposed by PowerGraph offers a good solution, but mandates the implementation of custom combiners. The authors plan to further reduce frequent migrations in Mizan by leveraging vertex replication, however, without requiring any custom combiners.