Загрузка…
Загрузка…
backend / middle / system_design
Формат
online
Стадия
system_design
Когда
within_quarter
Длительность
90 мин
01
Поведенческий
Был ли у вас опыт прохождения архитектурных секций в Яндексе или других компаниях?
Вводный вопрос перед началом технической части
02
System design
Спроектируйте сервис «Яндекс Пробки»: MVP оценки пробок по всему миру на базе GPS-треков, которые присылают телефоны водителей (координаты + время раз в ~20 секунд). Нужно придумать бэкенд, который оценивает загруженность дорог, и способ отдачи этих данных существующему клиентскому стеку.
Основная задача секции: полчаса на высокоуровневую схему, полчаса на погружение в детали. Авторизацию и смежные детали проектировать не требовалось.
03
System design
Оцените нагрузку: сколько активных машин одновременно может быть в Москве / в мире, сколько точек треков в секунду будет приходить и какой объём данных нужно хранить?
Интервьюер дал ориентир: ~100 млн машин в мире едут одновременно в пике; сошлись на ~1 млн машин в Москве, точка раз в 20 секунд.
Заметки
Архитектурная секция в Яндексе. Интервьюер — Егор, более 10 лет в Яндексе, руководит отделом инфраструктуры в рекламе; присутствовал второй наблюдатель (shadow) Александр с выключенными звуком и видео. Слот 1,5 часа: 1 час техническая часть (полчаса на высокоуровневую схему, полчаса на детали), остальное — буфер и вопросы кандидата. Инструменты: текстовый редактор Яндекс-интервью и Excalidraw. Результат на момент транскрипта не объявлен — кандидат ожидает итогов всех собеседований.
Подготовка
Структура секции: за первые полчаса дать высокоуровневую схему системы (компоненты, связи, потоки данных), за вторые полчаса погружаться в детали отдельных компонент (базы данных, протоколы, отказоустойчивость). Интервьюер играет роль смежников (продакта, аналитика) — нужно активно задавать уточняющие вопросы для корректировки требований. Полезно уметь делать capacity estimation (оценки числа пользователей, RPS, объёмов данных).
Стиль интервьюера
Доброжелательный, направляющий стиль: интервьюер подробно объяснил формат, давал ориентировочные числа для оценок, подтверждал разумные идеи («звучит очень хорошо») и двигал дальше, когда часть была понятна. Активно копал вглубь follow-up'ами: коллизии при параллельной обработке, задержки данных, падения компонент, реализация очереди, привязка шумной GPS-точки к дороге. Добавлял реалистичные ограничения по ходу («клиентский протокол менять нельзя — релиз займёт полгода»).
04
System design
Предложите алгоритм: как из GPS-треков получить оценку пробочной загруженности дорог?
Кандидат предложил разбить дороги на сегменты (~100 м) и считать среднюю скорость прохождения сегмента.
05
System design
За 100 метров (длина сегмента) за 20 секунд (интервал отправки точек) машина останется в одном сегменте или переедет в другой? Как обрабатывать треки, когда между двумя соседними точками машина прошла несколько сегментов, на которые не попало ни одной точки?
Привело к идее графа связности сегментов и восстановления промежуточного пути между точками.
06
System design
Нарисуйте схему системы: из каких компонент (сервисов) она состоит, как между ними устроены связи и как едут данные?
Рисование в Excalidraw: балансер, веб-сервис, очередь событий, предварительная математика (rt), Redis-хранилище, математика пересчёта пробок, хранилище карты/сегментов.
07
System design
Какую задержку между приходом свежего трека и его учётом в показываемом пользователю вердикте о пробках может обеспечить такая система? Например, на дороге случилась авария и всё встало — через какое время это отразится?
Обсуждали ленивый пересчёт раз в ~5 минут и пересчёт только по сегментам, где было движение.
08
System design
Кто и как инициирует расчёт пути по новой точке (realtime-математику)? Как событие о новой точке попадает в обработку?
Кандидат предложил очередь событий между веб-сервисом и предварительной математикой.
09
Теория
Очередь событий — это технологически что? Какой инструмент вы бы использовали?
Кандидат назвал RabbitMQ, in-memory хранилище без сохранения на диск; Redis — с персистенцией на диск.
10
System design
Как масштабируется система по регионам и по машинам: каждый компонент — это одна машина или несколько? Если инстансов математики несколько, как между ними распределяется нагрузка в рамках одного региона?
Кандидат с самого начала предложил локальность: разбиение на региональные кластеры (Москва общается только со своим узлом).
11
System design
Могут ли возникнуть конфликты/коллизии, если несколько инстансов математики обрабатывают данные параллельно (например, один и тот же трек посчитают два разных воркера)? Как это предотвратить?
Обсуждали и для rt-математики, и для математики пробок.
12
System design
Для обработки точки нужна предыдущая точка того же водителя, но клиентский протокол менять нельзя (обновление клиентов займёт полгода). Как хранить предыдущую точку и как избежать гонок, когда несколько воркеров одновременно обрабатывают точки одного пользователя?
Кандидат предложил хранить предыдущую точку в Redis с TTL и ставить блокировку на машину с истечением по таймауту.
13
System design
Как математика пробок определяет, какие сегменты пересчитывать? Делает ли она select всего из Redis или есть механизм распределения работы?
Кандидат предложил циклическую очередь сегментов: взял из головы — поставил в хвост, с TTL на обработку.
14
System design
На чём реализовать такую распределённую циклическую очередь (взять из головы, элемент остаётся залоченным, при падении воркера по TTL возвращается на обработку)? Есть ли готовые инструменты или как собрать из подручных средств?
Кандидат не знал готовых инструментов, предложил написать собственный in-memory сервис, держащий все сегменты в памяти.
15
System design
Что будет, если сегмент обработается два раза (воркер успел записать результат, но умер до подтверждения)? И что будет, если сам in-memory сервис очереди упадёт и потеряет состояние?
Сошлись на том, что двойной пересчёт не страшен, а очередь можно просто пересоздать заново — персистентность не нужна.
16
System design
GPS шумит и не всегда даёт координату строго на дороге. Как привязать пришедшую точку к сегменту дороги? Как организовать быстрый поиск ближайшего сегмента?
Обсуждали bounding box вокруг сегментов, сортировку по координатам; интервьюер указал на проблему перебора всех квадратов, в итоге пришли к разбиению плоскости на сетку (как тетрадный лист) с последующим перебором кандидатов. Кандидат упомянул аналогию с пространственным индексом в PostgreSQL.
17
Кейс
Что в этой системе ещё стоит продумать? Если отдать эту схему джунам/мидлам в разработку, что важное нужно им дополнительно объяснить?
Финальный вопрос секции. Кандидат ответил: формализовать API внешнего протокола, чтобы параллельно разрабатывать клиентов, описать форматы хранения.