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:

	sealed trait OrderBookEvent
	case class Trade(buyingBroker: String, sellingBroker: String,
	price: Double, qty: Double) extends OrderBookEvent

view raw

OrderBookEvent.scala

hosted with ❤ by GitHub

	class MatchingEngine(buy: OrderBook, sell: OrderBook, orderTypes: (Order => OrderType))
	extends mutable.Publisher[OrderBookEvent] {
	def acceptOrder(order: Order) = throw new NotImplementedError()
	}

view raw

MatchingEngine.scala

hosted with ❤ by GitHub

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:

	trait OrderType {
	def bookDisplay: String
	def price: PriceLevel
	def crossesAt(price: Double): Boolean
	def decreasedBy(qty: Double): Order
	}
	object OrderType {
	def all(): PartialFunction[Order, OrderType] = {
	case self@LimitOrder(_, side, _, limit) => new OrderType {
	def bookDisplay: String = limit.toString
	def price: PriceLevel = LimitPrice(limit)
	def crossesAt(price: Double): Boolean = side match {
	case Buy => price <= limit
	case Sell => price >= limit
	}
	def decreasedBy(qty: Double): LimitOrder =
	self.copy(qty = self.qty – qty)
	}
	}
	}

view raw

OrderType.scala

hosted with ❤ by GitHub

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.

	class OrderBook(side: Side, orderTypes: (Order => OrderType)) {
	private var limitBook: List[(Double, List[Order])] = Nil
	private val priceOrdering = if (side == Sell) Ordering[Double] else Ordering[Double].reverse
	def top: Option[Order] = limitBook.headOption.map({
	case (_, orders) => orders.head
	})
	def decreaseTopBy(qty: Double) {
	limitBook match {
	case ((level, orders) :: tail) => {
	val (top :: rest) = orders
	limitBook = (qty == top.qty, rest.isEmpty) match {
	case (true, true) => tail
	case (true, false) => (level, rest) :: tail
	case _ => (level, orderTypes(top).decreasedBy(qty) :: rest) :: tail
	}
	}
	case Nil => throw new IllegalStateException("No top order in the empty book")
	}
	}
	// the rest of the implementation is omitted
	}

view raw

OrderBook.scala

hosted with ❤ by GitHub

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:

	Scenario Outline: Decrease top outstanding order partially and then fill it completely
	When the following orders are added to the "<Side>" book:
	| Broker | Qty | Price |
	| A | 100 | 10.5 |
	| B | 100 | 10.5 |
	Then the "<Side>" order book looks like:
	| Broker | Qty | Price |
	| A | 100 | 10.5 |
	| B | 100 | 10.5 |
	When the top order of the "<Side>" book is filled by "20"
	Then the "<Side>" order book looks like:
	| Broker | Qty | Price |
	| A | 80 | 10.5 |
	| B | 100 | 10.5 |
	When the top order of the "<Side>" book is filled by "80"
	Then the "<Side>" order book looks like:
	| Broker | Qty | Price |
	| B | 100 | 10.5 |
	Examples:
	| Side |
	| Buy |
	| Sell |

view raw

OrderBook.Limit.feature

