Системный дизайн поисковых подсказок: trie с топ-k, частоты, кэш и шардирование
Как спроектировать автодополнение поиска на system design интервью: требования, оценка нагрузки, trie с топ-k в узлах, сбор частот из логов, кэш в браузере и CDN, шардирование и бюджет задержки.
Коротко
| Вопрос | Решение в этом разборе |
|---|---|
| Нагрузка | около 29 тыс. запросов подсказок в секунду в среднем, около 90 тыс. в пике |
| Задержка | ответ сервера за единицы миллисекунд, вся подсказка у пользователя до 100 мс |
| Структура данных | trie, в каждом узле заранее посчитан топ-k запросов |
| Откуда частоты | логи поиска → очередь → агрегация по дням → затухание старых данных |
| Обновление | индекс пересобирается офлайн и подменяется целиком, а не правится на лету |
| Кэш | браузер, CDN, затем память сервиса; короткие префиксы почти всегда в кэше |
| Шардирование | по диапазонам префиксов с учётом трафика, плюс реплики горячих шардов |
| Главный компромисс | свежесть подсказок против простоты и скорости чтения |
Подсказки в поисковой строке выглядят как одна структура данных, и многие кандидаты так и отвечают: «возьмём trie». Это треть ответа. Интервьюер хочет услышать, откуда берутся частоты, как индекс обновляется без простоя и почему сервер не захлебнётся, если каждое нажатие клавиши превращается в запрос.
Общая схема system design секции описана в статье про подходы к проектированию систем. Здесь она применена к одной задаче от начала до конца.
Как распределить время
| Этап | Минуты | Что должно остаться на доске |
|---|---|---|
| Требования | 5 | что подсказываем, сколько, насколько свежее |
| Оценка нагрузки | 5 | QPS, размер индекса |
| API и общая схема | 5 | путь чтения и путь сбора данных |
| Trie с топ-k | 10 | структура, сложность, память |
| Сбор частот и обновление | 8 | конвейер от логов до нового индекса |
| Кэш, шардирование, задержка | 10 | где отвечаем, как режем данные, бюджет в мс |
| Узкие места и вопросы вглубь | 2–5 | горячие префиксы, тренды, персонализация |
Типичная ловушка — полчаса писать trie на доске. Код тут вторичен: структуру хватит нарисовать и назвать сложность операций.
Шаг 1. Требования
Каждый вопрос должен что-то менять в дизайне.
| Вопрос | Ответ интервьюера | Что это меняет |
|---|---|---|
| Что подсказываем: запросы, товары, людей? | популярные поисковые запросы | источник данных — логи поиска |
| Сколько подсказок? | 10 | , топ-k храним заранее |
| Только совпадение по началу строки? | да, исправление опечаток — потом | хватает префиксного дерева |
| Насколько свежими должны быть? | сутки нормально, тренды — за час | основной индекс пакетный, тренды отдельно |
| Нужна персонализация? | нет, на первом этапе одинаково всем | ответ можно кэшировать для всех пользователей |
| Языки? | русский и английский | нормализация: регистр, «ё», пробелы |
| Фильтрация? | запрещённые запросы не показываем | чёрный список на этапе сборки индекса |
Нефункциональные требования предложите сами:
- Подсказка должна появиться быстрее, чем человек наберёт следующую букву. Ориентир — 100 мс от нажатия до отрисовки. Иначе подсказка запаздывает и мешает.
- Доступность высокая, но падение подсказок не ломает поиск: строка продолжает работать, просто без выпадающего списка. Поэтому деградация допустима.
- Строгая согласованность не нужна. Если два пользователя увидят слегка разные списки, никто не пострадает.
Последний пункт важен: он разрешает кэши, реплики с отставанием и пакетное обновление. Проговорите это вслух, на этом держится весь дизайн.
Не делаем: исправление опечаток, персонализацию, подсказки по середине слова. Вернёмся к ним в конце как к расширениям.
Шаг 2. Оценка нагрузки
Допущения, которые предлагаете вы:
- 50 млн активных пользователей в день, каждый делает 10 поисков.
- Средний запрос — 15–20 символов. Клиент не шлёт запрос на каждую букву: задержка перед отправкой и кэш в браузере оставляют примерно 5 запросов на поиск.
- Пик в 3 раза выше среднего.
- В индексе держим 50 млн самых частых уникальных запросов, хвост отрезаем.
| Параметр | Расчёт | Результат |
|---|---|---|
| Поисков в сутки | 50 млн × 10 | 500 млн |
| Запросов подсказок | 500 млн × 5 | 2,5 млрд в сутки |
| Средний QPS | 2,5 млрд / 86 400 | около 29 тыс. |
| Пиковый QPS | 29 тыс. × 3 | около 90 тыс. |
| Строки запросов | 50 млн × 40 байт (UTF-8) | около 2 ГБ |
| Узлы trie | допустим, 300 млн | см. ниже |
| Узел с топ-10 по id | 10 × 4 байта + 20 байт служебных | около 60 байт |
| Весь индекс | 300 млн × 60 байт + 2 ГБ | около 20 ГБ |
| Логи поиска | 500 млн × 100 байт | около 50 ГБ в сутки |
Выводы, которые надо сделать из таблицы:
- Индекс помещается в память. 20 ГБ — это одна машина с запасом. Значит, никакой базы данных на пути чтения: только структура в RAM.
- Шардировать нужно ради QPS, а не объёма. 90 тыс. запросов в секунду — это несколько десятков реплик, даже если одна держит десятки тысяч.
- Запись и чтение живут в разных мирах. 50 ГБ логов в сутки обрабатываются пакетно, на скорость ответа это не влияет.
Число узлов — самое слабое допущение. Верхняя граница — 50 млн × 20 символов = 1 млрд, но у запросов общие префиксы, и реальное число заметно меньше. Скажите об этом прямо: интервьюер оценит, что вы видите, где цифра взята с потолка.
Шаг 3. API и общая схема
Эндпоинт один:
GET /api/v1/suggest?q=пого&lang=ru&limit=10
HTTP/1.1 200 OK Content-Type: application/json Cache-Control: public, max-age=3600 { "prefix": "пого", "suggestions": ["погода", "погода москва", "погода спб"] }
Cache-Control: public — не мелочь. Без персонализации ответ одинаков для всех, и его могут кэшировать браузер и CDN. Это главный рычаг против 90 тыс. QPS.
Система делится на два пути, и их стоит нарисовать раздельно:
Чтение (онлайн, миллисекунды): браузер -> CDN -> балансировщик -> сервис подсказок (trie в памяти) Сбор данных (офлайн, часы): поиск -> лог запросов -> очередь -> агрегация частот -> сборщик trie | снапшот в хранилище объектов | сервисы подсказок загружают новую версию
Сервис подсказок ничего не пишет. Он загружает готовый снапшот, отвечает из памяти и раз в несколько часов меняет снапшот на новый. Это упрощает почти всё остальное.
Шаг 4. Trie с топ-k в узлах
Как устроено само префиксное дерево, разобрано в статье про trie. Здесь важен один вопрос: как быстро получить 10 лучших продолжений префикса.
Наивный вариант
Спуститься по префиксу, обойти всё поддерево, собрать все запросы и выбрать 10 самых частых. Для префикса длины с поддеревом из узлов и запросов это , если отбирать лучшие через кучу размера .
Для длинного префикса поддерево маленькое, и всё хорошо. Для префикса «п» поддерево — заметная часть всего индекса. Обходить миллионы узлов на каждое нажатие нельзя. А короткие префиксы как раз самые частые: каждый поиск начинается с одной буквы.
Топ-k храним в узле
Переносим работу со времени чтения на время сборки. В каждом узле лежит готовый список из лучших запросов его поддерева. Тогда чтение — это спуск на шагов и возврат готового списка: , от размера индекса не зависит.
Считается такой список снизу вверх: топ-k узла — это лучшие из его собственного запроса (если в узле заканчивается запрос) и топ-k всех детей. Запрос, не попавший в топ-k ребёнка, не может попасть и в топ-k родителя, поэтому глубже смотреть не нужно.
class Node: __slots__ = ("children", "top") def __init__(self): self.children = {} self.top = [] # до k пар (частота, запрос), лучшие первыми def rank(pairs, k): # больше частота — выше; при равенстве по алфавиту, чтобы порядок был стабилен return sorted(pairs, key=lambda p: (-p[0], p[1]))[:k] class AutocompleteTrie: def __init__(self, k=10): self.k = k self.root = Node() def build(self, freqs): """freqs: словарь запрос -> частота. Строим офлайн, целиком.""" for query in freqs: node = self.root for ch in query: node = node.children.setdefault(ch, Node()) self._fill(self.root, "", freqs) def _fill(self, node, prefix, freqs): # top-k узла = лучшие из его собственного запроса и top-k детей candidates = [] if prefix in freqs: candidates.append((freqs[prefix], prefix)) for ch, child in node.children.items(): self._fill(child, prefix + ch, freqs) candidates.extend(child.top) node.top = rank(candidates, self.k) def suggest(self, prefix): node = self.root for ch in prefix: node = node.children.get(ch) if node is None: return [] return [query for _, query in node.top] freqs = { "погода": 900, "погода москва": 700, "погода спб": 400, "почта": 650, "почта россии": 600, "поезда": 300, "покемон": 50, "пицца": 500, } trie = AutocompleteTrie(k=3) trie.build(freqs) print(trie.suggest("по")) # ['погода', 'погода москва', 'почта'] print(trie.suggest("пог")) # ['погода', 'погода москва', 'погода спб'] print(trie.suggest("пиц")) # ['пицца'] print(trie.suggest("я")) # []
Сборка: каждый узел сортирует не больше кандидатов. Суммарно это примерно для узлов. Для 300 млн узлов это минуты или десятки минут на одной машине, а сборка идёт офлайн, поэтому так можно.
Рекурсия в _fill глубиной в длину самого длинного запроса. Если не ограничить длину запросов при сборке, на мусорной строке в тысячи символов Python упадёт по лимиту рекурсии. В настоящем сборщике длину стоит обрезать, например до 100 символов.
Как уложиться в память
Код выше хранит в узлах строки и словари, на 300 млн узлов так не хватит никакой памяти. В проде делают иначе:
- Идентификаторы вместо строк. Запросы лежат в одном массиве, в узлах хранятся 4-байтовые номера. Это и дало 60 байт на узел в оценке.
- Сжатое дерево (radix tree). Цепочки узлов с одним ребёнком склеиваются в одно ребро со строкой. В хвостах длинных запросов таких цепочек большинство.
- Топ-k только до глубины . Для префиксов длиннее, скажем, 20 символов поддерево крошечное, его можно обойти на лету. Узлы глубже без списка экономят много памяти.
- Плоский формат. Дерево сериализуется в непрерывный массив и загружается через
mmap. Загрузка снапшота становится быстрой, а сборщик мусора не тратит время на миллионы объектов.
Есть и альтернатива, о которой полезно упомянуть: вообще без дерева хранить таблицу «префикс → топ-k» в key-value хранилище. Ключей получится столько же, сколько узлов, но чтение — один поиск по ключу, а хранилище само умеет шардироваться. Дерево компактнее за счёт общих префиксов. Таблица проще в эксплуатации. Оба ответа нормальны, если вы назвали компромисс.
Почему не обновлять дерево на лету
Кажется естественным увеличивать частоту в trie на каждый поиск. Посмотрим, что это стоит. Когда частота запроса выросла, топ-k нужно поправить во всех узлах на пути от корня:
def bump(self, query, new_freq): """Частота запроса выросла: правим top-k на всём пути от корня.""" node = self.root path = [node] for ch in query: node = node.children.setdefault(ch, Node()) path.append(node) for node in path: others = [p for p in node.top if p[1] != query] node.top = rank(others + [(new_freq, query)], self.k) trie.bump("покемон", 800) # вышла новая игра print(trie.suggest("по")) # ['погода', 'покемон', 'погода москва']
Проблем три:
- Работает только рост. Если частота упала, запрос может выпасть из топа, и на его место должен прийти кто-то из глубины поддерева. Узнать кто, не обходя поддерево, нельзя.
- Корень и короткие префиксы — горячие точки записи. Каждый поиск трогает узел «п». Тысячи записей в секунду в один узел на десятках реплик означают блокировки и расхождение реплик.
- Чтение и запись мешают друг другу. Сервис, который отвечает за миллисекунды, начинает держать блокировки.
Поэтому основной индекс неизменяемый: сборщик строит новую версию целиком, сервисы загружают её рядом со старой и атомарно переключают ссылку. Старая версия освобождается, когда завершатся запросы, которые её читают. Откат на прошлую версию — переключение ссылки обратно.
Шаг 5. Сбор частот
Конвейер от поиска до нового снапшота:
- Сервис поиска пишет событие «пользователь отправил запрос» в очередь, например Kafka. Про выбор очереди — в статье про очереди сообщений.
- Потоковый или пакетный агрегатор считает количество по каждому нормализованному запросу за день. Это классическая задача top k frequent, только распределённая: map по запросу, reduce суммой.
- Раз в несколько часов сборщик берёт дневные агрегаты за последние недели, считает итоговый вес, фильтрует и строит trie.
Важная деталь: считаем отправленные запросы, а не набранные префиксы. Иначе подсказки начнут подкармливать сами себя: что показали, то и выбрали, и это попало в статистику.
Вес с затуханием
Если просто суммировать за всё время, «погода москва» прошлогоднего урагана навсегда останется наверху. Поэтому вклад каждого дня затухает экспоненциально: вклад дня давностью дней умножается на , где — период полураспада.
from collections import defaultdict HALF_LIFE_DAYS = 7 # через неделю вклад дня уменьшается вдвое MIN_SCORE = 5.0 # отсекаем хвост из опечаток и разовых запросов BLOCKLIST = {"плохое слово"} def normalize(query): return " ".join(query.lower().replace("ё", "е").split()) def scores(daily_counts, today): """daily_counts: [(день, запрос, сколько раз)] — результат дневного агрегата.""" total = defaultdict(float) for day, query, count in daily_counts: age = today - day total[normalize(query)] += count * 0.5 ** (age / HALF_LIFE_DAYS) return { q: round(s, 1) for q, s in total.items() if s >= MIN_SCORE and q not in BLOCKLIST } log = [ (0, "Погода Москва", 100), # месяц назад был всплеск (28, "погода москва", 10), (28, "чемпионат мира", 40), # свежая тема (27, "чемпионат мира", 30), (28, "погода масква", 2), # опечатка, отсечётся (28, "Плохое слово", 50), ] print(scores(log, today=28)) # {'погода москва': 16.2, 'чемпионат мира': 67.2}
Месячный всплеск в 100 запросов весит теперь 6,25, а свежая тема с 70 запросами за два дня обогнала его. Порог MIN_SCORE решает сразу две задачи: убирает опечатки и не даёт по подсказкам восстановить чей-то редкий личный запрос вроде номера телефона или имени.
Фильтрация на этапе сборки, а не на чтении: чёрный список, нецензурные слова, запросы, которые юристы попросили не показывать. Отдельный ручной список на удаление тоже нужен. Если в подсказках всплыло что-то плохое, ждать следующей сборки нельзя: такой список проверяется на чтении и применяется сразу.
Тренды
Сутки на свежесть — нормально для «погода москва», но не для новости, которая вышла час назад. Ответ интервьюеру: второй, маленький индекс.
- Потоковый агрегатор считает частоты в скользящем окне за последний час.
- Запросы, у которых частота в окне резко выше обычной, попадают в «трендовый» индекс на тысячи записей. Его можно пересобирать каждые несколько минут.
- Сервис подсказок смешивает два списка: основной и трендовый, с весами.
Так свежесть получает только малая часть данных, которой она действительно нужна.
Шаг 6. Кэширование
Самый дешёвый запрос — тот, который не дошёл до сервера. Подробно уровни кэша разобраны в статье про стратегии кэширования, здесь — как они применяются к подсказкам.
| Уровень | Что кэшируем | TTL | Что даёт |
|---|---|---|---|
| Браузер | ответы на уже набранные префиксы | минуты–час | стёр букву — ответ мгновенный, без сети |
| CDN | ответ по ключу prefix + lang | около часа | короткие префиксы не доходят до наших серверов |
| Сервис подсказок | сам индекс в памяти | до новой сборки | промах CDN — всё равно микросекунды на поиск |
Почему CDN здесь особенно хорош: распределение префиксов очень неравномерное. Однобуквенных и двухбуквенных префиксов в каждом языке всего сотни или тысячи, а они собирают огромную долю трафика. Они почти всегда в кэше CDN. До сервиса доходят длинные, редкие префиксы. Про устройство CDN есть отдельная статья.
Ещё один приём — отдавать данные наперёд. Вместе с ответом на «п» можно прислать топ для всех префиксов «па», «пе», «по»... и клиенту не придётся ходить на сервер за второй буквой. Это пара килобайт ответа ради минус одного сетевого запроса.
TTL кэша согласуется с частотой пересборки. Если индекс пересобирается раз в 6 часов, TTL в час означает, что новая версия видна всем максимум через час после выкладки. Для трендов этого мало, поэтому трендовый список либо не кэшируется на CDN, либо кэшируется на минуту.
Шаг 7. Шардирование и репликация
Индекс в 20 ГБ помещается в одну машину, поэтому первый ответ — только реплики. Каждый сервер держит полную копию, балансировщик раскидывает запросы. Это проще всего: любой сервер отвечает на любой префикс. Про балансировку — в этой статье.
Шардирование понадобится, когда индекс перестанет помещаться в память: больше языков, больше хвоста, персонализированные данные. Общие подходы описаны в статье про шардирование и репликацию. Для подсказок есть два варианта.
По хешу префикса. Каждый узел-префикс лежит на шарде hash(prefix) % N, лучше через консистентное хеширование. Нагрузка ровная, но это естественно ложится только на схему «таблица префикс → топ-k». Дерево так не режется.
По диапазонам префиксов. Шард 0 хранит всё, что начинается с «а»–«о», шард 1 — с «п» и так далее. Дерево режется на поддеревья. Но буквы неравноценны: на «п» начинается гораздо больше запросов, чем на «ъ». Поэтому границы режут по трафику, а не по алфавиту:
from bisect import bisect_right def split_by_traffic(prefix_qps, shards): """prefix_qps: {префикс из двух символов: QPS}. Режем отсортированные префиксы на диапазоны с примерно равной нагрузкой. Возвращает левую границу каждого шарда.""" items = sorted(prefix_qps.items()) target = sum(prefix_qps.values()) / shards bounds, cum = [], 0.0 for prefix, qps in items: # новый шард начинается, когда набрали очередную «порцию» нагрузки if not bounds or (cum >= target * len(bounds) and len(bounds) < shards): bounds.append(prefix) cum += qps return bounds def shard_for(query, bounds): return bisect_right(bounds, query[:2]) - 1 traffic = {"ав": 10, "ба": 15, "по": 60, "пр": 40, "са": 20, "та": 15, "я ": 40} bounds = split_by_traffic(traffic, shards=4) print(bounds) # ['ав', 'пр', 'са', 'я '] print(shard_for("погода", bounds)) # 0 print(shard_for("сбер", bounds)) # 2 print(shard_for("я хочу", bounds)) # 3
На этом примере видны обе проблемы диапазонов:
- Горячий префикс. Один «по» даёт 60 QPS при целевых 50 на шард, и шард 0 перегружен, как ни режь. Решение — резать по трём символам внутри горячего диапазона или дать горячему шарду больше реплик.
- Короткие префиксы. Префикс «п» живёт на двух шардах сразу: «по» на нулевом, «пр» на первом. Опрашивать оба и сливать списки можно, но проще отдельная маленькая таблица для префиксов короче ключа шардирования. Их всего несколько тысяч, они лежат на каждом сервере и почти всегда отдаются из CDN.
Таблица границ хранится в конфигурации, её читает маршрутизирующий слой перед сервисами. Пересчитывается вместе со сборкой индекса: сборщик и так знает трафик по префиксам.
Шаг 8. Бюджет задержки
100 мс от нажатия до отрисовки складываются так. Цифры — порядок, а не замер:
| Этап | Время | Как экономим |
|---|---|---|
| Задержка перед отправкой на клиенте | 50–100 мс | короче на быстрых сетях, длиннее на медленных |
| Сеть до ближайшей точки CDN | 10–50 мс | CDN близко к пользователю |
| CDN → дата-центр при промахе | 10–80 мс | несколько регионов с копией индекса |
| Сервис: разбор запроса и спуск по trie | меньше 1 мс | индекс в памяти, |
| Отрисовка | единицы мс | без тяжёлых фреймворков в выпадающем списке |
Сразу видно: сервер — самая дешёвая часть. Оптимизировать спуск по дереву бессмысленно, пока каждый запрос идёт через океан. Поэтому главные рычаги — кэш, близость к пользователю и клиент.
Клиент делает три вещи: ждёт паузу в наборе, а не шлёт запрос на каждую букву; отменяет запрос, ответ на который уже не нужен; помнит ответы на префиксы, которые уже видел.
function createSuggester( fetchSuggestions, { delay = 100, cacheSize = 200 } = {} ) { const cache = new Map() // префикс -> подсказки, порядок вставки = LRU let timer = null let controller = null return function onInput(prefix, render) { clearTimeout(timer) controller?.abort() // ответ на старый префикс больше не нужен if (cache.has(prefix)) { const hit = cache.get(prefix) cache.delete(prefix) cache.set(prefix, hit) // освежаем позицию в LRU render(hit) return } timer = setTimeout(async () => { controller = new AbortController() try { const items = await fetchSuggestions(prefix, controller.signal) cache.set(prefix, items) if (cache.size > cacheSize) cache.delete(cache.keys().next().value) render(items) } catch (e) { if (e.name !== 'AbortError') throw e } }, delay) } }
Отмена закрывает частый баг: пользователь набрал «пого», запрос ушёл, пользователь стёр букву. Если не отменить, медленный ответ на «пого» придёт позже ответа на «пог» и перезапишет список, который уже не соответствует строке. Map в JavaScript помнит порядок вставки, поэтому из него получается простой LRU-кэш. Подробнее про LRU — в отдельном разборе.
Задержка перед отправкой — компромисс. Большая экономит запросы, но подсказка появляется позже. Маленькая даёт отзывчивость, но умножает нагрузку. 100 мс — разумная отправная точка, дальше настраивают по метрикам.
Вопросы вглубь
После основного дизайна интервьюер обычно добавляет одно-два условия. Короткие ответы:
- Персонализация. Глобальный топ берём как есть, а сверху клиент или отдельный сервис подмешивает недавние запросы пользователя. Глобальный ответ остаётся кэшируемым, личная часть маленькая.
- Опечатки. «пгода» → «погода». Ищем в trie префиксы на редакционном расстоянии 1 от введённого, это обход с ограничением, как в статье про расстояние Левенштейна. Дорого, поэтому включается, только если точный префикс ничего не нашёл.
- Совпадение по середине. «москва» должна находить «погода москва». Индексируем каждое слово запроса отдельно, это уже ближе к обратному индексу полнотекстового поиска.
- Несколько регионов. Индекс неизменяемый, поэтому копировать его в регионы просто: каждый регион скачивает снапшот из хранилища объектов.
- Сборка сломалась и выдала мусор. Перед переключением новая версия проверяется: размер в пределах нормы, топ по контрольным префиксам не изменился радикально. Иначе остаёмся на старой и поднимаем тревогу.
Как вести себя на таких продолжениях, разобрано в статье про вопросы вглубь.
Типичные ошибки
- Только trie. Структура данных без конвейера частот и без кэша — треть ответа.
- Обход поддерева на каждый запрос. Для коротких префиксов это миллионы узлов. Топ-k надо считать заранее.
- Запись частот прямо в обслуживающее дерево. Горячие узлы, блокировки и невозможность корректно обработать падение частоты.
- База данных на пути чтения. Индекс помещается в память, и миллисекунды надо тратить на сеть, а не на диск.
- Подсчёт набранных префиксов вместо отправленных запросов. Подсказки начинают подкармливать сами себя.
- Нет затухания. Прошлогодние всплески навсегда остаются наверху.
- Шардирование по первой букве. Нагрузка по буквам неравномерна в десятки раз.
- Забытый клиент. Без задержки перед отправкой, отмены и локального кэша сервер получает запрос на каждую букву, а пользователь видит мигающие устаревшие подсказки.
Что запомнить
- Подсказки — система с тяжёлым чтением и пакетной записью. Строгая согласованность не нужна, и это разрешает кэши и неизменяемые снапшоты.
- Топ-k в каждом узле превращает запрос в спуск на длину префикса. Цена — память и офлайн-сборка.
- Частоты берутся из логов отправленных запросов, с затуханием, порогом и фильтрами. Тренды — отдельным маленьким индексом.
- Основная экономия — браузер и CDN, а не быстрый сервер.
- Шардируют по трафику, а не по алфавиту, и отдельно думают о горячих и коротких префиксах.