3. 倒排索引压缩原理：信息熵与编码冗余、压缩比与解压速度的权衡、压缩对内存/磁盘I/O的影响
3.1 信息熵与编码冗余
倒排索引本质上是一个从词项到文档ID列表的映射。原始倒排表（Posting List）通常存储为有序的整数序列。信息熵（Entropy）衡量了该序列中每个符号的平均信息量，是理论无损压缩的下限。
核心公式： 对于符号集 \( S \) 中符号 \( s_i \) 出现的概率 \( p(s_i) \)，其信息熵 \( H(S) = -\sum p(s_i) \log_2 p(s_i) \)（单位：bit/符号）。
编码冗余（Redundancy）是指实际编码长度与信息熵之间的差值。倒排索引中存在大量冗余，主要来源包括：
- 文档ID的局部聚集性： 同一词项对应的文档ID往往在数值上接近，导致差值（Gap）很小，概率分布极不均匀。
- 重复模式： 高频词（如“的”、“是”）的倒排表极长，且ID间隔规律性强。
- 元数据冗余： 词频（TF）、位置信息等字段的数值范围有限，存在大量重复值。
下图展示了原始文档ID序列与差值序列（Gap List）的信息熵对比，差值序列的熵值显著降低，为压缩提供了理论基础。
3.2 压缩比与解压速度的权衡
倒排索引压缩算法需要在压缩比（Compression Ratio）和解压速度（Decompression Speed）之间进行权衡。高压缩比意味着更少的内存占用和磁盘I/O，但通常以更复杂的解码逻辑为代价，导致解压延迟增加。
| 压缩算法 | 压缩比（bits/doc） | 解压速度（亿doc/s） | 适用场景 |
|---|---|---|---|
| Varint（可变字节编码） | ~8-12 | ~2-3 | 通用场景，平衡性好 |
| Group Varint | ~9-13 | ~4-6 | 批量查询，高吞吐场景 |
| Simple-8b | ~5-8 | ~3-5 | 内存敏感，中等速度 |
| PForDelta（Patched Frame-of-Reference） | ~4-7 | ~5-8 | 高性能搜索，低尾延迟 |
| Roaring Bitmaps | ~3-6 | ~8-15 | 位图运算密集，极速交集 |
尾延迟关键洞察： 在搜索服务中，P99/P999尾延迟对解压速度的波动极为敏感。PForDelta和Roaring Bitmaps虽然压缩比不是最优，但因其稳定的高解压吞吐，能有效抑制尾延迟尖峰。
下图直观展示了不同算法在压缩比与解压速度二维空间中的分布，越靠近右上角表示综合性能越优。
3.3 压缩对内存/磁盘I/O的影响
压缩算法直接影响倒排索引在内存和磁盘两个层级的行为，进而影响搜索服务的整体延迟分布。
3.3.1 内存层面
- 内存占用降低： 压缩比越高，索引在内存中的常驻大小越小，可以缓存更多热数据，减少缺页中断（Page Fault）。
- CPU缓存友好性： 高解压速度的算法（如PForDelta）通常采用批量解码，能充分利用CPU的L1/L2缓存行，减少随机内存访问。
- GC压力缓解： 在Java等托管语言中，更小的内存对象意味着更少的垃圾回收停顿，间接降低尾延迟。
3.3.2 磁盘I/O层面
- I/O量减少： 压缩后的索引体积更小，每次查询从磁盘读取的数据量减少，磁盘I/O延迟降低。
- I/O次数增加风险： 某些高压缩比算法（如Varint）解码时需要逐字节解析，可能导致更多的随机小I/O，反而增加延迟。
- 预读失效： 压缩后的数据布局与原始顺序不同，操作系统的预读机制可能失效，需要应用层做针对性优化。
压测陷阱： 在尾延迟压测中，不能仅关注平均I/O延迟。压缩算法可能导致“长尾I/O”——即大部分请求I/O很快，但少数请求因解码复杂或缓存未命中而出现极高延迟。这是尾延迟恶化的常见原因。
下图展示了压缩算法在内存与磁盘I/O之间的典型影响路径。
3.4 小结：压缩算法选择对尾延迟的启示
从信息熵到编码冗余，再到压缩比与解压速度的权衡，最终落实到内存/磁盘I/O的影响，倒排索引压缩算法的选择是一个系统工程。在搜索服务尾延迟压测中，应优先关注：
- 解压速度的稳定性： 选择解压速度波动小的算法（如PForDelta、Roaring Bitmaps），避免因解码耗时差异导致尾延迟恶化。
- 内存访问模式： 优先采用批量解码、缓存行友好的算法，减少随机内存访问带来的延迟抖动。
- I/O模型适配： 结合存储介质（SSD/HDD）和I/O调度策略，选择能减少I/O次数且避免小随机I/O的压缩方案。