quepaxa 0.7.0

QuePaxa consensus for state machine replication: a sans-IO, no_std replicated log that, unlike Raft or Multi-Paxos, never stalls on election timeouts
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
//! Public configuration, inputs, actions and errors of a [`crate::Replica`].

use alloc::vec::Vec;
use bytes::Bytes;
use core::fmt;

use crate::batch::Entry;
use crate::types::{NodeId, PersistId, ProposalId, Slot, Timestamp};

const MILLI: u64 = 1_000_000;

/// Envelope and proposal framing budget on top of the values a message carries.
const MESSAGE_OVERHEAD: u64 = 1024;

/// Configuration of one replica, checked by [`crate::Replica::new`].
///
/// Every member must use the same `cluster_id`, `members` (the initial membership),
/// `leader_order` and `max_batch_bytes`; `seed` must be fresh CSPRNG output on every start,
/// including restarts. [`Config::new`] fills the limits and timers with defaults for a LAN;
/// [`guide::tuning`](crate::guide::tuning) explains each field and when to change it.
///
/// # Examples
///
/// ```
/// use quepaxa::{Config, NodeId};
///
/// const MILLI: u64 = 1_000_000;
/// let members = vec![NodeId(0), NodeId(1), NodeId(2)];
/// let mut cfg = Config::new(*b"orders-cluster-1", NodeId(1), members, [3; 32]);
/// // A cluster spread over regions with ~150 ms round trips:
/// cfg.retransmit_interval = 400 * MILLI;
/// cfg.hedge_max = 3_000 * MILLI;
/// cfg.leader_order = vec![NodeId(1), NodeId(0), NodeId(2)];
/// ```
#[derive(Clone, Debug)]
#[cfg_attr(feature = "model", derive(Hash))]
#[non_exhaustive]
pub struct Config {
    /// Identifies the cluster; messages from other clusters are dropped.
    pub cluster_id: [u8; 16],
    /// This replica.
    pub id: NodeId,
    /// All replicas, including this one.
    pub members: Vec<NodeId>,
    /// Randomness for proposal priorities. Liveness relies on the network being unable to
    /// predict it, so never reuse a seed across starts.
    pub seed: [u8; 32],
    /// Upper bound on the encoded entries of one batch (one slot), at least 64. Cluster-wide:
    /// every member must use the same value.
    pub max_batch_bytes: u32,
    /// Upper bound on one encoded network message; larger inputs are dropped unread. Must be
    /// at least `2 * max_batch_bytes + 1024` (a reply can carry two full values).
    pub max_message_bytes: u32,
    /// How many slots this replica may drive concurrently.
    pub max_in_flight_slots: u32,
    /// How many local proposals may be pending before [`Error::Busy`].
    pub max_outstanding_proposals: u32,
    /// How often an unanswered record request is re-sent, in nanoseconds. The default
    /// (50 ms) suits a LAN; across regions set it above the round trip to the farthest
    /// member of a majority, or every request is sent several times.
    pub retransmit_interval: u64,
    /// Lower bound of the adaptive hedge delay, in nanoseconds.
    pub hedge_min: u64,
    /// Upper bound of the adaptive hedge delay, in nanoseconds; a quarter of it is used
    /// until a commit latency has been observed. Keep it above the slowest client commit
    /// path (through the leader) or followers hedge routinely, which costs throughput.
    pub hedge_max: u64,
    /// Whether a follower stops waiting for a leader that has said nothing at all since it
    /// forwarded entries, after about one commit latency instead of the hedge delay: it
    /// hands its entries to the next member of the leader order and takes over the
    /// leader's unfinished slots. Across regions this cuts recovery from a lost leader
    /// region from several seconds to about one commit latency. A leader acknowledges
    /// forwards at once, before any write (at most once per eighth of
    /// `retransmit_interval` per follower), so one stalled on its disk is not taken for
    /// silent. On by default; off, a follower waits the hedge delay as it always did.
    pub silent_leader_takeover: bool,
    /// Preferred leaders, first to last: every member once. Empty (the default) means by
    /// id. Put the member with the fastest path to a majority first: on a WAN the
    /// placement alone can change client latency about 2x. The leader moves down this
    /// order only when it stops getting its values decided.
    ///
    /// Members with different orders would disagree on who leads, so the order is folded
    /// into the cluster identity on the wire: such members ignore each other. It is fixed
    /// for the life of the cluster's state: a replica refuses to start from, or install, a
    /// snapshot built under another order.
    pub leader_order: Vec<NodeId>,
    /// Whether this member takes part in leader placement: while writes flow it probes
    /// every member once a second for round trips and counts where writes come from, and
    /// while it leads it moves the leader to the member that gives writers the lowest
    /// commit latency, by an ordinary leader-order change. Members with it off neither
    /// probe nor answer, so enable it on every member. Off by default. See
    /// [`guide::tuning`](crate::guide::tuning).
    pub placement: bool,
    /// How long, in nanoseconds, a member must keep a gain of at least 20% over the leader
    /// before placement moves the leader to it. Default 3 minutes.
    pub placement_sustain: u64,
    /// After any change of the leader order, how long, in nanoseconds, placement leaves it
    /// alone. Default 10 minutes.
    pub placement_hold: u64,
}

