viewstamp

Pure-Rust Viewstamped Replication: a Sans-I/O consensus state machine, QUIC and TCP+TLS transports, real-I/O drivers, and a deterministic adversarial simulator.

Introduction

viewstamp is a Viewstamped Replication consensus library in pure Rust. The protocol logic lives in a single Sans-I/O "super state machine" — modeled on quinn-proto: it takes events as inputs (handle_*) and emits actions as outputs (poll_*), owning no I/O, no clock, and no randomness source. TigerBeetle's src/vsr/replica.zig is the correctness reference for the protocol logic, including its storage-fault model: WAL corruption (torn writes, bit-rot, misdirected reads) is part of the fault model, not an afterthought, and faults surface as data the protocol repairs from peers — never as panics.

Why viewstamp

• Sans-I/O core — the consensus logic is a pure state machine with no I/O, clock, or RNG of its own, so it ports to any runtime, embeds anywhere, and is exhaustively testable in a single thread. Batteries-included compio and tokio/smol drivers are provided when you do want real I/O.
• Storage faults are first-class — torn writes, bit-rot, and misdirected reads are part of the fault model (following TigerBeetle), repaired from peers rather than crashing the process.
• Deterministic replay — a whole cluster run is a pure function of one seed, so any failure the adversarial simulator finds replays exactly (see the VOPR).
• Feature-complete VR — not just the happy path: dynamic reconfiguration, non-voting learners, content-addressed incremental snapshots, and edge batching all ship today (see Capabilities).
• no_std + alloc capable — the core builds without the standard library.

Status: pre-0.1 and unpublished; the wire and on-disk formats are unstable and upgrades are flag-day. See Status.

Contents

• Threat model
• Workspace
• Capabilities
• Quickstart
• The embedder contract
• Validation: the VOPR
• Status & versioning

Threat model (non-Byzantine, crash-fault-tolerant)

viewstamp is crash-fault-tolerant for a trusted cluster, exactly like TigerBeetle — explicitly not Byzantine-fault-tolerant. It tolerates crash-stop failures, storage faults, and network partitions, assuming honest, authenticated participants. Authenticating a message's sender is the driver's job (the QUIC transport mandates cluster-private mTLS; the proto keeps a cheap sender-binding ingress backstop against a buggy or misrouting driver). Cryptographic message authentication against a genuinely malicious replica — signatures, BFT voting — is out of scope.

Workspace

Crate	What it is
viewstamp	The batteries-included umbrella: re-exports the consensus core as viewstamp::proto and, behind driver features, the real-I/O drivers as viewstamp::{compio, reactor} — plus viewstamp::{tokio, smol}, the reactor drivers with the runtime pre-pinned so callers never name it. Depend on this one crate and select a driver feature.
viewstamp-proto	The Sans-I/O consensus core (no_std + alloc capable), plus feature-gated Sans-I/O transports: tcp (length-prefixed framing + connection lifecycle + peer routing), tls (rustls record layer), quic (quinn-proto with mandatory cluster-private mTLS).
viewstamp-driver	The runtime-agnostic driver core shared by both driver crates: the embedder Handle/Command surface, in-flight submit budgets, the DriverConfig tuning surface, the Clock, and DriverError.
viewstamp-compio	Real-I/O drivers on the compio proactor runtime: a QUIC driver and a TCP/TLS stream driver. Generic over storage, state machine, and identity — they bundle no backend.
viewstamp-reactor	Reactor-I/O drivers on tokio or smol via the agnostic runtime abstraction: a QUIC driver and a TCP/TLS stream driver. Generic over storage, state machine, and identity — they bundle no backend.
viewstamp-simulation	The deterministic simulation harness + the VOPR adversarial sweep (see below). Also home of the in-memory Wal/Superblock fixtures.

Capabilities

Beyond the core VR replication + view-change + recovery paths, the following ship today:

