Compressed Differences: An Algorithm for Fast Incremental Checkpointing

The overhead of saving checkpoints to stable storage is the dominant performance cost in checkpointing systems. In this paper, we present a complete study of compressed differences, a new algorithm for fast incremental checkpointing. Compressed differences reduce the overhead of checkpointing by saving only the words that have changed in the current checkpointing interval while monitoring those changes using page protection. We describe two checkpointing algorithms based on compressed differences, called standard and online compressed differences. These algorithms are analyzed in detail to determine the conditions that are necessary for them to improve the performance of checkpointing. We then present results of implementing these algorithms in a uniprocessor checkpointing system. These results both corroborate the analysis and show that in this environment, standard compressed differences almost invariably improve the performance of both sequential and incremental checkpointing