Перед нами заключительная архитектурная секция в Яндексе. Задача — спроектировать сервис, который по координатам пользователя возвращает 100 ближайших заведений. В исходных данных около 100 миллионов точек, поэтому простой перебор не подходит.
Какие требования нужно уточнить в начале?
Короткий ответ: число запросов, допустимую задержку, объём и частоту обновления заведений, точность координат и состав ответа.
Нужно понять, ожидается ли результат за 50 мс или за секунду, как часто появляются новые заведения, нужны ли фильтры по типу и режиму работы, что делать при неточной геолокации. Полезно сразу оценить нагрузку: среднее и пиковое число запросов в секунду, размер карточки и долю чтений относительно записей.
На интервью кандидат узнал ключевой масштаб — 100 миллионов заведений. Это сразу исключает Pandas в памяти одного процесса и расчёт расстояния до каждой точки на каждом запросе.
Почему полный перебор не подходит?
Короткий ответ: он требует O(n) вычислений на запрос и плохо масштабируется с ростом данных и трафика.
Даже если одна операция быстрая, 100 миллионов расстояний нужно посчитать, отсортировать или поддерживать структуру лучших результатов. При сотнях одновременных пользователей стоимость повторяется. Предварительный пространственный индекс позволяет посмотреть только на небольшую область рядом с человеком.
Как quadtree ускоряет поиск?
Короткий ответ: дерево рекурсивно делит плоскость на четыре квадрата и хранит точки в листьях; запрос спускается только в пересекающиеся области.
Если квадрат полностью вне зоны поиска, всю его ветку можно отбросить. Если область пересекается, проверяем четыре дочерних квадрата. Так число кандидатов резко уменьшается, особенно при равномерном распределении точек.
Каждый уровень уточняет область поиска и позволяет не просматривать далёкие точки. Источник: OpenDSA, Virginia Tech, лицензия CC BY-SA 4.0.
В реальном проекте не обязательно писать дерево самостоятельно. PostgreSQL с PostGIS умеет выполнять KNN-поиск с GiST-индексом. Важно понимать принцип: индекс выбирает ближайших кандидатов без полного сканирования.
Как получить именно 100 ближайших заведений?
Короткий ответ: запросить кандидатов внутри начальной области, расширять её при нехватке точек, затем вычислить точное расстояние и взять первые 100.
Квадрат удобнее круга для quadtree: пересечение двух прямоугольников проверяется простым сравнением границ. Кандидаты из квадрата ещё не гарантированно ближайшие, поэтому финальная стадия считает расстояние от пользователя и сортирует ограниченный список.
Нужно учесть плотность города и окраины. Фиксированный радиус даст слишком много точек в центре и слишком мало за городом. Адаптивное расширение решает эту проблему. Чтобы не делать бесконечные запросы, задаём максимальную область и явно возвращаем меньше 100 результатов, если других заведений нет.
Как выглядит путь запроса через backend?
Короткий ответ: приложение вызывает публичный API, балансировщик выбирает здоровый экземпляр сервиса, а тот обращается к пространственному индексу и собирает карточки.
Один сервер становится точкой отказа и ограничением по нагрузке. Несколько одинаковых экземпляров backend можно масштабировать горизонтально. Балансировщик распределяет запросы по кругу, по числу соединений или другой политике и временно исключает узел после ошибок.
API также отвечает за валидацию координат, авторизацию при необходимости, лимиты запросов, таймауты и стабильный контракт ответа. Результаты популярных районов можно ненадолго кэшировать по ячейке координат, но кэш не должен показывать закрытые или удалённые места дольше согласованного срока.
Где хранить заведения и как пережить отказ базы?
Короткий ответ: основное состояние хранить в базе с геопространственным индексом, разделять чтение и запись при необходимости и иметь реплику с проверенным переключением.
Вместе с координатами нужны название, категория, статус, часы работы и версия данных. Пространственный индекс отвечает за поиск кандидатов, а обычные индексы — за фильтры. Две или несколько реплик повышают доступность чтения, но добавляют задержку обновления. На интервью важно назвать допустимую консистентность: может ли новое заведение появиться в выдаче через минуту или требуется мгновенное обновление.
Резервная копия не заменяет реплику, а реплика не заменяет резервную копию. Переключение должно быть автоматизировано и регулярно проверяться, иначе в аварии команда впервые узнает, что сценарий не работает.
Как собирать клики для будущего ранжирования?
Короткий ответ: отправлять события асинхронно в очередь или поток, затем сохранять их в аналитическом хранилище.
Клик пользователя не должен замедлять поиск. Приложение или backend формирует событие с идентификатором запроса, заведением, позицией в выдаче и временем. Потоковая система принимает большой объём событий, а обработчики проверяют схему, удаляют дубликаты и готовят данные для аналитики и моделей.
Прошёл ли кандидат собеседование?
В короткой версии окончательный ответ Яндекса не назван. Кандидат вместе с интервьюером пришёл к quadtree, адаптивной области поиска, нескольким backend-серверам, балансировщику и репликации базы. Однако ключевые шаги часто появлялись после подсказок.
Мы бы не делали уверенный вывод об оффере по одной секции. Для более сильного выступления стоило в первые минуты зафиксировать требования, самостоятельно предложить пространственный индекс и сразу нарисовать полный путь запроса. Техническая база есть, но структуру ответа нужно тренировать.
Источники
частые вопросы
Короткие ответы
Что проверяют на секции System Design в Яндексе?
Проверяют, как кандидат уточняет требования, оценивает масштаб, выбирает структуры данных, делит систему на компоненты и обсуждает отказоустойчивость, хранение и развитие решения.
Как найти ближайшие точки без полного перебора?
Использовать пространственный индекс: quadtree, R-tree, geohash или геопространственный индекс базы. Сначала индекс быстро даёт кандидатов, затем расстояние считается точно.
Зачем backend нужен балансировщик?
Он распределяет запросы между несколькими экземплярами приложения, исключает недоступные узлы и позволяет добавлять серверы по мере роста нагрузки.
Прошёл ли кандидат архитектурную секцию?
В короткой записи окончательное решение компании не раскрыто. По самому интервью кандидат нашёл основу решения, но часто двигался после подсказок, поэтому уверенно предсказать положительный результат нельзя.