• Dynamic reconfiguration — the membership mode is a compile-time choice on the Endpoint<S, R> parameter (a sealed Reconfig trait): RestartOnly (the default — a fixed set, membership only changes across a coordinated restart) and SingleChange (evolve membership one step at a time on a live cluster, driven through consensus). The two form a compile-time capability ladder — SingleChange subsumes RestartOnly — and the planner (plan_reconfiguration, MembershipTarget) turns a desired target into a legal sequence of single steps drawn from a closed four-delta vocabulary: AddLearner/PromoteLearner grows the voting set (a new voter always catches up as a learner first), and DemoteVoter/RemoveLearner shrinks it — the mirror image, so a departing voter keeps a live learner seat and its durable copy of the committed log until its removal is proven safe, never a direct ejection. A shrink that would lower crash tolerance is refused unless the caller names AcceptReducedFaultTolerance up front — capacity is never cut silently. Multi-change joint consensus is future work.
• Non-voting learners / standbys — replicas that receive the log and stay current without counting toward quorum, so quorum math is unchanged. A learner catches up and is then promoted to a voter through a fresh durable-prefix proof at promotion time — the read/standby and safe-onboarding scale-out path, rather than a bigger voting set. The same learner seat is also the shrink path's safety margin: a demoted voter lingers here, still a reachable repair donor, until its removal is garbage-collected.
• Content-addressed incremental snapshots — checkpoints are a content-addressed block DAG behind the BlockStore trait, so a laggard state-syncs only the blocks that actually changed instead of re-fetching the entire state machine on every transfer.
• Edge batching — many small operations share one consensus op through a batching aggregator, with per-unit reply demultiplexing (see below).
• Three Sans-I/O transports — length-prefixed TCP, TLS-over-TCP (rustls record layer), and QUIC (quinn-proto), all driven by the same consensus core.

Feature flags

viewstamp-proto (the core crate):

Feature	Enables
std (default)	The standard library. Disable (--no-default-features) for a no_std build.
alloc	Heap types without the OS — the consensus core builds no_std + alloc.
tcp	Sans-I/O length-prefixed TCP framing, connection lifecycle, and peer routing.
tls	A rustls record layer over tcp (pick a provider below).
tls-rustls-ring	The ring crypto provider — pure Rust + asm, builds on every platform.
tls-rustls-aws-lc-rs / …-fips	The aws-lc-rs provider (and its FIPS build).
quic	The quinn-proto QUIC transport with mandatory cluster-private mTLS (reuses the tls provider).

Runtime drivers select their reactor: viewstamp-compio (the compio proactor) and viewstamp-reactor (tokio or smol).

Quickstart

A runnable three-node cluster over real loopback TCP lives in viewstamp-compio/examples/three_node.rs:

cargo run -p viewstamp-compio --example three_node

The same embedding over the reactor drivers (on tokio) lives in viewstamp-reactor/examples/three_node.rs:

cargo run -p viewstamp-reactor --example three_node --features tokio

Each boots three in-process replicas, submits a few operations through a backup (which relays to the primary), prints the committed replies, and shuts down. The comments narrate each embedder obligation — storage, client identity, the driver handle — and the examples use the simulation crate's in-memory storage, which you replace with your durable implementation in production.

The embedder contract

The proto owns no log and no disk: you supply a Wal (the operation log) and a Superblock (the durable root + checkpoints), and the consensus core orchestrates over them. The contracts those implementations must honor — completion-means-durable, writes-never-fault, header durability independent of bodies, crash-atomic serialized root writes, drain-in-flight-before-recover — are consolidated in the storage module documentation. Read that before writing a backend; each clause is load-bearing for committed-op survival.

The state machine side is three methods (apply / snapshot / restore), required to be deterministic across replicas.

Edge batching

Many small operations can share one consensus op: callers hand individual units (or atomic groups) to a batching aggregator, which consumes a driver Handle, packs everything queued into the next request body while one is in flight, and demultiplexes each committed reply back to its callers. Your apply then decodes each committed body with the shared codec — BatchView in, one result per unit out through a ReplyBuilder:

