深度解剖：为何高频交易订单簿偏爱跳表（Skip List）？

作者： /

本文专为面临极端性能挑战的系统设计师与高级工程师撰写，旨在深入剖析一种在高频交易、撮合引擎等场景中至关重要的数据结构——跳表（Skip List）。我们将超越教科书式的概念介绍，从计算机科学第一性原理出发，结合CPU缓存行为、内存布局，并深入到并发控制的实现细节，最终揭示为何在与红黑树等传统平衡树的较量中，看似简单的跳表往往能成为延迟敏感型系统的更优选择。我们将通过原理、代码、权衡与演进路径，完整呈现一个工业级的思考框架。

现象与问题背景

在任何一个金融交易市场，无论是股票、期货还是数字货币，其核心都是一个被称为“订单簿”（Order Book）的模块。订单簿记录了所有尚未成交的限价委托（Limit Order），并按价格优先、时间优先的原则进行排序。对于买方（Bid），订单按价格从高到低排序；对于卖方（Ask），则按价格从低到高排序。撮合引擎（Matching Engine）的本质，就是在订单簿上进行极速的增、删、查操作。

一个典型的高频交易场景对订单簿数据结构提出了极其严苛的要求：

  • 极低的操作延迟： 每次添加订单（Insert）、取消订单（Delete）或查找最佳报价（FindMin/FindMax）的操作，必须在微秒（μs）甚至纳秒（ns）级别完成。
  • 极高的吞吐量： 系统需要能够每秒处理数百万次甚至更多的订单操作。
  • 可预测的性能： 性能毛刺（Latency Spike）是不可接受的。系统的P99、P999延迟必须得到严格控制。
  • 高效的并发处理： 多个交易请求会同时涌入，数据结构必须能被多个线程高效、安全地访问。

工程师们自然会想到使用平衡二叉搜索树（Balanced Binary Search Tree），如红黑树（Red-Black Tree）或AVL树。它们提供了理论上 O(log n) 的增删查时间复杂度。然而，在真实的硬件环境下，理论上的时间复杂度并不能完全等同于实际性能。红黑树在实践中存在一些难以克服的工程痛点：

  • 复杂的平衡操作： 插入或删除节点时，为维持树的平衡，可能需要进行一系列复杂的旋转（Rotation）和重新着色（Recoloring）操作。这些操作不仅逻辑复杂，而且可能导致树的大范围结构调整，产生不可预测的延迟。
  • 糟糕的缓存局部性（Cache Locality）： 树的节点在内存中通常是离散分配的。沿着树的指针进行遍历，相当于在内存中进行“跳跃”，这极易导致CPU缓存未命中（Cache Miss），从而招致昂贵的内存访问惩罚。
  • 并发控制的瓶颈： 对树进行结构修改（如旋转）需要对大片区域甚至整个树进行加锁，这严重限制了并发性能。实现细粒度的锁（Fine-Grained Locking）异常困难且容易出错。

正是这些工程现实，促使我们寻找一种理论性能同样优秀，但在硬件亲和性（Hardware-Friendly）和并发实现上更为简洁高效的替代方案——跳表（Skip List）因此进入了视野。

关键原理拆解

（切换到大学教授模式）

要理解跳表为何高效，我们必须回归到其数据结构的本质。跳表是一种基于概率的数据结构，它通过在有序链表的基础上增加多级“快速通道”来实现高效的查找、插入和删除操作。其核心思想可以分解为以下几个步骤：

1. 从有序链表开始

一个普通的有序链表，其查找、插入、删除操作的平均时间复杂度均为 O(n)，因为我们必须从头节点开始逐个遍历。这对于任何高性能场景都是无法接受的。

2. 建立“快速通道”

为了加速查找，我们可以在原始链表（Level 0）之上，构建一个稀疏的索引层（Level 1）。Level 1 中的每个节点都指向 Level 0 中对应的节点。例如，我们可以每隔一个节点，就在 Level 1 建立一个索引。查找时，我们首先在 Level 1 中快速“跳跃”，定位到一个大致范围，然后再下沉到 Level 0 进行精确查找。这使得查找效率近似于 O(n/2)。

3. 构建多级索引

这个思想可以被递归地应用。我们可以在 Level 1 之上构建更稀疏的 Level 2，在 Level 2 之上构建 Level 3，以此类推。每一层都是其下一层的“快速通道”。最终，我们得到一个层次化的结构。查找一个元素时，我们从最高层的头节点开始，向右移动直到下一个节点大于或等于目标值，然后下沉到下一层，重复此过程，直到在最底层找到目标。这个过程非常类似于二分查找，其路径是从左上角到右下角。

4. 概率性与平衡

