技术博客

盘口(十档)数据结构:快照+增量的合并算法

第 75 / 141 篇 · 2025-10-29 · secfin · 行情系统数据结构订单簿

行情客户端屏幕上那个买一卖五(Level-2 是十档)的盘口,不是服务器推什么显示什么,而是客户端本地维护的一份数据结构的投影。服务器只推变化(增量),客户端拿增量改本地快照。这篇讲这份快照的结构和合并算法。

为什么客户端要本地维护快照

服务器如果把十档全量每变一次就推一次,带宽是灾难:十档快照约 300 字节,一个证券每秒变动 20 个档位,单证券 6 KB/s,全市场乘出来专线直接爆。增量模式推一条 50 字节的"第 N 档价变了、量变了",带宽降一个数量级。代价是状态分散:每份终端各自维护快照,各自的正确性各自负责。

这就定下了合并算法的输入语义:三类消息。新增(某价位出现档位)、修改(某价位量变化)、删除(某价位消失),外加成交(它同时隐含删档或改档)。所有消息按每频道单调递增的序列号到达,乱序和丢失是异常处理的事(下一篇),合并算法只认"已排序的消息流"这个前提。

数据结构:小数组的胜利

十档盘口,每侧最多 10 个价位,用什么结构?候选有平衡树、链表、跳表,但工程上答案朴素得意外:定长数组。买一侧是价格降序数组,卖一侧价格升序,每元素 (price, qty) 两个定点整数。

$$ \text{bids} = [(p_1, q_1), \ldots, (p_{10}, q_{10})], \quad p_1 > p_2 > \cdots > p_{10} $$

数组的短板是中间插入删除 O(n),n=10 时 memmove 移动 9 个元素、每个 16 字节,一次合并几十纳秒,洪峰每秒几万条也毫无压力。而数组的缓存友好性是树结构比不了的:盘口快照每来一个客户端请求就要整体序列化一遍(全量下发给新接入者),数组是一段连续内存,memcpy 全出;树要中序遍历。读多写少、n 极小、批量输出频繁——三个条件叠一起,数组完胜。

服务器侧的行情服务器共享内存快照区同理:按证券 ID 哈希定址,每只证券固定槽位(预留十档空间加少量余位),下游进程用证券 ID 算出偏移直接读写,无锁无寻址成本。这是"内存撮合"思路在行情侧的镜像:把热数据放在算得出来的地方,而不是查得出来的地方。

合并状态机

增量消息的处理逻辑,伪代码:

void on_increment(Side* s, Msg* m) {
    switch (m->type) {
    case ADD:    // 新价位插入,保持有序
        insert_sorted(s, m->price, m->qty); break;
    case MODIFY: // 价位在,量变了
        s->qty[idx_of(s, m->price)] = m->qty; break;
    case DELETE: // 价位消失,数组压缩
        memmove(&s->arr[idx], &s->arr[idx+1],
                (--s->n - idx) * sizeof(Level)); break;
    }
    if (s->n > MAX_LEVELS)      // 挤出第 11 档
        s->n = MAX_LEVELS;
}

三个坑都藏在细节里。一是 ADD 插入位置必须用二分查找定,不能顺序扫——证券价格档位密集,顺序扫在洪峰时是热点。二是 DELETE 用"价位索引"而不是"档位数"寻址:消息说的是"14.32 这个价位没了",不是"第 3 档没了",档位数是快照的派生物,协议里带的是价位。三是深度溢出:第 11 档出现时直接截断,十档视野外的数据对客户端没有意义,服务器也不必下发。

成交消息的特殊性

成交增量不只是"记一笔成交"。撮合吃掉盘口一档的量,盘口快照必须同步收缩:量减到零就删档,没减完就改量。所以成交消息在合并层要转换成一次隐含的 MODIFY/DELETE。注意主动买方向吃掉卖一档——行情协议会带 BSFlag(主动买/主动卖)字段,合并算法据此判断改哪一侧。方向解析错了,盘口会越合越歪,且偏离是单向累积的:删除操作作用在错误的价位上,缺口永远无法靠后续增量补回,只能等下一张快照整体覆盖。这也是快照兜底的真实价值——它不仅救丢包,还救逻辑 bug 的累积漂移。

正确性验证

合并算法的测试不能只看"处理后盘口长什么样",要验证不变量:买一侧价格严格降序、卖一侧严格升序、两侧不交叉(买一价 < 卖一价,除非涨停跌停的特例——涨跌停价位上两侧可以同价,这是规则允许的)。盘中断言这些不变量,违例即告警切换数据源,是行情服务器的自保手段。更深一层的验证是双路比对:主备两条链各自独立合并,定期 diff 快照,不一致说明至少一路有 bug 或丢包,人工介入。行情系统的可信不是靠"单个实现很仔细",是靠冗余加上可观测。

盘口合并:增量驱动本地快照卖五(价升序)买五(价降序)卖5 14.38 × 3200卖4 14.37 × 5800卖3 14.36 × 2100卖2 14.35 × 9000卖1 14.34 × 12600卖1 被主动买吃掉 2600量 12600 → 10000(MODIFY)买1 14.33 × 15400买2 14.32 × 8800买3 14.31 × 4300买4 14.30 × 5100买5 14.29 × 2600买3 价位撤单14.31 档删除,memmove 压缩增量消息流ADD / MODIFY / DELETE快照消息全量覆盖兜底不变量断言:买侧严格降序、卖侧严格升序、两侧不交叉(涨跌停同价除外);违例告警切源