Moving work off the hot path

In Naoto the hot path is everything between an order arriving at a gateway and the matching engine being done with it. Time spent there shows up directly in someone's latency. The cold path is the rest, work that still has to happen but that no order is waiting on at that moment.

Before writing any code I went through every action an order sets off and asked whether it really had to happen on the hot path. Answering that took two angles at once. There's the context the action lives in: what it's for, which other service it involves, and what actually breaks if it happens earlier or on another thread. And there's what the hardware does with it, whether it's a syscall, an allocation, a network round trip, or a cache line that has to cross from one core to another.

Most of the work could move, in one of two directions. Earlier, to compile time, startup or login, before the order even exists. Or sideways, onto another thread that runs next to the hot one and never makes it wait. What's left on the hot path is five short steps.

Moving it earlier

The easiest moves are to compile time. Every pool, queue and batch is sized there, in one config header, and so is the number of records in each multicast packet, which is derived from the MTU. The shared loops (the epoll server, the queue consumer, the multicast emitter and receiver) are CRTP templates constrained with C++20 concepts, so which handler runs is decided by the compiler instead of by a virtual call on every message.

Startup takes what can't be decided at compile time but only needs doing once. Every pool is filled, so an order is read off the socket into a batch that already exists and goes back to the pool when the risk thread is done with it, and nothing on the path allocates. Threads are pinned to cores, though not yet one core each (where the threads sit). The gateway also looks up every matching engine registered in etcd and connects to it then, so the first order for an asset doesn't pay for a TCP handshake.

The account service, asked once per login

The biggest move is to login. The account service owns every balance, so the straightforward design asks it about every order: check the funds, reserve them, wait for the answer. That's a network round trip per order, and the account service's latency, and whether it happens to be up, becomes part of everyone's order latency.

In Naoto the gateway asks once, when the client logs in. It forwards the credentials and gets back a snapshot of the client's positions, tagged with the sequence number of the last trade report it reflects. From then on the gateway keeps that state current on its own, from the same multicast stream of trade reports the account service reads (one stream, many copies).

The snapshot is usually a little behind by the time it arrives, which is fine, because the gateway keeps the recent reports and replays the ones after that sequence number onto it (replaying a stale snapshot). This one was mostly a question of context. The balance has to be right, but nothing requires the account service to be the one answering on every order, as long as only one gateway can ever spend a given client's balance (one writer for every piece of state).

