Networks and data structures

0.7 Networking from the wire up

Everything that reaches a trading system, and every order it sends, is a packet: a block of bytes sent over a wire or fibre. A common Ethernet MTU allows a 1,500-byte IP packet, plus the frame’s headers and checksum; application messages may span packets. Chapter 4 follows one packet through the machine; this section names the parts.

Layers. A packet is a set of nested envelopes. The outer one, the Ethernet frame, carries the hardware addresses of the sending and receiving network cards and is only valid on one local network. Inside it, the IP header carries the addresses of the two machines and lets routers carry the packet across networks. Inside that, a UDP or TCP header carries two port numbers, 16-bit values that say which program on each machine the bytes are for. The rest is the payload: your message. Headers have minimum sizes, but options, IPv6 extensions and VLAN tags can change offsets. A parser must validate the actual headers before locating the payload.

Sockets and ports. A socket is the kernel object a program reads and writes to use the network; it is bound to an address and a port. When a packet arrives, the kernel uses the port to find the socket and the socket to find the thread waiting on it.

TCP and UDP. TCP makes a connection: bytes are delivered in order while the connection works, and lost packets are retransmitted or the connection eventually fails, at the cost of acknowledgements, retransmit timers and Nagle’s algorithm, which holds small writes back to batch them unless TCP_NODELAY is set. UDP sends a datagram and forgets it: no connection, no ordering, no retransmit, and so no waiting. Multicast UDP sends one packet that the network delivers to every subscriber, which is how traditional exchanges publish market data to all members at once, while order entry uses TCP because an order must not be lost. Crypto venues mostly publish over WebSocket, which runs on TCP with TLS encryption, so for them the TCP and TLS costs apply to market data too.

What the network card does. The NIC receives the frame, checks its checksum, writes it straight into a ring of buffers in DRAM without involving a core (direct memory access), stamps the arrival time if asked, and raises an interrupt. From there the kernel takes over: the driver’s interrupt handler, then a deferred kernel task (softirq) that runs the IP and TCP code, then the socket’s receive buffer, then a copy into your buffer when your thread calls read, and a wake-up if the thread was asleep. Those stages can add 5–20 µs on an illustrative kernel receive path. DPDK and Onload can move receive processing into user space; AF_XDP skips the normal protocol stack but retains the kernel’s driver and XDP path, and may still use interrupts and copies.

The frame row shows the envelopes on the wire. Receive processing removes them before a socket reader sees the payload; bypass changes which code performs that processing.

Time on the wire. A 10 Gb/s link moves 1,500 bytes in 1.2 µs; a switch adds a few hundred nanoseconds to a few microseconds; light in fibre covers about 200 km per millisecond, so a round trip between distant cities is tens of milliseconds whatever you do. Colocation, putting your server in the exchange’s own data centre, exists to take the fibre out of the equation.

Bytes and endianness. A number larger than one byte can be laid out most-significant byte first (big-endian, the convention for protocol headers, “network byte order”) or least-significant first (little-endian, what x86 does in registers and memory). Reading a 32-bit field from a packet means picking the right one: u32::from_be_bytes or u32::from_le_bytes. Serialization is the choice of how a message is laid out as bytes: a fixed binary layout, where field 3 is always bytes 16–23, can be read with one load; JSON must be scanned and converted; its cost relative to binary depends on the schema, parser and workload. Zero-copy parsing means reading the fields straight out of the receive buffer rather than copying the message into a struct first.

TLS. Encryption on top of TCP. A handshake at connection start costs milliseconds, once; after that every record must be decrypted on arrival, a per-message cost in the microseconds. Chapter 4 compares doing that in the kernel with doing it in user space.

0.8 Data structures and the Rust words the labs use

Stack and heap. A thread’s local variables live on its stack, a region that grows and shrinks as functions are called and return; putting a value there costs nothing beyond the function call. Values can also be returned or live in static storage; heap allocation is a separate lifetime and storage choice. Common heap-owning types are Vec, Box, String and HashMap, though empty collections and zero-sized values can avoid allocations. An allocation costs tens of nanoseconds when the allocator has free space and a syscall when it does not, and freeing has similar costs. Chapter 5’s first rule, allocate nothing on the hot path, follows from that.

Contiguous or linked. A Vec<T> or an array [T; N] stores its elements side by side in one block of memory, so element i is at a computable address and neighbours share cache lines. A linked structure (LinkedList, a tree of Boxes, a Vec<Box<T>>) adds indirection. A linked list’s next address depends on its current node; a Vec<Box<T>> has contiguous pointers, so several pointee loads can overlap. Chapter 1 measures the difference at 100× or more. Big-O notation (O(1), O(log n), O(n)) counts steps as n grows; it says nothing about what a step costs, and on this hardware a step can be 1 ns or 100.

Hash maps. A HashMap<K, V> turns a key into a number with a hash function and uses that number to pick a slot. Lookup is O(1) in steps but each step touches memory the prefetcher cannot predict, and the table occasionally doubles in size, moving everything. When keys are small integers such as an instrument id, a Vec<V> indexed by the id does the same job with one predictable load.

Ring buffers. A queue built on a fixed-size array: a producer writes at index head, a consumer reads at index tail, both count upwards forever, and the slot is index % capacity. With a power-of-two capacity the % becomes a bit mask. Nothing is allocated after startup, and with one producer and one consumer two atomic counters are enough. It is the queue the book uses between threads.

Bitmaps. A u64 used as 64 yes/no flags. trailing_zeros finds the lowest set bit in one instruction, which turns “find the next non-empty price level” into a few cycles instead of a scan.

Rust words you will meet. #[repr(C)] fixes a struct’s field order to what you wrote, as C does, which helps with FFI and field placement. It does not by itself make a packet overlay safe: length, alignment, valid bit patterns and byte order still need checking. #[repr(align(64))] starts the struct on a cache-line boundary. unsafe marks code where you, not the compiler, guarantee memory safety: raw pointers, get_unchecked to skip a bounds check, MaybeUninit to leave memory unwritten. #[inline] asks the compiler to paste a function into its caller. std::hint::black_box stops the optimiser deleting a benchmark. cargo build --release turns optimisations on; debug builds are 10–50× slower and every measurement in this book is made in release mode. cargo asm (the cargo-show-asm crate) prints the machine instructions the compiler produced for one function.