In the previous post I finished support for the two fundamental order types: market and limit. In this post I am going to add support for a bit more exotic one – pegged order. Supporting pegged order type is a bit more involved compared to order types we handled before. Therefore I’m going to tackle them in two posts. In this post I’m going to handle pegged order position in the order book. And in the following post I’m going to cross them with other orders. 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 pegged orders in the order book
A pegged order is a limit order to buy or sell a stated amount of a security at a displayed price set to track the current bid or ask of the central order book. The description of pegged order by Euronext is given next, and I am going to use it as acceptance criteria to test-drive the implementation: “Peg orders are accepted in continuous trading phase if there is in the order book a best bid or offer on its side. This means that in case of empty order book the peg order is automatically rejected. On a non empty book, the peg order is displayed at the best limit price in the market sheet. In case of an executable incoming order, the Peg order can be updated only if the new best limit is displayed in the order book (after the transaction). In case of a priced Peg order (set with a limit price), the order continues pegging until the display price meets the limit price specified. If the best limit of the order book disappears (following a cancellation or an execution), and the order book is suddenly empty, peg orders are automatically eliminated.”
Lets add a model to represent this new order type – for now, we will consider a simple Peg order that is not priced :
In the previous post I implemented the “best limit” crossing rule, matching incoming limit orders against outstanding market orders. In this post I am going to complete the logic related to market orders matching by implementing the last use case – matching market orders to opposite side market orders. To do this we will introduce and explain a notion of reference price. 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 Market Order with Opposite Side Outstanding Market Orders
Consider when a market order matches with another market order in the opposite order book. At what price should the resulting trade occur? There are two possibilites here:
- the opposite order book with the resting market order also contains one or more outstanding limit orders – in this case the opposite book has a “best limit” price we discussed in the previous post and this price becomes the price for the trade
- the opposte order book does not have outstanding limit orders, so the “best limit” price is not defined. In this case the trade occurs at the “reference price”. Most often reference price is the last traded price for a security. An exchange sets the reference price at the opening, perphaps to the closing price from the last session, or the result of the opening auction session.
Lets capture the first rule (best limit price is available) using Cucumber:
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: