系统设计：搜索引擎

如何设计一个支持百亿级文档、毫秒级响应的搜索引擎？

需求分析

场景与规模

功能需求

1. 全文检索：支持关键词、短语、布尔查询
2. 拼写纠错：“iphone” → 提示 “iphone”
3. 自动补全：输入 “ja” → 提示 “java”, “javascript”
4. 相关性排序：按与查询的相关度排序
5. 过滤与聚合：按时间、类目、价格等过滤，支持 facet 统计
6. 个性化：根据用户历史行为调整排序

核心概念：倒排索引

倒排索引（Inverted Index）是搜索引擎的核心数据结构。

正排索引 vs 倒排索引

正排索引（文档 → 词）：
  Doc 1: "搜索引擎设计"
  Doc 2: "分布式系统设计"
  Doc 3: "搜索引擎优化"

倒排索引（词 → 文档列表）：
  搜索   → [Doc 1, Doc 3]
  引擎   → [Doc 1, Doc 3]
  设计   → [Doc 1, Doc 2]
  分布式 → [Doc 2]
  系统   → [Doc 2]
  优化   → [Doc 3]

倒排索引的结构

Term Dictionary（词项字典）
  ├── "分布式"
  │     └── Posting List: [(Doc2, 位置1, 权重), ...]
  ├── "搜索"
  │     └── Posting List: [(Doc1, 位置1, 权重), (Doc3, 位置1, 权重)]
  ├── "引擎"
  │     └── Posting List: [(Doc1, 位置2, 权重), (Doc3, 位置2, 权重)]
  └── ...

Posting List 通常存储：
  - 文档 ID
  - 词频（TF）
  - 位置信息（用于短语查询）
  - 字段信息（title/body 中的权重不同）

压缩算法

Posting List 是排序的整数序列，可以用压缩算法大幅减少存储：

• Delta Encoding：存储相邻文档 ID 的差值（通常更小）
• Variable Byte Encoding：小整数用更少字节
• Roaring Bitmaps：密集集合用 bitset，稀疏集合用数组

系统架构

┌─────────────────────────────────────────────────────────────────┐
│                        Search Service                            │
│  ┌────────────┐  ┌────────────┐  ┌────────────┐  ┌───────────┐ │
│  │  Query     │  │ Autocomplete│  │ Spell     │  │ Personal- │ │
│  │  Parser    │  │ Service    │  │ Check     │  │ ization   │ │
│  └─────┬──────┘  └────────────┘  └────────────┘  └─────┬─────┘ │
│        │                                                │       │
│  ┌─────▼────────────────────────────────────────────────▼─────┐ │
│  │                    Ranking Service                           │ │
│  │  ┌────────────┐  ┌────────────┐  ┌────────────────────┐   │ │
│  │  │ First Phase│  │ Second Phase│  │ Learning to Rank   │   │ │
│  │  │ (粗排)      │  │ (精排)      │  │ (LTR/机器学习排序)  │   │ │
│  │  │ BM25/TF-IDF│  │ 业务规则   │  │ GBDT/Neural Ranker│   │ │
│  │  └────────────┘  └────────────┘  └────────────────────┘   │ │
│  └────────────────────────────────────────────────────────────┘ │
└─────┬────────────────────────┬──────────────────────────────────┘
      │                        │
┌─────▼────────────┐    ┌─────▼────────────┐
│   Index Service  │    │   Index Service  │
│  (Shard 1..N)    │    │  (Shard N+1..2N) │
│  ┌────────────┐  │    │  ┌────────────┐  │
│  │ Index Node │  │    │  │ Index Node │  │
│  │ ( inverted │  │    │  │ ( inverted │  │
│  │   index )  │  │    │  │   index )  │  │
│  └────────────┘  │    │  └────────────┘  │
└────────┬─────────┘    └────────┬─────────┘
         │                      │
         └──────────┬───────────┘
                    │
┌───────────────────▼─────────────────────────────┐
│              Document Store                       │
│  (原始文档存储，用于 result snippet 和详情页)      │
│         MySQL / MongoDB / HBase / S3             │
└─────────────────────────────────────────────────┘

核心模块详解

1. 数据采集与索引构建（Crawl + Index）

Web Crawler / Data Source
       │
       ▼
┌──────────────┐     ┌──────────────┐     ┌──────────────┐
│   Document   │────→│  Analyzer    │────→│   Indexer    │
│   Fetcher    │     │  (分词/过滤)  │     │ (倒排索引构建)│
└──────────────┘     └──────────────┘     └──────────────┘
                                                  │
                                                  ▼
                                          ┌──────────────┐
                                          │ Index Shard  │
                                          │ (Lucene seg) │
                                          └──────────────┘

分词（Tokenization）示例：

# 英文分词
"Search Engine Design" → ["search", "engine", "design"]

# 中文分词（需要分词器）
"搜索引擎设计" → ["搜索", "引擎", "设计"]  # 或 ["搜索引擎", "设计"]

# 常见中文分词器
# - IK Analyzer（最常用）
# - jieba（Python 流行）
# - HanLP（功能全面）

索引构建流程：

1. 文档解析：提取 title、body、url、时间戳等字段
2. 分词处理：Tokenizer → Filter（小写化、去停用词、同义词扩展）
3. 生成 Posting List：统计 TF、位置信息
4. 段合并（Segment Merge）：小的索引段定期合并为大的段，减少查询时的段扫描

2. 查询处理流程

用户输入: "分布式 搜索引擎"
           │
           ▼
┌────────────────────┐
│ 1. Query Parser    │ 分词 → ["分布式", "搜索引擎"]
└─────────┬──────────┘
          ▼