impl Config {
    /// A configuration with default limits and timers (see the table in
    /// [`guide::tuning`](crate::guide::tuning)): 1 MiB batches, 16 MiB messages, 8 slots in
    /// flight, 4096 outstanding proposals, 50 ms retransmission, hedging between 1 ms and
    /// 1 s, leaders by id.
    pub fn new(cluster_id: [u8; 16], id: NodeId, members: Vec<NodeId>, seed: [u8; 32]) -> Self {
        Self {
            cluster_id,
            id,
            members,
            seed,
            max_batch_bytes: 1 << 20,
            max_message_bytes: 16 << 20,
            max_in_flight_slots: 8,
            max_outstanding_proposals: 4096,
            retransmit_interval: 50 * MILLI,
            hedge_min: MILLI,
            hedge_max: 1000 * MILLI,
            silent_leader_takeover: true,
            leader_order: Vec::new(),
            placement: false,
            placement_sustain: 180_000 * MILLI,
            placement_hold: 600_000 * MILLI,
        }
    }

    /// The leader order in effect: `leader_order`, or the members by id.
    pub(crate) fn leaders(&self) -> Vec<NodeId> {
        if self.leader_order.is_empty() {
            let mut order = self.members.clone();
            order.sort_unstable();
            order
        } else {
            self.leader_order.clone()
        }
    }

    /// `cluster_id` as sent on the wire: a custom leader order is mixed in, so members
    /// configured with different orders never exchange messages.
    pub(crate) fn wire_cluster_id(&self) -> [u8; 16] {
        let mut id = self.cluster_id;
        let mut by_id = self.members.clone();
        by_id.sort_unstable();
        if self.leaders() != by_id {
            let fnv = self
                .leader_order
                .iter()
                .flat_map(|n| n.0.to_le_bytes())
                .fold(0xcbf2_9ce4_8422_2325_u64, |h, b| (h ^ u64::from(b)).wrapping_mul(0x0100_0000_01b3));
            for (b, f) in id[8..].iter_mut().zip(fnv.to_le_bytes()) {
                *b ^= f;
            }
        }
        id
    }

