撮合引擎 OrderBook 的 100ns 之路：无锁 RingBuffer + 伪共享消除，Go 1.22 下单 op 11ns

作者定位十年后端 / 高频交易链路前两篇写了自研 Scheduler 和 size-class 无锁对象池这篇是三部曲终章——撮合引擎的心脏 OrderBook 怎么在 Go 里做到 100ns 内匹配、RSS Δ 12MB、GC pause 0.03ms。代码可直接拷Go 1.22压测 16C64G。一、先把事故摆出来为什么不能用 map slice 搓 OrderBook2025 年大促压测我们期权撮合引擎跑 200 万 QPS 限价单pprof 里两块最刺眼runtime.mapaccess2_fast64 — 占 cpu 18% // price→[]Order 的 map 查档 runtime.growSlice — 占 cpu 11% // 每档 slice 追加根因三条map 查档有 hash 计算 bucket 遍历单步 40~60ns已经吃掉一半预算每档[]Order追加触发 growSlice撮合高峰每档 3~5 单grow 频率高GC scan map slice 的 backing arrayOrderBook 常驻 50 万档位时STW 一次 2~3ms连续 3 次 STW 就能让 P99 从 80ns 飙到 2μs 结论先给撮合引擎的 OrderBook 不是数据结构题是内存布局题。LMAX Disruptor 那套预分配 定长槽 序号取模的思路搬到 OrderBook 上就是——每档不再是 slice而是一个固定容量的 RingBuffer 槽位价格→档位用数组下标而不是 map。二、架构选型价格→档位怎么存期权/币圈这类场景有个关键特征报价盘口集中在最新价 ±N 档比如 BTC 在 90000 附近活跃档位只在 89990~90010 这 20 档。这意味着我们可以方案查档追加GC 压力map[int64][]Orderhash 40nsgrowSlice高array[priceIndex]*RingBucketpriceIndex (price - base) / tick下标 2ns定长槽位满则新 RingBucket 链零预分配无 slice grow核心思路把价格编码成数组下标用basePrice tickSize做坐标变换// book/priceidxas.gopackage bookconst TickSize 100 // 100 聪一档BTC 场景// priceIdx: 0 表示 basePrice 那档±方向各自扩// 实际盘口用两个半区askSide [0..N) bidSide [N..2N)func priceToIdx(base, price int64) int { offset : (price - be) / TickSize return int(offset) }func idxToPrice(base int64, idx int) int64 { return base int64(idx)*TickSize }三、核心结构每档一个 mini RingBuffer不搞全局一个大 RingBuffer那是 Disruptor 干的事而是每档一个 mini RingBuffer——因为撮合语义是按价格优先同价按时间优先同档内 FIFO 即可。// book/bucket.gopackage bookimport ( sync/atomic _ unsafe)const ( bucketCap 64 // 每档预分配 64 单够 99% 场景满了就 chain 新 bucket)// Order 精简到 32B3 个 int64 1 个 uint32 paddingtype Order struct { OrderID int64 // 8B Price int64 // 8B Amount int64 // 8B Seq uint32 // 4B Side uint8 // 1B _ [3]byte // padding 到 8 对齐32B 整}// bucket 是每档的 mini RingBuffertype bucket struct { // 热区64B 刚好一 cache lineseq / head / tail 三个变量一起缓存 seq uint64 // 写入序号自增取模得 slot原子 head uint32 // 消费游标 tail uint32 // 生产游标 _ [5]uint32 // padding 到 64B避免和 orders[0] 伪共享 // 定长槽位预分配永不 grow orders [bucketCap]Order next *bucket // 满了 chain 新 bucket}⚠️伪共享false sharing这一刀必须切seq/head/tail三个变量如果和orders[0]挨着Producer 写 seq、Consumer 读 orders[0]两个 CPU 核会反复把同一 cache line64B在 L1 间踢皮球单 op 能从 11ns 飙到 47ns。上面[5]uint32padding 把热区撑到 64B 单独占一条 cache lineorders从下一条 line 开始Producer/Consumer 各占各的 line。验证 padding 有没有生效// book/padding_test.gofunc TestBucketLayout(t *testing.T) { var b bucket seqOff : unsafe.Offsetof(b.seq) // 0 ordersOff : unsafe.Offsetof(b.orders) // 应该是 64 if ordersOff ! 64 { t.Fatalf(padding failed: orders at %d, expect 64, ordersOff) } }四、写入路径无锁追加同档内同一档位可能有多个 Goroutine 同时挂单比如 BTC 90000000 这档同一毫秒 5 个用户各挂 1 单需要atomic.AddUint64抢 seq// book/bucket.go 续func (b *bucket) push(o Order) (ok bool, full *bucket) { // 抢 seqLMAX Disruptor 的 claim 逻辑简化版 s : atomic.AddUint64(b.seq, 1) - 1 pos : s % bucketCap // 检查是否已满head 没追上来的话seq-head bucketCap 就是满 head : atomic.LoadUint32(b.head) if s-head bucketCap { // 本 bucket 满返回新 bucket 让调用方 chain return false, b } b.orders[pos] o // 写完成推进 tailRelease 语义这里用 Store monotonic 就够了 atomic.StoreUint32(b.tail, uint32(s1)) return true, nil}读取路径更简单——撮合引擎里 Consumer 只有一个 Goroutine 按档扫因为同侧撮合必须串行才能保证价格优先所以head不需要原子读单 Goroutine 自增即可func (b *bucket) pop() (Order, bool) { if b.head b.tail { return Order{}, false } o : b.orders[b.head%bucketCap] b.head return o, true}关键认知OrderBook 的无锁不是全路径无锁而是写路径挂单无锁、读路径撮合扫档单 Goroutine 无竞争。这才是撮合场景的真实并发模型——挂单千军万马撮合按价格串行扫。很多同学一上来就想把撮合也并行化那是跑偏的价格优先语义不允许。五、OrderBook 本体双向盘口 best 指针// book/orderbook.gopackage bookimport ( sync sync/atomic)const ( sideAsk 0 sideBid 1 maxDists 4096 // 盘口半径 4096 档够 BTC 场景)type OrderBook struct { basePrice int64 // 基准价priceIdx (price-base)/tick asks []*bucket // [0..maxDists) ask 档位 bids []*bucket // [0..maxDists) bid 档位 bestAsk int32 // 原子当前最优 ask 档 idx bestBid int32 // 原子当前最优 bid 档 idx mu sync.Mutex // 只在扩展 asks/bids slice 时用}func NewOrderBook(basePrice int64) *OrderBook { ob : OrderBook{ basePrice: basePrice, asks: make([]*bucket, maxDists), bids: make([]*bucket, maxDists), bestAsk: maxDists, // 初始无效 bestBid: 0, } // 预分配中心几档减少运行时 malloc for i : 0; i 32; i { ob.asks[i] bucket{} ob.bids[i] bucket{} } return ob }挂单入口LimitOrder限价单func (ob *OrderBook) PlaceLimit(o Order) { idx : priceToIdx(ob.basePrice, o.Price) var side int if o.Side A { // Ask side sideAsk } else { side sideBid } retry: var b *bucket if side sideAsk { b ob.getAsk(idx) } else { b ob.getBid(idx) } if b nil { b ob.allocBucket(side, idx) } ok, full : b.push(o) if !ok { // 本 bucket 满chain 新 bucket 到 full.next重试 full.next bucket{} goto retry } // 更新 best pointer原子 CAS避免两个挂单 Goroutine 竞态 if side sideAsk { for { old : atomic.LoadInt32(ob.bestAsk) if idx int(old) old ! maxDists { break } if atomic.CompareAndSwapInt32(ob.bestAsk, old, int32(idx)) { break } } } else { for { old : atomic.LoadInt32(ob.bestBid) if idx int(old) old ! 0 { break } if atomic.CompareAndSwapInt32(ob.bestBid, old, int32(idx)) { break } } } }func (ob *OrderBook) getAsk(idx int) *bucket { if idx len(ob.asks) { return nil } return ob.asks[idx] }func (ob *OrderBook) getBid(idx int) *bucket { if idx len(ob.bids) { return nil } return ob.bids[idx] }func (ob *OrderBook) allocBucket(side, idx int) *bucket { ob.mu.Lock() defer ob.mu.Unlock() b : bucket{} if side sideAsk { // 扩展 asks slice懒扩容预分配半径外的档 if idx len(ob.asks) { newAsks : make([]*bucket, idx256) copy(newAsks, ob.asks) ob.asks newAsks } ob.asks[idx] b } else { if idx len(ob.bids) { newBids : make([]*bucket, idx256) copy(newBids, ob.bids) ob.bids newBids } ob.bids[idx] b } return b }六、撮合核心扫 best → 成交 → 推进 head撮合 Goroutine 唯一死循环扫bestAsk/bestBid// book/match.gopackage bookfunc (ob *OrderBook) MatchLoop(matchCh chan- Trade) { for { bestAsk : atomic.LoadInt32(ob.bestAsk) bestBid : atomic.LoadInt32(ob.bestBid) // 跨盘口检查bestBid bestAsk 才成交bid 价 ≥ ask 价 askPrice : idxToPrice(ob.basePrice, int(bestAsk)) bidPrice : idxToPrice(ob.basePrice, int(bestBid)) if bidPrice askPrice { // 无交叉歇 1μs 再扫生产里用 futex/cond 唤醒更准 continue } // 取出 ask 首单 bid 首单 askB : ob.asks[bestAsk] bidB : ob.bids[bestBid] aOrder, aOk : askB.pop() bOrder, bOk : bidB.pop() if !aOk || !bOk { // 某一档空了推进 best pointer ob.advanceBest() continue } // 成交价格按 ask价格优先语义量取 min fillAmt : min(aOrder.Amount, bOrder.Amount) trade : Trade{ Price: aOrder.Price, Amount: fillAmt, AskOID: aOrder.OrderID, BidOID: bOrder.OrderID, } matchCh - trade // 剩余量回写市价单剩余直接撤限价单剩余挂回原档——这里简化假设全成交 } }func (ob *OrderBook) advanceBest() { // 扫 ask side把 headtail 的空档跳过 for i : atomic.LoadInt32(ob.bestAsk); i int32(len(ob.asks)); i { b : ob.asks[i] if b ! nil atomic.LoadUint32(b.head) atomic.LoadUint32(b.tail) { atomic.StoreInt32(ob.bestAsk, i) break } } // bid side 对称从大到小扫}七、压测数据16C64GGo 1.22200 万 QPS 限价单混合读写指标mapslice 旧实现本文 RingBucket单 op挂单67ns11ns单 op撮合一笔120ns38nsGC pause / 5s2.3ms0.03msRSS Δ50 万档预热后480MB12MBP99 撮合延迟2.1μs89ns 11ns 这个数字怎么来的atomic.AddUint64(4ns) seq-head边界检查(2ns) orders[pos]写入(3ns) 返回(2ns)Go 1.22 在 16C Ice Lake 上实测就是这个量级。关键变量是去掉了 map hash growSlice GC scan这三个大头。和 Java 侧 LMAX Disruptor单 op 6ns 量级比还有差距主要差在 Go 的atomic.AddUint64比 JVMContendedUnsafe重一点但 11ns 对 Go 生态已经够打——Rust 侧用crossbeam::RingQueue单 op 也是 9~13ns 区间。八、Metrics 埋点// book/metrics.govar ( bookPushTotal promauto.NewCounterVec( prometheus.CounterOpts{ Namespace: match, Name: push_total, }, []string{side}) // ask / bid bookDepth promauto.NewGaugeVec( prometheus.GaugeOpts{ Namespace: match, Name: depth, }, []string{side, price_idx}) matchLatency promauto.NewHistogram( prometheus.HistogramOpts{ Namespace: match, Name: match_latency_ns, Buckets: []float64{50, 100, 200, 500, 1000, 5000}, }) )看板核心报警match_latency_ns{bucket5000}非零 → 撮合 Goroutine 被调度延迟卡了检查GOMAXPROCS是否被 cgroup 限match_depth{sideask}某档 depth 持续 1000 → 买盘/卖盘单边积压可能是做市商异常告警给风控九、诚实说瓶颈什么时候不该这么搞十年老哥老规矩——这方案不是万金油盘口半径不可预测的场景比如垃圾股成交价跳 10 倍不适合basePrice idx编码得回退到array[price]大数组或者 BTree同档并发极高 每微秒 100 单atomic.AddUint64抢 seq 会成为 bottleneck得给每档再分 shard比如 4 个 sub-bucket 轮询需要持久化重放的OrderBook 内存态丢了就得回放 Kafka这套架构里加个WAL前缀写 etcd/RocksDB 就行但那是另一篇文章继续用 sync.Map / mapmutex 搓撮合的团队如果 QPS 没到 50 万、P99 没到 μs 级别急着重构——能跑和能打之间差的是业务阶段不是技术高低。我们这链路 80 万 QPS 起步才值得花这 800 行 Go。十、代码结构match-engine/ ├── main.go # 压测入口200 万 QPS 混合挂单撮合 ├── book/ │ ├── orderbook.go # OrderBook 本体双向盘口 best pointer │ ├── bucket.go # mini RingBuffer 每档伪共享 padding │ ├── priceidx.go # basePrice tick 坐标编码 │ ├── match.go # 撮合循环bestAsk/bestBid 扫档 │ ├── metrics.go # Prometheus 埋点 │ └── padding_test.go # 64B cache line 验证 ├── bench/ │ └── bench_test.go # go test -bench. -benchtime10s -count3 └── README.md完整可跑版本含 WAL 前缀 Kafka 重放示例评论区留求撮合源码老规矩私发避免吞链。参考资料https://www.moyubuhuang.com/keji/202607/42765.html