Разработка торгового движка (matching engine)

Разработка торгового движка (matching engine)

Matching engine — это ядро любой биржи. Он принимает ордера, сводит покупателей с продавцами и генерирует трейды. Это самый производительный и самый критический компонент: задержка в microseconds имеет значение, ошибка в логике ценообразования — катастрофа. Разберём архитектуру изнутри.

Что такое matching engine

Функции

1. Приём ордеров: новый ордер валидируется и направляется в правильный order book
2. Matching: поиск совместимых ордеров, генерация трейдов
3. Order management: partial fills, cancellations, expiry
4. Публикация событий: трейды, обновления стакана → downstream системы

Всё это должно происходить последовательно (single-threaded matching core) для предотвращения race conditions. Параллельность добавляется на уровне разных торговых пар — каждый символ имеет собственный thread/core.

Price-Time priority (FIFO)

Стандартный алгоритм matching:

1. Price priority: ордер с лучшей ценой исполняется первым
2. Time priority: при равной цене — более ранний ордер имеет приоритет

Для покупок "лучшая цена" = выше (готов платить больше). Для продаж = ниже (готов получить меньше).

Структуры данных

Order Book как sorted data structure

use std::collections::{BTreeMap, VecDeque, HashMap};

// Price как integer: избегаем float arithmetic (1.23456789 → 123456789)
// Все цены в наименьших единицах × 10^8
type Price = i64;
type Qty = u64;
type OrderId = u64;

#[derive(Clone, Debug)]
pub struct Order {
    pub id: OrderId,
    pub user_id: u64,
    pub symbol: String,
    pub side: Side,
    pub price: Price,           // 0 для market ордеров
    pub quantity: Qty,
    pub filled: Qty,
    pub order_type: OrderType,
    pub time_in_force: TimeInForce,
    pub created_at: u64,        // nanoseconds since epoch
}

impl Order {
    pub fn remaining(&self) -> Qty {
        self.quantity - self.filled
    }
    pub fn is_filled(&self) -> bool {
        self.filled >= self.quantity
    }
}

#[derive(Debug)]
pub struct PriceLevel {
    pub price: Price,
    pub total_qty: Qty,
    pub orders: VecDeque<OrderId>,  // FIFO
}

pub struct OrderBook {
    pub symbol: String,
    // Bids: DESC order (highest price first) → Reverse для BTreeMap
    pub bids: BTreeMap<std::cmp::Reverse<Price>, PriceLevel>,
    // Asks: ASC order (lowest price first)
    pub asks: BTreeMap<Price, PriceLevel>,
    // Fast lookup by order ID
    pub orders: HashMap<OrderId, Order>,
    // Sequence number для event ordering
    pub sequence: u64,
}

Использование BTreeMap вместо HashMap для ценовых уровней: O(log n) для insert/delete, но итерация по уровням = O(1) для best price. HashMap — O(1) для lookup, но нет порядка. Комбинация обоих — правильное решение.

Integer prices вместо floating point

Floating point arithmetic недопустима в финансовых расчётах. 0.1 + 0.2 != 0.3 в IEEE 754.

// Неправильно: float
let price: f64 = 43750.50;

// Правильно: integer с фиксированной точностью
const PRICE_PRECISION: i64 = 100_000_000;  // 10^8
let price: i64 = 4_375_050_000_000;  // 43750.50000000

fn float_to_price(f: f64) -> Price {
    (f * PRICE_PRECISION as f64).round() as Price
}

fn price_to_float(p: Price) -> f64 {
    p as f64 / PRICE_PRECISION as f64
}

Алгоритм matching

Limit Order matching

