The article was revised on 2020-04-18.
All forms of reprinting are prohibited without authorization. The original text was first published on the personal WeChat official account:
Liberty’s expedition recordSecurities trading System Construction Guide (Matching Engine)
Before introducing the matching engine, let’s briefly explain the common types of orders on exchanges.
The limit order must be executed at the specified price or better. If it cannot be executed immediately, it will enter the market and wait for the transaction until Completed a deal or received a cancellation order or closed.
The market order is executed immediately at the current best price.
The IOC order must be executed immediately at the limit price or a better price. If it cannot be completely executed, it will not be executed. The part is cancelled immediately.
The FOK order must be immediately at the limit price or a better price fully completed , If the transaction cannot be completed, the entire order will be cancelled immediately.
Cancel the specified commission
There are also some commission types such as
It is not commonly used in digital currency exchanges. Those who are interested can read the exchange manual by themselves.
Back to the matchmaking engine, since the secondary market is an open market, all the obligations of the transaction explain to the trader at what price and when each order was executed. This is the same as the game server The player matching logic is different in the matchmaking engine. The matchmaking engine should replay the transaction process again to get the same matchmaking result, which determines that the exchange is a strictly serial system. This is also the reason why the A-share market stipulates that after the stock is sold, the transfer to the bank must be completed on the next trading day. After the close of each trading day, the exchange will replay all orders of the day to check whether the matching results are consistent.
The nature of the world is parallel. An exchange will connect multiple brokers, and of course a broker will also have parallel orders. The previous article Securities Trading System Construction Guide (Principle) mentioned the 3 stages of transaction completion. Stage 1 ends when the exchange accepts the broker’s order. Here, the acceptance of the broker’s order means the completion of the ordering , After the order is ordered, it changes from disorder to order, and parallel to serial. This process is somewhat similar to the current limit queue in a distributed system, but the instruction sequence must be stored persistently, can only be increased, cannot be modified, and must be unique in each transaction pair.
The matching engine internally maintains a data structure called Orderbook. The order information that traders see is part of the Orderbook, but usually only includes n Best price for files. The logic of the matching engine is to continuously read the instruction sequence and match the order in the Orderbook according to the price-time priority principle. Each instruction has a corresponding processing method. The instruction logic determines the storage structure design of the Orderbook.
Initially, the Orderbook is empty, and the matching engine starts to execute the first order after the opening of the market. Untraded orders will decide whether to place an order according to the type of order, and then gradually form the depth of the exchange. There is also the concept of transaction direction in the transaction. After the order is placed, the transaction is called the maker, and vice versa, the one that actively trades the counterparty's commission is called the taker.
The matching engine is such a logic, but the implementation schemes are different, roughly divided into two types: database matching and memory matching. The current mainstream implementation schemes all use memory-based matching. Since the matchmaking engine is a strict serial logic, there is no resource competition, and there is no lock. If memory-based matchmaking does have a performance bottleneck, then GC is most likely to occur. Using a language without GC can solve this problem, such as Rust, C++. One of the main problems of memory-based matchmaking is the recovery of downtime data. According to the logic of matchmaking, as long as the instruction sequence is persistent, the recovery is also very simple. Replay can be started from the first instruction or checkpoint. Pay attention to the recovery of Orderbook And the impact of the matchmaking result on the clearing engine.
Finally, here is an update to a rust implementation, which belongs to the integration + liquidation, and does not include the broker part.