Matching engine algorithms and challenges with exchanges

2019-01-26

There isn't much in the literature about matching engine or their engineering details. So I'm going to attempt to figure out what is actually known about these systems behind our financial systems, and try to understand the engineering challenges behind them. If you look on the wikipedia page for order matching systems, it seems like there are only two different ways to match orders, those two being Price/Time and Pro-Rata. These are fairly simple, so I'll just explain them here.

Price/Time priority algorithm (implementation coming soon)

  1. When an order is submitted to an exchange using a price/time priority matching algorithm, the order is put into a queue corresponding to the price for the order.
  2. When an order (Let's call this order A) is submitted for the same price, the orders on the opposite side at the front of the queue get filled first until either there are no more orders on the side opposite to order A at order A's price point, or order A is completely filled.
And that's it. If you don't know what side means, it's essentially whether or not the order is a buy order, or if it's a sell order. There are plenty of other uses of the word side in finance but it's not that important for understanding matching engines.

Pro-Rata algorithm (implementation coming soon)

  1. Orders are submitted and partitioned according to their price.
  2. When an order is posted for the same price, the orders on the opposite side in the orderbook are filled partially according to their percentage of the total volume for that price point.
  3. If the newly posted order has a larger volume than what it would be filling, it completely fills the orders on the opposite side and remains partially filled on its own side for that price.
  4. If the order has an equal volume to the other side then all orders at that price point are completely filled.
The purpose of pro-rata is to proportionally fill all orders according to their volume, rather than taking into account time or anything but price and volume. Most of the time assets with low volatility follow a pro-rata matching algorithm. Other than this, there isn't really much. Variations on the pro-rata algorithm exist, but these variations are not very complex and it's unclear what benefit they actually provide, other than for issues with specific asset pairs.

Engineering challenges with matching engines and orderbooks

The engineering challenges with orderbooks and matching engines can widely differ according to implementation, but one of the interesting problems with matching engines is their "fairness". A certain level of trust in the matching engine and exchange is required even if it's non-custodial, considering front-running and other price manipulation issues are extremely difficult to regulate and detect. One specific engineering challenge is the challenge of provable fairness. For matching to be provably fair, not only does a record of transactions made on the exchange need to be kept and distributed, the matching engine needs to be completely deterministic. For most systems this can be done fairly easily, but for systems that are purely functional it can be very difficult.

If you're not aware of the way fully functional programming languages keep track of state while staying pure, they pass state through a sequence or cycle of pure functions, it may get difficult to stay deterministic while remaining pure. Considering determinism is required in order for something to be provably fair, a fully functional and provably fair matching engine would have no lack of engineering problems to solve, just to stay deterministic. Other than that, most matching engines' engineering problems consist of making themselves extremely fast. Traders do not want to wait for their orders to be executed. This is easy to understand when proximity hosting is a thing.

As well as extremely fast matching engines to ensure near-instant settlement, most exchanges also have designated market makers to ensure liquidity on the exchange. Market makers make more money the more volatile the asset pair is, and market makers are typically the ones to help close the bid-ask spread through another extremely simple market making algorithm. All of these systems work together to satisfy customers, help the financial markets' gears turn, and most importantly, print money.


Previous article: Merkle trees and inclusion proofs