Xây dựng Engine khớp lệnh giao dịch từ con số 0 bằng ngôn ngữ Go

Mỗi sàn giao dịch — dù là chứng khoán, tiền mã hóa (crypto) hay hàng hóa — đều sở hữu một "trái tim" gọi là engine khớp lệnh (matching engine). Đây là thành phần chịu trách nhiệm nhận các lệnh mua và bán, tìm kiếm các cặp lệnh tương thích và thực hiện giao dịch. Mặc dù đóng vai trò nền tảng và cực kỳ quan trọng, cơ chế hoạt động bên trong của các engine này hiếm khi được thảo luận công khai, bởi hầu hết các triển khai thực tế đều nằm sau bức tường sở hữu độc quyền.

Bài viết này sẽ đi sâu vào MatchEngine, một engine khớp lệnh mã nguồn mở được viết bằng ngôn ngữ Go. Chúng ta sẽ khám phá thuật toán cốt lõi, các cấu trúc dữ liệu đằng sau một "sổ lệnh" (order book), và các quyết định thiết kế giúp cho mã nguồn nhỏ gọn và dễ hiểu.

Tại sao lại chọn ngôn ngữ Go?

Go là sự lựa chọn tự nhiên cho hệ thống kiểu này vì những lý do sau:

• Goroutines và Mutexes: Đảm bảo xử lý đồng thời (concurrency) một cách trực tiếp mà không gặp phải sự phức tạp của các async runtime.
• Thư viện chuẩn phong phú: Đủ đầy đủ để xây dựng dự án mà không cần bất kỳ phụ thuộc bên ngoài nào.
• Biên dịch thành tệp nhị phân duy nhất: Việc triển khai (deployment) trở nên vô cùng đơn giản.
• Tính đơn giản: Giữ cho mã nguồn dễ đọc, điều rất quan trọng đối với một dự án giáo dục mã nguồn mở.

Mô hình miền (Domain Model)

Một engine khớp lệnh hoạt động dựa trên hai thực thể cơ bản: lệnh (orders) và giao dịch (trades).

Lệnh (Orders)

Một lệnh đại diện cho ý định của một người tham gia thị trường muốn mua hoặc bán một lượng tài sản nhất định tại một mức giá cụ thể (hoặc bất kỳ mức giá nào đối với lệnh thị trường).

type Order struct {
    ID        string
    Side      Side      // Buy hoặc Sell
    Type      OrderType // Limit hoặc Market
    Price     float64
    Quantity  float64
    Remaining float64
    Timestamp time.Time
}

Trường Remaining (còn lại) là chìa khóa. Khi một lệnh được khớp một phần (partial fill), Remaining sẽ giảm xuống trong khi Quantity giữ nguyên kích thước ban đầu. Sự tách biệt này giúp dễ dàng theo dõi tiến trình khớp lệnh mà không làm mất ý định ban đầu.

Hai loại lệnh được hỗ trợ:

• Lệnh giới hạn (Limit orders): Chỉ định mức giá mua tối đa hoặc mức giá bán tối thiểu. Chúng sẽ nằm trong sổ lệnh nếu không tìm thấy lệnh phù hợp ngay lập tức.
• Lệnh thị trường (Market orders): Được thực thi ngay lập tức tại mức giá tốt nhất hiện có. Chúng không bao giờ vào sổ lệnh — phần nào không được khớp sẽ bị hủy bỏ.

Giao dịch (Trades)

Một giao dịch là kết quả của việc khớp hai lệnh:

type Trade struct {
    BuyOrderID  string
    SellOrderID string
    Price       float64
    Quantity    float64
    Timestamp   time.Time
}

Đơn giản và bất biến (immutable). Khi một giao dịch được tạo ra, nó trở thành một sự kiện lịch sử.

Sổ lệnh (Order Book)

Sổ lệnh là cấu trúc dữ liệu trung tâm. Nó duy trì hai danh sách đã được sắp xếp:

• Bids (Lệnh mua): sắp xếp theo giá giảm dần, sau đó theo thời gian tăng dần.
• Asks (Lệnh bán): sắp xếp theo giá tăng dần, sau đó theo thời gian tăng dần.

Cơ chế sắp xếp này triển khai nguyên tắc ưu tiên giá-thời gian (price-time priority) (còn được gọi là khớp lệnh FIFO):

1. Mức giá "mạnh nhất" (aggressive) luôn được khớp trước.
2. Trong các lệnh có cùng mức giá, lệnh đến sớm hơn sẽ thắng.

