Eine kurze Einführung in den ScaNN-Index

ScaNN ist Googles Antwort auf eine bekannte Herausforderung bei der groß angelegten Vektorsuche: Wie lässt sich der Abfragedurchsatz erhöhen und die Speichernutzung reduzieren, ohne dass die Ergebnisqualität inakzeptabel leidet? Das Konzept von ScaNN basiert auf dem klassischen IVF+PQ-Rezept - grobes Clustering plus aggressive Produktquantisierung - aber es werden zwei wichtige Innovationen hinzugefügt, die die Leistungsgrenze deutlich verschieben:

• Ein Quantisierungsziel, das die relative Reihenfolge echter Nachbarn besser beibehält und so die Qualität des Rankings selbst bei starker Kompression verbessert.

• FastScan ist ein SIMD-optimierter 4-Bit-PQ-Lookup-Pfad, der den traditionellen Engpass bei der Speicherbelastung reduziert, indem mehr Arbeit in den CPU-Registern verbleibt.

In der Praxis ist dies eine gute Wahl, wenn Sie damit einverstanden sind, einen gewissen Rückruf gegen eine hohe QPS und einen viel kleineren Speicherbedarf einzutauschen (oft werden Vektoren auf ~1/16 der ursprünglichen Größe komprimiert), wie z. B. bei rückrufunempfindlichen Empfehlungsarbeiten.

In diesem Beitrag werden wir IVFPQ als Grundlage erneut betrachten, die wichtigsten Optimierungen, die ScaNN darauf aufbaut, untersuchen und mit experimentellen Ergebnissen abschließen, die die Diskussion auf die gemessene Leistung stützen.

IVFPQ-Rekapitulation

ScaNN wurde von Google im Jahr 2020 vorgeschlagen, und das Papier berichtet eine 3× Leistungsverbesserung über HNSW auf dem GloVe-Datensatz. Einzelheiten finden Sie in der Originalarbeit und der Open-Source-Implementierung.

Bevor wir ScaNN vorstellen, werden wir kurz IVFPQ rekapitulieren, da ScaNN auf demselben Gesamtrahmen aufbaut.

IVFPQ steht für Inverted File with Product Quantization, ein Algorithmus, der für die effiziente und groß angelegte Approximate Nearest Neighbor (ANN) Suche in hochdimensionalen Vektordatenbanken verwendet wird. Es handelt sich um einen hybriden Ansatz, der zwei Techniken, den invertierten Dateiindex (IVF) und die Produktquantisierung (PQ), kombiniert, um ein Gleichgewicht zwischen Suchgeschwindigkeit, Speicherverbrauch und Genauigkeit herzustellen.

Wie funktioniert IVFPQ?

Der Prozess umfasst zwei Hauptschritte bei der Indizierung und Suche:

• IVF-Schicht: Vektoren werden in nlist invertierten Listen (Clustern) geclustert. Bei der Abfrage wird nur eine Teilmenge von Clustern besucht (nprobe), um einen Kompromiss zwischen Abruf und Latenz/Durchsatz zu finden.

• PQ-Schicht: Innerhalb jedes besuchten Clusters wird jeder D-dimensionale Vektor in m Untervektoren mit der Dimension (D/m) aufgeteilt. Jeder Untervektor wird quantisiert, indem er dem nächstgelegenen Schwerpunkt in seinem Unterkodebuch zugewiesen wird. Wenn ein Unterkodebuch 256 Schwerpunkte hat, kann jeder Untervektor durch einen uint8 Code (eine ID in [0, 255]) dargestellt werden.

Die Abstandsberechnung kann dann als Summe über die Untervektoren umgeschrieben werden:

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)

Hier steht L für eine Nachschlagetabelle. Zum Zeitpunkt der Abfrage wird die Nachschlagetabelle erstellt, die den Abstand zwischen der Abfrage und jedem quantisierten Untervektor aufzeichnet. Alle nachfolgenden Abstandsberechnungen werden in Tabellennachschlageoperationen mit anschließender Summierung umgewandelt.

