DiskANN Explorer: Vektorsuche im Milliardenbereich aus SSD

DiskANN Es wird eine winzige, mit „PQ “-Komprimierung komprimierte Kopie jedes Vektors unter RAM sowie die vollständigen Vektoren und der Graph unter SSD gespeichert. Die Suche durchläuft den Graphen mit kostengünstigen „ RAM “-Vergleichen und ordnet anschließend die besten Kandidaten mit einer Handvoll aufwendiger Festplattenzugriffe neu.

Warum es „ DiskANN “ gibt: die Speicherwand

RAMPQ Codes (32 B/vec)3.2 GB

DiskVollständige Vektoren + Graph (3072 B/vec)307.2 GB

100M Vektoren × 768 -DimensionenDisk / RAM ≈ 96×

Ein einzelner Standard- SSD -Speicher reicht für die Festplattenseite problemlos aus. Die „ RAM “-Seite passt in jeden Laptop. Ohne den „ PQ “-Trick bräuchte man einen Server mit Hunderten von GB „ RAM “, um den Datensatz überhaupt laden zu können.

Graphgrad

Kandidatenpool

Neubewertung5

Lesevorgänge auf der Festplatte

Geschwindigkeit420ms

Pro Schritt

PQ-Vergleich (RAM) im Kandidatenpool Disk-Re-Rank top-K Ergebnis

Aktueller Schritt

30 / 30

Suche abgeschlossen. Top-3: [1, 28, 27].

Bisherige Kosten

RAM PQ vergleicht20≈ 20 µs

SSD liest5≈ 500 µs

Gesamtlatenz0.52 ms

Modelliert mit PQ ≈ 1 µs, SSD ≈ 100 µs. Reelle Zahlen sind hardwareabhängig.

Suchstatistiken

Besucht

20 / 36

Neu geordnet

Top-3

[1, 28, 27]

So funktioniert „ DiskANN “

Erstellen Sie den „ Vamana “-Graphen: einen einlagigen kNN-Graphen (Grad R), der für sequenzielles Festplattenlayout optimiert ist. Keine Hierarchie – nur ein großer Graph.
Quantisierung und Speicheraufteilung: Jeder Vektor erhält einen winzigen „ PQ “-Code (z. B. 32 Byte). „ PQ “-Codes befinden sich unter RAM. Vollständige Vektoren und Graphkanten befinden sich unter SSD.
Beam-Walk mit „ PQ “-Abständen: Ausgehend von einem festen Einstiegspunkt (dem Medoid) wird ein Kandidatenpool der Größe L beibehalten. Der beste Kandidat wird ausgewählt, seine Nachbarn werden erweitert, und die Abstände werden ausschließlich anhand der Codes „in-RAM “ und „ PQ “ geschätzt. Während des Beam-Walks findet kein Festplatten-I/O statt.
Führen Sie eine Neuordnung der Finalisten auf der Festplatte durch: Die Abstände der besten Einträge im Kandidatenpool wurden mit „ PQ “ approximiert. Lesen Sie deren vollständige Vektoren von der Festplatte ein und berechnen Sie die exakten Abstände neu, um die Rangfolge zu korrigieren.
Rückgabe top-K. Gesamt-Disk-I/O = eine geringe Anzahl zufälliger Lesevorgänge, in der Regel weniger als 20.

Der Handel

Warum es skalierbar ist: „ RAM “ enthält ausschließlich komprimierte Codes. Ein Datensatz mit 1 Milliarde Vektoren und 32-Byte- PQ en benötigt ca. 32 GB RAM – das passt auf eine einzige Workstation.
Warum es langsamer ist als „ HNSW “: SSD Zufällige Lesezugriffe sind ~100× langsamer als RAM. Selbst bei nur ~10 Lesezugriffen wird die Abfragelatenz maßgeblich durch die Festplatte bestimmt.
Warum es bei der Recall-Rate immer noch besser abschneidet als „ IVF_PQ “: Der Schritt der Neureihung behebt Quantisierungsfehler, die reine „ PQ “-basierte Methoden nicht beheben können.

Das mentale Modell: „ PQ “ ist der kostengünstige Test „Ist diese Umgebung vielversprechend?“. Lesevorgänge auf der Festplatte sind die aufwendige Überprüfung „Lass mich das tatsächlich verifizieren“. „ DiskANN “ erledigt den Großteil seiner Arbeit mit dem kostengünstigen Test.

Was ist „ DiskANN “?

DiskANN ist ein graphbasierter Index für die ungefähre Suche nach dem nächsten Nachbarn, der für Datensätze entwickelt wurde, die nicht in „ RAM “ passen. Er baut einen einlagigen „Vamana “-Graphen auf, der für effizienten Festplattenzugriff ausgelegt ist, hält für jeden Vektor im Speicher einen winzigen, produktquantisierten (PQ) Code bereit und speichert die Vektoren in voller Präzision sowie die Graphenkanten auf SSD. Bei der Suche wird der Graph mithilfe kostengünstiger In-RAM - PQ -Vergleiche durchlaufen, und auf die Festplatte wird nur zugegriffen, um eine Handvoll Finalisten neu zu ordnen.

