Lightweight Fault Tolerance


This is an extension of Pregel+ to support fault tolerance. In order to support automatic failure recovery, we require users to deploy ULFM which provides new MPI functions for failure detection and notification. While our heavyweight algorithms can support graph mutation, current prototypes remove the graph mutation functionality of Pregel+ for ease of implementation. The main proposal of this work is a lightweight checkpointing method, where only vertex states are written to a checkpoint and messages are generated from vertex states. We also extend the systems to support log-based fast recovery proposed by this paper.

To illustrate the benefit of lightweight checkpointing, we report the performance of computing PageRank on the WebUK dataset. While one superstep of computaton takes around 30 seconds, writing a conventional checkpoint takes around 60 seconds; on the other hand, it takes only around 2 seconds to write a lightweight checkpoint.



The major procedures are similar to this page. But one needs to replace MPICH with ULFM. A simple note on installing ULFM is given here, and a stable version of ULFM code that we deployed on our own cluster is given here.



System Code

  • Conventional Heavyweight Checkpointing (HWCP) [Download]

  • Lightweight Checkpointing (LWCP) [Download]

  • HWCP with Message Logging (HWLog) [Download]

  • LWCP with Vertex Logging (LWLog) [Download]

Application Code for HWCP and HWLog

Application Code for LWCP and LWLog

We present the format of each line for the input files.

For PageRank: vertexID \t num_of_out_neighbors out_neighbor1 out_neighbor2 ...

For Triangle Counting: vertexID \t num_of_neighbors neighbor1 degree1 neighbor1 degree2 ...

To obtain the format for triangle counting, you may run this program (compiled by ordinary Pregel+ system) to preprocess a file where each line has the following format:

vertexID \t num_of_neighbors neighbor1 neighbor2 ...

Remeber to upload a large local file to HDFS using the data putting program mentioned at the end of this page instead of using "hadoop fs -put".


Running from the Console

The major procedures are similar to this page. For compilation, since our system code uses std::thread from C++11, your g++ version should support C++11, and the option "-std=c++11" is necessary. A sample Makefile to compile your application program can be found here.

Since we are using ULFM instead of MPICH, there are some differences when calling "mpiexec" to run your program. Firstly, to specify the process-to-machine mapping file for the "mpiexec" command, one needs to use the "-hostfile" option to replace "-f". Secondly, one needs to use option "-am ft-enable-mpi" to enable ULFM's fault tolerance functionalities. A sample command of running a compiled program is as follows:

mpiexec -np [number-of-processes] -hostfile [machine-mapping-file] -am ft-enable-mpi ./[compiled-program] [program-arguments]