itch-book: Nasdaq feed handler

What it is

Nasdaq publishes every order event on its exchange as a stream of compact binary messages called TotalView-ITCH 5.0: hundreds of millions a day. Each one says something like "order 123 to buy 100 shares at $150.00 added" or "order 123 cancelled". itch-book reads that stream and rebuilds the order book for every stock: at each price, how many shares are bid and offered. This is the first thing any trading system has to do, and it has to be both correct and fast.

Results

On a 20-million-message feed:

• 10.9 ns per message to decode (92 million messages a second)
• 89 ns per message to decode and rebuild every stock's book (11.2 million a second)
• per-message latency: median 60 ns, 99th percentile 456 ns
• zero missing orders and zero book inconsistencies

Measured on a cloud VM with a synthetic feed; results on a full real Nasdaq trading day are next.

How it works

• Zero-copy decoder: messages are read straight from a memory-mapped file (or streamed from Nasdaq's .gz files) with no copying, and dispatch is a template, so there are no virtual calls.
• Order map: an open-addressing hash table with backward-shift deletion, so a full day of adds and deletes never leaves tombstones behind.
• Price levels: each side of the book is a contiguous array with the best price at the end, because nearly all activity happens at the top of the book.

Choosing the hash, by measurement

Order IDs arrive roughly in sequence and most cancels hit recent orders, so I benchmarked three hash functions. The obvious fast one degraded to 12 probes per lookup when old orders lingered. The one I chose keeps blocks of 64 consecutive IDs together for cache locality but scatters the blocks, so it stays fast in every case.

Testing

A generator writes feeds in Nasdaq's exact format while separately tracking every open order. The tests rebuild the expected book from scratch and compare the full depth of every stock with the fast one: 480,000 checks, including feeds split into random chunks. I also planted bugs on purpose to make sure the tests catch them.