A first project in Rust: in-memory order book

A first project to explore Rust: an in-memory order book.

Design

According to [https://www.chrisstucchio.com/blog/2012/hft_apology.html] an order book needs to be organized by price level first and then by arrival time. To simplify the order filling slightly, I've enforced that every order involved in a fill is above/below the requested limit for sells/buys. Presumably in practice you could still fill an order if the average fill price satisfied the requested limit.

We can have a separate order book per symbol as they are entirely independent and can be handled concurrently. A map can look up the respective order book for a given symbol in O(1) time. Each orderbook is a sorted vector of queues per price level, which gives us O(log(N)) to insert an order at an existing price level and finding a set of fulfilling orders takes O(N) time. Time complexity of filling an order depends on a few things:

1. The order price level distribution. The worst case is a single order per price level, yielding O(N * k) to fill where k is the number of orders on the other side of the trade required to fill. The best case is just a single queue at a one price level, yielding O(k).
2. How often we need to remove queues once orders a price level are drained because that results in a vector shift (O(N)).

Examples

RUST_BACKTRACE=1 RUST_LOG=debug cargo run curl -H "Content-Type: application/json" -d '{"price": 3, "side": "Sell", "amount": 5, "symbol": "AAPL"}' localhost:3000/order | jq { "id": "ef1c4f22-ff16-4b40-9c92-881b1f1db8ca", "amount": 5, "symbol": "AAPL", "price": 3, "side": "Sell" } curl -H "Content-Type: application/json" -d '{"price": 3, "side": "Sell", "amount": 5, "symbol": "AAPL"}' localhost:3000/order | jq { "id": "40bc6343-f2cf-486c-9dc6-8111ea3e69ac", "amount": 5, "symbol": "AAPL", "price": 3, "side": "Sell" } curl localhost:3000/sells | jq { "AAPL": [ [ { "id": "ef1c4f22-ff16-4b40-9c92-881b1f1db8ca", "amount": 5, "symbol": "AAPL", "price": 3, "side": "Sell" }, { "id": "40bc6343-f2cf-486c-9dc6-8111ea3e69ac", "amount": 5, "symbol": "AAPL", "price": 3, "side": "Sell" } ] ], "MSFT": [], "AMZN": [] } curl -H "Content-Type: application/json" -d '{"price": 3, "side": "Buy", "amount": 7, "symbol": "AAPL"}' localhost:3000/order | jq { "avg_price": 3 } curl localhost:3000/sells { "AMZN": [], "AAPL": [ [ { "id": "40bc6343-f2cf-486c-9dc6-8111ea3e69ac", "amount": 3, "symbol": "AAPL", "price": 3, "side": "Sell" } ] ], "MSFT": [] } 

Unit tests

RUST_BACKTRACE=1 cargo test -- --nocapture 

from Hacker News https://github.com/connorwstein/exchange