SeekStorm搜索引擎索引越界问题分析与修复

问题背景

SeekStorm是一个高性能的Rust语言实现的搜索引擎项目。在最新版本中，用户报告了在进行地址数据搜索时出现的索引越界错误问题。这类错误通常表现为"index out of bounds"或"range out of range"异常，会导致搜索引擎服务崩溃。

问题现象

用户在使用SeekStorm索引和搜索美国地址数据时，遇到了两种典型的错误：

1. 在搜索"123 Main St"这类地址时，出现index out of bounds: the len is 5638 but the index is 18446744073702146056错误
2. 在搜索"1443 maple a"这类查询时，出现index out of bounds: the len is 704 but the index is 1023错误

有趣的是，这些错误具有特定的触发条件：

• 添加或删除查询词中的字符后，搜索又能正常工作
• 错误只出现在特定查询词组合下

技术分析

经过深入分析，这些问题主要源于以下几个方面：

1. 压缩算法边界条件处理不足

SeekStorm使用多种压缩算法来优化倒排索引的存储和查询性能，包括RLE(游程编码)和位图压缩。在处理特定长度的文档ID列表时，压缩/解压算法的边界条件处理不够完善。

2. 文档ID列表长度限制

当单个词项的文档ID数量达到65536时，原有的指针大小计算逻辑存在缺陷，导致索引越界。这是因为：

• 原代码仅检查压缩后大小是否小于32768
• 但未考虑原始文档ID数量是否超过65535的限制

3. 查询词组合特性差异

不同的查询词组合会导致搜索引擎选择不同的压缩算法路径：

• 单个词项搜索和多词项交集采用不同实现
• RLE解压在多词交集场景下存在边界条件漏洞

解决方案

针对上述问题，开发团队实施了以下修复措施：

1. 完善RLE解压逻辑

在intersection.rs文件中：

• 修复了RLE解压时的指针重置逻辑
• 确保在解压过程中正确维护运行总和(run sum)和运行计数(run count)

2. 增强指针大小计算

在index_posting.rs文件中修改指针大小计算逻辑：

let mut posting_pointer_size = if value.size_compressed_positions_key < 32_768 && value.posting_count<65_535 {
    value.pointer_pivot_p_docid = value.posting_count as u16 + 1;
    2u8
} else {
    3u8
};

现在同时检查压缩后大小和原始文档ID数量两个条件。

3. 修复控制流问题

修正了intersection.rs中的控制流逻辑，确保在特定条件下正确跳转到重新开始位置，而不是跳过必要的初始化步骤。

影响与启示

这次修复不仅解决了具体的索引越界问题，也为搜索引擎开发提供了宝贵经验：

1. 压缩算法实现必须全面考虑各种边界条件
2. 对于大规模数据，需要考虑所有可能的数值范围
3. 不同查询路径(单词vs多词)需要保持一致的错误处理逻辑

这些改进使SeekStorm能够更稳定地处理各种地址搜索场景，提升了系统的整体健壮性。对于开发者而言，这也提醒我们在实现高性能搜索引擎时，需要特别注意数据压缩和查询处理中的边界条件。