Проектирование матчинг-движка на Rust: приоритет цены и времени без пауз GC

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

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

Стакан — отсортированный индекс ценовых уровней над FIFO-очередями

Стакан — это две стороны, каждая из которых упорядоченная по цене коллекция уровней. Уровень — не число: это очередь стоящих заявок по данной цене в порядке поступления. Сведение постоянно трогает лучший уровень и редко — глубокие, поэтому структура выбирается под этот шаблон доступа, а не ради изящества.

• Цены — целые числа в тиках, никогда не с плавающей точкой: тик и есть единица инструмента, а сравнение и арифметика на целых точны
• Каждая сторона держит уровни в порядке цены, а лучшая цена доступна без поиска — вершина стакана читается на каждой команде
• Уровень хранит FIFO-очередь стоящих заявок и агрегированный объём, чтобы агрегат не приходилось пересчитывать обходом очереди
• Заявки лежат в заранее выделенном слабе и адресуются индексными handle'ами, а очередь интрузивная: ссылки на следующий и предыдущий элемент живут внутри самой записи заявки
• Отдельная карта из клиентского id заявки в handle слаба делает отмену и замену прямым поиском, поэтому отмена никогда не сканирует стакан
• Удаление из очереди идёт по handle, а не поиском: отмена глубоко стоящей заявки стоит столько же, сколько отмена на вершине стакана

Следствие интрузивных очередей и индексных handle'ов в том, что стоящая заявка за свою жизнь никогда не переезжает в памяти. Её место в очереди — свойство её ссылок, а не того, где она лежит, и именно это делает частичные исполнения дешёвыми дальше.

Приоритет цены и времени — это цикл по уровням, а затем по очереди

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

• Взять лучший противоположный уровень; если его цена не пересекает лимитную цену входящей заявки — остановиться
• Взять первую заявку из очереди этого уровня — она самая старая по этой цене, а приоритет времени означает, что исполняется она первой
• Объём сделки — меньший из двух остатков; цена сделки — цена стоящей заявки, потому что условия задала именно она
• Уменьшить оба остатка, выдать событие сделки и уменьшить агрегат уровня
• Если остаток стоящей заявки дошёл до нуля — отцепить её от очереди и вернуть слот слаба; если уровень опустел — удалить уровень
• Повторять, пока количество входящей заявки не станет нулём или не кончатся приемлемые уровни

Семантика типов заявок — решения, принимаемые на границе этого цикла, а не внутри него. Immediate-or-cancel отбрасывает остаток вместо того, чтобы поставить его в стакан. Fill-or-kill сначала делает сухой прогон и либо исполняется целиком, либо отклоняется. Post-only отклоняется, если заявка пересеклась бы при поступлении. Держать это вне цикла — значит оставить цикл единственным местом, где меняется состояние стакана.

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

Детерминизм делает хвост предсказуемым, а аллокации его ломают

Средняя задержка редко бывает проблемой. Проблема — худшее наблюдение во время всплеска, то есть тогда, когда движок важнее всего и когда пауза stop-the-world вероятнее всего и случится. Под управляемой средой со сборщиком мусора эту паузу планирует сборщик, а не вы, и приходится она на середину того всплеска, который мусор и породил.

Ручное выделение памяти — уменьшенная версия той же проблемы. Аллокатор общего назначения может обходить списки свободных блоков, брать лок или просить память у ядра, и именно этот вызов попадает в хвост. Лечение одно в обоих случаях: не выделять память на горячем пути вовсе.

• Записи заявок, записи уровней и буферы событий берутся из арен, размер которых задан на старте: в установившемся режиме число аллокаций на пути сведения равно нулю
• Освободившиеся слоты возвращаются в список свободных внутри арены, поэтому активный инструмент всю сессию переиспользует одну и ту же память
• Структуры фиксированной формы и фиксированного размера, а предел ёмкости приводит к отказу, а не к росту
• Исходящие события пишутся в заранее выделенный кольцевой буфер, который вычитывает другой поток: поток сведения никогда не блокируется на потребителе
• Поток сведения — единственный писатель по стакану, поэтому на состоянии стакана нет лока и нет двусмысленности порядка, которую надо разрешать
• Вход нумеруется до того, как дойдёт до движка, и порядок решает номер в последовательности, а не время прихода

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

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

