Search System Design

В сентябре 2008 года инженеры Bing запустили внутренний эксперимент: добавить искусственную задержку 200 мс к каждому запросу. Результат через две недели - падение запросов на 0.4%, падение revenue на 2.5%. Через 6 месяцев пользователи реже возвращались к Bing в принципе - привычка ушла. Google провёл аналогичный эксперимент: каждые 100 мс задержки = -0.6% запросов на пользователя. Эти цифры (известные как 'Greg Linden's 100ms rule', изначально из Amazon 2006) определяют всю архитектуру современного поиска: размер шарда, число реплик, tail-latency бюджет, hedged requests. Search system design - это не про 'правильный алгоритм ранжирования', это про дисциплинированное достижение sub-200 ms p99 при миллиардных индексах.

• **Google** - 100K QPS на peak, 200 мс p99 SLA, fanout на сотни leaf-шардов с hedged requests; Caffeine indexer обновляет важный контент в индексе за <60 секунд после публикации.
• **Amazon A9** - lexical search плюс learned-to-rank с 100+ сигналами; sponsored продукты дают 10-15% revenue, но требуют тщательного балансирования с органической релевантностью.
• **Yandex Поиск** - русскоязычная морфология добавляет к стандартной архитектуре отдельный лемматизатор перед инвертированным индексом; персонализация по геолокации (Москва vs регионы) важнее, чем у Google в США.

Design: веб-поиск (масштаб Google)

На вопрос интервьюера 'разработай Google' большинство кандидатов начинает с инвертированного индекса - и это правильно. Но детали определяют, пройдён ли уровень. Реальный Google индексирует ~400 млрд страниц, обслуживает 100 000 запросов/сек, отвечает за 200 мс. Чтобы такая система держала SLA, она строится из трёх параллельных пайплайнов: crawl (получение страниц, политики вежливости, обновление), index (парсинг, токенизация, шардирование по doc-id), serve (query parsing, federation, ranking, snippet generation). Главные числа, которые надо назвать на интервью: каждый запрос обходит сотни шардов параллельно (root -> leaf), каждый шард держит долю инвертированного индекса в RAM, fanout = N шардов, latency = max задержки шарда + объединение.

Tail latency: при fanout 1000 шардов даже p99=100 мс отдельного шарда даёт p99 ответа ~700 мс (вероятность 'все ниже 100 мс' = 0.99^1000). Решения: hedged requests (тот же запрос в реплику через 50 мс), резервирование вычислительных ресурсов, отсечение шардов, отвечающих медленнее median + 2*MAD.

Design: поиск e-commerce (Amazon, Wildberries)

Поиск в e-commerce отличается от веб-поиска тем, что объект ранжирования - товар, а не страница. Релевантность смешивается с бизнес-логикой: доступность на складе, цена, маржинальность, sponsored placements. Запрос 'iphone 15 pro' не должен возвращать чехлы для iPhone 14 (lexical match по 'iphone'), а должен фильтровать по структурированным полям: brand=Apple, model=iPhone 15 Pro, category=Smartphone. Amazon A9 - комбинация lexical search (BM25 по title/description) + structured filters + learned-to-rank поверх 100+ сигналов: CTR, conversion rate, return rate, price competitiveness. Wildberries и Ozon добавляют свои особенности: персонализация по геолокации (доставка завтра vs через 5 дней), recommendation widgets в выдаче.

Facets и aggregations: в e-commerce выдача требует side-panel 'фильтры' с количеством товаров в каждой категории, цвете, бренде. Это требует aggregation поверх результатов поиска - дополнительная стоимость на каждом запросе. Решение: pre-computed facet counts в индексе, обновляемые batch-ом.

Typeahead и query suggestion

Каждое нажатие клавиши в поисковой строке Google вызывает API запрос, который должен ответить за <50 мс. На масштабе это 10x QPS основного поиска. Архитектура typeahead принципиально другая: нет инвертированного индекса по документам, есть Trie или FST (Finite State Transducer) по самым популярным запросам, с весами по частоте и времени суток. На вход - префикс, на выход - top-10 продолжений. Ключевая структура - prefix-tree с массивом популярных продолжений в каждом узле. Memcached layer перед trie для самых горячих префиксов. Дополнительные сигналы: персональная история (autocomplete недавних запросов), trending (boost для всплесков сегодня), безопасность (фильтр запрещённых паттернов).

FST (Finite State Transducer) - компактнее Trie за счёт суффиксного шаринга. Lucene Solr использует FST для completion: 100 миллионов запросов помещаются в ~2 GB, fits в RAM целиком на одной машине. Скорость лукапа - O(длина префикса), независимо от размера словаря.

Персонализация без катастрофы

Персонализация в поиске - меч с двумя лезвиями. Слишком слабая - все видят одно и то же, теряется ценность сигнала о пользователе. Слишком сильная - filter bubble: пользователю никогда не показывают то, что выходит за его пузырь интересов. Google нашёл баланс: персонализация ограничена ~15-20% позиций в выдаче, остальные определяются глобальной релевантностью. Сигналы персонализации - история поиска (7-30 дней), геолокация, язык интерфейса. Архитектура: глобальный ранкер выдаёт top-100, затем re-ranker с user features меняет порядок только в первых 30. E-commerce агрессивнее: до 50% выдачи зависит от пользователя (Amazon показывает 'обычно покупаемое тобой' выше категорийного результата). Опасность: cold start (новый пользователь не имеет истории), shadow profile (поиск с другого устройства), drift (пользовательские интересы меняются).

Two-tower model: классическая архитектура персонализированного ранжирования - две независимые сетки, одна кодирует пользователя в эмбеддинг, другая - документ. Совпадение через dot-product. Пользовательская башня обновляется чаще (раз в минуты) на короткой истории, документная - редко (раз в часы). Эмбеддинг пользователя кешируется на edge для sub-10 мс латентности.

Ключевые идеи

• **Web search at scale** - три параллельных пайплайна (crawl/index/serve); главная боль на serve - tail latency при fanout на сотни шардов.
• **E-commerce search** - объект ранжирования товар, не страница; релевантность смешивается с availability, ценой, sponsored placements; hard filter для in-stock.
• **Typeahead** - отдельная архитектура: Trie/FST по популярным запросам в RAM, не инвертированный индекс по документам; sub-50 мс SLA.
• **Персонализация** - меч с двумя лезвиями: слабая бесполезна, сильная создаёт filter bubble; разумный баланс - 15-30% позиций в выдаче.

Связанные темы

Search system design объединяет все ранее пройденные темы IR в единую инфраструктуру:

• Search Infrastructure at Scale — Tiering, кэширование и федерация - кирпичи, из которых строится верхнеуровневый design Google и Amazon; здесь они складываются в продуктовую систему
• Learning to Rank — LTR-модели - финальный этап серве-пайплайна; их роль в архитектуре - re-rank top-K после lexical retrieval, а не первичный поиск

Вопросы для размышления

• Возврат к мотивации: 100 мс задержки = -0.6% запросов. Какие архитектурные компромиссы оправданы для удержания p99 < 200 мс, и какие точно нет?
• Cold start для нового пользователя в персонализированном поиске - как сбалансировать explore (предложить новое) и exploit (показать что-то релевантное на основе скудных сигналов)?
• Если бы интервьюер попросил спроектировать поиск для платформы видео (TikTok, YouTube), какие компоненты из лекции остаются, а какие требуют принципиально иного решения?

Связанные уроки

• ir-12 — System design строится поверх масштабируемой инфраструктуры
• ir-04 — Learning to Rank - core ranking компонент в design
• ir-07 — Vector DB встраивается в semantic search архитектуру
• ir-08 — Query understanding - первый слой search pipeline
• ds-02-cap-theorem — Трилемма precision/recall/latency аналогична CAP
• net-37-load-balancing — Search load balancing - частный случай общего LB
• dist-12-consistency