Beschleunigung der Zusammenführung von HNSW-Diagrammen

Von der Vektorsuche bis hin zu leistungsstarken REST-APIs bietet Elasticsearch Entwicklern das umfangreichste Such-Toolkit. Sehen Sie sich die Beispiel-Notebooks auf GitHub an, um etwas Neues testen. Sie können auch noch heute Ihre kostenlose Testversion starten oder Elasticsearch lokal ausführen.

In der Vergangenheit haben wir einige der Herausforderungen erörtert , die mit der Suche in mehreren HNSW-Graphen einhergehen, und wie wir diese bewältigen konnten. Damals deuteten wir einige weitere Verbesserungen an, die wir geplant hatten. Dieser Beitrag ist der Höhepunkt dieser Arbeit.

Sie fragen sich vielleicht, warum Sie überhaupt mehrere Diagramme verwenden? Dies ist ein Nebeneffekt einer Architekturentscheidung in Lucene: unveränderliche Segmente. Wie bei den meisten architektonischen Entscheidungen gibt es Vor- und Nachteile. Beispielsweise haben wir vor Kurzem Serverless Elasticsearch allgemein zugänglich gemacht. In diesem Zusammenhang haben wir durch unveränderliche Segmente erhebliche Vorteile erzielt, darunter eine effiziente Indexreplikation und die Möglichkeit, die Index- und Abfrageberechnung zu entkoppeln und unabhängig voneinander automatisch zu skalieren. Bei der Vektorquantisierung bieten uns Segmentzusammenführungen die Möglichkeit, Parameter zu aktualisieren, um sie an die Dateneigenschaften anzupassen. In diesem Sinne sind wir der Meinung, dass die Möglichkeit, Datenmerkmale zu messen und Indexierungsentscheidungen zu überprüfen, noch weitere Vorteile mit sich bringt.

In diesem Beitrag besprechen wir die Arbeit, die wir geleistet haben, um den Aufwand für die Erstellung mehrerer HNSW-Diagramme deutlich zu reduzieren und insbesondere die Kosten für das Zusammenführen von Diagrammen zu senken.

Hintergrund

Um eine überschaubare Anzahl von Segmenten beizubehalten, prüft Lucene regelmäßig, ob Segmente zusammengeführt werden sollen. Dies läuft darauf hinaus, zu prüfen, ob die aktuelle Segmentanzahl eine Zielsegmentanzahl überschreitet, die durch die Basissegmentgröße und die Zusammenführungsrichtlinie bestimmt wird. Wenn die Anzahl überschritten wird, führt Lucene Segmentgruppen zusammen, während die Einschränkung verletzt wird. Dieser Vorgang wurde an anderer Stelle ausführlich beschrieben.

Lucene entscheidet sich für die Zusammenführung ähnlich großer Segmente, da dadurch ein logarithmisches Wachstum der Schreibverstärkung erreicht wird. Im Fall eines Vektorindex ist die Schreibverstärkung die Anzahl der Male, die ein Vektor in ein Diagramm eingefügt wird. Lucene versucht, Segmente in Gruppen von etwa 10 zusammenzuführen. Folglich werden Vektoren in einen Graphen eingefügt, der ungefähr $1+\frac{9}{10}\log_{10}\left(\frac{n}{n_0}\right)$beträgt. mal, wobei $n$ die Anzahl der Indexvektoren und $n_0$ die erwartete Anzahl der Basissegmentvektoren ist. Aufgrund des logarithmischen Wachstums liegt die Schreibverstärkung selbst bei großen Indizes im einstelligen Bereich. Die Gesamtzeit, die zum Zusammenführen von Graphen benötigt wird, ist jedoch linear proportional zur Schreibverstärkung.

Beim Zusammenführen von HNSW-Graphen nehmen wir bereits eine kleine Optimierung vor: Wir behalten den Graphen für das größte Segment bei und fügen Vektoren aus den anderen Segmenten darin ein. Dies ist der Grund für den oben genannten 9/10-Faktor. Im Folgenden zeigen wir, wie wir durch die Verwendung von Informationen aus allen Diagrammen, die wir zusammenführen, deutlich bessere Ergebnisse erzielen können.

