The original article is reprinted from liu Yue’s Technology blog v3u.cn/a_id_192

If you love him, send him to the stock market, because it is heaven. If you hate him, send him to the stock market, because it’s hell.

In the past year, the COVID-19 pandemic continued to impact the world economy, and the fluctuations of major stock markets around the world were relatively frequent, especially the A-share market. Bottom fishing is difficult to throw is difficult, rebound weak flowers residual. For the elusive stock market, new investors still need to enter cautiously. This time, we will use the data structure of double queue to realize real-time online trading matching engine and explore the mystery of stock trading.

First you need to be clear, the trading of securities and the traditional B2C electronic business system is completely different, buying and selling of securities trading system to provide the subject matter is the standard digital assets, such as the U.S. dollar, stocks, currency, etc., are the characteristics of digital denominated, divisible, that is to say, when we started buying application need to have a corresponding response selling price, To actually close the deal, and vice versa.

The logic is that all queues of buy or sell orders are passed to the matching engine, which tries to match their prices. The matching queue is divided into buy orders (in ascending order of price, with the highest bid preferred) and sell orders (in descending order, with the lowest bid preferred). If no matching price is found for the stock order, the order continues to be saved in its original appropriate location in the order queue.

Let’s take a look at the implementation of the correlation matching algorithm in an actual case. Suppose I have two order queues, one buy and one sell:

170 50 180 40 199 10 200 5Copy the code

The most common matching algorithm is the “price/time first” queue. Orders are matched primarily by price. If there are multiple orders at the same price level, the earliest one will be matched first. This is also the same as queuing: first in, first out.

As shown above, assume that there are two orders next to each other. The first was a buy order for 50 shares at $100. The second was a buy order for 10 shares at the same price. Since the order does not match any selling price (because its price is below the lowest selling price), they are placed in the order queue. The first order and the second order are stored at the same price level, but the former has priority over the latter due to time precedence. This basically means that the first order will be placed ahead of the second order in the buy queue.

And selling in the same way, first of all, the lowest price preferential trading, if the price is the same, the time preference, advanced queue to deal first, met a situation in which a lot of retail investors, however, is that if his stock continuous drop stop, even if the desperately to hang low price list is also difficult to sell, may even fall directly to the delisting wiped out, is this why?

Because when a stock falls stopped, also means that a lot of chips are stacked on the drop stop board, it is not easy to want to sell, get in line, in theory, in accordance with the “time priority and price priority” clinch a deal the trading principle of queuing, but under the condition of drop stop, there is only “time priority”, that is to say, if you want to shut down when we put the stock sold, You have to sell the stock as soon as possible.

But in fact, a stock limit, not only a small number of retail investors can not sell out, but most retail investors can not sell out, are in panic shipment, everyone is in line to sell. What’s more, buy and sell stocks is done through brokers, and brokers have VIP fast channel is not a secret, some large, hot money, agencies have big money brokerage, or by renting the channel of rapid priority on disk, it also led to the stock harden board rob to raise and drop stop board shipments when there is a certain “unfair”, and he said, Trading queue is not completely in accordance with the “price/time” order, there may be a priority (weighted) queue, so, when the fall can not run, trading can not buy into it is not what new.

In addition, we also need to pay attention to the problem of price matching and quantity matching in the matching algorithm. Assuming that the purchase order is 10 yuan and the purchase order is 10 yuan and the purchase order is 30 yuan, the matching price is 10 yuan and the purchase order is 30 yuan, and there will be 20 hands in the first position of the purchase queue, as shown below:

# Bid price quantity 10, 50 # Offer price quantity 10, 30, 11, 50Copy the code

After the matching algorithm:

# Bid price qty 10 20 # Offer price qty 11 50Copy the code

The order object is the element before the matching algorithm, and the transaction object is the object after the matching:

class Order:  
  
    def __init__(self, order_type, side, price, quantity):  
        self.type = order_type  
        self.side = side.lower()  
        self.price = price  
        self.quantity = quantity  
  
class Trade:  
  
    def __init__(self, price, quantity):  
        self.price = price  
        self.quantity = quantity
