Matching Engine – Crossing Limit Orders


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:


We have defined a simple interface that accepts an incoming limit order and emits back resulting matches (trades). We have also extended our domain to model a trade. Trade always has a known size, involves two parties (brokers), and executes at an established price. Note that MatchingEngine is able to publish events of type OrderBookEvent. Trade extends this trait and in the future we are going to support other events, for example, order status.

When two oposite side orders are crossed they are getting filled and their outstanding quantity decreases. Lets implement a few small helper methods on OrderType for convenience:

Implementation of crossesAt for LimitOrder is straightforward – a Buy order is happy to cross at a price that is at or below the limit; for a Sell order it is the opposite.

When we fill the top of the order book (lines 16 to 18) with some quantity there are two possible outcomes:

  • order is filled completely and is removed from the book
  • order is only filled partially – the remainder of the order continues to sit on the top of its book

These are the Cucumber tests I wrote to test-drive the implementation:

Note that I have used scenario outline here, since the tests for Buy and Sell books are identical.

Lets now write some tests to start driving the matching logic. Lets start with a few easy scenarios:

  • A Sell order matches against identical (same size) Buy order outstanding in the Buy order book
    • one trade should be generated for the full orders size
    • Sell order is fully filled and no remaining part is added to the Sell order book
    • Buy order is fully filled and is no longer outstanding in the Buy order book
  • The same test for matching a Buy order against identical (same size) Sell order outstanding in Sell order book

Lets see how we can express this with Cucumber:

Lets run the test now. New test fail and Cucumber reports new unimplemented scenarios. Lets take the generated stubs for new steps and implement them:

A quick walk through the steps implementation:

  • step at line 14 parsed a list of orders from a scenario and submits them one by one to the matching engine, capturing and accumulating any resulting trades (lines 10 to 12); the trades are stored so that later steps can assert against them
  • step at line 21 parses combined expected book, splits it into buy and sell books, and asserts those expected outstanding orders against actual orders reported by actual Buy and Sell books
  • step at line 30 parses expected trades and asserts them against actual trades captured by prior step(s); once asserted, captured trades are “forgotten”
  • step at line 37 is a convenience helper to use when we expect no trades to be generated

Now when scenario steps are implemented, let implement required logic so that tests pass. For MatchingEngine this is trivial:

Implementation of acceptOrder submits the order to its counter book (the book with the opposite side). Any unfilled portion of the order (if any) is then added to the appropriate book (the book with the same side). Resulting trades (if any) are emitted as they are generated (line 26).

While in practice I would implement just the bare minimum to have our first test scenario pass (exact match on quantity), for the sake of this post’s brevity, provided implementation happens to support the other possible use cases:

  • No matches at all – i.e. limit order submitted is not aggressive enough to cross with the top of the opposite book
  • Partial match for the incoming order – this occurs when the incoming order crosses with one or more orders from the top of the opposite order book, but their cumulative quantity is not enough to fill the incoming order completely
  • Partial match for the opposite side book order (for example, when incoming order is smaller in size than the top order from the opposite book)

Here are some scenarios that exercise all of these use cases:

Lets run the tests again – and they all pass!

That is it for the world of pure limit orders. In the next post I’ll introduce the support for another fundamental order type – market order.

Next post:

Previous posts in this series:

Advertisements
2 comments
  1. Omri said:

    I’m curious if there’s any more rational behind generating one trade when there’s a match?
    The model I’ve seen is that each order gets its own execution as an independent entity of the cross, and not a single generated trade that’s attributed to both the buy and sell orders. Independent of the two executions (one for buy order, one for sell order), there’s some what of a ‘cross entity’ generated which represents the matching of the two. It’s interesting from a domain design perspective to think whether or not this cross is an independent entity, when in reality if you bust a cross, both executions are busted, etc – that is, their life cycle is coupled.

  2. eprystupa said:

    Hi Omri, this is an implementation detail. In practice a matching engine, which is single threaded, need to output the result (a single match) quickly. A different thread may later split it into two trades, enrich and correlate as necessary, and report separately to each party.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: