Photo by Chris Liverani on Unsplash

Background & Context⌗

As an exercise in systems design, I tackled the order matching problem from first principles in Go. This post covers some of the different paths explored and the tradeoffs they made, as well as the decision of what was ultimately decided as the best approach. Developer exprience and performance are considered in the post as we dive in to the inner-workings of an asset exchange.

Orderbook structure⌗

Order matching really boils down to efficient price navigation and memory access. You have an order, you need to match it to other orders based on its price, but if you don’t have any orders, you can run into nil pointers. Binary trees are the most effective way I’ve found of solving this problem, because you can efficiently iterate in the direction of your desired price movement until you exhaust options. This reveals fewer places for nil pointer errors or other panics.

One version of the orderbook (verison 4 I think, need to confirm) organized orders by map[uint64][]Order but that turned out to be horrendously difficult to navigate because maps are unordered in Go. On one hand, the map[Price][]Order approach was more memory efficient because random access memory is not O(1) efficient, thus theoretically pointer lookups from the binary tree implementation would be slightly slower than sequential map or slice access times.

But in using a map for storing orders, the traversal logic became difficult and the best way to solve that was to create a price index as a spine against the map that holds the order lists anyway. The additional complexity wasn’t worth it if it required taking the same hit in price navigation. Instead, treating the binary tree as the core structure holding the order lists was simpler and easier to navigate the book, while providing a decent memory efficiency. If you exhaust a list of orders at a given price, you just recursively search in the acceptable direction of your order. Failure to do so and you just attempt again, recursively searching until you find a fill or the order expires.

The first part of this series discussed how the buy and sell orders should be separated on the actual books for easier traversal. After pulling it out, it was indeed easier to handle the matching of orders. You basically keep the two trees up against each other and just pick the first order of each side at a given price and then the tree will handle the traversal up or down until it finds an appropriate match.

Traversing the map structure looked like this:

// findLowest recursively searches for the lowest price in the map.
// It returns the index of the order, the order, and an error if anything went wrong.
func (o *orderbook) findLowest(price Price, side bool) (int64, *order, error) {
	o.Lock()
	defer o.Unlock()

	if side {
		buyable, ok := o.buy[price]
		if !ok {
			if price == 0 {
				return -1, nil, fmt.Errorf("ErrNotFound")
			}
			// recursively search for next lowest price.
			nextLowest := price - 1
			return o.findLowest(nextLowest, side)
		}
		if len(buyable) == 0 {
			return -1, nil, fmt.Errorf("ErrNotFound")
		}

		return int64(0), buyable[0], nil
	}

	sellable, ok := o.sell[price]
	if !ok {
		if price == 0 {
			return -1, nil, fmt.Errorf("ErrNotFound")
		}
		nextLowest := price - 1
		return o.findLowest(nextLowest, side)
	}
	if len(sellable) == 0 {
		return -1, nil, fmt.Errorf("ErrNotFound")
	}

	return int64(0), sellable[0], nil
}

findLowest is a recursive function that searches for an acceptable price. As you can see, it takes a naive approach that simply subtracts 1 and tries that price. It’s inefficient as all hell, and it’s a direct result of having no binary tree. Bolting one one, we’d still be at the mercy of the binary tree lookups.

Another Option⌗

Like stated above, if we maintain two sorted lists, it solves the problem of price traversal and makes memory access simpler. It does require a slight architectural and ownership change, but it is performant enough that it blew me away in Go on my local machine. Additionally, it is naturally inclined to the channel pattern and embraces the ownership benefits from it.

Life On The High Concurrency Seas⌗

The orderbook is at its essence a highly asynchronous system - it is not only common but expected that you will have orders on the books for months and years. Thus solving the asynchronous problem upfront was a key design choice made on subsequent iterations.

The first iteration was lock-heavy and deadlock prone because of it. Handling message passing with channels and wrapping access to the tree in a worker pattern for handling fills ended up being the most ergonomic solution found. Go’s wisdom of sharing memory by communicating with channels is crucial to staying sane with concurrency. No other patterns were found that were as simple to use as proper wrapping of functions to expose or limit parts of the system.

When you bake in that concurrency handling from the start, you automatically must think of the order lifecycle just to write the tests in the first place. I’ve used channels before, extensively even, but this exercise made a fundamental part of their utility “click” for me. The worker pattern is really about abstracting ownership and of the data structure you wrap it around, while also taking efficient advantage of available CPU cores. You can completely hide the access of a variable behind channels, such that it literally cannot be accessed outside the package or even outside of a given function when done correctly. It has this in common with some functional programming paradigms. Function scope can be tightly controlled to expertly carve out ownership of a highly sensitive piece of memory like the books.

Isolation & Boundaries⌗

All 5 versions of the orderbook written were isolated in packages, so the only thing each version had consistent access to was the pkg/accounts package. That meant that accounts were a common factor in all variations and likely influenced the design of components in its own way. However, the Account model was its own interesting exercise in code reuse in this project. Writing the same code in 5 different ways for the orderbook meant that I wrote 5 different ways of managing balances through an order matching engine with the account package, too.

Buy & Sell Order Separation⌗

The first version had buy and sell orders in the same lists by price and iterated until it found a match. A naive approach, in retrospect, but exactly the type of learning hoped for in this experiment. That was when the binary tree became a necessary bolt-on. Once they were separated, though, matching logic became far simpler. It was a matter of just keeping two sides of the tree. When they were all in the same list, it was a complicated set of control flow decisions. This separation was best handled by the data structure, not by the business logic.

Interface Discovery⌗

In this case, the core components are the buy and sell lists, the account balances, and the order filler. They work together to fulfill the lifecycle of an order in the system. An order cannot be placed unless the user has the necessary balance to afford the purchase. If they do, the order is placed into the books, where the filler starts work on it. How these are formed and shaped is up for debate, but boiled down to this

