第3章内存存储引擎实现

3、内存存储引擎实现：基于TreeMap的订单簿实现、基于ConcurrentSkipListMap的并发优化、订单簿的增删改查操作

好，咱们今天来聊点实在的。

上一章我们把订单簿的数据结构讲清楚了，说白了就是一张价格到订单列表的映射表。那这一章，我们就真刀真枪地把它写出来。我个人的习惯是，先跑通一个单线程版本，再考虑并发优化。别一上来就上 ConcurrentSkipListMap，你连 TreeMap 都玩不转，后面出了问题你都不知道是哪里崩的。

3.1 基于 TreeMap 的订单簿实现

先说说为什么选 TreeMap。订单簿的核心需求是什么？是按价格排序。买盘从高到低，卖盘从低到高。TreeMap 底层是红黑树，插入、删除、查找都是 O(log n)，而且天然有序。你想想看，这不就是为订单簿量身定做的吗？

我在项目中遇到过有人用 HashMap 存订单簿，结果每次查询都要全量排序，那个性能……嗯，我就不多说了。

来看代码：

public class OrderBook {
    // 买盘：价格从高到低
    private final TreeMap<Double, List<Order>> buyOrders = 
        new TreeMap<>(Comparator.reverseOrder());
    // 卖盘：价格从低到高
    private final TreeMap<Double, List<Order>> sellOrders = 
        new TreeMap<>(Comparator.naturalOrder());

    // 添加订单
    public void addOrder(Order order) {
        TreeMap<Double, List<Order>> book = 
            order.isBuy() ? buyOrders : sellOrders;
        book.computeIfAbsent(order.getPrice(), k -> new ArrayList<>())
            .add(order);
    }

    // 撤销订单
    public boolean cancelOrder(String orderId) {
        // 遍历买盘和卖盘，找到并移除
        for (Map.Entry<Double, List<Order>> entry : buyOrders.entrySet()) {
            List<Order> orders = entry.getValue();
            if (orders.removeIf(o -> o.getOrderId().equals(orderId))) {
                if (orders.isEmpty()) {
                    buyOrders.remove(entry.getKey());
                }
                return true;
            }
        }
        // 卖盘同理，代码略
        return false;
    }

    // 获取最优买价
    public Double getBestBid() {
        return buyOrders.isEmpty() ? null : buyOrders.firstKey();
    }

    // 获取最优卖价
    public Double getBestAsk() {
        return sellOrders.isEmpty() ? null : sellOrders.firstKey();
    }
}

核心要点：

买盘用 reverseOrder()，这样 firstKey() 就是最高价
卖盘用 naturalOrder()，firstKey() 就是最低价
computeIfAbsent 是个好东西，省去了判空逻辑

3.2 基于 ConcurrentSkipListMap 的并发优化

单线程版本跑通了，但现实世界是残酷的。你的订单簿可能要同时处理几百个下单请求，TreeMap 不是线程安全的，ConcurrentHashMap 又不支持排序。怎么办？

ConcurrentSkipListMap 就是答案。它底层是跳表，支持并发读写，而且同样保持有序。我建议你直接用它替换 TreeMap，改动量很小。

我曾经在一个高频交易项目里，用 TreeMap 做订单簿，上线第一天就被压垮了。后来换成 ConcurrentSkipListMap，吞吐量直接翻了 5 倍。嗯，这个坑我替你们踩过了。

public class ConcurrentOrderBook {
    private final ConcurrentSkipListMap<Double, CopyOnWriteArrayList<Order>> buyOrders = 
        new ConcurrentSkipListMap<>(Comparator.reverseOrder());
    private final ConcurrentSkipListMap<Double, CopyOnWriteArrayList<Order>> sellOrders = 
        new ConcurrentSkipListMap<>(Comparator.naturalOrder());

    public void addOrder(Order order) {
        ConcurrentSkipListMap<Double, CopyOnWriteArrayList<Order>> book = 
            order.isBuy() ? buyOrders : sellOrders;
        book.computeIfAbsent(order.getPrice(), k -> new CopyOnWriteArrayList<>())
            .add(order);
    }

    // 其他方法类似，只是把 TreeMap 换成 ConcurrentSkipListMap
}

小提示：

为什么用 CopyOnWriteArrayList 而不是 ArrayList？因为并发场景下，读多写少。CopyOnWriteArrayList 的读操作不加锁，写操作复制一份新数组。对于订单簿来说，查询频率远高于修改，这个选择很合理。

3.3 订单簿的增删改查操作

好了，现在我们把核心操作梳理一遍。订单簿的增删改查，说白了就四种：

操作	说明	时间复杂度
增加订单	按价格插入到对应列表	O(log n)
撤销订单	按订单 ID 查找并移除	O(n) 最坏情况
修改订单	先撤销再新增（价格可能变）	O(n) + O(log n)
查询盘口	获取最优买卖价及对应数量	O(1)

你可能会问，撤销操作为什么是 O(n)？因为我们要遍历某个价格下的所有订单，找到匹配的 orderId。如果某个价格下有几千笔订单，那确实慢。怎么优化？

我个人的做法是再加一个 HashMap，以 orderId 为 key，直接定位到订单所在的价格和列表位置。这样撤销就变成 O(1) 了。代价是多维护一份索引，内存换时间。

// 订单索引：orderId -> (price, isBuy)
private final ConcurrentHashMap<String, OrderLocation> orderIndex = 
    new ConcurrentHashMap<>();

public boolean cancelOrder(String orderId) {
    OrderLocation loc = orderIndex.get(orderId);
    if (loc == null) return false;
    
    ConcurrentSkipListMap<Double, CopyOnWriteArrayList<Order>> book = 
        loc.isBuy() ? buyOrders : sellOrders;
    List<Order> orders = book.get(loc.getPrice());
    if (orders != null) {
        orders.removeIf(o -> o.getOrderId().equals(orderId));
        if (orders.isEmpty()) {
            book.remove(loc.getPrice());
        }
        orderIndex.remove(orderId);
        return true;
    }
    return false;
}

注意：

加了索引之后，一定要保证索引和订单数据的一致性。我曾经因为忘记在修改订单时更新索引，导致订单撤销不了，排查了整整一个下午。血的教训啊。

3.4 本章小结

嗯，这一章的内容就这些。我们从单线程的 TreeMap 开始，讲到了并发的 ConcurrentSkipListMap，最后聊了增删改查的细节和优化思路。说白了，订单簿的内存存储引擎并不复杂，关键是要选对数据结构，并且处理好并发问题。