arXiv CS open access

Eliminating Servers in State Machine Replication

Dohyun Park et al. · arxiv_cs

arXiv CS · Papers

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Eliminating Servers in State Machine Replication Dohyun Park

Wenjie Hu

Xiangyao Yu

dohyunp2@illinois.edu UIUC

wenjiehuhippo@cs.wisc.edu University of Wisconsin–Madison

yxy@cs.wisc.edu University of Wisconsin–Madison

Mahesh Balakrishnan∗

Yongjoo Park

maheshb@gmail.com Meta

yongjoo@illinois.edu UIUC

arXiv:2611.01363v1 [cs.DB] 1 Nov 2026

Abstract

Conventional SMR

State Machine Replication (SMR) underpins many stateful systems, including distributed databases, coordination services, and metadata stores. Fundamentally, SMR requires state to be materialized from a durable total order of commands. Existing SMR systems rely on servers to materialize, locally store, and serve snapshots of state; while the durable total order either resides on the same servers, or on an external, disaggregated shared log. Unfortunately, servers act as brittle, expensive choke-points in such systems, causing service unavailability when they fail; incurring provisioning latency on cold starts; and red-lining when exposed to bad clients. In this paper, we propose Serverless SMR (S2 MR), where both the materialized state and the durable total order are stored on disaggregated storage; clients concurrently maintain a single copy of materialized state on external storage. Our key technical insight is that the shared log abstraction is useful not just for consistently ordering commands in SMR, but also for enabling distributed materialization, thus becoming the only interface for achieving SMR. We demonstrate S2 MR by developing AirDB, a transactional key-value store. In our evaluation, AirDB over S2 MR achieves higher availability than existing SMR-based systems like etcd over Raft: it is oblivious to server failures and bad client activity; and spins up 10×-45× faster from a cold start.

Client

materialized state Client

Server

Client

Server

Client Server

Consensus Disaggregated SMR Client

materialized state Client

Server

Client

Server

Client Server

External Storage (Shared Log)

Consensus (linearized commands) Serverless SMR (S2 MR; our proposal) Client

Client

External Storage (Shared Log)

Consensus (lin. commands)

State

Figure 1. Architectural comparison. Both conventional and disaggregated SMR materialize state on servers. Under S2 MR, distributed clients materialize state on external storage via a shared log, achieving higher availability and competitive latency-throughput at lower infrastructure costs.

Introduction

State Machine Replication (SMR) [37, 48] is a foundational building block for stateful services, enabling durability and availability for production systems such as distributed databases and key-value stores (e.g., Spanner [27], ZippyDB [41], CockroachDB [49], YugabyteDB [14], Oceanbase [31], TiDB [32]), as well as coordination services (e.g., Chubby [25], etcd [1], ZooKeeper [34], Delos [17], KRaft [2]). In SMR, arbitrary state is replicated with strong consistency by generating and materializing a durable total order (or equivalently, a shared log) of commands. SMR is exceptionally versatile: the replicated state can consist of any black-box deterministic state machine (e.g., single-node databases, hierarchical namespaces, block stores, etc.), while the shared log can be stored via any consensus protocol: for example, an SMR system might replicate MySQL database instances using Raft (e.g., ∗ Work done prior to author’s affiliation with Meta

Meta’s MyRaft [47]). In addition, SMR systems can support either single-master or multi-master operation; while the shared log can store either inputs / logical commands or outputs / physical change records. Unfortunately, durable and highly available services based on SMR are notoriously difficult and expensive to build, deploy, and operate [16, 26]. Consider the example of a MySQL database replicated via Raft [47], which requires the replicated state (i.e., MySQL instances) and the shared log (i.e., Raft participants) to be collocated on a single set of servers. Such a service is typically deployed with five servers storing full copies of state: Raft requires at least three servers to tolerate a single server failure; and five servers to tolerate a correlated failure during a planned server upgrade. Availability can be compromised by server crashes (e.g., the Raft leader), I/O contention between Raft and MySQL, software bugs in either layer that crash the entire process, etc.

State Placement external/cloud storage server(s)

N/A

S2 MR (ours)

PostgreSQL [45], etcd [1], AzureSQL [8], Spanner [27], ZooKeeper [34], CockroachDB [49]

LazyKV [40], Delos [17], CorfuDB [15], Tango [19], Scalog [28]

to prevent one client’s long-running full-DB scan from starving another client’s time-critical single-item reads). In effect, continued reliance on materialization servers for availability makes services complex, brittle, and expensive. Our Proposal. In this paper, we propose eliminating servers entirely: we disaggregate both materialized states and ordered commands onto the shared log. The key insight is that a shared log’s append supports both distributed command ordering and distributed materialization. Specifically, S2 MR (Serverless State Machine Replication) stores all state— including the state machine and the command log—entirely in external storage, where the storage can be one of the existing shared-log systems or cloud storage exposing similar APIs (e.g., Azure Blob). S2 MR inherits the foundational mechanism of the shared log: multiple clients consistently can manage (read/write) the shared state by directly accessing the log. S2 MR offers an additional benefit by allowing clients to query the state more quickly by inspecting the materialized snapshot without replaying the entire log from scratch. The materialized snapshots (with collocated indexes) are created by clients in a distributed way. Notably, only a single logical copy of materialized state is maintained by all clients (as opposed to conventional SMR or disaggregated SMR, where each server maintains its own independent copy). S2 MR’s serverless design offers “always-on” availability: • No Servers (and hence, no server failures or upgrades): Without materialization servers, service availability depends only on the underlying shared log. • Fast Start: The service is immediately responsive and available when a workload initially starts and ramps up, without having to over-provision servers in advance or spin them up on demand. • Better Isolation: Misbehaving or crashing clients have no availability impact on other clients and little impact on external storage, which is designed to provide isolation for multiple tenants via its simple, low-level storage API. S2 MR offers other practical benefits. It is cheaper for service operators, who no longer operate materialization servers and can push functionality to end clients. It also requires virtually no deployment effort: a new instance is initialized by creating a separate workspace (e.g., folder) in external storage and distributing access credentials to clients. The resulting protocol retains the simplicity and strong safety guarantees of shared-log systems: the log defines a linearizable command order, and the materialized state is a deterministic function of that log. When one client advances the shared materialized view, it reduces the replay work required by all clients. We evaluate S2 MR by building AirDB, a transactional keyvalue store that provides ACID guarantees with Strict Serializability and Snapshot Isolation [22]. AirDB offers the “always-on” availability of S2 MR along with the additional benefits of low cost and zero deployment effort. For bursty,

external/cloud storage server(s) Log Placement Figure 2. Taxonomy of SMR. We propose Serverless SMR (S2 MR), which places both the replication log and materialized state in external storage, eliminating servers.

