设计搜索引擎

搜索引擎是系统设计里「最难但也最经典」的题目之一，因为它把一个系统的所有复杂度（爬取、索引、检索、排序、分布式、实时性、评估）全揉在一起。本文按面试答题结构设计一个支持全网规模的 Web 搜索系统，重点讲清楚倒排索引、分片检索与排序三大硬核环节。

一句话：搜索引擎的本质是「把网页倒过来建索引」——离线把内容变成可检索的倒排表，在线把查询切词后在分片上并行检索、再全局排序。

一、需求澄清与量级估算

1.1 需求澄清

• 搜索范围：全网（Google/Bing 风格）还是站内（电商/文档/日志搜索）？我们选「全网 Web 搜索」，规模按全网估。
• 查询形式：关键词查询为主，是否需要拼写纠错、相关搜索、图片/视频、多语言？
• 新鲜度：新闻类要求分钟级收录，普通页面天级是否可接受？
• 排序目标：相关性 + 权威性（PageRank 类）+ 时效 + 个性化？
• 评估：如何衡量搜索结果质量（离线评测集、线上点击反馈）？

明确假设：

1.2 量级估算

一句话：100 亿文档不可能单机索引，必须「按文档分片 + 倒排索引分布 + 结果合并」，且所有环节（爬取、索引、检索）都要水平扩展。

1.3 非功能需求

一句话：搜索的非功能约束里，「可用性」和「延迟」优先于「一致」，索引短暂滞后可以接受，宕机一秒都不能接受。

二、高层架构设计

                    ┌───────────────────────────────────────────┐
                    │              全网 / 站内内容源                │
                    └───────────────┬───────────────────────────┘
                                    ▼
                    ┌───────────────────────────────────────────┐
                    │              离线索引管道                     │
                    │  爬取调度 ▶ 抓取 ▶ 去重/净化 ▶ 解析 ▶ 分词     │
                    │  ▶ 建倒排索引 ▶ 索引分片 ▶ 索引服务            │
                    └───────────────┬───────────────────────────┘
                                    │ 索引分片(副本)
    ┌──────────────┐                ▼
    │  查询请求 QPS │     ┌───────────────────────────────────────────┐
    │  用户/客户端   │────▶│              在线检索服务                    │
    └──────────────┘     │  查询解析 ▶ 改写 ▶ 分词 ▶ 查询分片广播        │
                         │  ▶ 各分片Top-K ▶ 结果合并 ▶ 全局排序 ▶ 返回  │
                         └───────────────────────────────────────────┘

两大管道：

1. 离线索引管道（Ingestion）：爬取 → 解析 → 建索引，产出分片索引。
2. 在线检索管道（Query）：查询处理 → 分布式检索 → 合并排序。

2.1 为什么索引要分片

• 单机存不下 100 TB 索引。
• 检索要「并行 + 合并」：每个分片只检索自己那一份，再把各分片 Top-K 合并。
• 分片按 文档 ID 哈希 或 文档分桶，保证每个分片独立可检索。

一句话：搜索的核心分布式范式是「数据分片 + 查询广播 + 结果归并」，这与 KV 存储的 key 直达完全不同，是本题必讲的点。

三、核心组件设计

3.1 爬取子系统

URL 队列(去重: 布隆过滤器+DB) → 调度器(优先级/配额) → 抓取器(并发, 遵守Robots)
  → 网页净化(去广告/去噪) → 正文抽取 → 链接抽取(新URL入队) → 哈希去重(SimHash)

爬取要点：礼貌爬取（每域限速、Robots 协议）、去重（URL 规范化 + SimHash 内容去重）、分布式队列（Kafka 作为待抓 URL 池）、增量抓取（根据网页更新频率调整优先级）。

3.2 文档处理与分词

• 分词：中文需要分词（jieba/分词模型），英文按空格 + 词干化（stemming）。
• 归一化：大小写、全半角、去停用词、繁简转换。
• 字段化：标题、正文、锚文本、URL、站点分字段存储，排序时给不同权重。

3.3 倒排索引

倒排索引是搜索的「心脏」：

倒排表 (Posting List):
  词条 term  →  [ (docId, termFreq, 位置列表, 权重...) , ... ]
  "支付"  →  [ (12, 5, [3,17,88,...], 0.8), (345, 2, [9,41], 0.6), ... ]

存储 Schema（离线索引产物）：

