Deja Vu: Transparent Checkpoint, Recovery and Migration for Large-Scale Distributed Systems

Students:

• Joseph Ruscio

Component failures are endemic to any large-scale computational resource. As inexpensive computational clusters continue to push the limits of performance and scalability, fundamental issues remain in engendering stability in large-scale cluster systems. The increased component count inherent in cluster-based systems increases the instability of the resource as a whole due to the combinatorial dependency of the integrated system on single-component failure rates. For instance, even if a cluster is based on very high reliability nodes, – where a node has a software or hardware failure once a year – a 1000 node cluster will fail several times a day. Engendering stability in ever growing networked collections of cluster systems needs a systemic software solution that provides reliable access to computing resources.

Deja vu provides an integrated solution to the problem of transparent fault tolerance, which enables large-scale cluster supercomputers to mask hardware, operating system and software failures. The primary contributions of Déjà vu are:

• A transparent parallel checkpointing and recovery mechanism that recovers from any combination of systems failures without any modification to parallel applications
• An online migration subsystem that recovers from failures by migrating failed nodes to "hot-spares". The migration subsystem can be invoked through administrative control or automatically by the queuing system.
• A new algorithm to achieve global state consistency.
• A post-compiler analysis system that transparently instruments the application and captures application state.
• A systems architecture that integrates user-initiated and system-initiated checkpoints in a single framework enabling the effective use of a wide variety of domain specific knowledge.
• Novel runtime mechanisms for transparent incremental checkpointing, to efficiently capture the least amount of state required to maintain global consistency.
• A non-blocking IO architecture for saving checkpoint state. This enables a parallel/distributed application to operate in parallel to checkpoint state storage.
• A communications architecture that enables transparent migration of existing MPI codes without source-code modifications to the application.
• Recoverable IO subsystems that can be tailored to specific storage environments.

Interestingly, Deja Vu's failure recovery model also enables preemptive scheduling in traditionally batch oriented environments. Since Deja Vu can recover from the "all nodes failure" case, a ququeing system can use this mode to preempt a running job and resume from the saved checkpoint at an arbitrary point in time. We are using this approach to develop a preemptive scheduler based on weighted fair queuing.

This work is a joint collaboration with the Pittsburgh Supercomputing Center (integration with distributed storage systems, accounting systems and grid integration) and the Institute for Scientific Research (grid integration).

Current Status (1/15/2005)

• This work is funded by a NSF Medium ITR grant (2003-2007). We thank the National Science Foundation for their support of this work.
• We received a provisional patent in Nov. 2003. An international utility patent was filed in Nov. 2004.
• Commercial development of this work is occuring under an exclusive license agreement between Virginia Tech Intellectual Properties and California Digital Corporation.
• The first prototype was demonstrated at Supercomputing 2004 in Pittsburgh.

Acknowledgements

This work is supported by an NSF medium ITR grant (CNS-0325534). We thank the National Science Foundation for their support.