本文面向具有一定并发编程和数据结构基础的中高级工程师。我们将深入探讨在金融交易等极端低延迟场景下，为何跳表（SkipList）能够成为构建订单簿（Order Book）的卓越数据结构。我们将从第一性原理出发，剖析其时间复杂度、内存布局，并层层递进，从一个带全局锁的朴素实现，演进到细粒度锁乃至Lock-Free的并发优化，最终给出一套可落地的工程实践与性能评测指南。
现象与问题背景
在任何一个交易系统中，无论是股票、期货还是数字货币，订单簿都是撮合引擎的心脏。订单簿的本质是一个实时维护的市场深度（Market Depth）快照，它记录了所有尚未成交的买单（Bids）和卖单（Asks）。买单按价格从高到低排序，卖单按价格从低到高排序。系统的核心性能瓶頸之一，就落在了对这个核心数据结构的读写效率上。
一个典型的订单簿需要支持以下几种高频操作：
- 新增订单（Add Order）：一个新订单进入市场，需要被快速插入到订单簿的正确价格位置。
- 取消订单（Cancel Order）：交易员撤单，需要根据订单ID快速定位并移除。
- 获取最优报价（Get Best Bid/Ask）：即买一价和卖一价，这是市场价格发现的基础，必须瞬时可得。
- 遍历市场深度（Iterate Market Depth）：为行情系统提供从最优价格开始的N层报价与挂单量。
对于一个热门交易对，每秒可能会有数万甚至数十万次的订单簿变更。这意味着，我们选择的数据结构必须在插入、删除、查找操作上都达到极低的延迟，通常在微秒（µs）级别。同时，撮合引擎是典型的多生产者（交易网关）、单消费者（撮合线程）或多生产者、多消费者模型，数据结构本身的并发性能直接决定了整个系统的吞吐上限。
传统的教科书方案，如使用平衡二叉搜索树（如红黑树）或者简单的排序数组，在真实工程中都会遇到难以逾越的障碍。排序数组的插入删除是 O(N) 的，直接出局。红黑树虽然各项操作都是 O(log N)，但在高并发场景下，树的旋转（rebalancing）操作需要对大范围节点加锁，锁粒度过大，导致并发性能急剧下降，成为瓶颈。
关键原理拆解
在深入工程实现之前，我们必须回归计算机科学的基础，理解为什么跳表在理论上能够胜任这个角色。跳表是一种概率性数据结构，它通过增加额外的“快车道”指针，以空间换时间，实现了高效的查找、插入和删除。
（教授声音）
我们可以将跳表想象成一个多层的有序链表。最底层（Level 0）是一个标准的有序链表，包含了所有元素。每一层（Level i）都是下一层（Level i-1）的一个子序列。一个元素如果在第 i 层出现，那么它一定在所有低于 i 的层中出现。最高层的链表元素最少，查找时，我们从最高层的“快速通道”开始，如果下一个节点的键值大于目标值，或者到达了链表末尾，我们就下降一层，继续在这个更稠密的链表上查找。这个过程不断重复，直到在最底层找到目标位置。这种设计将查找的期望时间复杂度从 O(N) 优化到了 O(log N)。
让我们来分析一下它的核心特性：
- 概率性平衡：与红黑树、AVL树等严格通过旋转操作来维持平衡不同，跳表通过一个随机函数来决定新插入节点的“层高”。一个节点出现在第 i 层的概率是 p^i（通常 p 取 1/4 或 1/2）。这种概率性的方式使得整个数据结构在期望上是平衡的，避免了复杂且影响并发的全局平衡操作。虽然存在理论上的最坏情况（所有节点都只有一层，退化为O(N)链表），但其概率低到可以忽略不计。
- 空间复杂度：由于高层节点是低层节点的子集，每个节点平均拥有的指针数量为 1/(1-p)。例如，当 p=1/4 时，平均每个节点有 1.33 个指针。因此，其空间复杂度为 O(N)，相比普通链表，只是增加了一个不大的常数项开销。
- 有序性与遍历：跳表的最底层本身就是一个完整的有序链表。这使得获取最优报价（头部节点）的操作是 O(1) 的，而遍历市场深度则可以沿着最底层的链表进行，非常高效。
- 天然的并发优势：这是跳表相比于平衡二叉树最显著的工程优势。对跳表的修改（插入/删除）通常只影响到目标节点及其“前驱”节点们的指针。而在平衡树中，一次插入或删除可能引发一系列的旋转，从叶节点一直影响到根节点，导致需要锁住整棵树或至少是树的很大一部分。跳表的局部性修改特性为实现细粒度锁乃至无锁（Lock-Free）操作提供了可能，这是构建高吞吐撮合引擎的技术基石。
系统架构总览
在一个典型的撮合引擎中，订单簿（Order Book）模块位于核心位置。我们通常会为每个交易对（如 BTC/USDT）创建两个独立的跳表实例：一个用于买单（Bids），另一个用于卖单（Asks）。
买单跳表 (Bid SkipList): 按照价格降序排列。这样，跳表的头节点（header.forward[0]）就是最优买单，即“买一价”。
卖单跳表 (Ask SkipList): 按照价格升序排列。这样，跳表的头节点就是最优卖单，即“卖一价”。
整个数据流大致如下：
- 交易网关接收到用户订单请求（RPC/TCP），进行初步校验后，将订单消息（包含用户ID、方向、价格、数量等）放入一个高吞吐的消息队列（如 Kafka 或 LMAX Disruptor）。
- 撮合引擎的核心线程从队列中消费订单消息。
- 对于一个“买单”请求，撮合引擎会查询 Ask SkipList，看是否存在价格小于或等于该买单价的卖单。
- 如果存在，则进行撮合，生成成交记录，并更新 Ask SkipList 中对应价格节点的订单队列（可能部分成交或完全成交，甚至移除该价格节点）。
- 如果不存在匹配的卖单，或者买单未完全成交，则将剩余的买单插入到 Bid SkipList 中。
- “卖单”请求的处理逻辑与此相反。
- “取消订单”请求需要一个额外的 `map[orderID]*Order` 结构来 O(1) 定位到订单对象，再通过订单对象中的价格信息去对应的跳表中执行删除操作。
这个架构的核心在于，两个跳表实例必须能够被撮合线程以极高的效率和并发安全性进行读写。行情发布系统则会定期或在订单簿发生变更时，对这两个跳表进行只读访问，以生成市场深度快照。
核心模块设计与实现
（极客声音）
纸上谈兵没意思，我们直接上代码。这里用 Go 语言作为示例，它的原生并发原语能很好地展示我们的设计思想。首先，定义核心数据结构。
注意：在金融场景，用 `float64` 表示价格是大忌，会因为精度问题导致灾难性后果。实战中必须使用定点数（fixed-point arithmetic）或者高精度数学库（如 `decimal`），这里为了简化，我们暂时用 `float64`。
package orderbook
import (
"container/list"
"math/rand"
"sync"
)
const MAX_LEVEL = 16 // 足够支持 2^16 = 65536 个价格档位
// PriceLevelNode 代表一个价格档位，内部是一个订单队列
type PriceLevelNode struct {
Price float64
Orders *list.List // 同一价格的所有订单，按时间顺序排列 (FIFO)
}
// SkipListNode 是跳表的基本节点
type SkipListNode struct {
forward []*SkipListNode
level *PriceLevelNode
}
// OrderBook 是一个完整的订单簿，包含买卖两侧
type OrderBook struct {
bids *SkipList // 买单，价格降序
asks *SkipList // 卖单，价格升序
// ... 其它辅助结构，如 orderID -> Order 的映射
}
// SkipList 结构
type SkipList struct {
header *SkipListNode
level int
mu sync.RWMutex // 最粗暴的读写锁，作为起点
// comparator for ascending or descending order
isDesc bool
}
// NewSkipList 初始化一个跳表
func NewSkipList(isDescending bool) *SkipList {
return &SkipList{
header: &SkipListNode{
forward: make([]*SkipListNode, MAX_LEVEL),
// header 节点的 level 是 nil
},
level: 0,
isDesc: isDescending,
}
}
这里的关键设计点是，跳表的节点 `SkipListNode` 并不直接存储订单，而是存储一个指向 `PriceLevelNode` 的指针。`PriceLevelNode` 内部包含一个双向链表 `list.List`，用于存放所有挂在同一价格的订单。这种设计避免了在跳表中存储重复的价格节点，极大地节省了空间，并且对同一价格档位的订单增删操作，只需要操作内部的链表，无需改动跳表的结构，效率极高。
插入操作 (Insert)
插入操作是跳表最复杂的部分。它分为两步：1. 查找插入位置；2. 执行插入。
// 随机生成新节点的层高
func (sl *SkipList) randomLevel() int {
level := 0
// p = 1/2
for rand.Intn(2) == 1 && level < MAX_LEVEL-1 {
level++
}
return level
}
// Insert 插入一个新的价格档位
func (sl *SkipList) Insert(price float64) *PriceLevelNode {
sl.mu.Lock()
defer sl.mu.Unlock()
update := make([]*SkipListNode, MAX_LEVEL)
current := sl.header
// 1. 寻找每一层的前驱节点
for i := sl.level; i >= 0; i-- {
for current.forward[i] != nil && sl.compare(current.forward[i].level.Price, price) {
current = current.forward[i]
}
update[i] = current
}
current = current.forward[0]
// 2. 如果价格已存在，直接返回，上层逻辑去操作 PriceLevelNode 里的链表
if current != nil && current.level.Price == price {
return current.level
}
// 3. 如果是新价格，创建新节点并插入
newLevel := sl.randomLevel()
if newLevel > sl.level {
for i := sl.level + 1; i <= newLevel; i++ {
update[i] = sl.header
}
sl.level = newLevel
}
newNode := &SkipListNode{
forward: make([]*SkipListNode, newLevel+1),
level: &PriceLevelNode{
Price: price,
Orders: list.New(),
},
}
for i := 0; i <= newLevel; i++ {
newNode.forward[i] = update[i].forward[i]
update[i].forward[i] = newNode
}
return newNode.level
}
// compare 封装了升序和降序的比较逻辑
func (sl *SkipList) compare(p1, p2 float64) bool {
if sl.isDesc {
return p1 > p2
}
return p1 < p2
}
这段代码展示了经典的跳表插入逻辑。`update` 数组是精髓，它记录了在每一层搜索路径上，需要被修改 `forward` 指针的节点。当找到一个已存在的 `PriceLevelNode` 时，我们直接返回它，让调用方去处理其内部的 `Orders` 链表。如果是新价格，则通过 `randomLevel` 决定新节点的高度，并像拉链一样将其链入跳表中。
注意那个全局的 `sl.mu.Lock()`。这是最简单、最安全的并发控制方式，但它也意味着任何时候只能有一个 goroutine 在写跳表，在高并发下，这里会是性能热点。
删除操作 (Delete)
删除操作同样需要先找到待删除节点的前驱节点们，然后修改指针，将其“跨越”过去。只有当一个价格档位下的所有订单都被取消后，我们才需要从跳表中删除这个 `PriceLevelNode`。
func (sl *SkipList) Delete(price float64) {
sl.mu.Lock()
defer sl.mu.Unlock()
update := make([]*SkipListNode, MAX_LEVEL)
current := sl.header
for i := sl.level; i >= 0; i-- {
for current.forward[i] != nil && sl.compare(current.forward[i].level.Price, price) {
current = current.forward[i]
}
update[i] = current
}
current = current.forward[0]
// 没找到或者价格不匹配
if current == nil || current.level.Price != price {
return
}
// 找到了，修改指针，将其从链表中移除
for i := 0; i <= sl.level; i++ {
if update[i].forward[i] != current {
break // 已经不在高层了
}
update[i].forward[i] = current.forward[i]
}
// 如果删除后最高层变空，降低跳表的整体层高
for sl.level > 0 && sl.header.forward[sl.level] == nil {
sl.level--
}
}
删除逻辑与插入类似，核心都是 `update` 数组。这里有一个收缩层高的逻辑，用于在删除最高层节点后，动态调整跳表的 `level`，避免不必要的遍历开销。
性能优化与高可用设计
全局锁的实现只是万里长征第一步，它无法满足严肃交易系统的性能要求。真正的挑战在于如何拆解这把大锁，提升并发度。
从粗粒度锁到细粒度锁
一个直接的思路是，不要锁整个跳表，而是锁需要被修改的节点。在执行插入或删除时，我们需要修改 `update` 数组中记录的所有前驱节点。我们可以尝试在遍历过程中，对这些前驱节点逐一加锁，操作完成后再解锁。这听起来很美好，但实现起来极其复杂，非常容易导致死锁。例如，两个线程同时插入相邻的价格，可能会出现一个线程锁住了A，等待锁B，而另一个线程锁住了B，等待锁A的情况。
一种更可行的细粒度锁方案是乐观锁（Optimistic Locking）配合节点锁。查找过程不加锁，只有在最后准备修改指针时，才对 `update` 路径上的节点进行加锁，并再次验证这些节点的 `forward` 指针没有被其他线程修改过。如果验证失败（说明在你查找和加锁之间，数据结构被改了），则释放所有锁，从头重试。这种方式在高读、低写的场景下表现优异，但在高写冲突场景下，重试成本会很高。
终极方案：无锁（Lock-Free）跳表
对于延迟极其敏感的系统（如高频交易），我们需要消除锁带来的所有开销，包括锁本身的争抢、上下文切换等。无锁编程是这里的终极武器，其核心是利用CPU提供的原子指令，如“比较并交换”（Compare-and-Swap, CAS）。
无锁跳表的插入逻辑大致如下：
- 查找过程完全无锁，和之前一样，找到每一层的前驱节点 `update[i]`。
- 创建一个新的 `SkipListNode`。
- 从最底层（level 0）开始，使用CAS操作尝试将 `update[0].forward[0]` 的指针从其旧值（你查找到时的值）原子地更新为指向你的新节点。
- 如果CAS成功，说明在你操作期间没有其他线程修改这个指针，你成功地将新节点链入了最底层。然后你继续向上层（level 1, 2, ...）尝试用CAS更新指针。
- 如果CAS失败，说明有“竞争者”抢先修改了指针。这时，你不能继续操作，必须放弃，从失败的那一层重新开始查找和CAS操作。
删除操作则更为复杂。直接移除一个节点可能会导致正在遍历该节点的其他线程“掉链子”。无锁删除通常采用“标记-删除”两阶段法：首先，使用CAS将节点的一个状态位置为“逻辑删除”（marked for deletion），然后再在后续的某个时刻，由另一个线程（或当前线程）来物理地移除（修改指针绕过它）。
工程血泪坑：无锁编程的复杂性远超想象。你需要处理 ABA 问题（一个值从A变为B又变回A，CAS无法察觉中间的变化），还要有可靠的内存回收机制（如 Epoch-based reclamation 或 Hazard Pointers），否则被移除的节点内存无法安全释放。在绝大多数场景下，一个精心设计的、基于细粒度锁的并发跳表，其性能已经足够好，且可维护性远高于无锁实现。不要为了炫技而选择无锁，除非你的性能压测数据明确告诉你，锁是最后的瓶颈。
架构演进与落地路径
一个新交易系统上线，不可能一步到位就上最复杂的无锁跳表。合理的演进路径至关重要。
- 第一阶段：原型验证与冷启动。 使用最简单的全局 `RWMutex` 锁。这个版本实现简单，正确性容易保证。在系统上线初期，交易量不大时，它的性能完全够用。同时，这个版本可以作为后续优化的性能基线（Benchmark）。
- 第二阶段：性能瓶颈出现。 随着交易量上升，你会通过 Profiling 工具（如 Go 的 pprof）发现，撮合线程大量时间阻塞在 `sl.mu.Lock()` 上。此时，证明全局锁已成为瓶颈，需要进行优化。这个阶段，可以考虑引入分段锁（类似 ConcurrentHashMap 的思想，对价格区间进行分段加锁），或者尝试实现基于乐观锁的细粒度加锁方案。
- 第三阶段：追求极致性能。 如果你的业务是华尔街级别的HFT，或者是头部交易所的核心撮合，那么每微秒的延迟都价值连城。此时，投入研发资源去攻克无锁跳表是值得的。这通常需要团队里有对操作系统底层、内存模型和并发理论有极深造诣的专家来主导。可以参考学术界成熟的论文实现，如 Herlihy and Shavit 的《The Art of Multiprocessor Programming》一书中描述的算法。
最终，数据结构的选择永远是 Trade-off 的艺术。跳表以其 O(log N) 的优秀期望性能、天然的有序性和无与伦比的并发改造潜力，在高性能订单簿的实现中胜出。但从一个简单的带锁实现，到工程上健壮、高效的并发版本，再到理论上完美的无锁版本，每一步都充满了挑战。理解其背后的原理，并根据业务的实际需求选择合适的演进阶段，才是一位首席架构师应有的决策智慧。
延伸阅读与相关资源
-
想系统性规划股票、期货、外汇或数字币等多资产的交易系统建设，可以参考我们的
交易系统整体解决方案。 -
如果你正在评估撮合引擎、风控系统、清结算、账户体系等模块的落地方式，可以浏览
产品与服务
中关于交易系统搭建与定制开发的介绍。 -
需要针对现有架构做评估、重构或从零规划，可以通过
联系我们
和架构顾问沟通细节，获取定制化的技术方案建议。