限价委托簿与撮合

某 HFT 私募在 CFFEX 张江 COLO 机房的市场数据组长，把你叫到白板前，09:25 开盘前问一个问题：沪深300 ETF（510300.SH）的委托簿在线路上和内存里到底应该怎么存，才能让 SSE 推送的二级行情每秒 20 万条增量消息全部落本，同时热路径上一次 malloc 都不调？你在白板上画出的那张结构图，就是这家私募所有市场数据系统、撮合引擎、内部对手盘、做市机器人的承载数据结构。委托簿写对了，本模块后续三课——行情处理器、策略框架、部署故事——一脉相通；写错了，下游每一层都要为这点延迟买单，永远还不清。

一段话讲清限价委托簿

限价委托簿（limit order book, LOB）是一个按价格排序的容器，每一档（price level）持有该价位上所有挂单组成的 FIFO 队列。买盘按价格降序排列（最高买价在顶），卖盘按价格升序排列（最低卖价在顶）。最优买价加最优卖价合称​​内部​​（inside of the book）——任何吃单（marketable order）只会先碰到这两个价格。每家交易所发布行情的方式都是增量更新：挂单、撤单、改单、成交（与挂单撮合）。你要做的，是用微秒级延迟把这些增量打进委托簿，并保证读取内部价随时廉价。

三种实现，三种代价

C++ 里 LOB 的写法主流有三种。选哪一种是 cycles 与灵活度之间的取舍，取决于品种 tick 密度以及内部价读取频率。

std::map<Price, Level> 是 <map> 提供的红黑树。迭代器顺序即价格排序，配合恰当的比较器，m.begin() 是最优卖价、m.rbegin() 是最优买价。每个树节点都是一次独立堆分配，只能通过指针追，50–100 ns 的开销就来自这里。原型与低频策略尚可，HFT 生产几乎不用。

boost::container::flat_map<Price, Level> 是一个排序的 vector 配二分查找。连续存储让查询缓存命中后落到 10–30 ns；代价是在前端插入（一个更深的新最优档）最坏 O(n)。读多写少、新挂单集中在尾端的场景下完全够用。

​数组索引价格阶梯​​才是 HFT 生产的默认。在构造期划定有界价格区间——比如典型成交带上下各取 10,000 个 tick——用一个 std::array<Level, kNumTicks> 连续存放每个 tick 对应的档位。索引就是 (price - min_price) / tick_size。插入是一次按下标写入，查询是一次按下标读取，内部价只需两个常驻指数（best_bid_idx_、best_ask_idx_）。每家活跃的 CN 私募自营桌、每家 HFT 蓝筹席位，内层委托簿都是数组索引阶梯，偶尔回落到 std::map 处理极少数越带价格。

承载结构

24 字节的 Order 是基本单位。字段顺序是有讲究的：order_id 居首（查询最频繁，常驻热缓存），side 紧贴对齐填充，随后是数量与整型 tick 价格（绝对不能用浮点，浮点在 tick 边界比较是 bug 工厂），最后是侵入式链表指针。

#include <array>
#include <cstdint>
#include <vector>

enum class Side : std::uint8_t { Buy = 0, Sell = 1 };

struct Order {
    std::uint64_t order_id;
    Side          side;
    std::uint32_t qty;
    std::int32_t  price_ticks;   // integer price in tick units (never floating-point)
    Order*        prev;
    Order*        next;
};

struct Level {
    std::uint64_t qty_total = 0;
    Order*        head      = nullptr;
    Order*        tail      = nullptr;
} alignas(64);   // padded to one cache line; prevents false sharing across adjacent levels

static constexpr std::size_t kNumTicks = 10'000;

