Implementing matching engine correctly can be tricky when you consider variety of order types offered by real exchanges. In addition to core limit and market orders exchanges offer additional execution strategies: market-to-limit, various types of pegged orders, stop orders, and others. Matching different order types is non-trivial, and there are many edge cases. In addition there are different rules for matching orders when session opens (i.e. auction mode) vs. continuous trading.
The resulting complexity strongly suggests a test driven approach for developing correctly working engine. In the following series of posts I’m going to gradually build a prototype of a functionally rich equity matching engine. To make things interesting I’m going to model the functionality based on a real, publicly available specs from Euronext: https://europeanequities.nyx.com/trading/order-types
The complete source code for every posts in the series is available in my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine
The foundation – limit order book
Implementing a matching engine inevitably requires maintaining buy and sell order books. In this first post I am going to test drive the implementation of a simple limit order book using Scala and Cucumber.
First lets start defining the domain model. All orders are created by brokers, are either to sell or to buy a given instrument, and have a known size and quantity. Limit orders, in addition, define a limit price, and will not execute if market conditions are inferior to the limit price:
And then a simple order book interface; for now, as TDD suggests, lets leave the methods unimplemented:
At this time we only need to be able to add a limit order to a given book and ask the book to show its current composition. Later, in the next post, we are going to extend the interface to support matching.
We are now ready to test drive the implementation of our first feature. Lets add a single order to the book and verify the order is indeed added. As I mentioned, I’m going to use Cucumber as this is a killer technology to express the types of tests we need. As you will see these tests are perfectly easy to understand and maintain by non developers, so they could (and should) be produced by business stakeholders:
Let’s run the tests. I’m using Cucumber-JVM (https://github.com/cucumber/cucumber-jvm) with Scala and JUnit:
Since we haven’t implemented the steps, the tests fail, and Cucumber is happy to provide us with skeletons for missing implementation:
So lets use the provided stubs and implement them. Note, that I have converted the Java stubs to Scala. The stubs are generated in Java because I’m using cucumber-java driver. Ideally, I would use cucumber-scala driver to get generated stubs in Scala directly but, unfortunately, this driver has not matured yet, and is broken in many places:
Here we define a couple of helper case classes to parse Gherkins tables with orders (OrderRow) and book entries (BookRow). We maintain two books in the steps definition class (one for each side, Buy and Sell), and implement the two steps we defined so far by delegation to corresponding operations on the OrderBook class. Now, when we run our tests again, we can see we are making progress. Now the tests are running and failing, reporting the implementation in OrderBook is missing:
Let now go ahead and implement just the bare minimum to have our first scenario pass:
Run the tests one more time and they are now all green.
Lets now turn our attention to the most important invariant of the order book – to sort the orders such that more agressive orders are closer to the top. Lets add more tests to drive this implementation, one with more aggressive order entering the book first, and second with less agressive one first. We will focus on the Sell orders first – the lower the limit price on the Sell order, the more aggressive the order is, and it should be given a price priority:
Now, when we run the two new tests, one of them passes (by accident) and the other one fails since we aren’t trying to maintain the price priority. Lets implement the proper ordering such that Sell orders with lower limit price are pushed to the top of the book:
When we run the three tests again, they all pass! Let’s add similar tests for Buy orders. Of course, for Buy orders, the order with a higher limit price should be given price priority:
Now run the tests again. Oops! All Buy scenarios related to price priority in the book now fail. This is not surprising since the logic we currently implemented is only valid for Sell orders. Lets fix this. To do this we just need to make a few changes. This is the final OrderBook code:
The important changes are:
- Line 4 – we defined a pricing ordering helper – natural Double ordering for Sell orders and reverse for Buy orders
- Line 21 – appropriate ordering is used to determine the order position in the order book
Lets run the tests again – all green. We have just developed a simple order book that properly sorts Buy and Sell orders according to price priority.
Time priority is another invariant that we need to maintain – for two orders with the same limit price, the order that enters the order book first has a higher priority. Let add two additional scenarios to make sure the time priority is currently maintained (we will submit two orders to each book, with the same price but for different brokers):
Ok, lets run the tests one more time – they are still green! The time priority invariant has already been supported by our current algorithm. We have built a simple limit order book that now maintains both price and time priority invariants. This is going to help us a lot in the next post where we are going to start matching incoming orders with each other: Matching Engine with Scala and Cucumber – Crossing Limit Orders.