Wenn zum Beispiel bei 128-dimensionalen Vektoren, die in 32 Untervektoren von je 4 Dimensionen aufgeteilt sind, jeder Untervektor durch eine uint8 ID kodiert wird, sinken die Speicherkosten pro Vektor von (128 x 4) Byte auf (32 x 1) Byte - eine Reduzierung um 1/16.

ScaNN-Optimierungen auf der Grundlage von IVFPQ

Zusammenfassend lässt sich sagen, dass ScaNN IVFPQ in zweierlei Hinsicht verbessert:

1. Quantisierung: ScaNN schlägt ein Ziel vor, das über das einfache Ersetzen jedes Untervektors durch den nächstgelegenen k-means-Schwerpunkt hinausgeht (d. h. Minimierung des Rekonstruktionsfehlers).

2. Effizienz des Nachschlagens: ScaNN beschleunigt die LUT-basierte Suche, die oft speicherabhängig ist, über einen SIMD-freundlichen FastScan-Pfad.

Quantisierungsverlust unter Berücksichtigung des Ergebnisses

Da die Analyse auf der IP-Metrik basiert, wirkt sich nach der Zerlegung des Quantisierungsfehlers in parallele und senkrechte Komponenten durch ScaNN nur die parallele Komponente auf das Ergebnis aus, so dass ein größerer Strafterm angewendet werden sollte. Folglich kann die Verlustfunktion wie folgt umgeschrieben werden:

