  Fault tolerance is critical for distributed stream processing systems, yet
achieving error-free fault tolerance often incurs substantial performance
overhead. We present AF-Stream, a distributed stream processing system that
addresses the trade-off between performance and accuracy in fault tolerance.
AF-Stream builds on a notion called approximate fault tolerance, whose idea is
to mitigate backup overhead by adaptively issuing backups, while ensuring that
the errors upon failures are bounded with theoretical guarantees. Specifically,
AF-Stream allows users to specify bounds on both the state divergence and the
loss of non-backup streaming items. It issues state and item backups only when
the bounds are reached. Our AF-Stream design provides an extensible programming
model for incorporating general streaming algorithms as well as exports only
few threshold parameters for configuring approximation fault tolerance.
Furthermore, we formally prove that AF-Stream preserves high algorithm-specific
accuracy of streaming algorithms, and in particular the convergence guarantees
of online learning. Experiments show that AF-Stream maintains high performance
(compared to no fault tolerance) and high accuracy after multiple failures
(compared to no failures) under various streaming algorithms.