Copy the code

Type is the order type, side is the purchase order, price is the price, and quantity is the quantity.

Next we implement the order queue:

class OrderBook:  
  
    def __init__(self, bids=[], asks=[]):  
  
        self.bids = sorted(bids, key = lambda order: -order.price)  
        self.asks = sorted(asks, key = lambda order: order.price)  
  
    def __len__(self):  
        return len(self.bids) + len(self.asks)  
  
    def add(self, order):  
        if order.type == 'buy':  
            self.bids.append(order)  
        elif order.type == 'sell':  
            self.asks.append(order)  
  
    def remove(self, order):  
        if order.type == 'buy':  
            self.bids.remove(order)  
        elif order.type == 'sell':  
            self.asks.remove(order)
Copy the code

The order queue here is easily implemented as a data structure with two sorted lists, two of which contain two instances of orders sorted by price. One is sorted in ascending order (buy orders) and the other in descending order (sell orders).

The following is to achieve the core function of the system, matching engine:

from collections import deque  
  
class MatchingEngine:  
  
    def __init__(self):  
  
        self.queue = deque()  
        self.orderbook = OrderBook()  
        self.trades = deque()
Copy the code

First, we need two FIFO queues; One is used to store all incoming orders and the other is used to store all transactions that result after a match. We also need to store any orders that do not match.

The order is then passed to the matching engine by calling the.process (order) function. The matching trades are then stored in a queue, which can then be retrieved in turn (via the matching engine transaction queue) or stored in a list by calling the.get_trades () function.

def process(self, order):  
        self.match(order)  
  
def get_trades(self):  
        trades = list(self.trades)  
        return trades
Copy the code

Then there is the matching method:

def match(self, order): if order.side == 'buy': filled = 0 consumed_asks = [] for i in range(len(self.orderbook.asks)): Ask = self. Orderbook. Asks [I] if ask. Price > order. Price: break # If filled + ask.quantity <= order.quantity: filled += ask.quantity trade = Trade(ask.price, ask.quantity) self.trades.append(trade) consumed_asks.append(ask) elif filled + ask.quantity > order.quantity: volume = order.quantity-filled filled += volume trade = Trade(ask.price, Volume) self.trades. Append (trade) ask.quantity -= volume # if filled < order. Quantity: Self.orderbook. add(Order("limit", "buy", order.price, order.quantit-filled)) # self.orderbook.remove(ask) elif order.side == 'sell': filled = 0 consumed_bids = [] for i in range(len(self.orderbook.bids)): bid = self.orderbook.bids[i] if bid.price < order.price: break if filled == order.quantity: break if filled + bid.quantity <= order.quantity: filled += bid.quantity trade = Trade(bid.price, bid.quantity) self.trades.append(trade) consumed_bids.append(bid) elif filled + bid.quantity > order.quantity: volume = order.quantity-filled filled += volume trade = Trade(bid.price, volume) self.trades.append(trade) bid.quantity -= volume if filled < order.quantity: self.orderbook.add(Order("limit", "sell", order.price, order.quantity-filled)) for bid in consumed_bids: self.orderbook.remove(bid) else: self.orderbook.add(order)Copy the code

It’s not very complicated logically, and it basically loops through the order queue until the received order is matched exactly. For each matched order, a transaction object is created and added to the transaction queue. If the matching engine cannot complete the match completely, it adds the remaining quantity to the order queue as a separate order.

Of course, in order to cope with high concurrency scenarios and achieve tens of thousands of transactions per second, we can modify the matching engine to perform multi-tasks asynchronously:

from threading import Thread  
from collections import deque  
  
class MatchingEngine:  
  
    def __init__(self, threaded=False):  
  
        self.queue = deque()

        self.orderbook = OrderBook()

self.trades = deque()

        self.threaded = threaded  
        if self.threaded:  
            self.thread = Thread(target=self.run)  
            self.thread.start()
Copy the code

Alter thread method:

def process(self, order):  
        if self.threaded:  
            self.queue.append(order)  
        else:  
            self.match(order)
Copy the code

