Order Matching Engine Part 1 - Overview

About the OME

An order matching engine is a piece of software that matches buy and sell orders; basically if I want to sell 100 shares of a stock for $100 and someone else wants to buy 100 shares of that same stock for $100, the engine matches our orders. Consider the scenario where I want to sell the same number of shares for the same price, and there are two buyers, one that is willing to buy the shares for a price of $100 per share and another that is willing to buy them for $101 per share. Obviously, I will sell to the second person, since they are willing to pay more, meaning they have a price priority. However, if I want to sell for $100 and the second person wants to buy for $101, at which price should the match happen - $100, $100.5 or $101?

Most exchanges would say: at the price given by whoever made the order first. In this case that would be the buyer, which makes sense, since, if I had sent an order to sell my shares for $100 per share before the buyer that wanted $101 per share, I would have matched with the first buyer that offered $100. This means that the sequence of events is:

• Person A - Buy 100 shares for $100
• Person B - Buy 100 shares for $101
  (Buy orders in no particular order)
• Me - Sell 100 shares for $100
• Match me with Person B for 100 shares at $101

This means that while I created an order for $100 per share, I actually received $101 per share, which is the resting order's price (resting order: the order that is sitting/resting waiting to be matched). Good for me!

Now what would have happened if instead of these two buy orders being at different prices, they were at the same price, say $100? Do you split it between them, do you give them all to one buyer at random, or is there a better way?

Most exchanges would say: it goes to whoever made their order first, meaning they have a time priority. This means that if you are the first to send a buy order at the best available price (aka the bid) or a sell order at the best available price (aka the ask) then you will have priority in being matched. This raises the question: what if two people send their orders at exactly the same time? Then the order that reaches the exchange first is given priority. This is also why high-frequency trading firms pay to have their servers/devices inside an exchange's data centers, to reduce their latency down to nanoseconds - where even trying to measure the time it takes interferes with it!

The matching strategy described above is called price-time priority, sometimes also called FIFO algorithm and it's how most exchanges work. Essentially, the best price has priority, and if the price is the same, then the earliest order has priority, both in a First-In First-Out manner. That being said, there's other strategies as well, which serve different purposes. An extra algorithm I have decided to implement is the top/priority pro-rata. It is very similar to the pro rata algorithm the CME Group uses for Eurodollar/SOFR futures, treasury options and other interest-rate derivatives. This works better when there are a few large market makers constantly quoting prices, with each order being large in size. Of course, the algorithm I implemented has a few more FIFO elements, but it is ultimately a pro-rata algorithm. Specifically, this algorithm has:

• price priority across levels, meaning if the price is better, it still chooses the better price. Of course, this also means that the prices are coarser, otherwise it would be easy to just send an order at only a slightly better price
• FIFO matching within a level, but only if an order can clear the entire level. Up to this point, the algorithm essentially works like the price-time priority
• priority slice given to the earliest order; for now I've chosen 5
• pro-rata distribution based on order size, rounded down to the nearest lot size
• remainder distributed in a round-robin manner

Here's an example of this algorithm at work:

Setup: a price level has 3 resting sells, lot size = 1 and priority slice = 5:

• S1: quantity 10, earliest
• S2: quantity 30
• S3: quantity 60, latest

Level total = 100. Incoming buy = 41 (smaller than the level, so this isn't the FIFO-clears-the-level case, it triggers priority slice + pro-rata).

1. Priority slice: S1, being earliest, gets filled first, up to 5 since priority slice = 5:

traded quantity = min(priority slice=5, min(buy=41, S1=10)) = 5
S1: 10 → 5 remaining
buy: 41 → 36 remaining (this is the pool to be pro-rata'd)

2. Pro-rata distribution, floored to lot size: remaining pool sizes are S1=5, S2=30, S3=60 (total=95), split proportionally against the remaining 36:

S1: 5  * 36 / 95 = 1.89 -> floor to lot(1) = 1
S2: 30 * 36 / 95 = 11.37 -> floor = 11
S3: 60 * 36 / 95 = 22.74 -> floor = 22
sum = 34   (2 short of 36 due to flooring)

3. Round-robin remainder: 2 leftover lots (36 - 34), handed one each to the earliest orders in queue order:

S1: +1 -> pool fill = 2
S2: +1 -> pool fill = 12
S3: +0 -> pool fill = 22

Final fills (priority slice + pool share):

S1 = 5 (priority) + 2 (pool) = 7
S2 =                12 (pool) = 12
S3 =                22 (pool) = 22
Total filled = 41  ✓ matches incoming buy exactly

Final state: S1=3, S2=18, S3=38. Note that S1, despite being earliest, only nets 7 total versus S3's 22, because pro-rata weights by size after the priority slice is spent. That's the whole point of the strategy: time priority gives you a small head start (the priority slice), but size dominates the rest of the allocation.

The reason I decided to implement this strategy instead of a simple pro rata is the complexity; my thought process was simply "if I implement a relatively complex strategy by hand it will be great practice, and if I want more strategies I can just simplify the one I made". After this strategy, adding a simple pro rata is only a matter of duplicating and renaming the relevant files and classes and removing a few lines of code. Perhaps I'll do a (very) short post in the future, showcasing the usefulness of interfaces.

The strategies I have implemented will always work regardless of the implementation details, so for this post I thought it best to focus on how they work and what they entail (I believe this falls under functional requirements). As for the system as a whole, I will provide a high-level overview of the architecture, hoping the architecture stays fairly stable over time. Also, as a heads-up, I really like diagrams, so expect to see plenty in my blog. My personal motto is: "If I can't explain it with 3 boxes and 5 lines, I don't understand it well enough".

OME Architecture

As you can see, the OME has a few features:

• A structure Books to hold all books. Every book contains:
  • A Strategy which contains the strategy of that book (price-time priority, pro-rata, etc.)
  • A Security which describes the security for this book (symbol name, lot size, etc.)
  • A structure Buy Orders which contains all pending orders on the buy side
  • A structure Sell Orders which contains all pending orders on the sell side
  • A structure All Orders which contains all orders for this book, pending or not (side note: I have not yet decided how to improve this field so that not all orders are in memory, I'll make a choice after I have explored the order lifecycle)
• TCP Servers that:
  • Receive orders:
    • A JSON Server that accepts JSON messages on ports 9000 and 9001
    • A FIX Server that accepts FIX messages on ports 9002 and 9003
  • Receive commands (eg. export book snapshot):
    • An Admin Server that runs on port 9100

Of course, it has a few other components (eg. log sink) but the ones above are the ones that are necessary to understand the functional requirements explained so far, excluding the TCP servers - those were added specifically so that I can send orders and commands to a running OME.

There is also a Flask API as a small HTTP wrapper for convenience, which I will eventually use for the web frontend (most likely) but for the moment I simply have a few Python scripts that connect directly to the TCP servers of the OME and send messages/commands. Since I'm mostly focused on testing and verifying functionality, I have created:

• a script to send orders on a few symbols (using price-time priority) with random price and quantity
• a script to send orders on a symbol (using top/priority pro-rata) with random price and quantity
• a script to export a book for a given symbol

I believe the above information is enough for the moment and my next post 'Order Matching Engine Part 2' will go into more technical detail about my implementation and choices. Cheers!