let (batch, pump) = aggregator(handle, BatchConfig::new(max_unit_reply_len));
// spawn pump.run() exactly like the driver's own run(); then, from any task:
let reply = batch.submit(unit).await?;

A body applies atomically (it is one op) and a group is never split across bodies, but batches are not transactions — units stay independent operations that share an op. The codec layout, the request/reply budget contracts, and the aggregator's retry-contract error taxonomy are documented in the batch module and the aggregate module.

Validation: the VOPR

The flagship test rig is a VOPR-style deterministic simulator (viewstamp-simulation): N endpoints + client models in one thread over a virtual network with a virtual clock and one seeded PRNG, so a whole cluster run is a pure function of its seed — any failure replays exactly.

Each seed builds a fresh cluster (size 2–6) and explores a randomized adversarial schedule within the crash-stop fault model (a quorum always survives):

• Process faults — crash + restart, with in-flight (un-fsynced) WAL appends discarded at the crash boundary; a wipe lane where a crashed replica rejoins with an empty disk.
• Network faults — reorder, drop, duplicate, delay; a hold lane where messages are held arbitrarily long and released late; a one-way (asymmetric) partition lane and a slow-replica (gray-failure) lane.
• Storage faults — read faults, torn writes, bit-rot, misdirected reads (a read returning a wrong-but-valid sibling slot), recover-time fault injection.
• Structural axes — async WAL + async superblock completion windows, small and large checkpoint intervals, a physical bounded-WAL ring on a third of seeds (stall-before-wrap, recovery off a wrapped ring), and a client-churn lane driving the session-cap eviction.

Safety, durability, view-monotonicity, boundedness, append-before-ack, and ring-residency invariants are checked every tick; liveness is judged over calm windows on virtual time. The committed CI gate sweeps seeds 0..64 plus a pinned list of every seed that ever caught a real bug; a nightly release-mode workflow sweeps 0..1024 (plus the hold lane) and is verified clean out to 0..2048. To replay one seed:

VOPR_SEED=<seed> cargo test -p viewstamp-simulation --test vopr replay_single_seed -- --ignored --nocapture

Byte-decode surfaces (Message, the superblock root, the WAL header codec, the stream transport ingress) are additionally fuzzed under cargo fuzz (see fuzz/).

Status

Pre-0.1 and unpublished. The wire format and the on-disk formats are unstable: versions are checked and mismatches rejected, but there is no cross-version compatibility story yet — upgrades are flag-day. APIs will move. The minimum supported Rust version is 1.95.

Versioning and upgrades

The wire protocol and the durable formats version independently, so a message-format change can never invalidate data already on disk:

• Messages ride a protobuf envelope, normatively defined by the schema (proto/viewstamp/v1/messages.proto); viewstamp-proto/WIRE.md pins the byte-level semantics. There is no per-message version field — the Labeled hello's HELLO_VERSION is the single wire-version fence instead, and mixed-version peers reject each other at the handshake before any consensus frame is trusted. An additive protobuf field needs no bump; a semantic break to the wire bumps HELLO_VERSION.
• Durable formats carry their own versions (viewstamp-proto/src/storage/mod.rs): the superblock root leads with SUPERBLOCK_VERSION and decodes by compatibility range — the whole layout-compatible range 1..=SUPERBLOCK_VERSION is accepted, so a wire-only bump never strands a persisted root — and each WAL slot header leads with its own HEADER_VERSION.

Pre-1.0 the cluster upgrade story is flag-day: stop all replicas, upgrade all of them, restart — mixed-version clusters are rejected at connect time by the handshake fence above. Rolling upgrades require wire-version negotiation (accept a range, speak the lowest common version), which is future work.

License

viewstamp is under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE, LICENSE-MIT for details.

Copyright (c) 2021 Al Liu.