Failover & Hot Standby

The idea is old (Schneider's 1990 tutorial is the classic statement) and your engine already satisfies its precondition. A deterministic state machine fed the same commands in the same order ends in the same state. You made the engine deterministic in week 9 and proved it with state hashes. So the primary doesn't need to ship its book to the standby. It ships the sequenced input stream, the same frames it journals, and the standby feeds them through its own copy of the engine.

Why inputs and not the alternatives?

• Not state. The book changes on every command; shipping diffs of it is more data, more code, and a second serialization of state that can drift from the first.
• Not outputs. Executions and market data are derived; replaying them doesn't rebuild the engine's internal state (queue positions, id generators, risk exposure).
• Inputs are small (tens of bytes per order), already sequenced and checksummed, and already journaled. The standby re-derives every output itself. Periodically comparing the two sides' state hashes at the same sequence number is a free detector for non-determinism bugs, the kind that would otherwise surface only after a failover.

The data path: the primary's sequencer assigns seq, appends to its journal, and sends the frame to the standby. The standby applies it and acknowledges the highest contiguous sequence number it holds. Nothing waits per command: the primary keeps matching while frames stream.

The subtle part is what leaves the building. Suppose the primary matches order N, publishes the trade on market data and acks the client, then dies before the standby received N. The standby takes over without N. The public saw a trade that, as far as the new primary is concerned, never happened, and a client holds an execution report for a fill that doesn't exist. The fix is output gating: every externally visible effect of command N (acks, execution reports, market data) is held until the standby has acknowledged N (plus whatever your week 18 fsync policy requires). The primary computes ahead, but the outside world only ever sees what both machines have.

/// The highest sequence number whose outputs may be released to clients
/// and to market data.
fn released_seq(&self) -> Seq {
    self.applied_seq                // the primary has computed the outputs
        .min(self.standby_ack)      // the standby has the input
        .min(self.durable_seq)      // and the week 18 policy is satisfied
}

The cost is one network round trip on the ack path, roughly 10–50 µs over a kernel TCP stack within a rack and a few microseconds with kernel bypass (week 33). Pipelining hides it from throughput, but it is in every order's latency, and it is why exchanges put the standby a rack, not a city, away. (Disaster recovery to another data center is usually asynchronous and accepts a small loss window. That is a different product decision.)

Heartbeats tell you that a node has gone silent. They can't tell you that it is dead. Silence looks the same whether the node crashed, the network dropped, or the process is stuck in a 3-second page-fault storm. So leadership must not rest on "I haven't heard from the primary, so I'll take over". It rests on a lease: a time-limited right to lead, granted by an arbiter that only ever has one live grant outstanding.

Three details make leases correct:

1. Time the lease from when you sent the request. The arbiter starts the lease clock no earlier than when it received the request, which is after you sent it. Measuring from your send time therefore makes your view of the deadline earlier than the arbiter's, which is the safe direction. Measuring from when the reply arrived would make it later.
2. Subtract a drift margin. Your clock and the arbiter's run at slightly different rates. Ordinary crystal oscillators are specified to tens of parts per million; 100 ppm over a 1-second lease is 100 µs. Stop leading at sent_at + duration − margin.
3. Monotonic clocks only. Leases are durations. A wall clock can be stepped by NTP or an operator by seconds in either direction (week 21); a lease computed from SystemTime can silently last forever or not at all.

Even a perfect lease check isn't sufficient, because checking and acting are not atomic. A leader checks its lease (valid), then the process stalls: a long page fault, a SIGSTOP, a VM live migration, a stuck fsync. By the time it resumes and writes, the lease has expired, a new leader exists, and the old one has no idea. The defense is a fencing token: every grant carries an epoch that increases with each new holder, every write carries the writer's epoch, and the protected resource remembers the highest epoch it has seen and refuses anything older. The stale leader's write is rejected by the resource, not by the leader's own (stale) judgement.

// Leadership = lease + fencing token. All times are nanoseconds on a
// MONOTONIC clock, passed in by the caller; nothing here reads a clock.

pub type NodeId = u32;

/// The arbiter (a witness process or a quorum) grants time-bounded leases.
/// A lease is live while `now < expires_at`.
pub struct LeaseArbiter {
    duration: u64,
    holder: Option<NodeId>,
    /// Fencing token of the latest grant. Starts at 0; the first grant is 1.
    epoch: u64,
    expires_at: u64,
}

impl LeaseArbiter {
    pub fn new(duration: u64) -> Self {
        LeaseArbiter { duration, holder: None, epoch: 0, expires_at: 0 }
    }

    /// If nobody holds a live lease: grant it to `node` with epoch + 1.
    /// If `node` already holds the live lease: extend it, same epoch.
    /// If another node holds a live lease: None.
    pub fn acquire(&mut self, node: NodeId, now: u64) -> Option<u64> {
        let _ = (node, now);
        todo!()
    }

    /// Extend the live lease to now + duration. Only the current holder,
    /// presenting the current epoch, strictly before expiry.
    pub fn renew(&mut self, node: NodeId, epoch: u64, now: u64) -> bool {
        let _ = (node, epoch, now);
        todo!()
    }
}

/// The holder's own view of its lease. `sent_at` is the holder's local
/// monotonic time when it SENT the request that produced this grant.
pub struct LeaseView {
    pub epoch: u64,
    pub sent_at: u64,
    pub duration: u64,
}

/// May the holder act as leader at `local_now`? Only strictly before
/// sent_at + duration - margin (`margin` covers clock-rate drift between
/// holder and arbiter). Must not underflow if margin > duration.
pub fn may_lead(view: &LeaseView, local_now: u64, margin: u64) -> bool {
    let _ = (view, local_now, margin);
    todo!()
}

#[derive(Debug, PartialEq, Eq)]
pub struct Stale {
    pub epoch: u64,
    pub highest: u64,
}

/// The protected resource (sequencer / journal). It remembers the highest
/// epoch it has ever accepted and refuses writes from older epochs.
pub struct FencedJournal {
    highest_epoch: u64,
    pub entries: Vec<(u64, u64)>, // (epoch, command)
}

impl FencedJournal {
    pub fn new() -> Self {
        FencedJournal { highest_epoch: 0, entries: Vec::new() }
    }

    pub fn append(&mut self, epoch: u64, cmd: u64) -> Result<(), Stale> {
        let _ = (epoch, cmd);
        todo!()
    }
}

In this exchange, what exactly is the protected resource? The standby. Every replication frame carries the primary's epoch, and on promotion the standby takes a new, higher epoch and refuses frames from older ones. Now combine that with Day 1's output gating. A deposed primary that is still running can match orders against its stale book, but it can never release their outputs, because releasing requires an ack from a standby that no longer accepts its frames. Fencing at the standby plus gated outputs means split brain can happen inside the old primary's memory without ever becoming visible to the outside world. (The repo's in-process version gets the fence without epochs: promoting consumes the standby and drops its end of the link, so a deposed primary's late frames reach nothing. The capstone has the details.)

Pause the primary for longer than its lease and step through the failover; then switch off fencing to see the deposed primary's stale frame reach clients, and switch off output gating and crash it to see an acknowledged order vanish.

With exactly two machines, a partition between them is undecidable. The primary sees a silent standby, the standby sees a silent primary, and neither can tell "the other one died" from "the link between us died". Asymmetric partitions are worse: the primary still reaches its clients but not the standby. Any rule that lets either side act unilaterally on silence will, eventually, produce two leaders.

There are three standard ways out:

• A third party decides. A lightweight arbiter (witness) on a third machine grants the lease. Whoever can reach the arbiter may lead, and the arbiter grants only one lease at a time. This is the design the drill models. The repo's in-process capstone uses a two-node variant: the standby itself grants the primary's lease and promotes only after it has expired. That never yields two leaders, but a dead standby also stops the primary, which is what a witness avoids.
• A quorum decides. Three or five full replicas run a consensus protocol (Raft, Paxos). A leader needs a majority, and two majorities always overlap. Raft's terms are exactly your epochs. Real Logic's Aeron Cluster packages Raft for low-latency state machines of precisely this shape.
• The loser is forcibly stopped. Classic HA clusters power-cycle the other node before taking over (STONITH: "shoot the other node in the head") through a management controller. It is crude and effective, and it still needs a tie-breaker to decide who shoots.

Whichever you choose, write down the policy for ambiguity: if the standby can't reach the arbiter, or the arbiter is down, nobody leads and the market halts. Exchanges do halt for technical reasons (the NYSE suspended trading for several hours in July 2015 after a problem with a software release). It is survivable, and it is the correct outcome when the alternative is guessing.

TCP gives you ordered, deduplicated bytes within one connection. Replication outlives connections: after a network blip the primary reconnects and resends from the last sequence number it knows the standby acknowledged, and some of those frames the standby already has. If you replicate over UDP or multicast (Aeron, or a multicast bus shared with other consumers), you also get reordering and loss. In every case the standby must apply by sequence number, not by arrival:

• seq ≤ applied is a duplicate. Ignore it.
• seq == applied + 1 gets applied, then anything buffered that is now contiguous gets drained.
• seq > applied + 1 is ahead of a gap. Buffer it and ask the primary to retransmit the missing range (a NAK), which it serves from its journal.
• Too much buffered means the standby has fallen too far behind to catch up by retransmission. It rebuilds from a snapshot (week 18) and resumes the stream from the snapshot's sequence number.

Acknowledge the highest contiguous sequence number, never the highest received. The primary uses that ack to release client-visible outputs, so it must mean "everything up to here is safe on the standby".

use std::collections::BTreeMap;

/// The standby side of primary → standby replication. Messages carry the
/// primary's sequence number; the network may duplicate, reorder or drop
/// them. The standby must apply every seq exactly once, in order.
pub struct Standby {
    /// Highest contiguous seq applied so far (0 = nothing yet).
    applied: u64,
    /// Messages that arrived ahead of a gap: seq → payload.
    pending: BTreeMap<u64, u64>,
    max_pending: usize,
    /// Payloads in apply order (stands in for feeding the engine).
    pub log: Vec<u64>,
}

/// The standby fell too far behind to buffer: it must reload a snapshot
/// (week 18) and resume from the snapshot's sequence number.
#[derive(Debug, PartialEq, Eq)]
pub struct NeedSnapshot;

impl Standby {
    pub fn new(max_pending: usize) -> Self {
        Standby { applied: 0, pending: BTreeMap::new(), max_pending, log: Vec::new() }
    }

    fn apply(&mut self, seq: u64, payload: u64) {
        debug_assert_eq!(seq, self.applied + 1);
        self.log.push(payload);
        self.applied = seq;
    }

    /// Process one replicated message.
    ///   seq ≤ applied            → duplicate, ignore
    ///   seq == applied + 1       → apply it, then drain contiguous pending
    ///   seq > applied + 1        → buffer it (a duplicate of a buffered seq
    ///                              is ignored); if `pending` is already
    ///                              full, return Err(NeedSnapshot) and
    ///                              change nothing
    /// Afterwards, if anything is still pending, return the first gap as an
    /// inclusive retransmit request Some((applied + 1, first_pending - 1)).
    pub fn on_message(&mut self, seq: u64, payload: u64) -> Result<Option<(u64, u64)>, NeedSnapshot> {
        let _ = (seq, payload);
        todo!()
    }

    /// What the standby acknowledges to the primary: everything ≤ this seq
    /// is applied here and survives a primary crash.
    pub fn ack(&self) -> u64 {
        todo!()
    }
}

A failover in your design runs in a fixed order, and each step has a duration you should be able to state:

1. Detection. The primary stops renewing its lease. Detection time is about the lease duration. Shorter leases mean faster failover but more false ones: a brief network blip or a long stall on the primary then costs a failover. Venues land anywhere from sub-second automatic failover to deliberately operator-confirmed promotion. Pick a number and justify it.
2. Expiry, then acquisition. The standby may acquire the lease only after the arbiter considers the old one expired. It receives epoch + 1.
3. Drain. The standby applies everything contiguous it has received. Anything the old primary sequenced but never replicated is gone, and by output gating none of it was ever visible to clients.
4. Promote. The new primary starts sequencing at applied + 1 under the new epoch, starts the gateway and the market-data publisher (continuing the market-data sequence, not restarting it), and starts rebuilding a new standby from a snapshot.
5. Clients reconnect. FIX sessions resume with sequence-number recovery (week 14). Orders a client sent but never saw acknowledged are unknown to that client. It must either query their status or resend them with the same client order id, and the exchange must deduplicate on (session, ClOrdID). That deduplication table is engine state, so it must be replicated and snapshotted too.
6. Market data consumers see a sequence gap or a session change and resynchronize from a snapshot (week 10).

Then practice. A failover path that only runs during real incidents will have rotted by the time you need it. Run failovers in your test environment on every build, and on a schedule in production outside trading hours.

Build the replication layer below, then run the in-process failover test in a loop with different seeds and crash points. A failover bug that shows up once in a thousand runs in CI shows up eventually in production.