Matching engine algorithms and challenges with exchanges
2019-01-26There 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)
- 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.
- 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.
Pro-Rata algorithm (implementation coming soon)
- Orders are submitted and partitioned according to their price.
- 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.
- 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.
- If the order has an equal volume to the other side then all orders at that price point are completely filled.
Engineering challenges with matching engines and orderbooksThe 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