On Fault Tolerance for Distributed Iterative Dataflow Processing
Authors:
- 3 April 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 29 (8) , 1709-1722
Abstract
Large-scale graph and machine learning analytics widely employ distributed iterative processing. Typically, these analytics are a part of a comprehensive workflow, which includes data preparation, model building, and model evaluation. General-purpose distributed dataflow frameworks execute all steps of such workflows holistically. This holistic view enables these systems to reason about and automatically optimize the entire pipeline. Here, graph and machine learning analytics are known to incur a long runtime since they require multiple passes over the data until convergence is reached. Thus, fault tolerance and a fast-recovery from any intermittent failure is critical for efficient analysis. In this paper, we propose novel fault-tolerant mechanisms for graph and machine learning analytics that run on distributed dataflow systems. We seek to reduce checkpointing costs and shorten failure recovery times. For graph processing, rather than writing checkpoints that block downstream operators, our mechanism writes checkpoints in an unblocking manner that does not break pipelined tasks. In contrast to the conventional approach for unblocking checkpointing (e.g., that manage checkpoints independently for immutable datasets), we inject the checkpoints of mutable datasets into the iterative dataflow itself. Hence, our mechanism is iteration-aware by design. This simplifies the system architecture and facilitates coordinating checkpoint creation during iterative graph processing. Moreover, we are able to rapidly rebound, via confined recovery, by exploiting the fact that log files exist locally on healthy nodes and managing to avoid a complete recomputation from scratch. In addition, we propose replica recovery for machine learning algorithms, whereby we employ a broadcast variable that enables us to quickly recover without having to introduce any checkpoints. In order to evaluate our fault tolerance strategies, we conduct both a theoretical study and experimental analyses using Apache Flink and discover that they outperform blocking checkpointing and complete recovery.Keywords
Funding Information
- German Ministry for Education and Research
- Berlin Big Data Center BBDC (01IS14013A)
This publication has 17 references indexed in Scilit:
- Zorro2015
- Optimistic Recovery for Iterative Dataflows in Action2015
- Fast failure recovery in distributed graph processing systemsProceedings of the VLDB Endowment, 2014
- PregelixProceedings of the VLDB Endowment, 2014
- The Stratosphere platform for big data analyticsThe VLDB Journal, 2014
- Opening the black boxes in data flow optimizationProceedings of the VLDB Endowment, 2012
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- HaLoopProceedings of the VLDB Endowment, 2010
- Parallel K-Means Clustering Based on MapReduce2009
- A first order approximation to the optimum checkpoint intervalCommunications of the ACM, 1974