Towards Log-Less, Fine-Granular State Machine Replication
- PDF / 985,456 Bytes
- 11 Pages / 612.419 x 808.052 pts Page_size
- 23 Downloads / 149 Views
SCHWERPUNKTBEITRAG
Towards Log-Less, Fine-Granular State Machine Replication Jan Skrzypzcak1 · Florian Schintke1 Received: 29 May 2020 / Accepted: 29 September 2020 © The Author(s) 2020
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.
Keywords Replicated State Machine · Consistency · Consensus · Non-volatile memory
1 Introduction State machine replication [1] is a general technique to increase service availability in the presence of failures without losing strongly consistent, i.e., linearizable [2], access to it. Its realization requires that multiple processes agree on the same sequence of commands. Consensus protocols such as Paxos [3] or Raft [4] are needed to achieve this reliably in the presence of failures. Current state-of-the-art designs of replicated state machines (RSM) rely on a command log to keep track of previously agreed-upon commands. While this design enables replicating even large states, the use of command logs incurs state management overhead to prevent the local state from growing unbounded. This overhead includes log allocation, truncation, log recovery, and snapshotting. These mechanisms must be kept in sync with the consensus protocol among replicas, further increasing the complexity of
Jan Skrzypzcak
[email protected] Florian Schintke
[email protected] 1
such systems [5]. The challenges and overhead associated with a log make the RSM approach cumbersome to replicate small states. In this article, we introduce the notion of in-place RSMs. In contrast to their log-based counterpart, in-place RSMs directly agree on a sequence of states without using a log. The resulting architecture only requires a small, constant set of state variables. It enables with little overhead the faulttolerant, consistent access to small states, such as counters, sets, locks, or small pieces of metadata like current group memberships, elected leaders, and more. These are ubiquitous primitives used in data management systems, ranging from datab
Data Loading...