┌────────────────────┐
│ 2. Query Rewrite   │ 同义词扩展、拼写纠错
│                    │ "搜索引擎" → ["搜索引擎", "Search Engine"]
└─────────┬──────────┘
          ▼
┌────────────────────┐
│ 3. Index Search    │ 从倒排索引取各词的 Posting List
│                    │ 合并求交集（AND）或并集（OR）
└─────────┬──────────┘
          ▼
┌────────────────────┐
│ 4. Scoring         │ BM25 / TF-IDF 计算相关性得分
└─────────┬──────────┘
          ▼
┌────────────────────┐
│ 5. Ranking         │ 粗排 → 精排 → LTR
└─────────┬──────────┘
          ▼
┌────────────────────┐
│ 6. Result Rendering│ 取摘要（snippet）、高亮关键词
└────────────────────┘

3. 相关性算法

TF-IDF

TF(t, d) = 词 t 在文档 d 中出现的次数 / 文档 d 的总词数
IDF(t) = log(文档总数 / 包含词 t 的文档数 + 1)

Score(d, q) = Σ TF(t, d) × IDF(t)  (对查询 q 中每个词 t 求和)

BM25（推荐）

BM25 是 TF-IDF 的改进版，解决了 TF 无限增长的问题。

BM25(d, q) = Σ IDF(t) × [TF(t,d) × (k1 + 1)] / [TF(t,d) + k1 × (1 - b + b × |d|/avgdl)]

参数：
- k1: 控制 TF 的饱和度，通常 1.2-2.0
- b: 控制文档长度归一化，通常 0.75

Python 实现：

import math

class BM25:
    def __init__(self, documents, k1=1.5, b=0.75):
        self.k1 = k1
        self.b = b
        self.documents = documents
        self.N = len(documents)
        self.avgdl = sum(len(d) for d in documents) / self.N

        # 计算 IDF
        self.idf = {}
        for doc in documents:
            for word in set(doc):
                self.idf[word] = self.idf.get(word, 0) + 1
        for word, df in self.idf.items():
            self.idf[word] = math.log((self.N - df + 0.5) / (df + 0.5) + 1)

    def score(self, document, query):
        score = 0.0
        dl = len(document)
        for word in query:
            if word not in self.idf:
                continue
            tf = document.count(word)
            idf = self.idf[word]
            score += idf * (tf * (self.k1 + 1)) / (
                tf + self.k1 * (1 - self.b + self.b * dl / self.avgdl)
            )
        return score

4. 分布式搜索

分片（Sharding）策略

查询分发与合并

用户查询 "搜索引擎"
         │
    Coordinator Node
         │
    ┌────┼────┬────┐
    ▼    ▼    ▼    ▼
 Shard1 Shard2 Shard3 Shard4
 (#1-100M) ...
    │    │    │    │
    └────┼────┼────┘
         ▼
    Merge Results
    (取 Top K 全局排序)

优化：如果查询带有类别过滤（如 category=tech），可以直接路由到相关 shard。

5. 近实时索引（Near Real-time）

搜索引擎需要平衡查询性能和索引实时性：

新文档写入
    │
    ▼
┌─────────┐   ┌─────────┐   ┌─────────┐
│ In-Memory│ → │ Segment │ → │ Merged  │
│ Index    │   │ (flush) │   │ Segment │
│ (translog)│   │         │   │         │
└─────────┘   └─────────┘   └─────────┘
  可搜索       持久化磁盘      定期合并
  (1s 内)     (默认 5s)      (后台任务)

Elasticsearch 的 refresh 机制：

• refresh_interval = 1s：每秒将内存中的文档刷新为可搜索的段
• 可以调大以减少刷新频率（提升索引吞吐），调小以提升实时性

面试答题框架

第一步：明确场景（30秒）

我需要确认：搜索对象的类型（网页/商品/文档）、数据规模、查询模式（关键词/过滤/聚合）、实时性要求。

第二步：核心数据结构（1分钟）

倒排索引是核心：词项字典 → Posting List（文档 ID、TF、位置）。用 Delta Encoding 压缩，FST 结构加速前缀查找。

第三步：搜索流程（2分钟）

Query Parser → Query Rewrite（同义词/纠错）→ Index Search（多词 Posting List 交集/并集）→ Scoring（BM25）→ Ranking（粗排/精排/LTR）→ Result Rendering。

第四步：分布式架构（2分钟）

按文档 ID 哈希分片，Coordinator 分发查询到各 shard，合并 Top K 结果。副本机制保证高可用。

第五步：高级特性（2分钟，面试官追问时）

• 自动补全：独立的 FST/Trie 索引，前缀匹配
• 拼写纠错：编辑距离（Levenshtein）+ 语言模型
• 个性化：Learning to Rank（GBDT/Neural），用户行为特征
• 近实时：translog + 定期 refresh + 段合并

Elasticsearch 原理速查

Elasticsearch 是基于 Apache Lucene 的分布式搜索引擎。

常见问题

Q：倒排索引为什么比正排索引快？

正排需要遍历所有文档来查找包含某词的文档；倒排直接通过词项字典定位到文档列表。

Q：ES 的写入为什么不是实时的？

Lucene 的段（Segment）是不可变的，新文档先写入内存 buffer 和 translog，refresh 后才变为可搜索的新段。这是为了查询性能（不可变段无需锁，可缓存）。

Q：100 亿文档的索引需要多大存储？

原始文本通常压缩到 1/4-1/3。倒排索引大约是原始文本的 20-50%。100 亿文档原始 100TB，索引约 20-50TB。

Q：BM25 和 TF-IDF 的核心区别？

BM25 对 TF 做了饱和度控制（词频再高也不会线性增长），并引入文档长度归一化，实际效果通常优于 TF-IDF。