Order Book cho cặp BTC/USD
─────────────────────────────
  Bids (Mua)    │  Asks (Bán)
─────────────────────────────
  10 @ 50200    │   5 @ 50300
   5 @ 50100    │   8 @ 50400
   3 @ 50000    │  12 @ 50500
─────────────────────────────
     Best Bid: 50200
     Best Ask: 50300
     Spread:   100

Các phương thức BestBid() và BestAsk() trả về phần tử đứng đầu của mỗi phía trong O(1) vì các slice luôn được sắp xếp. Spread — khoảng cách giữa giá mua tốt nhất và giá bán tốt nhất — là một chỉ số quan trọng về thanh khoản của thị trường.

Tại sao dùng Slice đã sắp xếp thay vì Cây (Tree)?

Nhiều engine khớp lệnh sản xuất thực tế sử dụng cây đỏ-đen (red-black trees) hoặc skip list để có độ phức tạp chèn là O(log n). Chúng tôi chọn sử dụng slice đã sắp xếp với sort.SliceStable vì một lý do: tính rõ ràng. Đây trước hết là một dự án giáo dục. Sự đánh đổi thuật toán là chấp nhận được đối với khối lượng lệnh trung bình, và mã nguồn dễ hiểu ngay lập tức với bất kỳ ai đọc nó.

Việc nâng cấp lên cấu trúc dựa trên cây sau này là một thay đổi cục bộ — nó chỉ ảnh hưởng đến phương thức AddOrder.

Thuật toán khớp lệnh (Matching Algorithm)

Khi một lệnh mới đến, engine sẽ cố gắng khớp nó với phía đối diện của sổ lệnh. Logic này đối xứng cho cả mua và bán, hãy cùng theo dõi một lệnh mua:

Lệnh đến: MUA 8 BTC @ THỊ TRƯỜNG (MARKET)

Phía bán của sổ lệnh:
  s1: BÁN 5 @ 50000
  s2: BÁN 5 @ 50100

Bước 1: Khớp với s1
  → Giao dịch: 5 BTC @ 50000
  → s1 đã được khớp đầy đủ (xóa khỏi sổ)
  → Lệnh đến còn lại: 3

Bước 2: Khớp với s2
  → Giao dịch: 3 BTC @ 50100
  → s2 được khớp một phần (còn lại: 2, giữ lại trong sổ)
  → Lệnh đến còn lại: 0 (đã khớp đầy đủ)

Kết quả: 2 giao dịch được thực hiện

Vòng lặp khớp lệnh cốt lõi rất gọn gàng:

func (e *Engine) matchBuy(book *orderbook.OrderBook, order *model.Order) []model.Trade {
    var trades []model.Trade

    for !order.IsFilled() {
        bestAsk := book.BestAsk()
        if bestAsk == nil {
            break
        }
        if order.Type == model.Limit && bestAsk.Price > order.Price {
            break
        }
        trade := executeTrade(order, bestAsk, bestAsk.Price)
        trades = append(trades, trade)
    }

    return trades
}

Ba điều kiện thoát vòng lặp:

1. Lệnh đến được khớp đầy đủ.
2. Phía đối diện của sổ lệnh trống.
3. Đối với lệnh giới hạn, giá không còn chéo nhau (giá bán tốt nhất quá đắt).

Lệnh thị trường sẽ bỏ qua điều kiện 3 — chúng tiêu thụ bất kỳ thanh khoản nào sẵn có bất chấp giá cả.

Thực thi giao dịch (Trade Execution)

Hàm executeTrade xử lý việc khớp thực tế:

func executeTrade(buyOrder, sellOrder *model.Order, price float64) model.Trade {
    quantity := min(buyOrder.Remaining, sellOrder.Remaining)
    buyOrder.Remaining -= quantity
    sellOrder.Remaining -= quantity

    return model.Trade{
        BuyOrderID:  buyOrder.ID,
        SellOrderID: sellOrder.ID,
        Price:       price,
        Quantity:    quantity,
        Timestamp:   time.Now(),
    }
}

Khối lượng khớp luôn là giá trị nhỏ nhất của hai lượng còn lại. Điều này tự nhiên xử lý cả khớp đầy đủ và khớp một phần mà không cần bất kỳ logic đặc biệt nào.

Xác định giá

