第4章核心数据结构设计

4、核心数据结构设计：价格队列、订单节点与缓存友好布局

好，咱们进入正题。订单簿的核心，说白了就是三个东西：价格队列、订单节点，以及它们怎么在内存里摆得漂亮。

我见过太多团队，一上来就写 std::map<double, std::vector<Order>>，觉得完事了。结果一到高频场景，延迟直接爆炸。为什么？因为 std::vector 的插入删除是 O(n)，而且内存碎片化严重。你想想看，每秒几十万笔订单，每次撮合都要挪动内存，CPU 缓存得哭死。

4.1 价格队列设计：别用 vector，用 intrusive 链表

我个人习惯，价格队列用侵入式双向链表。什么意思？就是订单节点自己带着 prev 和 next 指针，而不是容器帮你管理。

核心思路：把链表指针嵌入到订单对象内部，避免额外内存分配。

来看代码：

// 侵入式链表节点基类
struct ListNode {
    ListNode* prev;
    ListNode* next;
};

// 价格队列
struct PriceLevel {
    double price;
    ListNode head;  // 哨兵节点
    uint32_t order_count;
    uint64_t total_volume;
    
    void append(ListNode* node) {
        node->prev = head.prev;
        node->next = &head;
        head.prev->next = node;
        head.prev = node;
        order_count++;
    }
    
    void remove(ListNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        order_count--;
    }
};

嗯，这里要注意：head 是哨兵节点，不存实际数据。这样插入和删除都是 O(1)，而且没有内存分配开销。我在项目中遇到过，用 std::list 做价格队列，结果每次 new 节点都要走内存分配器，延迟抖动特别大。换成侵入式链表后，P99 延迟直接降了 40%。

4.2 订单节点设计：小而美，对齐是关键

订单节点是订单簿里最频繁操作的对象。每秒几百万次访问，它的内存布局直接决定了缓存命中率。

我建议这样设计：

struct OrderNode : public ListNode {
    uint64_t order_id;      // 8 字节
    uint32_t price_int;     // 4 字节，用整数表示价格，避免浮点
    uint32_t quantity;      // 4 字节
    uint32_t filled;        // 4 字节
    uint8_t  side;          // 1 字节：0=买，1=卖
    uint8_t  type;          // 1 字节：0=限价，1=市价
    uint16_t flags;         // 2 字节：各种状态标记
    // 总共 24 字节，正好 3 个 cache line（假设 64 字节 cache line）
    // 但实际上我们只用了 24 字节，剩下的 40 字节可以放其他数据
    char     padding[40];   // 显式填充到 64 字节
};

避坑指南：我曾经把 order_id 和 price_int 的顺序搞反了，结果每次访问价格都要跨 cache line。后来用 alignas(64) 强制对齐，性能又提升了 15%。

为什么用 price_int 而不是 double？因为浮点比较慢，而且容易有精度问题。我习惯把价格乘以 10000 转成整数，比如 123.4567 变成 1234567。这样比较、排序都直接用整数指令，快得多。

4.3 Level 数据结构的缓存友好布局

现在到了关键部分。价格队列和订单节点怎么组织，才能让 CPU 缓存开心？

我推荐用数组池 + 空闲链表的方式。说白了，就是预分配一大块连续内存，所有订单节点都从这里面取。

class OrderPool {
    static constexpr size_t POOL_SIZE = 1 << 20;  // 100 万个节点
    OrderNode nodes[POOL_SIZE];
    uint32_t free_head;  // 空闲链表头
    
public:
    OrderNode* allocate() {
        if (free_head == UINT32_MAX) return nullptr;
        OrderNode* node = &nodes[free_head];
        free_head = node->next_free;  // 复用 next 字段作为空闲链表
        return node;
    }
    
    void deallocate(OrderNode* node) {
        node->next_free = free_head;
        free_head = node - nodes;  // 用索引而不是指针
    }
};

注意：这里用 uint32_t 索引而不是原始指针。为什么？因为 32 位索引在 64 位系统上更省缓存空间，而且可以避免指针压缩的问题。我踩过这个坑——用指针做空闲链表，结果内存碎片导致 TLB miss 暴增。

来看一张整体结构图，帮你理清思路：

4.4 实战中的缓存优化技巧

光有结构还不够，操作方式也得讲究。我总结了几条铁律：

批量处理：不要一次只处理一个订单。攒够一批，比如 64 个，再一起遍历。这样能充分利用 cache line。
预取指令：在遍历链表时，用 __builtin_prefetch 提前加载下一个节点。我实测过，能再降 10-15% 的延迟。
分离热数据和冷数据：把经常访问的字段（价格、数量）放在结构体开头，不常用的（时间戳、用户ID）放后面。这样 cache line 里装的全是热数据。

一个小技巧：如果你用 x86 平台，可以试试把 OrderNode 的大小控制在 64 字节以内。这样每个节点正好占一个 cache line，访问时不会出现「跨行」的尴尬情况。我有个项目就是靠这个优化，把撮合延迟从 500ns 降到了 300ns。

嗯，关于数据结构设计，今天就聊这么多。记住一句话：内存布局决定性能上限，算法决定你能达到这个上限的多少。下一节咱们会深入聊聊订单簿的并发控制，那又是另一番天地了。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

4、核心数据结构设计：价格队列、订单节点与缓存友好布局

4.1 价格队列设计：别用 vector，用 intrusive 链表

4.2 订单节点设计：小而美，对齐是关键

4.3 Level 数据结构的缓存友好布局

4.4 实战中的缓存优化技巧