    pub(crate) fn validate(&self) -> Result<(), Error> {
        let mut sorted = self.members.clone();
        sorted.sort_unstable();
        sorted.dedup();
        let checks = [
            (!self.members.is_empty(), "members must not be empty"),
            (self.members.len() <= crate::schedule::MAX_MEMBERS, "at most 1024 members"),
            (sorted.len() == self.members.len(), "members must be unique"),
            // Room for at least one entry's framing (an empty barrier entry is 29 bytes).
            (self.max_batch_bytes >= 64, "max_batch_bytes must be at least 64"),
            (
                u64::from(self.max_message_bytes) >= 2 * u64::from(self.max_batch_bytes) + MESSAGE_OVERHEAD,
                "max_message_bytes must hold two full batches plus 1 KiB of framing",
            ),
            (self.max_in_flight_slots > 0, "max_in_flight_slots must be positive"),
            (
                u64::from(self.max_in_flight_slots) <= crate::schedule::LAG,
                "max_in_flight_slots must be at most 64",
            ),
            (
                self.hedge_max > 0 && self.hedge_min <= self.hedge_max,
                "hedge bounds must satisfy 0 <= hedge_min <= hedge_max, hedge_max > 0",
            ),
            (self.max_outstanding_proposals > 0, "max_outstanding_proposals must be positive"),
            (self.retransmit_interval > 0, "retransmit_interval must be positive"),
            (
                self.leader_order.is_empty() || {
                    let mut order = self.leader_order.clone();
                    order.sort_unstable();
                    order == sorted
                },
                "leader_order must list every member exactly once",
            ),
        ];
        match checks.iter().find(|(ok, _)| !ok) {
            Some((_, why)) => Err(Error::InvalidConfig(why)),
            None => Ok(()),
        }
    }
}

/// Something that happened outside the replica, fed with [`crate::Replica::handle`].
#[derive(Clone, Debug)]
#[non_exhaustive]
pub enum Input {
    /// A network message from a peer, exactly as received.
    Message(Bytes),
    /// Every [`Action::Persist`] with an id up to and including `id` is durable.
    Persisted(PersistId),
    /// Persisting `id` failed. The replica fences itself: it reports outstanding proposals
    /// as [`Action::Dropped`], ignores further events and refuses requests with
    /// [`Error::Fenced`]. Restart it from its durable records.
    StorageFailed(PersistId),
}

/// A message to send to one peer.
#[derive(Clone, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
pub struct Outbound {
    /// Destination replica.
    pub to: NodeId,
    /// Encoded message.
    pub bytes: Bytes,
}

/// Why a local proposal is no longer tracked.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
#[non_exhaustive]
pub enum DropReason {
    /// The replica fenced itself after a storage failure. As after a crash, the outcome is
    /// unknown: the proposal may already have reached a quorum and may still commit.
    Fenced,
    /// A membership change was decided but ignored by every replica: another change or a
    /// leader rotation came after the configuration it was computed from. Nothing changed;
    /// propose it again against the members now in force.
    Superseded,
    /// A membership change was decided, but this replica learned it from an installed
    /// snapshot, which does not record whether it was applied or ignored. Check the members
    /// now in force.
    Unresolved,
}

