搜索引擎系统设计

发表于 分类于

设计一个像 Google 那样的通用搜索引擎，核心链路分为三阶段：爬取 → 索引 → 查询排序。每一阶段都是独立的分布式系统。

一、爬虫系统 (Web Crawler)

1.1 爬虫架构

1
2
3
4
5
6
7
8
9
10
          [URL Frontier 队列]
                 │
    ┌────────────┼────────────┐
    │            │            │
[爬虫节点1] [爬虫节点2] [爬虫节点3]
    │            │            │
    ├─ DNS 解析 ─┤────────────┤
    ├─ HTTP 请求 ─┤───────────┤
    ├─ 解析 HTML ─┤───────────┤
    └─ 提取链接 → URL Frontier

1.2 URL Frontier

URL Frontier 是爬虫的调度核心，负责管理待抓取 URL 的优先级和去重。

设计要点：

要点 方案
去重 Bloom Filter 过滤已爬取的 URL
优先级 PageRank 预估值、域名热度、更新频率综合排序
礼貌性 同一域名两次请求间隔 ≥ 1 秒（robots.txt）
分布式 按域名一致性哈希分配到不同爬虫节点，避免同一域名被多节点同时抓取

1.3 去重策略

URL 数量是百亿级别的，不能用 HashSet 全量存储。布隆过滤器是标准的 URL 去重方案：

1
2
3
新 URL → BloomFilter.mightContain(url) → 
    False → 一定未爬取过 → 加入队列并插入 BloomFilter
    True → 可能已爬取 → 跳过（容忍少量漏抓）

误判率控制：100 亿 URL，误判率 0.01% → 约 24GB Bloom Filter，漏抓约 100 万条，可接受。

二、文档处理与索引构建

2.1 文档处理流程

1
2
3
原始 HTML → 清洗(Tag去除) → 分词 → 停用词过滤 → 词干提取 → 
    ┌→ [正排索引] 文档ID → 标题/正文/URL/时间
    └→ [倒排索引] 词 → {文档ID列表, 词频, 位置}

2.2 倒排索引

倒排索引是搜索引擎的核心数据结构：

1
2
3
4
5
6
7
词(Term)    →   倒排列表(Posting List)
─────────────────────────────────────
"系统设计"   →   [doc-1: tf=3, pos=[5,12,28]], 
                  [doc-5: tf=1, pos=[42]], 
                  [doc-12: tf=2, pos=[8,19]]
"分布式"    →   [doc-1: tf=1, pos=[15]],
                  [doc-8: tf=4, pos=[3,11,20,35]]

存储优化：

  • 压缩：倒排列表使用 Variable Byte / PForDelta 压缩，节省 60-80% 存储
  • 跳表加速：在倒排列表中加入跳表指针，加速多词 AND 查询时的求交操作

2.3 索引分片

百亿级文档，索引无法放在单机上。采用文档分片 + 查询扇出策略：

1
2
3
4
5
6
7
8
9
10
11
查询 "分布式 系统设计"
    │
[查询路由器]
    │
    ├→ [索引分片1: doc-0 ~ doc-1亿]
    ├→ [索引分片2: doc-1亿 ~ doc-2亿]
    └→ [索引分片N: doc-(N-1)亿 ~ doc-N亿]
    │
[合并排序 Top-100]
    │
  返回结果

每个分片独立存储完整的倒排索引，查询时扇出到所有分片，各分片返回 Top-K 结果后合并排序。

三、查询处理

3.1 查询流程

1
2
3
4
5
6
7
8
9
10
11
用户输入 "分布式系统设计"
    │
[查询解析] → 分词 → "分布式" "系统" "设计"
    │
[查询改写] → 纠错、扩展（"设计" → "设计模式" "系统架构"）
    │
[索引查询] → 并行查所有索引分片
    │
[相关性排序] → BM25 / TF-IDF / 点击率 / 时效性
    │
[Top-K 合并] → 取各分片的 Top-100，全局排序返回前 100

3.2 排序模型

早期搜索引擎使用 TF-IDF 和 BM25 等基于词频的统计模型。现代搜索引擎引入了数百个排序特征，使用机器学习模型（如 LambdaMART）进行学习排序。

关键排序特征：

  • 文本相关性：BM25 得分、标题匹配度
  • 质量信号：PageRank、域名权威度
  • 用户行为：点击率、停留时间、跳出率
  • 时效性：发布时间、内容新鲜度
  • 个性化：用户搜索历史、地理位置

3.3 分页优化

“搜索千万结果，用户只看前两页”——所以分页是性能优化的关键。

问题 方案
深分页 不实际查询第 1000 页，限制最多展示前 50 页
速度 各分片只返回前 100 条，合并后取 Top-100
一致性 搜索过程中索引可能正在更新，结果轻微波动可接受
缓存 热门搜索词的结果缓存到 Redis（TTL 5-30 分钟）

四、搜索建议与自动补全

搜索建议（Autocomplete/Suggester）需要在用户输入每个字符时实时返回建议。

4.1 Trie 树实现

关键词前缀查询适合用 Trie 树（字典树）：

1
2
3
4
5
6
7
8
9
10
11
12
root
├─ d
│  └─ i
│     └─ s
│        └─ t
│           └─ r ("分布式")
│              └─ i
│                 └─ b ("分布式")
├─ j
│  └─ a
│     └─ v ("Java")
│        └─ a ("Java")

每个节点存储 Top-10 最热门的完整查询词，查询时遍历到对应前缀节点直接返回。

4.2 生产级优化

  • FST (有限状态转换器)：比 Trie 节省 90% 内存，ES 和 Lucene 均使用 FST 实现 Term Index
  • 热度排序：每个节点按搜索频率排序 Top-K，存储 Top-10
  • 实时更新：通过 Kafka 消费搜索日志，在线更新前缀树节点的 Top-K

五、系统总览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
                  ┌──────────────┐
                  │   用户搜索    │
                  └──────┬───────┘
                         │
       ┌─────────────────┼─────────────────┐
       │                 │                 │
  [搜索建议]       [查询路由器]        [广告引擎]
  (Trie/FST)          │              (独立系统)
                      │
       ┌──────────────┼──────────────┐
       │              │              │
  [索引分片1]    [索引分片2]    [索引分片N]
       │              │              │
       └──────────────┼──────────────┘
                      │
               [合并排序层]
                      │
                  [返回结果]

后端离线链路：
[爬虫] → [文档处理] → [索引构建] → [索引分发] → [Ranking模型训练]

六、容量估算

假设 1000 亿网页：

  • 平均每页 10KB 文本 → 1000亿 × 10KB = 1PB 原始文本
  • 倒排索引约为原文本的 20%，压缩后 → ~200TB
  • 正排索引存储标题/摘要 → ~50TB
  • 每台机器 256GB 内存，需要 ~1000 台索引服务器

Google 的实际规模远超这个数量级，通过定制的 Colossus 文件系统、Spanner 数据库和自研 TPU 训练排序模型支撑。

七、小结

搜索引擎的设计精髓在于”空间换时间”——用海量预处理（爬取、索引）换取查询时的毫秒级响应。核心数据结构（倒排索引、FST、跳表、Bloom Filter）的选择直接决定了性能边界。在实践中，Google 和 Elasticsearch 选择了不同的路线：Google 走全栈自研，ES 基于 Lucene 提供开箱即用的分布式搜索引擎。