hosted with ❤ by GitHub

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:

	Feature: Core matching logic for limit orders
	Background: Submit initial non-crossing orders to work with
	Given the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| A | Buy | 100 | 10.4 |
	| B | Buy | 200 | 10.3 |
	| C | Sell | 100 | 10.7 |
	| D | Sell | 200 | 10.8 |
	Then no trades are generated
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| A | 100 | 10.4 | 10.7 | 100 | C |
	| B | 200 | 10.3 | 10.8 | 200 | D |
	Scenario Outline: Matching a single Buy order against identical in quantity outstanding Sell order
	When the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| E | Buy | 100 | <Buy Order Limit> |
	Then the following trades are generated:
	| Buying broker | Selling broker | Qty | Price |
	| E | C | 100 | <Expected Trade Price> |
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| A | 100 | 10.4 | 10.8 | 200 | D |
	| B | 200 | 10.3 | | | |
	Examples:
	| Buy Order Limit | Expected Trade Price | Comments |
	| 10.7 | 10.7 | Exact same price as top of the Sell order book |
	| 10.8 | 10.7 | Higher price then the top of the Sell book |
	Scenario Outline: Matching a single Sell order against identical outstanding Buy order
	When the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| E | Sell | 100 | <Sell Order Limit> |
	Then the following trades are generated:
	| Buying broker | Selling broker | Qty | Price |
	| A | E | 100 | <Expected Trade Price> |
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| B | 200 | 10.3 | 10.7 | 100 | C |
	| | | | 10.8 | 200 | D |
	Examples:
	| Sell Order Limit | Expected Trade Price | Comments |
	| 10.4 | 10.4 | Exact same price as the top of the Buy order book |
	| 10.3 | 10.4 | Lower price than the top of the Buy book |

view raw

LimitOrdersMatching.feature

hosted with ❤ by GitHub

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:

	class MatchingEngineSteps extends ShouldMatchers {
	val orderTypes = OrderType.all()
	val buyBook: OrderBook = new OrderBook(Buy, orderTypes)
	val sellBook: OrderBook = new OrderBook(Sell, orderTypes)
	val matchingEngine = new MatchingEngine(buyBook, sellBook, orderTypes)
	var actualTrades = List[Trade]()
	events {
	case trade: Trade => actualTrades = trade :: actualTrades
	}
	@When("^the following orders are submitted in this order:$")
	def the_following_orders_are_submitted_in_this_order(orders: java.util.List[OrderRow]) {
	orders.toList.foreach(o => matchingEngine.acceptOrder(
	LimitOrder(o.broker, parseSide(o.side), o.qty, o.price.toDouble)))
	}
	@Then("^market order book looks like:$")
	def market_order_book_looks_like(book: DataTable) {
	val (buyOrders, sellOrders) = parseExpectedBooks(book)
	buyBook.orders().map(o => BookRow(Buy, o.broker, o.qty, orderTypes(o).bookDisplay)) should equal(buyOrders)
	sellBook.orders().map(o => BookRow(Sell, o.broker, o.qty, orderTypes(o).bookDisplay)) should equal(sellOrders)
	}
	@Then("^the following trades are generated:$")
	def the_following_trades_are_generated(trades: java.util.List[Trade]) {
	actualTrades.reverse should equal(trades.toList)
	actualTrades = Nil
	}
	@Then("^no trades are generated$")
	def no_trades_are_generated() {
	actualTrades should equal(Nil)
	}
	private def events(handler: PartialFunction[OrderBookEvent, Unit]) {
	matchingEngine.subscribe(new matchingEngine.Sub {
	def notify(pub: matchingEngine.Pub, event: OrderBookEvent) {
	handler(event)
	}
	})
	}
	private def parseExpectedBooks(book: DataTable): (List[BookRow], List[BookRow]) = {
	def buildOrders(orders: List[List[String]], side: Side) = {
	orders.filterNot(_.forall(_.isEmpty)).map(order => {
	val (broker :: qty :: price :: Nil) = order
	BookRow(side, broker, qty.toDouble, price)
	})
	}
	val orders = book.raw().toList.drop(1).map(_.toList)
	val buy = orders.map(_.take(3))
	val sell = orders.map(_.drop(3).reverse)
	(buildOrders(buy, Buy), buildOrders(sell, Sell))
	}
	private def parseSide(s: String): Side = s.toLowerCase match {
	case "buy" => Buy
	case "sell" => Sell
	}
	private case class OrderRow(broker: String, side: String, qty: Double, price: String)
	private case class BookRow(side: Side, broker: String, qty: Double, price: String)
	}

view raw

MatchingEngineSteps.scala

