Orderbook is a simple implementation of limit-order-book, written in Go. It simulates the ordering system using Kafka and MongoDB. It also stores and updates orderbooks using some in-memory algorithms and data structures.
Orderbook consists of two applications: one for producing random orders and sending them to a Kafka topic, and one for consuming the orders, storing them in MongoDB, and updating the orderbook.
-
Run
cmd/orderproducer/main.gofor the producer application. This will create a Kafka producer and a scheduler that will produce a random order every second and send it to the orders topic. The orders are in four sample branches for testing purposes. -
Run
cmd/server/main.gofor the main application. This will create a Kafka consumer that will read the orders from the orders topic and process them. It also exposes an endpoint for getting the orderbook.
GET /orderbook: returns the entire orderbook as a JSON object.
{
"symbol": "ETHIRT"
"limit": 10
}{
"data": {
"bids": [
[
"1550006",
"0.325300"
]
],
"asks": [
[
"1550008",
"0.679650"
]
],
"minAsk": 1550008,
"maxBid": 1550006
}
}The orderbook is stored in memory using three data models: PricePoint, Order, and Orderbook.
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 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 PricePoint struct {
OrderHead *Order
OrderTail *Order
}Each Order is either a buy or sell, and has a limit price and amount. also, each of them 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 Order struct {
ID string
Side Side // Buy, Sell
Symbol Symbol // BTCUSDT, ETHUSDT, ...
Amount float64
Price uint32
Next *Order
CreatedAt time.Time
UpdatedAt time.Time
}OrderBooks does most of the heavy lifting by keeping track of the current maximum bid and minimum ask, an index mapping order IDs to pointers, and an array of all possible price points.
type Orderbook struct {
MinAsk uint32
MaxBid uint32
OrderIndex map[ObjectID]*Order
PricePoints [MaxPrice]*PricePoint
}These are the basic operations for an orderbook:
- Inserting a new order into the book.
- Filling an order by matching it with the best available opposite order.
- Updating an existing order by changing its price or volume.
- Deleting an existing order from the book.
But the inserting and the filling operations are just implemented in this project.
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 asking if necessary, adding an entry in the order index, and inserting the record to Mongo. These are all O(1).
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.
The performance of Filling 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).
Some possible improvements and extensions for this project:
- Using a sorted set data structure or Redis to store the price points, instead of an array. This would reduce the space complexity and handle the cases where the price range or precision is not fixed.
- Making the queries more ACID-compliant and the Kafka consumer more scalable and fault-tolerant.