Matching Engine – Pegged Orders in the Limit Book

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:

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 :

We have added PegOrder case class, new order book events – RejectedOrder and CancelledOrder, and a new pricing level – PegPrice.

Defining a corresponding order type partial function for a pegged order is interesting due to dynamic nature of peg – in order to implement “crossesAt(price)”, for example, the parameters of the pegged order itself aren’t sufficient – we also need to know what is currently the best limit in the order book. Thus the following pegged order type definition and corresponding changes to the OrderType framework:

Here is a walkthrough the code we just added:

  • Line 3 – as we discussed to implement some of the dynamic behavior of the pegged order type we need access to corresponding order book and its best limit. Thus we passing the books to the OrderType framework
  • Lines 25 – here is where we leverage access to the pegged order’s book to get its best limit. Note that evaluating a pegged order in the book with no best limit defined is illegal and a defensive exception is thrown
  • Line 14 – we display pegged order in the book at the book’s current best limit
  • Line 16 – we define a new PegPrice price level that the order book will have to handle (relative to its best limit) for the price priority rule
  • Lines 18 to 21 – the logic for crossing is similar to limit prices but relative to the current (dynamic) best limit of the book

Now that we defined PegOrder and its behavior we are ready to test-drive the implementation of our first acceptance criteria – if a peg order is submitted to an empty book (or the book with only market orders present) it should be rejected:

Note that we are defining new step for checking rejected orders, lines 12 and 22. Lets implement the step definition to support this:

  • Line 3 – note that we are now passing both order books to the OrderType framework, to support pegged orders functionality
  • Line 31 – adding support for parsing Peg orders from scenario steps
  • Lines 7 to 11 and 36 to 42 – subscribing to book events and storing rejected events in a Vector. Note, that we currently don’t have OrderBook support for emitting events, but we will add this support next
  • Lines 16 to 24 – the new step definition itself, compares actual rejected orders to the ones expected by a scenario

Before I proceed with implementing the feature I’d like to enact an important refactoring required for efficient implementation of pegged functionality in general. So far we were able to get away with maintaining a list of orders using the List data structure. This is not an ideal data structure for an order book since it only allows fast, O(1) access to the head of the list. With pegged orders, as best limit changes, we are going to remove them from the list and re-add (to the end of the price level list) quite often, so we want append and remove be O(1) fast too, if possible. The data structure that fits the bill is DoubleLinkedList and I have refactored the OrderBook to use it. DoubleLinkedList class that comes with Scala collection library is somewhat verbose to use, especially when handling the first and the last entries in the list. So I wrapped it in a class called FastList and updated OrderBook to use it. FastList provides O(1) fast implementation for appending/prepending, querying the head, and removal from anywhere in the list.

If you are interested, FastList implementation is here. Corresponding unit tests are here.

Implementing rejecting Peg orders feature in OrderBook requires new logic in the “add” and “addPeg” methods as follows:

Lines 23 to 28 contain the relevant new code. The case when best limit is available is not yet implemented. When best limit is not available, we emit the RejectedOrder event and leave the book unmodified. Run the new tests now and you should see them all pass.

Now lets add the rest of the acceptance tests. As a summary, we want to cover the following cases:

  • Price and time priority of pegged orders over market and limit orders
  • Pegged order starts pegging more aggressive limit order when the latter enters the book
  • Pegged order starts pegging less aggressive limit order when more aggressive leaves the book
  • Pegged order is automatically canceled if the best limit of the order book disappears

Following is the complete implementation of OrderBook with full support for pegged orders, and commentary on the most significant changes:

  • Line 11 – we maintain an additional list of all pegged orders currently in the book; this way if the best limit changes we can quickly peg all of them to the new limit, or cancel if no new best limit is available
  • Line 19 – if order’s price level is tested as PegPrice treat the order as pegged
  • Line 30 – added modify method to the order book; the idea is that the caller (usually the MatchingEngine) passes in the worker callback that gets access to the top of the book, i.e. can query it or decrease the top order, partially or completely, as many times as necessary. When the worker is done, OrderBook‘s best limit may have changed, so we may need resubmit our peg orders. We do so at line 57.
  • Lines 62 to 69 – logic for adding or resubmitting a peg order; if best limit is defined, peg order is treated as limit order which limit equals to the best limit, otherwise it is rejected (for new orders) or cancelled (for orders already in the book)
  • Line 75 – adding a limit order may have changed the best limit of the book; peg orders may need to be resubmitted to peg new best limit
  • Lines 97 to 103updatePegs() method; called when the best limit of the book has changed for any reason; resubmits all peg orders currently in the book, so they either start pegging new best limit (if available) or cancelled.

This is it for maintaining peg orders in the book. Run all tests again to confirm they all green. In the next post I am going to complete peg orders support by adding some tests for matching them against other orders.

Previous posts in this series:

1 comment
  1. sapeish said:

    Hey Eugene, nice post series!

    Do you have any bibliographic reference on the theory of matching principles to be followed by a Matching Engine?


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: