Введение
Проектирование поисковой системы — одна из самых комплексных задач на System Design интервью. Эта задача охватывает весь спектр: от сбора данных (crawling) до их индексации, ранжирования результатов и масштабирования на петабайты информации.
Ключевые компоненты поисковой системы
Сбор и обход веб-страниц
Создание inverted index
Ранжирование результатов
Функциональные требования
Core Features
- Полнотекстовый поиск по миллиардам документов
- Автодополнение и подсказки запросов
- Фасетный поиск и фильтрация
- Релевантное ранжирование результатов
- Spell correction и обработка синонимов
Дополнительные функции
- Поиск по изображениям и видео
- Персонализация результатов
- Локализация и языковые модели
- Real-time индексация новых страниц
Нефункциональные требования
Web Crawling
Связь
Alex Xu: Web Crawler
Детальный разбор архитектуры краулера в книге System Design Interview
Web Crawler — это автоматизированная система для обхода и сбора веб-страниц. Для масштаба Google это означает обработку миллиардов URL ежедневно.
Архитектура Crawler
Выберите этап, чтобы подсветить ключевые компоненты
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
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
Latency Budget
💡 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
3 chars
< 50ms
Топ-результаты хранятся в узле префикса
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