核心数据结构设计：订单簿的灵魂

做撮合引擎，说白了就是跟订单簿打交道。我入行那会儿，第一个任务就是优化一个撮合核心，当时看到那坨代码，内存分配满天飞，延迟高得离谱。嗯，今天我们就来聊聊订单簿的核心数据结构设计。

订单簿（OrderBook）设计

订单簿是什么？简单说，就是买卖双方挂单的集合。买盘叫Bid，卖盘叫Ask。每个价格上可能挂了很多单子，这些单子按时间排队。

我个人习惯把OrderBook设计成两个独立的价格队列容器：

class OrderBook {
    PriceQueue bids;  // 买盘，价格从高到低
    PriceQueue asks;  // 卖盘，价格从低到高
    uint64_t sequence; // 全局序列号
};

为什么分开？因为撮合逻辑只会在最高买价和最低卖价之间碰撞。你想想看，如果混在一起，每次撮合都要遍历查找，那延迟就上去了。

价格队列与时间优先原则

时间优先，说白了就是先来后到。同一个价格上，先挂的单子先成交。这个原则在期货、股票市场里是铁律。

我在项目中遇到过一个问题：如果直接用链表存订单，插入是O(1)，但查找价格位置是O(n)。当某个热门价格上有几万笔订单时，性能直接崩了。

解决方案是什么？用两层结构：

struct PriceLevel {
    int64_t price;
    std::deque<Order*> orders;  // 时间有序
    PriceLevel* next;
    PriceLevel* prev;
};

class PriceQueue {
    std::map<int64_t, PriceLevel> levels; // 价格到层级的映射
    PriceLevel* head; // 最优价格
};

这样，查找价格层级用红黑树（O(log n)），插入订单到队列尾部（O(1)）。时间优先自然就满足了。

内存布局与缓存友好性

嗯，这里要重点说说。现代CPU的L1缓存才32KB，L2也就256KB。如果你的数据结构散落在内存各处，CPU每次都要去主存拿数据，那延迟就是几十纳秒 vs 几纳秒的差别。

我曾经优化过一个撮合引擎，把延迟从5微秒降到了800纳秒。怎么做到的？核心就是缓存友好。

看这个对比：

方案	内存布局	缓存命中率	延迟
链表	分散	低	高
数组	连续	高	低
对象池	连续	极高	极低

我个人建议：订单对象用数组存储，用索引代替指针。这样遍历时，CPU预取器能提前把数据加载到缓存。

struct Order {
    int64_t order_id;
    int64_t price;
    int64_t quantity;
    uint32_t timestamp;
    uint8_t side; // 0买 1卖
    // 补齐到64字节，避免伪共享
    char padding[7];
};

// 用vector代替list
std::vector<Order> order_pool;

对象池与内存池技术

做低延迟系统，最忌讳的就是运行时动态分配内存。new/delete、malloc/free这些操作，延迟不稳定，有时候几纳秒，有时候几百微秒。

我习惯用对象池。说白了，就是提前分配好一批对象，用的时候拿，用完归还。

template<typename T>
class ObjectPool {
    std::vector<T> pool;
    std::vector<size_t> free_list;
    
public:
    T* acquire() {
        if (free_list.empty()) {
            pool.emplace_back();
            return &pool.back();
        }
        size_t idx = free_list.back();
        free_list.pop_back();
        return &pool[idx];
    }
    
    void release(T* obj) {
        size_t idx = obj - &pool[0];
        free_list.push_back(idx);
    }
};

你看，这里用vector存储对象，用free_list记录空闲位置。acquire和release都是O(1)操作，而且内存连续，缓存友好。

还有个细节：内存池的大小怎么定？我一般按最大订单数的1.2倍预分配。比如系统设计支持100万笔订单，那就预分配120万个Order对象。多出来的20%是缓冲，防止极端情况。

整体架构图

下面这张图展示了订单簿的核心数据流：

从图上你能看到，订单从入口进来，先找到对应的价格层级，然后插入到该层级的订单队列尾部。所有订单对象都从底部的内存池分配，保证内存连续。

总结一下

订单簿设计，核心就三点：

• 价格队列：买盘降序，卖盘升序，用map实现O(log n)查找
• 时间优先：同价格用deque，插入尾部O(1)，保证先来后到
• 内存优化：对象池预分配，数组连续存储，避免伪共享

这些设计看起来简单，但每个细节都直接影响撮合引擎的延迟。我见过太多团队在初期不重视数据结构，后期优化时发现牵一发而动全身。嗯，打好基础，后面才能走得快。

---