HNSW-Graphzusammenführung

Bisher haben wir den größten Graphen beibehalten und Vektoren aus den anderen eingefügt, wobei wir die Graphen, die sie enthalten, ignoriert haben. Die zentrale Erkenntnis, die wir im Folgenden nutzen, ist, dass jeder HNSW-Graph, den wir verwerfen, wichtige Näheinformationen über die darin enthaltenen Vektoren enthält. Wir möchten diese Informationen nutzen, um das Einfügen zumindest einiger Vektoren zu beschleunigen.

Wir konzentrieren uns auf das Problem des Einfügens eines kleineren Graphen $G_s=(V_s,E_s)$ in einen größeren Graphen $G_l=(V_l,E_l)$, da dies eine atomare Operation ist, die wir zum Erstellen beliebiger Zusammenführungsrichtlinien verwenden können.

Die Strategie besteht darin, eine Teilmenge von Eckpunkten von $J\subset V_s$ zu finden, die in den großen Graphen eingefügt werden soll. Wir verwenden dann die Konnektivität dieser Knoten im kleinen Graphen, um das Einfügen der verbleibenden Knoten $V_s \setminus J$ zu beschleunigen. Im Folgenden verwenden wir $N_s(u)$ und $N_l(u),$ um die Nachbarn eines Knotens $u$ im kleinen bzw. großen Graphen zu bezeichnen. Schematisch ist der Ablauf wie folgt.

MERGE-HNSW

Inputs $G_s$ and $G_l$

1$\;\;$Find $J\subset V_s$ to insert into $G_l$ using COMPUTE-JOIN-SET
2$\;\;$Insert each vertex $u\in J$ into $G_l$
3$\;\;$for $u\in V_s \setminus J$ do
4$\;\;\;\;J_u\leftarrow J\cap N_s(u)$
5$\;\;\;\;E_u\leftarrow \cup_{v\in J_u} N_l(u)$
6$\;\;\;\;W\leftarrow\,$FAST-SEARCH-LAYER$(J_u, E_u)$
7$\;\;\;\;neighbors \leftarrow\,$SELECT-NEIGHBORS-HEURISTIC$(u, W)$
8$\;\;\;\;J\leftarrow J \cup \{u\}$

Wir berechnen die Menge $J$ mithilfe eines Verfahrens, das wir unten besprechen (Zeile 1). Dann fügen wir jeden Knoten in $J$ mithilfe des Standard-HNSW-Einfügeverfahrens in den großen Graphen ein (Zeile 2). Für jeden Knoten, den wir nicht eingefügt haben, finden wir seine Nachbarn, die wir eingefügt haben, und deren Nachbarn im großen Graphen (Zeilen 4 und 5). Wir verwenden ein mit diesem Set (Zeile 6) gesätes FAST-SEARCH-LAYER -Verfahren, um die Kandidaten für SELECT-NEIGHBORS-HEURISTIC aus dem HNSW- Papier (Zeile 7) zu finden. Tatsächlich ersetzen wir SEARCH-LAYER , um den Kandidatensatz in der Methode INSERT (Algorithmus 1 aus dem Dokument) zu finden, die ansonsten unverändert bleibt. Schließlich fügen wir den Scheitelpunkt hinzu, den wir gerade in $J$ eingefügt haben (Zeile 8).

Damit dies funktioniert, ist klar, dass jeder Scheitelpunkt in $V_s \setminus J$ mindestens einen Nachbarn in $J$ haben muss. Tatsächlich verlangen wir, dass für jeden Scheitelpunkt in $u\in V_s \setminus J$ $|J\cap N_s(u) |\geq k_u$ für ein gewisses $k_u<M$, die maximale Schichtkonnektivität, gilt. Wir beobachten, dass in realen HNSW-Diagrammen eine ziemliche Streuung der Scheitelpunktgrade zu sehen ist. Die folgende Abbildung zeigt eine typische kumulative Dichtefunktion des Scheitelpunktgrads für die unterste Ebene eines Lucene HNSW-Diagramms.

