Спроектируй биржу

Требования

Биржа сводит заявки на покупку и продажу инструментов и публикует результаты. Ограничения необычны и переворачивают обычные инстинкты масштабирования. Почему биржа выглядит так непохоже на всё остальное в этом юните? Потому что «кто торговал первым» — это юридический вопрос, а не только инженерный.

Функциональные. Принимать заявки (инструмент, сторона, цена, количество, тип — лимитная/рыночная). Поддерживать книгу заявок на инструмент: лежащие заявки на покупку (биды) и продажу (аски). Сводить входящие заявки против книги по честному правилу. Исполнять сделки, обновлять позиции и публиковать рыночные данные (книгу и ленту сделок) всем участникам. Поддерживать отмены и поправки.

Нефункциональные. Честность и детерминизм превыше всего: единый каноничный порядок событий, идентичные результаты на каждой реплике, воспроизводимость для аудита годы спустя. Ультранизкая задержка: матчинг за микросекунды, потому что участники конкурируют на скорости. Долговечность: ни одна подтверждённая заявка не должна теряться, даже через крэш. Высокая пропускная способность во всплесках (миллионы сообщений/с на открытии). Честность — ограничение, доминирующее в дизайне — оно вынуждает единую последовательность, что вынуждает однопоточное ядро, что переворачивает всё.

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

Оценка

инструментов      = ~10 000 символов
пик сообщений     = ~1 000 000–10 000 000 заявок+отмен/с (всплеск открытия)
задержка матчинга = цель < 10 микросекунд на заявку (in-memory)
книга заявок      = тысячи ценовых уровней × заявок на уровень, всё в RAM
лог событий       = каждое сообщение, append, fsync, реплика → долговечность + аудит
фан-аут           = рыночные данные тысячам подписчиков, multicast

Числа объясняют архитектуру. Весь рабочий набор — книги заявок всех инструментов — влезает в RAM (это миллионы маленьких записей, не терабайты), так что движок матчинга — in-memory программа; касание диска на горячем пути взорвало бы микросекундный бюджет на порядки. Пик всплесковый и жестокий (открытие), так что путь должен быть худым. И каждое сообщение долговечно логируется и для восстановления после крэша, и для аудита — но запись лога устроена так, что никогда не стопорит матч (ниже подробнее). Поэтому биржа не похожа ни на что вроде шардированного веб-бэкенда: это быстрое однопоточное ядро, питаемое секвенсором и подпираемое логом.

Высокоуровневый дизайн

Паттерн (архитектура LMAX — знаменитый публичный пример): секвенсор назначает каждому сообщению глобальный номер последовательности, определяя единый истинный порядок; этот упорядоченный поток пишется в долговечный, реплицируемый лог событий; однопоточный движок матчинга потребляет поток по порядку против in-memory книги заявок и детерминированно производит сделки; результаты веером раздаются как рыночные данные. Восстановление и реплики тривиальны из-за детерминизма — переиграй лог с начала (или со снимка), и достигнешь ровно той же книги.

Глубокое погружение

Приоритет цена-время и книга заявок

Правило матчинга должно быть честным и тотальным, не оставляя двусмысленности о том, кто исполнится первым. Стандарт — приоритет цена-время (price-time priority): заявки ранжируются сперва по цене (покупатель, предлагающий больше, или продавец, просящий меньше, имеет приоритет), а среди заявок по той же цене — по времени (первым пришёл, первым исполнился — FIFO). Это в точности отвечает вступлению: две покупки по той же цене упорядочены своими номерами последовательности, и более ранняя исполняется.

Книга заявок — структура данных, делающая это быстрым: для каждого инструмента биды и аски держатся отсортированными по цене (часто как отображение от ценового уровня к FIFO-очереди заявок на этом уровне). Матчинг входящей заявки идёт по противоположной стороне от лучшей цены внутрь, исполняясь против лежащих заявок, пока входящая не исчерпана или цена не пересекается:

АСКИ (продавцы)       БИДЫ (покупатели)
101.00  × 50          100.50  × 30   ← лучший бид
100.75  × 20          100.25  × 40
                      100.00  × 100

входящая: КУПИТЬ 60 @ рынок
  → исполнить 20 @ 100.75, затем 40 @ 101.00 (идём вверх по аскам)  ⇒ две сделки, книга обновлена

Каждый уровень FIFO, так что приоритет времени держится; лучшая цена O(1) на поиск, а матчинг O(затронутых заявок). Книга — чистое in-memory состояние, мутируемое единым потоком матчинга, поэтому она может работать за микросекунды.

Детерминизм и долговечность через лог событий

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

Это даёт долговечность и восстановление дёшево: добавляй каждое секвенсированное сообщение в лог, что fsync’нут и реплицирован до (или одновременно с) матчингом, так что крэш не теряет ничего подтверждённого; при перезапуске переиграй лог (с периодического снимка, чтобы ограничить время реплея) для реконструкции точного in-memory состояния. Репликация — это и механизм failover — горячие реплики потребляют тот же лог и стоят готовыми принять на том же номере последовательности. Аудит — та же машинерия: неизменяемый, упорядоченный лог — идеальная запись, и вопрос регулятора («почему случилась эта сделка?») отвечается реплеем до того номера последовательности.

Фан-аут рыночных данных

Как только движок свёл, результаты — сделки и инкрементальные обновления книги — должны дойти до каждого участника честно и быстро. Это широковещание с высоким фан-аутом (тысячи подписчиков, каждый хочет ленту с минимальной задержкой). Биржи обычно используют multicast (групповую рассылку — один пакет, много получателей): движок публикует каждое обновление один раз, а сеть дублирует его всем подписчикам, так что цена фан-аута не растёт с числом подписчиков и все получают его почти в один миг (снова честность — нельзя дать одному подписчику фору). Лента сама — секвенсированный поток (протоколы gap-fill дают подписчику, пропустившему пакет, запросить реплей), и многие биржи публикуют ярусные ленты (полная глубина книги против вершины книги) для управления полосой. Фан-аут параллелится и держится прочь от потока матчинга — движок выдаёт, отдельный путь публикации распределяет.

Узкие места и компромиссы

Определяющая позиция — детерминизм и честность важнее параллелизма: ядро матчинга однопоточно намеренно, так что его потолок пропускной способности — один быстрый поток — масштабируешь, делая этот поток быстрее (книга в кэше, без аллокаций на горячем пути, mechanical sympathy) и партиционируя по инструментам (независимые книги могут работать на отдельных движках), но никогда параллеля одну книгу. Долговечность против задержки — центральное напряжение: запись лога должна случиться до того, как подтвердишь заявку, но fsync медленен относительно микросекундного матча — решается батчингом записей лога, записью в быстрое хранилище и перекрытием репликации, чтобы долговечная запись не сериализовалась за каждым матчем. In-memory значит ограничено RAM и временем восстановления: книга влезает в память, но реплей-из-лога должен быть ограничен периодическими снимками, иначе перезапуск слишком долог. И честность фан-аута ограничивает сеть: multicast держит его равным и масштабируемым, но требует протоколов gap-recovery и аккуратной ёмкости, чтобы ни один подписчик не был систематически в выгоде. Всюду биржа принимает однопоточный потолок и сложную долговечную обвязку как цену единственного, чем нельзя поступиться — честного, детерминированного, аудитируемого порядка сделок.