Durability is even more challenging to ensure: a correlated failure (e.g., due to a bad software upgrade) that takes down a majority of nodes can result in data loss (particularly if the underlying scheduler does not guarantee disk durability across node reboots). To mitigate these challenges, recent SMR systems have disaggregated the shared log, delegating durability entirely to an external (potentially cloud-based) storage service via an explicit shared log API [17, 19, 23, 28, 40]. In such systems (which we call disaggregated SMR), servers do not implement consensus protocols to maintain a shared log; instead, they store the shared log on external storage and locally materialize soft-state snapshots of application state (e.g., a MySQL database). Servers are no longer responsible for durability: service state can be reconstructed even if all servers fail permanently, as long as the shared log on the external storage service continues to exist. The key driver is the exceptional durability and availability of shared-log architectures [18, 40], which separate log ordering from storage through a dedicated sequencing layer rather than peer-topeer consensus among materializers. However, even if disaggregated SMR improves durability, availability remains challenging to ensure. The availability of the service continues to depend on a server-based materializer layer that can be difficult to harden, for three reasons: • Server Failures / Upgrades: The materialization layer consists of multiple failure-prone components (server software, server hardware, deployment infrastructure such as Kubernetes, etc.). Upgrades to service logic (e.g., to support new features) can be frequent and risky [54]. • Slow Start: The service must trade off cost against availability. Keeping full-state servers ready incurs energy and cloud costs, while starting one on demand requires downloading a snapshot and may violate the latency SLA. • Lack of Server Isolation: Servers have to ensure their own availability in a multi-tenant environment via complex mechanisms for rate-limiting and quarantining (e.g., 2

infrequently accessed state, it also provides strong semantics and lower latency than conventional designs at the same cost, improving availability under a fixed latency target. S2 MR does come with trade-offs. First, migrating the data layout in external storage requires careful coordination. Since S2 MR disaggregates all state onto the shared log while logic resides on the client side, upgrading the data layout can leave clients with an outdated library unable to read the new format. To address this, a version number can be encoded as part of the materialized state; upon a major version change, a client must either update its library or replay the entire shared log from scratch, incurring longer cold-start latency. Second, S2 MR adds round trips between clients and external storage, so it best suits deployments that colocate the two within a data center, such as web servers using a storage service in the same facility. We make the following contributions in this paper: • We propose S2 MR, a novel SMR variant that eliminates servers and materializes states on disaggregated storage. • We describe the design and implementation of AirDB using S2 MR, showing that it provides strong semantics. • Our evaluation shows that S2 MR achieves higher availability than both conventional and disaggregated SMR: it is oblivious to materializer failures and denial-of-service (DoS) attacks on clients; and recovers a 1 GB state from a cold start 45× faster than conventional SMR and 10× faster than disaggregated SMR.

systems, a single process on each machine acts as learner, proposer, and acceptor; accordingly, every process is responsible for both the durability and availability of the service. Starting in the 2010s, shared log systems in research [18, 19, 23, 24, 28, 39, 40, 42] and industry [4, 15, 17, 20, 36, 50– 52] reintroduced the clean logical (and physical) separation of roles into SMR. Such systems adopt a disaggregated SMR design where a tier of materializing servers uses an explicit shared log abstraction to store and order commands. In this setup, materialization encompasses the proposer and learner roles; while the shared log API hides the acceptor role. These systems offer the benefits of layered design: each layer can be scaled independently; optimized and sized separately without contending for shared hardware; and upgraded separately. In particular, the shared log can be implemented over inexpensive cloud storage. Splitting SMR in this manner (materializers running on servers + a shared log on external passive storage) also draws out stark differences in the nature of the two layers. First, SMR materializers are diverse [19, 20], encompassing key-value stores, SQL databases, queues, hierarchical namespaces, and object stores; while external storage has relatively little diversity. Second, SMR materializers can be fast-changing [54], with new code rolled out continuously to support new user-facing features, improve performance, and so on; whereas storage is slow-moving. Third, SMR APIs can be ill-conditioned [16], allowing a single request to trigger large, arbitrary amounts of work (e.g., full-DB scans); whereas storage offers simple APIs that impose constant work per request (e.g., a read on an address). Given this characterization, it follows that disaggregating SMR provides higher durability than converged SMR: failures in the materializer layer are frequent, but no longer impact durability (only availability); failures in storage that do impact durability are far less likely, because its code and APIs are simpler and slower-changing. In this paper, we explore the next logical step: can we improve availability by eliminating materializers entirely, splitting their functionality across clients and storage?

The Evolution of State Machine Replication

State Machine Replication was first described [37] by Lamport as a way to replicate any arbitrary state machine using a total order of commands, each of which could be decided, stored, and accessed via an instance of fault-tolerant consensus. Early descriptions of SMR (e.g., in Lamport’s description of Paxos [38]) typically distinguished between the multiple roles played by potentially different machines: acceptors that decide and store the total order; proposers that suggest candidate commands to be stored and ordered; and learners that play the total order and materialize the state machine. This explicit separation of roles was further reinforced by foundational theoretical results that mapped the problem of fault-tolerant consensus to the implementation of a durable, strongly consistent write-once register [29]: in this view, SMR involved proposers writing to (and learners reading from) an address space of registers, each of which was stored via a quorum protocol like Paxos on a set of acceptors. However, this clean separation of roles in SMR began to blur with the deployment of SMR systems in industry such as Chubby (2001) [25], ZooKeeper (2008) [34], and Raft (2012) [43]. Each of these systems combines all three roles into a single converged SMR architecture, typically for performance and ease of small-scale deployment. In these

2.1

Understanding SMR Availability. Or: Servers considered Harmful!

We first consider the ways in which materializers can fail and cause SMR downtime; and why eliminating them helps. Hardware failures and network outages: Machines crash due to kernel panics, hardware errors, and power failures; data centers disconnect from each other. Intelligent placement of replicas (e.g., each one in a different region) ensures that these types of failures map well to classical failure assumptions (e.g., no more than a majority fails). Schedulers: In virtualized cloud environments, schedulers such K8s and Twine can add an additional layer of faults [21], either by preempting physical hosts for maintenance tasks during correct operation, or by interacting in unexpected 3

• avoids durable local storage on clients. • reduces overall materialization and snapshot storage load. • distributes materialization load across clients.

ways with service logic (e.g., marking healthy hosts as failed; or failing to wait for the service to become healthy during a rolling upgrade). Anecdotal reports [3, 5, 6] show that stateful services encounter these failure modes with particular frequency and severity. Software upgrades: Materializers are constantly upgraded to support new features; each such upgrade is fraught. Zhang et al. [54] provide a comprehensive characterization of upgrade failures in production, highlighting the frequency and severity of such failures. New code can have bugs that only manifest once a rolling upgrade has completed, resulting in correlated failures (e.g., hangs or crash-loops) of all replicas. A single node failure during a rolling upgrade can cause unavailability for a three-replica deployment; or even data loss (if the host is swapped out during the upgrade and the deployment uses local disks). Bad tenants: Multi-tenancy is difficult to achieve for diverse services with complex APIs. Materialization servers can be overwhelmed by rogue tenants that impose large amounts of work: grabbing locks, multi-versioned state management, scrambling caches, and stressing metadata structures. The common theme is that clients must depend on a layer of servers that are stateful and hard to manage, upgrade, and protect. Ideally, a client accessing state would depend only on its own fate and highly reliable low-level services such as networking and external storage, including AWS S3 and Azure Blob Storage. Why not just run unmodified SMR on clients? At first glance, the solution appears simple: eliminate servers and move functionality to clients. In the context of disaggregated SMR, each client could act as a materializer over the shared log. Such a solution is trivially correct: the shared log continues to be the source of consistency and durability. It also definitively eliminates server failures as a source of unavailability – if a client fails, it only impacts itself – and provides protection against the activity of other clients. However, it does not provide the “fast start” property: conventional materializers are required to download full snapshots (which can run into multiple GB) before they become operational; if clients are ephemeral, the time-to-first-operation can be prohibitive. In addition, clients may often not have access to local durable storage, turning simple reboots or preemptions into cold starts. Finally, requiring each client to redundantly materialize the same shared log (and store snapshots periodically in remote storage) can be onerous, especially if clients are critical services in their own right. In the other direction, nominating a single client as a designated materializer can be efficient but introduce a new source of unavailability. Overall, running server-side SMR logic naively on clients might make services less available rather than more. Instead, we need a solution that can provide all three availability properties – no servers, client isolation, and fast start – without constraining or overloading clients. Specifically, we need a new type of client-driven SMR that:

Abstraction: Serverless SMR

We now describe the S2 MR abstraction. S2 MR concerns the class of state such that its subset (i.e., partial state) can be efficiently accessed through indexes (e.g., key-value list, inverted index, tree, graph). The S2 MR architecture involves three parties: the client-side library, the command log (i.e., an instance of the shared log), and the state log (i.e., another instance of the shared log). The role of the command log is identical to the conventional role of the shared log: it linearizes commands and serves as the groundtruth state. S2 MR’s difference lies in the way that the client-side library manages snapshots using the state log (see Fig. 3). The client-side library (or the library) serves the application clients (e.g., get/put of a key-value store) by communicating with the command log and the state log. Clients may read the current state or issue a new command to mutate the state; all are coordinated through the library. Clients may run on multiple machines, all sharing the same global state; the library runs on the same machine as each client. From the application’s perspective, the library looks like an embedded database such as SQLite [12] or RocksDB [10], but acts like a distributed database such as etcd [1] or ZooKeeper [34]. The command log stores linearized commands, which are originally issued by the client and are appended to the command log via the library. Each command may mutate the state by directly setting values (e.g., mykey=val) or by issuing an operation with optional conditions (e.g., balance-=100 if balance>=100). Processing a conditional operation requires two round-trips to ensure no concurrent commands have invalidated the condition. Our system supports both cases. Our evaluation includes a multiple-round-trip scenario, i.e., transaction processing based on snapshot isolation [22]. The state log stores incremental snapshots, which are created and appended by the library. The snapshots allow fast partial state retrieval (e.g., using indexes). The size of the indexes (e.g., storing key-offset pairs) may be significantly smaller than the original command log. Each incremental snapshot is created by playing a certain number of commands. The new snapshot is then added to the state log, using the timely snapshot mechanism described in §3.3. This snapshot creation consumes clients’ compute resources, just like RocksDB and SQLite do, while in S2 MR, the resource usage is distributed across multiple clients. Circling back to the library, retrieving and mutating the current state requires data retrieval from two sources in general: (1) partial states from snapshots and (2) the new commands that have been added since the last snapshot creation. Fetching these data is efficient because (1) retrieving partial states is performed efficiently with indexes; and (2) 4

Distributed clients Client

Client

...

I 𝜙 (0,7]

I 𝜙 (7,14]

I 𝜙 (14,21]

𝜙 (21,24]

new command

𝜎

The Shared Log / Cloud Storage

The command log The state log

𝜎1

𝜎2 · · · · · · · · · · · · 𝜎7

𝜎8

𝜎9 · · · · · · · · · · · · 𝜎14 𝜎15 𝜎16 · · · · · · · · · · · · 𝜎21 𝜎22 𝜎23 𝜎24 zoom-in

𝜙 (0,7]

𝜙 (7,14]

compaction of ⟨𝜎15 , . . . , 𝜎21 ⟩, and index I 𝜙 (14,21]

𝜙 (14,21]

Figure 3. S2 MR data organization. Authenticated clients store commands and states in the shared log. To read state, clients access materialized snapshots using indexes (e.g., I 𝜙 (0,7] ) with a partial state (e.g., 𝜙 (21,34] ) derived from non-materialized commands. To update the state, clients append new entries (e.g., 𝜎) to the command log. Conditional commands (e.g., “withdraw if balance is sufficient”) are validated by checking the command log to ensure the condition held at the time the command was logged. Snapshots are created in a timely and incremental manner by distributed clients. key-value from Φ requires only logarithmic I/O with respect to the size of Φ, using a conventional tree-structured index. Partial state Φ (𝑘,𝑗 ] satisfies Φ (0,𝑗 ] = Φ (0,𝑘 ] ⊕ Φ (𝑘,𝑗 ] , where ⊕ indicates that the right-operand state upserts the left state. Φ (𝑘,𝑗 ] can be constructed efficiently without fully downloading Φ (𝑘,𝑗 ] : only necessary key-values can be retrieved using indexes while applying ⟨𝜎𝑘+1, 𝜎𝑘+2 , . . . , 𝜎 𝑗 ⟩. Specifically, it requires 𝑂 ( 𝑗 − 𝑘) · log(|Φ (0,𝑘 ] |) I/O costs. The constructed partial states serve as incremental snapshots and are stored in the state log with necessary metadata. A merged state, e.g., 𝜙 (0,𝑗 ] , is again a state, which can then be merged with another state, say 𝜙 ( 𝑗,𝑙 ] , to form yet another state, i.e., 𝜙 (0,𝑙 ] . This property allows recursive compaction.

the number of new commands is automatically rate-limited if the data ingestion rate is too high (§3.3). Finally, S2 MR can easily ensure system-wide correctness because it relies on a shared log to linearize commands and manage snapshots. All clients observe the same state by deterministically applying logged commands or reading their materialized results from the snapshots. 3.1

High-level Workflow

The library performs three types of operations: (1) appending commands, (2) updating the local state, and (3) creating snapshots. Each operation issues a bounded number of storage API calls and transfers a bounded number of commands or key-value pairs. Together, these operations implement higher-level application logic, including the database transactions described next. First, appending a new command to the command log requires a single append API call to the command log. Second, the current state can be constructed by combining (1) materialized snapshots, i.e., the state log, and (2) the commands that have not been materialized yet, i.e., the tail of the command log. Suppose we need to update the value for a key. Reading it from the state log (i.e., snapshots) leverages indexes, allowing asymptotically logarithmic data accesses. Reading from the command log is expensive, especially at startup, if there are many non-materialized commands. S2 MR bounds this by introducing the timely snapshot policy; it ensures that all libraries actively create snapshots until the amount of non-materialized commands shrinks enough. Finally, the library materializes new commands and stores them in the state log as a new incremental snapshot. The incremental snapshot only contains the results of applying those new commands. For this reason, the incremental snapshot is small in size, allowing efficient in-memory construction and snapshot transfer to the state log. 3.2

3.3

Distributed Materialization

Minimizing the number of non-materialized commands ensures low start-up cost. To reduce them, snapshots should be created promptly and reliably. Policy. The library initiates snapshot creation (i.e., compaction) if there are more than 𝐵 non-materialized commands. Specifically, it maintains the timely snapshot invariant. Definition 1 (Timely Snapshot). L = ⟨𝜎1, . . . , 𝜎𝑛 ⟩ is the command log. S = Φ (0,𝑖 1 ] , . . . , Φ (𝑖𝑘 −1,𝑖𝑘 ] is the state log. Timely snapshot ensures non-materialized commands cannot grow too much; that is, 𝑛 −𝑖𝑘 ≤ (1+𝜖)𝐵, where 𝜖 is a small number to allow a soft limit (e.g., 0.2). If 𝑛 − 𝑖𝑘 ≥ 𝐵, the library initiates snapshot creation immediately; once 𝑛 − 𝑖𝑘 exceeds (1 + 𝜖)𝐵, it stops accepting new commands until enough have been materialized. Coordination. The library within any distributed clients may participate in snapshot creation. This may cause redundancy; that is, some snapshots may be created and added multiple times. It is desirable to avoid it. When a library recognizes the need for snapshot creation, it leverages the state log to ensure no other libraries are in the process of creating the same or overlapping snapshots. Specifically, a library begins snapshot creation by appending a begin-snapshot command to the state log, indicating (1) the range of commands it aims to compact and (2) Time to Live

Data Model

Let L = ⟨𝜎1, 𝜎2, . . . , 𝜎𝑛 ⟩ be the command log. The transition function 𝜌 applies a command, constructing a new state Φ (0,𝑖 ] = 𝜌 (𝜎𝑖 ; Φ (0,𝑖 −1] ); Φ (0,0] is the empty state. Reading a 5

(TTL). Then, the library immediately checks the state log to confirm there are no conflicting begin-snapshot commands that appear earlier in the log. Once confirmed, the library begins actual snapshot creation, which is completed when the declared snapshot is added to the state log.

state construction, and (3) the shared-log storage on top of cloud storage. Finally, we present optimization details. 4.1

Fault-tolerance. Compaction may not complete in time, which can be identified. Suppose a library 𝐿1 appended a begin-snapshot command and then soon crashed. Another library 𝐿2 finds 𝐿1 ’s begin-snapshot command at 𝐿2 ’s local time 𝑇 . If no corresponding snapshot appears until 𝐿2 ’s local time 𝑇 + TTL, 𝐿2 may begin compaction by appending its own begin-snapshot. This doesn’t require any global clocks. 3.4

Small, Bounded I/O

We analyze the amount of data the library must fetch from the storage during its life cycle. In short, the total I/O cost is (only) linear with respect to the number of reads and writes, and is sublinear with respect to the state size. A client starts at time 𝑇1 , when L contains 𝑛 1 commands. The client is alive for 𝑑 seconds, during which L receives 𝑚𝑎 commands (in total from distributed clients) per second on average. When the client terminates, L contains 𝑛𝑒 commands, where 𝑛𝑒 = 𝑛 1 + 𝑚𝑎 · 𝑑. At 𝑇2 (> 𝑇1 ), the client checks the state log to know that snapshots have been created for the [𝜎1, . . . , 𝜎𝑛′ ] commands where 𝑛 ′ ≤ 𝑛 1 . At 𝑇3 (> 𝑇2 ), the client read all currently existing commands positioned after 𝑛 ′ . 𝑇3 − 𝑇1 is the startup time. Now, the client is ready to serve client requests. While serving requests, the client continuously reads new commands, totaling (𝑛𝑒 − 𝑛 ′ ) commands across its lifetime. The client maintains two kinds of local states: (1) snapshot key set, and (2) the compacted tail. The snapshot key set is the merge of all the indexes of the snapshots that existed at 𝑇1 ; formally, I (Φ (0,𝑖 1 ) ) ⊕ · · · ⊕ I (Φ (𝑖𝑘 −1,𝑖𝑘 ) ), where I indicates the index (e.g., key-offset pairs) of a snapshot. The result of the merge is another index; it tells us which snapshot contains the latest value of a given key. The compacted tail is a partial state created by applying the commands positioned after 𝑛 ′ , i.e., the last snapshot point; unlike the index, it also stores the values themselves, not just keys. If the client makes an average of 𝑚𝑟 read requests per second, its per-second I/O cost is 𝑂 (𝑚𝑟 · log(|Φ|) + 𝑚𝑎 ), where |Φ| indicates the size of its key set. That is, the I/O cost is nearly proportional to the number of read/append requests, scaling sublinearly with respect to the state size.

A Command is A DB Transaction

AirDB can be configured at deployment time to support either Snapshot Isolation (SI) or Strict Serializability (SS). Our transaction protocol implements optimistic concurrency control over the shared log, similar to prior shared log databases [23]. A client begins a transaction 𝑇 by synchronizing with the tail of the command log. It uses this log offset as the snapshot timestamp 𝑠 (𝑇 ) for the transaction. The client then speculatively executes the transaction by issuing reads and buffering writes, generating an intention that describes either the read set (for SS) or the write set (for SI). To commit the transaction, we first append the intention as a command to the command log. The position of the intention in the log is the commit timestamp 𝑐 (𝑇 ) for the transaction. We then determine if the transaction commits or aborts by inspecting the state—the command log and state log— at the commit timestamp to see if any conflicting transactions have committed since our snapshot timestamp. In the case of SI, this requires checking whether any keys in the 𝑇 ’s write set have been written between 𝑠 (𝑇 ) and 𝑐 (𝑇 ). In the case of SS, this checks whether any keys in 𝑇 ’s read set have been written between 𝑠 (𝑇 ) and 𝑐 (𝑇 ). Each transaction intention is appended as a single log entry, whose size is bounded by the maximum append size of the underlying shared log (e.g., 4 MB for Azure Append Blob). Transactions exceeding this limit must be split. Checking conflicts—any updates on my read set (SS) or write set (SI)—requires historical data. AirDB’s (partial) state representation allows this check in a memory-efficient way, without the full command history, as described below. 4.2

State Representation

AirDB strictly follows the S2 MR data model: (1) applying a new command 𝜎𝑖 to the previous state Φ (0,𝑖 −1] constructs a new state Φ (0,𝑖 ] ; and (2) two partial states Φ (0,𝑘 ] and Φ (𝑘,𝑗 ] can be merged into a single state Φ (0,𝑗 ] . Partial State. The state representation should allow conflict checks. Simply storing the latest key-value pairs is insufficient since we cannot answer whether a key was modified between two offsets. However, storing the full change history for every key is memory-inefficient; thus, we should avoid it. We observe that under S2 MR, a new transaction’s commit time is always greater than any of the transactions that have been applied to existing states. Leveraging this, AirDB stores the (single) last modification time for each key. This allows correct conflict checks, as follows. For any key in 𝑇 ’s read-set (for SS) or write-set (for SI), if the last modification timestamp is within (𝑠 (𝑇 ), now), we can say there exists at least one conflicting transaction; thus, 𝑇 should be aborted. Vice versa, if the last modification time of a key is before 𝑠 (𝑇 ), we can

AirDB: S2 MR-based Key-Value Store

Built on S2 MR, AirDB provides a transactional key-value store interface. It runs inside distributed clients, manages globally shared state on cloud storage, and is implemented in Go in roughly 6.6K lines of code. We describe how AirDB extends S2 MR abstraction in terms of (1) command and state transition; (2) transaction-aware 6

say that the key has not been modified since 𝑇 observed it in its snapshot (SS) or wrote it (SI); thus, 𝑇 is committed. Merge. Merging two states, Φ (0,𝑘 ] and Φ (𝑘,𝑗 ] , is straightforward. The key-value pairs from Φ (𝑘,𝑗 ] overwrite any existing key-value pairs, including the last modification time. Note that merging doesn’t need to involve conflict checks. Each state only contains the results of committed transactions in relation to their respective prior transactions. In summary, AirDB requires 𝑂 (|Φ|) memory in maintaining (partial) states, irrespective of the command log length. 4.3

storage to serve a linearizable read request. Instead, we can speculatively read from the snapshot, assuming the key is not in the command log. We discard the value from the snapshot if a new command is found for the key. Reading the command log and materialized state concurrently reduces the latency observed by each request. Batched Reads and Writes. For higher throughput and lower storage overhead, AirDB uses an optimization called a bus-stand [16]: each client has a single thread that periodically synchronizes with the log. This synchronization checks the tail of the command log, plays commands back, updates local state, and serves pending read requests. The thread ensures that there is only one outstanding tail check to the command log. As a result, incoming reads have to wait until the next “bus” leaves the bus-stand for cloud storage; in the worst case, they can just miss it and have to wait for one extra RTT. The tail offset read by the synchronization becomes the linearization point for the reads assigned to it (or equivalently, the snapshot for SI or SS transactions). To rate-limit checks, the thread enforces some minimum time period between subsequent syncs (e.g., 10ms). Similarly, AirDB also uses a conventional batching thread for writes.

The Shared Log on Blob Storage

AirDB aims to operate with minimal setup, preferably on top of off-the-shelf cloud storage, without employing VM-based shared log systems [15, 19, 40]. AirDB achieves this goal by implementing the shared log atop of existing blob storage. Storage model. Storage should offer the following operations: (1) create a blob (failing if it already exists), (2) atomically append to a blob, (3) read from a blob, and (3) get the size of a blob. A blob is finite in size; the size limit is predefined. AirDB models each blob as a segment. AirDB can support a new storage system by extending the segment with a storage-specific implementation, e.g., a Redis-backed segment in place of an Azure blob.

Infinite log on finite blobs. In S2 MR, both the command log and the state log are instances of the shared log abstraction. AirDB implements the shared log through segments. That is, the shared log consists of one or more ordered segments, and each segment contains one or more commands. A new segment is added if the last one fills up. New commands append to the last segment, called the tail segment. The overall structure (i.e., a list of segments and their order) and their physical mapping (to blobs) are recorded in the special meta segment. The meta segments record the history of new segment additions. Any AirDB library (running within an application client) can add a segment as the new tail. To do so, it first creates a new segment with a unique name (e.g., using a GUID), and then updates the meta segment. AirDB loads the meta segment at startup and checks for updates, particularly when existing segments fill up. For the meta segment itself, we use a static naming scheme of fixed-size segments (e.g., meta0, meta1, and so on). 4.4

Evaluation

Our evaluation aims to answer the following questions: • Performance: Can a S2 MR-based system offer competitive throughput-latency when compared to the systems following more conventional SMR architecture? (§5.2) • Availability: Does eliminating servers preserve uptime during node, client, and storage failures? (§5.3) • Impact of Storage: How does the storage performance affect S2 MR performance? (§5.4) • Cost-Efficiency: Can S2 MR lower infrastructure costs, even considering client costs? (§5.5) • Scalability: Can S2 MR offer higher overall throughput when more clients interact with the shared storage? (§5.6) In the remainder of this section, we describe a common evaluation setup and then present evaluation results. 5.1

Setup

We evaluate S2 MR through AirDB, its transactional keyvalue store implementation. All systems in the comparison provide strict serializable execution. • etcd [1] is a Raft-based strongly consistent, distributed key-value store. We enable strict serializable execution. • Shared Log SMR (SLSMR) is a shared-log-based distributed multi-master database. SLSMR uses Azure Blob Storage to implement the shared-log abstraction, i.e., the same approach as AirDB. Each of SLSMR’s masters (re-)constructs the state by replaying commands (in the shared log) or loading snapshots. The state is kept in memory. SLSMR is configured to use strict serializability.

Optimizations

To mitigate the latency and cost of interactions with external storage, AirDB introduces two key optimizations. Speculative Reads. When a client reads a key, the latest value may reside either in the command log or in the state log. Naively, AirDB can first read the command log; and then read a snapshot from the state log if it does not find a value for the key. This requires at least two RTTs to cloud 7

P99 Latency (ms)

etcd (conventional SMR) 1,200 1,000

1,700 1,500 1,000

500 500 0

10K

15K

S2 MR on Azure Blob (ours)

SLSMR on Azure Blob (disaggregated SMR)

10K

20K

30K

800

400

2,500

600

300

2,000

400

200

100

0 20K 40K 60K 80K 100K

1,000

50K 100K 150K 200K

20K

40K

60K

Throughput (ops/s)

(a) Insert Only (100%-inserts)

(b) Update Heavy (50%-reads / 50%-updates)

(d) Read Only (100%-reads)

(e) Read-Modify-Write (50%-RMW / 50%-reads)

Figure 4. Latency-Throughput comparison with YCSB workloads. AirDB, an instance of S2 MR, achieves competitive performance compared to etcd (conventional SMR) and SLSMR (shared log-based disaggregated SMR) across all workload types.

Workloads. We use workloads from the YCSB benchmark [13]. We test four workload types: insert-only; updateheavy (50/50 update/read); read-heavy (5/95 update/read); read-only; and read–modify–write (50/50 RMW/read). All experiments operate on 1 GB data containing one million key–value pairs. Each pair is 1 KB in size. Unless otherwise noted, we set 𝜃 = 0; keys are accessed with equal probability. We choose 1 GB to reflect the scale of coordination services such as etcd, which enforces a default storage limit of 2 GB. Environments. We use Azure [9] within a single virtual network. The baseline systems (i.e., etcd and SLSMR) run on three-node clusters of Standard D4_v3 VMs (4 vCPUs, 8 GiB memory). Clients run on individual instances of the same type. All VMs run Ubuntu 20.04 on standard HDDs. Each VM uses a single standard Azure virtual NIC with IPv4 networking and accelerated networking disabled, capping aggregate bandwidth at roughly 2 Gbps per VM. Storage. We evaluate several storage backends for AirDB. First, we use Azure Blob [7] for the primary performance and cost analysis. Second, to demonstrate AirDB ’s extensibility, we also employ a replicated Redis cluster (with our own sequencer) to represent a low-latency shared-log storage. 5.2

etcd

1st

2nd

Throughput 3rd

1,000

1,500 1,000

500

500 0

SLSMR

1st

2nd

3rd

4th

5th

300 200

1,000 500

100 0

100

150

Thpt (ops/s)

P99 Latency (ms) P99 Latency (ms)

P99 Latency

Thpt (ops/s)

• AirDB is our S2 MR implementation. It offers the transactional key-value store interface. To implement the shared log abstraction, AirDB uses Azure Blob (for §5.2, §5.3, and §5.5) and additionally uses Redis (§5.4). It is set to use strict serializability for all our evaluations.

Time (s)

Figure 5. Server failures’ impact on availability. Each vertical dashed line indicates a node failure. (top) etcd becomes unavailable after the 3rd failure (loses quorum). (bottom) SLSMR tolerates 4 failures but crashes on the 5th (no remaining replicas). AirDB is unaffected by server failures by design, thus is omitted in this figure.

strict serializability. We use the 1 GB dataset (cold start is studied separately in §5.3.3); insert-only (Fig. 4a) starts from an empty database. Each workload runs three times; we report average throughput and P99 latency over a one-minute window, issued from three client VMs and controlled by the number of in-flight operations. Results. Fig. 4 shows P99 latency as a function of throughput. Overall, AirDB reaches higher peak throughput than the baselines. For read-heavy and read-only workloads (Figs. 4c and 4d), AirDB achieves up to 2.5× the throughput of SLSMR and 4× that of etcd. At lower offered load (<50K ops/s), etcd reports lower latency. For workloads involving writes (Fig. 4a), both AirDB and SLSMR attain higher throughput than etcd. SLSMR exhibits somewhat higher latency than AirDB at comparable throughput levels. For the RMW workload (Fig. 4e), the uniform key distribution yields low contention, AirDB achieves up to 3× the throughput of etcd.

S2 MR Delivers High Throughput

We examine AirDB’s throughput–latency against existing SMR systems, studying whether AirDB, running on external storage, can offer low-latency operations as load increases. Approach. We compare AirDB against etcd and SLSMR using throughput–latency curves collected after a one-minute warm-up. The five YCSB workloads comprise four singleoperation types and read-modify-write (RMW), whose multioperation commands commit only when conflict-free under 8

Throughput

etcd P99 (ms)

S2 MR (ours)

SLSMR

600

1,000

400

600

1,000

400 500

200 0

Bad Client Start

120

0 180

1,000

400 500

200 0

600

120

0 180

500

200 0

120

0 180

Thpt (ops/s)

P99 Latency

P99 (ms)

1,000

400

1,000

400 500

200 0

600

120

0 180

1,000

400 500

200 0

600

Time (s)

120

0 180

Time (s)

500

200 0

120

0 180

Thpt (ops/s)

(a) Read-only disruptive workload 600

Time (s)

(b) Update-heavy disruptive workload

Figure 6. Impact of disruptive (“bad”) clients on well-behaved (“good”) clients. Each row shows a different disruptive workload: (a) read-heavy and (b) update-heavy. Within each row, columns correspond to etcd, SLSMR, and AirDB, respectively. Each subplot reports two metrics for the Good Client over time: P99 latency (blue, left axis) and throughput (red, right axis). The vertical dashed line marks the moment when Bad Clients begin issuing high-rate requests. Discussion. These trends reflect architectural differences. etcd serves reads locally at low load but its latency rises sharply once the leader becomes CPU-bound; AirDB and SLSMR instead pay a fixed round trip to validate the log tail, which adds latency at low load but does not grow with throughput. This fixed cost stays roughly constant as load rises, whereas etcd’s latency degrades exponentially once the leader’s CPU saturates with Raft coordination. AirDB’s latency floor is thus set by the storage round-trip time, trading low-load latency for higher peak throughput and availability; client-side caching can further cut read latency. For writeheavy workloads, the disaggregated designs avoid Raft’s quorum replication and local persistence, sustaining higher throughput: writing directly to the disaggregated shared log removes the leader–follower replication bottleneck, letting write throughput scale with the storage layer rather than a consensus engine. SLSMR’s extra network hop raises its tail latency relative to AirDB, and the RMW workload’s uniform access yields little contention. 5.3

Results. Fig. 5 shows that etcd remains available until three nodes fail, at which point quorum is lost. SLSMR continues to operate with up to four failed nodes, as each remaining node can independently access the shared log. Both systems exhibit latency increases during failure. Discussion. etcd and SLSMR rely on servers to process operations, so those servers determine service availability. AirDB instead executes directly on storage; failures of application servers cannot make it unavailable.

5.3.2 Better Isolation. We evaluate whether AirDB isolates well-behaved clients from disruptive clients using the same shared-storage deployment. Approach. We examine two scenarios: Bad Clients disrupt the system with (1) excessive reads and (2) excessive writes. In both cases, the Good Client issues a YCSB read-only workload on 1 GB data with a Zipfian distribution (𝜃 = 0.99) at 1,000 operations per second. At 𝑡 = 30s, we introduce Bad Clients that issue high-throughput workloads with a Uniform distribution. etcd and SLSMR run on three-node clusters using D4_v3 VMs. For Fig. 6a, we launch three Bad Client VMs targeting 100K ops/s each. For Fig. 6b, we launch one Bad Client targeting 50k ops/s. Result. Fig. 6a shows the Good Client’s latency and throughput under read-based disruption. In etcd and SLSMR, latency increased immediately at 𝑡 = 30s. etcd experienced a brief throughput drop. AirDB’s latency and throughput stayed nearly identical. Fig. 6b shows the Good Client’s latency and throughput under update-based disruption. etcd showed large latency swings and significant throughput impact since 𝑡 = 30. SLSMR also showed latency degradation, though with lower variance. Its throughput remained stable. AirDB’s latency and throughput showed minimal impact.

S2 MR is More Available

We assess AirDB’s availability under three failure classes: application-server failures, cold starts after idle periods, and disruptive clients degrading availability for benign ones. 5.3.1 Application Server Failure. We evaluate system availability under application-server failures in comparison with etcd and SLSMR. Approach. We deploy five-node clusters for etcd and SLSMR and sequentially fail one node every 30 seconds. A client issues a read-only workload at a target throughput of 1,000 operations per second. Throughput and P99 latency are recorded during the sequence of failures. 9

67s 47.6s54s 64s 0.9s1.7s2.4s6.1s

100 M 500 B MB 1G B 5G 100 B M 500 B MB 1G B 5G 100 B M 500 B MB 1G B 5G B

etcd

SLSMR

20K

100 0

100

Time (s)

SSMR

(a) Cold start time breakdown

200

0 300

300

15K

200

10K

100

200

0 300

Throughput (ops/s)

81.5s 52s67.8s

40K

P99 Latency (ms)

100

Throughput

250 200

Throughput (ops/s)

200

P99 Latency

P99 Latency (ms)

Latency (s)

Server Startup Snapshot Restore VM Startup

278s

300

Time (s)

(b) AirDB’s cold start performance over time (left: 1GB, right: 5GB)

Figure 7. Cold-Start Performance. (a) Cold-start latency breakdown across dataset sizes (100 MB–5 GB). Stacked bars indicate VM startup, snapshot restore, and server initialization. (b) Throughput and P99 latency during AirDB’s cold start under a Zipfian workload (𝜃 = 0.99) with 1 GB in-memory buffer. The left panel (1 GB data) shows warm-up as the working set enters cache; the right panel (5 GB data) shows increased performance variance as the data size exceeded the buffer capacity. 5.3.4 Robustness to Compound Failures. We evaluate the system in an adversarial chaos test. Approach. We generated a 100-minute timeline with continuous, artificially injected faults. For node failures, we configured a 10% probability of a single VM reboot per minute, and a 1% probability of a simultaneous, cluster-wide reboot. Additionally, there was a 10% probability per minute that a “bad client” initiated a sustained, update-heavy workload for one minute. Finally, we introduced storage instability, where every storage I/O operation had a 0.1% probability of failure. These faults stress each architecture differently. VM reboots disrupt only the systems that run operations on dedicated servers (etcd and SLSMR), as AirDB has no servers to reboot. Storage faults disrupt only the systems that execute against the shared log (AirDB and SLSMR), and not etcd, as etcd serves operations from its own nodes’ local disks. The bad-client load affects all three systems. We compare AirDB, etcd, and SLSMR by the fraction of the target client’s operations that meet a 100 ms latency SLA. Throughout the timeline, the target client issues a steady 1K read operations per second. We classify each of its operations as a Success (completed within 100 ms), an SLA Violation (completed but slower than 100 ms), or Unreachable (failed to complete because the system was unavailable), and report each category as a percentage of all attempted operations. Results. Across the 100-minute timeline, we observed 15 individual VM reboots, 2 cluster-wide reboots, and 8 bad-client incidents. Tab. 1 summarizes the results. AirDB demonstrates superior resilience, maintaining 99.02% of operations within the SLA. With no VM-induced downtime, AirDB records 0.00% unreachable operations because it decouples compute from state.

Discussion. etcd and SLSMR process requests on application servers, so high-rate Bad-Client traffic loads those servers and inflates the Good Client’s latency. AirDB executes directly on storage: the Good Client keeps making progress after Bad Clients arrive, with only small latency increases from replaying newly committed updates, while throughput and P99 latency stay stable. 5.3.3 Faster Cold Start. This section measures cold-start behavior for etcd, SLSMR, and AirDB as the dataset grows. Approach. We recorded end-to-end cold-start time, defined as the interval from startup initiation to the first completed transaction. etcd and SLSMR run as three-node clusters and must provision VMs and restore state before serving requests. Data sizes were 100 MB, 500 MB, 1 GB, and 5 GB. Each experiment was repeated three times; we report the median. AirDB initialized directly from storage. It read only the state log indexes and applied the command log tail. It deferred full-state reconstruction, filling its cache only as requests accessed data. Results. Fig. 7a shows etcd and SLSMR slowing sharply as data size grew, since both depend on VM provisioning and full snapshot restoration; AirDB was largely insensitive to data size, touching only metadata and the log tail at startup. Fig. 7b shows runtime warm-up. With 1 GB data, throughput rose, and latency stabilized within 150s as the cache filled. 5 GB data—which exceeds the cache—raised latency variance and lowered throughput as it spilled to storage. Discussion. First, cold-start latency grew with dataset size for systems that rebuild full state; AirDB avoided this through storage-centric initialization. Second, warm-up latency depended on cache size: when the working set fit in memory, the cache stabilized quickly; otherwise, additional storage I/O extended the warm-up period. Finally, even the system restarting from local disk must load a full snapshot before serving requests, so its recovery time is still impacted by data size (e.g., etcd with 5 GB in Fig. 7a).

5.4

Faster Storage Reduces Latency

We study the impact of storage latency on S2 MR. Approach. To represent a low-latency shared-log system, we implemented the shared log interface on top of Redis 10

P99 Latency (ms)

S2 MR on Redis

S2 MR on Azure Blob 80

600 400

200

150

40 200

100

10K

20K

Throughput (ops/s) (a) Insert Only (100%-inserts)

20K

40K

60k

100

20 0

100K

200K

Throughput (ops/s)

(b) Update Heavy (50%-reads / 50%-updates)

50 0

100K

200K

Throughput (ops/s) (d) Read Only (100%-reads)

50K

100K

Throughput (ops/s) (e) Read-Modify-Write (50%-RMW / 50%-reads)

Figure 8. Impact of storage performance on S2 MR. Throughput–latency curves with Redis and Azure Blob across five YCSB workloads. Each subplot shows P99 latency versus throughput for a distinct workload. Table 1. Aggregate availability and performance under compound failures (VM reboots, bad clients, and storage faults) over a 100-minute timeline. System etcd SLSMR AirDB

Success (<100ms)

SLA Violation (>100ms)

Unreachable (Failures)

89.85% 92.50% 99.02%

8.49% 5.20% 0.98%

1.66% 1.28% 0.00%

Table 2. Monthly cost comparison under Azure pricing. We evaluate a low-load (1M reads/writes) and a high-load (100M reads/writes) scenarios. AirDB includes the cost of client memory (𝐶 mem ) under worst-case 0% cache hit rate. System Monthly Cost Model

etcd 3𝐶 vm – SLSMR 𝐶 vm +𝐶 stor +𝑁 w (𝐶 write +𝐶 read )+𝑁 r𝐶 read – AirDB 𝐶 mem +𝐶 stor +𝑁 w (𝐶 write +𝐶 read )+𝑁 r (𝐶 read ) $38.51

using Lua scripts and locks. Then, we ran the YCSB benchmarks on 1 GB data with AirDB, backed by a three-node Redis deployment (one master, two replicas). Results. Fig. 8 shows that AirDB achieves lower request latency across all workloads when backed by the low-latency Redis storage. The improvement is largest in workloads where AirDB must roll forward new transactions, since these operations depend directly on storage responsiveness: a faster backend shortens each tail check and log-tail read (Figs. 8a to 8c and 8e). Across these workloads, Redis lowers AirDB’s latency by 2–45 ms (Figs. 8d and 8e). Discussion. AirDB benefits most from faster storage on workloads that frequently process new log entries because each request spends less time fetching and applying committed transactions. These results also show that S2 MR accepts different shared-log backends. Cloud storage and Redis both implement its core abstraction through two operations: append and read. 5.5

Client Low Load High Load Overhead 1M R/W 100M R/W $924.18 $310.87 $41.32

$924.18 $574.21 $304.66

• 𝐶 mem : Monthly cost of each client’s 2GB RAM ($38.51). • 𝐶 write : Cost per 10,000 blob write operations ($0.0228). • 𝐶 read : Cost per 10,000 blob read operations ($0.0019). Approach. AirDB uses client-side caching to reduce latency and cost. This design requires additional client memory (up to 2 GB RAM for a 1 GB database). To evaluate an upper bound on cost, we also analyze a scenario with a 0% cache hit rate and include the full client memory cost. Result. Tab. 2 reports monthly costs. AirDB replaces the fixed expense of dedicated compute nodes with a small clientmemory cost (𝐶 mem ): etcd incurs a constant $924.18/month and SLSMR needs at least one sequencer VM at $308.06, both of which AirDB avoids. For 1M ops/mo, AirDB costs $41.32— about 22× cheaper than etcd and 7.5× than SLSMR—and even in the worst-case 100M-ops workload with no caching it keeps a 3× advantage over etcd. 5.6

S2 MR is Cost-Efficient

We evaluate the operational cost of AirDB against etcd and SLSMR using Azure pricing. We used 1 GB data size and compared two monthly workloads: a low-load scenario (𝑁 w =𝑁 r =1M) and a high-load scenario (𝑁 w =𝑁 r =100M). Pricing Model. We use the following Azure costs: • 𝐶 vm : Monthly cost of a Standard D4 v3 VM ($308.06). • 𝐶 stor : Monthly storage cost per GB ($0.15). 11

S2 MR Scales Well with More Clients

We measure how AirDB’s throughput changes as the number of clients increases. We use YCSB workloads: 1 GB data; data was fully cached. The number of client VMs varied from 10 to 80. We report aggregate throughput and P99 latency. Results. Fig. 9 shows AirDB scaling differently with the write fraction. For read-only workloads (Fig. 9d), throughput grows near-linearly from roughly 300K ops/s at 10 clients to about 2.7M ops/s at 80, with P99 latency stable around 25 ms. Workloads with writes (Figs. 9a to 9c) eventually

40K

# Clients

(b) Update Heavy

300

100K

P99 (ms)

50 200K

1.5M

# Clients

(d) Read Only

S2 MR, which keeps one materialized copy in external storage for direct use by every client. Databases over Shared Logs Hyder [23], Tango [19], and Delos [17] use a shared log to order transactions and reconstruct state. Each server or learner, however, materializes a private copy from the remote log, so recovery entails restoring a snapshot and replaying its suffix before serving requests. S2 MR instead makes reusable state shared: clients jointly maintain one materialized copy in external storage, and a new client reads that copy without first rebuilding the complete database locally. Log-structured Merge (LSM) trees [44] optimize writeintensive workloads by buffering writes in memory and periodically flushing to disk. Single-node LSMs [10] are common building blocks for distributed databases [11, 14, 49]. S2 MR can be viewed as a distributed LSM: instead of each node writing its own log and compacting to its own snapshot, many clients collaboratively extend a single shared log and compact it to a shared snapshot. Viewed this way, S2 MR resembles LSM-style designs over disaggregated storage [33], but uses the structure to improve SMR availability.

Thpt (ops/s)

2,500

(a) Insert Only Thpt (ops/s)

P99 (ms)

80K

600

5,000

Thpt (ops/s)

P99 (ms)

10K

1,500

Thpt (ops/s)

P99 (ms)

20K

3,000

Figure 9. Scalability of AirDB with increasing client VMs.

saturate from serialization on the shared log: throughput plateaus (near 70K ops/s for Update Heavy and 17K ops/s for Insert Only) and P99 latency rises to several seconds under high contention. By eliminating servers, S2 MR shifts the performance bottleneck from a central server to sharedlog serialization bandwidth. Write throughput is bounded by the underlying storage’s tail-segment append rate. This bottleneck differs from conventional SMR: higher-bandwidth shared logs would raise S2 MR’s write ceiling.

Conclusion

SMR is simplified by shared log designs on external storage, but hobbled by their reliance on failure-prone servers to materialize the log. S2 MR eliminates these servers by having clients maintain a single materialized copy of state on external storage and use the shared log for both command ordering and distributed materialization. This removes several sources of unavailability: server failures, misbehaving clients, and cold-start overheads. Our S2 MR key-value store AirDB delivers strong ACID semantics with far higher availability than conventional designs, lower cost, and simpler deployment. It runs atop commodity storage such as Azure Blob, and our Redis implementation shows how a low-latency shared log improves performance. The mechanism also clarifies which storage primitives matter. S2 MR needs a durable ordered append path and indexed access to compacted state; it does not require a database service or a private snapshot for every client. This separation lets a deployment choose storage for its latency, cost, and durability targets while preserving the client-side statemachine interface. It also localizes recovery because a new client reads shared indexes and the short log tail rather than reconstructing the entire database before serving requests. Evaluation marks the design’s boundary: cached reads scale with clients, while writes are capped by the shared log’s append rate. S2 MR best fits clients near durable shared storage that value availability, rapid startup, and elastic reads over single-node latency. More broadly, atomic shared-log operations let clients maintain reusable state without assigning materialization to a server.

Related Work

Classical SMR S2 MR builds on classical State Machine Replication, leveraging Lamport’s formulation of distinct roles [38]. In S2 MR, both acceptor and learner state reside on disaggregated storage, while the proposer runs in each client. Together, the clients implement a single “logical” learner whose materialized state is durable and directly accessible through the shared storage service. Disaggregated SMR relies on materializers that play an external shared log and maintain individual copies or snapshots of state, stored in memory [19] or on local disk [17]. Periodically, to speed log playback on recovery, each materializer writes its local snapshot—a deterministic function over some prefix of the shared log—to remote storage. A fundamental property of disaggregated SMR is that a server must download a full snapshot before serving requests. In contrast, S2 MR maintains a single shared copy of materialized state, so clients serve requests immediately from disaggregated storage without downloading full state. Serverless+Shared Logs A sub-class of disaggregated SMR systems deals with serverless functions, starting with Boki [35] and successors [30, 46, 53, 55]. Boki lets ephemeral functions materialize state by playing a fine-grained shared log (a LogBook), keeping state in local memory and periodically storing snapshots (“auxiliary data”) via the LogBook API. In this distinction between local and remote snapshots, Boki is closer to conventional disaggregated SMR than to 12

References

9–20, 2011. [24] Shreesha G Bhat, Tony Hong, Xuhao Luo, Jiyu Hu, Aishwarya Ganesan, and Ramnatthan Alagappan. Low {End-to-End} latency atop a speculative shared log with {Fix-Ante} ordering. In 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25), pages 465–481, 2025. [25] Mike Burrows. The Chubby lock service for loosely-coupled distributed systems. 2006. [26] Tushar D Chandra, Robert Griesemer, and Joshua Redstone. Paxos made live: an engineering perspective. In Proceedings of the twentysixth annual ACM symposium on Principles of distributed computing, pages 398–407, 2007. [27] James C Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, Jeffrey John Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, et al. Spanner: Google’s globally distributed database. ACM Transactions on Computer Systems (TOCS), 31(3):1–22, 2013. [28] Cong Ding, David Chu, Evan Zhao, Xiang Li, Lorenzo Alvisi, and Robbert Van Renesse. Scalog: Seamless reconfiguration and total order in a scalable shared log. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 325–338, 2020. [29] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374–382, 1985. [30] Dimitra Giantsidi, Emmanouil Giortamis, Nathaniel Tornow, Florin Dinu, and Pramod Bhatotia. Flexlog: A shared log for stateful serverless computing. In Proceedings of the 32nd International Symposium on High-Performance Parallel and Distributed Computing, pages 195–209, 2023. [31] Fusheng Han, Hao Liu, Bin Chen, Debin Jia, Jianfeng Zhou, Xuwang Teng, Chuanhui Yang, Huafeng Xi, Wei Tian, Shuning Tao, et al. Palf: Replicated write-ahead logging for distributed databases. Proceedings of the VLDB Endowment, 17(12):3745–3758, 2024. [32] Dongxu Huang, Qi Liu, Qiu Cui, Zhuhe Fang, Xiaoyu Ma, Fei Xu, Li Shen, Liu Tang, Yuxing Zhou, Menglong Huang, et al. Tidb: a raftbased htap database. Proceedings of the VLDB Endowment, 13(12):3072– 3084, 2020. [33] Haoyu Huang and Shahram Ghandeharizadeh. Nova-lsm: a distributed, component-based lsm-tree key-value store. In Proceedings of the 2021 International Conference on Management of Data, pages 749–763, 2021. [34] Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. ZooKeeper: wait-free coordination for internet-scale systems. In Proceedings of the 2010 USENIX conference on USENIX annual technical conference, USENIXATC’10, page 11, USA, 2010. USENIX Association. [35] Zhipeng Jia and Emmett Witchel. Boki: Stateful serverless computing with shared logs. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, pages 691–707, 2021. [36] Jay Kreps, Neha Narkhede, and Jun Rao. Kafka: a Distributed Messaging System for Log Processing. [37] Leslie Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. 21(7), 1978. [38] Leslie Lamport. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001), pages 51–58, December 2001. [39] Joshua Lockerman, Jose M Faleiro, Juno Kim, Soham Sankaran, Daniel J Abadi, James Aspnes, Siddhartha Sen, and Mahesh Balakrishnan. The fuzzylog: A partially ordered shared log. In OSDI, pages 357–372, 2018. [40] Xuhao Luo, Shreesha G Bhat, Jiyu Hu, Ramnatthan Alagappan, and Aishwarya Ganesan. Lazylog: A new shared log abstraction for lowlatency applications. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, pages 296–312, 2024. [41] Sarang Masti. How we built a general purpose key value store for Facebook with ZippyDB, August 2021.

