撮合引擎实现原理

概述

撮合引擎是交易系统中的核心组件，负责实现买卖订单的成交。它通过价格优先、时间优先的原则，确保买单价格大于等于卖单价格时双方成交。

关键概念

撮合交易：允许买卖双方各自提交订单并报价，按价格和时间优先级顺序成交。
价格优先、时间优先：买盘价格从高到低排序，卖盘价格从低到高排序。
订单：包含价格、数量、方向（买或卖）等信息。
订单簿(OrderBook)：存储买卖盘信息，确保订单按价格排序，好的订单簿结构设计是撮合效率的一个关键，这里采用红黑树实现，因为它是一种自平衡的二叉排序树，插入和删除的效率都是O(logN)。

订单类设计

Go语言实现订单类Order如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


import (
    "github.com/shopspring/decimal"
)
    
    type Order struct {
    SequenceId int64
    Direction  Direction
    Price      decimal.Decimal
    Amount     decimal.Decimal
}

订单方向枚举

Go语言实现订单方向枚举如下：

1
2
3
4
5
6


type Direction int

const (
    BUY Direction = iota
    SELL
)

订单簿(OrderBook)设计

使用红黑树实现，这里引入了github.com/emirpasic/gods这个包。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


import (
    "github.com/emirpasic/gods/trees/redblacktree"
    "github.com/emirpasic/gods/utils"
    "github.com/shopspring/decimal"
)

type OrderKey struct {
    Price decimal.Decimal
    Id    int64
}

type OrderBook struct {
    *redblacktree.Tree
}

func NewOrderBook(direction Direction) *OrderBook {
    switch direction {
    case BUY:
        return &OrderBook{Tree: redblacktree.NewWith(BuyComparator)}
    case SELL:
        return &OrderBook{Tree: redblacktree.NewWith(SellComparator)}
    }
    return nil
}

func BuyComparator(a, b interface{}) int {
    order1 := a.(OrderKey)
    order2 := b.(OrderKey)
    
    cmp := order2.Price.Cmp(order1.Price)
    if cmp == 0 {
        return utils.Int64Comparator(order1.Id, order2.Id)
    }
    return cmp
}

func SellComparator(a, b interface{}) int {
    order1 := a.(OrderKey)
    order2 := b.(OrderKey)
    
    cmp := order1.Price.Cmp(order2.Price)
    if cmp == 0 {
        return utils.Int64Comparator(order1.Id, order2.Id)
    }
    return cmp
}

func (b *OrderBook) Add(order *Order) {
    b.Tree.Put(OrderKey{Price: order.Price, Id: order.SequenceId}, order)
}

func (b *OrderBook) Remove(order *Order) {
	b.Tree.Remove(OrderKey{Price: order.Price, Id: order.SequenceId})
}

func (b *OrderBook) GetFirst() *Order {
    iterator := b.Tree.Iterator()
    if iterator.First() {
        return iterator.Value().(*Order)
    }
    return nil
}

func (b *OrderBook) GetLast() *Order {
    iterator := b.Tree.Iterator()
    if iterator.Last() {
        return iterator.Value().(*Order)
    }
    return nil
}

撮合引擎(MatchEngine)设计

撮合引擎包含买盘和卖盘，以及最新成交价。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


import (
	"github.com/shopspring/decimal"
)

type MatchEngine struct {
    buyBook     *OrderBook
    sellBook    *OrderBook
    marketPrice decimal.Decimal
}

func NewMatchEngine() *MatchEngine {
    return &MatchEngine{
        buyBook:     NewOrderBook(BUY),
        sellBook:    NewOrderBook(SELL),
        marketPrice: decimal.Zero,
    }
}

func (me *MatchEngine) ProcessOrder(order *Order) *MatchResult {
    switch order.Direction {
    case BUY:
        return me.processOrder(order, me.sellBook, me.buyBook)
    case SELL:
        return me.processOrder(order, me.buyBook, me.sellBook)
    default:
        panic("Invalid direction")
    }
}

处理订单逻辑

处理订单时，尝试在对手盘匹配合适的订单，如果匹配成功则成交，否则将订单放入订单簿。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


func (me *MatchEngine) processOrder(takerOrder *Order, makerBook, anotherBook *OrderBook) *MatchResult {
    result := &MatchResult{TakerOrder: takerOrder}
    for {
        makerOrder := makerBook.GetFirst()
        if makerOrder == nil {
            break
        }
        if takerOrder.Direction == BUY && takerOrder.Price.Cmp(makerOrder.Price) < 0 {
            break
        } else if takerOrder.Direction == SELL && takerOrder.Price.Cmp(makerOrder.Price) > 0 {
            break
        }
    
        me.marketPrice = makerOrder.Price
        matchedAmount := decimal.Min(takerOrder.Amount, makerOrder.Amount)
        result.MatchRecords = append(result.MatchRecords, &MatchRecord{Price: makerOrder.Price, Amount: matchedAmount, TakerOrder: takerOrder, MakerOrder: makerOrder})
        takerOrder.Amount = takerOrder.Amount.Sub(matchedAmount)
        makerOrder.Amount = makerOrder.Amount.Sub(matchedAmount)
        if makerOrder.Amount.Sign() == 0 {
            makerBook.Remove(makerOrder)
        }
        if takerOrder.Amount.Sign() == 0 {
            break
        }
    }
    if takerOrder.Amount.Sign() > 0 {
        anotherBook.Add(takerOrder)
    }
    return result
}

撮合结果(MatchResult)和撮合记录(MatchRecord)设计

撮合结果记录撮合匹配记录，包括成交价格、数量等信息。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


type MatchResult struct {
    TakerOrder   *Order
    MatchRecords []*MatchRecord
}

type MatchRecord struct {
    Price      decimal.Decimal
    Amount     decimal.Decimal
    TakerOrder *Order
    MakerOrder *Order
}

测试撮合引擎

可以通过构造一系列订单并输入到撮合引擎来验证其功能。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func TestMatchEngine(t *testing.T) {
    me := NewMatchEngine()
    orders := []*Order{
        {SequenceId: 1, Direction: BUY, Price: decimal.NewFromFloat(2082.34), Amount: decimal.NewFromFloat(1)},
        {SequenceId: 2, Direction: SELL, Price: decimal.NewFromFloat(2087.6), Amount: decimal.NewFromFloat(2)},
        {SequenceId: 3, Direction: BUY, Price: decimal.NewFromFloat(2088), Amount: decimal.NewFromFloat(1)},
        {SequenceId: 4, Direction: SELL, Price: decimal.NewFromFloat(2082), Amount: decimal.NewFromFloat(1)},
    
        // 添加更多订单...
    }
    for _, order := range orders {
        result := me.ProcessOrder(order)
        // 打印或处理撮合结果...
        log.Printf("takeOrder: %+v, matchRecords: %+v", result.TakerOrder, result.MatchRecords)
    }
}

小结

实现撮合引擎的关键在于设计合理的数据结构来高效管理订单，并正确实现撮合逻辑。在实际应用中，还需要考虑更多的因素，如并发处理、订单的时效性、手续费计算等，以满足交易所的实际业务需求。同时，要不断进行测试和优化，确保撮合引擎的性能和稳定性。

参考文献： https://liaoxuefeng.com/blogs/all/2021-12-10-exchange-match-engine/index.html

文章目录

概述