class OrderBook {
public:
    void add_order(Side side, std::int32_t price_ticks, std::uint32_t qty, std::uint64_t order_id);
    void cancel_order(std::uint64_t order_id);
    void modify_order(std::uint64_t order_id, std::int32_t new_price_ticks, std::uint32_t new_qty);
    std::int32_t best_bid_ticks() const noexcept;
    std::int32_t best_ask_ticks() const noexcept;
    std::uint64_t volume_at(Side side, std::int32_t price_ticks) const noexcept;
private:
    std::array<Level, kNumTicks> levels_{};
    std::size_t                  best_bid_idx_ = 0;
    std::size_t                  best_ask_idx_ = kNumTicks - 1;
};

24 字节排布：id 8 + side 1 (+ 3 pad) + qty 4 + price 4 + prev 8 + next 8 = 36 字节；生产实现进一步压到 32 字节的方法是把 side 折进 order_id 的高位。Level 标了 alignas(64)，使相邻两档不共享同一条 cache line——内部档与次档之间的伪共享一旦发生，每次更新会多付 30–80 ns。

池分配器

每个 Order 都从 freelist 串起来的池中分配。这就是 3.4.3 L3 的池分配器模式：一段连续的 std::vector<Order> 容量固定，未使用槽位的 next 指针串成下一空闲槽位。分配即从 freelist 弹出，回收即压回 freelist。两者都是一个 cycle，不调 malloc，不加锁。

#include <vector>

class OrderPool {
public:
    explicit OrderPool(std::size_t capacity)
        : storage_(capacity), free_head_(nullptr) {
        // Build the freelist threading through unused slots.
        for (std::size_t i = 0; i + 1 < storage_.size(); ++i) {
            storage_[i].next = &storage_[i + 1];
        }
        if (!storage_.empty()) storage_.back().next = nullptr;
        free_head_ = storage_.empty() ? nullptr : &storage_[0];
    }

    // Allocation: pop the freelist head. O(1).
    Order* allocate() noexcept {
        if (!free_head_) return nullptr;   // pool exhausted; production code logs+escalates
        Order* o = free_head_;
        free_head_ = o->next;
        return o;
    }

    // Deallocation: push back onto the freelist head. O(1).
    void deallocate(Order* o) noexcept {
        o->next = free_head_;
        free_head_ = o;
    }
private:
    std::vector<Order> storage_;
    Order*             free_head_;
};

生产环境里池按线程私有，容量按峰值在途单数留 3 倍冗余——活跃单品种委托簿通常 1M 槽位。池归委托簿线程所有，没有别人能碰，于是分配器从结构上就是无锁的。

插入：链到档位 FIFO 的尾部

插入路径是最便宜的有趣操作。算出档位索引、从池里分配、把新节点链到档位侵入式链表的尾部、更新档位数量、登记反查表、如果这一档刷新了最优价就滚动内部索引。

void OrderBook::add_order(Side side, std::int32_t price_ticks, std::uint32_t qty, std::uint64_t order_id) {
    // Production: validate price_ticks within ladder bounds; for didactic clarity we assume valid.
    const std::size_t idx = static_cast<std::size_t>(price_ticks);
    Level& lvl = levels_[idx];

    Order* o = pool_.allocate();
    o->order_id = order_id;
    o->side     = side;
    o->qty      = qty;
    o->price_ticks = price_ticks;
    o->prev = lvl.tail;
    o->next = nullptr;

    if (lvl.tail) lvl.tail->next = o;
    else          lvl.head = o;          // first order at this level
    lvl.tail = o;
    lvl.qty_total += qty;

    order_index_[order_id] = o;          // reverse lookup for cancel / modify by id

    // Roll the inside index if this order opens a new inside on its side.
    if (side == Side::Buy && idx > best_bid_idx_) best_bid_idx_ = idx;
    if (side == Side::Sell && idx < best_ask_idx_) best_ask_idx_ = idx;
}

order_index_ 是一个开放寻址的扁平哈希表，键为 order_id。撤单与改单都通过这张表反查；没有它，按单号定位订单就只能按档线性扫描，热路径上完全不能接受。

价格-时间优先与撮合走单

