WalTier

WalTier is an embeddable tiered write-ahead log for Rust: memory, local disk, and S3, coordinated by nothing but S3 conditional writes. You get a durable, totally ordered log per resource with user-defined compaction and read-only replicas. No consensus, no leases, no leader election — the etag chain is the arbiter.

It's the generalized core of the pattern in Cursor's "git at any scale", with nothing git-specific in it.

Quick start

Implement WalApp — how entries build your state, how state folds into snapshots, and when to fold:

use waltier::{Entry, Lsn, Options, Reconcile, WalApp, WalError, WalStats, WalTier};

struct Kv;

impl WalApp for Kv {
    type State = BTreeMap<String, String>;

    fn init(&self) -> Self::State { BTreeMap::new() }
    fn apply(&self, state: &mut Self::State, lsn: Lsn, entry: &[u8]) { /* fold entry into state */ }
    fn restore(&self, snapshot: &[u8]) -> Result<Self::State, WalError> { /* rebuild from snapshot */ }
    fn compact(&self, base: Option<&[u8]>, entries: &[Entry]) -> Result<Vec<u8>, WalError> { /* fold into new snapshot */ }
    fn should_compact(&self, stats: &WalStats) -> bool { stats.live_entries >= 1024 }
    fn reconcile(&self, state: &Self::State, pending: &[u8]) -> Reconcile { Reconcile::Retry }
}

let mut wal = WalTier::open(store, Kv, Options::new("/var/lib/mylog"))?;
let lsn = wal.write(b"set a 1".to_vec())?; // LSNs are assigned for you: 0, 1, 2, ...

cargo run --example kv is a complete last-write-wins KV store against the filesystem-backed store.

How does WalTier work?

The whole log is one small S3 object (the WAL image), rewritten wholesale on every write with a compare-and-swap on its etag:

