Search System (Google/Elasticsearch)

Поисковая система ломается не в момент записи документа, а в точке встречи индексации, ранжирования, свежести данных и пользовательского query path.

Глава помогает разложить ingest pipeline, inverted index, shard routing, ranking stages, autocomplete и consistency window между write model и search index.

В интервью и инженерных обсуждениях этот кейс полезен тем, что требует одновременно держать в голове relevance, latency и operational cost, а не только storage.

Pipeline Thinking

Критичны ingestion, partitioning, deduplication и задержки между стадиями обработки.

Serving Layer

Решения по индексам, cache locality и query path определяют пользовательскую latency.

Consistency Window

Явно фиксируйте, где допустима eventual consistency и где требуется stronger guarantees.

Cost vs Freshness

Балансируйте скорость обновления данных и стоимость вычислений/хранения.

Введение

Проектирование поисковой системы — одна из самых комплексных задач на System Design интервью. Эта задача охватывает весь спектр: от сбора данных (crawling) до их индексации, ранжирования результатов и масштабирования на петабайты информации.

Ключевые компоненты поисковой системы

Web Crawler

Сбор и обход веб-страниц

Indexer

Создание inverted index

Ranker

Ранжирование результатов

Функциональные требования

Core Features

Полнотекстовый поиск по миллиардам документов
Автодополнение и подсказки запросов
Фасетный поиск и фильтрация
Релевантное ранжирование результатов
Spell correction и обработка синонимов

Дополнительные функции

Поиск по изображениям и видео
Персонализация результатов
Локализация и языковые модели
Real-time индексация новых страниц

Нефункциональные требования

<200ms

P99 latency для поисковых запросов

10B+

Проиндексированных документов

100K QPS

Пиковая нагрузка запросов

99.99%

Availability

Web Crawling

Связь

Alex Xu: Web Crawler

Детальный разбор архитектуры краулера в книге System Design Interview

Читать обзор

Web Crawler — это автоматизированная система для обхода и сбора веб-страниц. Для масштаба Google это означает обработку миллиардов URL ежедневно.

Архитектура Crawler

Выберите этап, чтобы подсветить ключевые компоненты

Priority Queue

Politeness Manager

Freshness Scorer

Worker Pool

DNS Resolver

robots.txt Cache

Parser (HTML)

Duplicate Detector

URL Extractor

URL Frontier

Очередь URL для обхода с приоритизацией и контролем нагрузки на домены:

Priority Queue — важные страницы первыми
Politeness — не более N запросов/сек на домен
Freshness — частота переобхода страниц

Duplicate Detection

Обнаружение дубликатов для экономии ресурсов:

URL Deduplication — Bloom Filter для URL
Content Hash — SimHash/MinHash
Near-Duplicate — LSH для похожих страниц

💡 Politeness и robots.txt

Каждый краулер должен соблюдать robots.txt и не перегружать серверы. Google использует отдельные очереди для каждого домена с rate limiting. Типичный интервал между запросами к одному домену — 1-10 секунд.

Inverted Index

Теория

Database Internals

Глубокое погружение в структуры данных для индексации

Читать обзор

Inverted Index — фундаментальная структура данных для полнотекстового поиска. Вместо хранения «документ → слова» хранит «слово → документы».

Структура Inverted Index

Forward Index (традиционный):
┌─────────────┬──────────────────────────────────────┐
│   Doc ID    │              Terms                   │
├─────────────┼──────────────────────────────────────┤
│   doc_1     │  "system", "design", "interview"     │
│   doc_2     │  "design", "patterns", "book"        │
│   doc_3     │  "system", "architecture", "book"    │
└─────────────┴──────────────────────────────────────┘

Inverted Index:
┌─────────────────┬─────────────────────────────────────────────┐
│      Term       │            Posting List                     │
├─────────────────┼─────────────────────────────────────────────┤
│  "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])]                         │
└─────────────────┴─────────────────────────────────────────────┘

Posting List Entry:
┌──────────────────────────────────────────────────────────────┐
│  doc_id: uint64                                              │
│  term_frequency: uint16                                      │
│  positions: [uint32, ...]  // для phrase queries             │
│  field_lengths: {title: 5, body: 1000, ...}                  │
└──────────────────────────────────────────────────────────────┘

