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/workflows contains GitHub action configuration files for automated linting and testing.
• /app contains the entrypoint to the application, the runner of the limit order book processor.
• /book contains 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 best-case 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.