5 Probleme bei der Suche nach harten Vektoren und wie wir sie in Apache Cassandra gelöst haben

Die Vektorsuche ist eine entscheidende Komponente generativer KI-Tools, da Retrieval Augmented Generation (RAG) so ähnlich ist FLARE hilft LLMs, aktuelle, individuelle Informationen zu integrieren und gleichzeitig Halluzinationen zu vermeiden . Gleichzeitig ist die Vektorsuche eine Funktion und kein Produkt – Sie müssen Vektoren in ihrer Beziehung zum Rest Ihrer Daten abfragen, nicht isoliert, und Sie sollten keine Pipeline erstellen müssen, um den Rest Ihrer Daten zu synchronisieren Daten mit einem Vektorspeicher, um dies zu tun.

Im Jahr 2023 kam es zu einem explosionsartigen Anstieg der Vektorsuchprodukte und -projekte, was die Auswahl zu einer großen Herausforderung machte. Während Sie die Optionen recherchieren, müssen Sie die folgenden schwierigen Probleme und die verschiedenen Lösungsansätze berücksichtigen. Hier werde ich Sie durch diese Herausforderungen führen und beschreiben, wie DataStax sie für unsere Implementierung der Vektorsuche für DataStax Astra DB und Apache Cassandra bewältigt hat.

Inhaltsübersicht

• Der Fluch der Dimensionalität
• Problem 1: Scale-out
• Problem 2: Effiziente Speicherbereinigung
• Seitenleiste: Cloud-Anwendungs-Workloads
• Problem 3: Parallelität
• Problem 4: Effektive Nutzung der Festplatte
• Problem 5: Zusammensetzbarkeit
• Einpacken

Der Fluch der Dimensionalität

Im Kern dieser schwierigen Probleme liegt das, was Forscher als „ der Fluch der Dimensionalität .“ In der Praxis bedeutet dies, dass Algorithmen, die für die exakte Vektorsuche in 2D- oder 3D-Räumen funktionieren, z KD-Bäume , fallen auseinander, wenn Ihre Vektoren Abmessungen von 10, 100 oder 1000 erreichen. Das Ergebnis ist, dass es keine Abkürzung für die exakte Ähnlichkeitssuche mit hochdimensionalen Vektoren gibt; Um logarithmische Ergebnisse zu erhalten, müssen wir ANN-Algorithmen (Approximation Nearest Neighbor) verwenden, die Herausforderungen in den folgenden Bereichen mit sich bringen.

Problem 1: Scale-out

Viele Vektorsuchalgorithmen wurden für Datensätze entwickelt, die in den Speicher eines einzelnen Computers passen, und dies ist immer noch das einzige getestete Szenario Ann-Benchmarks . (Ann-Benchmarks beschränkt die Tests noch weiter auf einen einzigen Kern!) Dies mag für akademische Arbeiten mit einer Million Dokumenten oder Zeilen in Ordnung sein, aber es ist schon viele Jahre her, dass dies als repräsentativ für reale Arbeitslasten angesehen werden konnte.

Wie bei jeder anderen Domäne erfordert die Skalierung sowohl Replikation als auch Partitionierung sowie Subsysteme, die das Ersetzen toter Replikate, deren Reparatur nach einer Netzwerkpartition usw. übernehmen.

