EricJJ' Blog

交易所撮合引擎心得-数据结构

2020-01-12

  1. 1. 介绍
  2. 2. 撮合引擎订单过程
  3. 3. 升级前
  4. 4. 升级后

介绍

前阵子在升级撮合引擎,在实操过程中有一些心得。写篇文章来分享一波。这是第一篇:数据结构篇。

针对特定的场景,应该选用更合适的数据结构。来看看撮合引擎的 orderbook吧!
以BTC为例 大部分情况是这样的:

买方按降序排列,卖方按升序排列。同时按照价格优先 > 时间优先的规则。

撮合引擎订单过程

我在processon 上画了个流程图,解释了一个订单的撮合周期 https://www.processon.com/view/link/5e4a5704e4b07f3482cd427d

可以看出,撮合引擎再工作时,是经常需要进行 插入到指定位置,删除头部(即插入新订单,删除已成交订单)的操作。用 双向链表 来实现 orderbook 的订单结构非常合适。go 语言也内置了双向链表container/list

升级前

升级前的旧撮合引擎数据订单结构用了go的 slice存储,插入使用二分查找(O log N),删除直接使用append(Orders[:index], Orders[index+1:]...)函数。既耗时又浪费内存空间。

数据结构大概是这样:

Bids: [[9900, 1], [9800, 1], [9700, 1]]
Asks: [[11000, 1], [12000, 1], [13000, 1]]

升级后

这里改造了下 Go的 container/list.go 函数:

// OBList OrderBook LinkedList
type OBList struct {
    root     OBElement
    len      int64
    PriceMap map[int64]*OBElement
}

// OBElement OrderBook Element
type OBElement struct {
    next, prev *OBElement
    list       *OBList
    OrderList  *OrderList
}

// OrderList Order LinkedList
type OrderList struct {
    root   OrderElement
    len    int64
    Price  int64
    Amount int64
}

// OrderElement Order Element
type OrderElement struct {
    next, prev *OrderElement
    list       *OrderList
    Order      Order
}

大概是这样:

https://www.processon.com/view/link/5e4ba616e4b0996b2ba687cc

这样设计并实现后,每次插入订单变成了先根据订单的 Price 从 PriceMap 取出对应的 List。

  • 如果为空,则需要遍历上层链表找到价格合适的位置,创建新的节点并插入。最坏 O(n)。
  • 如果不为空,取出对应的下层链表插入到末尾。O(1)。

删除订单时因为是双向链表, 并且删除的订单是知道其所在的OrderElement, 复杂度也是 O(1)。

最后实测在 Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz 配置的机器上,处理1000w订单需要7s左右。平均每秒100W+。