In the first two posts in this series, Prototyping a Matching Engine with Scala and Cucumber and Matching Engine – Crossing Limit Orders, we built a simple limit order book and a matching algorithm that crosses limit orders of opposite sides. In this post I am going to continue using Cucumber to test-drive the implementation of order book and matching engine – this time we are going to add support for another fundamental order type – market order. The complete source code for this and other posts in the series is available from my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine
Maintaining Market Orders in the Order Book
First of all lets model market order as a case class:
By definition market orders cross at any price level (line 13). “MO” (line 9) is the code we use to display outstanding market orders in the book.
Since market orders are ready to cross at any price level they sort higher than any limit orders in the order book (they have a higher price priority). Among different market orders time priority is maintained – the orders that enter the order book earlier are closer to the top. Let capture these rules in a form of Cucumber scenarios (Buy and Sell tests are very similar, so I’m using an outline for brevity):
Our OrderBook Cucumber steps are only able to parse limit orders now, so we need to extend it to understand market orders as well. We only need to modify the following step:
The code at line 12 checks for “MO” book code in the price column for order submission table and create MarketOrder if it finds it. Otherwise price is treated as Double and a LimitOrder is created.
Now if we run the new tests they fail. To fix and get back to green a few changes need to be implemented. The final code for OrderBook is:
The main changes are:
- Line 3 – we maintain a separate list for market orders, since they sort higher than any other orders and do not define a price level
- Line 11 – market orders are added to special list
- lines 16 to 21 – when top of the book is queried the first market order is returned, if present, otherwise the first limit order is returned
- line 25 to 39 – when top order is being decreased, market orders are check first, if exist, then limit
With these change all our tests pass again and we are ready to take on a new task of including market orders in our matching algorithm.
Crossing with Market Orders
Generally speaking there are 3 different ways a market order can participate in a match:
- An incoming market order hits an outstanding limit order in the opposite book
- An incoming limit order hits an outstanding market order in the opposite book
- An incoming market order hist another market order of the opposite side
Of the three cases the first one is the easiest, so I’m going to tackle it first.
Crossing Market Orders against outstanding Limit Orders
The rules for matching are best presented by example: when incoming market order MO hits a limit order A on the top of the opposite order book, it matches at the limit price of the order A. If after the first trade market order MO is not filled completely it matches with the next best limit order B at the order’s B limit price. The match continues until either the market order is filled completely or the opposite order book is empty. If market order is not completely filled at the end of the match, the remaining order is placed in its order book.
Let capture these rules in a Gherkin script before we move on to implementation:
We have just introduced new grammar to our scripts to be able to send market orders (MO) to matching engine so we need to add support for it into the step definition:
When we run our new tests now, they all pass. This lucky outcome is due to rather flexible implementation of the crossing logic we have built already for limit orders:
Note that the code we wrote for matching limit orders (lines 3 to 9) will happily match ANY order type against outstanding limit order. The other two use cases (limit order against outstanding market, and market against outstanding market) are obviously going to fail the pattern matching. We are going to tackle them in the next post.
Previous posts in this series: