Спроектируйте подсказки поиска
Вопрос
Спроектируйте подсказки в строке поиска: по мере ввода пользователь видит 10 популярных запросов, начинающихся с введённого текста.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Требования: 10 подсказок по префиксу, ранжирование по популярности, обновление раз в час или сутки достаточно, ответ < 100 мс сквозной, фильтр запрещённых запросов; персонализация вне рамок
Оценка нагрузки: 10 млн DAU, 5 поисков в день, ~6 запросов подсказок на поиск с debounce ≈ 3 × 10^8 в сутки ≈ 3 000 RPS, пик ~10 000; 10 млн уникальных запросов в словаре, дерево с топ-K помещается в несколько ГБ памяти
API: GET /suggest?q=пре&limit=10 → [строки]; ответ кешируемый (Cache-Control на минуты)
Данные: логи поиска в ClickHouse или HDFS, агрегат «запрос → частота» за окно, офлайн-сборка trie с топ-K на каждом узле, сериализованный снимок в объектном хранилище
Компоненты: сборщик логов, периодическая задача построения дерева, сервис подсказок держит дерево в памяти (несколько реплик, загружают свежий снимок), CDN и кеш браузера для популярных префиксов, debounce на клиенте
Узкие места: память дерева (ограничить длину и число запросов), свежесть трендов (дополнительный слой «горячих» запросов за последний час), задержка сети (CDN, гео), фильтрация, шардирование по префиксу при росте
Что могут спросить следом
- Как быстро подхватить внезапно популярный запрос?
- Как уменьшить число запросов от клиента?
- Как шардировать, если дерево не влезет в память?
Разбор
Требования: 10 подсказок по префиксу, отсортированных по популярности, сквозная задержка до 100 мс, допустимо обновлять данные раз в час. Нагрузка: 10 млн DAU, 5 поисков в день и около 6 запросов подсказок на поиск при debounce, это около 3 000 RPS, в пике 10 000. Словарь 10 млн запросов, дерево с готовыми топ-10 на узлах займёт единицы гигабайт, это помещается в память одного сервера. Офлайн: логи поиска собираются в ClickHouse, раз в час считаются частоты, строится trie, где в каждом узле уже лежит топ-10, снимок кладётся в S3. Онлайн: несколько реплик сервиса подсказок держат дерево в памяти и периодически подгружают свежий снимок. Ответ это спуск по префиксу и чтение готового списка, микросекунды. Популярные короткие префиксы кешируются в CDN и браузере. Для трендов добавляю маленький слой горячих запросов за последний час, который подмешивается к ответу. Если дерево перерастёт память, шардирую по первым символам префикса.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.