Rate Limiting & Fairness

Venues limit message flow for three different reasons, and each one leads to a different mechanism:

• Capacity protection: a hard cap on messages per second per session, enforced at the gateway. Excess messages are rejected immediately, so the engine never sees them.
• Fairness: no participant's burst should delay everyone else's orders. That takes per-session limits and a fair way of serving sessions when the engine is busy (Day 5).
• Incentives: order-to-trade ratio programs penalize flow that doesn't trade. CME's Messaging Efficiency Program and MiFID II RTS 9 are the well-known examples. These are measured over hours or days and enforced with fees or reviews, not per message.

This week is about the first two. They act in nanoseconds on every message.

A token bucket has two parameters: a rate r (tokens per second) and a capacity b (the burst). It starts full. Each message takes a token if one is available and is rejected otherwise. Tokens refill continuously at rate r, never beyond b. Over any interval of length T, at most b + r·T messages pass. That's the whole guarantee, and it's why venues describe throttles as "N per second with a burst of M".

The implementation is "refill for elapsed time, then try to take", and nearly everyone gets it wrong the first time in one of four ways:

1. Losing fractional tokens. At 1,000 tokens/s, a call 100 µs after the last one earns 0.1 tokens. If you compute elapsed_ns * rate / 1e9 in integers and then set last = now, that 0.1 is rounded to 0 and thrown away. A client calling every 100 µs never gets a token back. Fix it by keeping tokens in scaled units (1 token = 10⁹ units, so elapsed_ns × rate is exact), or by advancing last only by the time you actually converted into whole tokens.
2. Overflow after idle. elapsed_ns × rate with an hour of idle at a million tokens per second is 3.6 × 10¹⁸, close to the u64 limit, and a day overflows. Use u128 for the product, or cap elapsed time at the time-to-full before multiplying.
3. Time going backwards. An injected clock can step back: a different core's timestamp, a test, or a replayed log. now − last then underflows. Treat any time at or before the latest seen as "no time passed", and never rewind last.
4. Partial takes. A request for n tokens with fewer than n available must take none.

pub struct TokenBucket {
    capacity: u64,
    rate_per_sec: u64,
    tokens: u64,
    last_ns: u64,
    // These fields are a starting point, and they hide a precision bug
    // (see Day 2). Change them as you see fit.
}

impl TokenBucket {
    /// Starts full.
    pub fn new(capacity: u64, rate_per_sec: u64, now_ns: u64) -> Self {
        TokenBucket { capacity, rate_per_sec, tokens: capacity, last_ns: now_ns }
    }

    /// Refill for the time since the latest time seen, then take `n` tokens
    /// if all n are available (otherwise take none and return false).
    /// Never panics or overflows. A now_ns earlier than one already seen adds nothing.
    pub fn try_acquire(&mut self, now_ns: u64, n: u64) -> bool {
        todo!()
    }

    /// Whole tokens available at now_ns (refills, does not consume).
    pub fn available(&mut self, now_ns: u64) -> u64 {
        todo!()
    }
}

The Generic Cell Rate Algorithm (GCRA), from ATM networking (ITU-T I.371), is a token bucket rewritten as a single timestamp. Let T = 1/r be the emission interval and τ = (b − 1)·T the burst tolerance. The state is the theoretical arrival time (TAT): when the next message would be due if the client sent at exactly rate r.

// GCRA: equivalent to a token bucket with rate 1/t_ns and capacity b.
fn try_acquire(tat: &mut u64, now: u64, t_ns: u64, tau_ns: u64) -> bool {
    let tat_now = (*tat).max(now);
    if tat_now - now > tau_ns {
        return false;           // arrived too early: more than the burst ahead of schedule
    }
    *tat = tat_now + t_ns;      // conforming: push the schedule forward one interval
    true
}

It has one u64 of state, no refill loop and no multiplication on the hot path, and it handles long idle naturally because max(tat, now) forgets old history. The catch is that T must be an integer number of nanoseconds. For rates that don't divide 10⁹, the rounding error in the rate is tiny but nonzero. Document it, or keep T in finer units.

Where now comes from matters as much as the algorithm:

• Don't read the clock inside the check. Instant::now() costs on the order of 20 ns on typical Linux x86 hardware, half the week's 40 ns budget. Read it once per message (or once per batch of messages from one socket read) at the gateway and pass it down.
• Make decisions reproducible. If throttling happens at the gateway, before sequencing, the journal holds only accepted commands, and replaying the journal reproduces the engine exactly. Log rejects with their timestamps if you need to audit them. If a throttle runs inside the engine, drive it from the sequencer's timestamp recorded in the journal, never from a fresh clock read, or replay will disagree with production.

