Системный дизайн биржи: стакан заявок, matching engine и журнал событий

Как спроектировать биржу на system design интервью: стакан заявок, matching engine с приоритетом цена-время, секвенсор и журнал событий, низкие задержки, риск-контроль и рыночные данные.

14 мин чтениясистемный дизайн · биржа · низкие задержки · python

Коротко

ВопросРешение в этом разборе
Сердце системыmatching engine: сводит заявки на покупку и продажу по одному инструменту
Структура данныхстакан заявок: уровни цен, на каждом уровне FIFO-очередь заявок
Правило исполненияприоритет цена-время: сначала лучшая цена, при равной цене — кто раньше пришёл
Порядоксеквенсор присваивает каждой команде номер, журнал событий — единственный источник правды
Масштабированиешардирование по инструментам; один инструмент — один поток, без блокировок
Отказоустойчивостьдетерминированный движок + журнал = горячий резерв, который проигрывает те же события
Задержкивсё в памяти, никакой сети и диска внутри цикла сопоставления, бинарные протоколы
Рыночные данныелента событий (L3), агрегированный стакан (L2), лучшие цены (L1); мультикаст + снапшоты

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

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

Шаг 1. Требования

Сначала договоритесь о рамках. «Биржа» бывает разной: от криптобиржи с веб-интерфейсом до площадки, где торгуют только профессиональные участники через брокеров. На интервью обычно имеют в виду второе.

ВопросТипичный ответЧто это меняет
Кто подключается?брокеры и маркет-мейкеры, не людибинарный API, постоянные соединения, а не REST из браузера
Какие заявки?лимитные, рыночные, отмена, изменениедве операции над стаканом плюс сопоставление
Сколько инструментов?несколько тысяч акцийестественный ключ шардирования
Торговая сессия?днём, ночью клиринг и обслуживаниеесть окно, чтобы сделать снапшоты и обнулить состояние
Расчёты, клиринг, депозитарий?вне рамокпосле сделки отдаём событие дальше и забываем

Нефункциональные требования назовите сами:

  • Справедливость. Две заявки, пришедшие в разном порядке, должны исполниться в этом порядке. Это не пожелание, а требование регулятора.
  • Детерминизм. Одна и та же последовательность команд всегда даёт одни и те же сделки.
  • Низкие и стабильные задержки. Важна не средняя, а p99 и p99.9: всплеск в 50 мс во время новостей обходится участникам дороже, чем стабильные 100 мкс.
  • Ни одной потерянной заявки или сделки. Подтверждённое должно пережить падение сервера.
  • Высокая доступность в торговые часы. Остановка торгов — инцидент, о котором пишут новости.

Шаг 2. Оценки

Цифры условные, но порядок важен. Как прикидывать, разобрано в статье про оценки на салфетке.

  • 5 000 инструментов, торговая сессия около 8 часов.
  • 1 млрд сообщений в день (заявки, отмены, изменения). Подавляющая часть — от алгоритмических участников, и большинство заявок отменяется, не дойдя до исполнения.
  • В среднем 109/28 800≈35 00010^9 / 28\,800 \approx 35\,000 сообщений в секунду, в пиках на открытии и на новостях — в 10–20 раз больше.
  • Нагрузка распределена неравномерно: несколько самых ликвидных бумаг дают львиную долю потока.
  • Сообщение в бинарном формате — 50–100 байт, то есть журнал за день — порядка 100 ГБ. Это легко пишется последовательно на один NVMe.

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

Шаг 3. API и поток заявки

Участники подключаются через шлюз по постоянному TCP-соединению. Исторически стандарт — протокол FIX, для скорости биржи дают собственные бинарные протоколы. Минимальный набор команд:

КомандаПоляОтвет
NewOrderclient_order_id, инструмент, сторона, тип, цена, количествоAccepted / Rejected, затем Fill-ы
Cancelclient_order_id или биржевой idCancelled / CancelRejected
Replaceновая цена и/или количествоReplaced

client_order_id уникален в рамках сессии участника и служит ключом идемпотентности: повтор после обрыва соединения не создаст вторую заявку.

Путь заявки:

  1. Шлюз (gateway) принимает соединение, аутентифицирует, проверяет формат.
  2. Риск-контроль до сделки (pre-trade risk): лимиты на размер заявки, допустимый коридор цены, хватает ли у участника обеспечения. Проверки синхронные, иначе бессмысленны.
  3. Секвенсор присваивает команде глобальный номер и пишет в журнал.
  4. Matching engine применяет команду к стакану и выдаёт события: принято, сделка, отменено.
  5. События уходят обратно участникам (execution reports), в рыночные данные, в клиринг и в хранилище.

Стакан заявок

