Exchange v2: End to End

The shape that falls out of the previous twelve weeks:

clients ──TCP──▶ gateway threads (N)         decode, session, throttle,
                    │                         stateless risk (bands, fat finger)
                    │ bounded MPSC (week 5)
                    ▼
               engine thread                  sequence → stateful risk → journal
                    │                         append → replicate → match
          ┌─────────┴──────────┐
          │ per-session queues │ broadcast ring (week 16)
          ▼                    ▼
   gateway threads        md publisher ──▶ subscribers
   (ack / exec reports)
          └──── both release outputs only up to released_seq ────┘

Three decisions deserve to be made explicitly.

Where risk runs. Week 15's checks split naturally. Stateless checks (price band against a published reference, maximum order size, fat-finger limits, the week 17 throttle) can run on gateway threads, in parallel, and shed bad or excess orders before they cost the engine anything. Stateful checks (projected position including open orders, notional limits, the kill switch) need the exact current state, which the engine thread owns. Running them there, as deterministic logic on sequenced input, keeps them exact, replayable and covered by the journal.

The order of journal and match. The journal records inputs, so a command can be appended (to the journal's buffer and the replication stream) before it's matched. There are two ways to guarantee that nothing is lost. LMAX gates the input: its journaller and replicator run in parallel with each other off one ring buffer, and the business logic processes an event only once both have finished with it. You can instead let matching run ahead of the flush and gate the outputs. Clients get the same guarantee either way; output gating keeps the replication round trip off the engine thread. With output gating, what must wait is everything visible: an order's ack, its fills and its market data are released only when the command is matched, durable under your week 18 policy, and acknowledged by the standby (week 20). That is released_seq, and both the session writers and the market-data publisher respect it.

Who never blocks. The engine thread must never block on a downstream consumer. Its outputs go into structures it can always write to: a broadcast ring with per-reader cursors for market data, bounded per-session queues with a slow-session policy for execution reports. If a session can't keep up, the policy is to cut that session, not to stall the engine for everyone.

What the repo's exchange v2 does. It keeps the no-blocking rule and is simpler than the diagram in three places:

• Risk: all of week 17's RiskGate (throttle, then limits) runs on the engine thread as the PreTrade hook, before the order is sequenced. The throttle uses the receive time rx_ns, so time spent in the queue never costs a client its budget. Moving the stateless checks out to the session readers is an optimization for later.
• Gating, per batch: outputs are gated per engine batch of up to 256 messages. Stage::on_command appends each command to its instrument's journal before the engine matches it, which makes it the write-ahead point. Then Stage::flush commits the batch: one write per instrument it touched, plus an fsync under fsync = always. That's group commit. After the commit, flush publishes the batch's market data, and only then does the gateway hand the batch's reports to the sessions.
• No replication: week 20's Primary replicates an in-memory journal only, so the repo releases outputs once they're matched and durable. Holding them for the standby as well is an extension.

With week 21's stage stamps on every order, you get one distribution per stage and one end to end. The drill below has five stages; the repo's exchange v2 has six. Two mistakes are common enough that the drill is built around them.

Percentiles don't add. The p99 of the end-to-end latency is not the sum of the stages' p99s. The slow 1% of each stage is usually a different 1% of orders, so the sum overstates the tail, sometimes by a lot. The opposite also happens: a stage can have a perfectly healthy p99 while a handful of its orders (under 1%) are slow enough to dominate the end-to-end p99.9. Measure the end-to-end distribution directly. Never reconstruct it.

Per-stage percentiles find suspects; the tail finds culprits. To explain the end-to-end p99, take the orders at or above it and look at where those specific orders spent their time. In practice the culprit is usually a queue, not a computation: the gap between risk_out and eng_in is waiting, and orders wait because something ahead of them was slow (a large sweep, an fsync stall, a burst from one client). That's head-of-line blocking, and a per-stage service-time histogram can't show it.

Know what each row of the repo's table contains before you blame it:

• gateway: exchange v2 stamps Ingress when the session's socket read returns and Gateway when the engine thread picks the order up. So this row is decode plus the wait in the sessions → engine queue. The queue has no row of its own.
• journal: stamped once per batch, when the group commit returns. Its interval starts at the order's Match, so it includes matching the rest of the batch as well as the fsync. The table prints this row above match (stage order), but it's the interval after it.
• The last stamp, Ack: the server's stamps stop there, when the reports are handed to the session queues. The writer's socket write appears only in the client's number.

The budget above is the same exercise from a trading firm's side (market data in, order out), and week 39 builds it properly. The method is identical: stamp every boundary, attribute the tail, and fix the stage the slow orders actually waited in.

/// Six timestamps (ns) stamped on every order as it crosses a boundary:
///   [0] gw_in      gateway read the message off the socket
///   [1] risk_out   decoded + pre-trade risk passed, enqueued to the engine
///   [2] eng_in     engine thread dequeued it
///   [3] match_out  matching finished
///   [4] durable    command journaled and replicated
///   [5] ack_out    ack written to the client socket
/// The five stage durations are the gaps between consecutive stamps:
pub const STAGES: [&str; 5] = ["gateway", "queue", "match", "journal", "ack"];

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Report {
    pub p50: [u64; 5],
    pub p99: [u64; 5],
    pub e2e_p50: u64,
    pub e2e_p99: u64,
    /// Among the tail orders (end-to-end ≥ e2e_p99), the stage with the
    /// largest TOTAL time. Ties go to the lower index.
    pub tail_stage: usize,
    /// Samples skipped because a stamp went backwards.
    pub invalid: usize,
}

/// The five stage durations, or None if any stamp is earlier than the one
/// before it (a clock or instrumentation bug: never "fix" it with a
/// saturating subtraction).
pub fn durations(s: &[u64; 6]) -> Option<[u64; 5]> {
    let _ = s;
    todo!()
}

/// Nearest-rank percentile of an ascending slice:
/// rank = ceil(q × n) clamped to 1..=n, answer = sorted[rank − 1]; 0 if empty.
pub fn nearest_rank(sorted: &[u64], q: f64) -> u64 {
    let _ = (sorted, q);
    todo!()
}

/// Per-stage and end-to-end p50/p99 over the valid samples, plus which
/// stage the tail orders spent their time in.
pub fn attribute(samples: &[[u64; 6]]) -> Report {
    let _ = samples;
    todo!()
}

Little's law connects the three numbers every queue has: average items in the system L = arrival rate λ × average time in the system W. Turned around, it's the most useful sizing rule in this course. A queue holding 1,000 orders in front of an engine that drains 2 million per second adds 500 µs of waiting to the last order in it. Your end-to-end budget is under 100 µs, so a queue that deep is a latency bug, whatever memory it saves.

So size queues from the latency budget, not from memory: capacity ≈ service rate × the waiting time you can tolerate. Then decide what happens when a queue is full, stage by stage:

• Inbound, at the edge: reject. The gateway answers with an explicit "busy" or throttle reject (week 17) that the client can act on. A rejected order costs the client one round trip; an order accepted into a queue it will wait 5 ms in costs it the market. In the repo this is [gateway] busy_reject. It's off by default: a full queue then makes the session's reader wait, and back-pressure reaches the client through TCP. With it on, a new order that finds the sessions → engine queue full is answered at once with Rejected { reason: BUSY }. types has no busy reason, so BUSY reuses Risk(RateLimit). Cancels and reduces are never refused for load: they wait for room, because they release risk.
• Between internal stages: hold, never drop. A full queue stops the stage feeding it, which fills its input, which eventually reaches the edge, where the reject happens. Dropping an accepted order inside the exchange is unacceptable.
• Outbound to a client: the engine can't wait for a client that isn't reading. If a session's outbound queue (or its TCP send buffer) stays full, disconnect it. The client recovers its state with sequence-number resend (week 14) on reconnect.
• Market data: conflate or disconnect per week 16's policies. Never let a subscriber's speed reach the engine.

Trace one order through exchange v2 below, then drag the offered load past the engine thread's capacity of about 2M orders/s. The inbound queue fills to its bound, the gateway starts answering busy, and the latency of accepted orders stops growing. Trace a p99 order to see where the tail waits, and switch to Ack after match to see what output gating costs in latency and what it buys.

use std::collections::VecDeque;

/// N stages joined by bounded queues:
///
///   offer → [q0] → stage 0 → [q1] → stage 1 → … → [qN-1] → stage N-1 → completed
///
/// Each tick, stage i moves up to rates[i] items from the front of queue i
/// to the back of queue i+1 (or to `completed` for the last stage), but
/// never fills queue i+1 past caps[i+1]. A full downstream queue stalls the
/// stage: that is backpressure. Nothing is ever dropped inside the
/// pipeline; the only place an order may be refused is the edge.
pub struct Pipeline {
    queues: Vec<VecDeque<u64>>,
    caps: Vec<usize>,
    rates: Vec<usize>,
    pub completed: Vec<u64>,
    pub rejected: Vec<u64>,
}

impl Pipeline {
    pub fn new(caps: &[usize], rates: &[usize]) -> Self {
        assert_eq!(caps.len(), rates.len());
        Pipeline {
            queues: caps.iter().map(|&c| VecDeque::with_capacity(c)).collect(),
            caps: caps.to_vec(),
            rates: rates.to_vec(),
            completed: Vec::new(),
            rejected: Vec::new(),
        }
    }

    /// Edge admission: if queue 0 has room, accept and return true;
    /// otherwise record the id in `rejected` (the client gets an explicit
    /// "busy" reject) and return false.
    pub fn offer(&mut self, id: u64) -> bool {
        let _ = id;
        todo!()
    }

    /// One time step. Run the stages from the LAST to the FIRST: space a
    /// downstream stage frees this tick can be used upstream this tick, yet
    /// every item still advances at most one stage per tick.
    pub fn tick(&mut self) {
        todo!()
    }

    pub fn depth(&self, i: usize) -> usize {
        self.queues[i].len()
    }

    pub fn in_flight(&self) -> usize {
        self.queues.iter().map(|q| q.len()).sum()
    }
}

A load test is an experiment, and most load tests have a broken method. The rules for this one:

• Keep the load generator off the system's cores. Pin it to its own cores (or its own machine). A generator that competes for the engine's core measures itself.
• Drive a fixed schedule, not a conversation. A closed-loop generator sends an order, waits for the ack, then sends the next. When the exchange stalls for 5 ms, the generator stops sending for 5 ms, so almost no orders experience the stall, and the percentiles hide it. Gil Tene named this coordinated omission, and week 25 is devoted to it. For now, generate orders on a fixed-rate (open-loop) schedule and measure each order's latency from its intended send time, not from when the generator got around to sending it.
• Measure at both ends. The client-side end-to-end number includes the kernel and TCP. The stage timestamps explain it. Report both.
• Warm up, then measure. The first seconds include page faults, cold caches and untrained branch predictors. Discard them, or report them separately.
• Sweep the rate. One rate gives one point. Step the offered load up and plot p50, p99 and p99.9 against throughput. The knee, where the tail starts climbing steeply, is the capacity number that matters, and it usually sits well below the maximum throughput.

Give the flow realistic structure (bursts, cancels, sweeps), not a uniform stream of identical orders. The repo's load generator, gateway::loadgen, is provided. It gives each session its own sim::OrderFlow, a synthetic trader population that sends passive and aggressive limits, IOC and market orders, and cancels of its own resting orders. Driving the load with your week 23 agents instead is an extension.

Component failure tests ran on an idle system. Run them again at your knee rate, and measure what clients see:

• Kill the primary mid-load (week 20). Measure the gap in acks as seen by clients, check that no released output is lost or duplicated, and time how long the new primary takes to return to the old p99. In the repo this needs the replication extension first, because its exchange v2 has no standby.
• A slow market-data subscriber (week 16). Engine and order-entry latency must not move.
• The kill switch fires for one account at peak (week 15). Its orders are rejected immediately; nobody else notices.
• A throttle storm: one agent bursts far beyond its limit (week 17). It gets throttle rejects; the other sessions' latency stays flat.
• Restart from a snapshot after a long run (week 18), and record the recovery time next to the snapshot's position in the journal. The repo's v2 takes no snapshots yet. On start it replays each instrument's whole journal with engine::recover, and ExchangeV2::recovery() reports how many commands each one replayed. Pre-trade risk state (positions, open orders) starts empty. Record the recovery time against the journal's length, and treat snapshots and rebuilding the risk state as improvements to make.

Then the retrospective. Phase 2 turned a matching engine into an exchange, and you now have numbers for every part of it.

Finish the capstone and run the full load test. Keep the report: Phase 3 starts by re-measuring this number correctly (week 25) and then spends fifteen weeks making it smaller.