/// Work the caller must carry out, in the order returned.
#[derive(Clone, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
#[non_exhaustive]
pub enum Action {
    /// Durably append `records` after every earlier `Persist`, then send `then`, then
    /// report [`Input::Persisted`]. Never send `then` before `records` are durable.
    Persist {
        /// Completion token to report back.
        id: PersistId,
        /// Opaque records; hand all of them back, in order, to [`crate::Replica::new`] on restart.
        records: Vec<Bytes>,
        /// Messages gated on this write.
        then: Vec<Outbound>,
        /// Replace every previously persisted record with `records` (atomically, e.g.
        /// write-new-then-rename) instead of appending. Emitted after compaction.
        replace: bool,
    },
    /// Send now; no durability required.
    Send(Outbound),
    /// Apply this slot's entries; slots arrive in strict order without gaps, as soon as
    /// they are decided (the local record of the decision may still be in flight). After a
    /// restart, slots already returned are emitted again: recovered from storage, or
    /// learned again from peers.
    Commit {
        /// The slot.
        slot: Slot,
        /// Entries decided in it, possibly none.
        entries: Vec<Entry>,
    },
    /// A local proposal was committed.
    Committed {
        /// The proposal.
        id: ProposalId,
        /// Where it was committed; if an installed snapshot resolved it, that snapshot's
        /// `through` (the proposal is in the log at or before it).
        slot: Slot,
    },
    /// A read is ready: after applying every commit up to and including `slot`, application
    /// state may serve a linearizable read. Emitted after the `Commit` of `slot`.
    ReadReady {
        /// The read ([`crate::Replica::read_barrier`]).
        id: ProposalId,
        /// The last slot the read must reflect.
        slot: Slot,
    },
    /// Slots up to `through` were compacted away at `peer`: fetch that peer's
    /// application snapshot and pass it to [`crate::Replica::install_snapshot`].
    SnapshotNeeded {
        /// A replica that has the snapshot.
        peer: NodeId,
        /// The last slot it covers (at least).
        through: Slot,
    },
    /// A membership change was applied (in the log order of `Commit`): from slot `from`,
    /// `members` (preferred leaders first) are the replicas and majorities are theirs.
    /// A replica not in `members` keeps running until it reports [`Action::Retired`].
    Reconfigured {
        /// The new epoch (the configured members are epoch 0).
        epoch: u64,
        /// First slot of the epoch.
        from: Slot,
        /// The members, preferred leaders first.
        members: Vec<NodeId>,
    },
    /// This replica is not a member of `epoch`, a majority of that epoch's members
    /// durably know every slot before it, and a barrier entry of its own committed with no
    /// later change adding it back: the cluster no longer needs this replica, which may shut
    /// down. Reported once per start. A change decided after that barrier can still add it
    /// back; the operator who proposes one keeps the replica running. See
    /// [`guide::membership`](crate::guide::membership).
    Retired {
        /// The epoch this replica is not a member of.
        epoch: u64,
    },
    /// A local proposal will not be reported again (see [`DropReason`] for whether it may
    /// still commit).
    Dropped {
        /// The proposal.
        id: ProposalId,
        /// Why.
        reason: DropReason,
    },
}

/// Counters for observability, from [`crate::Replica::metrics`]. Counters only grow
/// within one incarnation; gauges (marked) go up and down.
/// [`guide::tuning`](crate::guide::tuning) says what unusual values indicate.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
#[non_exhaustive]
pub struct Metrics {
    /// Network messages that failed to decode or came from a non-member.
    pub messages_rejected: u64,
    /// Record requests re-sent after `retransmit_interval`.
    pub retransmits: u64,
    /// Bulk catch-up requests re-sent after `retransmit_interval`.
    pub catch_up_retries: u64,
    /// Slots this replica learned as decided.
    pub slots_decided: u64,
    /// Decisions this replica's proposers reached on the leader fast path.
    pub fast_path_decisions: u64,
    /// Decided batches whose entries could not be decoded (committed as empty). Always 0
    /// unless replicas run incompatible versions.
    pub corrupt_batches: u64,
    /// Batches of entries forwarded to the leader.
    pub forwarded: u64,
    /// Own entries proposed directly after the leader did not commit them in time.
    pub hedged: u64,
    /// Times this replica stepped aside because a write waited too long on its disk.
    pub stepped_aside: u64,
    /// Gauge: decided slots held in memory (bounded by compaction).
    pub retained_slots: u64,
    /// Gauge: recorder registers held in memory.
    pub live_registers: u64,
    /// Times this replica suspected the member it hands entries to of being silent.
    pub suspicions: u64,
    /// Leader-order changes leader placement proposed from this replica.
    pub placement_moves: u64,
    /// Gauge: the membership epoch in force at the applied prefix (0: the configured members).
    pub epoch: u64,
    /// Gauge: this replica's position in the leader order in force at the applied prefix (0:
    /// it leads); the number of members if it is not one.
    pub leader_position: u64,
}

/// One member of the epoch in force as this replica sees it, from
/// [`crate::Replica::members`].
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct MemberView {
    /// The member.
    pub id: NodeId,
    /// Smoothed round trip from this replica, in nanoseconds, if measured recently (only
    /// with [`Config::placement`]).
    pub round_trip: Option<u64>,
    /// The commit index the member's latest message carried (this replica's own for itself).
    pub committed: Option<u64>,
    /// When a message from the member last arrived.
    pub last_heard: Option<Timestamp>,
}