与红黑树等结构通过严格的确定性算法（旋转）来维持平衡不同，跳表使用概率来维持其结构。当插入一个新节点时，我们通过一个随机过程（例如，抛硬币）来决定这个节点应该出现在哪些层级。一个常见的策略是：节点首先出现在最底层（Level 0），然后有 p 的概率（通常 p=1/2 或 p=1/4）被提升到上一层（Level 1），又有 p 的概率再被提升到 Level 2，以此类推，直到某次概率判断失败。这种概率性保证了从统计学角度看，跳表的结构是近似平衡的，其查找、插入、删除操作的平均时间复杂度均为 O(log n)。

5. 空间复杂度

如果提升概率为 p，那么一个节点出现在 Level 1 的概率是 p，出现在 Level 2 的概率是 p^2，以此类推。因此，每个节点平均拥有的指针数量为 1 + p + p^2 + … = 1/(1-p)。当 p=1/2 时，平均每个节点有 2 个指针；当 p=1/4 时，平均有 4/3 个指针。因此，其空间复杂度为 O(n)，与红黑树在同一量级，但常数因子较小。

从计算机科学的角度看，跳表的核心优势在于它将红黑树复杂的、确定性的平衡问题，转化为了一个简单的、概率性的层级问题。这使得其实现逻辑大为简化，并且在工程上带来了意想不到的好处。

系统架构总览

在一个典型的撮合引擎中，跳表作为订单簿的核心存在。整个架构可以被抽象地描述如下：

  • 撮合引擎（Matching Engine）： 这是系统的中央处理器。它通常是单线程或被严格分区以避免争用。
  • 订单簿（Order Book）： 每个交易对（如 BTC/USD）都拥有一个独立的订单簿。
  • 买盘（Bids）与卖盘（Asks）： 订单簿内部分为两个独立的部分。买盘使用一个跳表，按价格降序排列。卖盘使用另一个跳表，按价格升序排列。
  • 价格水平（Price Level）： 跳表中的每个节点代表一个价格水平（例如，所有报价为 $50000.00 的买单）。该节点的值（value）是一个队列（通常是 FIFO 队列），存放着所有报这个价格的订单。

一个新订单的处理流程如下：

  1. 一个买单（Buy Order）进入系统。
  2. 引擎首先查询卖盘（Asks）跳表。它查找价格小于或等于该买单报价的最低价卖单（即卖盘跳表的第一个节点）。
  3. 如果找到匹配的卖单（卖价 ≤ 买价），则进行撮合。从卖盘跳表的节点队列中取出订单，成交，更新双方状态。如果买单仍有余量，则继续与下一个价格或下一个订单匹配。
  4. 如果卖盘中没有可匹配的订单，或者买单在撮合后仍有剩余，那么这个买单（或其剩余部分）将被插入买盘（Bids）跳表中。
  5. 插入操作是：在买盘跳表中查找对应的价格节点。如果该价格节点已存在，则将订单追加到该节点的订单队列末尾；如果不存在，则创建一个新的价格节点（包含一个只有一个订单的队列）并将其插入跳表。
  6. 取消订单（Cancel Order）的操作则是在对应的跳表中找到价格节点，再从其订单队列中移除指定的订单。如果移除后队列为空，则从跳表中删除该价格节点。

这个架构的核心在于，两个跳表提供了对最佳买价（Bids 的第一个节点）和最佳卖价（Asks 的第一个节点）的 O(1) 访问，以及对任意价格水平的 O(log n) 的增删查能力。

核心模块设计与实现

（切换到极客工程师模式）

Talk is cheap. Show me the code. 我们用 Go 语言来勾勒一个跳表的核心实现。Go 的并发原语和指针操作使其非常适合这个任务。

数据结构定义

首先，定义节点（Node）和跳表（SkipList）的结构。注意，`forward` 是一个指针数组，其长度在节点创建时动态确定，这就是跳表的“层”的概念。


// Order represents a single limit order
type Order struct {
    ID        uint64
    Quantity  uint64
    // ... other fields like UserID, Timestamp
}

// PriceLevelNode is a node in the SkipList
type PriceLevelNode struct {
    price    int64         // Use int64 for price to avoid float issues
    orders   *list.List    // FIFO queue of orders at this price, use container/list
    forward  []*PriceLevelNode // Pointers to next nodes at different levels
}

// SkipList for the order book
type SkipList struct {
    head      *PriceLevelNode // A dummy head node
    level     int             // Current max level of the list
    randSource rand.Source
    // For concurrency, a simple mutex is a starting point
    lock      sync.RWMutex
}

const MAX_LEVEL = 32 // A reasonable max level for most applications
const PROBABILITY = 0.25 // Use p=1/4, gives sparser levels, slightly better cache performance

