Поисковая система ломается не в момент записи документа, а там, где встречаются индексация, ранжирование, свежесть данных и пользовательский путь запроса.
Глава помогает разложить конвейер приёма документов, инвертированный индекс, маршрутизацию по шардам, каскад ранжирования, автодополнение и окно согласованности между записью и поисковой выдачей.
В интервью и инженерных обсуждениях этот кейс полезен тем, что заставляет одновременно держать в голове релевантность, задержки и эксплуатационную стоимость, а не только хранение.
Pipeline Thinking
Критичны ingestion, partitioning, deduplication и задержки между стадиями обработки.
Слой сервинга
Решения по индексам, cache locality и query path определяют пользовательскую задержку.
Consistency Window
Явно фиксируйте, где допустима eventual consistency и где требуется stronger guarantees.
Cost vs Freshness
Балансируйте скорость обновления данных и стоимость вычислений/хранения.
Почему поиск сложен
Проектирование поисковой системы — одна из самых насыщенных задач на интервью по системному дизайну. Здесь в одной архитектуре встречаются , построение индекса, обработка запроса, ранжирование результатов и постоянная борьба за свежесть данных при огромном масштабе.
Ключевые подсистемы
Собирает страницы и планирует повторный обход
Преобразует документы в инвертированный индекс
Отбирает и упорядочивает лучшие результаты
Функциональные требования
Базовые возможности
- Полнотекстовый поиск по миллиардам документов
- Автодополнение и подсказки запросов
- Фасетный поиск и фильтрация
- Релевантное ранжирование результатов
- Исправление опечаток и обработка синонимов
Дополнительные возможности
- Поиск по изображениям и видео
- Персонализация результатов
- Локализация и языковые модели
- Почти мгновенная индексация новых страниц
Нефункциональные требования
Пользователь воспринимает поиск как быстрый, если система удерживает ответ в рамках и выдерживает сотни тысяч без заметной деградации релевантности.
Обход и обновление веб-страниц
Связь
Alex Xu: Web Crawler
Детальный разбор архитектуры краулера в книге System Design Interview
Краулер решает сразу несколько задач: что обходить в первую очередь, как часто возвращаться к документу и как не перегружать чужие сайты. Для масштаба Google это означает обработку миллиардов URL каждый день.
Архитектура краулера
Выберите этап, чтобы подсветить ключевые компоненты
Очередь URL и политика обхода
Очередь URL управляет порядком обхода и нагрузкой на домены:
- Приоритетная очередь — важные страницы идут первыми
- Вежливость — ограничение запросов к одному домену
- Свежесть — частота повторного обхода страниц
Поиск дубликатов
Чтобы не тратить ресурсы на одинаковые документы, система использует для URL и приближённые методы вроде для похожего содержимого:
- Дедупликация URL — быстрый отсев уже встреченных адресов
- Хеш содержимого — SimHash и MinHash для похожих страниц
- Почти дубликаты — LSH для схожих документов
💡 Вежливый обход и robots.txt
Каждый краулер должен соблюдать robots.txt и не перегружать серверы. Google использует отдельные очереди для каждого домена с ограничением частоты запросов. Типичный интервал между запросами к одному домену — 1-10 секунд.
Инвертированный индекс
Теория
Database Internals
Глубокое погружение в структуры данных для индексации
Инвертированный индекс — базовая структура данных для полнотекстового поиска. Вместо связи «документ → слова» он хранит обратную связь «слово → документы», что позволяет быстро находить кандидатов по термам запроса.
Как устроен инвертированный индекс
Прямой индекс (традиционный):
┌─────────────┬──────────────────────────────────────┐
│ ID док. │ Термы │
├─────────────┼──────────────────────────────────────┤
│ doc_1 │ "system", "design", "interview" │
│ doc_2 │ "design", "patterns", "book" │
│ doc_3 │ "system", "architecture", "book" │
└─────────────┴──────────────────────────────────────┘
Инвертированный индекс:
┌─────────────────┬─────────────────────────────────────────────┐
│ Терм │ Список документов │
├─────────────────┼─────────────────────────────────────────────┤
│ "system" │ [(doc_1, pos:[0]), (doc_3, pos:[0])] │
│ "design" │ [(doc_1, pos:[1]), (doc_2, pos:[0])] │
│ "interview" │ [(doc_1, pos:[2])] │
│ "patterns" │ [(doc_2, pos:[1])] │
│ "book" │ [(doc_2, pos:[2]), (doc_3, pos:[2])] │
│ "architecture" │ [(doc_3, pos:[1])] │
└─────────────────┴─────────────────────────────────────────────┘
Запись списка документов:
┌──────────────────────────────────────────────────────────────┐
│ doc_id: uint64 │
│ term_frequency: uint16 │
│ positions: [uint32, ...] // для запросов по фразе │
│ field_lengths: {title: 5, body: 1000, ...} │
└──────────────────────────────────────────────────────────────┘Компоненты индекса
- Словарь терминов (lexicon)
Словарь всех уникальных термов, который обычно держат в памяти
- Списки документов
Списки документов для каждого терма, которые обычно лежат на диске
- Списки пропусков
Ускоряют пересечение длинных списков документов
Оптимизации хранения
- Дельта-кодирование
Хранение разниц `doc_id` вместо абсолютных значений
- Вариабельное байтовое кодирование
Сжатие маленьких чисел в меньшее количество байт
- Блочное сжатие
PFOR, Simple9, Roaring Bitmaps
Конвейер обработки текста
Выберите этап, чтобы посмотреть результат трансформации
Исходный текст
"The System Design Interview is AMAZING!"Результат
["The","System","Design","Interview","is","AMAZING!"]Смысл этапа
Разбиваем текст на отдельные токены
Обработка поискового запроса
После поступления запроса система должна разобрать его, расширить, получить списки кандидатов и быстро сократить их до небольшого набора документов для ранжирования.
Обработка поискового запроса
Переключайте этапы, чтобы увидеть детали обработки
Текущий этап
Разбор запроса
Токены, операторы и поля запроса
Пример
Запрос: "system design patterns"Токены: ["system","design","patterns"]Оператор: ANDПоля: title?, body?Бюджет задержки
Разбор и расширение: < 20 мс, получение данных: < 50 мс, ранжирование: < 100 мс
⚡ Оптимизация: алгоритм WAND
WAND (Weighted AND) — алгоритм для быстрого отбора Top-K документов без полного сканирования всей коллекции:
- Для каждого терма хранится верхняя граница возможной оценки
- Документы, которые точно не попадут в Top-K, пропускаются заранее
- На практике это даёт многократное ускорение по сравнению с наивным проходом
Ранжирование и качество выдачи
Качество поиска определяется не только полнотой индекса, но и тем, как система расставляет документы. На первом слое обычно работают и , затем подключаются графовые сигналы вроде и более тяжёлые модели наподобие .
Формула BM25
Основная формула для текстового ранжирования:
BM25(D, Q) = Σ IDF(qi) × (f(qi, D) × (k1 + 1)) / (f(qi, D) + k1 × (1 - b + b × |D|/avgdl)) Где: f(qi, D) = частота терма в документе |D| = длина документа avgdl = средняя длина документа k1 = 1.2 (сатурация терма) b = 0.75 (нормализация длины)
BM25 — улучшенная версия TF-IDF с сатурацией и нормализацией длины
PageRank (упрощённо)
Оценка авторитетности страницы по входящим ссылкам:
PR(A) = (1-d) + d × Σ PR(Ti)/C(Ti) Где: d = коэффициент затухания (0.85) Ti = страницы, которые ссылаются на A C(Ti) = число исходящих ссылок у Ti Итеративное вычисление: 1. Инициализировать все PR = 1/N 2. Повторять до сходимости 3. Нормализовать результаты
Классический алгоритм Google для оценки ссылочного авторитета страницы
Многоэтапное ранжирование
Переключайте этапы, чтобы увидеть подробности ранжирования
Текущий этап
Этап 1: Генерация кандидатов
Поиск по индексу и базовая оценка BM25
Выход
≈ 10 000 кандидатов
Бюджет задержки
≈ 50 мс
Ключевые сигналы
- Оценка BM25
- Извлечение Top-10K
- Низкая задержка
Распределённая архитектура поиска
Теория
DDIA: Partitioning
Партиционирование данных для масштабирования
Поисковая система масштаба Google требует распределённой архитектуры, где индекс разбит на , а стратегия напрямую влияет и на масштабирование, и на стоимость каждого запроса.
Стратегии шардирования
Шардирование по документам
Шард 1: документы 1-1M Шард 2: документы 1M-2M Шард 3: документы 2M-3M ... Запрос → все шарды → слияние результатов Плюсы: + Простота + Удобное добавление документов Минусы: - Каждый запрос идёт во все шарды
Шардирование по термам
Шард 1: термы A-F Шард 2: термы G-M Шард 3: термы N-Z ... Запрос → только нужные шарды Плюсы: + Меньше шардов на запрос Минусы: - Перегрев на популярных термах - Сложнее добавлять документы
Распределённая обработка запроса
Подсветите маршрутизацию, работу шардов или финальное слияние
Балансировщик
Распределяет входящий трафик
Маршрутизатор запроса
Разбирает запрос и рассылает его по шардам
Агрегатор
Сливает Top-K и выполняет финальное ранжирование
Шард 1
Реплики A/B/C
Шард 2
Реплики A/B/C
Шард 3
Реплики A/B/C
Бюджет задержки
💡 Архитектура Elasticsearch
Elasticsearch использует шардирование по документам с автоматической маршрутизацией:
shard = hash(document_id) % number_of_primary_shards • Первичные шарды — запись и чтение • Шарды-реплики — чтение и резервирование • Типичная конфигурация: 5 первичных × 2 реплики = 15 шардов
Быстрое обновление индекса
Для новостей и социальных сетей критично, чтобы документ попадал в выдачу почти сразу после публикации. Поэтому архитектура индексации строится как компромисс между скоростью обновления, стоимостью refresh и долговечностью записи.
Многоуровневая архитектура индекса
Переключайте слой, чтобы увидеть его роль и характеристики
Активный слой
Слой мгновенной индексации
Индекс в памяти для горячих данных
Хранилище
RAM
Свежесть
Секунды
Назначение
Запись и свежесть
Задержка
< 1 с до появления в поиске
Параллельный запрос ко всем слоям
Запрос → все слои параллельно → слияние результатов → удаление дублей → ответ
Путь записи
- 1.Документ поступает в Kafka
- 2.Потребитель индексатора его обрабатывает
- 3.Документ попадает во временный буфер в памяти
- 4.После refresh документ становится доступным для поиска
- 5.После flush запись фиксируется на диске
Как работает refresh в Elasticsearch
- refresh_interval: 1s (по умолчанию)
- Создаёт новый сегмент в памяти
- Даёт поиск с почти мгновенным обновлением
- Компромисс между ценой refresh и свежестью индекса
Автодополнение и подсказки
Автодополнение должно отвечать ещё быстрее, чем основной поиск, поэтому обычно опирается на , предвычисленные популярные запросы и отдельный бюджет задержки.
Автодополнение на trie
Выберите префикс, чтобы посмотреть путь в trie и подсказки
Путь в trie
3 символов
< 50 мс
Топ-результаты хранятся в узле префикса
Лучшие подсказки
- system design
- system
- system administrator
- system metrics
Кэш Top-K
На узлах trie хранится список подсказок (Top-10), чтобы не обходить все поддерево.
Оптимизации
- Кэш префиксов — хранение самых популярных начал запросов
- Сжатый trie — объединение цепочек однотипных узлов
- Предвычисление Top-K — хранение лучших подсказок прямо в узлах
Сбор сигналов
- Логи запросов с агрегацией по времени
- Фильтрация оскорбительных запросов
- Персонализация (история пользователя)
Что проговорить на интервью
Что обсудить обязательно
- Инвертированный индекс против прямого индекса и их компромиссы
- Формулы BM25 и TF-IDF и понимание того, откуда берётся оценка
- Стратегия шардирования: по документам или по термам
- Распределение бюджета задержки между этапами
- Почти мгновенная индексация против пакетного обновления
Частые уточняющие вопросы
- Как обрабатывать запросы по точной фразе?
- Как реализовать нечёткий поиск?
- Как добавить персонализацию?
- Как бороться со спамом в результатах?
- Как измерять качество поиска?
Ключевые выводы
Инвертированный индекс
Базовая структура данных для быстрого полнотекстового поиска
Каскадное ранжирование
Путь от дешёвых формул к тяжёлым ML-моделям для баланса качества и задержки
Шардирование по документам
На практике чаще всего это самый понятный и удобный путь масштабирования
Многоуровневое хранение
Разные слои индекса позволяют сочетать свежесть новых данных и эффективность старых
Вежливый обход
Поиск начинается с уважения к robots.txt, лимитам домена и качеству входных данных
Связанные главы
- System Design Interview: An Insider's Guide (краткий обзор) - даёт классический каркас разбора: требования, масштаб, архитектура и ключевые компромиссы поисковой системы.
- Database Internals: A Deep Dive (short summary) - углубляет тему индексов, сжатия списков документов и способов хранения, на которых держится поисковое ядро.
- Designing Data-Intensive Applications, 2nd Edition (short summary) - даёт базу по распределённым данным, репликации и согласованности, без которой поисковый кластер трудно обсуждать всерьёз.
- Web Crawler - раскрывает входной слой поиска: очередь URL, вежливый обход, дедупликацию и стратегию повторного обхода.
- Hacking the System Design Interview (краткий обзор) - помогает превратить сложный поисковый дизайн в внятный разговор на интервью с понятными компромиссами.
- Примеры задач по системному дизайну - ставит поисковую систему в общий контекст кейсов и помогает сравнить её с другими архитектурными сценариями.