AirDB Moves Materialization into Clients and Shared Storage, but the Log Still Sets the Write Ceiling
DISTRIBUTED DATABASES AND SHARED LOGS
Serverless State Machine Replication removes a dedicated materializer tier rather than removing infrastructure. AirDB shows how shared snapshots shorten startup, while storage round trips, compaction backpressure and serialized appends define the trade-off.
By Ossam Hashim
KEY FINDINGS
- AirDB's clients jointly maintain one logical materialized state on external storage. A new client reads shared indexes and a bounded command-log tail instead of downloading a complete database snapshot before its first operation.
- In the authors' 100-minute injected-fault experiment, 99.02% of target-client operations complete within 100 milliseconds. That is a workload result under specified faults, not a production availability guarantee or immunity to storage outages.
- The read-only scaling experiment rises from roughly 300,000 operations per second with 10 client VMs to 2.7 million with 80, using a fully cached 1 GB dataset. Write-bearing workloads eventually plateau at the shared log and develop multi-second p99 latency.
- The design transfers work, not just state: clients perform materialization and need memory, storage access and compatible libraries. It favors clients near storage that value fast startup and elastic reads over the lowest single-operation latency.
What Serverless Means Here
A replicated database usually has more than a durable sequence of commands. Something must apply those commands and keep a readable state. Even if a shared log makes the command history durable, a service can remain unavailable while its materializer processes restart or restore snapshots.
In Eliminating Servers in State Machine Replication, Dohyun Park, Wenjie Hu, Xiangyao Yu, Mahesh Balakrishnan and Yongjoo Park move that work out of a dedicated server tier. Their Serverless State Machine Replication design, abbreviated S2MR, keeps both command history and materialized state in external storage. AirDB is their transactional key-value-store implementation, embedded in client processes.
The storage service still has servers. Client machines still run code and can fail. What disappears is the separate fleet responsible for maintaining private materialized database copies and serving every application request through that fleet. This changes the failure boundary; it does not abolish failures, consensus or resource bills.
Two Logs, Two Different Jobs
The command log establishes the durable order of operations. It is the source of truth. The state log stores incremental snapshots derived from ranges of those commands, with indexes that make partial state accessible. Many clients use the same logical snapshot history instead of each restoring a full private snapshot before doing useful work.
A client combines indexed materialized state with the newer command-log tail. For a key lookup, the relevant value may already be in a snapshot or may have changed in the tail. AirDB can fetch snapshot data speculatively while checking the tail, discarding the speculative value if a later command supersedes it. This overlaps storage access; it does not permit a stale value to become a valid linearizable read merely because it arrived first.
The distinction between one logical copy and one physical copy matters. The external storage backend is responsible for its own replication and durability. S2MR avoids independent full materializations at the application tier, not replicated storage underneath it. Local client caches are still useful and figure prominently in the performance results.
Who Compacts When There Is No Materializer Server?
Clients do. A library that notices too many unmaterialized commands starts producing an incremental snapshot. It first appends a begin-snapshot record identifying the range and a time-to-live, then checks that no earlier record claims a conflicting range. Completed snapshots go into the shared state log.
If a client disappears during compaction, another client can wait the declared interval after observing the record and attempt the work itself. The paper describes this without requiring synchronized global clocks. Coordination still comes from the log order, while the timeout allows work abandoned by a crashed participant to be picked up.
There is also explicit backpressure. At a configurable backlog threshold B, clients initiate snapshot creation. If the unmaterialized tail exceeds a soft bound of one plus epsilon times B, new commands stop being accepted until enough materialization finishes. This is a useful honesty check on the architecture: keeping startup work bounded can require sacrificing write admission when compaction cannot keep up.
The system therefore does not make materialization free. It spreads computation across clients and makes its results reusable. Capacity planning must include client CPU, client memory, storage calls and snapshot traffic, not simply subtract three database VMs from a spreadsheet.
An Ordered Intention Is Not Yet a Committed Transaction
AirDB can be configured for Snapshot Isolation or Strict Serializability. The evaluation uses Strict Serializability. A transaction begins by synchronizing to the command-log tail, which supplies its snapshot timestamp. It reads against that state and buffers writes, then appends an intention to obtain a position in the global order.
The library still checks conflicts before deciding whether that intention commits. Under Snapshot Isolation, it checks for intervening writes to the transaction's write set. Under Strict Serializability, it checks the read set. A transaction intention appearing in the log is therefore not evidence that its requested writes became committed state.
To support validation without retaining a complete modification history for every key, AirDB stores each key's last-modification timestamp in the materialized state. Snapshot merging overwrites values and those timestamps with newer partial-state results. This representation is tied to the protocol's ordered validation; it is not a general recipe for ignoring transaction history in arbitrary concurrency-control designs.
Storage Primitives Are Part of the Contract
AirDB's blob-backed log needs create-if-absent, atomic append, reads and size checks. Finite blobs become ordered segments, and metadata records segment creation and physical mapping. Extending the log is itself coordinated through that structure. A generic object store with a PUT operation is not automatically a compatible shared-log backend.
Transaction intentions must fit the implementation's append limit. The paper gives 4 MB for Azure Append Blob as its example, but that should not be repeated as a universal current Azure limit. Microsoft's current Append Block reference distinguishes older service versions with a 4 MiB maximum from version 2022-11-02 and later, which it documents with a 100 MiB preview maximum. Operators must check the selected API version and implementation path rather than enlarge a transaction on the strength of a headline limit.
The same reference documents append-position conditions and cautions about multiwriter redundant or delayed appends. Those API details do not replace AirDB's transaction protocol. Atomic appending is one building block; global ordering, conflict decisions, snapshot coordination and recovery still need a complete design.
Read the Availability Result as an Experiment
The authors compare AirDB with etcd and a disaggregated shared-log baseline called SLSMR. In the compound-fault experiment, the target client issues 1,000 reads per second over 100 minutes. Injected events include individual and cluster-wide VM reboots, disruptive update clients and a 0.1% failure probability for each storage I/O operation.
The realized timeline contains 15 individual VM reboots, two cluster-wide reboots and eight disruptive-client incidents. AirDB completes 99.02% of target operations within the 100 ms threshold, with 0.98% slower and 0.00% classified unreachable. The table reports 89.85% within threshold for etcd and 92.50% for SLSMR.
These percentages are not an outage forecast. The injected faults affect the architectures differently: dedicated-server reboots target etcd and SLSMR, while storage I/O failures target the shared-log designs. AirDB avoids dependence on the materializer VMs, but its surviving client and underlying storage path remain necessary. A common storage outage, lost credentials or an incompatible client library is not neutralized by the word serverless.
Cold Start Is Not a Warm Cache
The cold-start test measures startup initiation to the first completed transaction, not time to peak throughput. AirDB reads indexes and replays the tail, then fills its cache on demand. The baselines include VM provisioning and snapshot restoration. This is a deployment-path comparison, not merely a comparison of replay loops on already running machines.
Figure 7 labels the 1 GB case at 2.4 seconds for AirDB, 81.5 seconds for etcd and 64 seconds for SLSMR. Those plotted values do not reproduce the paper's introductory 45x and 10x summary claims for 1 GB, so this article uses the explicit figure values rather than repeating those multipliers. The cold-start experiment reports medians of three runs.
Warm-up continues after the first operation. With 1 GB data, the paper reports stabilization within roughly 150 seconds as the working set enters cache. At 5 GB with a 1 GB in-memory buffer, storage accesses increase latency variance and reduce throughput. Fast first access and fully warmed service are separate capacity-planning questions.
Read Scaling Does Not Remove Write Serialization
The scaling test uses a fully cached 1 GB dataset and increases client VMs from 10 to 80. Read-only throughput rises from about 300,000 to 2.7 million operations per second, with p99 around 25 ms. Those are aggregate results across growing client resources, not the performance of a single small process.
Workloads containing writes behave differently. The paper reports plateaus around 70,000 operations per second for update-heavy traffic and 17,000 for insert-only traffic, with p99 climbing to several seconds under high contention. The shared log's tail-segment append rate becomes the bottleneck. Eliminating materializer servers moves the serialization point; it does not make ordered writes scale without a ceiling.
AirDB also pays storage round trips at low load. In the main throughput-latency experiments, etcd has lower latency in the lower-load read-heavy and read-only region, even though AirDB reaches higher peak throughput. A separate Redis-backed log lowers AirDB latency, but introduces a different storage deployment. Azure-backed cost and failure results should not be silently combined with Redis-backed latency into one imaginary configuration.
A Deployment Decision, Not a Free Upgrade
This design is attractive for bursty coordination state or ephemeral clients that cannot justify restoring complete materialized copies before every useful operation. It is less compelling if the central requirement is minimum low-load latency or a sustained write rate beyond one shared log's append capacity. Clients far from storage also pay for the additional round trips.
Before adopting the pattern, test the append path under your actual contention, the client CPU cost of compaction, storage-failure behavior, cold and warm latency separately, and library-version transitions. The paper notes that changing the stored layout can strand older clients; a version marker can force a library update or a full replay. A shared snapshot is also a shared compatibility boundary.
The paper's Azure cost model includes client-memory overhead, which is better than treating client work as free. It remains a model with particular VM, memory and storage-operation assumptions, not a current quote or a complete bill for every client count. The fully cached 80-client throughput result should not be paired with a smaller cost example to claim a demonstrated price-per-operation ratio.
Assumptions and limitations
This is an analysis of one primary paper, not an independent database benchmark, correctness proof or production audit. Experimental numbers are the authors' results. Most evaluation uses 1 GB of YCSB data in one Azure virtual network; a specific scale test uses fully cached data across growing client VM counts. Those conditions do not establish wide-area performance, arbitrary transaction scalability or resistance to every hostile client.
Removing dedicated materializers does not establish a Byzantine security model for writers with storage credentials. Client-library correctness, access controls, storage durability and storage availability remain dependencies. The paper's injected I/O failures and disruptive-request tests should not be read as tests of arbitrary authenticated data corruption.
The cold-start summary multipliers and Figure 7 labels do not reconcile at the stated 1 GB point. The article preserves that uncertainty rather than deriving a preferred speedup. Azure append limits are version-dependent; the current documentation is included to prevent a historical example becoming a deployment rule.
Worked Example: Bounding the Unmaterialized Tail
This invented admission-policy illustration uses B=100 commands and epsilon=0.2, giving a soft limit of 120. At 99 commands it stays below the compaction trigger; at 100 it requests a snapshot. At 121 it pauses new appends. Advancing the materialized position from 0 to 80 leaves 41 unmaterialized commands, allowing normal admission again. The code models that decision only, not distributed leases, transaction validation or race-free enforcement.
from fractions import Fraction as F
bound = 100
slack = F(1, 5)
limit = bound * (1 + slack)
def policy(tail, materialized):
debt = tail - materialized
if debt > limit:
return "pause appends"
if debt >= bound:
return "make snapshot"
return "normal admission"
for tail, done in (
(99, 0), (100, 0),
(121, 0), (121, 80)
):
print(tail - done,
policy(tail, done))
assert limit == 120
Sources & Provenance
- Primary paper: Eliminating Servers in State Machine Replication, Dohyun Park, Wenjie Hu, Xiangyao Yu, Mahesh Balakrishnan and Yongjoo Park, arXiv:2611.01363, November 2026. Sections 2-4 support the mechanism; Section 5, Figures 7/9 and Table 1 support the scoped results and trade-offs.
- Microsoft Append Block reference, accessed November 16, 2026. Supports append semantics, version-dependent size limits and conditional-header/multiwriter cautions. It does not independently validate AirDB.
The admission example and deployment checklist are explanatory analysis, not measured AirDB behavior. No current pricing, production readiness or guaranteed availability is claimed.
Comments
Post a Comment