Компоненты индекса

Dictionary (Lexicon)
Словарь всех уникальных термов, хранится в памяти
Posting Lists
Списки документов для каждого терма на диске
Skip Lists
Ускорение пересечения posting lists

Оптимизации хранения

Delta Encoding
Хранение разниц doc_id вместо абсолютных значений
Variable Byte Encoding
Сжатие маленьких чисел в меньшее количество байт
Block Compression
PFOR, Simple9, Roaring Bitmaps

Text Processing Pipeline

Выберите этап, чтобы посмотреть результат трансформации

Input

"The System Design Interview is AMAZING!"

Output

["The","System","Design","Interview","is","AMAZING!"]

Stage Summary

Разбиваем текст на отдельные токены

Query Processing

Обработка запроса включает парсинг, расширение и эффективное пересечение posting lists.

Query Processing Flow

Переключайте этапы, чтобы увидеть детали обработки

Current Stage

Query Parser

Токены, операторы и поля запроса

Example

Input: "system design patterns"Tokens: ["system","design","patterns"]Operator: ANDFields: title?, body?

Latency Budget

Parser + expansion: < 20ms, retrieval: < 50ms, ranking: < 100ms

⚡ Оптимизация: WAND Algorithm

WAND (Weighted AND) — алгоритм для эффективного Top-K retrieval без полного сканирования всех документов:

Каждый терм имеет upper bound score
Пропуск документов, которые не могут попасть в Top-K
До 10x ускорение по сравнению с наивным подходом

Ranking и Relevance

Ранжирование — ключевой компонент, определяющий качество поиска. Современные системы используют многоуровневый подход: от простых формул до ML-моделей.

BM25 Formula

Основная формула для текстового ранжирования:

BM25(D, Q) = Σ IDF(qi) × 
  (f(qi, D) × (k1 + 1)) / 
  (f(qi, D) + k1 × (1 - b + b × |D|/avgdl))

Where:
  f(qi, D) = term frequency in document
  |D| = document length
  avgdl = average document length
  k1 = 1.2 (term saturation)
  b = 0.75 (length normalization)

BM25 — улучшенная версия TF-IDF с сатурацией и нормализацией длины

PageRank (упрощённо)

Оценка авторитетности страницы по входящим ссылкам:

PR(A) = (1-d) + d × Σ PR(Ti)/C(Ti)

Where:
  d = damping factor (0.85)
  Ti = pages linking to A
  C(Ti) = outbound links from Ti

Iterative computation:
  1. Initialize all PR = 1/N
  2. Iterate until convergence
  3. Normalize results

Классический алгоритм Google для web ranking

Multi-Stage Ranking Pipeline

Переключайте этапы, чтобы увидеть подробности ранжирования

Current Stage

Stage 1: Candidate Generation

Inverted index lookup + BM25

Output

~10,000 candidates

Latency Budget

≈ 50ms

Highlights

BM25 scoring
Top-10K retrieval
Low latency

100+

Ranking signals в Google

BERT

Neural ranking models

LTR

Learning to Rank

Distributed Architecture

Теория

DDIA: Partitioning

Партиционирование данных для масштабирования

Читать обзор

Поисковая система масштаба Google требует распределённой архитектуры с шардированием индекса и репликацией для отказоустойчивости.

Sharding Strategies

Document-based Sharding

Shard 1: docs 1-1M
Shard 2: docs 1M-2M
Shard 3: docs 2M-3M
...

Query → все шарды → merge results

Pros:
+ Простота
+ Добавление документов
Cons:
- Каждый запрос → все шарды

Term-based Sharding

Shard 1: terms A-F
Shard 2: terms G-M
Shard 3: terms N-Z
...

Query → только нужные шарды

Pros:
+ Меньше шардов на запрос
Cons:
- Hotspots (популярные термы)
- Сложное добавление docs

Distributed Query Processing

Подсветите этапы: router, shards или финальный merge

Load Balancer

