Viewstamped Replication

viewstamped_replication is a standalone, protocol-generic OTP application for replicating deterministic state machines with Viewstamped Replication (VSR). It does not depend on Concord. Concord depends on this application and uses it as its only replicated engine.

Status

This application implements the pure protocol kernel, supervised replica runtime, client sessions, normal operation, view changes, recovery, state transfer, storage adapters, transport adapters, and telemetry emission. It is the replication runtime for Concord 3.0.

The supported production profiles are fixed, explicitly configured groups of one through six replicas. Current operational constraints are:

• fixed membership with no reconfiguration protocol;
• no automatic log-compaction or storage-retention policy;
• applied client results are retained without eviction, so deployments that continually create new client identities need a future replicated session-retirement policy to bound the durable client table;
• no storage-format migration between incompatible VSR releases;
• snapshots are explicit rather than managed by a production checkpoint policy.

Fault and quorum model

VSR assumes crash failures, not Byzantine failures. A fixed, ordered configuration contains one through six replicas and requires a strict majority quorum of floor(n / 2) + 1. It tolerates floor((n - 1) / 2) crashed replicas. Even-sized groups therefore have the same failure tolerance as the preceding odd-sized group while requiring one additional quorum vote.

Membership is explicit and fixed. It is never inferred from connected distributed Erlang nodes. The primary for a view is selected deterministically from the view number and the ordered configuration.

Runtime and storage

The application supervisor owns a registry and a dynamic replica supervisor. Multiple independent groups may run in one VM. Public entry points include:

ViewstampedReplication.start_replica(opts)
ViewstampedReplication.stop_replica(group_id, replica_id)
ViewstampedReplication.status(group_id, replica_id)
ViewstampedReplication.primary(group_id, replica_id)
ViewstampedReplication.snapshot(group_id, replica_id)
ViewstampedReplication.command(group_id, operation, client: client)
ViewstampedReplication.read(group_id, operation,
  replica_id: replica_id,
  replicas: members
)

ViewstampedReplication.Storage.Memory is volatile and intended for tests. ViewstampedReplication.Storage.File provides a checksummed, fsynced WAL, atomic checkpoints, configuration identity validation, and truncation of incomplete version-two WAL tails whose length header is checksummed. Complete corrupt records and ambiguous incomplete version-one records fail recovery without modifying the WAL. A tail ending in a partial magic prefix, or in the complete magic without a version byte, is treated as an incomplete append and truncated. It does not yet provide an automatic compaction or retention policy.

WAL records and checkpoints have the same fixed 256 MiB ETF payload limit. Oversized writes fail before changing the WAL or replacing a checkpoint, so everything acknowledged to disk remains readable by recovery. State that grows beyond one checkpoint record requires a future chunked snapshot format; the adapter does not silently split or truncate it.

Writes default to version one for rollback compatibility. The file storage option write_version controls both new WAL records and rewritten checkpoints. Set write_version: 2 only after every deployment has passed the old-reader rollback window. Once either a version-two WAL record or checkpoint exists, setting write_version: 1 does not downgrade it, and opening that directory with an older reader is unsafe. A later binary rollback requires restoring a separately verified version-one-compatible backup; no automatic downgrade is provided.

State transfer must persist the transferred snapshot together with its matching hard state, log, commit/applied counters, and client table. A custom ViewstampedReplication.Storage adapter must implement install_snapshot_state/3 as one crash-atomic operation. The runtime returns {:atomic_snapshot_state_install_not_supported, adapter} instead of attempting a non-atomic fallback when that callback is absent.

ViewstampedReplication.Transport.Local routes through the local registry and supports an injectable delivery function for deterministic fault tests. ViewstampedReplication.Transport.Distribution routes only through explicit endpoint maps; connected Erlang nodes are never treated as membership.

Architecture

The protocol core is pure and deterministic:

event + protocol state
        |
        v
ViewstampedReplication.Protocol.step/2
        |
        v
new protocol state + ordered effects

The protocol does not send messages, read clocks, schedule timers, access storage, emit telemetry, or invoke the replicated state machine. The supervised replica runtime interprets its ordered effects.

Replicated services implement ViewstampedReplication.StateMachine. Operations must be deterministic and free of arbitrary external side effects.

Performance benchmark