hosted with ❤ by GitHub

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:

	class MatchingEngine(buy: OrderBook, sell: OrderBook, orderTypes: (Order => OrderType))
	extends mutable.Publisher[OrderBookEvent] {
	def acceptOrder(order: Order) {
	val (book, counterBook) = getBooks(order.side)
	val unfilledOrder = tryMatch(order, counterBook)
	unfilledOrder.foreach(book.add(_))
	}
	private def getBooks(side: Side): (OrderBook, OrderBook) = side match {
	case Buy => (buy, sell)
	case Sell => (sell, buy)
	}
	private def tryMatch(order: Order, counterBook: OrderBook): Option[Order] = {
	if (order.qty == 0) None
	else counterBook.top match {
	case None => Some(order)
	case Some(top) => tryMatchWithTop(order, top) match {
	case None => Some(order)
	case Some(trade) => {
	counterBook.decreaseTopBy(trade.qty)
	publish(trade)
	val unfilledOrder = orderTypes(order).decreasedBy(trade.qty)
	tryMatch(unfilledOrder, counterBook)
	}
	}
	}
	}
	private def tryMatchWithTop(order: Order, top: Order): Option[Trade] = top match {
	case topLimit: LimitOrder => {
	if (orderTypes(order).crossesAt(topLimit.limit)) {
	val (buy, sell) = if (order.side == Buy) (order, topLimit) else (topLimit, order)
	Some(Trade(buy.broker, sell.broker, topLimit.limit, math.min(buy.qty, sell.qty)))
	}
	else None
	}
	}
	}

view raw

MatchingEngine.scala

hosted with ❤ by GitHub

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:

	Feature: Core matching logic for limit orders
	Background: Submit initial non-crossing orders to work with
	Given the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| A | Buy | 100 | 10.4 |
	| B | Buy | 200 | 10.3 |
	| C | Sell | 100 | 10.7 |
	| D | Sell | 200 | 10.8 |
	Then no trades are generated
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| A | 100 | 10.4 | 10.7 | 100 | C |
	| B | 200 | 10.3 | 10.8 | 200 | D |
	# Omitted tests for exact order size match
	# …
	Scenario: Matching a Buy order large enough to clear the Sell book
	When the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| E | Buy | 350 | 10.8 |
	Then the following trades are generated:
	| Buying broker | Selling broker | Qty | Price |
	| E | C | 100 | 10.7 |
	| E | D | 200 | 10.8 |
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| E | 50 | 10.8 | | | |
	| A | 100 | 10.4 | | | |
	| B | 200 | 10.3 | | | |
	Scenario: Matching a Sell order large enough to clear the Buy book
	When the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| E | Sell | 350 | 10.3 |
	Then the following trades are generated:
	| Buying broker | Selling broker | Qty | Price |
	| A | E | 100 | 10.4 |
	| B | E | 200 | 10.3 |
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| | | | 10.3 | 50 | E |
	| | | | 10.7 | 100 | C |
	| | | | 10.8 | 200 | D |
	Scenario: Matching a large Buy order partially
	When the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| E | Buy | 350 | 10.7 |
	Then the following trades are generated:
	| Buying broker | Selling broker | Qty | Price |
	| E | C | 100 | 10.7 |
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| E | 250 | 10.7 | 10.8 | 200 | D |
	| A | 100 | 10.4 | | | |
	| B | 200 | 10.3 | | | |
	Scenario: Matching a large Sell order partially
	When the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| E | Sell | 350 | 10.4 |
	Then the following trades are generated:
	| Buying broker | Selling broker | Qty | Price |
	| A | E | 100 | 10.4 |
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| B | 200 | 10.3 | 10.4 | 250 | E |
	| | | | 10.7 | 100 | C |
	| | | | 10.8 | 200 | D |

view raw

LimitOrdersMatching.feature

hosted with ❤ by GitHub

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:

• Matching Engine with Scala and Cucumber – Market Orders

Previous posts in this series:

• Prototyping a Matching Engine with Scala and Cucumber