Hotdry.
归档
systems-engineering

HNSW向量搜索的扩展性优化实战：Redis作者的工程视角

深入解析HNSW算法在大规模部署中的内存、速度、管理等维度瓶颈，分享8位量化、全线程化、真正删除等关键优化策略及Redis Vector Sets的工程实践经验。

HNSW（Hierarchical Navigable Small World）算法在向量搜索领域已成为事实标准，但在实际的大规模部署中，其扩展性瓶颈往往成为工程团队的痛点。作为 Redis 作者 antirez 在经过近一年的 HNSW 实现和优化工作后，总结了一套针对扩展性的实战经验。这些优化策略不仅来自理论分析，更来自生产环境的工程实践，值得每一位从事向量搜索系统开发的工程师深入思考。

HNSW 扩展性的根本挑战

HNSW 算法的扩展性瓶颈主要体现在三个方面，这些瓶颈构成了大规模部署时的主要挑战。首先是内存占用问题：HNSW 需要存储大量指针，通常每个节点会有 16 到 32 个甚至更多的邻居指针，这在 64 位系统中意味着每个指针占用 8 字节。其次是多层结构开销：HNSW 采用类似跳表的多层设计，虽然多数节点只分布在第 0 层，但平均仍有约 1.3 倍的空间放大。第三是向量数据规模：每个向量通常包含 300 到 3000 个浮点分量，以 4 字节精度计算，仅向量数据就是 1.2KB 到 12KB 不等。

这些数字看似抽象，但让我们用一个具体场景来理解其影响：加载 300 万个 Word2Vec 条目（每条目 300 维向量）到内存中，仅向量数据就需 3.6GB，加上 HNSW 的指针和层级结构开销，实际内存占用可能达到 4-5GB。这还不包括 Redis 本身的元数据和索引开销，对于资源受限的生产环境显然是难以接受的。

更关键的是，HNSW 的查询性能与数据结构规模呈非线性关系。当图结构增大时，贪心搜索需要遍历更多节点来找到相似向量，这直接影响了系统的响应时间。在 Redis 强调低延迟高吞吐的设计哲学下，HNSW 这种 "天生缓慢" 的特性确实是一个挑战。

内存优化：8 位量化的显著效果

面对内存占用的根本挑战，antirez 的团队发现8 位量化是最有效的优化策略，这种量化的效果堪称 "低挂的果实"。具体实现是对每个向量的每个分量进行独立量化：先计算该向量的最大绝对值，然后使用有符号 8 位整数表示从 - 127 到 127 的量化值。

这种量化策略的数学原理是保持相对比例关系。在计算余弦相似度时，通过简单的缩放运算即可恢复近似浮点结果：

// 量化距离计算
const float scale_product = (range_a/127) * (range_b/127);
for (int i = 0; i < dim; i++) {
    dot0 += ((int32_t)x[i]) * ((int32_t)y[i]); // 整数域运算
}
float dotf = dot0 * scale_product; // 缩放回浮点域

实际测试结果显示，8 位量化带来了4 倍的向量内存减少和4 倍的速度提升，同时在真实应用场景中召回率几乎没有损失。这使得 300 万个 Word2Vec 条目的内存占用从原来的 12GB + 减少到 3GB，完全符合 Redis"快且简单" 的设计理念。

值得注意的是，Redis Vector Sets 还支持其他量化方式。全精度向量为那些对精度要求极高的场景保留，二值量化则为本身就是二进制特征的应用提供空间优化选择。但对于大多数基于学习向量的应用场景，8 位量化提供了最佳的性能 - 内存平衡。

性能优化：全线程化的并发策略

在性能优化方面，antirez 采取了与 Redis 传统 "单线程 + 共享无架构" 不同的大胆策略 ——全线程化 HNSW。这个决策基于两个核心认知：HNSW 在多数使用场景中主要是读密集型操作，且其查询和插入操作具有天然的可并行性。

