Recently I have been researching a matching algorithm for a certain sector of a swap market. This turned into a graph problem requiring finding strongly connected components of the graph (and then cycles) to generate possible multi-broker trades. I turned to Wikipedia for help and found this nice Tarjan’s algorithm:
I quickly coded it up as-is in Scala, my language of choice currently. All worked fine, but it did not feel right in Scala, relying so heavily on mutable state. It took me a bit but I managed to rework the algorithm into a purely functional style. Here is the code:
In the previous post I integrated a new order type – market – into the order book, implemented price and time priority rules for market orders, and started matching them. I tested and implemented the simplest case – matching incoming market order against outstanding limit order. In this post I am going to continue using Cucumber to test-drive the implementation of another use case: matching incoming limit order to outstanding market one. 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
Crossing Limit Order with Outstanding Market Orders
What happens when an incoming limit order crosses with a market order in the opposite book? At what price should they cross? The actual rule is a bit involved:
- If the opposite book does not have outstanding limit orders, then the trade settles at the incoming order’s limit price
- “Best limit” price improvement rule: if the opposite book does have limit orders, the trade settles at the better of two prices – the incoming order’s limit or the best limit from the opposite book – the term “better of two prices” is from the point of view of the incoming limit order. In other words, if incoming limit order would have crossed with outstanding opposite “best limit” order in the absence of market order, then trade at that, potentially improved, “best limit” price.
To implement this logic it is useful to have OrderBook class maintain the notion of “best limit” price at any time. Lets capture the different possible scenarios in a Cucumber script:
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):
In the first post in this series, Prototyping a Matching Engine with Scala and Cucumber, we built a simple limit order book that properly maintains price and time priority for incoming Buy or Sell orders. In this post I am going to continue using Cucumber to test-drive the implementation of an algorithm that matches incoming limit orders against the opposite side order book. 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
Introducing Matching Engine
So far we have dealt with two independent order books, one for Buy orders and one for Sell orders. Now when we are going to match opposite side orders, it is useful to introduce a concept of matching engine – an algorithm that operates on both order books and matches and determines the prices at which orders are matched:
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: