Deterministic Fuzzy Checkpoints
Michael Eischer, Markus Büttner, Tobias Distler · 2019
Replicated systems tolerating arbitrary (Byzantine) faults require periodic and deterministic application-state checkpoints to perform essential tasks such as initializing new replicas, enabling faulty replicas to recover, and garbage-collecting old agreement-protocol messages. Existing techniques to create checkpoints in these systems make it necessary to temporarily suspend request execution in order to capture a consistent checkpoint, causing significant service disruptions for applications with large states. Unfortunately, state-of-the-art approaches from the domain of crash-tolerant systems also are not directly applicable, because the checkpoints they produce are not comparable across replicas and therefore cannot be validated in an environment in which replicas may fail arbitrarily and do not trust each other. In this paper, we address these problems by proposing deterministic fuzzy checkpoints (DFC), a novel technique that enables all correct replicas in a system to create consistent and matching checkpoints in parallel to processing requests. As a consequence, DFC increases service availability while still allowing replicas to verify the correctness of a checkpoint before applying it to their local states. In addition to our general approach, we present different alternatives to implement DFC within a replication library and furthermore discuss support for the creation of differential checkpoints. Experiments with a key-value store show that DFC is able to snapshot states of 3 GB while sustaining high performance throughout the entire checkpointing process.