Перейти к содержанию

Stock Exchange System Design

Функциональные требования

  • Клиент отправляет заявку на покупку/продажу
  • Заявки с подходящей ценой должны матчится друг с другом
  • Клиент должен получать уведомление об исполнении сделки

Клиент может разместить заявку на покупке/продажу актива не выше/ниже определенной цены.
Заявка состоит из количества активов и цены (например заявку на покупку 5 монет за 8.50$).
Заявки по одному активу должны обрабатываться строго в определенной последовательности.

Заявки на покупку мэтчится с заявками на продажу по цене. Необходимо обеспечить клиентам лучшую сделку. Например, метчинг происходит, если Вася хочет продать актив как минимум за 10$ и находится Петя, который хочет купить актив не более чем за 12$. В этом случае Вася получает 10$, а Петя получает свой актив. Возможен частичный матчинг, когда Петя хочет купить 100 штук, а Вася продает только 50. Тогда Васина заявка исполняется полностью и покидает стакан, а Петина заявка остается в стакане ждать продавца еще на 50 штук. Все заявки, которые не получается пока сметчить остаются ждать.

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

  • 100 000 операций в секунду
  • высокая доступность
  • консистентность
  • 5 000 видов активов

Ключевые моменты

  • Как соблюсти очередность заявок по активу?
    • Отдельные очереди заявок для каждого актива
  • Как быстро матчить заявки?
    • Делать это в памяти
    • Использовать правильные структуры данных. Например, одну PriorityQueue на заявки по покупке и одну PriorityQueue на заявки по продаже. Добавление новой заявки будет за O(log n). Получение максимума/минимума за O(1). Но если будет возможно отменять заявки, то это будет работать медленно, за O(n). Другой вариант - SortedMap, где ключ - цена, значения - связанный список заявок по данной цене.
  • Как эффективно уведомлять всех потребителей информации о сделках?
    • Один из варианов - очереди, например Kafka. Из коробки высокая latency, но можно настройками добиться 1-5мс на передачу сообщения.
    • Больше подходит UDP Multicast или TCP.
  • Как добиться отказоустойчивости сервиса матчинга?
    • Держать запущенными несколько сервисов матчинга. Основной и запасной. Оба обрабатывают все заявки. Либо параллельно друг другу, либо обрабатывает только основной и постоянно копирует результаты в запасной.
    • Для определения основного и резервного сервиса и переключением между ними нужен фунционал Leader election. Например, его можно получить, при помощи Zookeeper.
  • Как маштабироваться?
    • Запускать отдельные сервисы матчинга на актив или группу активов, распределять по ним заявки.

Ссылки