Tick-to-Trade Latency Budget

Before you can budget a path you have to name every stage, including the ones your code never sees. Walk through the trading-firm version first, because it has the most stages:

1. Wire in. Serialization delay depends on the link speed. A 64-byte Ethernet frame also carries 20 bytes of overhead on the wire (7 B preamble, 1 B start-of-frame delimiter, 12 B inter-frame gap), so 84 bytes = 672 bits. At 10 Gb/s, which moves 10 bits per ns, that takes 67.2 ns. At 25 Gb/s it takes about 27 ns. Propagation in fiber adds roughly 5 ns per metre (light in glass travels at about two thirds of c), so a 50 m cross-connect inside a colocation facility costs about 250 ns before any electronics.
2. NIC → host memory. The NIC DMAs the frame over PCIe and writes a completion descriptor. A busy-polling thread notices it on its next poll. With kernel bypass (week 33) this is typically a few hundred ns. Through the kernel stack, with interrupts, softirq processing and a socket wakeup (week 31), it's several microseconds.
3. Decode + book update. Parse the feed message (week 11) and update a cache-resident book (week 28). Tens to low hundreds of ns if everything stays in L1/L2. An L2 miss that hits in L3 costs roughly 40–80 cycles (about 10–25 ns, depending on the microarchitecture). A miss that goes all the way to DRAM costs around 80–120 ns, and more if the memory is on the remote NUMA node.
4. Decision. Anything from a table lookup (tens of ns) to a model evaluation (microseconds). This stage is where firms spend their engineering.
5. Pre-trade risk. Week 15's checks: well under 100 ns when the limits are in cache.
6. Encode + send. Tens of ns to encode. Then the NIC has to fetch the descriptor and payload over PCIe, which costs hundreds of ns unless the NIC supports pushing small frames directly from the CPU, as some low-latency NICs do.
7. Wire out. Another serialization delay before the first bit leaves.

Your exchange's order path has the same shape: NIC → gateway decode → risk → match → publish ack → NIC. In this curriculum you measure the in-process part (gateway decode to ack published), so be explicit that the wire, NIC and kernel stages sit outside it.

A useful budget has three properties:

• It's stated at a percentile and a load. "Gateway decode: 150 ns at p99 at 200k orders/s open-loop" can be tested. "Gateway decode is fast" can't. Means add up neatly, which is why people budget them, but the mean is the wrong number for a trading path. What hurts you is the p99 and p99.9.
• It starts from the floors. Some costs don't move however good your code is: serialization delay, a PCIe round trip, the cache-line transfer when a message crosses from one core to another (on the order of 50–100 ns on one socket and more across sockets; it depends on the microarchitecture). Write those down first. If the floors already exceed the target, no optimization will save you. You need a different architecture.
• It keeps a reserve. Hold back a slice of the total for jitter you can't predict: an interrupt you didn't route away, a cold i-cache after a quiet period. 10–25% is a common heuristic, not a law. Without a reserve, the first unexpected 300 ns fails the whole path.

Once the floors and the reserve are set, share the remaining slack in proportion to how much variable work each stage does. A stage that is pure memcpy gets its floor. The strategy stage gets most of what's left. Each stage then has an owner and a number, so the owners can optimize independently, and CI can fail a change that pushes one stage past its share.

in-process order path (example shape, not targets)
stage            floor     budget p99   measured p99   owner
---------------  --------  -----------  -------------  --------
gateway decode     ~30 ns      200 ns         ?          gateway
queue: gw → risk   ~80 ns      150 ns         ?          sync
risk               ~20 ns      150 ns         ?          risk
match              ~60 ns      500 ns         ?          engine
publish ack        ~40 ns      250 ns         ?          marketdata
reserve                        ~20%

Notice the queue row. Time an order spends waiting between stages is a stage in its own right. If you lump it into the next stage's service time, you'll go looking for a slow risk check when the real problem is a consumer thread that went to sleep.

/// One stage of the tick-to-trade path.
#[derive(Clone, Copy, Debug)]
pub struct Stage {
    pub name: &'static str,
    /// Irreducible cost in ns: wire time, a PCIe crossing, a cache miss
    /// you cannot design away.
    pub floor_ns: u64,
    /// Relative share of the slack this stage gets (how much variable
    /// work it does). 0 = floor only.
    pub weight: u32,
}