[1] etcd. https://etcd.io/. https: [2] KRaft - Apache Kafka Without ZooKeeper. //developer.confluent.io/learn/kraft/. [3] Kubernetes failure stories. https://k8s.af/. https://engineering.fb.com/2017/08/31/core[4] Logdevice. infra/logdevice-a-distributed-data-store-for-logs/, 2017. [5] Grafana incident report #2. https://grafana.com/blog/2019/07/24/howa-production-outage-was-caused-using-kubernetes-podpriorities/, 2019. [6] Grafana incident report #1. https://grafana.com/blog/2020/01/23/howa-gcp-persistent-disk-incident-snowballed-into-a-23-houroutage--and-taught-us-some-important-lessons/, 2020. [Online; accessed 11-December-2025]. [7] Azure blob storage. https://azure.microsoft.com/en-us/services/ storage/blobs/, 2023. [Online; accessed 17-October-2024]. [8] Azure sql databases. https://azure.microsoft.com/en-us/products/ azure-sql/database, 2023. [Online; accessed 17-October-2024]. [9] Microsoft azure: Cloud computing services. https: //azure.microsoft.com/en-us, 2023. [Online; accessed 17-October2024]. [10] Rocksdb: A persistent key-value store. https://rocksdb.org/, 2023. [Online; accessed 17-October-2024]. [11] Scylladb: A fast and scalable nosql database. https: //www.scylladb.com/, 2023. [Online; accessed 17-October-2024]. [12] Sqlite. https://sqlite.org/index.html, 2023. [Online; accessed 17October-2024]. [13] Ycsb. https://github.com/brianfrankcooper/YCSB, 2023. [Online; accessed 17-October-2024]. [14] Yugabytedb: A cloud native distributed sql database. https:// www.yugabyte.com/, 2023. [Online; accessed 17-October-2024]. [15] CorfuDB/CorfuDB, August 2025. original-date: 2013-09-19T22:02:36Z. [16] Mahesh Balakrishnan. Taming consensus in the wild (with the shared log abstraction). ACM SIGOPS Operating Systems Review, 58(1):1–6, 2024. [17] Mahesh Balakrishnan, Jason Flinn, Chen Shen, Mihir Dharamshi, Ahmed Jafri, Xiao Shi, Santosh Ghosh, Hazem Hassan, Aaryaman Sagar, Rhed Shi, et al. Virtual consensus in delos. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 617–632, 2020. [18] Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobbler, Michael Wei, and John D Davis. {CORFU}: A shared log design for flash clusters. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12), pages 1–14, 2012. [19] Mahesh Balakrishnan, Dahlia Malkhi, Ted Wobber, Ming Wu, Vijayan Prabhakaran, Michael Wei, John D Davis, Sriram Rao, Tao Zou, and Aviad Zuck. Tango: Distributed data structures over a shared log. In Proceedings of the twenty-fourth ACM symposium on operating systems principles, pages 325–340, 2013. [20] Mahesh Balakrishnan, Chen Shen, Ahmed Jafri, Suyog Mapara, David Geraghty, Jason Flinn, Vidhya Venkat, Ivailo Nedelchev, Santosh Ghosh, Mihir Dharamshi, et al. Log-structured protocols in delos. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, pages 538–552, 2021. [21] Marco Barletta, Marcello Cinque, Catello Di Martino, Zbigniew T Kalbarczyk, and Ravishankar K Iyer. Mutiny! how does kubernetes fail, and what can we do about it? In 2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 1–14. IEEE, 2024. [22] Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O’Neil, and Patrick O’Neil. A critique of ansi sql isolation levels. ACM SIGMOD Record, 24(2):1–10, 1995. [23] Philip A Bernstein, Colin W Reid, and Sudipto Das. Hyder-a transactional record manager for shared flash. In CIDR, volume 11, pages 13

