DISKANN

In großen Szenarien, in denen Datensätze Milliarden oder sogar Billionen von Vektoren umfassen können, können standardmäßige In-Memory-Indizierungsmethoden (z. B. HNSW, IVF_FLAT) aufgrund von Speicherbeschränkungen oft nicht Schritt halten. DISKANN bietet einen plattenbasierten Ansatz, der diese Herausforderungen angeht, indem er eine hohe Suchgenauigkeit und -geschwindigkeit beibehält, wenn die Größe des Datensatzes den verfügbaren Arbeitsspeicher übersteigt.

Überblick

DISKANN kombiniert zwei Schlüsseltechniken für eine effiziente Vektorsuche:

• Vamana Graph - Ein festplattenbasierter, graphbasierter Index, der Datenpunkte (oder Vektoren) für eine effiziente Navigation während der Suche miteinander verbindet.

• Produktquantisierung (PQ) - Eine speicherinterne Komprimierungsmethode, die die Größe von Vektoren reduziert und eine schnelle, ungefähre Abstandsberechnung zwischen Vektoren ermöglicht.

Index-Konstruktion

Vamana-Graph

Der Vamana-Graph ist das Herzstück der festplattenbasierten Strategie von DISKANN. Er kann sehr große Datensätze verarbeiten, da er während und nach der Erstellung nicht vollständig im Speicher liegen muss.

Die folgende Abbildung zeigt, wie ein Vamana-Graph aufgebaut ist.

Diskann

1. Anfängliche zufällige Verbindungen: Jeder Datenpunkt (Vektor) wird als ein Knoten im Graphen dargestellt. Diese Knoten werden anfangs zufällig miteinander verbunden und bilden ein dichtes Netz. Normalerweise hat ein Knoten zu Beginn etwa 500 Kanten (oder Verbindungen), um eine breite Konnektivität zu erreichen.

2. Verfeinerung für mehr Effizienz: Der anfängliche Zufallsgraph wird einem Optimierungsprozess unterzogen, um ihn für die Suche effizienter zu machen. Dies umfasst zwei wichtige Schritte:

   • Ausschneiden überflüssiger Kanten: Der Algorithmus verwirft unnötige Verbindungen auf der Grundlage der Entfernungen zwischen den Knoten. Bei diesem Schritt werden Kanten höherer Qualität bevorzugt.

     Der Parameter max_degree schränkt die maximale Anzahl der Kanten pro Knoten ein. Eine höhere max_degree führt zu einem dichteren Graphen, der potenziell mehr relevante Nachbarn findet (höherer Recall), aber auch den Speicherverbrauch und die Suchzeit erhöht.

   • Hinzufügen strategischer Abkürzungen: Vamana führt weitreichende Kanten ein, die Datenpunkte verbinden, die im Vektorraum weit voneinander entfernt sind. Diese Abkürzungen ermöglichen es der Suche, schnell durch den Graphen zu springen, Zwischenknoten zu umgehen und die Navigation erheblich zu beschleunigen.

     Der Parameter search_list_size bestimmt die Breite des Graphenverfeinerungsprozesses. Eine höhere search_list_size erweitert die Suche nach Nachbarn während der Konstruktion und kann die endgültige Genauigkeit verbessern, erhöht aber die Zeit für die Indexerstellung.

Weitere Informationen zur Parametereinstellung finden Sie unter DISKANN-Parameter.

PQ

DISKANN verwendet PQ, um hochdimensionale Vektoren in kleinere Darstellungen(PQ-Codes) zu komprimieren, die im Speicher für schnelle Näherungsabstandsberechnungen gespeichert werden.

Der Parameter pq_code_budget_gb_ratio verwaltet den Speicherbedarf für die Speicherung dieser PQ-Codes. Er stellt ein Verhältnis zwischen der Gesamtgröße der Vektoren (in Gigabyte) und dem für die Speicherung der PQ-Codes zugewiesenen Platz dar. Sie können das tatsächliche PQ-Code-Budget (in Gigabyte) mit dieser Formel berechnen:

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

wobei:

• vec_field_size_gb die Gesamtgröße der Vektoren (in Gigabyte) ist.