/// Serialization delay of one Ethernet frame of `frame_bytes` on a link
/// of `gbps` Gbit/s, including the 20 bytes of per-frame overhead on the
/// wire (7 B preamble + 1 B start-of-frame delimiter + 12 B inter-frame
/// gap). Round UP to the next whole nanosecond.
/// Hint: 1 Gbit/s moves exactly 1 bit per ns.
pub fn wire_ns(frame_bytes: u64, gbps: u64) -> u64 {
    todo!()
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Allocation {
    /// Budget per stage, in the same order as the input.
    pub per_stage_ns: Vec<u64>,
    /// Unallocated time: the held-back reserve plus rounding leftovers.
    /// Invariant: sum(per_stage_ns) + reserve_ns == total_ns.
    pub reserve_ns: u64,
}

/// Split `total_ns` into per-stage budgets:
///   1. hold back reserve = total_ns * reserve_pct / 100 (integer division)
///      for jitter you cannot predict;
///   2. every stage gets its floor;
///   3. the remaining slack is shared in proportion to `weight`
///      (slack * weight / sum_of_weights, integer division per stage);
///      whatever rounding leaves over goes back to the reserve.
/// If the floors do not fit in total − reserve, return Err(shortfall_ns).
pub fn allocate(stages: &[Stage], total_ns: u64, reserve_pct: u64) -> Result<Allocation, u64> {
    todo!()
}

Put a stamp at every boundary, not inside stages. One clock read marks both the end of stage i and the start of stage i + 1, so five reads cover four stages with no gaps between them. Carry the stamps with the order in a fixed-size array so that later analysis can see all of one order's stages together:

/// Stage boundaries for one order: ingress, decoded, risk-checked,
/// matched, ack published. Raw clock ticks; converted to ns off the hot path.
#[derive(Clone, Copy, Default)]
#[repr(C)]
pub struct Stamps(pub [u64; 5]);

pub struct InFlight<T> {
    pub msg: T,
    pub stamps: Stamps, // 40 bytes riding along — no allocation, no atomics
}

impl Stamps {
    #[inline(always)]
    pub fn mark(&mut self, boundary: usize, clock: &Clock) {
        self.0[boundary] = clock.raw(); // week 21's raw TSC read, no conversion
    }
}

Each stamp has a cost. From week 21: rdtsc takes roughly 20–40 cycles on recent x86 (single-digit ns), and Instant::now() through the vDSO is roughly 15–30 ns with a TSC clocksource. Five reads on a 1–2 µs path is a few percent overhead. You can afford that, but measure it: run the bench with stamping compiled out and compare.

Three details decide whether the stamps can be trusted:

• Ordering. rdtsc isn't a serializing instruction, so the CPU can execute it before earlier loads have finished. That's harmless for coarse stage boundaries. Where it matters, use lfence; rdtsc or rdtscp. Intel's Software Developer's Manual documents the lfence pattern for exactly this case.
• Cross-core consistency. Each stage may run on a different core. On modern x86 with an invariant TSC (constant_tsc and nonstop_tsc in /proc/cpuinfo), the TSCs on one machine are synchronized, so stamps from different cores can be subtracted. Check this once at startup rather than assuming it (week 21). Across machines you need PTP and NIC hardware timestamps, and even then the error is tens of ns at best.
• Where the ingress stamp really is. A software stamp taken after recv returns misses the NIC, the kernel and any time the packet waited in a socket buffer. That's exactly the part that misbehaves under load. Hardware RX timestamps (SO_TIMESTAMPING on Linux, or the bypass stack's equivalent) close that gap.

Record the stamps off the hot path. Either copy each finished Stamps into an SPSC ring that a cold thread drains into per-stage histograms (week 19), or have the hot thread record into a thread-local histogram that a background merger reads. Never use a shared, locked histogram.

The obvious method gives the wrong answer. Compute each stage's p99, then point at the biggest. The trouble is that a stage can have a fat tail of its own that rarely lines up with the end-to-end tail. Another stage can be quiet 99.5% of the time and then take 5 µs at exactly the moments that make up the end-to-end tail.

The procedure that works is conditional:

1. Compute the end-to-end latency of every order and find the threshold at your percentile (nearest rank).
2. Keep only the orders at or above it. Those are the tail.
3. For each stage, measure how abnormal it was in those orders. One simple measure is the mean excess over that stage's own median across all orders.
4. The stage with the largest excess owns the tail. Then confirm it: reproduce the condition, fix it, and check that the end-to-end p99 actually moves.

The drill's data is built to fool the obvious method. The publish stage adds 400 ns jitter to one order in five, so it has the worst per-stage p99. The risk stage is quiet except for five orders in a thousand that take an extra 5 µs. The conditional analysis points at risk.