[42] Faisal Nawab, Vaibhav Arora, Divyakant Agrawal, and Amr El Abbadi. Chariots: A scalable shared log for data management in multidatacenter cloud environments. In EDBT, pages 13–24, 2015. [43] Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In 2014 USENIX annual technical conference (USENIX ATC 14), pages 305–319, 2014. [44] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. The log-structured merge-tree (lsm-tree). Acta informatica, 33(4):351– 385, 1996. [45] PostgreSQL Global Development Group. PostgreSQL. https:// www.postgresql.org/, April 2025. [46] Sheng Qi, Xuanzhe Liu, and Xin Jin. Halfmoon: Log-optimal faulttolerant stateful serverless computing. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 314–330, 2023. [47] Anirban Rahut, Vinaykumar Bhat, Abhinav Sharma, Yichen Shen, Bartlomiej Pelc, Chi Li, Ahsanul Haque, Yash Botadra, Xi Wang, Michael Percy, et al. Myraft: High availability in mysql using raft. In EDBT, pages 743–752, 2024. [48] Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Computing Surveys, 22(4):299–319, December 1990. [49] Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, et al. Cockroachdb: The resilient geo-distributed sql database. In Proceedings of the 2020 ACM SIGMOD international conference on management of data, pages 1493–1509, 2020.

