Поисковая система ломается не в момент записи документа, а там, где встречаются индексация, ранжирование, свежесть данных и пользовательский путь запроса.
Глава помогает разложить конвейер приёма документов, инвертированный индекс, маршрутизацию по шардам, каскад ранжирования, автодополнение и окно согласованности между записью и поисковой выдачей.
В интервью и инженерных обсуждениях этот кейс полезен тем, что заставляет одновременно держать в голове релевантность, задержки и эксплуатационную стоимость, а не только хранение.
Конвейерное мышление
Критичны приём данных, партиционирование, удаление дублей и задержки между стадиями обработки.
Слой сервинга
Решения по индексам, локальности кэша и пути запроса определяют пользовательскую задержку.
Окно консистентности
Явно фиксируйте, где допустима согласованность в конечном счёте и где нужны более строгие гарантии.
Стоимость и свежесть
Балансируйте скорость обновления данных и стоимость вычислений/хранения.
Почему поиск сложен
Поиск редко проваливают на одной подсистеме — его проваливают на стыках. В одном пользовательском пути сходятся , построение индекса, обработка запроса, ранжирование результатов и постоянная борьба за свежесть данных при огромном масштабе. Поэтому на интервью эту задачу любят: она быстро показывает, умеет ли инженер держать в голове сразу несколько компромиссов.
Ключевые подсистемы
Собирает страницы и планирует повторный обход
Преобразует документы в инвертированный индекс
Отбирает и упорядочивает лучшие результаты
Функциональные требования
Базовые возможности
- Полнотекстовый поиск по миллиардам документов
- Автодополнение и подсказки запросов
- Фасетный поиск и фильтрация
- Релевантное ранжирование результатов
- Исправление опечаток и обработка синонимов
Дополнительные возможности
- Поиск по изображениям и видео
- Персонализация результатов
- Локализация и языковые модели
- Почти мгновенная индексация новых страниц
Нефункциональные требования
Пользователь воспринимает поиск как быстрый, если система удерживает ответ в рамках и выдерживает сотни тысяч без заметной деградации релевантности.
Обход и обновление веб-страниц
Связь
Alex Xu: Web Crawler
Детальный разбор архитектуры краулера в книге System Design Interview
Краулер удерживает сразу три натянутых ограничения: что обходить в первую очередь, как часто возвращаться к документу и как при этом не перегружать чужие сайты. На масштабе Google речь идёт о миллиардах URL в день, и любой перекос в одну сторону бьёт по двум другим — гонка за свежестью съедает вежливость, а вежливость замедляет охват.
Архитектура краулера
Выберите этап, чтобы подсветить ключевые компоненты
Очередь URL и политика обхода
Очередь URL решает, что краулер увидит раньше и насколько мягко обойдётся с чужими серверами:
- Приоритетная очередь — важные страницы идут первыми
- Вежливость — ограничение запросов к одному домену
- Свежесть — частота повторного обхода страниц
Поиск дубликатов
Чтобы не тратить ресурсы на одинаковые документы, система использует для URL и приближённые методы вроде для похожего содержимого:
- Дедупликация URL — быстрый отсев уже встреченных адресов
- Хеш содержимого — SimHash и техника минимального хеша для похожих страниц
- Почти дубликаты — 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) — алгоритм для быстрого отбора первых k документов без полного сканирования всей коллекции:
- Для каждого терма хранится верхняя граница возможной оценки
- Документы, которые точно не попадут в первые k результатов, пропускаются заранее
- На практике это даёт многократное ускорение по сравнению с наивным проходом
Ранжирование и качество выдачи
Полный индекс ещё не делает выдачу хорошей: пользователь смотрит на первые строки, и всё решает порядок документов. На первом слое обычно работают и , затем подключаются графовые сигналы вроде и более тяжёлые модели наподобие .
Лексическая формула ранжирования
Дешёвый первый слой, по которому отбирают кандидатов до тяжёлых моделей:
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 (нормализация длины)
Формула учитывает насыщение терма и нормализацию длины документа
Ссылочный ранг страницы
Оценка авторитетности страницы по входящим ссылкам:
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 ... Запрос → только нужные шарды Плюсы: + Меньше шардов на запрос Минусы: - Перегрев на популярных термах - Сложнее добавлять документы
Распределённая обработка запроса
Путь запроса: вход, fan-out по шардам, локальный Top-K и финальное слияние
Вход и маршрутизация
Балансировщик
Принимает поисковый запрос и отдаёт его свободному маршрутизатору.
Маршрутизатор запроса
Разбирает запрос, выбирает нужные шарды и задаёт общий дедлайн.
Параллельные шарды
Каждый шард считает локальных кандидатов по своей части индекса.
Шард 1
Шард 2
Шард 3
Слияние и ответ
Агрегатор Top-K
Собирает локальные списки, удаляет дубли и применяет финальную дооценку.
Ответ пользователю
Возвращает отсортированный список результатов вместе с метаданными выдачи.
Бюджет задержки
💡 Архитектура Elasticsearch
Elasticsearch использует шардирование по документам с автоматической маршрутизацией:
shard = hash(document_id) % number_of_primary_shards • Первичные шарды — запись и чтение • Шарды-реплики — чтение и резервирование • Типичная конфигурация: 5 первичных × 2 реплики = 15 шардов
Быстрое обновление индекса
Для новостей и социальных сетей критично, чтобы документ попадал в выдачу почти сразу после публикации. Поэтому архитектура индексации строится как компромисс между скоростью обновления, стоимостью цикла обновления индекса и долговечностью записи.
Многоуровневая архитектура индекса
Переключайте слой, чтобы увидеть его роль и характеристики
Активный слой
Слой мгновенной индексации
Индекс в памяти для горячих данных
Хранилище
RAM
Свежесть
Секунды
Назначение
Запись и свежесть
Задержка
< 1 с до появления в поиске
Параллельный запрос ко всем слоям
Запрос → все слои параллельно → слияние результатов → удаление дублей → ответ
Путь записи
- 1.Документ поступает в Kafka
- 2.Потребитель индексатора его обрабатывает
- 3.Документ попадает во временный буфер в памяти
- 4.После обновления индекса документ становится доступным для поиска
- 5.После flush запись фиксируется на диске
Как работает обновление индекса в Elasticsearch
- интервал обновления: 1s (по умолчанию)
- Создаёт новый сегмент в памяти
- Даёт поиск с почти мгновенным обновлением
- Компромисс между ценой обновления и свежестью индекса
Автодополнение и подсказки
Автодополнение должно отвечать ещё быстрее, чем основной поиск, поэтому обычно опирается на , предвычисленные популярные запросы и отдельный бюджет задержки.
Автодополнение на trie
Выберите префикс, чтобы посмотреть путь в trie и подсказки
Путь в trie
3 символов
< 50 мс
Топ-результаты хранятся в узле префикса
Лучшие подсказки
- system design
- system
- system administrator
- system metrics
Кэш Top-K
На узлах trie хранится список подсказок (Top-10), чтобы не обходить все поддерево.
Оптимизации
- Кэш префиксов — хранение самых популярных начал запросов
- Сжатое префиксное дерево — объединение цепочек однотипных узлов
- Предвычисление лучших результатов — хранение лучших подсказок прямо в узлах
Сбор сигналов
- Логи запросов с агрегацией по времени
- Фильтрация оскорбительных запросов
- Персонализация (история пользователя)
Что проговорить на интервью
Что обсудить обязательно
- Инвертированный индекс против прямого индекса и их компромиссы
- Лексические формулы ранжирования и понимание того, откуда берётся оценка
- Стратегия шардирования: по документам или по термам
- Распределение бюджета задержки между этапами
- Почти мгновенная индексация против пакетного обновления
Частые уточняющие вопросы
- Как обрабатывать запросы по точной фразе?
- Как реализовать нечёткий поиск?
- Как добавить персонализацию?
- Как бороться со спамом в результатах?
- Как измерять качество поиска?
Ключевые выводы
Инвертированный индекс
Фундамент поиска: без него запрос по миллиардам документов превращается в полный перебор
Каскадное ранжирование
Путь от дешёвых формул к тяжёлым 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 (краткий обзор) - помогает свернуть сложный поисковый дизайн во внятный разговор на интервью с честно названными компромиссами.
- Примеры задач по системному дизайну - ставит поисковую систему в общий контекст кейсов и помогает сравнить её с другими архитектурными сценариями.