读操作的线程化相对直接：只要没有写入操作发生，就可以启动多个搜索线程并行执行贪心搜索，将结果返回给被阻塞的客户端。关键的技术创新在于visited 标记的线程安全实现。

传统的 HNSW 实现通常使用全局哈希表来记录已访问节点，但这在多线程环境下会形成竞争条件。antirez 采用了一种更高效的方案：为每个节点维护一个epoch 数组：

typedef struct hnswNode {
    uint32_t level;
    // ... 其他字段
    uint64_t visited_epoch[HNSW_MAX_THREADS]; // 线程安全访问标记
}

每个搜索线程使用独立的 epoch 值，通过比较节点存储的 epoch 值与当前搜索的 epoch 来判断该节点是否已被访问。这种设计避免了锁竞争，同时将空间换时间的权衡明确呈现给开发者。

写操作的线程化更加复杂。HNSW 插入过程被分解为读阶段和提交阶段：读阶段并行执行邻居候选搜索，收集足够的信息后进入需要写锁的提交阶段。这种设计确保了并发安全性，同时最大化利用了多核处理器的计算能力。

通过这些优化策略，Redis Vector Sets 在生产环境中达到了5 万 ops/sec的查询吞吐量，这已经接近了 Redis 单实例的理论性能上限。

内存管理：真正的节点删除机制

大多数 HNSW 实现都无法真正回收删除节点的内存，只能通过 tombstone 标记的方式 "假删除"，原因在于原始论文对节点删除缺乏清晰描述。antirez 的团队实现了强制双向链接策略来解决这个根本性问题。

双向链接的强制实现意味着如果 A 节点指向 B 节点，那么 B 节点必须也指向 A。这种设计看似严格，实际上为内存回收提供了数学保证。当需要删除节点时，系统可以安全地遍历所有指向该节点的指针，确保没有悬空引用。

删除过程中的关键步骤是邻接节点的重连接。当节点被删除后，其邻居节点之间可能出现断连，破坏了小世界特性。Redis 的实现方案是构建距离矩阵，计算邻居节点间的相似度和连接影响，通过贪心配对算法重新建立最优连接。

这种方法的效果令人印象深刻：在包含数百万元素的 HNSW 中删除 95% 的节点后，剩余图仍然保持良好的召回率，没有孤立节点。这种真正的内存回收能力使得 Redis Vector Sets 适合频繁更新的动态数据集，而非静态只读索引。

水平扩展：Redis 数据结构的灵活模式

相比将 HNSW 作为索引组件的传统实现方式，Redis Vector Sets 选择直接暴露 HNSW 作为一级数据结构。这个设计决策体现了 Redis"简单、灵活、可组合" 的核心哲学，同时也为水平扩展提供了天然优势。

数据结构的直接暴露意味着用户可以像操作 Sorted Set 一样操作 Vector Set：可以使用 VADD 添加元素，VREM 删除元素，VSIM 查询相似元素。这种 API 设计避免了索引的复杂性，让开发者能够以更直观的方式构建向量应用。

水平扩展的策略非常简单有效：客户端分片。由于每个 Vector Set 都是独立的数据结构，可以通过哈希分片将不同元素分配到不同的 Redis 实例。查询时使用多路复用技术并行查询多个实例，在客户端合并结果并排序：

# 伪代码示例
def parallel_vector_search(query_vector, instances):
    futures = []
    for instance in instances:
        future = asyncio.create_task(
            vsim_query(instance, query_vector, withscores=True)
        )
        futures.append(future)
    
    results = await asyncio.gather(*futures)
    merged = merge_and_sort(results)  # 客户端合并
    return merged

这种模式特别适合写密集型场景：通过哈希分片，多个 Redis 实例可以并行处理插入操作，相比单实例显著提高了写入吞吐量。同时也简化了故障恢复和负载均衡的复杂性。

加载优化：序列化的工程细节