Wir haben die Verwendung eines festen Werts für $k_u$ sowie die Möglichkeit untersucht, ihn zu einer Funktion des Scheitelpunktgrads zu machen. Diese zweite Wahl führt zu größeren Beschleunigungen bei minimalen Auswirkungen auf die Grafikqualität, daher habe ich mich für Folgendes entschieden

Beachten Sie, dass $|N_s(u)$| per Definition gleich dem Grad des Scheitelpunkts $u$ im kleinen Graphen ist. Eine Untergrenze von zwei bedeutet, dass wir jeden Scheitelpunkt einfügen, dessen Grad kleiner als zwei ist.

Ein einfaches Zählargument legt nahe, dass wir bei sorgfältiger Wahl von $J$ nur etwa $\frac{1}{5}|V_s|$ direkt in $G_l$ einfügen müssen. Konkret färben wir eine Kante des Graphen, wenn wir genau einen ihrer Endknoten in $J$ einfügen. Dann wissen wir, dass wir für jeden Knoten in $V_s \setminus J$ mindestens $\sum_{u\in V_s\setminus J} k_u$ Kanten einfärben müssen, um mindestens $k_u$ Nachbarn in $J zu haben.$ Darüber hinaus erwarten wir, dass

Dabei ist $\mathbb{E}_U\left[N_s(U)|\right]$ der durchschnittliche Knotengrad im kleinen Graphen. Für jeden Knoten $u\in J$ färben wir höchstens $|N_s(u)|$ Kanten. Daher beträgt die Gesamtzahl der Kanten, die wir voraussichtlich einfärben werden, höchstens $|J|\, \mathbb{E}_U\left[|N_s(U)|\right]$. Wir hoffen, dass wir durch sorgfältige Wahl von $J$ annähernd diese Anzahl von Kanten einfärben können. Um alle Eckpunkte abzudecken, muss $|J|$ folgende Bedingung erfüllen:

Dies impliziert, dass $|J|=\frac{1}{4}(|V_s|-|J|)=\frac{4}{5}\frac{1}{4}|V_s|=\frac{1}{5}|V_s|$.

Vorausgesetzt, SEARCH-LAYER dominiert die Laufzeit, lässt dies darauf schließen, dass wir eine bis zu $fünffache$ Beschleunigung der Zusammenführungszeit erreichen könnten. Angesichts des logarithmischen Wachstums der Schreibverstärkung bedeutet dies, dass wir selbst bei sehr großen Indizes die Erstellungszeit im Vergleich zum Erstellen eines Diagramms normalerweise nur verdoppeln würden.

Das Risiko bei dieser Strategie besteht darin, dass wir die Grafikqualität beeinträchtigen. Wir haben es zunächst mit einem No-Op FAST-SEARCH-LAYER versucht. Wir haben festgestellt, dass dies die Qualität des Diagramms in dem Maße verschlechtert, dass die Rückrufrate als Funktion der Latenz beeinträchtigt wird, insbesondere beim Zusammenführen auf ein einzelnes Segment. Anschließend haben wir mithilfe einer eingeschränkten Suche im Diagramm verschiedene Alternativen untersucht. Am Ende war die effektivste Wahl die einfachste. Verwenden Sie SEARCH-LAYER , aber mit einem niedrigen ef_construction. Mit dieser Parametrisierung konnten wir Grafiken von hervorragender Qualität erzielen und die Zusammenführungszeit dennoch durchschnittlich um etwas mehr als 30 % verkürzen.

Berechnung der Join-Menge

Die Suche nach einer guten Join-Menge kann als HNSW-Graphüberdeckungsproblem formuliert werden. Eine Greedy-Heuristik ist eine einfache und effektive Heuristik zur Annäherung an optimale Graphüberdeckungen. Bei unserem Ansatz werden die Knotenpunkte nacheinander in absteigender Reihenfolge der Verstärkung zu $J$ hinzugefügt. Der Gewinn ist wie folgt definiert:

Dabei bezeichnet $c(v)$ die Anzahl der Nachbarn eines Vektors $v$ in $J$ und $1\{\cdot\}$ ist die Indikatorfunktion. Der Gewinn beinhaltet die Änderung der Anzahl der Scheitelpunkte, die wir zu $J$ hinzugefügt haben, also $\max(k_v-c(v),0)$, da wir unserem Ziel durch das Hinzufügen eines weniger abgedeckten Scheitelpunkts näher kommen. Die Gewinnberechnung wird in der folgenden Abbildung für den zentralen orangefarbenen Scheitelpunkt veranschaulicht.

Wir behalten für jeden Knoten $v$ den folgenden Zustand bei:

1. Ob es abgestanden ist,
2. Sein Gewinn $Gain(v)$,
3. Die Anzahl der benachbarten Eckpunkte in $J$ wird $mit c(v)$ bezeichnet,
4. Eine Zufallszahl im Bereich [0,1], die zum Auflösen eines Gleichstands verwendet wird.

Der Pseudocode zum Berechnen des Join-Sets lautet wie folgt.

COMPUTE-JOIN-SET

Inputs $G_s$

1$\;\;C\leftarrow\emptyset$
2$\;\;Gain_{exit}\leftarrow 0$
3$\;\;$for $u\in G_s$ do
4$\;\;\;\;C\leftarrow C \cup \{(\text{false}, k_u+deg(u), 0, \text{rand in }[0,1])\}$
5$\;\;\;\;Gain_{exit}\leftarrow Gain_{exit}+k_u$
6$\;\;Gain_{tot}\leftarrow 0$
7$\;\;$while $Gain_{tot}<Gain_{exit}$ do
8$\;\;\;\;v^*\leftarrow\,$ maximum gain vertex in $C$
9$\;\;\;\;$Remove the state for $v^*$ from $C$
10$\;\;\;$if $v^*$ is not stale then
11$\;\;\;\;\;J\leftarrow J\cup\{v^*\}$
12$\;\;\;\;\;Gain_{tot}\leftarrow Gain_{tot}+Gain(v^*)$
13$\;\;\;\;\;$for $u \in N_s(v^*)$ do
14$\;\;\;\;\;\;\;$mark $u$ as stale if $c(v^*)<k_{v^*}$
15$\;\;\;\;\;\;\;$mark neighbors of $u$ stale if $c(u)=k_u-1$
16$\;\;\;\;\;\;\;c(u)\leftarrow c(u)+1$
17$\;\;\;$else
18$\;\;\;\;\;Gain(v^*)\leftarrow \max(k_v-c(v^*),0)+\sum_{u\in N_s(v^*)\setminus J} 1\left\{c(u)<k_u\right\}$
19$\;\;\;\;\;$if $Gain(v^*)>0$ then
20$\;\;\;\;\;\;\;C\leftarrow C \cup \{(\text{false},Gain(v^*),c(v^*),\text{copy rand})\}$
21$\;\;$return $J$

Wir initialisieren zunächst den Status in den Zeilen 1-5.

In jeder Iteration der Hauptschleife extrahieren wir zunächst den Scheitelpunkt mit der maximalen Verstärkung (Zeile 8) und lösen Gleichstände nach dem Zufallsprinzip auf. Bevor wir Änderungen vornehmen, müssen wir prüfen, ob die Verstärkung des Scheitelpunkts veraltet ist. Insbesondere beeinflussen wir jedes Mal, wenn wir einen Scheitelpunkt zu $J$ hinzufügen, den Gewinn anderer Scheitelpunkte:

1. Da alle seine Nachbarn einen zusätzlichen Nachbarn in $J$ haben, können sich ihre Gewinne ändern (Zeile 14).
2. Wenn einer seiner Nachbarn jetzt vollständig gedeckt ist, können sich die Gewinne aller seiner Nachbarn ändern (Zeilen 14-16).

Wir berechnen die Gewinne auf verzögerte Weise neu, d. h. wir berechnen den Gewinn eines Scheitelpunkts nur dann neu, wenn wir ihn in $J$ einfügen möchten (Zeilen 18–20). Da die Gewinne immer nur abnehmen, können wir nie einen Scheitelpunkt verpassen, den wir einfügen sollten.