Das war für uns einfach: Scale-out-Replikation ist das A und O von Cassandra, und die Kombination mit dem neuen SAI in Cassandra-5.0 (Storage-Attached Indexing – siehe CEP-7 für die Funktionsweise und die SAI-Dokumentation (für die Verwendung) gaben unserer Implementierung der Vektorsuche leistungsstarke Scale-out-Funktionen, die effektiv und kostenlos zur Verfügung standen.

Problem 2: Effiziente Speicherbereinigung

Mit „Garbage Collection“ meine ich das Entfernen veralteter Informationen aus dem Index – das Bereinigen gelöschter Zeilen und den Umgang mit Zeilen, deren indizierter Vektorwert sich geändert hat. Das scheint vielleicht nicht der Rede wert zu sein – es ist seit vierzig Jahren ein mehr oder weniger gelöstes Problem in der Welt der relationalen Datenbanken –, aber Vektorindizes sind einzigartig.

Das Hauptproblem besteht darin, dass alle uns bekannten Algorithmen, die sowohl Suchvorgänge mit geringer Latenz als auch Ergebnisse mit hoher Erinnerung liefern, diagrammbasiert sind. Es stehen viele andere Vektorindizierungsalgorithmen zur Verfügung – FAISS implementiert viele davon – aber alle sind entweder zu langsam zum Erstellen, zu langsam zum Suchen oder bieten einen zu geringen Rückruf (und manchmal alle drei!), um eine Allzwecklösung zu sein. Aus diesem Grund verwendet jede mir bekannte Produktionsvektordatenbank einen graphbasierten Index, der einfachste davon ist HNSW. Hierarchische navigierbare Small-World-Graphen waren eingeführt von Yury Malkov et al. im Jahr 2016 ; Das Papier ist gut lesbar und ich kann es nur wärmstens empfehlen. Mehr zu HNSW weiter unten.

Die Herausforderung bei Diagrammindizes besteht darin, dass Sie nicht einfach den alten (vektorbezogenen) Knoten herausreißen können, wenn sich eine Zeile oder ein Dokument ändert. Wenn Sie dies mehr als ein paar Mal tun, kann Ihr Diagramm seinen Zweck, die BFS (Breite-zuerst-Suche) auf Bereiche mit größerer Ähnlichkeit zu einem Abfragevektor zu lenken, nicht mehr erfüllen.

Sie müssen Ihre Indizes also irgendwann neu erstellen, um diese Speicherbereinigung durchzuführen. Aber wann – und wie – organisieren Sie sie? Wenn Sie bei Änderungen immer alles neu erstellen, erhöhen Sie die Anzahl der durchgeführten physischen Schreibvorgänge erheblich. dies wird als Schreibverstärkung bezeichnet. Wenn Sie andererseits nie eine Neuerstellung durchführen, müssen Sie zusätzliche Arbeit leisten, indem Sie veraltete Zeilen zum Zeitpunkt der Abfrage herausfiltern („Leseverstärkung“).

Dies ist ein weiterer Problembereich, an dem Cassandra seit Jahren arbeitet. Da SAI-Indizes an den Hauptspeicherlebenszyklus angehängt sind, nehmen sie auch an Cassandra teil Verdichtung , wodurch die Speichereinheiten logarithmisch erhöht werden, um ein gesundes Gleichgewicht zwischen Lese- und Schreibvorgängen zu gewährleisten.

Seitenleiste: Cloud-Anwendungs-Workloads

DataStax Astra DB basiert auf Apache Cassandra und bietet eine Plattform für Cloud-Anwendungs-Workloads.

Das bedeutet Arbeitslasten, die:

• Massiv gleichzeitig Tausende bis Millionen von Anfragen pro Sekunde, normalerweise um jeweils nur ein paar Zeilen abzurufen. Aus diesem Grund könnten Sie Netflix nicht auf Snowflake ausführen, selbst wenn Sie es sich leisten könnten: Snowflake und ähnliche Analysesysteme sind darauf ausgelegt, nur wenige gleichzeitige Anfragen zu verarbeiten, die jeweils viele Sekunden bis Minuten oder sogar länger laufen.

  
  

• Größer als der Speicher Wenn Ihr Datensatz in den Speicher eines einzelnen Computers passt, spielt es fast keine Rolle, welche Tools Sie verwenden. SQLite, MongoDB, MySQL – sie werden alle gut funktionieren. Wenn das nicht der Fall ist, wird es schwieriger – und die schlechte Nachricht ist, dass Vektoreinbettungen normalerweise mehrere KB oder etwa eine Größenordnung größer als typische Datenbankdokumente sind, sodass Sie relativ schnell zu einer Größe kommen, die größer als der Speicher ist.

  
  

• Der Kern der Anwendung Wenn es Ihnen egal ist, ob Sie Ihre Daten verlieren, weil sie entweder nicht so wichtig sind oder weil Sie sie aus der eigentlichen Datenquelle wiederherstellen können, spielt es wiederum keine Rolle, welche Tools Sie verwenden. Datenbanken wie Cassandra und Astra DB sind darauf ausgelegt, Ihre Daten in jedem Fall verfügbar und dauerhaft zu halten.

Problem 3: Parallelität

Ich habe oben das Bekannte erwähnt Ann-Benchmarks Der Vergleich beschränkt alle Algorithmen auf einen einzigen Kern. Dies gleicht zwar die Wettbewerbsbedingungen aus, behindert aber auch diejenigen, die die Hauptquelle der Hardware-Verbesserung der letzten zwei Jahrzehnte nutzen können.

Ein damit verbundenes Problem besteht darin, dass ann-benchmarks jeweils nur eine Art von Operation ausführt: Zuerst wird der Index erstellt und dann wird er abgefragt. Der Umgang mit Updates, die mit Suchvorgängen verzahnt sind, ist optional – und wahrscheinlich sogar ein Handicap; Wenn Sie wissen, dass Sie sich nicht mit Updates befassen müssen, können Sie viele vereinfachende Annahmen treffen, die auf künstlichen Benchmarks gut aussehen.

Wenn es Ihnen wichtig ist, mehrere gleichzeitige Vorgänge mit Ihrem Index durchzuführen oder ihn nach der Erstellung zu aktualisieren, müssen Sie etwas genauer hinschauen, um zu verstehen, wie er funktioniert und welche Kompromisse damit verbunden sind.

Erstens verwenden alle mir bekannten Allzweck-Vektordatenbanken graphbasierte Indizes. Das liegt daran, dass Sie mit der Abfrage eines Diagrammindex beginnen können, sobald der erste Vektor eingefügt wird. Bei den meisten anderen Optionen müssen Sie entweder den gesamten Index erstellen, bevor Sie ihn abfragen, oder zumindest einen vorläufigen Scan der Daten durchführen, um einige statistische Eigenschaften zu erfahren.

Allerdings gibt es auch innerhalb der Diagrammindexkategorie noch wichtige Implementierungsdetails. Beispielsweise dachten wir zunächst, dass wir durch die Verwendung der HNSW-Indeximplementierung von Lucene Zeit sparen könnten, so wie es MongoDB Elastic und Solr tun. Aber wir haben schnell gelernt, dass Lucene nur Single-Threaded-, nicht-gleichzeitige Indexkonstruktionen bietet. Das heißt, Sie können es weder während der Erstellung abfragen (was einer der Hauptgründe für die Verwendung dieser Datenstruktur sein sollte!) noch zulassen, dass mehrere Threads es gleichzeitig erstellen.

Das HNSW-Papier legt nahe, dass ein feinkörniger Sperransatz funktionieren kann, aber wir sind noch einen Schritt weiter gegangen und haben einen nicht blockierenden Index erstellt. Dies ist Open-Source in JVector .

JVector skaliert gleichzeitige Updates linear auf mindestens 32 Threads. Dieses Diagramm ist sowohl auf der x- als auch auf der y-Achse logarithmisch skaliert und zeigt, dass eine Verdoppelung der Thread-Anzahl die Erstellungszeit halbiert.

Noch wichtiger ist, dass die nicht blockierende Parallelität von JVector durch die Mischung von Suchvorgängen und Aktualisierungen realistischere Arbeitslasten ermöglicht. Hier ist ein Vergleich der Leistung von Astra DB (mit JVector) im Vergleich zu Pinecone über verschiedene Datensätze hinweg. Während Astra DB für einen statischen Datensatz etwa 10 % schneller ist als Pinecone, ist es 8- bis 15-mal schneller und indiziert auch neue Daten. Wir haben mit Pinecone die beste verfügbare Pod-Stufe ausgewählt (Pod-Typ: p2 und Pod-Größe: x8, mit 2 Pods pro Replikat), basierend auf den Empfehlungen für höheren Durchsatz und geringere Latenz. Pinecone gibt nicht bekannt, auf welche physischen Ressourcen dies zurückzuführen ist. Auf der Astra DB-Seite haben wir uns für das standardmäßige PAYG-Bereitstellungsmodell entschieden und mussten uns keine Gedanken über die Auswahl der Ressourcen machen, da es serverlos ist. Tests wurden mit durchgeführt NoSQLBench .

Astra DB erreicht dies und behält gleichzeitig eine höhere Erinnerung und Präzision bei ( F1 ist eine Kombination aus Erinnerung und Präzision ) :

Problem 4: Effektive Nutzung der Festplatte

Wir begannen mit dem HNSW-Graph-Indizierungsalgorithmus weil der Index schnell erstellt, Abfragen schnell durchgeführt werden können, die Genauigkeit hoch ist und die Implementierung unkompliziert ist. Allerdings hat es einen bekannten Nachteil: Es benötigt viel Speicher.

Ein HNSW-Index besteht aus einer Reihe von Schichten, wobei jede Schicht über der Basisschicht etwa 10 % so viele Knoten wie die vorherige aufweist. Dadurch können die oberen Schichten als Sprungliste fungieren, sodass sich die Suche auf die rechte Nachbarschaft der unteren Schicht konzentrieren kann, die alle Vektoren enthält.

Dieses Design bedeutet jedoch, dass Sie (wie bei allen Diagrammindizes) nicht mit der Aussage „Der Festplatten-Cache wird uns retten“ davonkommen können, da im Gegensatz zu normalen Datenbankabfrage-Workloads jeder Vektor im Diagramm eine nahezu gleiche Wahrscheinlichkeit hat für eine Suche relevant sein. (Die Ausnahme bilden die oberen Schichten, die wir zwischenspeichern können und auch tun.)

So sah ein Profil zur Bereitstellung eines 100 Millionen Vektordatensatzes aus Wikipedia-Artikelblöcken (ca. 120 GB auf der Festplatte) auf meinem Desktop mit 64 GB RAM aus, als wir Lucene verwendeten:

Cassandra verbringt fast die ganze Zeit damit, darauf zu warten, Vektoren von der Festplatte zu lesen.

Um dieses Problem zu lösen, haben wir einen fortschrittlicheren Algorithmus namens DiskANN implementiert und ihn als eigenständige eingebettete Vektorsuchmaschine als Open-Source-Lösung bereitgestellt. JVector . (Konkret implementiert JVector die inkrementelle Version von DiskANN, die im beschrieben wird FreshDiskANN Papier.) Kurz gesagt: DiskANN verwendet ein einstufiges Diagramm mit längeren Kanten als HNSW und einem optimierten Layout von Vektoren und Nachbarn, um Festplatten-IOPS zu reduzieren, und behält eine komprimierte Darstellung von Vektoren im Speicher bei, um Ähnlichkeitsberechnungen zu beschleunigen. Dies führt zu einer Verdreifachung des Durchsatzes der Wikipedia-Arbeitslast.

So sieht HNSW im Vergleich zu DiskANN in einem rein eingebetteten Szenario ohne Client/Server-Komponenten aus. Dies misst die Geschwindigkeit der Suche im Deep100M-Datensatz unter Lucene (HNSW) und JVector (DiskANN). Der Lucene-Index ist 55 GB groß, einschließlich des Index und der Rohvektoren. Der JVector-Index beträgt 64 GB. Die Suche wurde auf meinem 24-GB-MacBook durchgeführt, das etwa ein Drittel so viel Speicher hat, wie nötig wäre, um den Index im RAM zu halten.

Problem 5: Zusammensetzbarkeit

Zusammensetzbarkeit bezieht sich im Kontext von Datenbanksystemen auf die Fähigkeit, verschiedene Funktionen und Fähigkeiten nahtlos und kohärent zu integrieren. Dies ist besonders wichtig, wenn die Integration einer neuen Funktionskategorie wie der Vektorsuche diskutiert wird. Nicht-Spielzeug-Anwendungen erfordern immer beide klassischen CRUD Datenbankfunktionen sowie die neue Vektorsuche.

Betrachten Sie das Einfache KI-Chatbot Beispielanwendung für Astra DB. Dabei handelt es sich um eine so reine RAG-Anwendung, wie Sie sie nur finden werden. Sie nutzt die Vektorsuche, um dem LLM geeignete Dokumentation zur Verfügung zu stellen und auf Benutzerfragen zu antworten. Allerdings muss selbst eine einfache Demo wie diese immer noch „normale“ Nicht-Vektor-Anfragen an Astra DB stellen, um den Konversationsverlauf abzurufen, der auch bei jeder Anfrage an das LLM enthalten sein muss, damit es sich „merken“ kann, was bereits vorhanden ist geschehen. Zu den Schlüsselfragen gehören also:

1. Finden Sie die relevantesten Dokumente (oder Dokumentfragmente) für die Frage des Benutzers
2. Rufen Sie die letzten zwanzig Nachrichten aus der Konversation des Benutzers ab

In einem realistischeren Anwendungsfall arbeitete einer unserer Lösungsingenieure kürzlich mit einem Unternehmen in Asien zusammen, das seinen Produktkatalog um eine semantische Suche erweitern, aber auch einen begriffsbasierten Abgleich ermöglichen wollte. Wenn der Benutzer beispielsweise nach [„roter“ Kugelhahn] sucht, möchte er die Suche auf Elemente beschränken, deren Beschreibung mit dem Begriff „rot“ übereinstimmt, unabhängig davon, wie semantisch ähnlich die Vektoreinbettungen sind. Die wichtigste neue Abfrage lautet dann (zusätzlich zu klassischen Funktionen wie Sitzungsverwaltung, Bestellhistorie und Warenkorbaktualisierungen): Beschränken Sie die Produkte auf diejenigen, die alle zitierten Begriffe enthalten, und suchen Sie dann nach den Produkten, die der Suche des Benutzers am ähnlichsten sind

Dieses zweite Beispiel macht deutlich, dass Anwendungen nicht nur sowohl klassische Abfragefunktionen als auch Vektorsuche benötigen, sondern dass sie häufig auch in der Lage sein müssen, Elemente beider in derselben Abfrage zu verwenden.

Der aktuelle Stand der Technik in diesem jungen Bereich besteht darin, zu versuchen, das, was ich klassische Abfragen nenne, in einer „normalen“ Datenbank und Vektorabfragen in einer Vektordatenbank durchzuführen und die beiden dann ad hoc zusammenzufügen, wenn beides der Fall ist gleichzeitig erforderlich. Dies ist fehleranfällig, langsam und teuer; Der einzige Vorteil besteht darin, dass Sie es zum Laufen bringen können, bis Sie eine bessere Lösung haben.

Mit Astra DB haben wir diese bessere Lösung auf Basis von Cassandra SAI entwickelt (und als Open-Source-Lösung bereitgestellt). Da SAI die Erstellung benutzerdefinierter Indextypen ermöglicht, die alle an den Stable- und Komprimierungslebenszyklus von Cassandra gebunden sind, ist es für Astra DB einfach, Entwicklern die Kombination von booleschen Prädikaten, begriffsbasierter Suche und Vektorsuche ohne Mehraufwand zu ermöglichen Verwaltung und Synchronisierung separater Systeme. Dadurch erhalten Entwickler, die generative KI-Anwendungen erstellen, ausgefeiltere Abfragefunktionen, die zu höherer Produktivität und schnellerer Markteinführung führen.

Einpacken

Vektorsuchmaschinen sind eine wichtige neue Datenbankfunktion mit mehreren architektonischen Herausforderungen, darunter Scale-out, Garbage Collection, Parallelität, effektive Festplattennutzung und Zusammensetzbarkeit. Ich glaube, dass wir beim Aufbau der Vektorsuche für Astra DB die Fähigkeiten von Cassandra nutzen konnten, um Entwicklern generativer KI-Anwendungen ein erstklassiges Erlebnis zu bieten. Erfahren Sie hier mehr über Astra DB , oder wenn Sie Vektorsuchalgorithmen aus nächster Nähe kennenlernen möchten, schauen Sie sich das an JVector .

– Von Jonathan Ellis, DataStax