
Условие
Однопоточное исполнение здесь — решение, а не ограничение: оно даёт детерминизм. А произведение изменений на подписчиков не помещается ни в какую сеть, и выбрасывать изменения нельзя: доставляется не каждое изменение, а верное текущее состояние.
Спроектируйте торговую систему с книгой заявок.
Участник выставляет заявку купить или продать по цене либо по рынку. Система сводит встречные заявки, публикует сделки и текущее состояние книги подписчикам. Заявку можно отменить, пока она не исполнена.
Считайте, что:
- две заявки по одной цене исполняются в порядке поступления, и этот порядок должен быть воспроизводим; - после сбоя система обязана прийти ровно в то же состояние, а не в похожее; - участник получает подтверждение приёма заявки не дольше чем за 1 мс на p99, и подтверждённая заявка не может пропасть; - подписчик читает котировки с экрана: ему нужна верная картина книги не старше 200 мс, а неверная цена — ущерб.
Расчёты и клиринг, маржинальное кредитование, надзорная отчётность, риск участников (контроль экспозиции и кредитных лимитов), деривативы и аукционы открытия и закрытия в задачу не входят. Регуляторные требования и правила допуска — тоже: это учебный разбор интервью-задачи, а не проект торговой системы.
Требования
Функциональные 6
- Приём лимитной и рыночной заявки на покупку и продажу
- Сведение встречных заявок по приоритету «цена, затем время»
- Отмена неисполненной заявки с определённым исходом: отменена полностью, частично или отменять нечего
- Поток сделок и состояния книги подписчикам
- Воспроизводимость: одна и та же последовательность заявок даёт одну и ту же последовательность сделок
- Восстановление после сбоя: книга возвращается в то же состояние, исполненное не теряется
Нефункциональные 4
- Подтверждение приёма заявки участнику: p99 < 1 мс
- Подтверждённая заявка не теряется при отказе одного узла
- Картина книги у подписчика отстаёт от матчинга не больше чем на 200 мс на p99
- После отказа основного узла матчинг возобновляется не позже чем через 10 с
Задачи того же уровня
СложнаяДрузья рядомпоток координат по графу дружбыДрузья в радиусе 5 км вживую: 333 тысячи координат в секунду, у каждой свой круг получателей, и этот круг постоянно меняется. Нерв задачи в адресной рассылке и в отзыве доступа, который должен обогнать следующую координату.
СложнаяИнференс языковой моделиДвенадцать запросов в секунду, а ограничен дорогой ускоритель: его память и время. Нерв задачи в том, чтобы карта не простаивала и не переполнялась.
СложнаяКорзина и оформление заказаЧетыреста попыток в секунду зарезервировать один и тот же остаток и три владельца данных, которых нельзя закрыть одной транзакцией. Нерв задачи: деньги и остаток, объём здесь невелик.
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