Beachten Sie, dass wir lediglich den Gesamtgewinn der zu $J$ hinzugefügten Scheitelpunkte im Auge behalten müssen, um zu bestimmen, wann wir aussteigen müssen. Darüber hinaus wird, obwohl $Gain_{tot}<Gain_{exit}ist,$ mindestens ein Scheitelpunkt einen von Null verschiedenen Gewinn aufweisen, sodass wir immer Fortschritte machen.

Ergebnisse

Wir haben Experimente mit vier Datensätzen durchgeführt, die zusammen unsere drei unterstützten Distanzmetriken (euklidisch, Kosinus und inneres Produkt) abdecken:

1. quora-E5-small: 522931 Dokumente, 384 Dimensionen und verwendet Kosinusähnlichkeit,
2. cohere-wikipedia-v2: 1 Million Dokumente, 768 Dimensionen und verwendet Kosinusähnlichkeit,
3. Kern: 1 Million Dokumente, 960 Dimensionen und verwendet euklidische Distanz und
4. cohere-wikipedia-v3: 1 Mio. Dokumente, 1024 Dimensionen und verwendet das maximale innere Produkt.

Für jeden Datensatz bewerten wir zwei Quantisierungsstufen:

1. int8 – verwendet eine 1-Byte-Ganzzahl pro Dimension und
2. BBQ – das ein einzelnes Bit pro Dimension verwendet.

Schließlich haben wir für jedes Experiment die Suchqualität bei zwei Abruftiefen bewertet und nach dem Erstellen des Index und anschließend nach der erzwungenen Zusammenführung zu einem einzelnen Segment untersucht.

Zusammenfassend lässt sich sagen, dass wir durchgängig erhebliche Beschleunigungen bei der Indizierung und Zusammenführung erzielen und dabei in allen Fällen die Grafikqualität und damit die Suchleistung beibehalten.

Experiment 1: int8-Quantisierung

Die durchschnittlichen Beschleunigungen von der Basislinie bis zum Kandidaten, die vorgeschlagenen Änderungen, sind:

Beschleunigung der Indexzeit: 1,28$\times$

Beschleunigung der Force Merge: 1,72$\times$

Dies entspricht folgender Laufzeitaufteilung

Der Vollständigkeit halber sind die genauen Zeiten

Unten zeigen wir die Diagramme „Rückruf vs. Latenz“, die den Kandidaten (gestrichelte Linien) mit der Basislinie bei zwei Abruftiefen vergleichen: Rückruf@10 und Rückruf@100 für Indizes mit mehreren Segmenten (das Endergebnis unserer Standard-Zusammenführungsstrategie nach der Indizierung aller Vektoren) und nach der erzwungenen Zusammenführung zu einem einzelnen Segment. Eine Kurve, die höher und weiter links liegt, ist besser, da sie eine höhere Rückrufrate bei geringerer Latenz bedeutet.

Wie Sie sehen, ist der Kandidat für mehrere Segmentindizes für den Cohere v3-Datensatz besser und für alle anderen Datensätze etwas schlechter, aber fast vergleichbar. Nach der Zusammenführung zu einem einzigen Segment sind die Erinnerungskurven in allen Fällen nahezu identisch.

Experiment 2: BBQ-Quantisierung

Die durchschnittlichen Beschleunigungen von der Basislinie zum Kandidaten sind:

Beschleunigung der Indexzeit: 1,33$\times$

Beschleunigung der Force Merge: 1,34$\times$

Dies entspricht folgender Laufzeitaufteilung

Der Vollständigkeit halber sind die genauen Zeiten

Bei Indizes mit mehreren Segmenten ist der Kandidat für fast alle Datensätze besser, mit Ausnahme von Cohere v2, wo die Basislinie etwas besser ist. Für die einzelnen Segmentindizes sind die Recall-Kurven in allen Fällen nahezu identisch.

Fazit

Der in diesem Blog besprochene Algorithmus wird im kommenden Lucene 10.2 und in der darauf basierenden Elasticsearch-Version verfügbar sein. Benutzer können in diesen neuen Versionen von der verbesserten Zusammenführungsleistung und der verkürzten Indexerstellungszeit profitieren. Diese Änderung ist Teil unserer kontinuierlichen Bemühungen, Lucene und Elasticsearch für die Vektor- und Hybridsuche schnell und effizient zu machen.