Ben Homnick

Building an exchange limit order book in Go

Ben Homnick -

With all of the hype around cryptocurrency trading I thought it might be fun to take a look at what it takes to build an exchange order book. It's been a while since I've worked on a Go project, so it seemed like a good choice for a refresher.

For this project, I wanted my basic exchange to:

  • Support adding, canceling, and executing buy/sell orders
  • Execute all operations in as close to O(1) as possible
  • Be durable and recoverable in the event of failure

I never got around to implementing the third, but I'll talk about the basic operations and performance in more detail below, along with some ideas for improvements. The project source is available on GitHub.

Under the hood

There are 3 data models worth looking at:

type PricePoint struct {
    orderHead *Order
    orderTail *Order
}

Each PricePoint represents a discreet limit price. For products that need to be priced at higher precision this might not be a scalable solution, but for this exercise I'm going to assume whatever we're trading is priced in USD, so 8 or 9 digits is the max we'll need and can easily be handled in memory. Each PricePoint just contains pointers to the first and last order entered at that price for ease of executing and appending new orders.

type Order struct {
    id uint64
    isBuy bool
    price uint32
    amount uint32
    status OrderStatus
    next *Order
}

Each Order is either a buy or sell, has a limit price and amount, and a status that lets us know whether the order is open, partially filled, filled, etc. This value isn't actually used by the exchange as you'll see below, but it might be useful to report to trader clients. Lastly, each order is linked to the next order at the same price point so we can ensure orders are examined in the order they are entered.

type OrderBook struct {
    ask uint32
    bid uint32
    orderIndex map[uint64]*Order
    prices [MAX_PRICE]*PricePoint
    actions chan<- *Action
}

The OrderBook does most of the heavy lifting by keeping track of the current maximum bid and minimum ask, an index mapping order IDs to pointers so we can easily cancel outstanding orders, an array of all possible price points, as well as a channel to report actions (fills, cancellations, etc.) to some handler as they occur.

Adding orders

Inserting a new order into the book is just a matter of appending it to the list of orders at its price point, updating the order book's bid or ask if necessary, and adding an entry in the order index. These are all O(1).

func (ob *OrderBook) openOrder(o *Order) {
    pp := ob.prices[o.price]
    pp.Insert(o)
    o.status = OS_OPEN
    if o.isBuy && o.price > ob.bid {
        ob.bid = o.price
    } else if !o.isBuy && o.price < ob.ask {
        ob.ask = o.price
    }
    ob.orderIndex[o.id] = o
}

Canceling orders

Canceling is done by looking up the order by ID from the index and setting the amount to 0, also O(1). We don't actually need to remove the order from the book, just ignore it.

func (ob *OrderBook) CancelOrder(id uint64) {
    if o, ok := ob.orderIndex[id]; ok {
        o.amount = 0
        o.status = OS_CANCELLED
    }
    ob.actions <- NewCancelledAction(id)
}

Filling orders

Filling orders in the case of a sell is done by starting at the max bid and iterating over all open orders until we either fill the order or exhaust the open orders at that price point. Then we move down to the next price point and repeat.

func (ob *OrderBook) FillSell(o *Order) {
    for ob.bid >= o.price && o.amount > 0 {
        pp := ob.prices[ob.bid]
        ppOrderHead := pp.orderHead
        for ppOrderHead != nil {
            ob.fill(o, ppOrderHead)
            ppOrderHead = ppOrderHead.next
            pp.orderHead = ppOrderHead
        }
        ob.bid--
    }
}

func (ob *OrderBook) fill(o, ppOrderHead *Order) {
    if ppOrderHead.amount >= o.amount {
        ob.actions <- NewFilledAction(o, ppOrderHead)
        ppOrderHead.amount -= o.amount
        o.amount = 0
        o.status = OS_FILLED
        return
    } else {
        if ppOrderHead.amount > 0 {
            ob.actions <- NewPartialFilledAction(o, ppOrderHead)
            o.amount -= ppOrderHead.amount
            o.status = OS_PARTIAL
            ppOrderHead.amount = 0
        }
    }
}

Buys happen in the exact same way, except starting at the maximum ask and working our way up.

It's interesting to note bid and ask here don't necessarily indicate where open orders are, but rather are starting points for examining potential order pairs. This is what lets us do cancellations without having to manipulate a price point's list of orders. While attempting to fill an order we just ignore orders remaining in the book with an amount of 0.

The performance of fills depends on how sparse the order book is at the time. In the worst case we'd need to iterate over every price point, however as the number of orders in the book increases the number of price points we need to examine approaches 1. All of the other operations are constant time so this can also be done in O(1).

Performance

Testing performance of the system was done by pre-generating large numbers of random orders, varying the number of orders, mean and standard deviation of price, and maximum amount. The number of actions per second was then timed under different configurations.

func TestPerf(t *testing.T) {
    // nOrders, priceMean, priceStd, maxAmount
    doPerfTest(10000, 5000, 10, 50)
    doPerfTest(10000, 5000, 1000, 5000)
    doPerfTest(100000, 5000, 10, 50)
    doPerfTest(100000, 5000, 1000, 5000)
    doPerfTest(1000000, 5000, 10, 50)
    doPerfTest(1000000, 5000, 1000, 5000)
}

$ go test
Handled 16533 actions in 14.846866ms at 1113568 actions/second.
Handled 16597 actions in 17.971637ms at 923510 actions/second.
Handled 165584 actions in 78.475638ms at 2110005 actions/second.
Handled 165867 actions in 465.881034ms at 356028 actions/second.
Handled 1656289 actions in 1.406557785s at 1177547 actions/second.
Handled 1658457 actions in 2.548383913s at 650787 actions/second.
PASS
ok  	_/Users/bhomnick/Projects/bexchange	9.069s

Increasing the sparsity of the order book by widening the standard deviation and range of possible prices as expected has a significant effect on the number of actions that can be handled, however even in non-optimal cases we're still looking at more than 350k actions per second on a 2015 Mac. For reference NASDAQ handles over 60k messages per second.

This is of course a minimum feature set and lacking any durability or persistence, where I'd expect bottlenecks to occur.

Next steps

While a fun exercise, this order book isn't much use without an interface for trading clients. The next step would be to set up some kind of interface to serialize order book writes and reads and allow clients to manipulate orders. A web interface and WebSocket server might be a good follow-up project.

The other item I mentioned earlier was durability. Writing actions ahead to disk with something like Kafka would allow rebuilding of the order book state in the event of a crash. This would also be a good place to decouple the trade settlement process and reporting from the exchange engine. The original project was done with this vaguely in mind by supporting pluggable action handlers. If you're curious check out the code on GitHub.