Поисковые подсказки (typeahead) — это панель из топ-N вариантов запроса, которая обновляется по мере ввода и появляется почти везде: в поиске, адресной строке браузера, в полях мессенджеров и в товарном поиске магазинов. На первый взгляд это «маленькая фича», но за ней стоит самостоятельная архитектура с экстремально жёстким бюджетом задержки на каждое нажатие.
В отличие от соседнего кейса про полнотекстовый поиск, здесь мы ранжируем не документы, а запросы-кандидаты по префиксу. Основа — префиксная структура (trie, сжатый trie или FST) с предвычисленным top-K в узлах, горячий путь чтения через edge-кэш и тяжёлая офлайн-пересборка словаря из агрегированных частот запросов.
На интервью этот кейс ценят за чистое разделение онлайн/офлайн, понятные размены память↔задержка и обилие практических деталей: debounce, шардирование по префиксу, свежесть, персонализация, fuzzy-поиск по опечаткам и приватность логов. Разобрав его, вы получаете готовый каркас для разговора о любой системе подсказок.
Конвейерное мышление
Критичны приём данных, партиционирование, удаление дублей и задержки между стадиями обработки.
Слой сервинга
Решения по индексам, локальности кэша и пути запроса определяют пользовательскую задержку.
Окно консистентности
Явно фиксируйте, где допустима согласованность в конечном счёте и где нужны более строгие гарантии.
Стоимость и свежесть
Балансируйте скорость обновления данных и стоимость вычислений/хранения.
Постановка и границы продукта
Пользователь ещё не дописал запрос, а система уже должна угадать, что он ищет. Поисковые подсказки (typeahead, search autocomplete) — это панель из топ-N вариантов запроса, которая обновляется по мере ввода: набран префикс «sys», и сразу видны «system design», «system administrator» и так далее. Подсказки экономят нажатия и помогают сформулировать намерение; встречаются в поиске, адресной строке браузера, в полях «Кому» мессенджеров и в товарном поиске магазинов. Главная сложность здесь не в выдаче, а в том, что отвечать нужно на каждое нажатие и быстрее, чем человек печатает.
Граница с поисковой системой
Соседний кейс «Поисковая система» — про полнотекстовый поиск: инвертированный индекс, ранжирование документов и по уже отправленному запросу. ЭТОТ кейс — про то, что происходит до отправки: префиксный поиск, экстремально низкая задержка на каждое нажатие и ранжирование кандидатов-запросов (а не документов). Подсказки подбирают, что пользователь, скорее всего, ищет; поиск отвечает на уже выбранный запрос.
Что НЕ входит в кейс
Само и ранжирование результатов — это search-system-case
«Возможно, вы имели в виду…» после поиска — отдельная подсистема
Векторное сопоставление по смыслу — другой класс задач
Функциональные требования
Базовые возможности
- Топ-N (обычно 5–10) подсказок по введённому префиксу
- Ранжирование кандидатов по популярности (частоте запросов)
- Учёт свежести: всплеск интереса к новому запросу попадает в подсказки
- Подсветка совпавшего префикса в выдаче подсказок
- Фильтрация мусора, оскорблений и опасного контента
Расширенные возможности
- Персонализация по истории и контексту пользователя
- Терпимость к опечаткам (fuzzy / расстояние редактирования)
- Многоязычность и разные раскладки клавиатуры
- Совпадение по словам внутри запроса, а не только по началу строки
Нефункциональные требования
Подсказка должна успеть появиться раньше следующего нажатия, иначе она бесполезна. Поэтому ключевая метрика — задержка по на одно нажатие, а не время полного поиска. При этом нагрузка измеряется в и в несколько раз выше, чем у самого поиска: каждый символ запроса порождает свой вызов подсказок.
Почему задержка важнее, чем для поиска
Подсказки конкурируют со скоростью набора текста. Если пользователь печатает быстрее, чем приходят ответы, панель «мигает» устаревшими вариантами. Поэтому бюджет на одно нажатие меряют десятками миллисекунд (бюджет — до ~100 мс), а не сотнями, и доступность строят на мягкой деградации: если сервис подсказок недоступен, поле ввода всё равно работает — пользователь просто не видит панель. Подсказки не должны быть строго : небольшая задержка в обновлении частот незаметна.
Оценки масштаба
Связь
CDN и edge-кэш
Где гасить большую часть запросов подсказок ближе к пользователю
Числа ниже — порядковые оценки для интервью, а не реальные данные конкретной компании. Главный нелинейный множитель — длина запроса: каждое нажатие после первых символов генерирует отдельный вызов подсказок.
Допущения для расчёта
DAU, число поисков в день, эффективные запросы после debounce и пиковый множитель — входные параметры интервью-модели. Меняем их под продукт и заново пересчитываем QPS, память и исходящий трафик; сами цифры ниже не являются гарантией для Google, Amazon или другого конкретного сервиса.
Прикидка нагрузки (оценка)
Дано (порядки величин для интервью):
DAU = 100 млн пользователей
поисков на пользователя/день = 5
поисков/день = 500 млн
средняя длина запроса = ~20 символов
Нажатия → запросы подсказок:
обычно вызываем не каждый символ, а с debounce (раз в N символов)
допустим, эффективно ~6 запросов подсказок на один поиск
запросов подсказок/день = 500 млн × 6 = 3 млрд
Средний QPS подсказок:
3 млрд / 86 400 с ≈ 35 000 QPS
Пиковый QPS (×3) ≈ 100 000 QPS
Вывод: подсказки = более горячий путь, чем сам поиск,
потому критичен edge-кэш и предвычисление top-K.Все значения помечены как оценки. На интервью важно показать сам ход рассуждения, а не «точные» цифры.
Объём словаря и память
- Уникальных запросов — десятки–сотни миллионов после обрезки «длинного хвоста»
- Сырой словарь — при ~20 байт на запрос это единицы гигабайт текста
- Префиксная структура — сжатый /FST уменьшает это в разы за счёт общих префиксов
Пропускная способность ответа
- Ответ — 10 подсказок × ~30 байт ≈ 300 байт + накладные расходы
- Трафик — 100K × ~0,5 КБ ≈ 50 МБ/с исходящих (оценка)
- Кэш — высокий процент попаданий на коротких префиксах сильно снижает нагрузку на бэкенд
Структуры данных для префикса
Связь
Inverted index vs trie
Поиск опирается на инвертированный индекс, подсказки — на префиксную структуру
Базовая структура для поиска по префиксу — (префиксное дерево): общий путь от корня описывает общий префикс, а в листьях и узлах лежат сами запросы. Ключевая идея для скорости — хранить на узле уже готовый список лучших подсказок (), чтобы не обходить всё поддерево на каждое нажатие.
Как top-K на узлах ускоряет ответ
Trie с предвычисленным top-K в узлах:
(root)
│
s ──► top-K: [system design, system, ...]
│
y ──► top-K: [system design, system, ...]
│
s ──► top-K: [system design, system admin, ...]
(префикс "sys")
Запрос на "sys":
1. спуститься по узлам s → y → s (O(длина префикса))
2. вернуть готовый top-K из узла (O(K), без обхода поддерева)
Без top-K в узлах пришлось бы обойти всё поддерево
и отсортировать кандидатов на каждое нажатие.Варианты хранения
- Обычный
Прост, но прожорлив по памяти: много узлов с одним потомком
- Сжатый (radix tree)
Склеивает цепочки одиночных узлов — меньше памяти, тот же поиск по префиксу
- FST (finite state transducer)
Минимизированный автомат: делит и префиксы, и суффиксы. Именно его используют Lucene и Elasticsearch для completion suggester
Компромисс память ↔ задержка
- в узлах
Память растёт (K вариантов на узел), зато ответ — почти O(длины префикса)
- Вычисление на лету
Экономит память, но требует обхода поддерева и сортировки — дороже по задержке
- FST в памяти
Очень компактно, но выше CPU при обходе автомата — классический размен RAM на процессор
💡 FST в Lucene/Elasticsearch
Completion suggester в Elasticsearch строится поверх взвешенного FST, который держится целиком в памяти. По бенчмарку Elastic 2013 года, на ~2,1 млн заголовков Википедии completion suggester отвечал за доли миллисекунды против нескольких миллисекунд у обычного префиксного запроса. Размен прямой: FST экономит RAM и даёт быстрый префиксный поиск, но дороже в построении и обновляется по сегментам, а не «по одной записи».
Архитектура: онлайн и офлайн
Связь
Шардирование структуры
Как разнести префиксную структуру и счётчики частот по шардам
Главная архитектурная идея — разделить горячий путь чтения и тяжёлый путь обновления. На чтении мы только спускаемся по готовой структуре и отдаём . Обновление (сбор логов, агрегация частот, пересборка структуры) — офлайн-процесс, который периодически выкатывает новую версию структуры.
Автодополнение на trie
Выберите префикс, чтобы посмотреть путь в trie и подсказки
Путь в trie
3 символов
< 50 мс
Топ-результаты хранятся в узле префикса
Лучшие подсказки
- system design
- system
- system administrator
- system metrics
Кэш Top-K
На узлах trie хранится список подсказок (Top-10), чтобы не обходить все поддерево.
Путь чтения (онлайн, горячий)
- 1.Нажатие → запрос к ближайшему /кэшу
- 2.Кэш-промах → сервис подсказок выбирает нужный шард по префиксу
- 3.Спуск по /FST до узла префикса
- 4.Возврат предвычисленных (опционально — переранжирование под пользователя)
- 5.Запись результата в кэш на короткое
Путь обновления (офлайн, тяжёлый)
- 1.Сбор логов запросов в очередь/лог-стрим
- 2.Агрегация частот за окно (час/сутки) с затуханием старых данных
- 3.Фильтрация: мусор, оскорбления, редкий «длинный хвост»
- 4.Офлайн-пересборка /FST с готовыми на узлах
- 5.Атомарная выкатка новой версии структуры на узлы чтения
Шардирование по префиксу
Структуру разбивают по диапазонам первых символов: каждый узел держит свою часть словаря. Маршрутизатор по первым 1–2 символам направляет запрос в нужный шард. Это ограничивает память на узел и распределяет нагрузку, но порождает «горячие» шарды на популярных буквах — их балансируют дополнительными репликами.
shard(prefix) = route_by_first_chars(prefix) префиксы a–f → шард 1 (+ реплики) префиксы g–m → шард 2 (+ реплики) префиксы n–z → шард 3 (+ реплики) Горячие буквы получают больше реплик, очень короткие префиксы — отдаются из edge-кэша.
Ранжирование кандидатов-запросов
В отличие от поиска, здесь ранжируют не документы, а запросы-кандидаты. Базовый сигнал — частота запроса; поверх него накладывают свежесть, персонализацию и контекст. По короткому префиксу нужно угадать намерение раньше, чем пользователь его дописал, — поэтому сигналы подбирают так, чтобы вероятный вариант оказался в верхних строках с первых нажатий.
Сигналы ранжирования
- Частота
Как часто запрос вводят — основной вес кандидата
- Свежесть (recency)
Затухание по времени поднимает то, что популярно сейчас, а не год назад
- Персонализация
История пользователя и его сегмент сдвигают порядок
- Контекст
Язык, регион, устройство, время суток
Защита от мусора и взрывов
- Порог частоты
Редкие запросы и опечатки не попадают в словарь
- Блок-листы и классификаторы
Оскорбления, опасный и взрослый контент фильтруются до выдачи
- Защита от накруток
Аномальный всплеск одного запроса с узкой группы ботов гасится
- Контроль свежего хвоста
Новый запрос поднимают осторожно, чтобы не продвигать шум как тренд
⚡ Простая формула веса (для интервью)
score(q) = w1 × log(freq(q))
+ w2 × recency_decay(q)
+ w3 × personalization(q, user)
− w4 × spam_penalty(q)
freq — агрегированная частота запроса
recency — экспоненциальное затухание по времени
personal — близость к истории пользователя
spam — штраф за аномалии и блок-листыФормула иллюстративная. На практике веса подбирают офлайн, а тяжёлую ML-модель применяют как опциональный переранжировщик уже к коротким .
Опечатки и нечёткость
Точный поиск по префиксу не прощает опечаток: «sytsem» не найдёт «system». Нечёткость добавляют осознанно, потому что она дороже — это размен между качеством подсказок и бюджетом задержки.
Расстояние редактирования
Допускаем 1–2 правки (вставка, удаление, замена). На FST это реализуют через автомат Левенштейна — но fuzzy расширяет пространство поиска, поэтому его обычно включают только для коротких или редко совпадающих префиксов.
N-граммы
Запрос бьют на n-граммы (например, по 3 символа) и ищут пересечение. Это ловит опечатки и совпадения внутри строки, но требует отдельного индекса и даёт более шумные кандидаты, чем строгий префикс.
Когда включать fuzzy
Сначала пробуем точный префикс; fuzzy подключаем как запасной путь, если точных кандидатов мало. Так в типичном случае задержка остаётся низкой, а опечатки всё равно обрабатываются.
💡 Fuzzy в completion suggester
Completion suggester в Elasticsearch поддерживает fuzzy-запросы с настраиваемым расстоянием редактирования прямо поверх FST: правки разрешают начиная с некоторой позиции (чтобы не «плыло» начало слова) и ограничивают их число. Это типичный приём — оставить начало префикса строгим, а терпимость к опечаткам разрешить только дальше.
Глубокие разборы
Кэширование и доставка
- Edge-кэш коротких префиксов — самые частые начала запросов отдаются из , не доходя до серверной части
- Debounce на клиенте — не слать запрос на каждое нажатие, а ждать паузы в наборе
- Инкрементальная доставка — клиент дополняет уже показанный список, а не перерисовывает его целиком
- Отмена устаревших ответов — поздно пришедший ответ на старый префикс игнорируется
Данные, языки, приватность
- Дедупликация — нормализация регистра, пробелов и эквивалентных вариантов одного запроса
- Многоязычность — отдельные структуры по языкам/регионам, учёт раскладок и транслитерации
- Приватность логов — агрегирование частот по многим пользователям, k-анонимность, отсев редкого личного хвоста
- Хранилище счётчиков — частоты держат в key-value хранилище с шардированием по запросу
Компромиссы и частые ошибки
Что обсудить обязательно
- Граница: подсказки запросов против поиска документов
- Размен память ↔ задержка: в узлах против вычисления на лету
- Разделение онлайн-чтения и офлайн-пересборки структуры
- Свежесть данных против стоимости пересборки и выкатки
- Мягкая деградация: что показываем, если сервис подсказок недоступен
Частые уточняющие вопросы
- Как доставлять свежие тренды в течение часов, а не суток?
- Как добавить персонализацию, не ломая кэш?
- Как обрабатывать опечатки без скачка задержки?
- Как фильтровать оскорбления и опасный контент?
- Как защититься от накрутки частот ботами?
Типичные ошибки на интервью
- Путать подсказки с поиском и проектировать инвертированный индекс вместо префиксной структуры
- Обновлять на каждое нажатие в реальном времени вместо офлайн-пересборки
- Забывать про edge-кэш и debounce — и получать раздутый поток на серверной части
- Игнорировать фильтрацию мусора и приватность логов запросов
Ключевые выводы
Подсказки ≠ поиск
Typeahead ранжирует запросы-кандидаты по префиксу, а не документы по запросу
Префиксная структура
trie/сжатый trie/FST с предвычисленным top-K в узлах даёт ответ почти за длину префикса
Онлайн против офлайн
Горячий путь только читает; частоты агрегируются и структура пересобирается офлайн
Задержка — главная метрика
p99 на нажатие меряют десятками миллисекунд; edge-кэш и debounce снимают большую часть нагрузки
Качество и безопасность
Свежесть, персонализация, защита от мусора и приватность логов — часть дизайна, а не довесок
Источники и материалы
Связанные главы
- Поисковая система - соседний кейс про полнотекстовый поиск: инвертированный индекс, ранжирование документов и retrieval — там, где typeahead заканчивается на отправке запроса.
- CDN (сеть доставки контента) - объясняет edge-кэширование и географическое распределение, на которых держится низкая задержка подсказок на каждое нажатие.
- Распределённое key-value хранилище - раскрывает шардирование и реплики, нужные для хранения префиксных структур и счётчиков частот запросов.
- Архитектура ранжирования и рекомендаций - углубляет персонализацию и ML-сигналы, которыми расширяют простое ранжирование кандидатов-запросов по частоте.