Kvrocks项目中HNSW索引单元测试的随机性问题分析

问题背景

在Kvrocks这个高性能键值存储项目中，HNSW（Hierarchical Navigable Small World）索引是一个重要的组成部分，它用于高效处理高维向量的近似最近邻搜索。在最近的CI测试中，开发团队发现了一个不稳定的测试用例失败问题。

问题现象

测试用例在执行过程中出现了预期值与实际值不匹配的情况。具体表现为：

• 测试期望值：411.52266242457773
• 实际计算值：411.5226337448559

这个差异虽然看似微小，但在严格的单元测试中会导致测试失败。值得注意的是，这个问题并非每次都会出现，而是呈现出"flaky"（不稳定）的特性，即在某些运行中通过，而在另一些运行中失败。

技术分析

HNSW层级选择机制

HNSW索引采用分层结构，每一层的构建都基于概率选择。在Kvrocks的实现中，层级选择遵循以下数学公式：

(3^-4 - 3^-5) * 50000 = 411.5226337448559

这个公式决定了向量被分配到特定层级的概率。理论上，当样本量足够大时，实际分布应该接近这个期望值。

随机数生成问题

问题的根源在于当前的实现使用了真随机数生成器：

std::random_device rd;
std::mt19937 gen(rd());

这种实现方式有两个特点：

1. 使用硬件熵源（如果可用）生成随机种子
2. 每次运行都会产生不同的随机序列

这导致了测试结果的不确定性，虽然在大样本情况下统计结果会趋近期望值，但在有限的测试样本中可能会出现波动。

解决方案

确定性测试环境

为了保证测试的可重复性，建议采用以下改进措施：

1. 固定随机种子：在测试环境中使用固定的随机种子，确保每次测试运行都产生相同的随机序列
2. 适当放宽容差：对于概率性测试，可以设置合理的误差范围，而不是要求精确匹配
3. 分离测试逻辑：将随机数生成器作为可配置参数，在生产环境使用真随机，在测试环境使用伪随机

实现建议

修改HNSW索引的初始化接口，增加随机种子参数：

class HNSWIndexer {
public:
    explicit HNSWIndexer(int random_seed = -1) {
        if (random_seed == -1) {
            std::random_device rd;
            gen_ = std::mt19937(rd());
        } else {
            gen_ = std::mt19937(random_seed);
        }
    }
    // ...
private:
    std::mt19937 gen_;
};

在单元测试中，可以使用固定种子：

TEST(HNSWIndexerTest, LayerDistribution) {
    HNSWIndexer indexer(42);  // 使用固定种子42
    // 执行测试...
}

更深层次的思考

这个问题反映了在实现概率算法时测试策略的重要性。对于依赖随机性的算法，测试设计需要考虑：

1. 确定性测试：核心逻辑应该能够在确定性环境下验证
2. 统计测试：对于概率分布，应该设计大样本测试来验证统计特性
3. 异常路径测试：验证算法在极端随机输入下的鲁棒性

在Kvrocks这样的存储系统中，平衡测试的严格性和稳定性尤为重要。过于严格的测试可能导致不必要的CI失败，而过于宽松的测试则可能掩盖真正的问题。

结论

通过分析Kvrocks中HNSW索引的随机性问题，我们不仅解决了具体的测试失败问题，更重要的是建立了一套适用于概率算法的测试方法论。这种思路可以推广到其他类似场景，帮助开发者构建更加健壮的测试体系。