SSE / SZSE 主板对沪深300 ETF 与 CFFEX 对 IF / IC 股指期货采用的撮合规则都是​​价格-时间优先​​（price-time priority）：内部价档先撮，同一档内先到先撮（FIFO）。把这个例子从头到尾走一遍。

// Initial book state (price in CNY; the trace uses tick units in parentheses).
// bid 4.20 x 100  --> price_ticks 4200
// bid 4.19 x 200  --> price_ticks 4190
// ask 4.22 x 100  --> price_ticks 4220
// ask 4.23 x 200  --> price_ticks 4230
// ask 4.24 x 100  --> price_ticks 4240
//
// Aggressor: BUY 250 shares (no price limit; marketable).
// Step 1: match 100 at 4220                ; aggressor remaining = 150; ask level 4220 empties; best_ask_idx_ rolls to 4230.
// Step 2: match 150 at 4230                ; aggressor remaining = 0;   ask level 4230 has 50 left.
//
// Final book state:
// bid 4.20 x 100
// bid 4.19 x 200
// ask 4.23 x 50    <-- new inside ask; first FIFO order partially filled, second untouched
// ask 4.24 x 100

吃单方把 4.22 上的 100 全部吃掉，再部分吃 4.23 上的 200 笔头一单。这一单剩下的 50 留在 4.23 档 FIFO 头部，对那 50 股保留时间优先。best_ask_idx_ 只滚动了一次——4.22 档清空时；第二次撮合没有触发滚动，因为 4.23 档还有挂单。

latency_per_op = base_cycles + cache_misses * 100

与之对照，​​比例分配撮合​​（pro-rata matching）值得点名。CME 上少数品种（历史上是 Eurodollars，以及个别其他）采用：吃单方的数量按内部档所有挂单的大小按比例分配。这会改变挂单方的策略激励——既然时间不再决定胜负，就没必要早早排队。规则因交易所而异：撮合假设 FIFO 之前先读规则书。

快照+回放：故障恢复契约

生产行情都跑 UDP 多播，包丢失是常态。每条消息都带序号。如果处理器收到序号 N，但上一条按序到达是 N-2（N-1 丢了），处理方案有三种——L2 详谈——但万能后备总是​​快照+回放​​（snapshot-and-resume）：连到交易所的 TCP 快照服务器，请求"序号 N 时符号 X 的完整委托簿"，收一份完整状态作为挂单列表，安装为当前委托簿，再把多播序号 N+1 起的所有增量重放追上。

委托簿必须提供 install_snapshot(const std::vector<Order>& snap) 作为批量装载入口。L1 定义这一契约，L2 实现多播 / 序号 / 缺口检测层，并在缺口超阈时回调 install_snapshot。

不在本课范围的内容

集合竞价撮合（SSE / SZSE 集合竞价、各家美股交易所的开 / 收盘竞价、LSE SETS 拍卖、JPX 板寄せ）是交易所特定算法，属于另一个市场微观结构模块——本课讲的是连续交易阶段的 FIFO 数据结构，集合竞价最终也读取这套结构。limit 与 market 以外的订单类型动物园（stop、stop-limit、冰山、隐藏、IOC / FOK / GTC）增加预撮合校验，不改变内层容器；每多一种订单类型都是多一道前置校验，不是多一种容器。跨场所的智能订单路由（SOR、跨交易所与暗池）属于 L3 订单路由器节，且在本模块内只覆盖单一场所路由这一案例。

衔接下一课

至此你已经有了一份能在 10 ns 内完成挂单、撤单、改单、批量快照的委托簿。下一个问题是怎么喂它：SSE Level-2 多播 UDP 火力、每条消息上的序号、不可避免的丢包。L2 构建行情处理器——一条只做 recvmsg 与解析的固定 CPU 线程，一组对两路冗余流去重的 A/B 仲裁器，以及三种生产级缺口恢复方案，并回调 L1 的 install_snapshot。

练习