The wisdom of this phrase is that you’re not designing them upfront, which exposes you to the risk of premature optimization. For example, v3 had only a push and fill method for interacting with the book. Orders would alert on their own signal channel when they were filled, and status updates were passed as a read only mechanism for updating a global state. This was a repeating theme in these interfaces, I found - the books are a pure black box. you should only be able to see a screen. Nothing else. You feed orders in and it processes everything.

// pkg/v3/v3.go
//
// Orderbook defines the interface that must be fulfilled by an exchange.
// This is the work in progress and interface may yet change.
type Orderbook interface {
	//  Push inserts the order into our books and immediately starts attempting to fill it.
	Push(o *order) error
	// Fill is called as a goroutine and sends on out when the order is completed.
	// It sends OrderUpdates on status whenever updates to the order occur.
	Fill(o *order, out chan<- *order, status chan<- OrderUpdate)
}

Compare that against v1, which separated order filling as its own responsibility and cycle, distinct from placing and canceling orders.

// pkg/v1/v1.go
//
// Market defines the most outer API for our books.
type Market interface {
	Name() string
	Orderbook() ([]Order, error)
	Place(order Order) (Order, error)
	Cancel(orderID string) error
}

// Filler is concurrently called passing the order and a context
// and is meant to handle the order from start to finish.
type Filler interface {
	Fill(ctx context.Context, o Order)
}

Playing around with the interface for interacting with the book revealed its true forms. It wants to be a blackbox. You feed it in an order slip, and it has an outbox that it spits orders into, filled or cancelled or errored.

Orders⌗

Orders are the central unit of an orderbook. Exploration around various book structures revealed that it was best to define a concrete struct, separate the buy and sell orders on that struct, and let the interface focus on the lifecycle of the order.

// pkg/v2/v2.go
//
// Order holds a second approach at the Order interface
// that incorporates lessons learned from the first time around.
type Order interface {
	OwnerID() string
	ID() string
	Price() int64
	Side() string
	Open() uint64

	// Fill adds a transaction that ties a Transaction event to an Account.
	Fill(tx *Transaction) ([]*Transaction, error)
	History() []*Transaction
}

// Transaction the data for a trade.
type Transaction struct {
	AccountID string // who filled the order
	Quantity  uint64 // The amount they filled it for
	Price     uint64 // The price they paid
	Total     uint64 // The total of the Transaction.
}

The v2 Order interface embedded the Fill operation and combined it with the concepts of a Transaction. This populated a set of transactions, aka fill events, onto an order. Then, the History method returned that list of transactions.

Fill returned the set of transactions and an error when the order was filled, and it was meant to be a blocking function, passing concurrency control off to its user. Ultimately, it was better to keep the book like a mysterious machine. You put orders in, you get orders out. Fills were better abstracted out to the orderbook as a whole rather than focused around the order, since they need access to all three at runtime (the fill order, the book order, and the filler function).

Order Matching⌗

Another opportunity for an interface that some versions used and some didn’t is the order matching functionality. Some versions left this up to the filling function, others made it a part of the interface for the orderbook itself. Order matching is really an implementation detail, as it’s just part of the filling process, depending on how your engine decides to look at it. I think ultimately, treating it as an implementation detail and abstracting it out into the filler interface is probably the right call.

// pkg/v1 Match function 
func (t *TreeNode) Match(fillOrder Order, cb func(bookOrder Order)) { ... }

// pkg/v2 Match function 
func (o *Orderbook) Match(buyOrder Order) (Order, error){ ... }

The v1 version uses a callback pattern, while the v2 version simply returns a matching order or an error. The callback pattern was convenient, but it’s on the binary tree, and the other one is on the book itself. One must examine the data structure and access patterns of the component they’re designing before judging if a callback or a return value (or some other option) is the right choice for finding matching orders.

Order matching in this experiment is actually pretty easy once you get the data structures and the interface aligned. It’s simply a matter of keeping the buy and sell side books aligned at their current price.

The order matcher needs to look higher or lower, depending on what side of the book it’s traversing, and it needs to peek to the next list of orders in the direction (cheaper or more expensive) that it’s searching until it fails, then it should return it’s current location’s highest time priority order. In our case this is whatever order is at index 0 because orders are always appended to this list.

This is just to match two appropriate orders together, though. The next step is to actually fill the orders. Filling involves updating account balances, updating order fill counts, and removing the orders from the tree if they’re fully filled.

Current Price⌗

So far, the orderbook has no concept of the current market price of an asset in the book. There are a few different ways to go about this, but let’s examine it from first principles.

First, what is the price of an asset? By definition, it’s whatever people are willing to pay for it. But that definition gets blurry when you have thousands of people willing to pay a series of prices across a given range. What would make sense to consider the “current market price” then? A rolling average strikes me as the first best option here.

The orderbook currently pumps all matches out to a channel for handling and balance transfers according to the match. Our market price algorithm could hook into that channel after they’ve been actually paid for and record the price. That series of prices could then be summed and averaged to provide the current ‘rolling average’ price. It could either account for all time or even be a rolling average of the last X orders.

Another approach could simply be to consider the last price sold as the current price. This approach is more naive but is also simpler: The book only tracks the last order price for each sale, which is faster and more memory efficient.

Next Steps⌗

There is currently no persistence layer to the application so it all happens in memory and disappears when the server stops. Adding a KV store interface and implementing badgerDB or SQLite through that interface should be a performant solution. I also want to experiment with opening this up to the public as a sort of experiment. Giving everyone a set amount of token and then letting them file real trades with their fake balances would be an interesting experiment to get real production data into this application. Plus, it would be cool to analyze that data and have a leaderboard of best performing trades across all accounts.