impl OrderBook {
    pub fn add_limit_order(&mut self, mut order: Order) -> MatchResult {
        let mut trades = Vec::new();
        let mut events = Vec::new();

        // Try to match against opposite side
        match order.side {
            Side::Buy => {
                while order.remaining() > 0 {
                    // Получаем лучший ask
                    let best_ask_price = match self.asks.keys().next() {
                        Some(&p) => p,
                        None => break,  // Нет продавцов
                    };

                    // Проверяем совпадение цен
                    if order.price < best_ask_price {
                        break;  // Покупатель не готов платить столько
                    }

                    let level = self.asks.get_mut(&best_ask_price).unwrap();
                    self.execute_against_level(&mut order, level, &mut trades, &mut events);

                    // Удаляем пустой уровень
                    if level.orders.is_empty() {
                        let price = level.price;
                        self.asks.remove(&price);
                    }
                }
            }
            Side::Sell => { /* симметрично */ }
        }

        // Если не полностью заполнен — добавляем в book
        if !order.is_filled() {
            match order.time_in_force {
                TimeInForce::GTC => self.insert_order(order.clone()),
                TimeInForce::IOC => {
                    // Immediate or cancel: если не заполнен полностью — отменяем остаток
                    events.push(Event::OrderCancelled { id: order.id, reason: "IOC" });
                }
                TimeInForce::FOK => {
                    // Fill or kill: если не заполнен полностью — отменяем ВСЁ
                    // Откатываем уже выполненные трейды
                    trades.clear();
                    events.push(Event::OrderCancelled { id: order.id, reason: "FOK" });
                    // Возвращаем maker-ам их количество обратно
                    for trade in &trades {
                        self.restore_maker_qty(trade);
                    }
                }
            }
        }

        self.sequence += 1;
        MatchResult { trades, events, sequence: self.sequence }
    }

    fn execute_against_level(
        &mut self,
        taker: &mut Order,
        level: &mut PriceLevel,
        trades: &mut Vec<Trade>,
        events: &mut Vec<Event>,
    ) {
        while taker.remaining() > 0 && !level.orders.is_empty() {
            let maker_id = *level.orders.front().unwrap();
            let maker = self.orders.get_mut(&maker_id).unwrap();

            let fill_qty = taker.remaining().min(maker.remaining());
            let fill_price = maker.price;  // Maker's price wins

            taker.filled += fill_qty;
            maker.filled += fill_qty;
            level.total_qty -= fill_qty;

            trades.push(Trade {
                id: self.next_trade_id(),
                maker_order_id: maker_id,
                taker_order_id: taker.id,
                price: fill_price,
                quantity: fill_qty,
                timestamp: current_nanoseconds(),
            });

            if maker.is_filled() {
                level.orders.pop_front();
                self.orders.remove(&maker_id);
                events.push(Event::OrderFilled { id: maker_id });
            } else {
                events.push(Event::OrderPartialFill { id: maker_id, filled: fill_qty });
            }
        }
    }
}

Market Order

Market ордер исполняется немедленно по лучшей доступной цене. Не имеет price limit — будет исполнен до конца книги если нужно:

pub fn add_market_order(&mut self, mut order: Order) -> MatchResult {
    // Market order не добавляется в book при неполном заполнении
    // Исполняем сколько можно, остаток отменяем
    order.price = match order.side {
        Side::Buy => Price::MAX,   // любая цена подходит
        Side::Sell => 0,           // любая цена подходит
    };

    let mut result = self.add_limit_order(order.clone());

    if !order.is_filled() {
        result.events.push(Event::OrderPartialFill {
            id: order.id,
            filled: order.filled,
        });
    }

    result
}

Stop Orders

Stop ордера — это триггеры, не активные ордера в book. При достижении stop price создаётся реальный ордер:

pub struct StopOrderManager {
    // Stop price → список stop ордеров
    buy_stops: BTreeMap<Price, Vec<StopOrder>>,   // Активируются при price >= stop
    sell_stops: BTreeMap<std::cmp::Reverse<Price>, Vec<StopOrder>>,  // price <= stop
}

impl StopOrderManager {
    pub fn check_triggers(&mut self, last_price: Price) -> Vec<Order> {
        let mut triggered = Vec::new();

        // Buy stops: триггер при росте цены выше stop price
        let triggered_prices: Vec<Price> = self.buy_stops
            .range(..=last_price)
            .map(|(&p, _)| p)
            .collect();

        for price in triggered_prices {
            if let Some(stops) = self.buy_stops.remove(&price) {
                for stop in stops {
                    triggered.push(stop.into_order(last_price));
                }
            }
        }

        triggered
    }
}

