How to Build a Trading Engine

In my last article I wrote about how you can build an Ethereum Wallet Manager using nodejs, watch for incoming deposits and execute withdrawals.

I wanted to continue with showing you how to build a similar wallet using Bitcoin, but I had the opportunity to work on the trading engine for the exchange instead and I am super excited to share what I learned out of that experience.

What is a matching engine?

A matching or trading engine is a piece of software that keeps a record of all open orders in a market and generates new trades if the two orders can be fulfilled by each other.

To think about it in other terms: if you have a market where users can sell Ether for Bitcoin, you want to keep track of things like what is the current buy/sell price of Ether in Bitcoins, what buy or sell orders remain unfilled and allow processing of new orders.

Scale this up to multiple market pairs and integrate the wallet managers from our other articles and you have a full exchange engine that you can use to build a complete exchange like Binance.com

Vocabulary

So how do you get started with building a matching engine?

First, you need to understand all the concepts involved and what each type of order does, so let's take them one by one.

Matching/Trading Engine

As detailed above, the matching engine is the piece of software that we want to build. And like any useful piece of software, it has some inputs and outputs.

In this case, we take some commands as inputs and generate events as outputs.

The possible commands can be:

• NewOrder: adds a new order in the order book and tries to match it against existing orders.
• CancelOrder: cancels an order if it is still open in the orderbook.

Other commands can also be defined, but for simplicity let's discuss only these two for now.

The events which can be generated are related to how the commands above have been executed:

• TradesGenerated: contains the list of trades that were generated by a given order pair.
• OrderCancelled: signals an order has been canceled before it was fully filled.

Order Book

The order book is a list of buy or sell orders sorted by price and timestamp.

When a new order is received, it is checked against the other side of the market (for a new buy order we check the sell orders) to see if there are any orders matching the conditions imposed by the new order.

If this is the case, then we generate trades between the orders until the conditions are invalidated or until the order is filled.

Orders

In any trading engine there can be multiple types of orders the end user has access to.

Some of these include:

• Limit order
• Market order
• Stop order.

Optionally, you can also add extra conditions that affect when an order should enter/exit a market using conditions and duration. But these will not be discussed here as they represent more advanced topics.

Limit Order

Limit orders are the most commonly used orders in the current crypto exchange environment.

They allow you to create an order with a specific price that gets filled either at the specified price better.

For a buy order, this means that if I place a buy order at the price of $100, it will get filled at any price bellow or equal to $100. As a sell order it will instead get filled at an amount above or equal to $100.

Market Order

Market orders prioritize completing the order for the specified amount ignoring the price completely. They have a priority in the order book and they guarantee fulfillment in markets with sufficient liquidity.

For example, when you place a buy 2 Ether order it can get executed at $900, $1000, $2000 or any other price depending on the current open orders in the market. Market orders are limited only by the number of funds the user has and the amount of assets he wants to buy/sell.

Stop Order

Stop orders become active only after a specific price level is reached. In this way they act in the opposite direction as the limit orders. Once they are activated they are automatically converted to a market or limit order.

There are a few other notions that you need to understand if you want to build a more advanced exchange, like liquidity, long/short trades, FIX/FAST protocols and a bunch of others, but I will leave that for you to discover.

Architecture

As you can see above, our system will consist of multiple clients of our engine. They can be other components of an exchange that receives order requests from the end users, validates them against their available funds and sends them for processing.

The communication between clients and engine is done through topics in Apache Kafka. One for each currency pair. This way we ensure that when an order is accepted in the message queue, it will be processed in that same order by the engine as well.
This creates a traceable system that we can reiterate over to recreate the order book if something craches or if we need to restart the engine.

The engines job in this case would be to listen on the Kafka command topic, execute the command on the order book and publish the result on the events topic.

It would also be cool to have some kind of monitoring service that tells us how fast do we process orders and generate trades, what the load is on the engine or on the entire system.

For that a great solution is to use Prometheus and Grafana. Prometheus will help us get metrics from our application and grafana will display all of them in an easy to understand dashboard.

Language choices

Depending on what programming languages you are familiar with you can pick whatever works best for you. The matching engine relies heavily on processing power to match the trades and calculate the new amounts for each matched order.

Therefore, you should pick language which is as low level as possible: C/C++, Golang, Rust and Java are some of the languages that come in mind here.

For this tutorial we will work with Golang, mainly because it's very fast, easy to understand, has simple concurrency and I haven't done C++ in a while :).

How to build a trading engine

Basic types

Let's first create some basic types to work with. We need an Order type, an OrderBook and a Trade type for starters.

engine/order.go

package engine

import "encoding/json"

type Order struct {
	Amount uint64 `json:"amount"`
	Price  uint64 `json:"price"`
	ID     string `json:"id"`
	Side   int8   `json:"side"`
}

func (order *Order) FromJSON(msg []byte) error {
	return json.Unmarshal(msg, order)
}

