Home
Blog
ScaNN 索引简介

ScaNN 索引简介

Engineering

January 21, 2026

Jack Li

ScaNN是谷歌对大规模向量搜索中一个常见挑战的回应：如何提高查询吞吐量并减少内存使用量，同时又不对结果质量造成不可接受的影响。从概念上讲，ScaNN 以经典的 IVF+PQ 方法为起点--粗略聚类加上积极的乘积量化--但在此基础上进行了两项重要创新，从而有意义地改变了性能前沿：

分数感知量化目标能更好地保留真实邻域的相对排序，即使在重度压缩的情况下也能提高排序质量。
FastScan是一种 SIMD 优化的 4 位 PQ 查找路径，通过将更多工作保留在 CPU 寄存器中，减少了传统的内存负载瓶颈。

在实践中，当你可以用一些召回率来换取高 QPS 和更小的内存占用（通常将向量压缩到原始大小的约 1/16）时，比如在对召回不敏感的推荐工作负载中，FastScan 是一个不错的选择。

在这篇文章中，我们将以 IVFPQ 为基准，重新审视 IVFPQ，探讨 ScaNN 在此基础上引入的关键优化，并以实验结果作为总结，以实际性能作为讨论的基础。

IVFPQ 回顾

ScaNN 是谷歌在 2020 年提出的，该论文报告称，在 GloVe 数据集上，ScaNN 的性能比 HNSW 提高了 3 倍。详情可参阅原始论文和开源实现。

在介绍 ScaNN 之前，我们先简单回顾一下 IVFPQ，因为 ScaNN 也是建立在相同的整体框架之上的。

IVFPQ 是Inverted File with Product Quantization 的缩写，是一种用于在高维向量数据库中进行高效、大规模近似近邻（ANN）搜索的算法。它是一种混合方法，结合了倒置文件索引（IVF）和乘积量化（PQ）这两种技术，以平衡搜索速度、内存使用和准确性。

IVFPQ 如何工作

该过程包括索引和搜索两个主要步骤：

IVF 层：向量被聚类为nlist 反向列表（簇）。查询时，只访问簇的子集（nprobe ），以权衡召回率和延迟/吞吐量。

PQ 层：在每个访问过的簇内，每个 D 维向量被分成 m 个子向量，每个子向量的维数为 (D/m)。通过将每个子向量分配给其子编码本中最近的中心点，对每个子向量进行量化。如果子代码簿有 256 个中心点，那么每个子向量都可以用uint8 代码（[0, 255] 中的 ID）来表示。

这样，距离计算就可以改写为子向量上的总和：

D(q, X) = D(q, u0) + D(q, u1) + D(q, u2) + ... + D(q, un)

= L（q，id1） + L（q，id2） + L（q，id3） + ... + L（q，idn）

这里，L 表示查找表。在查询时，查找表被构建，记录查询和每个量化子向量之间的距离。所有后续的距离计算都转换为查找表，然后求和。

例如，对于分割成 32 个子向量（每个子向量 4 维）的 128 维向量，如果每个子向量都用uint8 ID 编码，则每个向量的存储成本将从 (128 x 4) 字节降至 (32 x 1) 字节，减少了 1/16。

基于 IVFPQ 的 ScaNN 优化

总之，ScaNN 在两个方面改进了 IVFPQ：

量化：ScaNN 提出的目标不仅仅是用最接近的 k-means 中心点替换每个子向量（即最小化重构误差）。
查找效率：ScaNN 通过 SIMD 友好型 FastScan 路径加速基于 LUT 的搜索，这种搜索通常会占用内存。

分数感知量化损失

由于分析基于 IP 指标，ScaNN 将量化误差分解为平行和垂直分量后，只有平行分量会影响结果，因此应采用较大的惩罚项。因此，损失函数可以重写如下：