Finally, to enable the matching engine to loop matches in a threaded fashion, add a start entry:

def run(self):  
          
        while True:  
            if len(self.queue) > 0:  
                order = self.queue.popleft()  
                self.match(order)  
                print(self.get_trades())  
                print(len(self.orderbook))
Copy the code

The complete code is as follows:

class Order: def __init__(self, order_type, side, price, quantity): self.type = order_type self.side = side.lower() self.price = price self.quantity = quantity class Trade: def __init__(self, price, quantity): self.price = price self.quantity = quantity class OrderBook: def __init__(self, bids=[], asks=[]): self.bids = sorted(bids, key = lambda order: -order.price) self.asks = sorted(asks, key = lambda order: order.price) def __len__(self): return len(self.bids) + len(self.asks) def add(self, order): if order.type == 'buy': self.bids.append(order) elif order.type == 'sell': self.asks.append(order) def remove(self, order): if order.type == 'buy': self.bids.remove(order) elif order.type == 'sell': self.asks.remove(order) from threading import Thread from collections import deque class MatchingEngine: def __init__(self, threaded=False): order1 = Order(order_type="buy",side="buy",price=10,quantity=10) order2 = Order(order_type="sell",side="sell",price=10,quantity=20) self.queue = deque() self.orderbook = OrderBook() self.orderbook.add(order1) self.orderbook.add(order2) self.queue.append(order1) self.queue.append(order2) self.trades = deque() self.threaded = threaded if self.threaded: self.thread = Thread(target=self.run) self.thread.start() def run(self): while True: if len(self.queue) > 0: order = self.queue.popleft() self.match(order) print(self.get_trades()) print(len(self.orderbook)) def process(self, order): if self.threaded: self.queue.append(order) else: self.match(order) def get_trades(self): trades = list(self.trades) return trades def match(self, order): if order.side == 'buy': filled = 0 consumed_asks = [] for i in range(len(self.orderbook.asks)): Ask = self. Orderbook. Asks [I] if ask. Price > order. Price: break # If filled + ask.quantity <= order.quantity: filled += ask.quantity trade = Trade(ask.price, ask.quantity) self.trades.append(trade) consumed_asks.append(ask) elif filled + ask.quantity > order.quantity: volume = order.quantity-filled filled += volume trade = Trade(ask.price, Volume) self.trades. Append (trade) ask.quantity -= volume # if filled < order. Quantity: Self.orderbook. add(Order("limit", "buy", order.price, order.quantit-filled)) # self.orderbook.remove(ask) elif order.side == 'sell': filled = 0 consumed_bids = [] for i in range(len(self.orderbook.bids)): bid = self.orderbook.bids[i] if bid.price < order.price: break if filled == order.quantity: break if filled + bid.quantity <= order.quantity: filled += bid.quantity trade = Trade(bid.price, bid.quantity) self.trades.append(trade) consumed_bids.append(bid) elif filled + bid.quantity > order.quantity: volume = order.quantity-filled filled += volume trade = Trade(bid.price, volume) self.trades.append(trade) bid.quantity -= volume if filled < order.quantity: self.orderbook.add(Order("limit", "sell", order.price, order.quantity-filled)) for bid in consumed_bids: self.orderbook.remove(bid) else: self.orderbook.add(order)Copy the code

Test it out:

me = MatchingEngine(threaded=True)  
  
me.run()
Copy the code

Return result:

liuyue:mytornado liuyue$ python3 "/Users/liuyue/wodfan/work/mytornado/test_order_match.py"  
[<__main__.Trade object at 0x102c71750>]  
2  
[<__main__.Trade object at 0x102c71750>, <__main__.Trade object at 0x102c71790>]  
1
Copy the code

No problem.

Conclusion: the so-called world Xixi, are to benefit; The world is bustling, all for profit. This famous saying of Tai Shi Gong reveals the essence of the stock market. The instinct of human nature is to pursue interests, but the pursuit of interests should be under the principle of determination. However, the capital market is often cruel.

The original article is reprinted from liu Yue’s Technology blog v3u.cn/a_id_192