-- 主索引分片表(每分片一个物理索引, 逻辑Schema如下)
CREATE TABLE inverted_index (
  term        VARCHAR(64),       -- 词条
  doc_id      BIGINT,
  term_freq   INT,               -- 词频
  positions   ARRAY<INT>,        -- 位置(短语查询/邻近度)
  field_mask  INT,               -- 命中字段(标题/正文)
  payload     BLOB,              -- 压缩的定长字段编码
  PRIMARY KEY (term, doc_id)
) COMMENT='倒排索引(按term哈希分区)';

CREATE TABLE doc_meta (
  doc_id     BIGINT PRIMARY KEY,
  url        VARCHAR(1024),
  title      VARCHAR(512),
  body_hash  BIGINT,             -- 内容去重
  pagerank   DOUBLE,             -- 权威度
  crawl_time DATETIME,
  language   CHAR(2)
);

一句话：倒排索引让「全表扫描」变成「按词条跳表直接定位文档列表」，检索复杂度从 O(N) 降到 O(词条文档数)。

3.4 查询解析与改写

用户查询 "北京 支付 系统 面试"
  → 分词: [北京, 支付, 系统, 面试]
  → 归一化: 同义词扩展 [北京/北京市/Beijing], 拼写纠错 [支付→支付(正确)]
  → 查询改写: 同义词/相关性扩展、时区处理
  → 构造查询树: AND 强约束 + OR 弱约束(宽召回)
  → 查询意图识别: 本地化(加城市限制)/实体识别

3.5 相关性排序：BM25 + 向量混合

经典 BM25 打分：

import math
def bm25_score(query_terms, doc, doc_len, avg_len, idf_cache):
    k1, b = 1.2, 0.75
    score = 0.0
    for t in query_terms:
        tf = doc.term_freq(t)
        if tf == 0:
            continue
        idf = idf_cache[t]
        denom = tf + k1 * (1 - b + b * doc_len / avg_len)
        score += idf * tf * (k1 + 1) / denom
    return score

def final_score(query, doc):
    lexical = bm25_score(query.terms, doc, ...)
    semantic = dot(query.vector, doc.vector)      # 向量相似度
    quality  = doc.pagerank / (1 + doc.pagerank)  # 权威度平滑
    recency  = decay(doc.crawl_time)              # 时效衰减
    return w1*lexical + w2*semantic + w3*quality + w4*recency

混合排序的好处：BM25 保证关键词精确命中，向量召回保证语义相似（同义改写、跨语言），两者加权互补。

3.6 索引存储优化（压缩 + 分层）

全网索引 100 TB 起步，存储优化是必答题：

一句话：倒排索引不光要「能查」，还要「查得快、存得省」——压缩率、内存驻留率、磁盘分层是决定搜索成本的三件事。

3.7 权威度计算（PageRank）

仅靠词面相关性会把「标题党」「垃圾站」排到前面，需要文档权威度信号：

PageRank 迭代: PR(A) = (1-d) + d * Σ PR(T_i) / C(T_i)
  其中 T_i 是指向 A 的网页, C(T_i) 是 T_i 的出链数, d 通常取 0.85

工程要点：

• 离线迭代：全网图在 Hadoop/Spark 上迭代 50-100 轮收敛，产出每文档权威分，写入索引元数据。
• 补充信号：站点级质量分（白名单/黑名单）、域名年龄、外链域名多样性、用户点击「权威性」反馈。
• 实时性：PR 天级更新即可，新站点用「预测 PR」或站点质量分近似。

一句话：权威度是「文档自身的质量背书」，与「查询相关的相关度」相乘后，才能把垃圾页压下去、把权威页提上来。

3.8 查询意图识别

同一查询在不同场景含义不同（「苹果」是水果还是公司？），意图识别提升相关性：

• 分类：导航型 / 信息型 / 交易型（如「买 手机壳」→ 购物意图，接入商品搜索结果）。
• 实体识别与解析：抽取地点、人名、产品名，构造结构化查询（如「北京 天气」→ city=北京）。
• 本地化：结合用户 IP/地点，本地结果加权。
• 时令识别：节假日/热点事件期间时效加权更高。

意图识别一般用「词典规则 + 分类模型」组合：规则兜底高频 query，模型处理长尾语义。识别结果作为排序的强信号，但绝不改变检索本身。

四、数据模型

索引层之外的数据：

五、关键流程

5.1 在线检索时序

查询到达 → 解析/分词/改写 → 构造查询树
  → 查询广播到所有分片(或选取副本)
  → 每个分片: 本地倒排检索 → 用 BM25+向量粗排 → 返回本地 Top-1000
  → 协调节点: 合并各分片 Top-1000 → 全局精排 → 截断 Top-10 → 拼装摘要(高亮)
  → 返回结果 + 相关搜索

