队列数据结构：FIFO队列原理、优先级队列原理、时间轮算法在撮合中的应用

聊到撮合引擎，队列这东西是绕不开的。说白了，整个撮合过程就是一场「排队游戏」。谁先来、谁单子大、谁优先级高，全得靠队列来管。我这些年调过不少撮合系统，踩过的坑多半都跟队列设计有关。今天咱们就把三种核心队列掰开揉碎了讲清楚。

一、FIFO队列：最朴素的公平

FIFO，先进先出。这个太直观了——先到的先服务。在撮合场景里，FIFO队列保证的是「时间公平性」。

举个例子。假设有两个买单，价格都是100元。A在10:00:00.001下单，B在10:00:00.002下单。那A就该排在B前面。这就是FIFO干的事。

核心要点：FIFO队列用链表或数组实现，入队追加到尾部，出队从头部取。时间复杂度O(1)。

我在项目中遇到过一个问题：用Java的ConcurrentLinkedQueue做FIFO队列，结果在高并发下偶尔出现顺序错乱。后来排查发现，是CAS操作在极端竞争下导致入队顺序和实际时间戳不一致。解决方案？嗯，用ReentrantLock加一个严格的时间戳校验。

// 一个简单的FIFO队列实现（伪代码）
class FIFOQueue {
    Node head, tail;
    
    void enqueue(Order order) {
        Node node = new Node(order);
        tail.next = node;
        tail = node;
    }
    
    Order dequeue() {
        if (head == null) return null;
        Order order = head.order;
        head = head.next;
        return order;
    }
}
小提示：FIFO队列在撮合中通常用于「同一价格档位」内的订单排序。价格优先是第一位，时间优先是第二位。

二、优先级队列：价格优先的底气

FIFO只解决了「谁先来」的问题。但撮合的核心逻辑是「价格优先」。你出价100块，我出价99块，哪怕我先到，你也得排我前面。这就是优先级队列的用武之地。

优先级队列，本质上是一个堆结构。最大堆或最小堆，取决于你是买单还是卖单。买单用最大堆（价高者优先），卖单用最小堆（价低者优先）。

我记得有一次，团队里新来的同事直接用PriorityQueue做撮合队列。跑压测时发现性能上不去。为什么？因为PriorityQueue的remove()操作是O(n)的。你想想看，撮合引擎每秒要处理几万笔订单，每次撤销订单都要遍历整个队列，这谁顶得住？

避坑指南：我曾经用Java的PriorityQueue做撮合队列，结果在订单撤销场景下性能暴跌。后来换成了「跳表+哈希表」的组合结构，才把撤销操作降到O(log n)。 
// 优先级队列核心逻辑（伪代码）
class PriorityQueue {
    // 买单用最大堆，卖单用最小堆
    Heap buyHeap = new MaxHeap();
    Heap sellHeap = new MinHeap();
    
    void addBuyOrder(Order order) {
        buyHeap.push(order); // 按价格排序
    }
    
    Order getBestBuy() {
        return buyHeap.peek(); // 最高价买单
    }
}

优先级队列的公平性问题，其实挺微妙的。同一价格下，谁先来？这时候就得结合FIFO了。所以实际系统中，往往是「价格优先 + 时间优先」两层结构：先按价格分桶，每个桶内再用FIFO队列。

三、时间轮算法：延迟撮合的利器

说到时间轮，很多人第一反应是Kafka里的延时消息。其实在撮合场景里，时间轮也有妙用。

什么场景需要时间轮？举个例子：冰山订单。一个大单不想暴露全部数量，只显示一部分。剩下的部分需要「延迟释放」。或者，条件订单——价格到了某个阈值才触发。这些都需要一个高效的定时器机制。

时间轮算法的核心思想，说白了就是「用空间换时间」。把时间分成一个个槽位，每个槽位对应一个时间间隔。指针每走一格，就处理当前槽位里的所有任务。

时间轮的优势：插入和取消操作都是O(1)时间复杂度。相比传统的DelayQueue（O(log n)），在高并发场景下优势明显。

我参与过一个期货撮合系统的重构。原来的延迟订单用ScheduledExecutorService管理，结果在极端行情下，线程池积压了上万个定时任务，CPU直接飙到100%。后来改成时间轮，问题迎刃而解。

// 时间轮简化实现（伪代码）
class TimeWheel {
    int tickMs;          // 每个槽位的时间跨度
    int wheelSize;       // 槽位数量
    List<Task>[] slots;  // 槽位数组
    int currentIndex;    // 当前指针位置
    
    void addTask(Task task, long delayMs) {
        int ticks = delayMs / tickMs;
        int index = (currentIndex + ticks) % wheelSize;
        slots[index].add(task);
    }
    
    void advance() {
        currentIndex = (currentIndex + 1) % wheelSize;
        // 处理当前槽位的所有任务
        for (Task task : slots[currentIndex]) {
            task.execute();
        }
    }
}
实战经验：时间轮的精度取决于tickMs。tickMs设得太小，轮询开销大；设得太大，延迟精度不够。我个人习惯设成1ms，配合批量处理来平衡性能。

四、三种队列在撮合中的协同

实际撮合引擎不会只用一种队列。它们是配合使用的。我画了一张图，帮你理清关系。

撮合队列架构图 订单流入 价格分桶（优先级队列） 价格档位1 FIFO队列 订单A → 订单B → 订单C 价格档位2 FIFO队列 订单D → 订单E 价格档位3 FIFO队列 订单F 时间轮（延迟订单/冰山订单） 撮合结果

你看这张图，订单进来后，先按价格分桶——这是优先级队列干的活。每个桶内部，再用FIFO队列保证时间公平性。至于那些需要延迟处理的订单，比如冰山订单的剩余部分，就扔进时间轮里，等时间到了再放回对应的价格桶里。

三种队列各司其职，配合起来才能既保证公平性，又保证性能。我见过不少系统只用了优先级队列，结果同一价格下的订单顺序乱得一塌糊涂。也见过只用FIFO的，结果高价单被低价单堵在后面，用户体验极差。

注意：时间轮不是万能的。如果你的系统延迟精度要求极高（微秒级），时间轮的轮询开销可能成为瓶颈。这时候可以考虑分层时间轮，或者用硬件定时器。

好了，队列这块就聊到这儿。记住一句话：没有最好的队列，只有最合适的组合。具体怎么选，得看你的业务场景和性能要求。

专注资料整理
← 上一章 📖 返回目录 下一章 →