Системный дизайн биржи: стакан заявок, matching engine и журнал событий
Как спроектировать биржу на system design интервью: стакан заявок, matching engine с приоритетом цена-время, секвенсор и журнал событий, низкие задержки, риск-контроль и рыночные данные.
Коротко
| Вопрос | Решение в этом разборе |
|---|---|
| Сердце системы | matching engine: сводит заявки на покупку и продажу по одному инструменту |
| Структура данных | стакан заявок: уровни цен, на каждом уровне FIFO-очередь заявок |
| Правило исполнения | приоритет цена-время: сначала лучшая цена, при равной цене — кто раньше пришёл |
| Порядок | секвенсор присваивает каждой команде номер, журнал событий — единственный источник правды |
| Масштабирование | шардирование по инструментам; один инструмент — один поток, без блокировок |
| Отказоустойчивость | детерминированный движок + журнал = горячий резерв, который проигрывает те же события |
| Задержки | всё в памяти, никакой сети и диска внутри цикла сопоставления, бинарные протоколы |
| Рыночные данные | лента событий (L3), агрегированный стакан (L2), лучшие цены (L1); мультикаст + снапшоты |
Биржу дают на интервью, когда хотят проверить, понимаете ли вы, что «распределённо и горизонтально» — не всегда правильный ответ. Здесь всё наоборот: ядро системы принципиально однопоточное, а главная работа архитектора — не мешать ему. Задача похожа на платёжную систему требованием к корректности, но добавляет жёсткие требования к задержкам и строгий глобальный порядок событий.
Общий каркас секции описан в статье про подходы к проектированию систем. Идём по нему: требования, оценки, API, архитектура, затем вглубь — стакан, matching engine, журнал, задержки, рыночные данные.
Шаг 1. Требования
Сначала договоритесь о рамках. «Биржа» бывает разной: от криптобиржи с веб-интерфейсом до площадки, где торгуют только профессиональные участники через брокеров. На интервью обычно имеют в виду второе.
| Вопрос | Типичный ответ | Что это меняет |
|---|---|---|
| Кто подключается? | брокеры и маркет-мейкеры, не люди | бинарный API, постоянные соединения, а не REST из браузера |
| Какие заявки? | лимитные, рыночные, отмена, изменение | две операции над стаканом плюс сопоставление |
| Сколько инструментов? | несколько тысяч акций | естественный ключ шардирования |
| Торговая сессия? | днём, ночью клиринг и обслуживание | есть окно, чтобы сделать снапшоты и обнулить состояние |
| Расчёты, клиринг, депозитарий? | вне рамок | после сделки отдаём событие дальше и забываем |
Нефункциональные требования назовите сами:
- Справедливость. Две заявки, пришедшие в разном порядке, должны исполниться в этом порядке. Это не пожелание, а требование регулятора.
- Детерминизм. Одна и та же последовательность команд всегда даёт одни и те же сделки.
- Низкие и стабильные задержки. Важна не средняя, а p99 и p99.9: всплеск в 50 мс во время новостей обходится участникам дороже, чем стабильные 100 мкс.
- Ни одной потерянной заявки или сделки. Подтверждённое должно пережить падение сервера.
- Высокая доступность в торговые часы. Остановка торгов — инцидент, о котором пишут новости.
Шаг 2. Оценки
Цифры условные, но порядок важен. Как прикидывать, разобрано в статье про оценки на салфетке.
- 5 000 инструментов, торговая сессия около 8 часов.
- 1 млрд сообщений в день (заявки, отмены, изменения). Подавляющая часть — от алгоритмических участников, и большинство заявок отменяется, не дойдя до исполнения.
- В среднем сообщений в секунду, в пиках на открытии и на новостях — в 10–20 раз больше.
- Нагрузка распределена неравномерно: несколько самых ликвидных бумаг дают львиную долю потока.
- Сообщение в бинарном формате — 50–100 байт, то есть журнал за день — порядка 100 ГБ. Это легко пишется последовательно на один NVMe.
Вывод для интервьюера: по пропускной способности задача решается на нескольких серверах. Сложность не в объёме, а в порядке и задержках.
Шаг 3. API и поток заявки
Участники подключаются через шлюз по постоянному TCP-соединению. Исторически стандарт — протокол FIX, для скорости биржи дают собственные бинарные протоколы. Минимальный набор команд:
| Команда | Поля | Ответ |
|---|---|---|
NewOrder | client_order_id, инструмент, сторона, тип, цена, количество | Accepted / Rejected, затем Fill-ы |
Cancel | client_order_id или биржевой id | Cancelled / CancelRejected |
Replace | новая цена и/или количество | Replaced |
client_order_id уникален в рамках сессии участника и служит ключом идемпотентности: повтор после обрыва соединения не создаст вторую заявку.
Путь заявки:
- Шлюз (gateway) принимает соединение, аутентифицирует, проверяет формат.
- Риск-контроль до сделки (pre-trade risk): лимиты на размер заявки, допустимый коридор цены, хватает ли у участника обеспечения. Проверки синхронные, иначе бессмысленны.
- Секвенсор присваивает команде глобальный номер и пишет в журнал.
- Matching engine применяет команду к стакану и выдаёт события: принято, сделка, отменено.
- События уходят обратно участникам (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, она агрессивная: сразу исполняется против стакана. Иначе она пассивная и встаёт в очередь своего уровня.
Требования к операциям:
| Операция | Частота | Нужная сложность |
|---|---|---|
| узнать лучшую цену | на каждой заявке | |
| добавить заявку на уровень | очень часто | или |
| отменить заявку по id | чаще, чем сделки | |
| исполнить заявку в голове уровня | на каждой сделке |
Здесь — число уровней цен, обычно десятки-сотни активных. Классическая реализация:
- уровни одной стороны — в упорядоченной структуре (красно-чёрное дерево, куча) или в массиве, индексированном ценой в тиках: цена всегда кратна шагу, а торгуют рядом с текущей ценой;
- заявки уровня — в двусвязном списке: добавление в хвост, снятие с головы и удаление из середины за ;
- хеш-таблица
order_id → узел спискадля отмены за .
Цены хранятся целыми числами в тиках, никогда не float: на бирже превращается в заявку, которая не сошлась с встречной по «той же» цене.
Matching engine и приоритет цена-время
Правило исполнения, которое используют почти все биржи для акций, — приоритет цена-время (price-time priority, FIFO):
- Входящая заявка исполняется против лучшей встречной цены.
- Внутри уровня цены — против самой старой заявки.
- Цена сделки — цена заявки, которая стояла в стакане (мейкера), а не входящей (тейкера). Покупатель, готовый платить 102, при лучшей продаже 101 купит по 101.
- Исполнение продолжается, пока заявка не заполнена или встречные цены не перестали подходить. Остаток лимитной заявки встаёт в стакан.
Существуют и другие алгоритмы, например 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для цен. - Ставить метку времени в движке через системные часы. Резерв получит другие метки, и детерминизм пропадёт.
- Забыть отмены. Их в потоке больше, чем сделок, и отмена за поиском по списку — частая слабость решения.
- Путать цену сделки. Она берётся у заявки из стакана.
- Не упомянуть риск-контроль. Биржа без лимитов до сделки — путь к сбою, когда ошибочный алгоритм участника отправляет миллион заявок.
Вопросы, которые могут задать дополнительно
- Как сделать аукцион открытия? Заявки копятся без исполнения, затем ищется одна цена, при которой исполняемый объём максимален, и все сделки проходят по ней.
- Как обрабатывать
Replace? Уменьшение количества обычно сохраняет место в очереди, а изменение цены или увеличение количества — это отмена и новая заявка в хвосте. - Что делать с самосделками? Проверка self-trade prevention: если обе стороны от одного участника, одну из заявок отменяют вместо исполнения.
- Как защитить рынок от обвалов? Ценовые коридоры и автоматическая приостановка торгов бумагой при резком движении.
Если интервьюер просит сосредоточиться на одном месте, чаще всего это стакан и правило цена-время или журнал с детерминированным движком. Это две идеи, на которых держится весь дизайн.