Process One Million Quote Updates per Second

A cross-exchange quote system must process **1,000,000 quote updates per second** with low latency. For each instrument and exchange, it maintains the current bid, ask, and available sizes. Opportunity detection requires a valid bid to be strictly above a valid ask on a different exchange. The reported design suggestions include preallocated contiguous memory, flat data structures, direct addressing by instrument and exchange IDs, and incremental maintenance of best prices. It also suggests retaining only each instrument's global best bid and ask and checking for opportunities only when a new quote improves one of those extrema. Explain how you would design the concurrent processing path and choose its data structures. Evaluate the correctness of the extrema suggestion when a winning quote worsens, is removed, or becomes stale. No hardware capacity, maximum instrument/exchange count, or numeric tail-latency target is supplied; distinguish design choices from measured guarantees. ### What a Strong Answer Covers - Memory layout and ID mapping that make direct addressing valid without assuming arbitrary external IDs are dense. - Ownership and publication of consistent quote state under concurrent feeds. - Correct maintenance of current best and alternative quotes, including distinct-exchange eligibility. - Update, expiry, and recovery costs; contention, bounded buffering, and overload behavior. - A workload and latency measurement plan that can establish whether the stated update rate is achieved. ### Follow-up Questions - Why can remembering only the all-time best prices create a false opportunity? - When might a short scan outperform a more complex extrema structure despite its asymptotic cost?