Журнал и есть состояние движка, а стакан — его кеш

Восстановление — не фича, прикрученная после того, как заработало сведение. Движок пишет append-only журнал принятых команд в порядке последовательности, а стакан в памяти есть не что иное, как результат свёртки этого журнала. Восстановление после сбоя — это его повторное проигрывание.

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

Журнал пишет движок, но долговечность — свойство пути хранения и того, на скольких машинах есть запись до отправки подтверждения. Это решение про репликацию и железо, и именно там на самом деле выигрывается или проигрывается время восстановления.

Тестирование — это детерминированный реплей плюс инварианты, которые обязаны выполняться всегда

Детерминизм — это то, что делает движок тестируемым. Раз один и тот же вход даёт один и тот же выход, записанная сессия становится регрессионным тестом, а найденный однажды сбой воспроизводится точно, а не отлавливается заново.

• Стенд реплея: подать записанную последовательность команд, сравнить выданный поток событий с сохранённым и упасть на первом расхождении, назвав номер последовательности
• Проверка инвариантов после каждой команды в тестовых сборках — очереди отсортированы по приходу, агрегаты уровня равны сумме своей очереди, стакан не пересечён, суммарное количество сохраняется в каждой сделке
• Property-based тесты, которые генерируют случайные, но корректные последовательности команд и проверяют инварианты, а не конкретные исходы
• Дифференциальная эталонная модель: медленная, очевидно корректная реализация на наивных структурах данных прогоняется на том же входе, а любое расхождение считается багом быстрой версии
• Фаззинг на границе декодера, куда снаружи приходит некорректный вход и где паника уронила бы поток сведения
• Измерение задержки на том профиле всплеска, который вас беспокоит, с записью распределения, а не среднего, потому что дизайн решает именно хвост

Что Rust здесь даёт, а чего не даёт

Rust убирает целый класс проблем, а не ускоряет цикл сам по себе. Сборщика мусора нет, поэтому никакая пауза не планируется у вас за спиной. Владение делает дисциплину единственного писателя тем, что проверяет компилятор, а не тем, что должно заметить ревью. Handle'ы в слабе и интрузивные связи, легко дающие ошибку в языке без времён жизни, здесь проверяемы. Паника при переполнении целых в debug-сборках ловит класс багов, тихо портящих стакан.

Честная граница в том, что почти всё, что определяет хвост задержки, — не язык:

• Планировщик ядра, обработка прерываний, привязка к ядрам CPU и управление питанием двигают хвост сильнее, чем код сведения
• Сетевой интерфейс, наличие или отсутствие обхода ядра и физический путь до площадки задают пол, ниже которого движок не опустится
• Сериализация и протокол на границе часто стоят дороже всего, а не само сведение
• Семантика сведения, типы заявок, правила комиссий и ребейтов, фазы рынка — это бизнес-решения: неверное правило, реализованное быстро, остаётся неверным
• Риск-проверки, лимиты позиций и путь расчётов живут вне движка, со своей задержкой и своими режимами отказа
• Эксплуатация — выкатка, мониторинг, runbook на случай неудавшегося реплея — решает, переживут ли гарантии столкновение с продовым инцидентом

Rust и стоит чего-то. Borrow checker тормозит первые недели дизайна, который ещё движется, экосистема биржевых протоколов тоньше, чем в более старых языках, а unsafe-блоки вокруг lock-free структур требуют той же дисциплины ревью, что и аналогичный код где угодно. Выбор Rust — решение про хвост задержки и про безопасность памяти в ядре с единственным писателем, а не про комфорт разработчика.

amBrain строит торговую инфраструктуру в Ереване с 2019 года, горячие пути — на Rust; построенная нами мини-биржа работает в проде на колокации MOEX. Если вы проектируете матчинг-движок и хотите пройти по структуре книги заявок, формату журнала или стенду воспроизведения — такой разговор стоит провести до первой строки горячего пути.