Weekly Paper Notes — one of the top picks from the 2026-11-07 CS paper digest. Area: Distributed Computing / Databases.
Authors: Dohyun Park (UIUC), Wenjie Hu (UW–Madison), Xiangyao Yu (UW–Madison), Mahesh Balakrishnan (Meta; work done prior), Yongjoo Park (UIUC) arXiv: 2611.01363 · PDF
TL;DR
State machine replication (SMR) is how etcd, ZooKeeper, Spanner, CockroachDB and their relatives keep state consistent: agree on a total order of commands, then have servers apply them. Over the last decade the shared-log line of work (CORFU, Tango, Delos, Scalog, LazyLog) moved the log out of those servers onto a separate storage layer. Durability improved. Availability still depends on a tier of servers that materialize state, and those servers crash, get upgraded badly, take minutes to cold-start, and get overloaded by one noisy tenant.
This paper removes that tier. In Serverless SMR (S²MR), the command log and the materialized state both live on external storage, and a client-side library reads and writes them directly. There’s one logical copy of state, kept as incremental snapshots in a second shared log that clients take turns producing. The prototype, AirDB, is a transactional key-value store in about 6,600 lines of Go on Azure Blob append blobs. Against three-node etcd and a shared-log SMR baseline it reaches up to 4× etcd’s read throughput, cold-starts a 1 GB database in 2.4 s where the baselines need over a minute, and keeps 99.02% of operations within a 100 ms SLA through 100 minutes of injected faults, against 89.85% for etcd.
Where the servers went
Figure: Conventional, disaggregated, and serverless SMR. Source: arXiv:2611.01363, Figure 1.
The paper opens with a short history. Lamport’s and Paxos’s original framing separated the proposers, acceptors and learners. Chubby, ZooKeeper and Raft merged all three roles into one process per machine for performance and easy deployment, so each server became responsible for both durability and availability. Shared-log systems split them apart again: a log service holds the acceptor role, and servers become materializers.
The authors argue that the two layers are different kinds of software. Storage is simple, slow-changing, and has bounded-cost APIs (read this address). Materializers are diverse, change constantly, and expose APIs where one request can cost unbounded work (scan the whole database). So durability sits on the reliable layer while availability still rests on the fragile one. The paper lists the ways that fragile layer fails in practice: rolling upgrades that crash-loop every replica, Kubernetes preempting or mislabelling healthy stateful pods, slow cold starts that force you to keep idle replicas warm, and rogue tenants with no good isolation.
The obvious fix, running an ordinary materializer inside every client, doesn’t work either. Each client would have to download a multi-gigabyte snapshot before its first operation, every client repeats the same replay work, and naming one client as the materializer just recreates the server.
How S²MR works
S²MR uses two shared logs on external storage.
The command log works like any shared log: clients append commands, and the log’s order is the ground truth.
The state log holds incremental snapshots. Each snapshot is the partial state produced by applying one range of commands, together with an index. Partial states merge by upsert, so Φ(0,k] ⊕ Φ(k,j] = Φ(0,j], and compaction can be applied recursively.
To read a key, the library checks the merged snapshot indexes (logarithmic in state size) and applies whatever commands sit in the not-yet-materialized tail. To keep that tail short, a timely snapshot rule applies. Once the tail reaches B commands, any library may start compacting it. Above (1 + ε)·B it stops accepting new commands until materialization catches up, which also rate-limits writers automatically.
Coordinating compaction uses the log itself. A library appends a begin-snapshot record naming the range and a TTL, then reads back to check that no earlier conflicting record exists. If a compactor crashes, another library that sees no snapshot appear within TTL of its own local clock takes over. No global clock is needed. The authors show per-client I/O is O(reads · log|Φ| + appends), roughly linear in the client’s own activity and sublinear in state size.
Transactions in AirDB. AirDB runs optimistic concurrency control over the log, similar to Hyder. A transaction takes the current log tail as its snapshot timestamp, executes speculatively, then appends its read set (for strict serializability) or write set (for snapshot isolation) as one command. Its position in the log is the commit timestamp. It commits if no key in that set was modified between the two offsets. State only needs the last-modified offset per key for this check, so memory stays proportional to state size, not log length.
Logs on blobs. The shared log is built from fixed-size Azure append blobs, with a “meta segment” recording which blob is the current tail. Any client can roll over to a new segment. A Redis-backed segment works too, which the evaluation uses to show how storage latency affects the system.
Two optimizations matter for latency. Speculative reads fetch from the snapshot and the log tail in parallel rather than one after the other. A bus-stand thread keeps exactly one outstanding tail check per client, at most every 10 ms, and every read waiting at that moment shares it as its linearization point.
Results
All tests use YCSB on 1 GB (one million 1 KB pairs), on Azure D4_v3 VMs, compared with three-node etcd and SLSMR, a shared-log multi-master baseline on the same Azure Blob log.
- Throughput. On read-heavy and read-only mixes AirDB reaches up to 2.5× SLSMR’s peak throughput and 4× etcd’s. On read-modify-write it reaches up to 3× etcd. etcd has lower latency below roughly 50K ops/s. AirDB pays a fixed storage round trip to validate the log tail, but that cost stays flat while etcd’s latency climbs once the Raft leader’s CPU saturates.
- Server failures. Killing one node every 30 seconds, etcd goes down at the third failure (lost quorum) and SLSMR at the fifth. AirDB has no nodes to kill.
- Noisy neighbours. When bad clients flood the system at t = 30 s, the good client’s latency jumps immediately on etcd and SLSMR. On AirDB it barely moves, since the bad clients load blob storage, which is built for multi-tenant isolation.
- Cold start. etcd and SLSMR need VM provisioning plus full snapshot restore, from about 52 s at 100 MB to 278 s (etcd) at 5 GB. AirDB reads only snapshot indexes and the log tail: 0.9 s at 100 MB, 2.4 s at 1 GB, 6.1 s at 5 GB, then fills its cache lazily.
- Chaos. Over 100 minutes of random VM reboots, two cluster-wide reboots, eight bad-client bursts and a 0.1% storage-error rate, AirDB keeps 99.02% of reads under 100 ms with zero unreachable operations. etcd keeps 89.85% with 1.66% unreachable, and SLSMR 92.50% with 1.28% unreachable.
- Cost. At 1M operations a month, AirDB costs $41.32 against $924.18 for a three-VM etcd cluster, about 22× cheaper and 7.5× cheaper than SLSMR. With no caching at 100M operations it still keeps a 3× advantage over etcd.
Trade-offs the authors acknowledge
The authors name the costs. Every operation pays a round trip to storage, so the design suits clients in the same data centre as their storage. Upgrading the on-storage format is hard, because all the logic lives in client libraries. A client with an old library can’t read a new format, so the state must carry a version number, and a major version change means either upgrading every client or replaying the whole log. Transactions are bounded by the maximum append size (4 MB on Azure append blobs). The evaluation also uses uniform keys for the RMW workload, which means low contention, so how optimistic concurrency behaves on a hot key over a log with millisecond round trips isn’t tested.
Trust is a less obvious issue. With no server in the path, every client has write access to the shared state, and the paper’s model assumes authenticated, well-behaved library code. A buggy client that appends a malformed snapshot can corrupt state for everyone. Server-based SMR contains that kind of fault behind an API.
Why this matters
The paper takes the separation of ordering from state, which the shared-log literature has argued for since CORFU, as far as it can go. For coordination-service-sized state (etcd defaults to a 2 GB limit, and the evaluation uses 1 GB), the claim is that you can drop the cluster and use an object-store bucket plus a library, getting better availability and a much smaller bill. Anyone running a small etcd or ZooKeeper only to hold configuration, leases or metadata should look at it. So should anyone building serverless or agent workloads that need a strongly consistent store without paying for idle replicas.
The same approach shows up elsewhere: Delta Lake and Iceberg commit over object storage, and Boki and Halfmoon build stateful serverless functions on shared logs. S²MR states the general version: a log on storage plus cooperatively compacted snapshots is enough to implement SMR without servers.
Read alongside
- Schneider, Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial (ACM Computing Surveys, 1990): the standard SMR reference.
- Balakrishnan et al., CORFU: A Shared Log Design for Flash Clusters (NSDI 2012) and Tango: Distributed Data Structures over a Shared Log (SOSP 2013): where materializing state from a shared log started.
- Balakrishnan et al., Virtual Consensus in Delos (OSDI 2020): the production shared-log system at Meta that this work builds on.
- Bernstein, Reid, Das, Hyder: A Transactional Record Manager for Shared Flash (CIDR 2011): optimistic transactions over a shared log, the model for AirDB’s commit protocol.
- Luo et al., LazyLog: A New Shared Log Abstraction for Low-Latency Applications (SOSP 2024).
Links
📄 arXiv abstract · 📄 PDF
Part of the Weekly CS Paper Digest series. Summary written from a close read of the preprint; figure cropped from the arXiv PDF (CC BY 4.0).