Stock exchanges are electronic marketplaces where participants trade securities.
Let’s attempt to design one! First, let’s clarify some basics before proceeding to the design.
Order Types
Users place orders to buy/sell using mainly market and limit orders.
A market order specifies the security, say APPL, the number of shares, and whether it is a buy or sell order. The price is then determined based on the lowest price anyone is currently willing to sell the stock at.
A limit order additionally specifies the price. In the case of a buy-limit order, the price determines the highest price at which the user is willing to purchase the security. If the limit order cannot be fully matched, it enters the order book. This is different from market orders, which do not ever enter the order book.
There are other types of orders as well: take profit, stop loss, or order canceling, but I will not go into these.
Order Books
The core of an exchange is an order book - a data structure that holds limit orders, sorted by price and time. Sorting by price guarantees that the best offer is at the top of the order book, sorting by time then helps to differentiate offers at the same price.
The difference between the top orders in buy and sell order books is known as the bid-ask spread.
Dark Pools
Dark pools sound ominous, but they are just anonymous exchanges where orders can be placed without being publicly visible. This helps to reduce the market impact of large transactions. The bottom line is that in a dark pool exchange, the participants don’t see the order books when they place orders. Participants typically determine the price at which they place orders by referencing the price at a public exchange.
With definitions out of the way, let’s move to the fun part: designing and building an exchange.
Designing an Exchange
An exchange needs a couple of basic features:
Ability to receive user orders
Order books to store orders
Matching engine to match incoming orders with orders already in the order book
A full exchange would also have a lot of other features, like authentication, compliance, risk management, etc. To keep things simple, I’ve focused mainly on the matching engine and order books, which form the core of any exchange.
I’ve been picking up Go recently, so that’s what I used. There are more performant options including C++, Rust, and COBOL.
I opted for a gRPC server to handle receiving orders. It’s pretty simple to set up, performant, and automatically deserializes orders into structs, which is a delight to work with.
The server just places incoming orders into a queue for another goroutine to process. The gRPC server can respond to the client as soon as the order is entered into the queue without waiting for it to be matched.
The fun part is matching orders once they are read from the queue. Let’s walk through what the matching engine does with an example:
Suppose these are the buy/sell order books for a particular stock:
And the following order is read from the queue: LIMIT SELL 12 at 94 - a limit sell order for 12 units at the price of 94 per unit.
The Matching Engine tries to match the order with orders already in the order book:
It checks the top of the buy order book. As 94 is less than 100, the engine can partially fill the sell order with the top buy at the price of 100 per unit. The sell order is for 12 units, so the remaining 2 units are matched from the second position in the buy book at 95.
When the transaction is finished, the updated order books look like this:
If part (or entirety) of the limit order book couldn’t be matched, the remainder would be added to the corresponding order book.
Order Book Design
The previous section highlighted the importance of having fast access to the best order in an order book. For this reason, I implemented my order books with heaps using Go’s built-in heap interface. Where they lag is retrieving top k elements, which is a necessary operation for normal exchanges that have to frequently publish order books.
There are likely customized data structures that perform better for order books. It would be fun to revisit this and benchmark a couple of implementations to see the impact on the system throughput. One advantage of heaps is that they generally have good cache locality.
Heaps also aren’t optimized to search for a specific element. My implementation does not support canceling or updating orders, so this is not a big concern. If I wanted fast order access, I’d likely start by adding an auxiliary hash map mapping from the order ID to the order book item.
Performance
In local benchmarks with 1000 clients, I’m getting a throughput of around 14000 orders per second on my 8th gen Intel 15W laptop CPU.
Conclusion
This was a fun project to learn about how matching engines and stock exchanges as a whole are designed. You can find my implementation on github.
If you have a background in trading systems, are there any resources you’d recommend to learn more about trading systems?