func (order *Order) ToJSON() []byte {
	str, _ := json.Marshal(order)
	return str
}

Here we just create a new structure that holds our most important properties for an order and we add an easy way of converting it to/from JSON.

We do something very similar for the trade type:

engine/trade.go

package engine

import "encoding/json"

type Trade struct {
	TakerOrderID string `json:"taker_order_id"`
	MakerOrderID string `json:"maker_order_id"`
	Amount       uint64 `json:"amount"`
	Price        uint64 `json:"price"`
}

func (trade *Trade) FromJSON(msg []byte) error {
	return json.Unmarshal(msg, trade)
}

func (trade *Trade) ToJSON() []byte {
	str, _ := json.Marshal(trade)
	return str
}

Great! We now have our basic input and output types. Let's see what the order book looks like.

engine/order_book.go

package engine

// OrderBook type
type OrderBook struct {
	BuyOrders  []Order
	SellOrders []Order
}

// Add a buy order to the order book
func (book *OrderBook) addBuyOrder(order Order) {
	n := len(book.BuyOrders)
	var i int
	for i := n - 1; i >= 0; i-- {
		buyOrder := book.BuyOrders[i]
		if buyOrder.Price < order.Price {
			break
		}
	}
	if i == n-1 {
		book.BuyOrders = append(book.BuyOrders, order)
	} else {
		copy(book.BuyOrders[i+1:], book.BuyOrders[i:])
		book.BuyOrders[i] = order
	}
}

// Add a sell order to the order book
func (book *OrderBook) addSellOrder(order Order) {
	n := len(book.SellOrders)
	var i int
	for i := n - 1; i >= 0; i-- {
		sellOrder := book.SellOrders[i]
		if sellOrder.Price > order.Price {
			break
		}
	}
	if i == n-1 {
		book.SellOrders = append(book.SellOrders, order)
	} else {
		copy(book.SellOrders[i+1:], book.SellOrders[i:])
		book.SellOrders[i] = order
	}
}

// Remove a buy order from the order book at a given index
func (book *OrderBook) removeBuyOrder(index int) {
	book.BuyOrders = append(book.BuyOrders[:index], book.BuyOrders[index+1:]...)
}

// Remove a sell order from the order book at a given index
func (book *OrderBook) removeSellOrder(index int) {
	book.SellOrders = append(book.SellOrders[:index], book.SellOrders[index+1:]...)
}

In the order book - apart from creating the support to hold the list of buy/sell orders - we also need to define how orders are added to these arrays.

Each list of orders should first be sorted in ascending or descending order based on the type of the contained order. Sell orders are sorted descendently so that the element with the highest index in the array has the lowest price and buy orders are sorted in ascending order so that the last element of the array has the highest price.

Since most trades should happen at the market price we can easily insert/remove from these arrays.

Let's finally process some orders.

In the following code we will add a method of processing limit orders.

engine/order_book_limit_order.go

package engine

// Process an order and return the trades generated before adding the remaining amount to the market
func (book *OrderBook) Process(order Order) []Trade {
	if order.Side == 1 {
		return book.processLimitBuy(order)
	}
	return book.processLimitSell(order)
}

// Process a limit buy order
func (book *OrderBook) processLimitBuy(order Order) []Trade {
	trades := make([]Trade, 0, 1)
	n := len(book.SellOrders)
	// check if we have at least one matching order
	if n != 0 || book.SellOrders[n-1].Price <= order.Price {
		// traverse all orders that match
		for i := n - 1; i >= 0; i-- {
			sellOrder := book.SellOrders[i]
			if sellOrder.Price > order.Price {
				break
			}
			// fill the entire order
			if sellOrder.Amount >= order.Amount {
				trades = append(trades, Trade{order.ID, sellOrder.ID, order.Amount, sellOrder.Price})
				sellOrder.Amount -= order.Amount
				if sellOrder.Amount == 0 {
					book.removeSellOrder(i)
				}
				return trades
			}
			// fill a partial order and continue
			if sellOrder.Amount < order.Amount {
				trades = append(trades, Trade{order.ID, sellOrder.ID, sellOrder.Amount, sellOrder.Price})
				order.Amount -= sellOrder.Amount
				book.removeSellOrder(i)
				continue
			}
		}
	}
	// finally add the remaining order to the list
	book.addBuyOrder(order)
	return trades
}

