Abstract
A single CPU core sustains 32 million order messages per second at sub-microsecond median end-to-end host-path response latency, 4.7-11 times faster than the best available open-source matching engines on identical hardware. Scaled out, a single 96-core commodity server (~$1,630/month) sustains ~640 million messages per second across 10,000 symbols, over 20 times the provisioned capacity of the U.S. consolidated quote feed. We reach these numbers by attacking the storage layer that sets matching latency.
Technical Details
The dominant order-book implementation, linked lists chained through a balanced tree, imposes two costs on every operation: pointer-chased traversal to the insertion point and root-to-leaf search to locate the target price level. Under micro-bursts, these costs produce tail-latency spikes that degrade market quality precisely when liquidity is most needed.
We present two data-structure contributions that eliminate them.
Priority-Indicated Node (PIN)
The first is the Priority-Indicated Node (PIN), a priority queue in which entries occupy fixed-capacity, contiguously addressable slots, with indicators encoding the entry's global priority status. Unlike heaps, which require O(log n) comparisons per operation, the PIN resolves insertion position directly from the indicators without comparing entries; indicator updates are O(1), independent of queue size.
Neighbor-Aware Insertion and Deletion
The second targets a broader inefficiency: balanced search trees search from root to leaf on every insertion and deletion, even when the caller already knows the key's in-order neighbors, which in electronic trading are available at zero cost. Neighbor-aware insertion and deletion use known neighbor references to attach or remove a node with O(1) reference writes, followed by single-path rebalancing, across red-black, AVL, and B+-tree variants.
Blogger's Review: The innovation of this algorithm lies in its improved data structures that significantly reduce matching latency, enhancing the performance of trading systems. This provides strong support for latency-sensitive applications like high-frequency trading and is worth promoting in practical systems.