倒排索引基础回顾：结构、词典与分片原理
在深入缓存一致性架构之前，必须牢固掌握倒排索引的核心数据结构。倒排索引是搜索引擎实现亚秒级全文检索的基石，它将“文档→词项”的正向关系反转，建立“词项→文档列表”的快速查找路径。本章从三个层次展开：索引结构、词典与倒排列表、索引分片原理。
2.1 倒排索引结构
倒排索引由两个核心部分组成：词典（Dictionary） 和 倒排列表（Posting List）。词典存储所有不重复的词项（Term），每个词项指向一个倒排列表；倒排列表记录包含该词项的所有文档ID及位置信息。
核心公式： 倒排索引 = 词典 + 倒排列表。查询时，先查词典定位词项，再遍历倒排列表获取文档集合。
下图展示了一个包含3篇文档的倒排索引结构示例：
关键理解： 倒排索引的查询时间复杂度为 O(1) 到 O(log N)（取决于词典实现），远优于正向索引的 O(N) 全表扫描。这是搜索引擎能够处理百亿级文档的核心原因。
2.2 词典与倒排列表
2.2.1 词典（Dictionary）
词典是倒排索引的入口，必须支持高效的词项查找。常见的词典实现方式有三种：
| 实现方式 | 查询复杂度 | 内存占用 | 适用场景 |
|---|---|---|---|
| 哈希表 | O(1) 平均 | 较高（需预分配） | 小规模词典，内存充足 |
| B+ 树 | O(log N) | 中等 | 磁盘索引，范围查询 |
| 有限状态转换器（FST） | O(len(term)) | 极低（共享前缀） | Lucene/Elasticsearch 核心 |
工程实践： Lucene 使用 FST（Finite State Transducer）作为词典实现，它利用词项之间的公共前缀压缩存储，内存占用仅为哈希表的 1/5 到 1/10，同时支持前缀查询和模糊匹配。
2.2.2 倒排列表（Posting List）
倒排列表记录包含某个词项的所有文档信息，通常包含以下字段：
- 文档ID（DocID）：文档的唯一标识，通常按升序排列以支持跳表合并。
- 词频（Term Frequency, TF）：词项在该文档中出现的次数，用于计算相关性评分。
- 位置信息（Position）：词项在文档中的偏移位置，支持短语查询和邻近搜索。
- Payload（可选）：附加元数据，如词性标注、权重等。
倒排列表的压缩技术直接影响索引的存储效率和查询性能：
| 压缩算法 | 原理 | 压缩比 | 解码速度 |
|---|---|---|---|
| 差分编码（Delta Encoding） | 存储相邻DocID的差值 | 2x-5x | 极快 |
| 可变字节编码（VByte） | 按需分配字节数 | 3x-8x | 快 |
| Simple9/16 | 打包多个整数到32/64位 | 4x-10x | 中等 |
| Roaring Bitmaps | 分桶+位图/数组混合 | 5x-20x | 极快（支持位运算） |
注意： 压缩算法的选择需要权衡压缩比和解码速度。在缓存一致性场景中，频繁更新的倒排列表更适合使用 Roaring Bitmaps，因为它支持高效的集合运算（并、交、差），且更新时无需完全重建。
2.3 索引分片原理
当单机无法承载全部索引数据时，必须将索引水平切分为多个分片（Shard）。分片是分布式搜索引擎（如 Elasticsearch）的基本数据单元，每个分片本质上是一个独立的倒排索引实例。
2.3.1 分片策略
常见的分片策略有两种：
| 策略 | 路由方式 | 优点 | 缺点 |
|---|---|---|---|
| 基于文档ID哈希 | hash(docID) % N | 数据均匀分布，实现简单 | 范围查询需广播所有分片 |
| 基于词项范围 | 词项字典序分区 | 支持词项级剪枝，减少查询分片数 | 数据倾斜风险（热点词项） |
下图对比了两种分片策略的查询路径：
2.3.2 分片与副本
在分布式系统中，每个分片通常配置多个副本（Replica），用于提高可用性和查询吞吐量：
- 主分片（Primary Shard）：负责写入和一致性协调，每个分片只有一个主分片。
- 副本分片（Replica Shard）：从主分片同步数据，只处理查询请求，不参与写入。
缓存一致性挑战： 当主分片更新倒排索引时，所有副本分片必须同步更新。如果使用缓存加速查询，还需要保证缓存与分片数据的一致性——这正是本课程后续章节要解决的核心问题。
2.3.3 分片合并与段（Segment）
在 Lucene/Elasticsearch 中，每个分片内部由多个段（Segment）组成。段是不可变的倒排索引文件，新写入的数据先写入内存缓冲区，然后定期刷盘生成新段。段合并（Merge）将多个小段合并为一个大段，以优化查询性能并回收磁盘空间。
| 操作 | 触发条件 | 对缓存的影响 |
|---|---|---|
| 段刷新（Refresh） | 每隔 1s（默认） | 新段可见，缓存需失效或更新 |
| 段刷盘（Flush） | 内存缓冲区满或 30min | 数据持久化，缓存可重新加载 |
| 段合并（Merge） | 段数量超过阈值 | 段被删除，缓存中的段ID失效 |
缓存失效陷阱： 段合并会删除旧段、创建新段。如果缓存中存储了段级别的元数据（如段ID、文档计数），合并后必须及时清理，否则查询可能返回过期或错误的结果。这是缓存一致性设计中容易被忽视的细节。