- 一个实现 HFT-Orderbook
- 主要讨论美股的限价订单簿(LOB)，A股的“市价单”和“对手最优单”可以在一定程度上转换成限价单插入到LOB中
- 定义了三种结构：
- Order: 某个价位的委托链表，每个节点表示一个买入/卖出委托；每个委托有独立的订单号；新的委托总是加在链表的尾部，成交总是从头部开始。
- Limit: 价格档二叉树，每个节点表示一个价位，且包含此价位的委托链表指针，用价格作为节点值。
- Book: 包含买方二叉树和卖方二叉树，以及指向各自最优买/卖价格节点的指针。
- 另有
{订单号:*Order}和{价格:*Limit}的两组map用来快速查找 - 时间复杂度：
- Add – O(log M) for the first order at a limit, O(1) for all others. #某个价格档首笔委托到达时需要在二叉树内插入一个节点，因此时间复杂度为O(log M) M为现有价格档数；后续委托通过其价格map到二叉树节点，因此为O(1)。
- Cancel – O(1) # 通过订单号map到链表。
- Execute – O(1) # 通过订单号map到链表。
- GetVolumeAtLimit – O(1) #通过Book中最优价格指针直接获取，在Add/Cancel/Execute时需要维护最优价格指针。
- GetBestBid/Offer – O(1)
- 空间复杂度：
{订单号:*Order}和{价位:*Limit}两组map如果时间复杂度为O(1)，则空间复杂度为O(n)。
- 价格二叉树、用链表组织每个价格的委托队列，前者使插入新价位的复杂度降到O(log M)，后者可以快速撮合、输出委托队列、新增委托。
- 用map来快速查找ID对应的委托和价格对应的二叉树节点，如果要使时间复杂度为O(1)，则需要用数组、空间复杂度为O(n)，FPGA显然无法采用，或许可以考虑用hash映射数组+树。
- 及时维护双方最优价格可以更快地生成快照并且开销也不大。
- 买一价和卖一价只差称为点差；当最新成交价与卖一价之差小于其与买一价之差时称为卖方市场，反之为买方市场。
- 方法1：
- 结构
- 用数组存放价格档信息（指针），价格作为数组的地址
- 用链表维护每个价格档的委托
- 时间复杂度：
-
插入 O(1)
-
删除(成交) O(1)
-
基于委托ID的撤单 O(n)
-
基于价格的撤单 O(ni)~O(n) #A股深圳无此操作，上海可行
-
修改委托数量(不修改时戳) O(ni)~O(n) #A股无此操作
-
修改委托数量(修改时戳) O(ni+1)~O(n) #A股无此操作
-
修改委托价格 O(ni+1)~O(n) #A股无此操作
-
n为所有委托的数目，ni为某个价格档i当前的排队委托数目
-
- 空间复杂度：
- O(n+d)，n为所有委托的数目，d为所有可能的价格的总数
- 结构
- 方法2：
- 结构
- 在方法1的基础上增加一个
hash(委托ID)模块，将委托ID的hash值作为数组地址快速查找委托，从而减少撤单耗时。
- 在方法1的基础上增加一个
- 时间复杂度变化：
- 基于委托ID的撤单 O(n)~O(n)，当hash表的alpha值小于0.5时平均O(1)
- 基于价格的撤单 O(logn+ni)~O(n/d) #A股深圳无此操作，上海可行
- 空间复杂度：
- O(n+d+s)，s为hash表深度
- 问题：
- hash表的大小至关重要的，当hash表快满时撤单的耗时会快速提高到接近O(n)，需要在事先合理评估表大小。
- 结构
- 方法3：
- 结构
- 将方法2中的hash表值从单个委托改为链表，解决hash值冲突时的耗时问题。
- 时间复杂度变化：
- 基于委托ID的撤单 O(nj)~O(n)，nj为hash值对应的链表深度
- 基于价格的撤单 O(logn+ni)~O(logn) #A股深圳无此操作，上海可行
- 空间复杂度：
- O(n+d+s)，s为hash表深度
- 价格档如果也用hash+链表维护，可以解决价格范围不定的问题，但将增加插入、删除的时间复杂度
- 结构
- 方法4：
- 结构
- 将方法2中的hash表改为用平衡二叉树管理所有委托，委托的ID值作为二叉树的节点的权重，这样在用ID检索委托时的时间复杂度降到O(logn)
- 时间复杂度变化：
- 插入 O(logn)
- 删除(成交) O(logn)
- 基于委托ID的撤单 O(logn)
- 由于每次操作都需要操作二叉树，所以复杂度都是O(logn)，同时每次修改二叉树后都需要再平衡
- 结构
- 如果可以把所有的订单都用数组地址直接索引，可以将各种操作的时间复杂度都降到O(1)
- 除了订单簿之外，逐笔数据中可以推导出很多其它信息，对交易算法可能有用：
- 最近一秒内每个价格档上的撤单数
- 最近一秒内的平均成交价
- 突发的大量委托的开始时刻
- 订单簿点差的变化情况
- 成交订单分布
- 委托的移动平均值
- 循序渐进地讨论了订单簿的各种数据结构，虽然主要是针对美股+FIX协议，但对A股也很有借鉴意义
- A股深交所的逐笔撤单不含价格，只能用序列号来查找委托；上海既可以用价格也可以用序列号来查找，可以在操作时选择复杂度低的来执行
- 方法4的结构和参考1是很接近的，而且O(logn)的复杂度更加合理
- 没有讨论多只个股间的结构，也没有讨论并行处理
文中“卖方市场”与传统商品的卖方市场类似，指股票供给减少、价格对卖方有利，价格看涨？
- 这是一个面向FPGA的订单簿更新算法
- 为减小FPGA实现难度，不保存所有委托，只保存价格档上的委托总手数（输出快照不含委托队列）
- 将涨停价到跌停价间的每个有效价格各用一个数组地址存放对应的委托总手，A股就是每0.01￥一个地址
- 采用树状的两两比较器(parallel tree reduction algorithm)计算所有价格档位中的最优价
- 缓存最优5档价格信息，在更新价格数组时同步更新缓存，这样在生成快照时时间复杂度为O(1)
- 每个有委托的价格档都有一个指针指向下一个有委托的价格档，便于更新5档价格缓存
- 将比较树做修改成Clipped reduction tree，快速查找大于或小于某个价位的有效价格，用于插入新价格档
- A股深交所撤单消息内没有原始订单的价格，因此必须保存原始订单数据，否则无法修改订单簿
- 树状的两两比较器要能并行比较的前提是所有价格档都放在FPGA的寄存器内，资源消耗无法接受
- 论文没有给出设计的FPGA资源用量，以及测试标的的价格范围等指标，所以测试数据只能作为参考
- 最优5档缓存的设计值得借鉴