{prefix}wal            snapshot pointer + live entries (CAS'd on every write)
{prefix}snap/<lsn>-<n> immutable snapshots written by compaction

The image is its own manifest, so bootstrap is one GET. Entries are small metadata — every write re-uploads the whole image, so you write large payloads as separate immutable objects first (through the same ObjectStore), then append an entry that references them.

Writes and conflicts

write(entry) assigns the next LSN and CASes the new image. The S3 PUT is the commit point: an acked write is durable. If another instance wrote first, the PUT fails, WalTier pulls the missed entries into your state, and asks your reconcile:

  • Retry — append unchanged at the new tip (right when your entries commute)
  • Replace(bytes) — append a rewritten entry instead
  • Abort (default) — you get Conflict { entry } back with your state already refreshed

Compaction

Compaction is insert-triggered and never blocks writes. When should_compact fires, a background thread runs your compact and uploads the result as a new snapshot object. The fold installs on the writer's next PUT (or an explicit flush()): same CAS as the append, so compaction never contends with its own writer. A fold that loses to a remote compaction is discarded and its orphan deleted — there's no retry loop, the next trigger just tries again. Because the trigger lives inside write, replicas structurally cannot compact.

Replicas

Replica::open bootstraps from the same objects and refresh() polls with a conditional GET — a cheap 304 when nothing changed. A replica that fell behind a fold rebuilds from the snapshot via your restore. Replicas never write.

The tiers

  • Memory — your State, built by applying entries in LSN order
  • Local disk — a warm-start cache of the image and snapshot, validated by etag on open
  • S3 — the durable copy and the arbiter of truth

For immutable application payloads, TieredPayloadStore adds a bounded, checksum-validated RAM → local disk → S3 path. put_durable confirms the payload object remotely before caching it; pair the returned PayloadRef with write_idempotent to commit its reference into the CAS WAL. A successful client acknowledgment therefore means both the payload and its WAL reference were observed in S3. Local caches are accelerators and never part of the durability contract.

write_idempotent accepts a caller-generated OperationId. A lost PUT response is resolved by rereading the WAL, and an already committed operation returns its original LSN instead of appending a duplicate. Folded identities remain available up to Options::idempotency_window (4096 by default).

Failure semantics

  • A stale writer corrupts nothing — it loses CASes until it catches up.
  • An error can hide a PUT that landed (a timeout after S3 applied it). WalTier never applies unacked entries locally; the next refresh picks them up. A caller that resubmits appends a duplicate, so writes are at-least-once — make entries idempotent or catch duplicates in reconcile.
  • A crash between uploading a snapshot and installing it orphans one object; pair the snap/ prefix with a lifecycle rule if that matters to you.

Object stores

ObjectStore is the seam: conditional get, CAS put (If-Match / If-None-Match: *), plain put, delete.

  • S3Store (default feature s3) — blocking facade over the official AWS SDK for Rust. It supports custom S3-compatible endpoints and automatically detects --x-s3 directory buckets, selects their zonal S3 Express endpoint, and manages CreateSession credentials and refresh.
  • MemoryStore and FsStore — for tests and single-process development.

Testing

cargo test runs unit tests, integration tests (fencing, all reconcile modes, competing compactions, ambiguous failures), and deterministic simulation tests: seeded runs interleave writes, refreshes, compactions, and crash/reopen cycles across writers and replicas, with and without injected store faults. An oracle checks after every step that the committed history only grows, every instance's state is an exact prefix of it, and no snapshot object leaks or vanishes. A run is a pure function of its seed — reproduce with DST_SEED=<seed>, watch with DST_TRACE=1, scale with DST_SEEDS / DST_STEPS.

The waltier::sim module (feature sim, on by default) provides the seeded RNG and SimStore — fault injection and a latency model — and works just as well for testing apps built on WalTier.

Benchmarks

cargo bench runs against a simulated S3 (sleeps RTT + bytes/bandwidth per op):

cargo bench --bench wal -- --rtt-ms 15 --mbps 100 --writes 200

It reports write latency percentiles and throughput, per-write cost growth without compaction, cold vs warm open, and replica poll cost. Commit latency is RTT-bound; with no store latency the library sustains ~70k writes/s on one thread.

Production S3 benchmark

waltier-bench is the real-provider harness. It performs an authenticated CAS litmus, creates equal-count 4 KiB, 1 MiB, and 16 MiB durable payload cohorts, measures a hot WAL and sharded WALs, runs concurrent live writers and replicas at five polling intervals, suppresses notification hints and pauses followers across compaction, runs isolated writer-head plus reader-head/replica cache processes, forces RAM/disk/S3 read paths, races compactions, verifies acknowledged payloads, and publishes versioned JSON and JSONL artifacts for the React dashboard.

Follower results separate steady-state commit-to-apply latency from declared notification-loss and pause/recovery windows, while retaining a labeled all-operations aggregate for diagnosis.

Credentials are read from .env (which is ignored by git):

AWS_REGION=us-east-1
AWS_ACCESS_KEY_ID=...
AWS_SECRET_ACCESS_KEY=...
S3_BUCKET=your-bucket

AWS_ENDPOINT_URL_S3 is optional for AWS. Set it for a compatible custom service, for example https://t3.storage.dev; directory buckets ending in --x-s3 always use the AWS SDK's generated zonal endpoint. Set AWS_SESSION_TOKEN as well when the base IAM credentials are temporary. The SDK independently creates, caches, and refreshes the short-lived S3 Express bucket session.

Useful commands:

# Disposable conditional-write correctness gate
cargo run --release --bin waltier-bench -- preflight

# Live durable acknowledgments and tail replication. Defaults to 32 WALs,
# 8 KiB payloads, unthrottled peak load, and 60 seconds (120-second maximum).
cargo run --release --bin waltier-bench -- live

# Development run
cargo run --release --bin waltier-bench -- run --profile smoke \
  --results-dir ./benchmark-results

# Standard 2/10/49 GiB and full 20/100/200 GiB cache/dataset profiles.
# Every profile measures 4 KiB, 1 MiB, and 16 MiB payloads.
# Both retain their remote prefix by default; the global safety ceiling is 500 GiB.
cargo run --release --bin waltier-bench -- run --profile scaled
cargo run --release --bin waltier-bench -- run --profile full

# Continue an interrupted run from its durable payload manifest. Resume purges
# and reruns that run's timed load/chaos/follow prefixes before measuring reads.
cargo run --release --bin waltier-bench -- run --profile full \
  --resume-run <exact-run-id>

cargo run --release --bin waltier-bench -- list-runs
cargo run --release --bin waltier-bench -- cleanup <exact-run-id>

The scaled and full performance phases give each payload size a 15-second warmup followed by a one-minute measurement window. WAL pressure is measured at 1, 16, 32, and 64 shards. Hot and warm read sets are deterministically preconditioned in isolated per-size caches before their timed windows; cold reads use zero-capacity caches. A longer soak remains available through --warmup-secs and --measure-secs. The 200 GiB full dataset remains twice the writer's disk-cache capacity and leaves 300 GiB below the 500 GiB ceiling for WAL images, historical object versions, snapshots, and chaos artifacts. Existing retained objects count against the same ceiling and can cause a new run to be refused before it writes anything. For versioned general-purpose buckets, cleanup purges historical versions and delete markers; for S3 Express directory buckets, it lists and deletes current objects because versioning is unavailable. Local caches use the private /var/tmp/waltier-bench-cache scratch root by default (override it with --cache-root) and the exact run directory is removed after its result bundle is published.

Writer-head reads run in an isolated process which exits before reader-head and replica processes start concurrently. This models dedicated machines without artificially summing the writer's 20 GiB RAM cache with all follower caches on one benchmark host. RAM and disk LRU metadata are themselves bounded, so a hot hit-only workload cannot grow bookkeeping with total operation count.

The publication report source lives in report/. It ingests the four schema-4 provider bundles into an allowlisted public snapshot, builds interactive Apache ECharts figures, and exports every chart as SVG, 2x PNG, and CSV:

cd report
npm install
npm run ingest -- /media/data/wal-bench/results
npm run build
npm test

The generated static site is written to report/dist/. Its production Caddy configuration is deploy/wal-report.caddy; only the curated build output is deployed to /srv/wal-report, while raw result bundles and credentials remain outside the web root. The published report is available at https://wal-report.trylle.dev.

See docs/benchmarking.md for the exact methodology, docs/bench_live.md for live-session setup and operation, and docs/bench-runs/run-1.md for the first full run's hardware, caveats, correctness evidence, and results.

What WalTier doesn't do

  • Route requests to the current writer — run one writer per log and let stale ones lose CASes.
  • Retry a lost compaction eagerly — the next valid trigger retries.
  • Expose an async API — ObjectStore remains blocking; S3Store bridges the official async SDK through an internal Tokio runtime.