Спроектируй автодополнение поиска
Спроектируй typeahead с бюджетом меньше 100мс: trie префиксов, предвычисленный top-k на узел, офлайн-пайплайн агрегации, ранжирующий запросы по частоте, edge-кеширование и почему подсказки отдаются из предвычисленных структур, никогда не запрашиваются вживую на нажатие.
Команда построила автодополнение поиска очевидным способом: на каждое нажатие клавиши пускала запрос, сканировавший лог поиска ради топа совпадающих прошлых запросов, и возвращала их. В демо на малом датасете было шустро. В продакшене это была катастрофа — каждый символ, набранный пользователем, запускал свежую агрегацию по миллиардам строк лога, так что «restaurant» — это десять отдельных тяжёлых запросов, поисковый кластер прогнулся под штормом нажатий, а подсказки прилетали с опозданием 600 мс, сильно после того, как пользователь дописал и нажал ввод. Фича, что должна была ощущаться телепатичной, ощущалась сломанной. Урок, что они упустили: у автодополнения зверский бюджет задержки (подсказки должны обогнать следующее нажатие, меньше чем за ~100 мс) и огромный объём чтений, так что нельзя вычислять подсказки вживую — их отдают из структуры, предвычисленной офлайн. Этот урок проектирует эту структуру и пайплайн, что её питает.
Требования
Требования здесь почти целиком диктует одно жёсткое число: бюджет задержки. Как только понимаешь, почему 100 мс — потолок, все остальные решения вытекают сами собой.
Функциональные: по мере набора пользователем префикса вернуть топ несколько (скажем, 5–10) наиболее релевантных полных запросов, начинающихся с этого префикса, ранжированных по популярности (и, возможно, персонализации/свежести). Обновлять подсказки, отражая тренды во времени. Слабо тянуть опечатки (часто это stretch-цель) и фильтровать небезопасные/забаненные подсказки.
Нефункциональные: бюджет задержки — заглавное ограничение — подсказка должна появиться быстрее, чем пользователь наберёт следующий символ, так что end-to-end бюджет примерно 100 мс, а раз он включает сетевой round trip, у сервера лишь десятки миллисекунд. Объём чтений огромен: каждое нажатие каждого поиска — запрос, так что запросы сильно превосходят реальные поиски (набрать «weather» — 7 запросов на 1 поиск). Свежесть eventually consistent — подсказки, отражающие вчерашние тренды или отстающие от нового вирусного термина на минуты, приемлемы; ничего не неверно, если совсем новый запрос ещё не предлагается.
Определяющее напряжение — бюджет задержки против размера данных: ты ранжируешь топ дополнений из миллиардов исторических запросов, меньше чем за 100 мс, на каждое нажатие. Это возможно лишь если ранжирование уже сделано — предвычислено — до прихода запроса.
Оценка
Возьми 5 миллиардов поисков/день. Каждый поиск — ~6 набранных символов, и каждый символ (после крошечного дебаунса) — запрос, так что объём запросов в несколько раз больше объёма поисков: порядка 10^10+ запросов автодополнения/день, грубо сотни тысяч запросов/секунду, с пиком выше. Один этот объём чтений говорит: предвычисляй и кешируй агрессивно; ничто на запрос не должно касаться сырых логов.
Данные: словарь различных запросов велик, но trie префиксов, достойных подсказки, ограничен — ты хранишь лишь популярные запросы (длинный хвост одноразовых никогда не предлагается), так что trie держит миллионы узлов, не миллиарды. С top-k дополнений, закешированными на каждом узле, вся структура отдачи помещается в памяти (единицы-до-десятков ГБ), что и делает возможной отдачу за десятки миллисекунд. Вердикт салфетки: отдача = in-memory предвычисленный top-k; ранжирование = отдельная офлайн batch-задача по логам.
Высокоуровневый дизайн
Два развязанных пути: офлайн-пайплайн, строящий ранжированный trie, и онлайн-путь, отдающий из него.
- Офлайн-пайплайн: ингест логов поиска, агрегация частот запросов за окно, ранжирование и сборка trie, где каждый узел-префикс несёт свой top-k дополнений. Публикация нового trie как неизменяемого снапшота.
- Отдаваемый trie: опубликованный снапшот, в памяти и реплицированный по узлам отдачи ради пропускной способности чтений.
- Typeahead-сервис: на запрос идёт по trie к узлу-префиксу и возвращает его закешированный top-k. Без ранжирования, без доступа к логам — просто лукап.
- Edge-кеш/CDN: популярные префиксы («a», «th», «wea») кешируются на краю, так что самые частые запросы отдаются вовсе не касаясь сервиса.
Глубокое погружение
Trie и top-k на префикс
Trie (префиксное дерево) хранит строки по их символам вдоль пути от корня: префикс «te» — узел, достигнутый следованием по ребру t, затем e, и все дополнения, начинающиеся с «te», живут в поддереве под ним. Наивное использование trie — «иди к узлу-префиксу, затем обойди всё поддерево ради лучших дополнений» — но это поддерево может быть огромным, и обход его на нажатие взрывает бюджет задержки. Сеньорный ход — предвычислить и хранить top-k дополнений на каждом узле: узел «te» прямо держит ["tesla", "tennis", "temperature", ...] уже ранжированными. Теперь отдача — это O(длина префикса) на спуск плюс O(1) на чтение закешированного списка — никакого обхода поддерева вовсе.
Это предвычисление — весь фокус. Оно меняет работу на сборке и немного памяти (k строк на узел) на отдачу за константное время, что ровно верный обмен, когда чтения превосходят записи на порядки, а бюджет задержки крошечный. k дополнений на узел обычно хранятся как малый ранжированный список (или Redis sorted set на префикс), так что лукап — одно быстрое чтение.
▸Почему это работает
Почему хранить top-k на каждом узле, а не просто обходить поддерево по запросу или хранить полный ранжированный список раз в корне? Из-за асимметрии между чтениями и бюджетом. Поддерево под коротким префиксом вроде «a» может содержать миллионы запросов; обойти и ранжировать их меньше чем за десятки миллисекунд, сотни тысяч раз в секунду, невозможно. Хранение top-k на узле делает чтение O(1) независимо от того, как огромно поддерево — дорогое ранжирование уже произошло офлайн. Стоимость памяти ограничена: k мало (5–10), и ты держишь лишь узлы для префиксов популярных запросов, так что это k строк на миллионы узлов, не миллиарды. Это тот же паттерн предвычисли-на-записи-чтобы-сделать-чтения-дешёвыми, что у fan-out-on-write ленты — заплати раз на сборке, отдавай дёшево на потоке чтений. Trie лишь делает сам лукап «какой предвычисленный ответ» за O(длина префикса).
Пайплайн сбора и агрегации данных
Подсказки хороши настолько, насколько хорошо ранжирование, а ранжирование идёт от офлайн-пайплайна агрегации, полностью отдельного от отдачи. Он читает сырые логи поиска, считает, как часто каждый запрос выдавался за скользящее окно (например, последний день/неделя, часто с затуханием во времени, чтобы свежие поиски весили больше), отфильтровывает редкие/одноразовые запросы и забаненные термины и выдаёт ранжированный список запрос, скор. Сборщик trie затем вставляет эти запросы и для каждого узла записывает top-k его поддерева.
Критично, это работает по расписанию (непрерывно или каждые несколько минут/часов), не на пути запроса. Выход публикуется как новый неизменяемый снапшот, который узлы отдачи загружают атомарно — ты никогда не мутируешь живой trie на месте под трафиком чтений (это рискует неконсистентностью и блокировками). Поскольку сборка по миллиардам строк тяжела, это batch/потоковая задача (агрегация в стиле MapReduce или потоковый процессор с оконными счётчиками), и её каденс задаёт свежесть: более тугой каденс выводит тренды быстрее ценой большего компьюта. Потому автодополнение может быть eventually consistent — снапшот по дизайну отстаёт на минуты, и это нормально.
▸Частая ошибка
Определяющая ошибка — это ошибка hook: вычислять подсказки вживую на нажатие, запрашивая логи или базу на каждый запрос. Кажется естественным («просто найди совпадающие запросы»), но проваливается по двум осям сразу. Первая — задержка: агрегация или скан ради ранжирования, на запрос, не помещается в серверный бюджет десятков миллисекунд по большому датасету. Вторая — нагрузка: каждое нажатие — запрос, так что один пользователь, набирающий слово, пускает полдюжины тяжёлых запросов, а на масштабе это шторм нажатий, плавящий поисковый кластер. Починка — архитектурная разбивка: ранжирование офлайн и периодическое, отдача — O(1) чтение предвычисленной структуры. Связанная, тоньше, ошибка — мутировать отдаваемый trie на месте по мере прихода новых данных — вместо этого строй свежий неизменяемый снапшот офлайн и подменяй атомарно, так что чтения никогда не конкурируют с записями и недостроенный индекс никогда не отдаётся. Если ты ловишь себя на касании логов на пути чтения, ты уже проиграл бюджет задержки.
Бюджет задержки и edge-кеширование
End-to-end бюджет ~100 мс — спека, и он тратится осознанно. Клиент дебаунсит нажатия (ждёт несколько десятков мс паузы в наборе), чтобы не пускать запрос на символ на машинной скорости, и может префетчить/кешировать локально. Сеть съедает большой кусок round trip, оставляя серверу лишь десятки мс — что предвычисленный лукап trie легко выдерживает. Чтобы ещё урезать сетевую и серверную стоимость, популярные префиксы отдаются из edge-кеша/CDN: подсказки для «a», «th», «new» идентичны для большинства пользователей и меняются медленно, так что их кеширование на краю (с коротким TTL под каденс снапшота) отдаёт самые объёмные запросы близко к пользователю без round trip к origin и щитит сервис от основной массы трафика чтений. Персонализированные подсказки (подмешивающие свою историю пользователя) — исключение, обходящее общий edge-кеш, наслоённое поверх популярной базы — и держимое дёшево, ведь история на пользователя мала.
Логика бюджета — сквозная нить: каждый выбор дизайна (предвычисли, кешируй top-k на узлах, неизменяемые снапшоты, edge-кеширование, дебаунс) существует, чтобы держать путь чтения далеко под 100 мс, гася поток запросов, обеспечивая, что ни один запрос не делает реальной работы ранжирования.
Твоё автодополнение запрашивает логи поиска на каждое нажатие ради ранжирования совпадающих запросов. Оно тормозит на 600 мс, и поисковый кластер перегружен. В чём архитектурная починка?
В твоём trie каждый лукап идёт к узлу-префиксу и затем обходит всё поддерево, ранжируя дополнения на лету. Короткие префиксы вроде 'a' таймаутят. В чём починка?
Чтобы отдать подсказки в бюджет ~100 мс, top-k дополнений хранится на каждом узле trie заранее офлайн-пайплайном, так что запрос — лишь проход к префиксу плюс чтение за константное время — ранжирование _______, никогда не вычисляется вживую на пути чтения на нажатие.
Узкие места и компромиссы
Связывающее ограничение — бюджет задержки под огромным объёмом чтений, и каждый выбор служит ему. Ключевые компромиссы:
- Предвычисление vs вычисление вживую. Предвычисление top-k на узел меняет компьют сборки и память на O(1) чтения — обязательно при этом отношении чтение:запись и бюджете. Вычисление вживую (hook) проще строить, но не может уместить бюджет или нагрузку.
- Свежесть vs стоимость. Более тугой каденс снапшота выводит тренды быстрее, но стоит больше компьюта; автодополнение терпит минуты устарелости (eventual consistency), так что ты выбираешь каденс, не реальное время.
- Память vs качество ответа. Хранение top-k на каждом узле и trie в памяти стоит RAM; ты ограничиваешь это, индексируя лишь популярные запросы (отбрасывая никогда-не-предлагаемый длинный хвост) и держа k малым.
- Общий edge-кеш vs персонализация. Подсказки популярных префиксов идентичны по пользователям и прекрасно кешируются на краю; персонализация обходит этот общий кеш, так что ты наслаиваешь малый персонализированный набор поверх закешированной популярной базы, а не персонализируешь всё.
- Неизменяемый снапшот vs обновление на месте. Публикация неизменяемого снапшота избегает конкуренции чтение/запись и никогда не отдаёт недостроенный индекс, ценой полных пересборок; потому живой trie подменяется, не мутируется.
Глубочайший принцип тот же, что у ленты: сделай дорогую работу раз, офлайн, на стороне записи/сборки, чтобы путь чтения был тривиальным лукапом. Автодополнение — read-оптимизированная система, чья вся архитектура устроена вокруг того, чтобы никогда не делать работу ранжирования, пока пользователь ждёт.
- 01Почему автодополнение никогда не может вычислять подсказки вживую на нажатие и что за архитектурная разбивка?
- 02Как trie с предвычисленным top-k на узел отдаёт подсказки за константное время?
- 03Что делает офлайн-пайплайн агрегации и почему публиковать неизменяемый снапшот?
- 04Как тратится бюджет ~100 мс и что добавляет edge-кеширование?
Автодополнение поиска — read-оптимизированная система, определяемая зверским бюджетом задержки (~100 мс end-to-end, десятки мс серверу) под огромным объёмом чтений (каждое нажатие — запрос). Это делает подход hook — вычисление подсказок вживую на нажатие сканом логов — гибельным и по задержке, и по нагрузке. Архитектура разбивает две заботы: офлайн-пайплайн агрегации читает логи поиска, считает и ранжирует запросы за скользящее (часто с затуханием) окно, фильтрует редкие и забаненные термины, а сборщик trie хранит top-k дополнений, предвычисленный на каждом узле-префиксе, публикуемый как неизменяемый снапшот, который узлы отдачи подменяют атомарно. Отдача тогда тривиальна: иди по trie к набранному префиксу (O(длина префикса)) и верни его закешированный top-k (O(1)) — без обхода поддерева, без доступа к логам. Edge-кеш/CDN фронтит самые объёмные популярные префиксы, так что большинство запросов не доходит до сервиса, а клиент дебаунсит нажатия; персонализация наслаивает малый набор на пользователя поверх закешированной популярной базы. Свежесть eventually consistent по дизайну — снапшот отстаёт на минуты, и это нормально. Объединяющий принцип, общий с лентой, — сделай дорогое ранжирование раз, офлайн, на стороне сборки, чтобы путь чтения был лукапом за константное время — никогда не заставляй пользователя ждать, пока ранжируешь миллиарды строк. Теперь, когда увидишь автодополнение, тормозящее под нагрузкой или выбивающее бюджет задержки, ты знаешь, что проверить первым: происходит ли ранжирование на пути запроса, или система отдаёт предвычисленный top-k из trie?
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.