In „ Milvus “ ermöglicht „ DiskANN “ die Option für einen Index auf Festplatte: Sammlungen im Milliardenbereich lassen sich auf Rechnern mit Dutzenden – nicht Hunderten – von Gigabyte „ RAM “ durchsuchen, während der Schritt der Neuordnung auf Festplatte den Recall nahe an den von In-Memory-Graphenindizes hält.

Was die Regler steuern

R (Graphgrad, Erstellungszeit): Die maximale Anzahl von Kanten pro Knoten im „ Vamana “-Graph. Ein höherer R-Wert sorgt für bessere Konnektivität und einen besseren Recall, geht jedoch mit einem größeren Graph auf der Festplatte und langsameren Erstellungsvorgängen einher.
L / „ search_list “ (Abfragezeit): Der während der Beam-Suche gepflegte Kandidatenpool – der wichtigste Regler für Recall und Latenz, vergleichbar mit „ ef “ in „ HNSW “. Er muss mindestens so groß sein wie Ihr „ top-K “.
„Re-rank budget“: Wie viele Finalisten erhalten ihre vollständigen Vektoren von „ SSD “, um eine exakte Bewertung zu erhalten. Jeder Abruf ist ein zufälliger Lesevorgang auf der Festplatte, daher liegt hier die Latenz der Abfrage – und hier werden auch die Approximationsfehler von „ PQ “ korrigiert.

DiskANN vs HNSW vs IVF

Wählen Sie „ DiskANN “, wenn der Datensatz (oder der Speicherbedarf) die Kapazität von „ RAM “ übersteigt: Es bedient Abfragen mit hoher Recall-Rate mit einem Bruchteil des Speichers, im Gegenzug für eine Latenz im Millisekundenbereich, die durch Lesevorgänge von „ SSD “ dominiert wird. Wenn alles problemlos in den Speicher passt, liefert „ HNSW “ schnellere Ergebnisse. Wenn Sie schnelle Indexerstellungen oder moderate Speichereinsparungen ohne Einbeziehung der Festplatte benötigen, bieten die Varianten von „ IVF “ einen Mittelweg.

Häufig gestellte Fragen

Wann sollte ich „ DiskANN “ anstelle von „ HNSW “ verwenden?

Wenn Ihre Vektoren nicht mehr in „ RAM “ passen – oder der „ RAM “, der sie aufnehmen soll, mehr kostet, als Sie bereit sind zu zahlen. Eine Milliarde 768-dimensionale Float-Vektoren benötigen ~3 TB im Arbeitsspeicher für „ HNSW “, aber nur einige Dutzend GB für „ RAM “ sowie ein „ SSD “ mit „ DiskANN “. Wenn der Datensatz problemlos in den Arbeitsspeicher passt, bleibt „ HNSW “ die Wahl mit der geringeren Latenz.

Welche Hardware benötigt „ DiskANN “?

Ein schneller „ NVMe “ ( SSD ) ist die zentrale Anforderung, da die Abfragelatenz durch eine Handvoll zufälliger Festplattenzugriffe (jeweils ~100 µs) dominiert wird. Die Anforderungen an den „ RAM “ sind bescheiden: in etwa die „ PQ “-Codes (z. B. 32–64 Bytes pro Vektor) plus Arbeitspuffer.

Ist „ DiskANN “ langsamer als In-Memory-Indizes wie „ HNSW “?

Pro Abfrage ja – typischerweise im niedrigen einstelligen Millisekundenbereich im Vergleich zu unter einer Millisekunde bei der „In-Memory“- HNSW, da jede Neuordnung auf Festplatte etwa 100-mal langsamer ist als ein Zugriff über „ RAM “. Der Kompromiss liegt bei den Kosten: „ DiskANN “ verarbeitet denselben Datensatz mit einer um eine Größenordnung geringeren „ RAM “, während der Recall bei über 90–95 % bleibt.

Wie sorgt „ DiskANN “ trotz „ PQ “-Komprimierung für einen hohen Recall?

PQ Codes dienen ausschließlich zur Steuerung des Graphdurchlaufs, nicht zur Ermittlung endgültiger Bewertungen. Vor der Rückgabe der Ergebnisse liest „ DiskANN “ die Vektoren mit voller Genauigkeit der besten Kandidaten aus „ SSD “ ein und ordnet sie exakt neu, wobei der Quantisierungsfehler korrigiert wird, den reine, auf „ PQ “ basierende Indizes wie „ IVF_PQ “ nicht beheben können.

Mehr dazu: Lesen Sie die Dokumentation zu „DiskANN “ für die Systemvoraussetzungen oder sehen Sie sich „Index Explained“ an, um den vollständigen Leitfaden zu erhalten.