Committed-prefix validation reuses an equal immutable log and otherwise compares the retained overlap in a single ordered pass. It never iterates through compacted historical operation numbers or performs a list-index lookup for each committed position. Changed logs still reject missing, reordered, or rewritten retained committed entries, including metadata changes. Snapshot-compacted positions retain their existing snapshot trust boundary; quorum rules are unchanged.

The public pure Protocol.step/2 API accepts caller-constructed states and remains exhaustive. It validates retained log contiguity, applied-request uniqueness, and committed-prefix preservation. Its ready singleton reads use an untrusted derived index to bound process-heap allocation, but still check every retained entry's exact indexed operation number. Missing, malformed, or stale indexes fall back to the complete uniqueness check; forged metadata cannot conceal duplicates. Pure transitions retain linear history validation and list append/fetch costs. Constructing a canonical log from a list now validates it in one pass.

The supervised replica owns an event-only transition closure. Its initial state receives full validation and a freshly built applied-request index; callers cannot substitute state or supply a validation flag. Normal singleton and multi-voter client writes use immutable indexed logs. Exact sequential apply acknowledgements check and update only the newly applied request's index entry, including when another committed operation is ready to apply. The existing protocol handlers still produce the ordered append, commit, apply, applied-state persistence, and reply effects. Scalar and changed-entry checks preserve their operation-number and duplicate-request invariants without revisiting unrelated committed history. Exact retries reuse their recorded result. Ready singleton reads reuse the unchanged owned state's validity.

The owned normal path also handles current-view Prepare appends and exact retained duplicates, PrepareOk acknowledgements within the local log, and Commit messages within the local operation bound. All envelope identity and membership checks remain in the shared handlers. Pipelined client appends and cumulative acknowledgements may visit the uncommitted suffix; their work does not scan the retained applied prefix. An idle normal primary's heartbeat uses the current emitted token and reschedules without rebuilding its history, for any membership size. Heartbeats with uncommitted retries remain on the exhaustive path.

Recovery, snapshots, view changes, state-transfer gaps, future-view messages, and other events outside these guards convert to the canonical representation and use the exhaustive protocol kernel. Administrative :sys.replace_state/2 calls and direct OTP callback invocation bypass runtime state ownership and are not supported protocol-state ingress.

The private indexed log and applied-request index occupy memory proportional to retained history. Immutable map insertion and lookup replace full-list copying and scans on ordinary runtime writes; they do not imply literal constant-time map work or automatic retention. Built-in Memory storage and File storage's in-memory mirror also use indexed logs. Recovery results, wire/state-transfer payloads, and both File checkpoint writers retain canonical ordered-list logs. WAL operations, checkpoint formats, quorum requirements, and rollback compatibility are unchanged. Snapshot and recovery boundaries may rebuild these private representations in proportion to retained history.

The ordinary runtime paths therefore avoid history-wide protocol and built-in storage-mirror work without requiring compaction. The original pure protocol diagnostic still has linear CPU work because its arbitrary input state must be checked on every call. State-machine admission/materialization, client-table persistence, fsync, network latency, pending quorum work, and mailbox waiting remain separate costs. Singleton runtime regressions retain 1,000/2,000/4,000 entries; legal three-voter protocol flows and emitted idle heartbeat tokens are also checked at 1,000/10,000 entries. History traversal traces are measured separately from exhaustive parity checks. These diagnostics do not establish HTTP timeout causes or downstream throughput acceptance.

Run the explicit local-memory benchmark to compare command throughput and p50/p95/p99 latency across all supported cluster sizes:

mix do --app viewstamped_replication cmd mix test \
  test/performance/cluster_size_benchmark.exs --trace

The benchmark defaults to four concurrent clients with 100 commands per client for each cluster size. Override the workload with VSR_BENCHMARK_CLIENTS and VSR_BENCHMARK_OPERATIONS_PER_CLIENT. Optional regression gates are available through VSR_BENCHMARK_MIN_OPS_PER_SECOND and VSR_BENCHMARK_MAX_P99_US.

This benchmark uses in-memory storage and local transport so it measures the protocol and OTP runtime rather than disk or network performance. Production results must also be measured with the deployment's actual storage, network, and hardware.

Terminology

This application uses the VSR terms primary, backup, replica, view, view change, operation number, and commit number.

See the Viewstamped Replication application ADR for the architectural decision and scope.