两阶段排序：分片内「粗排」（轻量、可用大阈值召回），协调节点「精排」（用全特征重打分），兼顾吞吐与质量。

5.2 索引更新与近实时

近实时索引：新文档写入内存 buffer（可检索），达到阈值后刷入磁盘 segment，旧 segment 合并压缩；查询同时查内存 + 磁盘 segment，实现秒级可见。

5.3 缓存与性能

• 结果缓存：高频查询（热门词）缓存结果，命中率可达 30-50%，缓解下游压力。
• 查询级优化：AND 先从最短 postlist 开始合并（提前终止），跳表求交集。
• 词典缓存：term 词典驻留内存，倒排列表用压缩编码（delta + Varint/PFor）。
• 多级副本：分片副本承载更高 QPS，故障时自动摘除。

5.4 降级与容错

搜索是核心入口，必须「坏了也要有结果」：

一句话：搜索的容错原则是「有降级路径、永远返回 Top-10」——宁可结果差点，也不能白屏。

5.5 增量与全量索引的分工

索引更新不是「要么全量要么增量」，而是分层配合：

• 全量与增量索引共存：查询时合并检索（segment 合并机制）。
• 全量切换用「新索引就绪 → 原子切换 → 旧索引保留待回滚」，避免重建失败导致线上索引失效。

一句话：索引更新是「全量打底 + 增量常态化 + NRT 追新」的三层结构，每层解决一类时效需求。

六、结果质量评估

6.1 离线评测集

• 人工标注查询-相关文档集合（相关性分级：强相关/弱相关/不相关）。
• 用 NDCG、MAP、召回率衡量排序质量，避免只看「在线点击」的偏差（点击受位置影响，首位天然点得多）。
• 评测集要覆盖：常见词、长尾词、歧义词、时效词、不同语言。

6.2 线上点击反馈与 LTR

线上行为（点击、停留、无点击跳出）回流训练学习排序模型（LTR）：

查询日志 → 特征(词法/语义/权威/时效) → 标签(点击/时长分桶)
  → LambdaMART / 神经网络排序 → 上线 → AB → 持续迭代

点击有「位置偏差」：要引入位置特征 + 逆倾向加权（IPW）纠正，否则模型会「学成头条点击率」。

评估闭环：离线评测集（人工标注）→ 离线指标 → AB 实验 → 线上行为反馈 → 回流训练排序模型。

一句话：搜索系统要能持续变好，必须建「离线评测 + 线上点击」双评估体系，否则排序调优就是拍脑袋。

七、性能与扩展

• 分片规模：100 亿文档按 10000 个分片，每片 100 万文档，单分片检索毫秒级。
• 副本扩展：每分片 2-3 副本，承载 QPS 与容灾。
• 降级策略：向量召回不可用 → 纯 BM25；分片故障 → 剔除副本重查；热门词命中缓存直出。
• 容量规划：索引膨胀率 5-10 倍，磁盘按 100 TB × 副本数 × (1+膨胀率) 预留。

八、权衡与备选

取舍原则

• 相关性与实时性：新闻搜索宁牺牲一点相关也要分钟级收录，普通搜索相反。
• 精度与召回：电商搜索偏精确（不想推无关商品），信息检索偏召回。
• 成本与延迟：多副本和更大缓存降低延迟，但要算清楚扩容成本。

九、扩展场景与面试追问

9.1 站内搜索 vs 全网搜索

面试先说「站内用 ES 即可、全网必须分片广播」，再展开全网设计，能体现边界判断。

9.2 语音 / 图片 / 多模态搜索

• 语音：ASR 转文本 → 走文本检索。
• 图片：视觉 Embedding + 反向图片索引（感知哈希/特征向量）+ ANN。
• 多模态：统一 Embedding 空间对齐「文本↔图片」，向量召回 + 重排融合。

9.3 拼写纠错与相关搜索

• 拼写纠错：对查询词做编辑距离/语言模型纠错（如「yyz」→「鸭子」），纠错分高才替换并提示「您是不是要找…」。
• 相关搜索：从查询日志挖掘共现/点击跳转图，产出「相关词推荐」，提升体验和二次点击。
• query 补全：前缀 Trie + 热门度排序（搜索自动完成），与 CHAPTER 13 的题目呼应。

9.4 面试常见追问

十、总结

一句话：搜索引擎面试要按「爬取 → 索引 → 检索 → 排序 → 评估」五段讲，重点秀「倒排索引 + 分片合并」的分布式思想和「BM25/向量混合」的排序权衡，这就是全部加分项。