Event Sourcing и persistence

Журнал событий

Matching engine не делает прямых записей в базу данных — это убьёт производительность. Вместо этого: все события пишутся в append-only log (Kafka), downstream консьюмеры асинхронно обновляют базу:

Matching Engine → Kafka (trades, order_updates) → DB Writer
                                                  → Balance Updater
                                                  → Market Data Publisher
                                                  → Notification Service

Kafka гарантирует ordering в пределах partition (партиционируем по symbol → все события одного символа строго упорядочены).

Snapshot + Replay

При рестарте matching engine восстанавливает состояние из последнего snapshot + replay событий:

class MatchingEngineRecovery:
    def restore_order_book(self, symbol: str) -> OrderBook:
        # Загружаем последний snapshot
        snapshot = self.load_latest_snapshot(symbol)
        book = OrderBook.from_snapshot(snapshot)

        # Replay событий после snapshot
        events = self.kafka.get_events_after(symbol, snapshot.sequence)
        for event in events:
            book.apply_event(event)

        return book

Snapshot создаётся каждые N минут или каждые M событий. Без snapshot-ов при большом количестве событий replay может занять часы.

Производительность и оптимизации

Профилирование bottlenecks

Типичные bottlenecks matching engine в порядке приоритета:

1. Memory allocation: каждый новый ордер = heap allocation. Решение: object pool / arena allocator
2. Serialization: упаковка событий в Kafka. Решение: FlatBuffers / Cap'n Proto вместо JSON
3. Locking: если несколько потоков, любой мьютекс убивает throughput. Решение: single-threaded per-symbol + lock-free queues
4. Cache misses: неоптимальная memory layout. Решение: cache-friendly структуры (SoA вместо AoS)

LMAX Disruptor паттерн

LMAX Disruptor — lock-free ring buffer для inter-thread коммуникации, разработанный для high-frequency trading:

Input Thread → [Disruptor Ring Buffer] → Matching Engine Thread
                                       → Journaling Thread
                                       → Replication Thread

Ring buffer на 2^N элементов, wrapped sequence number. Producers и consumers используют CAS (compare-and-swap) операции вместо mutex. Latency: ~1-2 nanoseconds vs ~100ns для mutex.

Готовые реализации: LMAX Disruptor (Java), в Rust — crossbeam channel, в Go — disruptor-go.

Latency benchmarks

Реалистичные latency цифры для разных реализаций:

P99.9 (наихудший 0.1% запросов) особенно важен для репутации — именно туда попадают жалобы трейдеров на "тормоза".

Тестирование matching engine

Correctness testing

def test_price_time_priority():
    """Ордера с одинаковой ценой исполняются в порядке поступления"""
    book = OrderBook("BTCUSDT")

    # Два maker ордера по одной цене
    order1 = make_limit_order(side='sell', price=50000, qty=1, ts=100)
    order2 = make_limit_order(side='sell', price=50000, qty=1, ts=200)
    book.add(order1)
    book.add(order2)

    # Taker ордер
    taker = make_limit_order(side='buy', price=50000, qty=1, ts=300)
    result = book.add(taker)

    assert len(result.trades) == 1
    assert result.trades[0].maker_order_id == order1.id  # order1 раньше по времени

def test_fok_full_cancel():
    """FOK должен отменить целиком если не хватает ликвидности"""
    book = OrderBook("BTCUSDT")
    book.add(make_limit_order(side='sell', price=50000, qty=0.5))

    fok = make_fok_order(side='buy', price=50000, qty=1.0)
    result = book.add(fok)

    assert len(result.trades) == 0  # Нет трейдов
    assert book.asks[50000].total_qty == 0.5  # Maker ордер не тронут

Matching engine тестируется тысячами unit tests, property-based тестами (fuzzing случайных последовательностей ордеров), и сравнением с reference implementation.

Matching engine — это компонент, который пишется один раз и поддерживается годами. Инвестиции в качество кода, тесты и документацию здесь окупаются многократно.