这里有几个工程上的小九九：

  • 价格用 `int64`： 在金融计算中，绝不要用浮点数表示金钱，精度问题会让你死得很难看。通常会将价格乘以一个固定的放大倍数（如 10^8）转换成整数。
  • 订单队列： 每个价格节点挂一个订单队列。Go 的 `container/list` 是一个双向链表，非常适合实现 FIFO 队列。

    • * `randSource`： 不要用全局的 `math/rand`，它内部有锁，在高并发下会成为瓶颈。每个跳表实例应该有自己的随机数源。

插入操作（Insert）

插入是跳表最精髓的操作。核心逻辑是：找到每一层需要被新节点“切入”的前驱节点，然后像做外科手术一样精确地插入新节点并连接指针。


func (sl *SkipList) Insert(price int64, order *Order) {
    sl.lock.Lock()
    defer sl.lock.Unlock()

    // `update` stores the predecessor nodes at each level that need to be updated.
    // This is the key to the insertion algorithm.
    update := make([]*PriceLevelNode, MAX_LEVEL)
    current := sl.head

    // 1. Find the insertion path and populate `update` array.
    for i := sl.level - 1; i >= 0; i-- {
        // Assume descending order for Bids book
        for current.forward[i] != nil && current.forward[i].price > price {
            current = current.forward[i]
        }
        update[i] = current
    }

    // `current` is now predecessor of the target position at level 0.
    current = current.forward[0]

    // 2. If price level already exists, just add the order.
    if current != nil && current.price == price {
        current.orders.PushBack(order)
        return
    }

    // 3. If not, create a new node.
    // Determine the new node's level randomly.
    newLevel := 1
    // A trick for random level generation: keep tossing a coin.
    r := sl.randSource.Int63()
    for (r&(1<<uint(newLevel-1))) == 0 && newLevel < MAX_LEVEL {
         newLevel++
    }

    if newLevel > sl.level {
        for i := sl.level; i < newLevel; i++ {
            update[i] = sl.head
        }
        sl.level = newLevel
    }

    // Create the new node
    newNode := &PriceLevelNode{
        price:   price,
        orders:  list.New(),
        forward: make([]*PriceLevelNode, newLevel),
    }
    newNode.orders.PushBack(order)

    // 4. Splice the new node into the list at all its levels.
    for i := 0; i < newLevel; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }
}

这段代码最关键的部分是 `update` 数组。它像一个手术台上的器械盘，在你一路向下探索插入位置时，把每一层需要修改的前驱节点都整齐地“摆放”好。最后，你只需要遍历这个数组，就能一次性完成所有层级的指针重定向。这种“两阶段”的操作（先查找并记录，后修改）是跳表算法优雅之处，也为后续实现无锁（Lock-Free）操作提供了可能。

性能优化与高可用设计

一个基础的、带全局锁的跳表实现，在高并发下很快会成为瓶颈。真正的战场在于并发控制和内存优化。

并发控制的演进

  • 阶段一：全局读写锁（`sync.RWMutex`）
    这是最简单、最安全的起点。读操作（如查找最佳报价）使用读锁，写操作（插入、删除）使用写锁。它能允许多个读操作并行，但任何写操作都会阻塞所有其他操作。在读多写少的场景下尚可，但在订单簿这种写操作频繁的场景，写锁的争用会非常激烈。
  • 阶段二：细粒度锁（Per-Node Locking）
    理论上，可以给每个 `PriceLevelNode` 配一把锁。在修改一个节点及其前驱节点的 `forward` 指针时，只需要锁定这几个相关的节点。这种方法能极大提升并发度，但实现起来极其复杂，需要严格的锁获取顺序来避免死锁（例如，总是从高层到底层，从左到右地加锁），代码会变得非常丑陋和难以维护。不推荐自己手写。
  • 阶段三：无锁（Lock-Free）实现
    这是性能的圣杯，也是复杂度的地狱。无锁跳表利用CPU提供的原子指令（如 `Compare-And-Swap`, CAS）来更新指针。

    基本思路：当插入一个新节点时，你不再加锁。你首先按照普通逻辑找到插入点 `update` 数组。然后，你尝试用一个 `CAS` 操作将前驱节点的 `forward` 指针从 `old_next` 原子地更新为 `new_node`。如果 `CAS` 成功，说明在你操作期间没有其他线程修改过这个指针，操作完成。如果失败，说明有争用，你必须回退并重试整个过程。删除操作更复杂，通常需要一个“逻辑删除”步骤：先用 `CAS` 将节点标记为“已删除”，然后再在后续操作中进行“物理删除”（摘除指针）。

    工程挑战：无锁编程充满了陷阱，如ABA问题、内存屏障（Memory Barrier）的正确使用、复杂的重试逻辑等。除非你的团队有深厚的底层并发编程经验，否则直接使用成熟的第三方库（如 aries-for-go 中的 lock-free skiplist 实现）或自己动手前三思。这是典型的“高风险高收益”的技术决策。

