Limit Order Book
Limit order books keep records of orders for a given symbol to be traded. The purpose of the order book is to track
the best orders for each side (buy/sell) in price then time priority order. For buys, the best price is a higher price,
and sell orders are prioritised for lower prices. Orders hitting the book for an existing limit price are added to the
book at lower priority than existing orders as they met the market later in time. If orders enter the book that
cross/match the opposite side then they can be traded.
This program processes limit orders for trading symbols from a CSV input file. The requirements of the program are to
accept orders and cancels from a file, and publish changes to the top of the book, for each book. By default, this
program will reject trades that cross the book, but trading can be switched on by passing in a flag to the application.
When provided a CSV file, the program will output acknowledgments, rejections, top of book changes and trade information
to the console in a CSV format.
Usage
In order to run the application:
$ go build -o limit-order-book
$ ./limit-order-book -orders-csv=app/testdata/all_scenarios_input.csv -trade=false
Within the app/testdata directory, there are a number of example scenario input and output files, these are used for
testing, but can also be passed to the application.
There is also a Dockerfile to support containerisation of the application. It is a multi-stage build Dockerfile producing
a distroless image of around 4MB. The docker image will only be built if the tests pass successfully which is important
to prevent the creation of invalid images.
To run with docker:
$ docker build --tag limit-order-book .
$ docker run --mount type=bind,\
source="$(pwd)"/app/testdata/all_scenarios_input.csv,\
target=/data/input.csv \
limit-order-book -orders-csv=/data/input.csv
Project Structure
/the project root contains the main.go file as well as the project configuration files./.github/workflowscontains GitHub action configuration files for automated linting and testing./appcontains the entrypoint to the application, the runner of the limit order book processor./bookcontains the book interface, two limit book implementations and associated test suites.
Design Decisions
When presented with the order book programming exercise, my first approach was to manage the sides of the book with two
separate lists, maintained in sorted order of price-time priority. This implementation can be seen in the
book/naive_limit_order_book.go implementation. In this implementation two slices are created with an initial capacity,
orders are added by using a binary search algorithm (provided by the Go standard library) to find the point of insertion
based on the price of the incoming order. The time complexity of the AddOrder operation is in O(log N) time – the cost
of the binary search algorithm. Fetching the top of the book, and executing orders at the top of the book can happen in
constant time (O(1)) as we know the position of the best order for a given side due to it being at the head of the
slices (index 0). Cancellations in this implementation take longer – on the order of O(N) as we need to iterate through
all elements on each side of the book to find the order to be cancelled as we only know the user ID and their order ID.
After understanding how limit order books are typically used it became clear that the Add, Cancel and Execute operations
should happen as quickly as possible. Orders for currencies/stock/securities can be traded and requested at very high
frequencies. To improve upon the performance of the naive implementation I implemented the
book/sparse_array_limit_order_book.go implementation. In this implementation a sparse array (where many of the entries
in the array are nil or empty) is used to track lists of limit orders at each given price point where the price is the
index of the array, e.g:
list of orders for each price point
9
4 6 5
1 3 2 7 8
__ __ __ __ __
price array indexes: [ ..., 10, 11, 12, 13, 14, ... ]
The array contains pointers to doubly linked lists for each price point, this makes it easy to append elements at each
price point by adding to the tail of the list (see book/limit_list.go), the AddOrder operation can now be completed in
constant time as we know where to insert the new order ahead of time (O(1)). To overcome the limitations of the CancelOrder
implementation of the naive implementation, the book/sparse_array_limit_order_book.go implementation keeps a map of the limit
nodes added to the book keyed on user and user order ID. This allows for constant-time lookup of orders to be cancelled
as removing nodes from their respective lists does not require searching through lists to find the correct order for
cancellation. Execute order performance is kept by maintaining the price of the best bid and ask within the book so this
stays at constant time.
A series of benchmark tests were written in order to assert the performance of the sparse array implementation compared
to the naive implementation that was written first, see: book/limit_order_book_bench_test.go. The sample output
below shows that the ns/operation of the sparse array implementation was better for all three core operations of the
limit order book – AddOrder, CancelOrder, and ExecuteOrder:
BenchmarkBook_AddOrder/naive_implementation-6 100 28185260 ns/op
BenchmarkBook_AddOrder/sparse_array_implementation-6 4166 284213 ns/op
BenchmarkBook_CancelOrder/naive_implementation-6 740 1583303 ns/op
BenchmarkBook_CancelOrder/sparse_array_implementation-6 3349 316291 ns/op
BenchmarkBook_ExecuteOrder/naive_implementation-6 4839 248972 ns/op
BenchmarkBook_ExecuteOrder/sparse_array_implementation-6 5176 225276 ns/op
It should be noted that this application requires no external dependencies and uses only the Go standard library.
Testing
There are two components of this application that require testing, the first component is the Book interface and its
implementations; the second is the app that contains the csv exchange processor for the application.
Tests for the book interface cover scenarios that ensure that the integrity of the book is maintained on each side by
adding and cancelling orders across a range of price limits using the AddOrder and CancelOrder method of each of the
two book implementations. The ExecuteOrder method is also tested with both full order fulfilment and partial order
fulfilment.
Tests for the csv exchange application utilise the provided example scenarios given in the app/testdata/all_scenarios_input.csv
and can be found in the app/app_test.go file. The scenarios in the end-to-end test file have also been extracted into
individual files so that they can be tested in isolation and run with the trade flag set to either true or false.
Extra test scenarios have also been added to test-drive the implementation of partial trade matching functionality, see
these test cases in app/app_test.go:
"trade limit sell partial": {"testdata/scenario_7_input.csv", "testdata/scenario_7_trade_output.csv", true},
"trade limit buy partial": {"testdata/scenario_8_input.csv", "testdata/scenario_8_trade_output.csv", true},
Future Improvements
Given more time it would be good to add support for scenarios that require fulfilment of an order that spans a volume of
more than what is available on the best matching order. The sparse_array_limit_order_book.go could support this, but
the application would need to be modified to output multiple trade lines to make this clear in the program output.
More work could be done to the app package to separate the csv processing aspect from the concept of an exchange and allow
the exchange to manage multiple limit order books at any given time. More separation of concerns in this area could lead
to a library that allows for inputs other than CSV, such as accepting orders from a message queue.
Exchanges generally accept the concept of Market Orders. These are orders that are placed for a given volume/quantity
regardless of the best bid or ask. These orders can span multiple price limits to meet fulfilment and would be a good
extension to this exercise.
Other quality-of-life improvements would be to extend the GitHub actions to automate the publishing of release artefacts
so that the library can be used in other projects and publication of the docker file to a repository.
