Day 12 Hard Search Inverted Index Elasticsearch Vector Search

搜索系统 — 从倒排索引到语义检索Search Systems: Inverted Index, Lucene Segments, Sharding, Vector ANN

问题场景 + 需求约束

给一个 10 亿文档的 IM / 电商搜索（像 Discord 的消息搜索、淘宝的商品搜索）设计后端：用户输入关键词，要在 200ms 内返回最相关的 20 条。难点不是「装个 Elasticsearch」，而是写入和查询同时要快——文档以 5 万/秒涌入，查询也是 5 万 QPS，还要支持前缀补全、错字容忍、以及「找意思相近的」语义检索。

规模：10 亿文档 ×平均 1KB 正文，倒排索引膨胀到原文 30%~150%（取决于是否存 positions / term vectors）。
写入：5w docs/s，要求近实时可见（写入到可搜索 < 1s），但不能为此牺牲查询延迟。
查询：5w QPS，p99 < 200ms；既要 BM25 关键词匹配，又要 embedding 语义召回。
相关性：top-20 的排序质量是产品生死线——搜索不准等于没有。
约束：单 Lucene index 上限约 21 亿文档（MAX_DOC = 2^31），逼着你从第一天就分片。

高层架构

graph TD
    subgraph 写入路径
      SRC[("源 DB / CDC")] --> Q["索引队列
Kafka"]
      Q --> IW["Index Workers
批量 bulk"]
      IW --> SEG["不可变 Segment
Lucene"]
    end
    subgraph 查询路径
      U["用户查询"] --> CO["Coordinator
query router"]
      CO -->|scatter| S1["Shard 1
倒排+HNSW"]
      CO -->|scatter| S2["Shard 2"]
      CO -->|scatter| S3["Shard N"]
      S1 -->|top-k| CO
      S2 -->|top-k| CO
      S3 -->|top-k| CO
      CO -->|gather + rerank| U
    end
    SEG -.refresh 1s.-> S1

    classDef src fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    classDef pipe fill:#0e2030,stroke:#5eead4,color:#e8eef5
    classDef shard fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef coord fill:#1a2530,stroke:#64c8ff,color:#e8eef5
    class SRC src
    class Q,IW,SEG pipe
    class S1,S2,S3 shard
    class CO,U coord

写入异步批量进队列 → 生成不可变 segment；查询 scatter-gather 到所有 shard，coordinator 归并重排

组件职责：写入不直接打索引，先进 Kafka 解耦、削峰、保证 at-least-once；Index Workers 攒批做 bulk 写（单条写 Lucene 极慢）。每个 shard 是一个独立 Lucene index，内含倒排索引（关键词）和 HNSW 图（向量）。Coordinator 负责把查询广播到所有 shard、合并各自的 top-k、做最终重排。

关键技术点

1. 倒排索引：搜索引擎的心脏

一句话 trade-off：用空间和写入成本，换 O(查询词数) 而非 O(文档数) 的检索。

原理：正排是「文档 → 词」，搜索要反过来——倒排索引是「词 → 包含它的文档列表（posting list）」。查询「红色连衣裙」就是取这两个词的 posting list 求交集。每个 posting 还存词频（tf）和位置（positions，支持短语查询）。打分用 BM25：词频越高、文档越短、词越稀有（IDF），分数越高。词典本身用 FST（有限状态转换机）压缩，几百万词条压到几 MB 还能做前缀匹配。

Trade-off：

存 positions / term vectors：✅ 支持短语、高亮、相似文档；❌ 索引体积翻倍。不需要短语搜索就关掉。
posting list 压缩：doc id 递增 → delta 编码 + VByte/PFor；稀疏高频词用 Roaring Bitmap，求交极快。代价是 CPU 解压。
前缀倒排（instant search）：为 "engine" 的每个前缀 "e/en/eng…" 都建 posting list，输入即搜；代价是索引膨胀数倍——Algolia 的做法。

# posting list 求交（带 skip 跳表加速，galloping）
def intersect(p1, p2):           # p1 短，p2 长
    out = []
    for doc in p1:
        # 在 p2 上用 skip pointer 跳到 >= doc 的位置
        if p2.advance_to(doc) == doc:
            out.append(doc)      # 两个 list 都含 → 命中
    return out
# 关键：先交最短的 list，最大化剪枝

现实案例：

Lucene / Elasticsearch：FST 词典 + Roaring Bitmap posting，是绝大多数搜索的底座。
Algolia：为所有前缀建倒排列表实现毫秒级 instant search（见其 Inside the Algolia Engine 系列）。
Postgres GIN：全文搜索的倒排索引就叫 Generalized Inverted Index。

2. 不可变 Segment 与「在线 vs 离线索引」

一句话 trade-off：可见性延迟 vs 写吞吐 vs 查询碎片化，三者拉扯。

原理：Lucene 的 segment 一旦写盘就不可变。新文档不去改旧 segment，而是攒在内存 buffer，定期 refresh 刷成一个新的小 segment 才可被搜索（ES 默认 1s，这就是「近实时 NRT」的由来）。删除/更新不是原地改，而是写 tombstone 标记，查询时过滤、合并时才真正清除。小 segment 越积越多会拖慢查询，后台 merge 把它们合并成大 segment。

Trade-off（refresh 间隔）：

refresh 短（1s）：✅ 写入快速可见；❌ 段碎片多、merge 压力大、写放大严重。
refresh 长（30s）或离线重建：✅ 吞吐高、段大查询快；❌ 数据延迟可见。批量回填历史数据时应直接关掉 refresh（设 -1），导完再开。
在线增量 vs 离线全量重建：换分词器/改 mapping 往往无法在线改，要离线重建新索引 + 别名原子切换（zero-downtime reindex）。

现实案例：

Discord：消息懒索引——不实时写，通过消息队列让 worker 拉一批批量 bulk 写入 ES，充分利用批量吞吐（见 How Discord Indexes Trillions of Messages）。
Elasticsearch：refresh_interval 和 force-merge 是调优写入吞吐的第一旋钮。
LinkedIn (Galene)：在线增量索引 + 离线 Hadoop 全量构建双轨并行。

3. 分片、Scatter-Gather 与深分页陷阱

一句话 trade-off：分片提供并行与水平扩展，但归并与 tail latency 是代价。

原理：10 亿文档放不进单机，按 doc id hash 或 业务维度（Discord 按 guild/DM）切成 N 个 shard。查询走 scatter-gather：coordinator 把 query 广播到每个 shard，每个 shard 本地算出自己的 top-k 返回，coordinator 归并出全局 top-k。replica 副本既做高可用又分摊读 QPS。

深分页陷阱：要第 10000~10020 条（from=10000,size=20）时，每个 shard 都得返回前 10020 条给 coordinator 排序——内存和网络随页码线性爆炸。正解是 search_after（基于上一页最后一条的排序值游标）或 scroll（快照遍历）。永远别给用户开放跳到第 N 页。

Trade-off（分片数）：

shard 多：✅ 并行度高、单 shard 小；❌ 每次查询 fan-out 广，最慢的那个 shard 决定 p99（tail latency 放大）、归并开销大。
routing key：把同租户数据路由到同一 shard，查询只打一个 shard，避免广播——但可能造成热点 shard。
IDF 不一致：BM25 的 IDF 是 per-shard 算的，文档分布不均会让跨 shard 打分不可比，需 DFS query-then-fetch 全局统计校正。

现实案例：

Discord：按 guild/DM 路由分片；并撞上单 Lucene index MAX_DOC ≈ 20 亿的硬上限，被迫多集群（现运行约 40 个 ES 集群，p50 < 100ms）。
Elasticsearch：query-then-fetch 两阶段——先各 shard 返回 id+score，归并后再 fetch 命中文档正文，避免传输全部正文。

4. 向量检索：从关键词到语义

一句话 trade-off：召回率 vs 内存 vs 构建/更新成本，ANN 算法在此三角里选点。

原理：关键词搜不到「笔记本电脑」≈「laptop」这种语义近似。把文档和查询都用 embedding 模型映射成向量，语义相近 = 向量距离近。10 亿向量暴力算距离不可行，用 ANN（近似最近邻）。HNSW 建多层导航图：上层稀疏长边快速逼近，下层稠密短边精修，查询是从顶层贪心下降，复杂度近似对数级。

算法	召回	内存	更新	适合
HNSW	高	大（全在内存）	难（删除麻烦）	低延迟、量级中等
IVF-PQ	中	小（量化压缩）	较易	十亿级、省内存
暴力 (flat)	100%	大	易	百万内、要精确

# HNSW 查询：从顶层逐层贪心下降
def search(q, entry, top_layer):
    cur = entry
    for layer in range(top_layer, 0, -1):     # 上层粗导航
        cur = greedy_nearest(q, cur, layer)   # 跳到更近的邻居
    # 第 0 层做带候选堆的精搜，返回 ef 个候选
    return beam_search(q, cur, layer=0, ef=128)

混合检索（Hybrid）才是生产答案：纯向量丢失精确匹配（型号 "A1706"、人名），纯关键词丢失语义。生产里BM25 + 向量并行召回，用 RRF（倒数排名融合）合并两路结果，再用 cross-encoder 精排 top-100。下期推荐系统会深入 rerank。

现实案例：

Lucene / Elasticsearch：内置 HNSW 实现 kNN 查询，可与 BM25 在同一引擎混合。
pgvector：Postgres 扩展，支持 HNSW/IVFFlat，让小团队不用单独上向量库。
Faiss (Meta)：IVF-PQ 的工业标杆，十亿级向量的内存压缩方案。

扩展与优化

读写分离：索引集群（接写）与查询集群（接读）物理隔离，避免 merge 风暴拖垮查询；replica 扩查询 QPS。
冷热分层：近期数据放 SSD hot tier，历史数据 force-merge 成大段挪到便宜的 warm/cold tier（Discord/日志类系统的标配）。
查询缓存：高频 query 的结果集 + filter bitmap 缓存（呼应 Day 2）。
多阶段检索：召回（BM25+向量，要快要全）→ 粗排 → 精排（贵的模型只跑 top-100），用算力换相关性。
CDC 入索引：用 Debezium 把 DB binlog 变更流进 Kafka 再进索引，保证搜索与主库最终一致（呼应 Day 7 Outbox）。

常见陷阱 + 面试问题

陷阱：把搜索当数据库的 LIKE。 ES 不是事务库、刷新有延迟、不保证强一致；它是派生数据，源头永远是主库，要能随时从主库重建。
陷阱：分片数拍脑袋定且不可改。 ES 的 primary shard 数建索引时就固定，改它要 reindex。先做容量估算（单 shard 建议 10~50GB）。
陷阱：忽略分词与相关性调优。 中文分词、同义词、stemming 没做好，召回再快也是错的。相关性是搜索的产品核心，不是 infra 细节。
面试题：为什么 Lucene segment 要不可变？答：免锁并发读、利于 OS page cache 与压缩、崩溃恢复简单；代价是删除靠 tombstone、需后台 merge。
面试题：跨 shard 的 BM25 打分为什么可能不准？如何修正？（per-shard IDF → DFS 全局统计）
面试题：from+size 深分页为什么爆？换成什么？（每 shard 取 from+size → search_after 游标）
面试题：向量索引 HNSW 删除一个文档为什么麻烦？（图结构原地删会破坏连通性，通常软删 + 周期重建）

深入资源

DDIA《Designing Data-Intensive Applications》(Kleppmann) 第 3 章「Storage and Retrieval」讲全文索引与 LSM 思想。
Discord 工程博客：How Discord Indexes Trillions of Messages（ES 多集群、Rust、MAX_DOC 限制）。
Algolia 博客：Inside the Algolia Engine 系列（倒排索引、前缀 instant search、索引 vs 查询分离）。
HNSW 论文：Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs（arXiv 1603.09320, IEEE TPAMI 2020）。
Elasticsearch: The Definitive Guide（官方）讲 segment、refresh、scatter-gather、query-then-fetch。

深入思考（点击展开答案）

1. refresh_interval 调成 1s 和 30s，对「写吞吐」「查询延迟」「磁盘」各有什么二阶影响？为什么批量导入时反而要设成 -1？

refresh 每次都生成一个新的小 segment。1s：段产生极快，段数量暴涨 → 查询要扫更多段（查询是各段结果归并），同时 merge 线程疯狂合并小段，写放大（同一份数据被反复读写合并）拉高 CPU 和磁盘 IO。30s：攒更久刷一个更大的段，段少、merge 少、写吞吐高，代价是数据 30s 才可见。

批量导入设 -1（关闭自动 refresh）：历史数据回填时根本没人实时搜它，每秒刷段纯属浪费——关掉后所有文档攒在 buffer，导完手动 refresh 一次 + force-merge 成大段。实测能把导入吞吐提升数倍。这是「可见性延迟」与「写吞吐」trade-off 的极端选择：导入期不要可见性，全要吞吐。

2. 用户搜一个超热词（如「促销」命中 5000 万文档），scatter-gather 会发生什么？怎么救？

每个 shard 都要遍历这个巨长的 posting list 算 BM25、取本地 top-k，CPU 飙升；coordinator 归并各 shard 结果。问题不在归并（只传 top-k），而在每个 shard 扫描海量 posting + 打分的开销，以及最慢 shard 决定整体延迟。

救法：① WAND / Block-Max WAND 动态剪枝——维护当前 top-k 的分数阈值，提前跳过不可能进 top-k 的文档，不必给每个候选都打分；② 高频词结果缓存；③ 加 filter 缩小候选集（时间范围、类目）；④ 用 two-phase：先廉价召回再精排。Lucene 的 BMW 是默认查询加速器，正是为这种长尾热词设计。

3. 既然有了语义向量检索，为什么不直接抛弃 BM25 倒排索引、全用向量？

向量擅长「意思相近」，但丢失精确匹配：搜商品型号 "A1706"、订单号、人名、代码符号时，embedding 会把它和一堆「差不多」的东西混在一起，而用户要的是精确那一个。向量还有：① 召回是近似的（ANN 漏召回）；② 无法解释为什么命中（倒排能指出命中了哪个词）；③ 索引/查询都要跑模型，成本高；④ 过滤（filter）和聚合（facet）在倒排上极其廉价，纯向量库做这些很别扭。

所以生产是 hybrid：BM25 保精确与可解释，向量补语义召回，RRF 融合。Google、淘宝、Elasticsearch 都是两路并行而非二选一。「全用向量」是面试里常见的过度简化陷阱。

4. 估算：10 亿文档、每文档 1KB，倒排索引大概多大？需要多少 shard、多少内存？

量级估算（数量级即可，别背精确值）：原文 10 亿 × 1KB ≈ 1TB。倒排索引体积通常是原文的 30%~150%——存 positions/term vectors 就接近甚至超过原文，纯 doc id posting 则小得多。取中间值约 0.5~1TB 索引。

分片：单 shard 建议 10~50GB（太大恢复慢、merge 久），取 30GB → 约 20~40 个 primary shard。加 1 副本则文档/存储翻倍。

内存：搜索吃 OS page cache（让热段常驻内存）和 JVM heap（FST 词典、缓存）。经验是给文件系统缓存留够装下热点段。若上 HNSW 向量：10 亿 × 768 维 × 4 字节 ≈ 3TB，纯 HNSW 全驻内存不现实 → 必须 IVF-PQ 量化压缩，或只对热数据建向量索引。这一步常暴露候选人对「向量比文本贵一个量级」缺乏直觉。

5. 搜索索引和主库如何保持一致？双写为什么是反模式？正确做法是什么？（串联 Day 7）

双写（应用同时写 DB 和 ES）是反模式：两个写没有原子性，DB 成功而 ES 失败（或反之）就永久不一致，且无重试边界、并发下顺序错乱。这正是 Day 7 分布式事务要避免的跨系统双写。

正确做法：① Outbox + CDC——应用只写主库（含一张 outbox 表或直接读 binlog），用 Debezium 把变更可靠地流进 Kafka，索引 worker 消费后写 ES。主库是唯一真相源，ES 是派生数据，可随时全量重建。② 消息处理要幂等（按 doc id upsert，带版本号防乱序，旧版本丢弃）。③ 接受最终一致：搜索结果短暂滞后于主库是可接受的（呼应 Day 6）。关键心智：搜索索引永远是「可重建的缓存」，不是真相源。

← 回到 index