Apache Kvrocks项目中HNSW索引单元测试的稳定性问题分析

问题背景

在Apache Kvrocks这个高性能键值存储系统的开发过程中，开发团队发现了一个与HNSW(Hierarchical Navigable Small World)索引相关的单元测试稳定性问题。HNSW是一种用于高效近似最近邻搜索的图结构算法，广泛应用于向量搜索场景。

问题现象

在持续集成(CI)环境中运行HNSW索引相关的单元测试时，测试偶尔会出现失败情况。具体表现为测试中生成的层级分布频率与预期值存在偏差，例如日志中显示"Layer: 4 Frequency: 458 Expected: 411.52266242457773"这样的不匹配信息。

技术分析

HNSW层级分配机制

HNSW算法通过构建多层图结构来实现高效的近似最近邻搜索。在构建过程中，每个数据点会被随机分配到一个层级，这个分配过程遵循指数衰减的概率分布。具体来说：

• 第0层包含所有数据点
• 第L层的点同时存在于所有低于L的层中
• 点被分配到第L层的概率大致为3^(-L)

随机性导致的测试不稳定性

当前实现中使用了C++标准库的random_device作为随机数生成器的种子源。random_device通常会从系统熵源获取真随机数，这意味着：

1. 每次运行测试时，随机数序列都不相同
2. 生成的层级分布虽然理论上会收敛到期望值，但在有限样本下会有波动
3. 这种随机性导致了测试结果的不确定性

数学期望计算

测试中期望值的计算基于概率理论： 对于50000个样本点，分配到第4层的期望数量为： (3^(-4) - 3^(-5)) * 50000 ≈ 411.5226337448559

由于随机波动，实际观察值458与期望值存在约11%的偏差，这在统计学上是可能的，但导致了测试失败。

解决方案

固定随机种子策略

最直接的解决方案是在单元测试中使用固定的随机种子。这种方法可以：

1. 确保每次测试运行都产生相同的随机序列
2. 使测试结果完全可重现
3. 消除因随机性导致的测试不稳定性

实现建议

1. 修改HNSW索引构建接口，增加可选的随机种子参数
2. 在单元测试中显式指定固定种子值
3. 保持生产环境中使用真随机种子的默认行为

阈值调整的替代方案

虽然也可以考虑放宽测试中的比较阈值来容忍更大的随机波动，但这会：

1. 降低测试的精确性
2. 可能掩盖真正的实现问题
3. 不如固定种子方案来得彻底和可靠

结论

通过分析可以确定，HNSW索引单元测试的不稳定性源于算法实现中的随机性。采用固定随机种子的方法能够从根本上解决这个问题，同时保持测试的严格性和可重复性。这种方案既解决了CI环境中的测试稳定性问题，又不会影响生产环境中的算法随机性需求。