分布式系统中的检查点算法

检查点能够保存和恢复程序的运行状态．它在进程迁移、容错、卷回调试等领域都有重要的应用．本文对分布式系统中的检查点算法进行了详细的分类评述．检查点算法可分为单进程和分布式程序检查点算法，分布式程序检查点算法又可分为异步检查点算法和一致检查点算法．同时本文系统介绍了改进检查点算法性能的典型方法．这些改进算法主要采用两个策略来减少算法的开销与延迟：一是减少检查点文件中需要存储的信息量，如增量算法等；二是提高检查点操作与目标程序运行的并行性，如主存算法等．最后，文章讨论了目前检查点算法的局限性和进一步的工作．

CHECKPOINTING ALGORITHMS IN DISTRIBUTED SYSTEMS

Checkpointing can save and restore programs running state. It is thebackbone of certain program control utilities, such as process migration, fault-tol-erance, and playback debugging, etc. In the paper, existing checkpointing algo-rithms are classified and discussed in detail. Existing checkpointing algorithms areclassified into two broad categories. One is for single-process programs, the otheris for distributed programs. Moreover, the checkpointing algorithms for distributedprograms are classified into also-asynchronous checkpointing algorithms and consis-tent checkpointing algorithms. Furthermore, the typical methods to improve theperformance of checkpointing algorithms are also introduced in the paper, such asincremental checkpoints, CAME, compression, user-directed checkpoints, mainmemory, copy-on-write, and CLL, etc. The first four optimizations reduce theamount of information saved in a checkpoint, and the rest increase the concurrencyof checkpointing by overlapping executing a target program with writing check-points to the disk. Overhead and latency are used to evaluate the performance ofcheckpointing algorithms in the paper. In the end, the paper discusses the commondrawbacks of existing checkpointing algorithms and the future work.