Skip to main content

Crate quepaxa

Crate quepaxa 

Source
Expand description

QuePaxa consensus for state machine replication: a sans-IO, no_std replicated log, and an alternative to Raft and Multi-Paxos that never stalls waiting for an election timeout.

A cluster of replicas agrees on one ordered log of opaque entries, tolerating the crash (and recovery) of any minority. QuePaxa’s distinguishing property is that liveness never depends on timeouts: a leader gives a one-round-trip fast path, but when it is slow, partitioned or gone, any replica can drive any slot with randomized priorities and the log keeps moving — no election, no stall waiting for a timeout to fire.

§Sans-IO

A Replica never touches the network, a disk or a clock, and owns no threads. You feed it events and carry out the Actions it returns: persist these records, send these messages, apply this slot. That makes the same code run under Tokio, a custom event loop, a deterministic simulator or a C program (see the quepaxa-ffi crate), and it is why the crate is no_std (with alloc).

§Quick start

A single-member cluster commits on its own:

use bytes::Bytes;
use quepaxa::{Action, Config, Input, NodeId, Replica, Timestamp};

let cfg = Config::new([7; 16], NodeId(0), vec![NodeId(0)], [42; 32]);
let mut replica = Replica::new(cfg, [], Timestamp(0))?;
let mut disk = Vec::new();
let mut actions = Vec::new();

replica.poll_actions(&mut actions); // after every call, before the next one
replica.propose(Timestamp(0), Bytes::from_static(b"hello"))?;
replica.poll_actions(&mut actions);

let mut committed = Vec::new();
while !actions.is_empty() {
    for action in std::mem::take(&mut actions) {
        match action {
            // Durable first (append + fsync), then `then` messages, then report.
            Action::Persist { id, records, then, .. } => {
                disk.extend(records);
                assert!(then.is_empty());
                replica.handle(Timestamp(0), Input::Persisted(id))?;
            }
            Action::Send(_out) => { /* deliver out.bytes to out.to */ }
            Action::Commit { entries, .. } => committed.extend(entries.into_iter().map(|e| e.payload)),
            _ => {}
        }
    }
    replica.poll_actions(&mut actions);
}
assert_eq!(committed, [Bytes::from_static(b"hello")]);

§Where to go next

The guide explains each part of an embedding in its own chapter: driving the replica, durability and restart, snapshots, linearizable reads, membership and leaders, tuning and how the protocol works. Runnable programs are in the crate’s examples/ directory; examples/kv-tokio in the repository is a complete networked, fsynced key-value store with a load generator.

§Guarantees

  • Agreement and validity: every replica applies the same entries in the same order, and only entries that were proposed; each entry at most once.
  • Crash recovery: replies never leave before the state they report is durable, and a restarted replica never contradicts what it said before — given storage that keeps the promises in guide::durability.
  • Linearizable reads on any replica, without a log slot (quorum reads).
  • Liveness whenever a majority of the members can communicate, without depending on timeouts or a stable leader.

These are checked by unit and property tests, a deterministic simulator with crashes, partitions and membership changes, model checking of the real replica, fuzzing, mutation testing, seeded-bug canaries and an independent TLA+ model (VERIFICATION.md in the repository). The crate assumes crash faults: peers are not malicious, so authenticate the network yourself if it is not trusted.

§Features and platforms

No default features; the model feature is test support and not part of the API. The core builds for any target with alloc, including wasm32-unknown-unknown and thumbv7em-none-eabihf; it is tested on Linux, macOS and Windows. Minimum Rust: 1.89.

The wire format, durable format and API may change in minor versions before 1.0; the changelog lists every such change with upgrade notes.

Modules§

guide
Guides to embedding a replica correctly, one topic per chapter.

Structs§

Config
Configuration of one replica, checked by crate::Replica::new.
Entry
One application payload committed in the log, tagged with where it was proposed.
MemberView
One member of the epoch in force as this replica sees it, from crate::Replica::members.
Metrics
Counters for observability, from crate::Replica::metrics. Counters only grow within one incarnation; gauges (marked) go up and down. guide::tuning says what unusual values indicate.
NodeId
Identity of one replica in the cluster. Ids are chosen by the operator and must be unique; they never change for a replica’s lifetime (its durable state is tied to it).
Outbound
A message to send to one peer.
PersistId
Identifier of a crate::Action::Persist; strictly increasing within one incarnation.
ProposalId
Identifier of a local proposal, returned by crate::Replica::propose (and read_barrier, propose_reconfiguration), unique within one incarnation of a replica. Entries in crate::Action::Commit carry it with their origin and incarnation, which together identify an entry cluster-wide. Treat ids as opaque: reads and logged proposals use separate ranges, so interleaved calls do not return ids in increasing order.
Replica
One replica of a QuePaxa cluster: a recorder and a proposer for every slot of the log, with the decided log, leader schedule and durability bookkeeping around them.
Slot
Position in the replicated log, from 0. Each slot holds one decided batch of entries.
Timestamp
Monotonic time in nanoseconds, supplied by the caller with every call; the epoch is the caller’s choice (process start is typical). Only differences matter, and the replica never lets its clock move backwards, so a slightly stale reading is harmless.

Enums§

Action
Work the caller must carry out, in the order returned.
DropReason
Why a local proposal is no longer tracked.
Error
Why a call was refused. A refused call changes nothing in the replica.
Input
Something that happened outside the replica, fed with crate::Replica::handle.