Стакан (order book) — две стороны: покупка (bids) и продажа (asks). Каждая сторона — набор уровней цен, а на каждом уровне — очередь заявок в порядке поступления.

           ASK  10200 │ [#3: 10]
           ASK  10100 │ [#1: 5] → [#2: 3]
 ─────── спред ───────┼──────────────
           BID   9900 │ [#4: 7]

Лучшая цена продажи (best ask) — минимальная из asks, лучшая цена покупки (best bid) — максимальная из bids. Разница между ними — спред. Если заявка на покупку пришла с ценой не ниже best ask, она агрессивная: сразу исполняется против стакана. Иначе она пассивная и встаёт в очередь своего уровня.

Требования к операциям:

ОперацияЧастотаНужная сложность
узнать лучшую ценуна каждой заявкеO(1)O(1)
добавить заявку на уровеньочень частоO(1)O(1) или O(log⁡L)O(\log L)
отменить заявку по idчаще, чем сделкиO(1)O(1)
исполнить заявку в голове уровняна каждой сделкеO(1)O(1)

Здесь LL — число уровней цен, обычно десятки-сотни активных. Классическая реализация:

  • уровни одной стороны — в упорядоченной структуре (красно-чёрное дерево, куча) или в массиве, индексированном ценой в тиках: цена всегда кратна шагу, а торгуют рядом с текущей ценой;
  • заявки уровня — в двусвязном списке: добавление в хвост, снятие с головы и удаление из середины за O(1)O(1);
  • хеш-таблица order_id → узел списка для отмены за O(1)O(1).

Цены хранятся целыми числами в тиках, никогда не float: 0.1+0.2≠0.30.1 + 0.2 \ne 0.3 на бирже превращается в заявку, которая не сошлась с встречной по «той же» цене.

Matching engine и приоритет цена-время

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

  1. Входящая заявка исполняется против лучшей встречной цены.
  2. Внутри уровня цены — против самой старой заявки.
  3. Цена сделки — цена заявки, которая стояла в стакане (мейкера), а не входящей (тейкера). Покупатель, готовый платить 102, при лучшей продаже 101 купит по 101.
  4. Исполнение продолжается, пока заявка не заполнена или встречные цены не перестали подходить. Остаток лимитной заявки встаёт в стакан.

Существуют и другие алгоритмы, например pro-rata (объём делится пропорционально размеру заявок на уровне), их применяют на части срочных рынков. На интервью достаточно упомянуть, что правило — бизнес-параметр, а не техническое решение.

Вот рабочая модель на Python. Уровни — куча цен плюс словарь цена → deque, отмена ленивая: заявка помечается нулём и выкидывается, когда доходит до головы очереди. Для учебного примера это проще двусвязного списка и сохраняет нужную асимптотику.

import heapq from collections import deque from dataclasses import dataclass @dataclass class Order: id: int side: str # 'B' или 'S' price: int # в тиках (целое число), не float qty: int class OrderBook: def __init__(self): self.levels = {'B': {}, 'S': {}} # цена -> deque заявок (FIFO) self.prices = {'B': [], 'S': []} # кучи цен: для B храним -price self.index = {} # id -> заявка (для отмены) def best(self, side): heap = self.prices[side] while heap: p = -heap[0] if side == 'B' else heap[0] queue = self.levels[side].get(p) while queue and queue[0].qty == 0: queue.popleft() # отменённые заявки в голове очереди if queue: return p heapq.heappop(heap) # уровень опустел — ленивое удаление return None def submit(self, o): trades = [] other = 'S' if o.side == 'B' else 'B' while o.qty > 0: p = self.best(other) if p is None or (o.side == 'B' and p > o.price) \ or (o.side == 'S' and p < o.price): break # лучшая встречная цена не подходит queue = self.levels[other][p] maker = queue[0] # самая старая живая заявка уровня q = min(o.qty, maker.qty) trades.append((maker.id, o.id, p, q)) # цена сделки = цена мейкера o.qty -= q maker.qty -= q if maker.qty == 0: queue.popleft() del self.index[maker.id] if o.qty > 0: # остаток встаёт в стакан lvl = self.levels[o.side] if o.price not in lvl or not lvl[o.price]: lvl[o.price] = deque() heapq.heappush(self.prices[o.side], -o.price if o.side == 'B' else o.price) lvl[o.price].append(o) self.index[o.id] = o return trades def cancel(self, order_id): o = self.index.pop(order_id, None) if o: o.qty = 0 # ленивая отмена: удалим при встрече book = OrderBook() book.submit(Order(1, 'S', 10100, 5)) book.submit(Order(2, 'S', 10100, 3)) book.submit(Order(3, 'S', 10200, 10)) book.submit(Order(4, 'B', 9900, 7)) print(book.submit(Order(5, 'B', 10200, 12))) # [(1, 5, 10100, 5), (2, 5, 10100, 3), (3, 5, 10200, 4)] print(book.best('B'), book.best('S')) # 9900 10200 book.cancel(3) print(book.best('S')) # None

Заявка №5 на покупку 12 штук по 10200 сначала забрала уровень 10100 целиком — сначала №1, пришедшую раньше, затем №2, — и только потом 4 штуки у №3 по 10200. Если бы №2 пришла раньше №1, порядок исполнения поменялся бы: в этом и есть приоритет времени.

Рыночная заявка — частный случай: цена «бесконечная» для покупки и нулевая для продажи, а остаток не встаёт в стакан, а отменяется. На реальных биржах её дополнительно ограничивают коридором цены, чтобы крупная рыночная заявка в тонком стакане не исполнилась по абсурдной цене.

Секвенсор и журнал событий

Самое важное архитектурное решение: matching engine — детерминированная машина состояний. Его состояние полностью определяется последовательностью входных команд. Отсюда всё остальное:

  • Секвенсор — единственная точка, где устанавливается порядок. Он присваивает каждой команде монотонный номер seq и записывает её в журнал. Порядок, в котором команды попали в журнал, и есть официальный порядок поступления.
  • Журнал — последовательный append-only лог, тот же принцип, что у write-ahead log в базах данных. Последовательная запись на диск быстрая, а для надёжности команду реплицируют на другой узел до того, как движок её обработает.
  • Движок читает журнал и применяет команды по порядку. Сам он ничего не пишет на диск и не ходит в сеть.

Это по сути event sourcing: состояние — свёртка лога событий. Проверим детерминизм на модели выше: два прогона одного журнала дают одинаковые сделки.

journal = [ # последовательный журнал: seq, команда, аргументы (1, 'NEW', 1, 'S', 10100, 5), (2, 'NEW', 2, 'S', 10100, 3), (3, 'NEW', 3, 'B', 10000, 4), (4, 'CANCEL', 1), (5, 'NEW', 4, 'B', 10100, 6), ] def replay(log): book, out = OrderBook(), [] for seq, cmd, *args in log: if cmd == 'NEW': out += book.submit(Order(*args)) else: book.cancel(*args) return out print(replay(journal)) # [(2, 4, 10100, 3)] print(replay(journal) == replay(journal)) # True

Что даёт детерминизм:

  • Горячий резерв. Второй экземпляр движка читает тот же журнал и держит то же состояние. При падении основного резерв продолжает с последнего seq. Выбор, кто сейчас основной, — задача выбора лидера или консенсуса вроде Raft, но только для этого решения, а не для каждой заявки.
  • Восстановление. Ночью делается снапшот стакана с номером seq, после падения — загрузка снапшота и проигрывание хвоста журнала.
  • Аудит и разбор инцидентов. Любую ситуацию можно воспроизвести бит в бит на тестовом стенде.
  • Простое тестирование. Записанный журнал боевого дня — готовый регрессионный тест для новой версии движка.

Чтобы детерминизм не сломался, в движке запрещено всё, что зависит от окружения: системное время (метку времени ставит секвенсор и кладёт в команду), случайные числа, итерация по хеш-таблицам с недетерминированным порядком, обращения к внешним сервисам.

Почему один поток и как масштабироваться

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

Поэтому:

  • Один инструмент обрабатывается ровно одним потоком. Никаких блокировок внутри.
  • Шардирование по инструментам. Каждый поток или сервер отвечает за свой набор бумаг. Сделки по разным инструментам независимы, глобальный порядок между ними не нужен. Подробнее о шардах — в статье про шардирование и репликацию.
  • Горячие бумаги — на отдельных ядрах. Распределение не равномерное, а по реальной нагрузке.

Известный публичный пример — архитектура LMAX (британская торговая площадка): бизнес-логика в одном потоке, все данные в памяти, а взаимодействие с внешним миром через кольцевые буферы (паттерн Disruptor). Подробнее о структуре — в статье про кольцевой буфер.

Низкие задержки

Список приёмов, которые стоит назвать на интервью:

ПриёмЗачем
всё состояние в памятидиск только для последовательной записи журнала, вне критического пути движка
без аллокаций в горячем путипулы заявок заранее; сборщик мусора не должен останавливать торги
поток прибит к ядру, busy-spinнет переключений контекста и пробуждений из сна
кольцевые буферы между этапамипередача без блокировок, одна запись — один читатель
бинарные протоколы фиксированной длиныразбор без парсинга текста, как у FIX
kernel bypass, мультикаст по UDPсеть минует стек ядра; рыночные данные — один пакет для всех подписчиков
пакетирование записи журналаодин fsync или сетевая репликация на группу команд, а не на каждую
колокацияучастники ставят серверы в дата-центр биржи; длина кабелей выравнивается

Последний пункт любят интервьюеры: справедливость на уровне физики. Биржи выравнивают длину кабелей до серверов участников в колокации, чтобы никто не получал данные раньше соседа.

Измерять нужно гистограммы задержек по этапам (шлюз → риск → секвенсор → движок → ответ) и хвостовые перцентили. Средняя задержка тут почти ничего не говорит.

Рыночные данные

Каждое событие движка — источник публичной информации. Её отдают в трёх уровнях детализации:

УровеньЧто содержитКому нужно
L1лучшие bid и ask, последняя сделкатерминалы, сайты с котировками
L2агрегированный объём по каждому уровню цены (глубина)трейдеры, большинство алгоритмов
L3каждая заявка: добавлена, изменена, отменена, исполненамаркет-мейкеры, HFT; позволяет восстановить стакан

L2 строится из L3 агрегацией по уровням:

def depth(book, side, n=5): rows = [] for p in sorted(book.levels[side], reverse=(side == 'B')): vol = sum(o.qty for o in book.levels[side][p]) if vol: rows.append((p, vol)) if len(rows) == n: break return rows b = OrderBook() orders = [('B', 9990, 3), ('B', 9990, 2), ('B', 9980, 7), ('S', 10010, 4), ('S', 10020, 1), ('S', 10010, 6)] for i, (s, p, q) in enumerate(orders): b.submit(Order(i, s, p, q)) print('bids', depth(b, 'B')) # bids [(9990, 5), (9980, 7)] print('asks', depth(b, 'S')) # asks [(10010, 10), (10020, 1)]

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

Как доставлять:

  • Инкрементальная лента по UDP-мультикасту с номером последовательности. Один пакет получают все подписчики одновременно — и быстро, и честно.
  • Обнаружение потерь по пропуску номера. Пропавшие сообщения запрашивают у сервиса повторной отправки (retransmission) по TCP.
  • Снапшоты стакана периодически: подписчик, подключившийся посреди дня, берёт снапшот с seq = N и применяет инкременты начиная с N + 1.
  • Для внешнего мира — отдельный слой: агрегированные и прореженные данные через WebSocket или стриминговый API, с кэшами и CDN. Этот слой может отставать на сотни миллисекунд, и это нормально.

Свечи, объёмы торгов, исторические графики считаются асинхронно из того же журнала сделок в аналитическом хранилище. Классическая задача про покупку и продажу акции решается как раз на таком ряду цен.

Итоговая архитектура

Участники ──TCP──▶ Шлюзы ──▶ Pre-trade risk ──▶ Секвенсор ──▶ Журнал (реплицирован)
                                                                │
                                         ┌──────────────────────┼─────────────────────┐
                                         ▼                      ▼                     ▼
                              Matching engine          Matching engine         Matching engine
                              (шард A, основной)       (шард A, резерв)        (шард B, ...)
                                         │
                       ┌─────────────────┼───────────────────┬────────────────┐
                       ▼                 ▼                   ▼                ▼
               Execution reports   Рыночные данные      Клиринг/учёт     Хранилище и
                (обратно в шлюз)   (мультикаст, L1-L3)  (пост-трейд)     аналитика

Типичные ошибки на интервью

  • Сразу предлагать базу данных для стакана и транзакции на каждую заявку. Задержки вырастут на порядки, а порядок исполнения будет зависеть от планировщика СУБД.
  • Распараллеливать сопоставление одного инструмента блокировками или несколькими инстансами за балансировщиком. Ломается приоритет времени.
  • Использовать float для цен.
  • Ставить метку времени в движке через системные часы. Резерв получит другие метки, и детерминизм пропадёт.
  • Забыть отмены. Их в потоке больше, чем сделок, и отмена за O(log⁡n)O(\log n) поиском по списку — частая слабость решения.
  • Путать цену сделки. Она берётся у заявки из стакана.
  • Не упомянуть риск-контроль. Биржа без лимитов до сделки — путь к сбою, когда ошибочный алгоритм участника отправляет миллион заявок.

Вопросы, которые могут задать дополнительно

  • Как сделать аукцион открытия? Заявки копятся без исполнения, затем ищется одна цена, при которой исполняемый объём максимален, и все сделки проходят по ней.
  • Как обрабатывать Replace? Уменьшение количества обычно сохраняет место в очереди, а изменение цены или увеличение количества — это отмена и новая заявка в хвосте.
  • Что делать с самосделками? Проверка self-trade prevention: если обе стороны от одного участника, одну из заявок отменяют вместо исполнения.
  • Как защитить рынок от обвалов? Ценовые коридоры и автоматическая приостановка торгов бумагой при резком движении.

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

Потренироваться в спокойной обстановке

Все задачи