ScaNN 索引簡介

ScaNN是 Google 對大規模向量搜尋中一個大家都熟悉的挑戰的回應：如何在不影響結果品質的情況下，提高查詢吞吐量並減少記憶體使用量。在概念上，ScaNN 以經典的 IVF+PQ 方程式為起點 (粗略的聚類加上積極的乘積量化)，但卻加入了兩項重要的創新，讓效能前沿有了顯著的改變：

• 分數感知量化目標能更好地保留真正鄰居的相對排序，即使在嚴重壓縮的情況下也能改善排序品質。

• FastScan是 SIMD 最佳化的 4 位元 PQ 尋找路徑，可將更多工作保留在 CPU 暫存器中，從而減少傳統的記憶體負載瓶頸。

實際上，當您可以用一些召回率來換取高 QPS 和更小的記憶體佔用空間 (通常會將向量壓縮到原始大小的 ~1/16)，例如在對召回不敏感的推薦工作負載中，FastScan 是一個很好的選擇。

在這篇文章中，我們將以 IVFPQ 為基準，重新檢視 IVFPQ，並探討 ScaNN 在其基礎上所引進的主要最佳化，最後再以實驗結果做為總結，以測量的效能做為討論的基礎。

IVFPQ 回顧

ScaNN 由 Google 在 2020 年提出，論文報告在 GloVe 資料集上的效能比 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 代碼 (ID 在 [0, 255] 中) 表示。

因此，距離計算可以重寫為子向量上的總和：

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：

1. 量化：ScaNN 提出了一個超越簡單地以最接近的 k-means 中心點取代每個子向量 (即最小化重建誤差) 的目標。

2. 查詢效率：ScaNN 透過 SIMD 友好的 FastScan 路徑加速基於 LUT 的搜尋，而 LUT 通常會受到記憶體限制。

分數感知量化損失

由於分析是以 IP 度量為基礎，因此 ScaNN 將量化誤差分解為平行與垂直分量後，只有平行分量會影響結果，因此應使用較大的懲罰項目。因此，損失函數可改寫如下：

$$\begin{array}{rll}{\displaystyle \mathrm{\ell }({\mathrm{xi}}_{},{\mathrm{x~i}}_{}}& {\displaystyle ,}& {\displaystyle w)}\end{array}$$$$∥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,\tilde{x}_i\right)\right\|^2 \end{aligned}$$ ℓ$$\begin{array}{r}(x\end{array}$$i, x~i,w) =h∥ $$\begin{array}{l}(w.、\end{array}$$∥xi$$\begin{array}{l}\Vert )\end{array}$$ $$\begin{array}{l}r\end{array}$$∥ $$\begin{array}{l}(x\end{array}$$i, x~i) 2+h$$\begin{array}{l}\perp \end{array}$$ $$\begin{array}{l}(w,\Vert x\end{array}$$i$$\begin{array}{l})\Vert r\end{array}$$⊥ $$\begin{array}{l}(x\end{array}$$i,

下圖顯示一個二維範例，說明平行分量造成的誤差較大，會導致不正確的最近鄰結果，因此應受到較嚴重的懲罰。

左圖顯示量化效果不佳，因為平行偏移會影響最終結果，而右圖則顯示量化效果較佳。

4 位元 PQ FastScan

首先讓我們回顧一下 PQ 的計算過程：在查詢過程中，查詢與子向量叢集中心之間的距離是預先計算出來的，以建立查詢表。然後透過查詢表執行距離計算，以取得分段距離並加以總和。

然而，頻繁讀取記憶體仍會成為效能瓶頸。如果能將查詢表縮小到足以放入暫存器，記憶體讀取作業就能轉換成有效率的 CPU SIMD 指令。

首先，每個子向量被聚類為 16 個類別，因此一個 4 位元值可以代表一個聚類中心 - 這就是 「4 位元 PQ」 名稱的由來。接著，通常以浮點數表示的距離使用標量量化 (Scalar Quantization, SQ) 進一步轉換為 uint8。如此一來，一個子向量的查詢表就可以使用 16 × 8 = 128 位元儲存在暫存器中。

最後，讓我們檢視一下暫存器的儲存配置（以 AVX2 指令集為例）：32 個向量的子向量與查詢表結合，放置在 128 位元的暫存器中。這樣，「查詢」作業就可以使用單一 SIMD shuffle CPU 指令有效率地完成。

暫存器配置

查找的 SIMD 洗牌

這裡有一個有趣的觀察：ScaNN 論文完全著重於第一個最佳化，這是合理的，因為它可被視為一篇強調數學推導的演算法論文。然而，該論文提出的實驗結果卻令人印象深刻。

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 頻道，與我們的工程師和社群中的其他 AI 工程師交談。您也可以透過Milvus Office Hours 預約 20 分鐘的一對一會議，以獲得深入的瞭解、指導和問題解答。