• pq_code_budget_gb_ratio ist ein benutzerdefiniertes Verhältnis, das den für PQ-Codes reservierten Anteil der Gesamtdatengröße angibt. Mit diesem Parameter kann ein Kompromiss zwischen Suchgenauigkeit und Speicherressourcen gefunden werden. Weitere Informationen zur Parametereinstellung finden Sie unter DISKANN-Konfigurationen.

Technische Einzelheiten über die zugrunde liegende PQ-Methode finden Sie unter IVF_PQ.

Suchprozess

Sobald der Index (der Vamana-Graph auf der Festplatte und die PQ-Codes im Speicher) aufgebaut ist, führt DISKANN die ANN-Suche wie folgt durch:

Diskann 2

1. Abfrage und Einstiegspunkt: Ein Abfragevektor wird bereitgestellt, um seine nächsten Nachbarn zu finden. DISKANN beginnt mit einem ausgewählten Einstiegspunkt im Vamana-Graphen, häufig ein Knoten in der Nähe des globalen Schwerpunkts des Datensatzes. Der globale Schwerpunkt stellt den Durchschnitt aller Vektoren dar, was dazu beiträgt, die Traversaldistanz durch den Graphen zu minimieren, um die gewünschten Nachbarn zu finden.

2. Erkundung der Nachbarschaft: Der Algorithmus sammelt potenzielle Nachbarschaftskandidaten (rote Kreise in der Abbildung) an den Kanten des aktuellen Knotens und nutzt speicherinterne PQ-Codes, um die Abstände zwischen diesen Kandidaten und dem Abfragevektor zu approximieren. Diese potenziellen Nachbarschaftskandidaten sind die Knoten, die über Kanten im Vamana-Graphen direkt mit dem ausgewählten Einstiegspunkt verbunden sind.

3. Auswahl von Knoten für eine genaue Abstandsberechnung: Aus den Näherungsergebnissen wird eine Teilmenge der vielversprechendsten Nachbarn (grüne Kreise in der Abbildung) für eine genaue Abstandsberechnung anhand ihrer ursprünglichen, nicht komprimierten Vektoren ausgewählt. Dazu müssen die Daten von der Festplatte gelesen werden, was sehr zeitaufwändig sein kann. DISKANN verwendet zwei Parameter, um dieses empfindliche Gleichgewicht zwischen Genauigkeit und Geschwindigkeit zu steuern:

   • beam_width_ratio: Ein Verhältnis, das die Breite der Suche steuert und bestimmt, wie viele Nachbarschaftskandidaten parallel ausgewählt werden, um ihre Nachbarn zu untersuchen. Ein größeres beam_width_ratio führt zu einer breiteren Suche, was zu einer höheren Genauigkeit führen kann, aber auch die Rechenkosten und die Festplatten-E/A erhöht. Die Breite des Suchstrahls, d. h. die Anzahl der ausgewählten Knoten, wird anhand der folgenden Formel bestimmt: Beam width = Number of CPU cores * beam_width_ratio.

   • search_cache_budget_gb_ratio: Der Anteil des Speichers, der für die Zwischenspeicherung häufig abgerufener Festplattendaten zugewiesen wird. Diese Zwischenspeicherung trägt dazu bei, die Festplatten-E/A zu minimieren, wodurch wiederholte Suchvorgänge schneller durchgeführt werden können, da sich die Daten bereits im Speicher befinden.

   Weitere Informationen zur Parametereinstellung finden Sie unter DISKANN-Konfigurationen.

4. Iterative Erkundung: Die Suche verfeinert iterativ die Menge der Kandidaten, indem sie wiederholt ungefähre Bewertungen (unter Verwendung von PQ) durchführt, gefolgt von präzisen Prüfungen (unter Verwendung der Originalvektoren von der Festplatte), bis eine ausreichende Anzahl von Nachbarn gefunden wurde.

Aktivieren von DISKANN in Milvus

Standardmäßig ist DISKANN in Milvus deaktiviert, um der Geschwindigkeit von In-Memory-Indizes für Datensätze, die bequem in den RAM passen, den Vorrang zu geben. Wenn Sie jedoch mit großen Datensätzen arbeiten oder die Skalierbarkeit von DISKANN und die SSD-Optimierung nutzen möchten, können Sie DISKANN problemlos aktivieren.

Hier erfahren Sie, wie Sie DISKANN in Milvus aktivieren können:

