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:
- Checkpoint Overhead: The duration for which the application must be frozen to initiate the state save.
- 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.
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.
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