$$\begin{array}{r}{\displaystyle \ell ({\mathrm{xi}}_{},{\mathrm{x~i}}_{},w)}\end{array}$$$$∥2\begin{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}(w,\Vert x\end{array}$$i$$\begin{array}{l}\Vert )\Vert r\end{array}$$⊥ $$\begin{array}{l}(x\end{array}$$i,

Die folgende Abbildung zeigt ein zweidimensionales Beispiel, das veranschaulicht, dass der durch die parallele Komponente verursachte Fehler größer ist und zu falschen Ergebnissen bei der nächsten Nachbarschaft führen kann, so dass eine strengere Strafe gerechtfertigt ist.

Die linke Abbildung zeigt eine schlechte Quantisierung, da der parallele Offset das Endergebnis beeinflusst, während die rechte Abbildung eine bessere Quantisierung zeigt.

4-Bit-PQ-FastScan

Schauen wir uns zunächst den PQ-Berechnungsprozess an: Während der Abfrage werden die Abstände zwischen den Zentren der Abfrage und der Untervektoren vorberechnet, um eine Nachschlagetabelle zu erstellen. Die Abstandsberechnung erfolgt dann durch Tabellenabfragen, um Segmentabstände zu erhalten und diese zu summieren.

Die häufigen Speicherzugriffe werden jedoch immer noch zu einem Leistungsengpass. Wenn die Nachschlagetabelle so klein gemacht werden kann, dass sie in Register passt, können Speicherleseoperationen in effiziente CPU-SIMD-Anweisungen umgewandelt werden.

Zunächst wird jeder Untervektor in 16 Klassen geclustert, so dass ein 4-Bit-Wert ein Clusterzentrum darstellen kann - daher auch der Name "4-Bit-PQ". Dann werden die Abstände, die normalerweise als Fließkommazahlen dargestellt werden, mithilfe der Skalarquantisierung (SQ) in uint8 umgewandelt. Auf diese Weise kann die Lookup-Tabelle für einen Untervektor in einem Register mit 16 × 8 = 128 Bits gespeichert werden.

Betrachten wir abschließend die Registerspeicheranordnung (am Beispiel des AVX2-Befehlssatzes): Die Untervektoren von 32 Vektoren werden zusammen mit der Lookup-Tabelle in einem 128-Bit-Register untergebracht. Die "Lookup"-Operation kann dann mit einem einzigen SIMD-Shuffle-CPU-Befehl effizient abgeschlossen werden.

Register-Layout

SIMD-Shuffle für Lookup

Hier eine interessante Beobachtung: Das ScaNN-Papier konzentriert sich ausschließlich auf die erste Optimierung, was vernünftig ist, da es als ein Algorithmus-Papier mit Schwerpunkt auf mathematischen Ableitungen betrachtet werden kann. Die experimentellen Ergebnisse, die in dem Papier vorgestellt werden, sind jedoch bemerkenswert beeindruckend.

Die experimentellen Ergebnisse, die in der ScaNN-Studie vorgestellt werden.

Intuitiv sollte die Optimierung des Verlusts allein keine so dramatischen Auswirkungen haben. In einem anderen Blog wurde ebenfalls darauf hingewiesen, dass der 4-Bit-PQ-FastScan-Anteil den Unterschied ausmacht.

Experimentelle Ergebnisse

Mit dem Vektordatenbank-Benchmark-Tool VectorDBBench haben wir einen einfachen Test durchgeführt. Der Leistungsvorteil von ScaNN gegenüber den traditionellen IVFFLAT und IVF_PQ ist ganz offensichtlich. Nach der Integration in Milvus kann QPS auf dem Cohere1M-Datensatz bei gleicher Recall-Rate das Fünffache von IVFFLAT und das Sechsfache von IVF_PQ erreichen.

Der QPS ist jedoch etwas niedriger als der von graphenbasierten Indizes wie HNSW, so dass er nicht die erste Wahl für Anwendungsfälle mit hohem QPS ist. Für Szenarien mit geringerem Recall ist er jedoch akzeptabel (z. B. in einigen Empfehlungssystemen). Die Verwendung von ScaNN ohne das Laden von Rohdaten kann beeindruckende QPS mit einem extrem geringen Speicherbedarf (1/16 der Originaldaten) erreichen, was ihn zu einer ausgezeichneten Indexwahl macht.

Index_Typ	Fall	QPS	Latenz(p99)	Abruf	Speicher
IVFFLAT	Leistung1M	266	0.0173s	0.9544	3G
HNSW	Leistung1M	1885	0.0054s	0.9438	3.24G
IVF_PQ	Leistung1M	208	0.0292s	0.928	0.375G
ScaNN（mit_Rohdaten: true）	Leistung1M	1215	0.0069s	0.9389	3.186G
ScaNN（mit_Rohdaten: false）	Leistung1M	1265	0.0071s	0.7066	0.186G

Schlussfolgerung

ScaNN baut auf dem vertrauten IVFPQ-Framework auf, erweitert es aber durch tiefgreifende Entwicklungsarbeit sowohl bei der Quantisierung als auch bei der Beschleunigung von Low-Level-Lookups erheblich. Durch die Anpassung des Quantisierungsziels an die Qualität des Rankings und die Beseitigung von Speicherengpässen in der inneren Schleife kombiniert ScaNN eine Score-bewusste Quantisierung mit einem 4-Bit-PQ-FastScan-Pfad, der einen traditionell speichergebundenen Prozess in eine effiziente, SIMD-freundliche Berechnung verwandelt.

In der Praxis bedeutet dies, dass ScaNN eine klare und gut definierte Nische hat. Es ist nicht dazu gedacht, graphbasierte Indizes wie HNSW in Umgebungen mit hohem Abruf zu ersetzen. Stattdessen liefert ScaNN für abrufunempfindliche Arbeitslasten mit knappen Speicherbudgets einen hohen Durchsatz bei sehr geringem Platzbedarf. In unseren Experimenten erreichte ScaNN nach der Integration in Milvus VectorDB etwa das Fünffache der QPS von IVFFLAT auf dem Cohere1M-Datensatz, was es zu einer guten Wahl für ANN-Abrufe mit hohem Durchsatz und geringer Latenz macht, bei denen Komprimierung und Effizienz wichtiger sind als ein perfekter Abruf.

Wenn Sie daran interessiert sind, ScaNN weiter zu erforschen oder die Indexauswahl in realen Systemen zu diskutieren, treten Sie unserem Slack Channel bei, um mit unseren Ingenieuren und anderen KI-Ingenieuren in der Community zu chatten. Sie können auch eine 20-minütige Einzelsitzung buchen, um Einblicke, Anleitung und Antworten auf Ihre Fragen über die Milvus-Sprechstunde zu erhalten.