1. Aktualisieren Sie die Milvus-Konfigurationsdatei

   1. Suchen Sie Ihre Milvus-Konfigurationsdatei. (Einzelheiten zum Auffinden dieser Datei finden Sie in der Milvus-Dokumentation zur Konfiguration).

   2. Suchen Sie den Parameter queryNode.enableDisk und setzen Sie seinen Wert auf true:

       queryNode:
           enableDisk: true # Enables query nodes to load and search using the on-disk index
      

2. Optimieren Sie den Speicher für DISKANN

Um die beste Leistung mit DISKANN zu gewährleisten, wird empfohlen, Ihre Milvus-Daten auf einer schnellen NVMe-SSD zu speichern. Im Folgenden wird beschrieben, wie Sie dies sowohl für Milvus Standalone als auch für Cluster-Einsätze tun können:

• Milvus Standalone

  • Mounten Sie das Milvus-Datenverzeichnis auf eine NVMe-SSD innerhalb des Milvus-Containers. Sie können dies in der Datei docker-compose.yml oder mit anderen Container-Management-Tools tun.

  • Wenn Ihre NVMe-SSD beispielsweise unter /mnt/nvme eingehängt ist, aktualisieren Sie den Abschnitt volumesin der Datei docker-compose.yml wie folgt:

   volumes:
        - /mnt/nvme/volumes/milvus:/var/lib/milvus
  

• Milvus-Cluster

  • Hängen Sie das Milvus-Datenverzeichnis sowohl im QueryNode- als auch im IndexNode-Container auf eine NVMe-SSD ein. Sie können dies über Ihre Container-Orchestrierung erreichen.

  • Durch das Mounten der Daten auf einer NVMe-SSD in beiden Knotentypen stellen Sie schnelle Lese- und Schreibgeschwindigkeiten für Such- und Indizierungsvorgänge sicher.

Sobald Sie diese Änderungen vorgenommen haben, starten Sie Ihre Milvus-Instanz neu, damit die Einstellungen wirksam werden. Jetzt nutzt Milvus die Fähigkeiten von DISKANN, um große Datensätze zu verarbeiten und eine effiziente und skalierbare Vektorsuche zu ermöglichen.

DISKANN konfigurieren

DISKANN-bezogene Parameter können nur über Ihre Milvus-Konfigurationsdatei (milvus.yaml) konfiguriert werden:

# milvus.yaml
common:
  DiskIndex:
    MaxDegree: 56  # Maximum degree of the Vamana graph
    SearchListSize: 100  # Size of the candidate list during building graph
    PQCodeBudgetGBRatio: 0.125  # Size limit on the PQ code (compared with raw data)
    SearchCacheBudgetGBRatio: 0.1 # Ratio of cached node numbers to raw data
    BeamWidthRatio: 4 # Ratio between the maximum number of IO requests per search iteration and CPU number

Einzelheiten zu den Parameterbeschreibungen finden Sie unter DISKANN params.

DISKANN-Parameter

Die Feinabstimmung der DISKANN-Parameter ermöglicht es Ihnen, das Verhalten von DISKANN an Ihren spezifischen Datensatz und Ihre Suchlast anzupassen und das richtige Gleichgewicht zwischen Geschwindigkeit, Genauigkeit und Speicherverbrauch zu finden.

Indexaufbau-Parameter

Diese Parameter beeinflussen, wie der DISKANN-Index aufgebaut wird. Eine Anpassung dieser Parameter kann die Indexgröße, die Erstellungszeit und die Suchqualität beeinflussen.

	Parameter	Beschreibung	Wertebereich	Tuning-Vorschlag