/// Why a call was refused. A refused call changes nothing in the replica.
///
/// | Kind | Variants | What to do |
/// |---|---|---|
/// | Backpressure | [`Busy`](Error::Busy), [`ReconfigurationPending`](Error::ReconfigurationPending) | Retry later. |
/// | Bad input | [`InvalidConfig`](Error::InvalidConfig), [`PayloadTooLarge`](Error::PayloadTooLarge), [`InvalidCoreState`](Error::InvalidCoreState) | Fix the argument. |
/// | Storage | [`CorruptRecord`](Error::CorruptRecord), [`Fenced`](Error::Fenced) | Repair or restore the data; restart. |
/// | Identity exhaustion | [`RequestIdExhausted`](Error::RequestIdExhausted) | Restart from durable records. |
/// | Driver bug | [`NotDrained`](Error::NotDrained), [`UnknownPersistId`](Error::UnknownPersistId) | Fix the event loop ([`guide::driving`](crate::guide::driving)). |
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Error {
    /// The configuration (or a proposed membership) breaks a documented rule; the message
    /// names it.
    InvalidConfig(&'static str),
    /// A durable record handed to [`crate::Replica::new`] is corrupt; `index` is its position.
    CorruptRecord {
        /// Position in the records passed in.
        index: usize,
    },
    /// [`Config::max_outstanding_proposals`] local proposals are already waiting; retry after
    /// some commit.
    Busy,
    /// The payload alone does not fit in one batch ([`Config::max_batch_bytes`]).
    PayloadTooLarge,
    /// The replica fenced itself after [`Input::StorageFailed`]; restart it.
    Fenced,
    /// Actions from the previous call were not taken with
    /// [`poll_actions`](crate::Replica::poll_actions); this call did nothing.
    NotDrained,
    /// `Persisted` named an id that was never issued or was already reported.
    UnknownPersistId,
    /// The core state passed to `compact` or `install_snapshot` is malformed or does not
    /// match the slot it claims to cover.
    InvalidCoreState,
    /// A membership change is still waiting to take effect; propose the next one after its
    /// [`Action::Reconfigured`] slot is committed.
    ReconfigurationPending,
    /// This incarnation has used all ids for reads or logged requests (2^63 of each).
    /// Restart from durable records to obtain a new incarnation; never reset its storage.
    RequestIdExhausted,
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Error::InvalidConfig(why) => write!(f, "invalid config: {why}"),
            Error::CorruptRecord { index } => write!(f, "durable record {index} is corrupt"),
            Error::Busy => f.write_str("too many outstanding proposals"),
            Error::PayloadTooLarge => f.write_str("payload exceeds max_batch_bytes"),
            Error::Fenced => f.write_str("replica is fenced after a storage failure"),
            Error::NotDrained => f.write_str("poll_actions must drain actions before the next call"),
            Error::UnknownPersistId => f.write_str("unknown persist id"),
            Error::InvalidCoreState => f.write_str("invalid core state"),
            Error::ReconfigurationPending => f.write_str("a membership change has not taken effect yet"),
            Error::RequestIdExhausted => {
                f.write_str("request id space exhausted; restart from durable records")
            }
        }
    }
}

impl core::error::Error for Error {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn the_wire_identity_is_stable_across_versions() {
        let members = alloc::vec![NodeId(0), NodeId(1), NodeId(2)];
        let mut cfg = Config::new([7; 16], NodeId(0), members, [1; 32]);
        assert_eq!(cfg.wire_cluster_id(), [7; 16], "the default order leaves the id as configured");
        cfg.leader_order = alloc::vec![NodeId(2), NodeId(0), NodeId(1)];
        // Replicas of different versions must agree on this mix, so it is pinned.
        let mut expected = [7u8; 16];
        expected[8..].copy_from_slice(&[0x61, 0x1e, 0x70, 0x7b, 0x15, 0x0b, 0xf3, 0x99]);
        assert_eq!(cfg.wire_cluster_id(), expected);
    }
}