// Process a limit sell order
func (book *OrderBook) processLimitSell(order Order) []Trade {
	trades := make([]Trade, 0, 1)
	n := len(book.BuyOrders)
	// check if we have at least one matching order
	if n != 0 || book.BuyOrders[n-1].Price >= order.Price {
		// traverse all orders that match
		for i := n - 1; i >= 0; i-- {
			buyOrder := book.BuyOrders[i]
			if buyOrder.Price < order.Price {
				break
			}
			// fill the entire order
			if buyOrder.Amount >= order.Amount {
				trades = append(trades, Trade{order.ID, buyOrder.ID, order.Amount, buyOrder.Price})
				buyOrder.Amount -= order.Amount
				if buyOrder.Amount == 0 {
					book.removeBuyOrder(i)
				}
				return trades
			}
			// fill a partial order and continue
			if buyOrder.Amount < order.Amount {
				trades = append(trades, Trade{order.ID, buyOrder.ID, buyOrder.Amount, buyOrder.Price})
				order.Amount -= buyOrder.Amount
				book.removeBuyOrder(i)
				continue
			}
		}
	}
	// finally add the remaining order to the list
	book.addSellOrder(order)
	return trades
}

It seems like one method turned into two, one for buy orders and one for sell orders. They are very similar in every regard except side of the market the operate on.

The algorithm is very simple. We match a buy order with any sell order that lists sells at a price higher or equal to the price of our order. When this condition is no longer valid or the order is fully filled, we return the trades matched.

We're nearly done with our trading engine. We just need to connect to the Apache Kafka server and start listening for orders.

main.go

package main

import (
	"engine/engine"
	"log"

	"github.com/Shopify/sarama"
	cluster "github.com/bsm/sarama-cluster"
)

func main() {

	// create the consumer and listen for new order messages
	consumer := createConsumer()

	// create the producer of trade messages
	producer := createProducer()

	// create the order book
	book := engine.OrderBook{
		BuyOrders:  make([]engine.Order, 0, 100),
		SellOrders: make([]engine.Order, 0, 100),
	}

	// create a signal channel to know when we are done
	done := make(chan bool)

	// start processing orders
	go func() {
		for msg := range consumer.Messages() {
			var order engine.Order
			// decode the message
			order.FromJSON(msg.Value)
			// process the order
			trades := book.Process(order)
			// send trades to message queue
			for _, trade := range trades {
				rawTrade := trade.ToJSON()
				producer.Input() <- &sarama.ProducerMessage{
					Topic: "trades",
					Value: sarama.ByteEncoder(rawTrade),
				}
			}
			// mark the message as processed
			consumer.MarkOffset(msg, "")
		}
		done <- true
	}()

	// wait until we are done
	<-done
}

//
// Create the consumer
//

func createConsumer() *cluster.Consumer {
	// define our configuration to the cluster
	config := cluster.NewConfig()
	config.Consumer.Return.Errors = false
	config.Group.Return.Notifications = false
	config.Consumer.Offsets.Initial = sarama.OffsetOldest

	// create the consumer
	consumer, err := cluster.NewConsumer([]string{"127.0.0.1:9092"}, "myconsumer", []string{"orders"}, config)
	if err != nil {
		log.Fatal("Unable to connect consumer to kafka cluster")
	}
	go handleErrors(consumer)
	go handleNotifications(consumer)
	return consumer
}

func handleErrors(consumer *cluster.Consumer) {
	for err := range consumer.Errors() {
		log.Printf("Error: %s\n", err.Error())
	}
}

func handleNotifications(consumer *cluster.Consumer) {
	for ntf := range consumer.Notifications() {
		log.Printf("Rebalanced: %+v\n", ntf)
	}
}

//
// Create the producer
//

func createProducer() sarama.AsyncProducer {
	config := sarama.NewConfig()
	config.Producer.Return.Successes = false
	config.Producer.Return.Errors = true
	config.Producer.RequiredAcks = sarama.WaitForAll
	producer, err := sarama.NewAsyncProducer([]string{"127.0.0.1:9092"}, config)
	if err != nil {
		log.Fatal("Unable to connect producer to kafka server")
	}
	return producer
}

Using the Sarama Kafka client library from Golang we can create a consumer and a producer that are connected to a Kafka server.

The consumer will wait for new orders on the orders topic and start processing each message against our order book. The generated trades are then sent to the trades topic using the producer.

Messages from Kafka are encoded as byte arrays so we need to decode them as an order from their JSON representation.

The reverse has to be done when sending trades back to the queue.

Now you have a scalable trading engine

Its purpose is to educate and help others who are struggling with building their own exchange. Plus, the code supports many further optimizations.

Here are just a couple improvements that can be effected:

• Use a more efficient matching algorithm.
• Add the ability to cancel orders.
• Increase communication performance.
• Backup and restore the order book to prevent losing data.
• Add monitoring.

Upon implementing these improvements, you can get this basic code to process around 1 milion orders/second/market pair without network traffic and 250k trades/second/market pair with full consumer/producer traffic on a single server.

That's a lot more than most crypto exchanges out there can process with their entire infrastructure.

With that, I have to conclude this tutorial and hope you got great value from it.

If you want to skip ahead a few months/years of developement/testing and use a proved production ready solution today consider subscribing to our high performance trade engine solution that you can deploy in your own infrastructure.
It takes all the lessons we've accumulated in the past 3 years of improving and maintaining a crypto exchange and makes it available for startups looking to jumpstart their development needs even if on a small budget.