$\begin{aligned} ℓ (xi, x~i, w) \end{aligned}$ $∥2begin{aligned}\ell（left（x_i, tilde{x}_i, w\right) &=h_{\|}\left(w,\left\|x_i\right\|\right)\left\|r_{\|}\left(x_i, \tilde{x}_i\right)\right\|^2 +h_{\perp}\left(w,\left\|x_i\right\|\right)\left\|r_{\perp}\left(x_i,$ $ℓ$ $(x$ $,$ $x$ $~$ $,$ $w$ $=$ $h$ $(w .、$ ∥x $∥)$ $r$ $(x$ $,$ $x$ $~$ $)$ $2$ $+$ $h$ $⊥$ $(w, ∥x$ $∥) ∥r$ $(x$ $,$

下图显示了一个二维示例，说明平行分量造成的误差更大，可能导致不正确的近邻结果，因此需要更严重的惩罚。

The left figure shows poor quantization because the parallel offset affects the final result, while the right figure shows better quantization. 左图显示的量化效果较差，因为并行偏移会影响最终结果，而右图显示的量化效果较好。

4 位 PQ 快速扫描

让我们先回顾一下 PQ 的计算过程：在查询过程中，查询和子扇区聚类中心之间的距离会被预先计算，以构建一个查找表。然后通过查找表进行距离计算，以获得分段距离并求和。

然而，频繁读取内存仍会成为性能瓶颈。如果能将查找表做得足够小，以适合寄存器，那么内存读取操作就可以转化为高效的 CPU SIMD 指令。

首先，每个子扇区被聚类为 16 个类，因此一个 4 位值可以代表一个聚类中心--这就是 "4 位 PQ "名称的由来。然后，使用标量量化（SQ）技术将通常以浮点表示的距离进一步转换为 uint8。这样，一个子扇区的查找表就可以用 16 × 8 = 128 位存储在寄存器中。

最后，让我们来研究一下寄存器的存储布局（以 AVX2 指令集为例）：32 向量的子向量与查找表结合，被放置在一个 128 位的寄存器中。这样，"查找 "操作就可以通过一条 SIMD shuffle CPU 指令高效完成。

SIMD Shuffle for Lookup 用于查找的 SIMD 洗牌指令

这里有一个有趣的现象：ScaNN 论文完全侧重于第一项优化，这是合理的，因为它可以被视为一篇强调数学推导的算法论文。然而，论文中展示的实验结果却令人印象深刻。

The experimental results presented in the ScaNN paper. ScaNN 论文中的实验结果。

直观地说，单纯优化损耗不应该产生如此显著的效果。另一个博客也指出了这一点--真正产生差异的是 4 位 PQ FastScan 部分。

实验结果

我们使用向量数据库基准工具VectorDBBench 进行了一次简单的测试。与传统的 IVFFLAT 和 IVF_PQ 相比，ScaNN 的性能优势非常明显。集成到 Milvus 后，在相同召回率的 Cohere1M 数据集上，QPS 可以达到 IVFFLAT 的 5 倍，IVF_PQ 的 6 倍。

不过，QPS 略低于 HNSW 等基于图的索引，因此不是高 QPS 用例的首选。但对于召回率较低的应用场景（如某些推荐系统），使用 ScaNN 而不加载原始数据，可以以极低的内存占用（原始数据的 1/16）达到令人印象深刻的 QPS，使其成为一个极佳的索引选择。

索引类型	案例	QPS	延迟（p99）	调用	内存
IVFFLAT	性能1M	266	0.0173s	0.9544	3G
HNSW	性能1M	1885	0.0054s	0.9438	3.24G
IVF_PQ	性能1M	208	0.0292s	0.928	0.375G
ScaNN（with_raw_data: true）	性能1M	1215	0.0069s	0.9389	3.186G
ScaNN（with_raw_data: false）	性能1M	1265	0.0071s	0.7066	0.186G

结论

ScaNN 建立在我们熟悉的 IVFPQ 框架基础上，但通过在量化和底层查找加速方面的深入工程工作，将其大大推进了一步。ScaNN 将量化目标与排名质量保持一致，并消除了内循环中的内存瓶颈，从而将分数感知量化与 4 位 PQ FastScan 路径相结合，将传统的内存受限流程转变为高效的 SIMD 友好计算。

在实践中，这为 ScaNN 提供了一个清晰明确的定位。在高召回设置中，ScaNN 并不打算取代 HNSW 等基于图的索引。相反，对于内存预算紧张、对召回不敏感的工作负载，ScaNN 以非常小的占用空间提供了高吞吐量。在我们的实验中，集成到 Milvus VectorDB 后，ScaNN 在 Cohere1M 数据集上的 QPS 大约是 IVFFLAT 的 5 倍，这使它成为高吞吐量、低延迟 ANN 检索的有力选择，在这种情况下，压缩和效率比完美召回更重要。

如果您有兴趣进一步了解 ScaNN 或讨论实际系统中的索引选择，请加入我们的Slack 频道，与我们的工程师和社区中的其他人工智能工程师聊天。您还可以通过Milvus Office Hours 预订 20 分钟的一对一课程，以获得见解、指导和问题解答。