Einleitende Worte
Ich habe diesen Vortrag auf Englisch auf der GopherCon Russland 2019 in Moskau gehalten und auf Russisch beim Meetup in Nischni Nowgorod. Es geht um Bitmap-Indizes – weniger verbreitet als B-Bäume, aber nicht weniger interessant. Ich teile meiner Präsentation auf der Konferenz in Englisch und die schriftliche Transkription auf Russisch.
Wir werden betrachten, wie ein Bitmap-Index aufgebaut ist, wann er besser ist als andere Indizes und wann er deutlich schneller ist; wir sehen uns an, in welchen beliebten DBMS es bereits Bitmap-Indizes gibt; und versuchen, unseren eigenen in Go zu schreiben. Als ‚Dessert‘ nutzen wir vorhandene Bibliotheken, um unsere superschnelle spezialisierte Datenbank zu erstellen.
Ich hoffe sehr, dass meine Arbeit für Sie nützlich und interessant ist. Lassen Sie uns beginnen!
Einführung
Hallo zusammen! Es ist jetzt sechs Uhr abends, und wir sind alle super müde. Eine wunderbare Zeit, um über die langweilige Theorie von Datenbankindizes zu sprechen, oder? Keine Sorge, ich werde hier und da ein paar Codezeilen haben. 🙂
Im Ernst, der Vortrag ist voller Informationen, und wir haben nicht viel Zeit. Lassen Sie uns also anfangen.
Heute werde ich über Folgendes sprechen:
- Was sind Indizes?
- Was ist ein Bitmap-Index?
- Wo wird er eingesetzt und wo nicht, und warum?
- Einfache Implementierung in Go und ein wenig Kämpfen mit dem Compiler.
- Etwas weniger einfach, aber deutlich leistungsfähigere Implementierung in Go-Assembler.
- Die "Probleme" von Bitmap-Indizes.
- Bestehende Implementierungen.
Also, was sind Indizes?
Ein Index ist eine separate Datenstruktur, die wir zusätzlich zu den Hauptdaten halten und aktualisieren. Sie wird verwendet, um die Suche zu beschleunigen. Ohne Indizes würde die Suche einen vollständigen Durchgang durch die Daten erfordern (ein Prozess, der als Full Scan bezeichnet wird), und dieser Prozess hat eine lineare algorithmische Komplexität. Aber Datenbanken enthalten normalerweise eine riesige Menge an Daten, und lineare Komplexität ist zu langsam. Idealerweise hätten wir logarithmische oder konstante Komplexität.
Das ist ein riesiges, komplexes Thema, das voller Feinheiten und Kompromisse ist, aber nachdem ich jahrzehntelange Entwicklungen und Forschungen zu verschiedenen Datenbanken betrachtet habe, bin ich bereit zu behaupten, dass es nur wenige weit verbreitete Ansätze zur Erstellung von Datenbankindizes gibt.
Der erste Ansatz besteht darin, den Suchbereich hierarchisch zu verkleinern, indem man ihn in kleinere Teile aufteilt.
In der Regel tun wir dies, indem wir verschiedene Arten von Bäumen verwenden. Ein Beispiel dafür könnte eine große Kiste mit Materialien in Ihrem Schrank sein, in der sich kleinere Kisten mit Materialien zu verschiedenen Themen befinden. Wenn Sie Materialien benötigen, suchen Sie sicherlich in der Kiste mit der Beschriftung "Materialien" und nicht in der, auf der "Kekse" steht, oder?
Der zweite Ansatz besteht darin, sofort das gesuchte Element oder eine Gruppe von Elementen zu identifizieren. Dies geschieht in Hash-Maps oder in umgekehrten Indizes. Die Nutzung von Hash-Maps ähnelt dem vorherigen Beispiel, nur dass Sie anstelle einer Kiste mit Kisten eine Vielzahl von kleinen Boxen mit endgültigen Objekten in Ihrem Schrank haben.
Der dritte Ansatz ist, die Notwendigkeit einer Suche zu eliminieren. Dies erreichen wir mit Bloom-Filtern oder Cuckoo-Filtern. Erstere liefern die Antwort sofort und befreien Sie von der Notwendigkeit zu suchen.
Der letzte Ansatz besteht darin, alle Möglichkeiten, die moderne Hardware bietet, vollständig zu nutzen. Genau das tun wir bei Bitmap-Indizes. Ja, manchmal müssen wir den gesamten Index durchlaufen, aber wir machen dies super effizient.
Wie ich bereits erwähnt habe, ist das Thema Datenbankindizes umfangreich und voller Kompromisse. Das bedeutet, dass wir manchmal mehrere Ansätze gleichzeitig nutzen können: wenn wir die Suche noch weiter beschleunigen müssen oder wenn es erforderlich ist, alle möglichen Suchtypen abzudecken.
Heute werde ich über die am wenigsten bekannte Methode sprechen — die Bitmap-Indizes.
Wer bin ich, um über dieses Thema zu sprechen?
Ich arbeite als Teamleiter bei Badoo (vielleicht kennen Sie unser anderes Produkt besser — Bumble). Wir haben über 400 Millionen Nutzer weltweit und viele Funktionen, die darauf abzielen, das beste Matching zu finden. Dabei nutzen wir maßgeschneiderte Services, die unter anderem auch Bitmap-Indizes einsetzen.
Was ist also ein Bitmap-Index?
Bitmap-Indizes verwenden, wie der Name schon sagt, Bitmaps oder Bitsets, um einen Suchindex zu implementieren. Aus der Vogelperspektive besteht dieser Index aus einem oder mehreren dieser Bitmaps, die bestimmte Entitäten (wie Personen) und deren Eigenschaften oder Parameter (Alter, Augenfarbe usw.) repräsentieren, sowie aus einem Algorithmus, der bitweise Operationen (UND, ODER, NICHT) nutzt, um Suchanfragen zu beantworten.
Es wird gesagt, dass Bitmap-Indizes am besten geeignet und sehr leistungsfähig sind für Fälle, in denen Suchanfragen mehrere Spalten mit geringer Kardinalität kombinieren (denken Sie an 'Augenfarbe' oder 'Familienstand' im Gegensatz zu etwas wie 'Entfernung zum Stadtzentrum'). Aber später werde ich zeigen, dass sie auch bei Spalten mit hoher Kardinalität hervorragend funktionieren.
Lassen Sie uns ein einfaches Beispiel für einen Bitmap-Index betrachten.
Stellen Sie sich vor, dass wir eine Liste von Restaurants in Moskau mit binären Eigenschaften wie diesen haben:
- in der Nähe der U-Bahn (near metro);
- mit privatem Parkplatz (has private parking);
- mit Terrasse (has terrace);
- mit Tischreservierungen (accepts reservations);
- veganfreundlich (vegan friendly);
- teuer (expensive).
Lassen Sie uns jedem Restaurant eine fortlaufende Nummer ab 0 geben und Speicher für 6 Bitmaps reservieren (je eines für jedes Merkmal). Dann füllen wir diese Bitmaps abhängig davon aus, ob das Restaurant das jeweilige Merkmal besitzt oder nicht. Hat Restaurant 4 eine Terrasse, wird das Bit Nr. 4 im Bitmap "hat Terrasse" auf 1 gesetzt (wenn keine Terrasse vorhanden ist, auf 0).
Jetzt haben wir den einfachsten Bitmap-Index, den es gibt, und wir können ihn verwenden, um auf Anfragen zu antworten wie:
- "Zeig mir Restaurants, die für Vegetarier geeignet sind";
- "Zeig mir preiswerte Restaurants mit Terrasse, in denen man einen Tisch reservieren kann."
Wie? Schauen wir uns das an. Die erste Anfrage ist sehr einfach. Alles, was wir tun müssen, ist, das Bitmap "geeignet für Vegetarier" zu nehmen und es in eine Liste von Restaurants umzuwandeln, deren Bits gesetzt sind.
Die zweite Anfrage ist etwas komplexer. Wir müssen die BIT-NOT-Operation auf der Bitmap "teuer" verwenden, um eine Liste von günstigen Restaurants zu erhalten. Dann verknüpfen wir sie mit der Bitmap "Reservierung möglich" und kombinieren das Ergebnis mit der Bitmap "hat eine Terrasse". Die resultierende Bitmap wird eine Liste von Einrichtungen enthalten, die all unseren Kriterien entsprechen. In diesem Beispiel ist das nur das Restaurant "Junge Jahre".
Hier gibt es viel Theorie, aber keine Sorge, wir werden bald den Code sehen.
Wo werden Bitmap-Indizes verwendet?
Wenn Sie "Bitmap-Indizes googeln", werden 90 % der Antworten irgendwie mit Oracle DB verbunden sein. Aber auch andere DBMS unterstützen diese coole Funktion, oder? Nicht ganz.
Lassen Sie uns die Liste der Hauptverdächtigen durchgehen.
MySQL unterstützt Bitmap-Indizes noch nicht, aber es gibt einen Vorschlag, diese Option hinzuzufügen ().
PostgreSQL unterstützt keine Bitmap-Indizes, verwendet jedoch einfache Bitmaps und Bitoperationen zur Kombination von Suchergebnissen über mehrere andere Indizes.
Tarantool hat Bitset-Indizes, es unterstützt einfache Suchen darauf.
Redis hat einfache Bitfelder) ohne die Möglichkeit, danach zu suchen.
MongoDB unterstützt noch keine Bitmap-Indizes, es gibt jedoch einen Vorschlag zur Hinzunahme dieser Option.
Elasticsearch verwendet Bitmaps intern.).
- Aber in unserem Haus hat ein neuer Nachbar Einzug gehalten: Pilosa. Dies ist eine neue nicht-relationale Datenbank, die in Go geschrieben wurde. Sie enthält ausschließlich Bitmap-Indizes und basiert komplett auf ihnen. Darüber werden wir später sprechen.
Implementierung in Go
Warum werden Bitmap-Indizes jedoch so selten verwendet? Bevor ich diese Frage beantworte, möchte ich Ihnen eine sehr einfache Implementierung eines Bitmap-Index in Go demonstrieren.
Bitmaps sind im Wesentlichen einfach Datenstücke. In Go verwenden wir dafür Byte-Slices.
Wir haben einen Bitmap für ein Restaurantmerkmal, und jedes Bit im Bitmap zeigt an, ob ein bestimmtes Restaurant dieses Merkmal hat oder nicht.
Wir benötigen zwei Hilfsfunktionen. Eine wird verwendet, um unsere Bitmaps mit zufälligen Daten zu füllen. Zufällig, aber mit einer bestimmten Wahrscheinlichkeit, dass ein Restaurant bestimmte Eigenschaften aufweist. Zum Beispiel denke ich, dass es in Moskau sehr wenige Restaurants gibt, in denen man keinen Tisch reservieren kann, und ich schätze, dass etwa 20 % der Lokale für Vegetarier geeignet sind.
Die zweite Funktion wird das Bitmap in eine Liste von Restaurants umwandeln.
Um die Anfrage „Zeig mir preiswerte Restaurants mit einer Terrasse, in denen man einen Tisch reservieren kann“ zu beantworten, benötigen wir zwei bitweise Operationen: NOT und AND.
Wir können unseren Code etwas vereinfachen, indem wir eine komplexere Operation AND NOT verwenden.
Wir haben Funktionen für jede dieser Operationen. Beide durchlaufen die Slices, nehmen die entsprechenden Elemente aus jedem, führen die bitweise Operation durch und speichern das Ergebnis in dem Ergebnis-Slice.
Und jetzt können wir unsere Bitmaps und Funktionen nutzen, um die Suchanfrage zu beantworten.
Die Leistung ist nicht so hoch, obwohl die Funktionen sehr einfach sind und wir beträchtliche Einsparungen erzielt haben, da wir bei jedem Funktionsaufruf nicht einen neuen Resultats-Slice zurückgegeben haben.
Nach ein wenig Profilerstellung mit pprof bemerkte ich, dass der Go-Compiler eine sehr einfache, aber äußerst wichtige Optimierung ausgelassen hat: das Inlining von Funktionen.
Das Problem ist, dass der Go-Compiler große Angst vor Schleifen hat, die über Slices gehen, und kategorisch ablehnt, Funktionen zu inlinen, die solche Schleifen enthalten.
Aber ich habe keine Angst und kann den Compiler täuschen, indem ich anstelle einer Schleife goto verwende, wie in alten Zeiten.
Und wie Sie sehen, inline der Compiler jetzt gerne unsere Funktion! Letztendlich gelingt es uns, etwa 2 Mikrosekunden zu sparen. Gar nicht schlecht!
Das zweite Engpass ist leicht zu erkennen, wenn man den Assembler-Ausgabe aufmerksam betrachtet. Der Compiler hat eine Überprüfung der Slice-Grenzen direkt in unseren heißesten Schleifen eingefügt. Das Problem ist, dass Go eine sichere Sprache ist und der Compiler befürchtet, dass meine drei Argumente (drei Slices) unterschiedliche Größen haben. Dadurch könnte theoretisch ein so genanntes Buffer Overflow entstehen.
Lassen Sie uns den Compiler beruhigen, indem wir ihm zeigen, dass alle Slices die gleiche Größe haben. Das können wir erreichen, indem wir zu Beginn unserer Funktion eine einfache Überprüfung hinzufügen.
Wenn der Compiler das sieht, lässt er die Überprüfung gerne aus, und wir sparen am Ende weitere 500 Nanosekunden.
Große Batches
Okay, wir haben eine gewisse Leistung aus unserer einfachen Implementierung herausgeholt, aber dieses Ergebnis ist tatsächlich viel schlechter, als es mit der aktuellen Hardware möglich wäre.
Alles, was wir tun, sind grundlegende bitweise Operationen, und unsere Prozessoren führen diese sehr effizient aus. Leider "füttern" wir unseren Prozessor jedoch mit sehr kleinen Arbeitsstücken. Unsere Funktionen führen Operationen byteweise aus. Es ist ganz einfach, unseren Code so zu optimieren, dass er mit 8-Byte-Stücken arbeitet, indem wir UInt64-Slices verwenden.
Wie Sie sehen können, hat diese kleine Änderung unser Programm um das Achtfache beschleunigt, indem die Batch-Größe um das Achtfache erhöht wurde. Der Gewinn ist sozusagen linear.
Implementierung in Assembler
Aber das ist noch nicht das Ende. Unsere Prozessoren können mit Stücken von 16, 32 und sogar 64 Byte arbeiten. Solche "breiten" Operationen werden als Single Instruction Multiple Data (SIMD; eine Anweisung, viele Daten) bezeichnet, und der Prozess, der den Code so umgestaltet, dass er solche Operationen nutzt, wird als Vektorisierung bezeichnet.
Leider ist der Go-Compiler nicht gerade ein Meister in der Vektorisierung. Derzeit gibt es keinen anderen Weg, um Go-Code zu vektorisieren, als die Datenoperationen manuell mithilfe von Go-Assembler zu organisieren.
Go-Assembler ist ein interessantes Phänomen. Sie wissen wahrscheinlich, dass ein Assembler stark an die Architektur des Computers gebunden ist, für den Sie schreiben, aber im Fall von Go ist das nicht so. Go-Assembler ähnelt mehr einer IRL (Intermediate Representation Language) oder einer Zwischenrepräsentation: Er ist nahezu plattformunabhängig. Rob Pike hat vor einigen Jahren auf der GopherCon in Denver einen hervorragenden Vortrag zu diesem Thema gehalten. Zusätzlich dazu verwendet Go ein ungewöhnliches Format von Plan 9, das sich von den allgemein anerkannten Formaten AT&T und Intel unterscheidet.
Es lässt sich mit Sicherheit sagen, dass das manuelle Schreiben von Go-Assembler nicht die unterhaltsamste Aufgabe ist.
Aber glücklicherweise gibt es bereits zwei hochentwickelte Tools, die uns beim Schreiben von Go-Assembler helfen: PeachPy und avo. Beide Werkzeuge generieren Go-Assembler aus höherstufigem Code, der entweder in Python oder Go geschrieben ist.
Diese Tools erleichtern Aufgaben wie die Zuweisung von Registern, das Schreiben von Schleifen und vereinfachen insgesamt den Einstieg in die Welt der Assembler-Programmierung in Go.
Wir werden avo verwenden, sodass unsere Programme nahezu normale Go-Programme sein werden.
Wir werden avo verwenden, sodass unsere Programme fast wie ganz normale Go-Programme sind.
So sieht das einfachste Beispiel eines Avo-Programms aus. Wir haben eine Funktion main(), die innerhalb ihr eine Funktion Add() definiert, deren Aufgabe es ist, zwei Zahlen zu addieren. Hier sind Hilfsfunktionen vorhanden, um Parameter nach Namen zu erhalten und einen der verfügbaren geeigneten Prozessorregister abzurufen. Jede Prozessoroperation hat die entsprechende Funktion in Avo, wie bei ADDQ zu sehen ist. Und schließlich sehen wir eine Hilfsfunktion zum Speichern des Ergebniswerts.
Wenn wir go generate aufrufen, führen wir das Programm in Avo aus, und am Ende werden zwei Dateien generiert:
- add.s mit dem resultierenden Code in Go-Assembler;
- stub.go mit Funktionskopfzeilen zur Verbindung der beiden Welten: Go und Assembler.
Nun, da wir gesehen haben, was Avo tut und wie es funktioniert, schauen wir uns unsere Funktionen an. Ich habe sowohl die Skalare als auch die Vektorversionen (SIMD) der Funktionen implementiert.
Zuerst werfen wir einen Blick auf die skalaren Versionen.
Wie im vorherigen Beispiel bitten wir darum, uns ein freies und geeignetes allgemeines Register bereitzustellen; wir müssen keine Offsets und Größen für die Argumente berechnen. All das erledigt Avo für uns.
Früher haben wir Labels und Goto (oder Sprünge) verwendet, um die Leistung zu steigern und den Go-Compiler auszutricksen, aber jetzt machen wir das von Grund auf neu. Das Problem ist, dass Schleifen ein höheres Konzept sind. Im Assembler haben wir nur Labels und Sprünge.
Der verbleibende Code sollte Ihnen bereits vertraut und verständlich sein. Wir emulieren eine Schleife mit Labels und Sprüngen, nehmen einen kleinen Teil der Daten aus unseren beiden Slices, kombinieren sie mit einer Bitoperation (in diesem Fall AND NOT) und legen das Ergebnis dann in den Ergebnis-Slice. Das war's.
So sieht der endgültige Code in Assembler aus. Wir mussten keine Offsets und Größen berechnen (grün hervorgehoben) oder die verwendeten Register überwachen (rot hervorgehoben).
Wenn wir die Leistung der Implementierung in Assembler mit der Leistung der besten Implementierung in Go vergleichen, werden wir feststellen, dass sie gleich ist. Und das ist zu erwarten. Schließlich haben wir nichts Besonderes getan – wir haben nur reproduziert, was der Go-Compiler tun würde.
Leider kann der Compiler unsere in Assembler geschriebenen Funktionen nicht inline einfügen. Der Go-Compiler bietet diese Möglichkeit derzeit nicht, obwohl die Bitte, dies hinzuzufügen, schon seit geraumer Zeit besteht.
Genau deshalb ist es nicht möglich, irgendwelche Vorteile aus kleineren Assembler-Funktionen zu ziehen. Wir müssen große Funktionen schreiben, ein neues Paket math/bits verwenden oder Assembler ganz umgehen.
Lassen Sie uns nun die vektorisierten Versionen unserer Funktionen betrachten.
Für dieses Beispiel habe ich beschlossen, AVX2 anzuwenden, daher verwenden wir Operationen, die mit 32-Byte-Stückchen arbeiten. Die Struktur des Codes ist sehr ähnlich der skalaren Version: Parameter laden, um einen freien allgemeinen Register zu bitten usw.
Eine der Neuerungen besteht darin, dass breitere Vektoroperationen spezielle breite Register verwenden. Im Fall von 32-Byte-Stücken sind dies die Register mit dem Präfix Y. Deshalb sehen Sie die Funktion YMM() im Code. Wenn ich AVX-512 mit 64-Bit-Stücken verwenden würde, wäre das Präfix Z.
Die zweite Neuerung besteht darin, dass ich eine Optimierung eingeführt habe, die als Loop Unrolling bekannt ist. Das bedeutet, dass ich acht Schleifenoperationen manuell durchgeführt habe, bevor ich zum Anfang der Schleife zurücksprung. Diese Optimierung verringert die Anzahl der Verzweigungen im Code und ist durch die Anzahl der verfügbaren Register begrenzt.
Wie sieht es mit der Leistung aus? Sie ist hervorragend! Wir haben eine Beschleunigung von etwa sieben Mal im Vergleich zur besten Lösung in Go erreicht. Beeindruckend, oder?
Selbst diese Implementierung könnte potenziell noch weiter beschleunigt werden, indem man AVX-512, Prefetching oder JIT (Just-in-Time-Compiler) für den Anfragenplaner nutzt. Aber das wäre wirklich ein Thema für einen eigenen Vortrag.
Probleme mit Bitmap-Indizes
Jetzt, da wir bereits die einfache Implementierung des Bitmap-Index in Go und die deutlich leistungsfähigere Version in Assembler betrachtet haben, lassen Sie uns endlich darüber sprechen, warum Bitmap-Indizes so selten verwendet werden.
In älteren wissenschaftlichen Arbeiten werden drei Probleme von Bitmap-Indizes erwähnt, aber neuere Studien und ich sind der Meinung, dass sie mittlerweile nicht mehr relevant sind. Lassen Sie uns nicht zu tief in jedes dieser Probleme eintauchen, sondern sie nur oberflächlich betrachten.
Das Problem der hohen Kardinalität
Es wird darauf hingewiesen, dass Bitmap-Indizes nur für Felder mit niedriger Kardinalität geeignet sind, also solche mit wenigen Werten (zum Beispiel Geschlecht oder Augenfarbe). Der Grund dafür ist, dass die übliche Darstellung solcher Felder (ein Bit pro Wert) bei hoher Kardinalität zu viel Platz benötigen würde und zudem diese Bitmap-Indizes sparsamer (selten) gefüllt wären.
Manchmal können wir eine andere Darstellung verwenden, beispielsweise die Standarddarstellung, die wir zur Darstellung von Zahlen nutzen. Doch genau die Entwicklung von Kompressionsalgorithmen hat alles verändert. In den letzten Jahrzehnten haben Wissenschaftler und Forscher eine Vielzahl von Kompressionsalgorithmen für Bitmaps entwickelt. Der Hauptvorteil besteht darin, dass es nicht notwendig ist, Bitmaps zu dekomprimieren, um bitweise Operationen durchzuführen – wir können bitweise Operationen direkt auf komprimierten Bitmaps ausführen.
In letzter Zeit sind auch hybride Ansätze aufgetaucht, wie beispielsweise Roaring-Bitmaps. Diese nutzen gleichzeitig drei verschiedene Darstellungen für Bitmaps – nämlich die Bitmaps selbst, Arrays und sogenannte Bit Runs – und balancieren zwischen ihnen, um die Leistung zu maximieren und den Speicherverbrauch zu minimieren.
Roaring-Bitmaps finden Sie in vielen beliebten Anwendungen. Es gibt bereits eine große Anzahl von Implementierungen in verschiedenen Programmiersprachen, darunter mehr als drei für Go.
Ein weiterer Ansatz, der uns helfen kann, mit hoher Kardinalität umzugehen, ist die Gruppierung (Binning). Stellen Sie sich vor, Sie haben ein Feld, das die Körpergröße einer Person repräsentiert. Größe ist eine Fließkommazahl, aber wir Menschen denken nicht in diesen Begriffen. Für uns gibt es keinen Unterschied zwischen 185,2 cm und 185,3 cm.
Das bedeutet, wir können ähnliche Werte in Gruppen innerhalb von 1 cm zusammenfassen.
Und wenn wir zudem wissen, dass nur sehr wenige Menschen eine Größe von weniger als 50 cm oder mehr als 250 cm haben, können wir das Feld mit unendlicher Kardinalität im Grunde genommen in ein Feld mit ungefähr 200 Werten umwandeln.
Natürlich können wir, wenn nötig, eine zusätzliche Filterung auch nachträglich vornehmen.
Das Problem mit der hohen Bandbreite
Ein weiteres Problem der Bitmap-Indizes ist, dass deren Aktualisierung sehr kostspielig sein kann.
Datenbanken müssen in der Lage sein, Daten zu aktualisieren, während potenziell Hunderte anderer Anfragen diese Daten abfragen. Wir benötigen Locks, um Probleme mit gleichzeitigen Datenzugriffen oder anderen Problemen des gemeinsamen Zugriffs zu vermeiden. Wo es einen großen Lock gibt, treten Probleme auf — Lock-Kontention, wenn dieser Lock zum Flaschenhals wird.
Dieses Problem kann durch Sharding oder die Verwendung von versionierten Indizes gelöst oder umgangen werden.
Sharding ist einfach und allgemein bekannt. Sie können einen Bitmap-Index auf die gleiche Weise sharden, wie Sie andere Daten shardieren würden. Anstelle eines großen Locks erhalten Sie viele kleine Locks und vermeiden damit Lock-Kontention.
Eine zweite Möglichkeit zur Problemlösung ist die Verwendung versionierter Indizes. Sie können eine Kopie des Indexes haben, die Sie für Suchanfragen oder Lesevorgänge verwenden, und eine weitere für das Schreiben oder Aktualisieren. In regelmäßigen Abständen (zum Beispiel alle 100 ms oder 500 ms) duplizieren Sie diese und tauschen sie aus. Natürlich ist dieser Ansatz nur anwendbar, wenn Ihre Anwendung mit einem leicht verzögerten Suchindex arbeiten kann.
Diese beiden Ansätze können gleichzeitig verwendet werden: Sie können einen shardierten versionierten Index haben.
Komplexere Abfragen
Das letzte Problem der Bitmap-Indizes ist, dass sie, wie uns gesagt wird, schlecht für komplexere Abfragetypen geeignet sind, wie zum Beispiel Abfragen "im Intervall".
Tatsächlich sind bitweise Operationen wie AND, OR und Ähnliches nicht besonders geeignet für Anfragen wie: "Zeig mir Hotels mit Preisen zwischen 200 und 300 Dollar pro Nacht".
Eine naive und äußerst unkluge Lösung wäre es, die Ergebnisse für jeden Dollarwert zu nehmen und sie mit einer bitweisen OR-Operation zu kombinieren.
Eine effizientere Lösung wäre die Verwendung von Gruppierungen, zum Beispiel in Gruppen zu je 50 Euro. Dies würde unseren Prozess um das 50-Fache beschleunigen.
Das Problem lässt sich jedoch ebenfalls leicht durch eine speziell für diese Art von Anfragen entwickelte Darstellung lösen. In wissenschaftlichen Arbeiten wird sie als range-encoded Bitmaps bezeichnet.
In dieser Darstellung setzen wir nicht einfach ein Bit für einen bestimmten Wert (zum Beispiel 200), sondern kennzeichnen diesen Wert sowie alle Werte darüber. 200 und mehr. Das Gleiche gilt für 300: 300 und mehr. Und so weiter.
Mit dieser Darstellung können wir solche Suchanfragen beantworten, indem wir den Index nur zweimal durchsuchen. Zuerst erhalten wir eine Liste von Hotels, in denen der Preis unter 300 Euro liegt, und filtern dann diejenigen heraus, bei denen der Zimmerpreis unter 199 Euro liegt. Fertig.
Sie werden überrascht sein, aber sogar Geosuchen sind mit Bitmap-Indizes möglich. Der Trick besteht darin, eine geographische Darstellung zu verwenden, die Ihre Koordinaten mit einer geometrischen Form umgibt. Zum Beispiel S2 von Google. Die Form sollte aus drei oder mehr sich kreuzenden Linien bestehen, die nummeriert werden können. So können wir unsere Geosuche in mehrere Anfragen nach dem "Intervall" (entlang dieser nummerierten Linien) umwandeln.
Fertige Lösungen
Ich hoffe, ich habe Ihr Interesse geweckt und Sie haben ein weiteres nützliches Werkzeug in Ihrem Arsenal. Wenn Sie jemals etwas Ähnliches benötigen, wissen Sie, in welche Richtung Sie schauen sollten.
Allerdings haben nicht alle die Zeit, Geduld und Ressourcen, um Bitmap-Indizes von Grund auf neu zu erstellen. Besonders die fortschrittlicheren, die SIMD nutzen, zum Beispiel.
Zum Glück gibt es einige fertige Lösungen, die Ihnen helfen können.
Roaring Bitmaps
Zunächst gibt es die besagte Roaring Bitmaps-Bibliothek, von der ich bereits gesprochen habe. Sie enthält alle erforderlichen Container und Bitoperationen, die Sie benötigen, um einen vollständigen Bitmap-Index zu erstellen.
Leider verwenden derzeit keine Go-Implementierungen SIMD, was bedeutet, dass Go-Implementierungen weniger leistungsfähig sind als C-Implementierungen beispielsweise.
Pilosa
Ein weiteres Produkt, das Ihnen helfen kann, ist die Datenbank Pilosa, die im Wesentlichen nur Bitmap-Indizes verwendet. Es ist eine relativ neue Lösung, die jedoch schnell an Beliebtheit gewinnt.
Pilosa verwendet Roaring-Bitmaps und ermöglicht Ihnen, diese zu nutzen, wodurch die zuvor genannten Konzepte wie Gruppierung, rangekodierte Bitmaps und das Konzept von Feldern vereinfacht und erklärt werden.
Lassen Sie uns schnell einen Blick auf ein Beispiel werfen, wie Pilosa zum Beantworten einer Ihnen bereits bekannten Frage verwendet wird.
Das Beispiel ähnelt stark dem, was Sie zuvor gesehen haben. Wir erstellen einen Client für den Pilosa-Server, erstellen einen Index und die erforderlichen Felder, fügen dann Zufallsdaten mit Wahrscheinlichkeiten in unsere Felder ein und führen schließlich die vertraute Abfrage aus.
Danach verwenden wir NOT im Feld „expensive“, kreuzen das Ergebnis (oder AND) mit dem Feld „terrace“ und dem Feld „reservations“ und erhalten schließlich das Endergebnis.
Ich hoffe sehr, dass in naher Zukunft dieser neue Index-Typ – Bitmap-Indizes – auch in Datenbanken wie MySQL und PostgreSQL verfügbar sein wird.
Fazit
Falls Sie noch nicht eingeschlafen sind, danke. Ich musste viele Themen aufgrund der begrenzten Zeit kurz anreißen, aber ich hoffe, dass der Vortrag hilfreich war und vielleicht sogar motivierend.
Es ist gut, über Bitmap-Indizes Bescheid zu wissen, auch wenn sie Ihnen gerade nicht nützen. Lassen Sie sie ein weiteres Werkzeug in Ihrer Werkzeugkiste sein.
Wir haben verschiedene Tricks zur Leistungssteigerung für Go besprochen sowie die Aspekte, bei denen der Go-Compiler noch Schwierigkeiten hat. Diese Informationen sind absolut wichtig für jeden Go-Programmierer.
Das ist alles, was ich Ihnen mitteilen wollte. Vielen Dank!
Quelle: habr.com
