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

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

分布式系统检查点算法中程序卷回时文件系统的状态恢复

检查点技术,也称为“回溯恢复”,是软件容错的重要手段,它主要用于保存和恢复程序的运行状态。在分布式计算和并行计算系统中有十分重要的作用。该文从减少检查点的开销角度,对分布式系统检查点算法中关于程序卷回时文件系统状态的恢复问题进行了分析讨论和进一步的研究。     

一种基于检查点的并行程序调试器的设计与实现

为支持大规模长时间运行并行程序的调试，有必要将检查点机制引入到并行程序调试器中，检查点设置与卷回应用中需要解决中途消息，孤儿消息和多米诺效应，活锁4个问题，并行程序调试中需要解决不确定性问题，提出的基于状态冻结的确定性检查点设置方法，可以避免检查点应用中孤儿消息和多米诺效应，活锁3个问题，通过消化记录的方法处理中途消息问题，采用记录／重放方法解决并行调试中的不确定性问题，基于状态冻结的确定性检查点设置方法，有效地解决了并行程序调试器和检查点结合时产生的诸多问题，该方法具有结构清晰，易于实现的优点，基于此技术，设计并实现了一个并行调试工具－DENNET。     

支持移动合作实时事务的一种新的协同检验点算法

现有的协同检验点方法在移动环境中会带来较大的检验点过程延时 ,不能很好地支持实时事务处理 .提出了一种新的协同并行检验点方法 ,在正常的消息传输过程中 ,通过一点额外的带宽传送事务间检验点依赖关系 ;在某一事务记检验点时 ,尽可能地同时通知相关的事务记检验点 .实验表明 ,该算法对网络带宽没有明显的增加 ,而能大大降低事务记检验点的延时 ,使系统中超截止期的事务比例大大降低     

Optimizing checkpoint-based fault-tolerance in distributed stream processing systems: Theory to practice

Fault-tolerance is an essential part of a stream processing system that guarantees data analysis could continue even after failures. State-of-the-art distributed stream processing systems use checkpointing to support fault-tolerance for stateful computations where the state of the computations is periodically persisted. However, the frequency of performing checkpoints impacts the performance (utilization, latency, and throughput) of the system as the checkpointing process consumes resources and time that can be used for actual computations. In practice, systems are often configured to perform checkpoints based on crude values ignoring factors such as checkpoint and restart costs, leading to suboptimal performance. In our previous work, we proposed a theoretical optimal checkpoint interval that maximizes the system utilization for stream processing systems to minimize the impact of checkpointing on system performance. In this article, we investigate the practical benefits of our proposed theoretical optimal by conducting experiments in a real-world cloud setting using different streaming applications; we use Apache Flink, a well-known stream processing system for our experiments. The experiment results demonstrate that an optimal interval can achieve better utilization, confirming the practicality of the theoretical model when applied to real-world applications. We observed utilization improvements from 10% to 200% for a range of failure rates from 0.3 failures per hour to 0.075 failures per minute. Moreover, we explore how performance measures: latency and throughput are affected by the optimal interval. Our observations demonstrate that significant improvements can be achieved using the optimal interval for both latency and throughput.     

Modular Checkpointing for Atomicity

Transient faults that arise in large-scale software systems can often be repaired by re-executing the code in which they occur. Ascribing a meaningful semantics for safe re-execution in multi-threaded code is not obvious, however. For a thread to correctly re-execute a region of code, it must ensure that all other threads which have witnessed its unwanted effects within that region are also reverted to a meaningful earlier state. If not done properly, data inconsistencies and other undesirable behavior may result. However, automatically determining what constitutes a consistent global checkpoint is not straightforward since thread interactions are a dynamic property of the program.In this paper, we present a safe and efficient checkpointing mechanism for Concurrent ML (CML) that can be used to recover from transient faults. We introduce a new linguistic abstraction called stabilizers that permits the specification of per-thread monitors and the restoration of globally consistent checkpoints. Global states are computed through lightweight monitoring of communication events among threads (e.g. message-passing operations or updates to shared variables). Our checkpointing abstraction provides atomicity and isolation guarantees during state restoration ensuring restored global states are safe.Our experimental results on several realistic, multithreaded, server-style CML applications, including a web server and a windowing toolkit, show that the overheads to use stabilizers are small, and lead us to conclude that they are a viable mechanism for defining safe checkpoints in concurrent functional programs. Our experiments conclude with a case study illustrating how to build open nested transactions from our checkpointing mechanism.     

Periodicity in optimal hierarchical checkpointing schemes for adjoint computations

We reexamine the work of Aupy et al. on optimal algorithms for hierarchical adjoint computations, where two levels of memories are available. The previous optimal algorithm had a quadratic execution time. Here, with structural arguments, namely periodicity, on the optimal solution, we provide an optimal algorithm in constant time and space, with appropriate pre-processing. We also provide an asymptotically optimal algorithm for the online problem, when the adjoint chain size is not known before-hand. Again, these algorithms rely on the proof that the optimal solution for hierarchical adjoint computations is weakly periodic. We conjecture a closed-form formula for the period. Finally, we assess the convergence speed of the approximation ratio for the online problem through simulations.     

Analysis of Checkpointing for Real-Time Systems

Predictable performance in the event of failuresis of paramount importance in most safety critical real-timesystems. Various hardware as well as software fault-toleranttechniques are employed towards this goal among which checkpointingis a relatively cost-effective scheme. Since checkpointing schemesdepend on time redundancy, they could affect the correctnessof the system by causing deadlines to be missed. This paper providesexact schedulability tests for fault tolerant task sets undera specified failure hypothesis and employing checkpointing toassist in fault recovery. The effects of checkpointing strategieson task response time are analysed and some insights for optimalcheckpointing are provided. The emphasis here is on utilizingthis analysis as an off-line design support tool.     

基于作业进展描述的计算网格作业检查点

分析了计算网格环境中实现检查点机制的特殊性,提出了一种新的应用级检查点方法：基于作业进展描述的检查点方法。介绍了这种检查点方法的基本思想,定义了构成作业进展描述的作业进展状态对象和作业进展描述对象,这些对象的方法构成了检查点API;讨论了检查点作业的构建。