quepaxa
An open-source Rust implementation of QuePaxa (SOSP'23), a consensus algorithm for state machine replication whose liveness never depends on timeouts. Any replica can drive any slot; a leader is only a fast path (one round trip), and hedged, randomized proposers keep the replicated log moving when the leader is slow, partitioned or gone. QuePaxa is the algorithm behind Cloudflare Research's Meerkat global consensus service.
- No timeout tuning for availability. A slow or dead leader costs latency, never a stall; there are no elections.
- Sans-IO and
no_std. The core never touches the network, a disk or a clock: you feed it events and carry out the actions it returns, on any runtime (Tokio, threads, an event loop, a simulator). - Embeddable anywhere. A stable C ABI with prebuilt libraries for Linux, macOS, Windows, Android and iOS.
- Verified continuously. Deterministic simulation, model checking, a TLA+ model, fuzzing, Miri and mutation testing, all in CI (details).
Install
On no_std targets, use cargo add bytes --no-default-features for bytes.
From C, C++, Go, Swift or another FFI language: download the prebuilt library for your platform from the releases and read docs.rs/quepaxa-ffi.
Quick start
A single-member cluster commits on its own. With more members, messages go to peers
(Action::Send, and each Action::Persist's then once its records are durable) and
their replies come back through Replica::handle; the loop is the same.
use Bytes;
use ;
Next: three replicas exchanging messages in
examples/cluster.rs, and the
guide for everything a production embedding needs.
QuePaxa compared to Raft and Multi-Paxos
All three replicate a log across n replicas and stay available while a majority is up
(2f + 1 replicas tolerate f crashes). In Raft and Multi-Paxos, progress depends on one
leader: when it crashes, the cluster waits for an election timeout; when it is slow but
still answers heartbeats, it stays leader and every write pays for it. Timeouts short
enough to recover quickly cause spurious elections on a jittery wide-area network, so they
are a tuning problem with no right answer.
QuePaxa keeps the leader's one-round-trip fast path in the common case, but never waits for it: if a slot is not decided in time, other replicas hedge and propose too, and the protocol still decides exactly one value. A timeout set too short costs extra messages, not availability; a slow leader costs latency, not a stall. The price is a more involved protocol (without the fast path, a round takes up to four phases, and a decision usually three) and slightly more state per slot.
Documentation
The API reference on docs.rs/quepaxa comes with a guide (also
readable in crates/quepaxa/docs):
| Chapter | What it covers |
|---|---|
| Driving the replica | The event loop, every action, persist-before-send, timers, threads |
| Durability and restart | What storage must promise, recovery, what breaks safety |
| Snapshots | Compacting the log, installing a peer's snapshot |
| Linearizable reads | Read barriers, and reading on any replica |
| Membership and leaders | Adding and removing members, choosing the leader order |
| Tuning | Every Config field, WAN settings, metrics |
| How the protocol works | QuePaxa in a few pages, and a glossary |
Examples
| Example | Shows |
|---|---|
cargo run -p quepaxa --example cluster |
Three replicas, writes and a linearizable read |
cargo run -p quepaxa --example restart |
Crash recovery, compaction, catching up from a snapshot |
cargo run -p quepaxa --example membership |
Replacing a member and the leader |
examples/kv-tokio |
A networked key-value store: TCP, fsync'd storage, snapshots, membership changes, a load generator |
crates/quepaxa-ffi/examples/smoke.c |
The same loop in C |
The first three share a small in-memory driver,
crates/quepaxa/examples/common, written to be read.
Guarantees and verification
- Agreement and validity: every replica applies the same entries in the same order, only entries that were proposed, each at most once.
- Crash recovery: replies never leave before the state they report is durable (ADR 0002); a restarted replica never contradicts what it said before.
- Linearizable reads through read barriers.
- Membership changes through the log (
Replica::propose_reconfiguration), effective 64 slots after they are decided, and a configurable leader order (Config::leader_order) to put the leader where a majority is closest (design).
Checked by unit and property tests; a deterministic simulator (loss, duplication, reordering, partitions, crash-restart with lost and torn writes, snapshots, membership changes) with agreement and linearizability oracles; delay-bounded model checking of the real replica; an independent TLA+ model; fuzzing; Miri; mutation testing with a ratchet; and seeded-bug canaries that must keep failing. See VERIFICATION.md.
Performance
examples/kv-tokio, three replicas on one VM over loopback, every write fsynced to a
virtual disk before it is acknowledged, half writes and half linearizable reads: 250,000
operations/s with p50 7.2 ms and p99 14 ms; at 5,000 operations/s, p50 5.9 ms. Latency is a few fsyncs and barely depends on load. Setup, in-memory numbers and
simulated WAN placements: docs/benchmarks.md.
Platforms
Tested natively on Linux, macOS and Windows (x86_64 and aarch64); the C ABI is tested on
Android (emulator) and iOS (simulator); the core builds for wasm32-unknown-unknown and
thumbv7em-none-eabihf (no_std with alloc). MSRV: Rust 1.89.
Status
Pre-1.0. The wire format, durable format and C ABI may change between minor versions until 1.0; the changelog has upgrade notes. Not supported: Byzantine faults, witnesses (vote-only members), automatic latency-based leader tuning. Design record: spec, decisions, ADRs.
License
Licensed under either of Apache License, Version 2.0 or MIT license at your option.