Towards Log-Less, Fine-Granular State Machine Replication

Abstract

State machine replication is used to increase the availability of a service such as a data management system while ensuring consistent access to it. State-of-the-art implementations are based on a command log to gain linear write access to storage and avoid repeated transmissions of large replicas. However, the command log requires non-trivial state management such as allocation and pruning to prevent unbounded growth. By introducing in-place replicated state machines that do not use command logs, the log overhead can be avoided. Instead, replicas agree on a sequence of states, and former states are directly overwritten. This method enables the consistent, fault-tolerant replication of basic data management primitives such as counters, sets, or individual locks with little to no overhead. It matches the properties of fast, byte-addressable, non-volatile memory particularly well, where it is no longer necessary to rely on sequential access for good performance. Our approach is especially well suited for small states and fine-granular distributed data management as it occurs in key-value stores, for example.