Распределение входящего трафика

Query Router

Parsing + fanout

Aggregator

Merge + re-rank

Shard 1

Replica A/B/C

Shard 2

Replica A/B/C

Shard 3

Replica A/B/C

1. Router разбирает запрос

2. Параллельный fanout на все шарды

3. Merge Top‑K + финальный re‑rank

Latency Budget

Router: < 10msShard fanout: < 100msMerge: < 20ms

💡 Elasticsearch Architecture

Elasticsearch использует document-based sharding с автоматическим routing:

shard = hash(document_id) % number_of_primary_shards

• Primary shards — запись и чтение
• Replica shards — только чтение, failover
• Типичная конфигурация: 5 primary × 2 replicas = 15 shards

Real-time Indexing

Для поиска по новостям и социальным сетям критична скорость индексации — секунды от публикации до появления в поиске.

Tiered Index Architecture

Переключайте слой, чтобы увидеть его роль и характеристики

Active Tier

Real-time Tier

In-memory index (hot data)

Storage

RAM

Freshness

Seconds

Focus

Writes + freshness

Latency

< 1s to searchable

Query Fanout

Query → все tiers параллельно → merge → deduplicate → return

Write Path

1.Документ поступает в Kafka
2.Indexer consumer обрабатывает
3.Запись в in-memory buffer
4.Refresh → searchable
5.Flush → durable on disk

Elasticsearch Refresh

refresh_interval: 1s (default)
Создаёт новый segment в памяти
Near real-time search
Trade-off: refresh cost vs freshness

Autocomplete и Typeahead

Автодополнение требует ещё более низкой latency (<50ms) и работает на основе prefix trees и предвычисленных популярных запросов.

Trie-based Autocomplete

Выберите префикс, чтобы посмотреть путь в trie и подсказки

Trie Path

rootsys

Prefix length

3 chars

Latency target

< 50ms

Note

Топ-результаты хранятся в узле префикса

Top Suggestions

system design
system
system administrator
system metrics

Top-K Cache

На узлах trie хранится список подсказок (Top-10), чтобы не обходить все поддерево.

Оптимизации

Prefix caching — кеш популярных префиксов
Compressed Trie — объединение однодетных узлов
Top-K precomputation — храним топ-10 в узлах

Data Collection

Query logs → агрегация по времени
Фильтрация оскорбительных запросов
Персонализация (история пользователя)

Советы для интервью

Что обсудить обязательно

Inverted index vs forward index — trade-offs
BM25/TF-IDF — понимание формулы
Sharding strategy — document vs term
Latency budget allocation
Near real-time vs batch indexing

Частые follow-up вопросы

Как обрабатывать phrase queries?
Как реализовать fuzzy search?
Как добавить персонализацию?
Как бороться со спамом в результатах?
Как измерять качество поиска?

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

Inverted Index

Фундаментальная структура данных для эффективного полнотекстового поиска

Multi-stage Ranking

Каскад от простых формул к тяжёлым ML-моделям для баланса latency и качества

Document Sharding

Предпочтительная стратегия для большинства систем — проще масштабировать

Tiered Storage

Разделение на real-time, recent и historical tiers для fresh content

Politeness в Crawling

Обязательное соблюдение robots.txt и rate limiting

Связанные главы

System Design Interview: An Insider's Guide (short summary) - даёт классический интервью-флоу для Search System: требования, масштаб, архитектура, bottlenecks и trade-offs.
Database Internals: A Deep Dive (short summary) - углубляет структуры индекса, компрессию posting lists и storage-паттерны, критичные для поискового ядра.
Designing Data-Intensive Applications (short summary) - укрепляет базу по распределённым данным, репликации и консистентности для search-кластера.
Web Crawler - раскрывает ingestion-слой поисковой системы: URL frontier, politeness, deduplication и re-crawl стратегии.
Hacking the System Design Interview (short summary) - помогает упаковать сложный search-дизайн в интервью-коммуникацию с фокусом на компромиссы.
Примеры задач по системному дизайну - позволяет сравнить Search System с другими кейсами и быстрее выбирать релевантные архитектурные шаблоны.