Ордербук-DEX: движок сопоставления заявок

В прошлом уроке мы собрали пул: цена задаётся формулой, контрагент один на всех, ликвидность пассивна. Но исторически рынки устроены иначе, и профессиональный трейдер хочет именно стакан: выставить свою цену, стоять в очереди, отменить, когда передумал. Этот урок про то, как написать движок сопоставления, почему такой DEX прижился на Solana и не прижился в Ethereum, и когда стакан честно лучше пула.

Почему стакан не переехал в Ethereum

Разберём по числам, а не по ощущениям. У активного маркетмейкера на классической бирже соотношение примерно такое: на одну сделку приходятся десятки выставленных и отменённых заявок. Он постоянно подвигает котировку вслед за рынком.

Теперь посчитаем это в цепи, где каждое действие это транзакция.

Выставление стоит газ. Запись в хранилище это самая дорогая операция EVM.

Отмена тоже стоит газ. И отмен на порядок больше, чем сделок.

Скорость ограничена блоком. Двигать котировку чаще, чем раз в блок, нельзя физически.

Порядок внутри блока продаётся. Всё, что мы разбирали про MEV, бьёт по стакану прямее, чем по пулу: тот, кто выбирает порядок, решает, чья заявка исполнится первой.

Отсюда вывод, который индустрия сделала на практике: стакан в цепи требует дешёвых и частых транзакций. Там, где они есть, он живёт, где их нет, побеждает пул.

Три модели ордербук-DEX

Полностью в цепи. И заявки, и матчинг живут в контракте. Так работал Serum на Solana и работает его наследник OpenBook: цена блока около четырёхсот миллисекунд, комиссия копеечная, поэтому выставлять и отменять можно часто. Плюс: всё проверяемо, никакого доверия оператору. Минус: скорость всё равно ограничена цепью, а место в аккаунте стоит денег, поэтому стакан имеет фиксированный размер.

Матчинг вне цепи, расчёт в цепи. Заявка это подписанное сообщение, которое ходит по обычной сети. Оператор сводит заявки и отправляет в цепь уже готовую сделку. Так устроен 0x и семейство протоколов вокруг него. Плюс: выставление и отмена бесплатны и мгновенны. Минус: доверие оператору в вопросе очерёдности, хотя украсть деньги он не может, подпись ограничивает условия сделки.

Своя цепь под матчинг. Крайний случай второго варианта: если тебе нужен настоящий биржевой движок, построй под него отдельную сеть с валидаторами, которые держат стакан в памяти. Так поступил dYdX в четвёртой версии. Плюс: биржевая скорость. Минус: это уже отдельный блокчейн со своей безопасностью, а не приложение поверх чужой.

Общее у всех трёх одно: сам движок сопоставления везде одинаковый. Его и напишем.

Правило: цена, потом время

Приоритет исполнения задаётся двумя правилами подряд.

Цена важнее. Заявка с лучшей ценой исполняется раньше, независимо от того, когда пришла. Лучшая для покупателя это самая высокая, для продавца самая низкая.

Внутри цены важнее время. Кто раньше встал в очередь, тот раньше исполнится.

Второе правило не мелочь: именно оно вознаграждает того, кто дал ликвидность раньше и держал риск дольше. На биржах, где приоритет времени заменяют пропорциональным распределением, поведение маркетмейкеров меняется целиком.

Структура данных отсюда выводится почти автоматически:

/// Стакан заявок.
///
/// Покупки и продажи лежат в отдельных деревьях, ключ это цена, значение это
/// очередь заявок по времени. Дерево даёт отсортированный обход, очередь
/// даёт приоритет по времени, а индекс `by_id` позволяет отменить заявку,
/// не обходя весь стакан.
#[derive(Debug, Default)]
pub struct OrderBook {
    bids: BTreeMap<u64, VecDeque<Order>>,
    asks: BTreeMap<u64, VecDeque<Order>>,
    by_id: HashMap<OrderId, (Side, u64)>,
    next_id: OrderId,
    next_sequence: u64,
}

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

Цены и количества целые. Цена это номер ценового шага, количество это минимальный лот.

Сердце движка

fn match_against_book(
    &mut self,
    taker_id: OrderId,
    owner: u32,
    side: Side,
    limit_price: Option<u64>,
    quantity: u64,
    fills: &mut Vec<Fill>,
) -> u64 {
    let mut remaining = quantity;
    loop {
        if remaining == 0 {
            break;
        }
        let best = match side {
            Side::Buy => self.best_ask(),
            Side::Sell => self.best_bid(),
        };
        let Some(price) = best else { break };
        let acceptable = match (side, limit_price) {
            (_, None) => true,
            (Side::Buy, Some(limit)) => price <= limit,
            (Side::Sell, Some(limit)) => price >= limit,
        };
        if !acceptable {
            break;
        }
        // Дальше идём по очереди этого уровня, пока есть что исполнять.
    }
    remaining
}

Три решения, зашитые в этот цикл.

Рыночная заявка это лимитная без ограничения. limit_price: None означает «согласен на любую цену», и отдельного кода для рыночных заявок не нужно вовсе.

Сделка проходит по цене мейкера. Готов купить по 105, а в стакане стоит продажа по 100: сделка будет по 100. Тейкер получает улучшение цены, потому что мейкер объявил свою цену первым и обязан её держать.

Выход при неподходящей цене, а не пропуск уровня. Раз лучший уровень не подходит, дальше цены только хуже. Дерево отсортировано, поэтому проверять остальное бессмысленно.

Срок жизни заявки

Три режима, в биржевых протоколах их называют сроком жизни заявки. Разница между ними это разные ответы на вопрос «что делать с неисполненным остатком».

pub enum TimeInForce {
    /// Остаток встаёт в стакан и ждёт.
    Gtc,
    /// Исполнить сколько можно прямо сейчас, остаток отменить.
    Ioc,
    /// Либо исполнить целиком, либо не исполнять вовсе.
    Fok,
}

Fok требует отдельной осторожности: решение принимается до того, как что-то изменилось.

if tif == TimeInForce::Fok && self.available(side, limit_price, owner) < quantity {
    execution.rejected = true;
    return execution;
}

Соблазн реализовать это иначе (исполнить, а если не хватило, откатить) в системе с общим состоянием опасен: пришлось бы уметь откатывать уже проведённые сделки. Проверить наличие объёма заранее дешевле и честнее.

Потрогай все три режима на живом стакане: подай заявку по цене хуже рынка, потом IOC на объём больше доступного, потом FOK на тот же объём.