Lobster

A fast in-memory limit order book (LOB).

Quickstart

To use Lobster, create an order book instance with default parameters, and send orders for execution:

use lobster::{FillMetadata, OrderBook, OrderEvent, OrderType, Side};

let mut ob = OrderBook::default();
let event = ob.execute(OrderType::Market { id: 0, qty: 1, side: Side::Bid });
assert_eq!(event, OrderEvent::Unfilled { id: 0 });

let event = ob.execute(OrderType::Limit { id: 1, price: 120, qty: 3, side: Side::Ask });
assert_eq!(event, OrderEvent::Placed { id: 1 });

let event = ob.execute(OrderType::Market { id: 2, qty: 4, side: Side::Bid });
assert_eq!(
    event,
    OrderEvent::PartiallyFilled {
        id: 2,
        filled_qty: 3,
        fills: vec![
            FillMetadata {
                order_1: 2,
                order_2: 1,
                qty: 3,
                price: 120,
                taker_side: Side::Bid,
                total_fill: true,
            }
        ],
    },
);

Lobster only deals in integer price points and quantities. Prices and quantities are represented as unsigned 64-bit integers. If the traded instrument supports fractional prices and quantities, the conversion needs to be handled by the user. At this time, Lobster does not support negative prices.

More information can be found in the documentation.

Quantcup

The winning quantcup submission is at the moment up to 10x faster than Lobster. While Lobster can surely be improved significantly, some design choices by necessity make it slower. Here's a non-exhaustive list:

1. The Quantcup solution holds all the possible price points in memory, whereas Lobster uses two BTreeMap structs that hold price points on demand. The performance boost of holding all the price points in a contiguous data structure on the stack is massive, but it's not very practical: the array is indexed by the price, so it can be huge (imagine implementing an order book for forex markets with integer price points at all non-fractional values); in reality limit orders can be made at any price, and in most markets there is no upper bound, so the static array solution is not viable.

2. The Quantcup solution does not update the max bid/min ask values when canceling orders. So if an order at the best bid/ask is canceled, that solution will not be correct. To be fair, this is pretty trivial to fix, but nonetheless it wasn't done in the benchmarked winning solution.

3. The Quantcup solution does not accept external order IDs; instead it provides them as integer indices from a static array. This has obvious practical consequences: the order book can handle a maximum number of open orders, and that number is chosen at compile time. Furthermore, if order IDs are not known to the sender before executing the order, it's difficult to broadcast the events to the right sender. Lobster supports unsigned 128-bit integers as order IDs, which can thus contain v4 UUIDs.

Todo

1. Remove OrderBook::update_min_ask and OrderBook::update_max_bid and instead update the min ask/max bid values only when needed. Currently those methods are called on every order execution, and flamegraph analysis confirms that they are the main bottleneck.
2. Experiment with replacing BTreeMaps with Trie from qp_trie.

Logo made by turkkub from www.flaticon.com.