A Checkpointing Method with Small Checkpoint Latency

Masato Kitakami, Bochuan Cai, Hideo ItoIEICE Trans. Information and Systems 2008 · DOI

Introduction

In high-dependability computing, checkpointing is a fundamental technique for fault tolerance. It involves periodically saving the system state—including registers, stacks, and memory—to stable storage. In the event of a failure, the system can roll back to the most recent valid checkpoint rather than restarting from scratch.

A critical challenge in checkpointing is balancing two metrics:

  1. Checkpoint Overhead: The duration for which the application must be frozen to initiate the state save.
  2. Checkpoint Latency: The total time elapsed from the start of the checkpointing process until all data is safely committed to disk.

While modern techniques like copy-on-write (COW) effectively minimize overhead, they often suffer from high latency. This creates a "vulnerability window": if a second failure occurs during the latency period, the current checkpoint may be corrupted, forcing a rollback to an even earlier state and doubling the lost computation time. This paper proposes a method to significantly reduce this latency.

Proposed Sub-Checkpointing Methods

The authors introduce the concept of sub-checkpoint intervals. By dividing a standard checkpoint interval into $N$ smaller sub-intervals, the system can proactively save memory pages that are unlikely to be modified again before the main checkpoint.

Two specific algorithms are proposed:

  • Method 1: This approach identifies "stable" pages—those modified in earlier sub-intervals but not in the most recent one. These pages are saved to disk in the background during the current sub-interval.
  • Method 2: This method enhances the first by incorporating a frequency queue ($FQ$). It tracks the modification frequency of pages; those with lower frequencies are prioritized for early saving, as they are statistically less likely to be dirtied again.
Comparison of the two proposed sub-checkpointing methods illustrating the distribution of page saving across sub-intervals.

Experimental Evaluation

The proposed methods were evaluated using a computer simulation of a 128x128 double-float matrix multiplication program. The environment consisted of a master-client model running on Pentium III 700 MHz systems with 500 MB RAM under Solaris 2.8. A 4-minute checkpoint interval was utilized for the tests.

Key Results and Discussion

The simulation results indicate that the proposed methods offer a superior balance between overhead and latency compared to traditional techniques.

  • Latency Reduction: The proposed methods achieved a 25% reduction in checkpoint latency compared to incremental checkpointing, which previously held the record for the smallest latency among existing methods.
  • Comparative Performance: While COW methods offer minimal overhead, their latency exceeded 800ms in the simulation. In contrast, the proposed methods maintained low overhead (~100-150ms) while keeping latency under 200ms.
Performance comparison of various checkpointing methods, highlighting the low latency of the proposed approaches.

The study also revealed a trade-off regarding the number of sub-intervals ($N$). Increasing $N$ generally reduces overhead by distributing the workload, but excessive sub-intervals can eventually increase latency due to the management overhead of frequent sub-tasks.

Conclusion

By leveraging predictive background saving through sub-checkpoint intervals, the proposed methods effectively shrink the vulnerability window associated with checkpoint latency. This approach enhances system reliability without imposing significant overhead. Future work will focus on evaluating these methods across a broader range of applications, particularly those with irregular memory access patterns or heavy I/O requirements.

Summary updated

BibTeX
@article{kitakami2008checkpointing,
  author = {Masato Kitakami and Bochuan Cai and Hideo Ito},
  title = {{A Checkpointing Method with Small Checkpoint Latency}},
  journal = {IEICE Trans. Information and Systems},
  year = {2008},
  doi = {10.1093/ietisy/e91-d.3.857},
}
Figure