The same reasoning keeps the risk check from waiting on the engine: it reserves funds the moment it accepts an order instead of waiting for a confirmation (checking risk against a balance that's always behind).

Moving it sideways

Some work has to happen for every order, just not while the order waits on it. That work runs on other threads, and the hot thread's side of each handoff is pushing a pointer onto a single-producer single-consumer queue.

The ack to the client is the simplest case. The risk thread doesn't call send on the client's socket, it queues the confirmation and moves on to the next order, and a separate sender thread makes the syscall. The engine does the same with what it produces: the matching thread fills a pooled trade report and pushes its pointer, and the DPDK emitter packs reports into multicast packets on another core. Discovery goes the other way. When an engine joins or leaves, an etcd watcher thread opens the new connection and swaps it in as a versioned fd, so all the risk thread does about it per order is one atomic load.

Applying fills to client state is where the hardware angle mattered most. Handing work to a second thread only helps if the two don't end up fighting over the same memory, because a cache line written on one core and read on another has to travel between them, and a line both of them write keeps bouncing back and forth. So the states writer is the only thread that writes client state. It writes into one of three copies and publishes it with a single store to an index (triple buffering), and the risk thread only reads. The reservations the risk thread makes live in memory no other thread touches, so they never leave its core (a thread-local counter).

Client state is indexed by the client's socket fd, so finding it is an array offset rather than a hash lookup, and each copy is 64-byte aligned and 320 bytes long: five cache lines, copied once per order. Measured, copying all five instead of the one asset slot the check reads costs about 10 ns more, because the core fetches the lines in parallel (measured against a mutex and a seqlock).

What stays

The five steps left are the order itself, so they can't move anywhere. They got made cheap where they are instead.

The order book is the biggest of them. It answers two questions constantly, whether a price level exists and which price is best, and no single structure is good at both, so it keeps a hand-written SIMD hash map and a skip list side by side (one order book, two data structures, and the SIMD key-value store under it). Stamping the order id is a shift and an increment, with no id service to ask (order ids without an id service).

The transport is picked per link. Client orders come in on edge-triggered epoll, read straight into pooled batches. When a gateway and an engine share a machine, orders cross in a shared-memory SPSC queue instead of a socket. Trade reports and book updates go out through DPDK as fixed-size packed structs, so a receiver never parses a length.

Measuring it

P99 is 600 ns in matching and 1.1 µs to gateway ack at 40k msg/s. Each order and report carries four timestamps: ingested by the gateway, routed, received by the engine, emitted as an update. Those are tracked at min, P50, mean, P95, P99 and max, so a regression shows up as a specific segment getting slower rather than one number drifting.

The 1.1 µs runs from ingested to routed, which is the server thread on CPU 2 handing the order to the risk thread on CPU 4 and the risk check deciding. It stops there. The ack still has to reach the sender thread and go out on the socket, and the client state the risk check read was written on another core earlier. Neither of those is in the number, and measuring them separately is how the next section came about.

Where the threads sit

The laptop these numbers come from has a Ryzen 5 4600H, whose six cores come in two halves of three (CPUs 0 to 5 and 6 to 11 as Linux numbers them, two hardware threads per core), and each half has its own L3. A cache line moving between two cores has to cross whatever separates them. Measured with the method of nviennot's core-to-core-latency, one compare-and-swap ping-pong, it costs 9.4 ns between the two threads of one core, 19 to 24 ns between cores of the same half, and 62 to 88 ns between halves, in line with the 16 to 24 ns and 84 to 92 ns that repository lists for other Ryzen generations.

Naoto's own SPSC queue pays more per hop, since the consumer reads the slot and the producer then has to take the line back to write the next one. One way, it's 50 ns between the two threads of one core, 90 ns within a half, and 180 to 385 ns between halves, the cross-half figure changing from one run to the next. A round trip within a half is 180 ns, against 133 ns for rigtorp's SPSCQueue on a desktop Zen 2 chip.

Those costs are small next to what happens on CPU 10. The gateway pins three threads there, the states writer, the account receiver and the ack sender, and all three busy-poll, so none of them ever gives the CPU up. The scheduler then rotates them, and on this machine the default slice is 0.70 ms × (1 + log2 8) = 2.8 ms (kernel/sched/fair.c). An item pushed to a consumer on CPU 10 that's alone there arrives in 0.3 µs at P50 and 0.7 µs at P99. With two other spinning threads on the same CPU it takes 1.47 ms at P50 and 5.96 ms at P99. That matches the rotation almost exactly: a third of the items land while the consumer is running, the rest wait for anything up to the other two threads' slices, 5.6 ms, which predicts 1.4 ms at P50 and 5.5 ms at P99.

That puts a lock-free queue in the same range as the lock-based queue the LMAX Disruptor paper set out to replace, whose P99 was 2.1 ms. It doesn't touch the 1.1 µs, since CPUs 2 and 4 aren't involved, but it's what an ack waits before the sender thread gets to it, and it's how far behind a client's balance is when the risk check reads it (how far behind it is). These numbers come from a benchmark that reproduces that pinning, not from the running gateway, which doesn't time its acks on the client side yet.

The account receiver and the request sender only carry logins, so they don't need to spin at all and can block until there's something to read. That leaves CPU 10 to the writer, with a core of its own for the ack sender. A six-core laptop can't give every thread a core, which is why the threads that only handle logins shouldn't be spinning in the first place.