[50] Yacine Taleb, Kevin McGehee, Nan Yan, Shawn Wang, Stefan C Müller, and Allen Samuels. Amazon memorydb: A fast and durable memoryfirst cloud database. In Companion of the 2024 International Conference on Management of Data, pages 309–320, 2024. [51] Alexandre Verbitski, Anurag Gupta, Debanjan Saha, Murali Brahmadesam, Kamal Gupta, Raman Mittal, Sailesh Krishnamurthy, Sandor Maurice, Tengiz Kharatishvili, and Xiaofeng Bao. Amazon aurora: Design considerations for high throughput cloud-native relational databases. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1041–1052, 2017. [52] Michael Wei, Amy Tai, Christopher J Rossbach, Ittai Abraham, Maithem Munshed, Medhavi Dhawan, Jim Stabile, Udi Wieder, Scott Fritchie, Steven Swanson, et al. {vCorfu}: A {Cloud-Scale} object store on a shared log. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 35–49, 2017. [53] Maximilian Wiesholler, Florin Dinu, Javier Picorel, and Pramod Bhatotia. Indilog: Bridging scalability and performance in stateful serverless computing with shared logs. In Proceedings of the 17th ACM International Systems and Storage Conference, pages 1–13, 2024. [54] Yongle Zhang, Junwen Yang, Zhuqi Jin, Utsav Sethi, Kirk Rodrigues, Shan Lu, and Ding Yuan. Understanding and detecting software upgrade failures in distributed systems. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, pages 116– 131, 2021. [55] Zhiting Zhu, Zhipeng Jia, Newton Ni, Dixin Tang, and Emmett Witchel. Impeller: Stream processing on shared logs. In Proceedings of the Twentieth European Conference on Computer Systems, pages 637–653, 2025.

Eliminating Servers in State Machine Replication

Analyze & explore related research in Conceptio

Related documents