Order Book Phase 1

As our order book is a collection of bids and asks, let’s create a naive implementation:

#pragma once
#include <vector>
#include <cstdint>

class Order
{
    uint32_t id;
    uint32_t qty;
    double price;
};

class OrderBook
{
    std::vector<Order> bids;
    std::vector<Order> asks;
};

Ok, so there is the basics. But with plenty of issues.

Firstly, we will almost always be expecting those collections to be sorted. So rather than a vector, we should look at a sorted collection. And since it would probably be convenient to have them sorted so that NBBO is near the front, we’ll need a container where we can dictate the sorting order. What do we have in the standard library?

We have 4, and I’ll put them in 2 groups: set and multiset, map and multimap. All are O(log n) complexity.

The containers set and multiset are key storage. Map and multimap are key/value storage. Set and map require each storage object to be unique, multiset and multimap permit multiple entries with the same key.

Certainly, more than one order can be at the same price level. So we will need to decide. Do we change the container type to handle keys only, or do we make an intermediate object keyed on price levels that stores the collection of orders internally?

Let’s walk down the road of keys only. A common operation is to get all the orders at a price level. Using set would mean the key itself must hold a collection of orders. So we would ask the set for the key, and when the key was returned we would ask it for the internal collection of orders.

Using multiset would eliminate the need for the key to hold the collection of orders. We will still ask for the key. The response will be the first key, which we will then iterate through until we get to the next price level. Multisets also have the equal_range function, which provide iterators for the first and last element with the matching key.

Map is key/value storage. So if the order object itself had no key, we could create one and insert the order inside the collection with its associated (external) key. Of course, map does not allow duplicates. So since we want the key to be price, we would need to store the value as a collection of orders.

Multimap allows the key to be external and allows for duplicates. So we could store the price as the key, and there would be no need for the internal collection.

After analyzing all of this, it seems as if a multiset would work best. The key will be on price, and we expect multiple orders at the same price. We now need to think about ordering within the same price. How will that work? As with almost anything in software engineering, it depends.

A common inter-price sorting scheme is by the time the order is placed – FIFO. Looking at our case, the id could be sequential, and could be used as a proxy for time. But we’ll dig a bit deeper.

Time is not the only way order books work. There are many schemes for this. Some exchanges reward based on order size, business partnerships, or many other forms of arbitrary values. Should we plan for that here? Yes. We will use an external comparator to sort the values within a price level.

This also means we will have to revisit our choice of multiset. How does a multiset sort items with the same key? We don’t know. And we need that granular control to meet business requirements. What are our possible solutions?

• Option A: Make a complex key that is guaranteed to be unique and provide the desired ordering. We could then move to set. The downside is that iterating over that set will require us to handle the upper bound.
• Option B: Move to a map, and have the value be the collection within the price level sorted the way we like. This means the bounds while iterating is handled for us.

We will decide for option A. This has the (somewhat minor) advantage that if we are attempting to cross from one price to the next (i.e. filling an order that overlaps several price ranges) we can simply continue iterating.

Ok. How does that change our (still naive) order book?

#pragma once
#include <set>
#include <cstdint>

class Order
{
    public:
    uint32_t id;
    uint32_t qty;
    double price;

    friend bool operator<(const Order& a, const Order& b);
    friend bool operator>(const Order& a, const Order& b);
    friend bool operator==(const Order& a, const Order& b);
};

class OrderBook
{
    public:
    std::set<Order, std::greater<Order>> bids;
    std::set<Order, std::less<Order>> asks;
};

Not too different from the original. Getting all orders for a particular price level is a touch harder, but getting all “top of the book” orders for a range of prices up to a particular volume (another common operation) is somewhat easier. I feel this is a good tradeoff.

Now we are going to implement this, test it, and see just how much data we can throw at it.

You can see the project up to this point on GitHub. The next step in our journey is documented here.