Giá giao dịch luôn là giá của lệnh đang chờ (resting order) — lệnh đã có trong sổ lệnh. Đây là hành vi chuẩn của sàn giao dịch: phía thụ động (maker) xác định giá, và phía chủ động (taker) chấp nhận nó.

An toàn luồng (Thread Safety)

Engine sử dụng sync.Mutex để tuần tự hóa quyền truy cập vào các sổ lệnh:

type Engine struct {
    mu     sync.Mutex
    books  map[string]*orderbook.OrderBook
    trades []model.Trade
}

Mọi phương thức công khai (SubmitOrder, CancelOrder, GetTrades, GetOrderBook) đều phải lấy khóa trước khi truy cập trạng thái được chia sẻ. Đây là một lựa chọn có chủ đích vì sự đơn giản — một khóa duy nhất cho mỗi thể hiện engine.

Để đạt được thông lượng (throughput) cao hơn, bạn có thể:

• Sử dụng khóa theo cặp tiền (một mutex cho mỗi sổ lệnh) để cho phép khớp lệnh song song trên các cặp khác nhau.
• Sử dụng bộ đệm vòng không khóa (lock-free ring buffer) cho đầu ra giao dịch.
• Chia nhỏ engine theo cặp tiền trên nhiều goroutine.

Nhưng để đảm bảo tính chính xác và rõ ràng, một mutex duy nhất là điểm khởi đầu đúng đắn.

Hỗ trợ đa cặp tiền (Multi-Symbol)

Engine duy trì một map từ ký hiệu tiền tệ đến sổ lệnh:

books map[string]*orderbook.OrderBook

Sổ lệnh được tạo ra một cách lười biếng (lazily) khi lần đầu tiên được sử dụng. Các cặp tiền tệ hoàn toàn cô lập — một giao dịch trong BTC/USD không có ảnh hưởng gì đến sổ ETH/USD.

Hủy lệnh (Order Cancellation)

Việc hủy lệnh khá đơn giản — tìm lệnh theo ID và xóa nó:

func (e *Engine) CancelOrder(symbol, orderID string) bool {
    e.mu.Lock()
    defer e.mu.Unlock()

    book, ok := e.books[symbol]
    if !ok {
        return false
    }
    return book.RemoveOrder(orderID)
}

Giá trị trả về boolean báo cho người gọi biết lệnh có tồn tại hay không. Việc hủy một lệnh đã được khớp đầy đủ hoặc đã bị hủy sẽ trả về false.

Đường đi phía trước

Đây là một nền tảng vững chắc, nhưng một hệ thống sản xuất thực tế sẽ cần thêm nhiều thứ:

• Lưu trữ bền vững: Ghi trạng thái giao dịch và lệnh vào cơ sở dữ liệu hoặc nhật ký ghi trước (write-ahead log) để khôi phục sau sự cố.
• Độ chính xác thập phân: Thay thế float64 bằng kiểu thập phân có dấu phẩy tĩnh (fixed-point decimal) như shopspring/decimal để tránh lỗi làm tròn số thực trong tính toán tài chính.
• Các loại lệnh nâng cao: Lệnh dừng (stop orders), stop-limit, fill-or-kill (FOK), immediate-or-cancel (IOC), và good-till-cancelled (GTC) với thời hạn.
• Luồng sự kiện (Event streaming): Xuất bản các cập nhật sổ lệnh và giao dịch đến hàng đợi tin nhắn (Kafka, NATS) cho các hệ thống tiêu thụ phía sau.
• API REST/gRPC: Tiếp xúc engine qua mạng để clients có thể gửi lệnh theo chương trình.
• Đánh giá hiệu năng (Benchmarking): Thêm benchmark Go để đo thông lượng (lệnh/giây) và độ trễ (thời gian khớp).

Kết luận

Một engine khớp lệnh không hề bí ẩn. Bản chất của nó chỉ là một cấu trúc dữ liệu được sắp xếp và một vòng lặp so sánh giá cả. Sự phức tạp trong các hệ thống sản xuất thực tế đến từ cơ sở hạ tầng xung quanh — mạng, lưu trữ, giám sát và tuân thủ quy định — chứ không phải từ chính logic khớp lệnh.

MatchEngine loại bỏ sự phức tạp đó để phơi bày thuật toán trong dạng tinh khiết nhất. Hãy fork nó, mở rộng nó, phá vỡ nó và học hỏi từ nó. Đó chính là mục đích của mã nguồn mở.

GitHub: https://github.com/iwtxokhtd83/MatchEngine Giấy phép: MIT