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
//! 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};
const MILLI: u64 = 1_000_000;
/// Envelope and proposal framing budget on top of the values a message carries.
const MESSAGE_OVERHEAD: u64 = 1024;
/// Static configuration of one replica. Every member must use the same `cluster_id`,
/// `members`, `leader_order` and `max_batch_bytes` (receivers reject values larger than
/// their own limit);
/// `seed` must be fresh CSPRNG output on every start, including restarts.
#[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). 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,
/// 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>,
}
impl Config {
/// A configuration with default limits and timers.
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,
leader_order: Vec::new(),
}
}
/// 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"),
(self.max_batch_bytes > 0, "max_batch_bytes must be positive"),
(
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.
#[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 until restarted.
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,
}
/// 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. After a
/// restart, slots recovered from storage are emitted again.
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 barrier is in the log: after applying every commit up to and including
/// `slot`, application state may serve a linearizable read.
ReadReady {
/// The barrier.
id: ProposalId,
/// The barrier's slot.
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` may shut down once it has applied the slot before `from`.
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>,
},
/// 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.
#[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.
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,
/// Gauge: decided slots held in memory (bounded by compaction).
pub retained_slots: u64,
/// Gauge: recorder registers held in memory.
pub live_registers: u64,
}
/// A caller contract violation or a refused request.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Error {
/// The configuration is invalid.
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,
},
/// Too many outstanding proposals; retry after some commit.
Busy,
/// The payload does not fit in one batch.
PayloadTooLarge,
/// The replica is fenced after a storage failure.
Fenced,
/// Actions from the previous call were not drained with `poll_actions`.
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,
}
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"),
}
}
}
impl core::error::Error for Error {}