Vamana	MaxDegree	Steuert die maximale Anzahl von Verbindungen (Kanten), die jeder Datenpunkt im Vamana-Diagramm haben kann.	Typ: Integer Bereich: [1, 512] Standardwert: 56	Höhere Werte führen zu dichteren Graphen, was die Wiederauffindbarkeit erhöht (es werden mehr relevante Ergebnisse gefunden), aber auch die Speichernutzung und die Erstellungszeit erhöht. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs zu wählen: [10, 100].
	SearchListSize	Während der Indexerstellung definiert dieser Parameter die Größe des Kandidatenpools, der bei der Suche nach den nächsten Nachbarn für jeden Knoten verwendet wird. Für jeden Knoten, der dem Graphen hinzugefügt wird, führt der Algorithmus eine Liste mit den search_list_size besten bisher gefundenen Kandidaten. Die Suche nach Nachbarn wird beendet, wenn diese Liste nicht mehr verbessert werden kann. Aus diesem endgültigen Kandidatenpool werden die besten max_degree Knoten ausgewählt, um die endgültigen Kanten zu bilden.	Typ: Integer Bereich: [1, int_max] Standardwert: 100	Ein größerer search_list_size erhöht die Wahrscheinlichkeit, die wahren nächsten Nachbarn für jeden Knoten zu finden, was zu einem qualitativ hochwertigeren Graphen und einer besseren Suchleistung (Recall) führen kann. Dies hat jedoch den Nachteil, dass die Indexerstellung deutlich länger dauert. Er sollte immer auf einen Wert größer oder gleich max_degree gesetzt werden.
	SearchCacheBudgetGBRatio	Steuert die Menge an Speicher, die für die Zwischenspeicherung häufig aufgerufener Teile des Graphen während des Indexaufbaus zugewiesen wird.	Typ: Float Bereich: [0.0, 0.3) Standardwert: 0.10	Ein höherer Wert weist mehr Speicher für die Zwischenspeicherung zu, was die Festplatten-E/A erheblich reduziert, aber mehr Systemspeicher verbraucht. Ein niedrigerer Wert verwendet weniger Speicher für die Zwischenspeicherung und erhöht möglicherweise den Bedarf an Festplattenzugriffen. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs festzulegen: [0.0, 0.3).
PQ	PQCodeBudgetGBRatio	Steuert die Größe der PQ-Codes (komprimierte Darstellungen von Datenpunkten) im Vergleich zur Größe der unkomprimierten Daten.	Typ: Float Bereich: (0.0, 0.25] Standardwert: 0.125	Ein höheres Verhältnis führt zu genaueren Suchergebnissen, da ein größerer Anteil des Speichers für PQ-Codes reserviert wird und somit mehr Informationen über die ursprünglichen Vektoren gespeichert werden. Ein geringeres Verhältnis reduziert den Speicherbedarf, kann aber zu Lasten der Genauigkeit gehen, da kleinere PQ-Codes weniger Informationen speichern. Dieser Ansatz eignet sich für Szenarien, in denen Speicherbeschränkungen ein Problem darstellen, und ermöglicht möglicherweise die Indizierung größerer Datensätze. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs festzulegen: (0,0625, 0,25)

Indexspezifische Suchparameter

Diese Parameter beeinflussen, wie DISKANN die Suche durchführt. Eine Anpassung dieser Parameter kann sich auf die Suchgeschwindigkeit, die Latenzzeit und die Ressourcennutzung auswirken.

	Parameter	Beschreibung	Wertebereich	Tuning-Vorschlag
Vamana	BeamWidthRatio	Steuert den Grad der Parallelität während der Suche, indem die maximale Anzahl der parallelen Festplatten-E/A-Anforderungen im Verhältnis zur Anzahl der verfügbaren CPU-Kerne festgelegt wird.	Typ: Float Bereich: [1, max(128 / CPU-Anzahl, 16)] Standardwert: 4.0	Höhere Werte erhöhen die Parallelität, was die Suche auf Systemen mit leistungsstarken CPUs und SSDs beschleunigen kann. Ein zu hoher Wert kann jedoch zu übermäßiger Ressourcenkonkurrenz führen. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs zu wählen: [1.0, 4.0].
	search_list	Während eines Suchvorgangs bestimmt dieser Parameter die Größe des Kandidatenpools, den der Algorithmus beim Durchlaufen des Graphen beibehält. Ein größerer Wert erhöht die Wahrscheinlichkeit, dass die wahren nächsten Nachbarn gefunden werden (höhere Trefferquote), erhöht aber auch die Suchlatenz.	Typ: Integer Bereich: [1, int_max] Standardwert: 100	Um ein gutes Gleichgewicht zwischen Leistung und Genauigkeit zu erreichen, wird empfohlen, diesen Wert gleich oder etwas größer als die Anzahl der abzurufenden Ergebnisse (top_k) zu setzen.