HNSW 的序列化和反序列化是扩展性优化的重要一环，特别是对于大规模数据加载和 Redis 复制场景。简单的方式是序列化 "元素 + 向量" 对，然后重新构建 HNSW 图结构，但这种方法效率极低。

Redis Vector Sets 采用直接序列化节点和邻居关系的策略：在持久化时保存每个节点的向量数据和其邻居指针列表，反序列化时将邻居 ID 转换为内存指针。这种方法实现了100 倍的加载速度提升，让数百万条目的 HNSW 可以在秒级时间内完成加载。

安全性考虑同样重要：Redis 要求即使在 RDB 文件被恶意修改的情况下，加载后的 HNSW 仍然保持有效性。工程实现中使用了互反性校验算法：对每条边（A 指向 B 或 B 指向 A）计算哈希值并异或到 128 位累加器中，如果每条边都有对应的反向边，累加器结果保证为 0。这种 O (1) 复杂度的校验确保了数据完整性验证的开销极低。

高级功能：JSON 元数据的混合搜索

生产环境中，单纯的向量搜索往往不够用，大多数应用需要混合搜索：根据向量相似度找到候选，再根据业务属性进行过滤。Redis Vector Sets 创新性地在 HNSW 贪心搜索循环中集成了JSON 元数据过滤。

实现原理是在搜索主循环中添加过滤条件判断：

// 简化的混合搜索逻辑
while(candidates.len() > 0) {
    c = candidates.pop_nearest(query);
    if (!c.json_filter_matches(filter_conditions)) continue;
    
    worst_distance = results.get_worst_dist(query);
    if (distance(query,c) > worst_distance) break;
    
    foreach (neighbor from c) {
        if (neighbor.already_visited()) continue;
        if (results.has_space() || neighbor.distance(query) < worst_distance) {
            candidates.add(neighbor);
            results.add(neighbor);
        }
    }
}

这种设计充分利用了 HNSW 的局部性特性：相似向量在图中聚集在一起，过滤不匹配的元素不会大幅增加搜索开销。用户可以用简单的表达式描述过滤条件：

VSIM movies VALUES ... 电影向量 ... 
FILTER '.year >= 1980 and .year < 1990'

相比传统的 "先搜索后过滤" 的两段式方案，这种集成搜索减少了网络往返和数据传输开销，同时保持了搜索的实时性。

实际部署中的权衡与建议

基于这些优化经验，在实际部署 HNSW 系统时需要考虑几个关键权衡。首先是内存与性能的平衡：虽然 8 位量化提供了显著优势，但对于极度要求精度的场景，全精度向量仍然是必要的。其次是并发与复杂性的权衡：全线程化带来的性能提升需要付出实现复杂性的代价，特别是在保证内存安全和一致性方面。

对于不同规模的数据集，建议采用分层策略：

  • 小型数据集（< 100 万条目）：单个 Redis 实例，使用 8 位量化
  • 中型数据集（100 万 - 1000 万条目）：客户端分片，多实例并行
  • 大型数据集（> 1000 万条目）：考虑热冷数据分层，热数据使用内存，查询频率较低的冷数据可以考虑磁盘存储或其他结构

缓存策略的优化同样重要：Redis Vector Sets 适合作为热点数据的快速访问层，对于需要完整搜索功能的大规模应用，可以结合传统数据库或向量数据库构建分层架构。

最重要的是理解 HNSW 的适用边界：虽然通过各种优化技术可以显著改善扩展性，但 HNSW 本质上仍然是内存密集型数据结构。对于极大规模的数据集，需要考虑是否真的需要 HNSW 的实时查询特性，或者是否可以采用预处理、缓存、近似算法等替代方案。

Redis 作者 antirez 的这些经验表明，优秀的算法实现不仅需要深入的算法理解，更需要务实的工程思维。通过内存优化、并发优化、真正的内存管理、灵活的水平扩展策略，HNSW 完全可以在生产环境中发挥其应有的价值，成为向量搜索应用的有力支撑。

参考资料：

查看归档