pub const STAGES: usize = 4;
pub const STAGE_NAMES: [&str; STAGES] = ["gateway", "risk", "match", "publish"];

/// Timestamps (ns) taken at the boundaries of one order's path:
/// t[0] ingress, t[1] after gateway decode, t[2] after risk,
/// t[3] after matching, t[4] after the ack is published.
pub type Stamps = [u64; STAGES + 1];

/// Per-stage latency: d[i] = t[i + 1] − t[i].
pub fn stage_latencies(s: &Stamps) -> [u64; STAGES] {
    todo!()
}

/// Nearest-rank percentile of an ASCENDING-sorted slice:
/// index = ceil(q · n) − 1, clamped to [0, n − 1]. Empty slice → 0.
pub fn percentile(sorted: &[u64], q: f64) -> u64 {
    todo!()
}

#[derive(Debug, Clone, PartialEq)]
pub struct TailReport {
    /// End-to-end latency (t[4] − t[0]) at quantile q, nearest rank.
    pub threshold_ns: u64,
    /// Number of samples whose end-to-end latency is ≥ threshold_ns.
    pub tail_count: usize,
    /// Per stage: the MEAN over tail samples of max(0, d[i] − median_i),
    /// where median_i is stage i's median (q = 0.5) over ALL samples.
    /// Integer division.
    pub excess_ns: [u64; STAGES],
    /// Index of the largest excess (lowest index wins ties).
    pub culprit: usize,
}

/// Which stage is responsible for the end-to-end tail? Not "the stage
/// with the worst p99" — the stage that is unusually slow in the samples
/// that ARE the end-to-end tail.
pub fn attribute_tail(samples: &[Stamps], q: f64) -> TailReport {
    todo!()
}

Attribution is a lead, not a verdict. Stages are often correlated: a page fault in the gateway leaves risk running on a cold cache, so both look slow. Use the attribution to choose your first experiment, then let the experiment decide.

Once your code is tight, the tail mostly comes from outside it. Typical magnitudes, which vary a lot with hardware, firmware and kernel version:

• Interrupts and softirqs landing on the hot core: a few µs each. Steer them away with /proc/irq/*/smp_affinity and keep housekeeping work on other cores (week 30).
• The scheduler tick. On a core that isn't nohz_full, the timer interrupt fires at CONFIG_HZ (commonly 250–1000 Hz) and steals on the order of a microsecond each time. nohz_full plus isolcpus (or cpusets) on the hot cores largely removes it.
• System Management Interrupts (SMIs). The firmware takes over the CPU, invisibly to the OS, for tens to hundreds of µs. The only remedy is BIOS settings and choice of platform. Detect them with the kernel's hwlat tracer or hwlatdetect from rt-tests.
• Page faults. A minor fault costs on the order of a microsecond, a major fault milliseconds. Pre-fault everything at startup and mlockall(MCL_CURRENT | MCL_FUTURE).
• TLB shootdowns. When any thread in your process unmaps or changes the protection of memory, every core running the process takes an inter-processor interrupt. An allocator that returns memory to the OS on a cold thread can stall your hot thread this way.
• Transparent huge pages. Compaction and khugepaged can stall you. Prefer explicit huge pages, or THP in madvise mode.
• Power management. Waking from a deep C-state can take tens of µs. Check /sys/devices/system/cpu/cpu*/cpuidle/state*/latency. Busy polling keeps the core in C0. Frequency changes add their own wobble.
• Neighbours. An SMT sibling sharing your core's execution units and L1/L2, or another process thrashing the shared L3. Disable the sibling or leave it idle. On CPUs that support it, resctrl (Intel's Cache Allocation Technology or AMD's equivalent) can partition the L3.
• Your own cold paths. Allocator slow paths, log formatting, a hash map resize, the first execution of code that fell out of the i-cache during a quiet period. Week 38's hot/cold split exists for these.

For tooling, Linux has the osnoise and timerlat tracers (5.14 and later) for OS noise on a given CPU, cyclictest for wakeup latency, and perf sched for scheduler delays.

A budget is only real if it's written down and checked. The document needs:

• The scope: which boundaries the path includes and which it excludes (wire, NIC, kernel).
• The load: the open-loop offered rate and message mix the numbers refer to (week 25). A budget that holds at 10k orders/s and breaks at 200k is two budgets.
• Per stage: floor, budget, measured p50/p99/p99.9, owner, including queueing stages.
• The reserve, and how much of it the current build uses up.
• The tail attribution of the latest run, and what you did about it.
• The environment: CPU model, kernel, isolation and pinning, frequency settings, and the commit.