advertise
« Stuff The Internet Says On Scalability For November 4, 2011 | Main | Finding the Right Data Solution for Your Application in the Data Storage Haystack »
Thursday
Nov032011

Paper: G2 : A Graph Processing System for Diagnosing Distributed Systems

One of the problems in building distributed systems is figuring out what the heck is going on. Usually endless streams of log files are consulted like ancients using entrails to divine the will of the Gods.

To rise above these ancient practices we must rise another level of abstraction and that's the approach described in a Microsoft research paper: G2: A Graph Processing System for Diagnosing Distributed Systems, which uses execution graphs that model runtime events and their correlations in distributed systems.

The problem with these schemes is viewing applications, written by programmers in low level code, as execution graphs. But we're heading in this direction in any case. To program a warehouse or an internet sized computer we'll have to write at higher levels of abstraction so code can be executed transparently at runtime on these giant distributed computers. There are many advantages to this approach, fault diagnosis and performance monitoring are just one of the wins.

Abstract from the paper:

G2 is a graph processing system for diagnosing distributed systems. It works on execution graphs that model runtime events and their correlations in distributed systems. In G2, a diagnosis process involves a series of queries, expressed in a high-level declarative language that supports both relational and graph-based operators. Each query is compiled into a distributed execution. G2’s execution engine supports both parallel relational dataprocessing and iterative graph traversal.

Execution graphs in G2 tend to have long paths and are in structure distinctly different from other largescale graphs, such as social or web graphs. Tailoredfor execution graphs and graph traversal operations onthose graphs, G2’s graph engine distinguishes itself byembracing batched asynchronous iterations that allowsfor better parallelism without barriers, and by enabling partition-level states and aggregation.

We have applied G2 to diagnosis of distributed systems such as Berkeley DB, SCOPE/Dryad, and G2 itself to validate its effectiveness. When co-deployed on a 60-machine cluster, G2’s execution engine can handle execution graphs with millions of vertices and edges; for instance, using a query in G2, we traverse, filter, and summarize a 130 million-vertex graph into a 12 thousand vertex graph within 268 seconds on 60 machines. The use of an asynchronous model and a partition-level interface delivered a 66% reduction in response time when applied to queries in our diagnosis tasks.

Reader Comments

There are no comments for this journal entry. To create a new comment, use the form below.

PostPost a New Comment

Enter your information below to add a new comment.
Author Email (optional):
Author URL (optional):
Post:
 
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>