内存与CPU缓存优化

这是红黑树的软肋，也是跳表的潜在优势。

  • 内存分配器（Allocator）： 默认的Go内存分配器（TCMalloc-like）可能会将不同节点分配到内存的各个角落。为了提升缓存局部性，可以实现一个自定义的内存池或区域分配器（Arena Allocator）。将属于同一个跳表的节点尽可能地在连续的内存块（Memory Block）上分配。这样，当遍历跳表的底层链表时，CPU的预取（Prefetch）机制能更有效地将后续节点加载到缓存中，减少Cache Miss。
  • 节点结构对齐： 确保 `PriceLevelNode` 结构体的大小是缓存行（Cache Line，通常是 64 字节）的整数倍，可以避免伪共享（False Sharing）。当两个线程频繁修改位于同一个缓存行但不同的数据时，会导致缓存行在不同CPU核心之间来回失效，造成性能下降。虽然在跳表场景不那么突出，但在极致优化中值得考虑。

对抗与权衡（Trade-off）

我们来做一个直观的对比：

特性 红黑树 跳表 (带全局锁) 跳表 (无锁)
单线程性能 优秀 (O(log n)) 极优秀 (O(log n) 但常数更低，缓存更友好) 优秀 (有CAS重试开销)
并发性能 差 (全局锁，或极复杂的细粒度锁) 一般 (受限于写锁) 极优秀 (可扩展性好)
实现复杂度 高 (旋转、平衡逻辑复杂) 低 (逻辑清晰，易于理解和调试) 极高 (需要深入理解内存模型和原子操作)
延迟可预测性 一般 (旋转可能导致延迟抖动) 好 (操作路径相对固定) 优秀 (无锁，避免了锁导致的调度延迟)

结论很清晰：跳表用一种概率性的优雅，换取了实现的简洁性和更优的硬件亲和性，尤其是在并发场景下，其无锁实现的潜力远超红黑树。

架构演进与落地路径

对于一个从零开始构建或重构撮合引擎的团队，不应一上来就追求最复杂的无锁实现。推荐一个分阶段的演进路径：

第一阶段：基础验证与性能基线

  • 实现一个单线程的、功能完备的跳表订单簿。
  • 与一个标准的红黑树实现（例如，使用成熟的库）进行性能对比测试（Benchmarking）。测试集应覆盖高频插入、高频取消、深度订单簿查找等多种场景。
  • 这个阶段的目标是验证跳表在你的特定业务负载下，单核性能是否真的优于红黑树。数据是唯一标准。

第二阶段：引入并发，满足商用需求

  • 在验证过的跳表实现上，增加全局读写锁 (`sync.RWMutex`)。这是最稳妥的并发方案，能快速让系统上线并服务于中等并发量的场景。
  • 部署完善的监控，重点关注锁争用（Lock Contention）相关的指标。通过性能剖析（Profiling）工具（如Go的pprof），确定锁是否已成为系统瓶颈。

第三阶段：极限优化，冲击顶尖性能

  • 只有当监控和剖析数据明确指出全局锁是无法逾越的瓶颈时，才启动无锁跳表的研发或引入。
  • 优先考虑寻找并集成经过工业验证的无锁数据结构库。自己造轮子需要极高的成本和风险。
  • 进行详尽的正确性测试和压力测试。无锁代码的Bug通常非常诡异且难以复现。需要设计专门的并发测试用例（如Go的race detectorだけでは不十分），并进行长时间的稳定性压测。

最终，选择哪种方案并非一个纯粹的技术问题，而是一个关乎业务需求、团队能力和投入产出比的综合性工程决策。对于绝大多数系统，一个带有读写锁的、内存布局友好的跳表，已经足以提供卓越的性能。而对于那些在延迟和吞吐量上追求极致的“华尔街之狼”们，无锁跳表则是他们手中那把最锋利的军刀。

延伸阅读与相关资源

  • 想系统性规划股票、期货、外汇或数字币等多资产的交易系统建设，可以参考我们的
    交易系统整体解决方案。
  • 如果你正在评估撮合引擎、风控系统、清结算、账户体系等模块的落地方式，可以浏览
    产品与服务
    中关于交易系统搭建与定制开发的介绍。
  • 需要针对现有架构做评估、重构或从零规划，可以通过
    联系我们
    和架构顾问沟通细节，获取定制化的技术方案建议。
滚动至顶部