mod gate;
mod log;
mod proposing;
mod snapshot;
use alloc::collections::{BTreeMap, VecDeque};
use alloc::vec::Vec;
use bytes::Bytes;
use core::mem;
use self::gate::Gate;
use crate::api::{Action, Config, DropReason, Error, Input, Metrics, Outbound};
use crate::batch::{self, Entry, Item, Kind};
use crate::codec::{Body, Envelope, Message, WireCtx};
use crate::core_state::CoreState;
use crate::dedup::Dedup;
use crate::durable::Record;
use crate::proposal::{Proposal, ValueKey};
use crate::proposer::SlotProposer;
use crate::recorder::Register;
use crate::rng::ChaCha20;
use crate::schedule::Schedule;
use crate::types::{MAX_SLOT, MAX_STEP, NodeId, PersistId, ProposalId, Slot, Timestamp};
#[cfg_attr(feature = "model", derive(Clone, Hash))]
struct Decision {
proposal: Proposal,
durable: bool,
}
#[cfg_attr(feature = "model", derive(Clone, Hash))]
struct Active {
prop: SlotProposer,
batch: u64,
resend_at: Timestamp,
}
#[cfg_attr(feature = "model", derive(Clone, Hash))]
struct LocalBatch {
key: ValueKey,
value: Bytes,
entries: Vec<(NodeId, u64, ProposalId)>,
slot: Option<Slot>,
}
#[cfg_attr(feature = "model", derive(Clone, Hash))]
enum Effect {
ReservationDurable(u64),
DecidedDurable(Slot),
LocalReply(Body),
}
#[cfg_attr(feature = "model", derive(Clone, Hash))]
pub struct Replica {
cfg: Config,
me: NodeId,
wire: WireCtx,
rng: ChaCha20,
incarnation: u64,
now: Timestamp,
fenced: bool,
metrics: Metrics,
gate: Gate<Effect>,
actions: Vec<Action>,
inbox: VecDeque<(NodeId, Body)>,
registers: BTreeMap<Slot, Register>,
log: BTreeMap<Slot, Decision>,
committed: u64,
emitted: u64,
peer_committed: u64,
seen: BTreeMap<Slot, Timestamp>,
catch_up: Option<(NodeId, Timestamp)>,
ahead_peer: Option<NodeId>,
schedule: Schedule,
applied_schedule: Schedule,
dedup: Dedup,
proposers: BTreeMap<Slot, Active>,
batches: BTreeMap<u64, LocalBatch>,
pending: VecDeque<Item>,
hedged: VecDeque<Item>,
forwarded: BTreeMap<ProposalId, (Item, Timestamp)>,
outstanding: BTreeMap<ProposalId, (Timestamp, Kind)>,
commit_latency: Option<u64>,
next_batch: u64,
next_proposal: u64,
next_alloc: u64,
h_floor: u64,
reserved_through: Option<u64>,
reserved_durable: Option<u64>,
floor: u64,
snapshot_state: Option<Bytes>,
snapshot_asked: Option<Timestamp>,
#[cfg(feature = "model")]
decided_steps: BTreeMap<Slot, (Proposal, u32)>,
}
impl Replica {
pub fn new(cfg: Config, durable: impl IntoIterator<Item = Bytes>, now: Timestamp) -> Result<Self, Error> {
cfg.validate()?;
let mut last_incarnation = 0;
let mut registers = BTreeMap::new();
let mut log = BTreeMap::new();
let mut reservation: Option<u64> = None;
let mut snapshot: Option<(CoreState, Bytes)> = None;
for (index, bytes) in durable.into_iter().enumerate() {
match Record::decode(&bytes).map_err(|_| Error::CorruptRecord { index })? {
Record::Incarnation(n) => last_incarnation = last_incarnation.max(n),
Record::Recorder { slot, reg } => {
if reg.step > MAX_STEP || slot.0 > MAX_SLOT {
return Err(Error::CorruptRecord { index });
}
registers.insert(slot, reg);
}
Record::Reservation { through } => reservation = reservation.max(Some(through.0)),
Record::Decided { slot, proposal } => {
log.insert(slot, Decision { proposal, durable: true });
}
Record::Compacted { through, core_state } => {
let state = snapshot::decode_state(through, &core_state, &cfg.members)
.ok_or(Error::CorruptRecord { index })?;
if snapshot.as_ref().is_none_or(|(s, _)| s.next < state.next) {
snapshot = Some((state, core_state));
}
}
}
}
if snapshot.as_ref().is_some_and(|(s, _)| s.leaders != cfg.leaders()) {
return Err(Error::InvalidConfig(
"leader_order differs from the one this replica's durable state was built with",
));
}
let floor = snapshot.as_ref().map_or(0, |(s, _)| s.next);
log = log.split_off(&Slot(floor));
registers = registers.split_off(&Slot(floor));
registers.retain(|slot, _| !log.contains_key(slot));
let wire = WireCtx {
cluster_id: cfg.wire_cluster_id(),
config_epoch: 0,
max_message_bytes: cfg.max_message_bytes,
max_value_bytes: cfg.max_batch_bytes,
};
let mut r = Self {
me: cfg.id,
wire,
rng: ChaCha20::new(cfg.seed),
schedule: snapshot
.as_ref()
.map_or_else(|| Schedule::with_order(cfg.leaders()), |(s, _)| s.schedule.clone()),
applied_schedule: snapshot
.as_ref()
.map_or_else(|| Schedule::with_order(cfg.leaders()), |(s, _)| s.schedule.clone()),
cfg,
incarnation: last_incarnation + 1,
now,
fenced: false,
metrics: Metrics::default(),
gate: Gate::new(Record::Incarnation(last_incarnation + 1).encode()),
actions: Vec::new(),
inbox: VecDeque::new(),
registers,
log,
committed: floor,
emitted: floor,
peer_committed: 0,
seen: BTreeMap::new(),
catch_up: None,
ahead_peer: None,
dedup: snapshot.as_ref().map_or_else(Dedup::default, |(s, _)| s.dedup.clone()),
proposers: BTreeMap::new(),
batches: BTreeMap::new(),
pending: VecDeque::new(),
hedged: VecDeque::new(),
forwarded: BTreeMap::new(),
outstanding: BTreeMap::new(),
commit_latency: None,
next_batch: 0,
next_proposal: 0,
next_alloc: 0,
h_floor: reservation.map_or(0, |r| r + 1),
reserved_through: None,
reserved_durable: None,
floor,
snapshot_state: snapshot.map(|(_, b)| b),
snapshot_asked: None,
#[cfg(feature = "model")]
decided_steps: BTreeMap::new(),
};
r.advance_committed();
let started: Vec<Slot> = r.registers.keys().copied().collect();
for slot in started {
r.seen.entry(slot).or_insert(now);
}
r.emit_commits();
r.flush();
Ok(r)
}
pub fn id(&self) -> NodeId {
self.me
}
pub fn commit_index(&self) -> u64 {
self.committed
}
pub fn metrics(&self) -> &Metrics {
&self.metrics
}
pub fn propose(&mut self, now: Timestamp, payload: Bytes) -> Result<ProposalId, Error> {
self.enqueue(now, payload, Kind::App)
}
pub fn read_barrier(&mut self, now: Timestamp) -> Result<ProposalId, Error> {
self.enqueue(now, Bytes::new(), Kind::Barrier)
}
pub fn propose_reconfiguration(
&mut self,
now: Timestamp,
members: Vec<NodeId>,
leader_order: Vec<NodeId>,
) -> Result<ProposalId, Error> {
let mut by_id = members.clone();
by_id.sort_unstable();
by_id.dedup();
if members.is_empty() || by_id.len() != members.len() || members.len() > crate::schedule::MAX_MEMBERS
{
return Err(Error::InvalidConfig("members must be non-empty and unique"));
}
let order = if leader_order.is_empty() { by_id.clone() } else { leader_order };
let mut sorted = order.clone();
sorted.sort_unstable();
if sorted != by_id {
return Err(Error::InvalidConfig("leader_order must list every member exactly once"));
}
let proposed_here = self.outstanding.values().any(|(_, kind)| *kind == Kind::Reconfigure);
if self.schedule.epoch().1 > self.committed || proposed_here {
return Err(Error::ReconfigurationPending);
}
self.enqueue(now, crate::schedule::encode_order(&order), Kind::Reconfigure)
}
fn enqueue(&mut self, now: Timestamp, payload: Bytes, kind: Kind) -> Result<ProposalId, Error> {
self.begin(now)?;
if self.fenced {
return Err(Error::Fenced);
}
if self.outstanding.len() >= self.cfg.max_outstanding_proposals as usize {
return Err(Error::Busy);
}
let id = ProposalId(self.next_proposal);
let item =
Item { entry: Entry { origin: self.me, incarnation: self.incarnation, id, payload }, kind };
if !batch::fits_alone(&item, self.cfg.max_batch_bytes as usize) {
return Err(Error::PayloadTooLarge);
}
self.next_proposal += 1;
self.outstanding.insert(id, (self.now, kind));
self.pending.push_back(item);
self.pump();
self.flush();
Ok(id)
}
pub fn handle(&mut self, now: Timestamp, input: Input) -> Result<(), Error> {
self.begin(now)?;
if self.fenced {
return Ok(());
}
match input {
Input::Message(bytes) => self.on_message(&bytes),
Input::Persisted(id) => self.on_persisted(id)?,
Input::StorageFailed(_) => self.fence(),
}
self.pump();
self.flush();
Ok(())
}
pub fn handle_timeout(&mut self, now: Timestamp) -> Result<(), Error> {
self.begin(now)?;
if self.fenced {
return Ok(());
}
self.fire_timers();
self.pump();
self.flush();
Ok(())
}
pub fn next_deadline(&self) -> Option<Timestamp> {
if self.fenced { None } else { self.earliest_timer() }
}
pub fn poll_actions(&mut self, out: &mut Vec<Action>) {
out.append(&mut self.actions);
}
fn begin(&mut self, now: Timestamp) -> Result<(), Error> {
if !self.actions.is_empty() {
return Err(Error::NotDrained);
}
self.now = self.now.max(now);
Ok(())
}
fn window(&self) -> u64 {
u64::from(self.cfg.max_in_flight_slots)
}
fn after_durable(&mut self, e: Effect) {
if let Some(e) = self.gate.after_durable(e) {
self.apply(e);
}
}
fn flush(&mut self) {
self.metrics.retained_slots = self.log.len() as u64;
self.metrics.live_registers = self.registers.len() as u64;
self.gate.flush(&mut self.actions);
}
fn on_persisted(&mut self, id: PersistId) -> Result<(), Error> {
for e in self.gate.persisted(id, &mut self.actions)? {
self.apply(e);
}
Ok(())
}
fn apply(&mut self, e: Effect) {
match e {
Effect::ReservationDurable(t) => self.reserved_durable = self.reserved_durable.max(Some(t)),
Effect::DecidedDurable(slot) => {
if let Some(d) = self.log.get_mut(&slot) {
d.durable = true;
}
self.registers.remove(&slot);
self.emit_commits();
}
Effect::LocalReply(body) => self.inbox.push_back((self.me, body)),
}
}
fn fence(&mut self) {
self.fenced = true;
for id in mem::take(&mut self.outstanding).into_keys() {
self.actions.push(Action::Dropped { id, reason: DropReason::Fenced });
}
self.proposers.clear();
self.pending.clear();
self.hedged.clear();
self.forwarded.clear();
self.batches.clear();
self.inbox.clear();
self.gate.fence();
}
fn encode(&self, to: NodeId, body: Body) -> Outbound {
let env = Envelope {
cluster_id: self.wire.cluster_id,
config_epoch: 0,
from: self.me,
to,
commit_index: self.committed,
};
Outbound { to, bytes: Message { env, body }.encode() }
}
fn send(&mut self, to: NodeId, body: Body) {
if to == self.me {
self.inbox.push_back((to, body));
return;
}
let out = self.encode(to, body);
self.gate.send(out, &mut self.actions);
}
fn send_gated(&mut self, to: NodeId, body: Body) {
let out = self.encode(to, body);
self.gate.send_after_durable(out, &mut self.actions);
}
fn on_message(&mut self, bytes: &Bytes) {
let Ok(msg) = Message::decode(bytes, &self.wire) else {
self.metrics.messages_rejected += 1;
return;
};
let from = msg.env.from;
let known = self.cfg.members.contains(&from) || self.schedule.knows(from);
if msg.env.to != self.me || from == self.me || !known {
self.metrics.messages_rejected += 1;
return;
}
if msg.env.commit_index > self.peer_committed {
self.peer_committed = msg.env.commit_index;
self.ahead_peer = Some(from);
}
if self.peer_committed > self.committed {
self.seen.entry(Slot(self.committed)).or_insert(self.now);
}
if msg.env.commit_index > self.committed + 1 && self.catch_up_due() {
self.request_catch_up(from);
}
self.inbox.push_back((from, msg.body));
}
fn catch_up_due(&self) -> bool {
self.catch_up.is_none_or(|(_, t)| t.after(self.cfg.retransmit_interval) <= self.now)
}
fn request_catch_up(&mut self, peer: NodeId) {
self.catch_up = Some((peer, self.now));
self.send(peer, Body::CatchUp { from: Slot(self.committed) });
}
fn pump(&mut self) {
loop {
while let Some((from, body)) = self.inbox.pop_front() {
match body {
Body::RecordRequest { slot, step, proposal } => {
self.on_request(from, slot, step, proposal)
}
Body::RecordReply { slot, req_step, step, first, prev_agg } => {
self.on_reply(from, slot, req_step, step, first, prev_agg)
}
Body::Decided { slot, proposal } => self.learn(slot, proposal, false),
Body::CatchUp { from: start } => self.on_catch_up(from, start),
Body::Entries { first, proposals } => {
for (i, p) in proposals.into_iter().enumerate() {
let Some(slot) = first.0.checked_add(i as u64) else { break };
self.learn(Slot(slot), p, false);
}
if self.catch_up.is_some_and(|(peer, _)| peer == from) {
self.catch_up = None;
if self.peer_committed > self.committed + 1 {
self.request_catch_up(from);
}
}
}
Body::Forward { batch } => self.on_forward(&batch),
Body::Compacted { through } => self.on_compacted(from, through),
}
}
self.drive();
if self.inbox.is_empty() {
break;
}
}
}
}
#[cfg(feature = "model")]
impl Replica {
#[doc(hidden)]
pub fn inspect(&self) -> crate::inspect::Inspection {
crate::inspect::Inspection {
registers: self.registers.iter().map(|(s, r)| (s.0, r.into())).collect(),
decided_here: self.decided_steps.iter().map(|(s, (p, step))| (s.0, p.into(), *step)).collect(),
decided: self.log.iter().map(|(s, d)| (s.0, (&d.proposal).into())).collect(),
local_batches: self.batches.len(),
}
}
#[doc(hidden)]
pub fn fingerprint(&self) -> u64 {
struct Fnv(u64);
impl core::hash::Hasher for Fnv {
fn finish(&self) -> u64 {
self.0
}
fn write(&mut self, bytes: &[u8]) {
for &b in bytes {
self.0 = (self.0 ^ u64::from(b)).wrapping_mul(0x0100_0000_01b3);
}
}
}
let mut h = Fnv(0xcbf2_9ce4_8422_2325);
core::hash::Hash::hash(self, &mut h);
core::hash::Hasher::finish(&h)
}
}
#[cfg(test)]
mod tests;