"All roads lead to Rome": optimistic recovery for distributed iterative data processing
"All roads lead to Rome": optimistic recovery for distributed iterative data processing
复制标题
DOI：
10.1145/2505515.2505753
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Sebastian Schelter;Stephan Ewen;K. Tzoumas;V. Markl
中科院分区：
文献类型：
--
作者：
Sebastian Schelter;Stephan Ewen;K. Tzoumas;V. Markl
在大型数据集上执行数据并行迭代算法对于数据挖掘和机器学习领域的许多高级分析应用程序至关重要。当前用于执行大型群集中迭代任务的系统通常通过回滚恢复实现故障公差。这种悲观方法背后的原理是定期检查算法状态。失败后，系统从以前的书面检查点恢复了一致的状态，并从此恢复执行。我们提出了使用算法补偿的乐观恢复机制。我们的方法利用了在数据挖掘和机器学习中使用的大量FIXPOINT算法的强大，自我校正性质，这些算法会从各种中间一致的状态中收集到正确的解决方案。在失败的情况下，我们应用了用户定义的补偿功能，该功能算法从算法创建如此一致的状态，而不是回到先前的检查点状态。我们乐观的恢复无法检查任何状态，因此就保证容错所需的间接开销而实现了最佳的无故障性能。我们说明了这种方法对于三个范围的问题的适用性。此外，我们展示了如何在数据流系统中实现所提出的乐观恢复机制。与MapReduce中的联合收源运算符类似，我们提出的功能是可选的，可以应用于在不更改程序语义的情况下提高性能。在大型数据集的实验评估中，我们表明我们提出的方法提供了最佳的无故障性能。在没有失败的情况下，我们的乐观计划能够以2到5倍的倍数优于悲观的方法。在存在故障的情况下，我们的方法提供了快速恢复，并且在大多数情况下都超越了悲观的方法。
Executing data-parallel iterative algorithms on large datasets is crucial for many advanced analytical applications in the fields of data mining and machine learning. Current systems for executing iterative tasks in large clusters typically achieve fault tolerance through rollback recovery. The principle behind this pessimistic approach is to periodically checkpoint the algorithm state. Upon failure, the system restores a consistent state from a previously written checkpoint and resumes execution from that point. We propose an optimistic recovery mechanism using algorithmic compensations. Our method leverages the robust, self-correcting nature of a large class of fixpoint algorithms used in data mining and machine learning, which converge to the correct solution from various intermediate consistent states. In the case of a failure, we apply a user-defined compensate function that algorithmically creates such a consistent state, instead of rolling back to a previous checkpointed state. Our optimistic recovery does not checkpoint any state and hence achieves optimal failure-free performance with respect to the overhead necessary for guaranteeing fault tolerance. We illustrate the applicability of this approach for three wide classes of problems. Furthermore, we show how to implement the proposed optimistic recovery mechanism in a data flow system. Similar to the Combine operator in MapReduce, our proposed functionality is optional and can be applied to increase performance without changing the semantics of programs. In an experimental evaluation on large datasets, we show that our proposed approach provides optimal failure-free performance. In the absence of failures our optimistic scheme is able to outperform a pessimistic approach by a factor of two to five. In presence of failures, our approach provides fast recovery and outperforms pessimistic approaches in the majority of cases.