Many venues specify limits as "at most N messages in any one second". There are three ways to count:

• Fixed window: one counter per calendar second, reset at the boundary. It's simple and badly wrong at the edges. N messages at 0.999 s and N more at 1.000 s are 2N within a millisecond, and the limit is violated by every useful definition.
• Sliding log: keep the timestamps of the last N accepted messages in a ring. A new message is allowed if fewer than N timestamps fall within the window, which means the oldest of the N is at least W old. It's exact for every window and O(1) per check, but costs N timestamps of memory per session, which matters at N = 10,000 and thousands of sessions.
• Bucketed sliding window: split W into K buckets of W/K and keep a counter per bucket in a ring. The count is the sum over the current bucket and the K − 1 before it. Memory is K counters. Any interval shorter than W − W/K holds at most N messages. A burst of 2N is still possible, but only spread over nearly a full window, not packed into a microsecond at a boundary. More buckets give a tighter guarantee and cost more counters.

Some systems interpolate instead: count the current fixed window plus the previous window's count weighted by how much of it still overlaps. That's two counters and approximately right, which is fine for abuse protection and not for a venue rule that must be enforced exactly.

Below, one bursty client hits three limiters with the same long-run rate: a fixed window, the bucketed sliding window and Day 2's token bucket. Switch to Edge attack and watch the fixed window pass almost 2N within 100 ms while the other two hold, then set the bucket's refill to Naive and watch Day 2's rounding bug throw its credit away.

pub struct SlidingWindow {
    limit: u32,
    bucket_ns: u64,
    counts: Vec<u32>, // ring of K counters; slot = bucket_id % K
    ids: Vec<u64>,    // absolute bucket id each slot currently counts (u64::MAX = none)
    last_bucket: u64, // highest bucket id seen; time never rewinds
}

impl SlidingWindow {
    /// The window is `buckets` buckets of window_ns / buckets each.
    pub fn new(limit: u32, window_ns: u64, buckets: usize) -> Self {
        SlidingWindow {
            limit,
            bucket_ns: window_ns / buckets as u64,
            counts: vec![0; buckets],
            ids: vec![u64::MAX; buckets],
            last_bucket: 0,
        }
    }

    /// Accepted messages in the current bucket plus the K-1 buckets before it.
    /// Current bucket = max(now_ns / bucket_ns, last bucket seen).
    pub fn count(&mut self, now_ns: u64) -> u32 {
        todo!()
    }

    /// If count(now) < limit, count this message in the current bucket and
    /// return true. Rejected messages are not counted.
    pub fn try_acquire(&mut self, now_ns: u64) -> bool {
        todo!()
    }
}

Per-session throttles bound each session, but two fairness problems remain:

• Hierarchy. A firm can open twenty sessions to get twenty budgets. So limits nest: session within account within firm, and a message must pass every level. The check must be all-or-nothing. Check all the buckets, then consume from all of them. Consume from the session bucket first and then fail on the account bucket, and the session has lost a token for a message that was never sent. Under sustained load that leak looks like an unexplained throttle.
• Contention at the engine. Even when every session is within its limits, the sum can exceed what the engine can process right now. With one shared FIFO, whoever sends the most in a burst occupies the queue and everyone else waits behind them. Per-session queues served round-robin (or with deficit round robin, when commands have different costs) give each active session a fair share of engine time during contention.

Be careful what you call fair. The order in which the sequencer takes commands is time priority in the book. Round-robin across sessions means a session that sent first in wall-clock time may be sequenced second. Many venues keep strict arrival order and rely on throttles alone. Others use fair queuing, explicitly and in their rulebooks. Either way, it's a market-structure decision, so document it.

The algorithm is the easy part. The policy around it decides whether the throttle helps or hurts:

• What counts. New orders and modifies, certainly. Heartbeats, usually not. Cancels are the contentious case: throttling them can trap a client in risk it's trying to reduce during exactly the fast market that triggered the burst. Common answers are a separate, larger cancel budget, or exempting cancels and relying on the engine's capacity margin.
• Where it runs. In the reader task, after framing and session checks and before the command enters the engine queue. Rejected messages cost the gateway a little CPU and the engine nothing.
• What the client sees. A reject with an explicit "throttled" reason and, ideally, when the budget refills. Under a sustained flood, the rejects themselves become load, so escalate after a configured period: throttle the rejects, then disconnect.
• Configuration. Limits per session class (market maker vs. regular), loaded and validated at startup (week 22) and changeable by operations without a restart.