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.
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
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.
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:
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:
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.
In any trading engine there can be multiple types of orders the end user has access to.
Some of these include:
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 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 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 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.
Now that we have a better understanding of what constitutes a matching engine, let's see how our architecture might look like and what technologies we can use for the project.
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.
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.
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 :).
Let's now see what we need to do in order to implement a matching engine capable of processing limit orders and generate trades.
What are the steps to build a trading engine?
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 in non-ascending order 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.
Its purpose is to educate and help others who are struggling with building their own exchange. Plus, the code supports many further optimisations.
Here are just a couple improvements that can be effected:
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.
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.