The Order Book
The problem
Chapter 2 of Trading Systems for Software Engineers described the order book as two sorted heaps. Time to build it.
The requirement: buyers' orders sorted so the highest bid is instantly available, sellers' sorted so the lowest ask is. Orders arrive and cancel constantly. You need "give me the best" plus "insert" plus "remove the best," all fast.
A sorted slice gives you O(1) best and O(n) insert, because everything after the insertion point shifts. With thousands of orders per second, that's too slow.
A binary heap gives you O(log n) insert, O(log n) remove-best, and O(1) peek-best.
The idea
A heap is a binary tree with one rule: every parent is smaller than its children (a min-heap). Not fully sorted - just enough ordering that the smallest is always at the top.
1
/ \
3 2
/ \ /
7 4 5Row two isn't sorted. Doesn't matter. The minimum is at the root, and that's the question we ask.
The clever part: you store it in a flat slice, with the tree structure implied by arithmetic.
index: 0 1 2 3 4 5
value: [1, 3, 2, 7, 4, 5]
for index i:
parent = (i-1)/2
left child = 2i+1
right child = 2i+2No pointers, no nodes, no allocation per element. Just index maths on a slice.
Building it
Two operations. When you add at the end and it's too small, sift up - swap with the parent until the rule holds. When you remove the root, move the last element to the top and sift down.
package main
import "fmt"
type Order struct {
ID int
Price float64
Quantity float64
}
// MinHeap keeps the lowest-priced order at the root. For bids,
// negate the prices (or flip the comparison) to get a max-heap.
type MinHeap struct {
orders []Order
}
func (h *MinHeap) Len() int { return len(h.orders) }
func (h *MinHeap) Peek() (Order, bool) {
if len(h.orders) == 0 {
return Order{}, false
}
return h.orders[0], true
}
func (h *MinHeap) Push(o Order) {
h.orders = append(h.orders, o)
h.siftUp(len(h.orders) - 1)
}
func (h *MinHeap) Pop() (Order, bool) {
if len(h.orders) == 0 {
return Order{}, false
}
top := h.orders[0]
last := len(h.orders) - 1
h.orders[0] = h.orders[last]
h.orders = h.orders[:last]
if len(h.orders) > 0 {
h.siftDown(0)
}
return top, true
}
func (h *MinHeap) siftUp(i int) {
for i > 0 {
parent := (i - 1) / 2
if h.orders[parent].Price <= h.orders[i].Price {
break
}
h.orders[parent], h.orders[i] = h.orders[i], h.orders[parent]
i = parent
}
}
func (h *MinHeap) siftDown(i int) {
n := len(h.orders)
for {
smallest := i
left, right := 2*i+1, 2*i+2
if left < n && h.orders[left].Price < h.orders[smallest].Price {
smallest = left
}
if right < n && h.orders[right].Price < h.orders[smallest].Price {
smallest = right
}
if smallest == i {
return
}
h.orders[i], h.orders[smallest] = h.orders[smallest], h.orders[i]
i = smallest
}
}Each sift walks one path from a node to the root or a leaf. A binary tree of n items is about log₂(n) deep, so both are O(log n). For a million orders that's 20 swaps.
See It Work: draw the tree, then check it
Print the shape after each insert:
func (h *MinHeap) Print() {
level, idx := 0, 0
for idx < len(h.orders) {
count := 1 << level // 1, 2, 4, 8 ...
fmt.Printf(" level %d: ", level)
for i := 0; i < count && idx < len(h.orders); i++ {
fmt.Printf("%.1f ", h.orders[idx].Price)
idx++
}
fmt.Println()
level++
}
}
// IsValid checks the heap property holds everywhere.
// Run it after every operation while you're learning.
func (h *MinHeap) IsValid() bool {
for i := 1; i < len(h.orders); i++ {
if h.orders[(i-1)/2].Price > h.orders[i].Price {
return false
}
}
return true
}
func main() {
h := &MinHeap{}
for _, p := range []float64{50, 30, 70, 10, 60, 20, 40} {
h.Push(Order{Price: p})
fmt.Printf("after inserting %.0f (valid: %t):\n", p, h.IsValid())
h.Print()
}
}after inserting 50 (valid: true):
level 0: 50.0
after inserting 30 (valid: true):
level 0: 30.0
level 1: 50.0
after inserting 70 (valid: true):
level 0: 30.0
level 1: 50.0 70.0
after inserting 10 (valid: true):
level 0: 10.0
level 1: 30.0 70.0
level 2: 50.0
...Watch 10 bubble from the bottom to the root, swapping past 50 then past 30. That's siftUp happening in front of you.
IsValid is worth keeping. An assertion that checks your data structure's invariant after every operation is the fastest way to find a bug in it - far faster than staring at output and wondering.
See It Work: heap versus sorted slice
func BenchmarkHeapInsert(b *testing.B) {
for i := 0; i < b.N; i++ {
h := &MinHeap{}
for j := 0; j < 10000; j++ {
h.Push(Order{Price: float64((j * 7919) % 10000)})
}
}
}
func BenchmarkSortedSliceInsert(b *testing.B) {
for i := 0; i < b.N; i++ {
var s []Order
for j := 0; j < 10000; j++ {
o := Order{Price: float64((j * 7919) % 10000)}
idx := sort.Search(len(s), func(k int) bool {
return s[k].Price >= o.Price
})
s = append(s, Order{})
copy(s[idx+1:], s[idx:])
s[idx] = o
}
}
}The sorted slice finds its position quickly - binary search, from Chapter 12 - and then pays O(n) to shift everything. The heap doesn't shift. Expect a large gap, and expect it to widen as you raise the count from 10,000 to 100,000.
(j * 7919) % 10000 produces a scattered rather than sequential order. 7919 is prime, which keeps it from landing in a pattern. Benchmarking an insert-sorted structure with already-sorted input flatters it enormously - a good general warning about benchmark inputs.
The standard library version
Go ships container/heap, which supplies the algorithms if you supply five methods. It's worth knowing, and it's worth having written your own first, because the interface makes very little sense until you've built the thing it abstracts.
A toy matching engine
Two heaps, and a rule:
type OrderBook struct {
bids *MaxHeap // highest price at the root
asks *MinHeap // lowest price at the root
}
type Fill struct {
BuyID, SellID int
Price float64
Quantity float64
}
func (ob *OrderBook) AddLimitBuy(o Order) []Fill {
var fills []Fill
for o.Quantity > 0 {
bestAsk, ok := ob.asks.Peek()
if !ok || bestAsk.Price > o.Price {
break // nothing to cross with
}
qty := math.Min(o.Quantity, bestAsk.Quantity)
fills = append(fills, Fill{
BuyID: o.ID, SellID: bestAsk.ID,
Price: bestAsk.Price, // the resting order sets the price
Quantity: qty,
})
o.Quantity -= qty
bestAsk.Quantity -= qty
ob.asks.Pop()
if bestAsk.Quantity > 0 {
ob.asks.Push(bestAsk) // partially filled, goes back
}
}
if o.Quantity > 0 {
ob.bids.Push(o) // remainder rests on the book
}
return fills
}That is, in outline, what every exchange does several million times a second. The real thing adds time priority within a price level, order types, self-trade prevention, and a great deal of care about correctness - but the shape is this.
Note Price: bestAsk.Price. The resting order's price is the trade price, and the incoming aggressor takes it. That's price-time priority, and it's why posting a limit order and waiting is different from crossing the spread - the distinction Chapter 3 of the other book spends pages on.
Exercises
13.1 Write MaxHeap by flipping the comparisons in MinHeap. Then reflect: could you have avoided duplicating the code? (Generics are the answer, and looking them up here is a good use of an hour.)
13.2 Add Remove(id int) to cancel a resting order. Find it, swap the last element in, then sift - you may need to sift either direction. Verify with IsValid() after every removal.
13.3 Instrument Push to count swaps. Insert 1,000,000 orders and print the average. Compare to log₂(1000000).
13.4 Build the two-sided OrderBook and feed it a stream of random buys and sells. Print the resulting fills and the book state after each. Confirm the spread never inverts - the best bid must never exceed the best ask.
13.5 Benchmark heap versus sorted-slice insert at 1,000 / 10,000 / 100,000. Plot or tabulate. Then rerun with sorted input and explain why the sorted slice suddenly looks much better.
13.6 Harder. Add time priority: when two orders share a price, the one that arrived first fills first. Add a sequence number and use it as a tiebreak in the comparison.
13.7 Harder still. Use your order book to replay a real trade file and reconstruct the best bid and offer over time. Compare against the quoted spread if your data has one.
Solutions
13.1 Change <= to >= in siftUp and < to > in siftDown. Generics let you write it once with a comparison function - this is exactly the problem they exist for.
13.2
func (h *MinHeap) Remove(id int) bool {
for i, o := range h.orders {
if o.ID != id {
continue
}
last := len(h.orders) - 1
h.orders[i] = h.orders[last]
h.orders = h.orders[:last]
if i < len(h.orders) {
h.siftDown(i)
h.siftUp(i) // may need to go either way
}
return true
}
return false
}Finding the order is O(n) - heaps aren't built for lookup by ID. Real books keep a separate map from ID to position, which is Chapter 9 and Chapter 13 working together.
13.3 Average swaps per insert comes out around 1-2, well below log₂(1000000) ≈ 20. The worst case is 20; the average is much better, because most inserted values don't belong near the root. Worst case and average case are different questions, and this is a clean demonstration of why.
13.5 With sorted input the insertion point is always at the end, so nothing shifts and the sorted slice is O(1) per insert. Benchmark inputs that accidentally match your structure's best case are one of the commonest ways to draw a wrong conclusion from a benchmark.