Module vsr 

Replication: a primary-backup protocol in the style of Viewstamped Replication Revisited, as a pure state machine.

Each shard group has 3 or 5 replicas. In a view, one replica is primary (view % n). The primary appends entries (the shard’s records, in canonical encoding, one per LSN) and sends them to the backups at once, before its own flush finishes. A backup appends, flushes, and answers PrepareOk with how far it is durable. An entry is committed when a quorum (n / 2 + 1, the primary included) holds it durably in the current view; the primary releases outputs and opens step gates at the commit position, so nothing leaves the process on state a minority of failures could take back.

Entries form a hash chain (parent is the previous entry’s checksum), so a replica can verify entries it receives from any peer.

View change. A backup that stops hearing from the primary starts view v + 1 (StartViewChange). With a quorum of those, replicas send their log state (DoViewChange) to the new primary, which takes the log with the highest (last normal view, op), fetches any committed entries it is missing, and announces the view (StartView). Backups drop uncommitted entries that do not match and fetch what they lack. A primary that is cut off cannot commit (it has no quorum), so its outputs never leave.

Protocol-aware recovery. A replica restarting with a damaged entry in the middle of its log (see crate::segment::Tail::Corrupt) does not truncate committed work. It stays Recovering, takes no part in view changes, fetches the missing range from peers, verifies it against the hash chain, and rewrites its log from there.

The host persists entries, reports durability, saves the view (Action::SaveView) before sending anything in it, and carries messages. Membership is fixed.

Structs

Entry

Membership

The members of one epoch.

Recovered

What a replica found on its disk at start.

Replica

Timing

Failure detection, in milliseconds of each member’s monotonic clock.

Enums

Action

Msg

Status

Constants

MAX_CLOCK_DRIFT_PPM

The clock-rate assumption behind read leases: every member’s clock (the now the host passes in) advances at a rate within this many parts per million of real time, 1 %. Message delays and scheduling pauses are unbounded; only rates are assumed. A clock that stops while time passes (a suspended host whose clock does not count the suspension) breaks it.

MAX_GROUP

The most members a configuration may have.

MAX_MEMBERS

Member IDs are below this (the host keeps one bit per member).

Functions

decode_entry

decode_msg

decode_reconfig

encode_entry

encode_msg

encode_reconfig

epoch_of

A view carries its epoch (the configuration it belongs to) in its high 32 bits, so views of different configurations never coincide and the order of views is the order of epochs, then of views within one.

first_view

is_reconfig

Whether an entry body is a reconfiguration. 0xF5 0x00 starts neither a segment-group batch (a canonical varint), a log batch (0xF3 0x00) nor a permit command (0).

Type Aliases

Op

ReplicaId