Einleitungswort
Ich habe diesen Vortrag auf Englisch auf der Konferenz GopherCon Russland 2019 in Moskau und auf Russisch bei einem Meetup in Nischni Nowgorod gehalten. Er handelt von einem Bitmap-Index – weniger verbreitet als ein B-Baum, aber ebenso interessant. Ich teile des Vortrags auf der Konferenz auf Englisch und einer schriftlichen Transkription auf Russisch.
Wir werden uns ansehen, wie ein Bitmap-Index funktioniert, wann er besser ist, wann schlechter als andere Indizes und in welchen Fällen er erheblich schneller ist; wir werden sehen, in welchen beliebten DBMS bereits Bitmap-Indizes vorhanden sind; und wir versuchen, unseren eigenen in Go zu schreiben. Zum „Dessert“ werden wir fertige Bibliotheken nutzen, um unsere superschnelle, spezialisierte Datenbank zu erstellen.
Ich hoffe sehr, dass meine Arbeit für Sie nützlich und interessant sein wird. Lassen Sie uns beginnen!
Einführung
Hallo zusammen! Es ist jetzt sechs Uhr abends, wir sind alle super müde. Eine großartige Gelegenheit, um über die langweilige Theorie von Datenbankindizes zu sprechen, oder? Keine Sorge, ich habe hier und da einige Zeilen Quellcode.
Wenn wir ernsthaft sind, ist der Vortrag voller Informationen und wir haben nicht viel Zeit. Also lassen Sie uns anfangen.
Heute werde ich über Folgendes sprechen:
- Was sind Indizes;
- Was ist ein Bitmap-Index;
- Wo er verwendet wird und wo er NICHT verwendet wird und warum;
- Einfache Implementierung in Go und ein wenig Kämpfen mit dem Compiler;
- Etwas weniger einfache, aber viel leistungsfähigere Implementierung in Go-Assembler;
- Die „Probleme“ von Bitmap-Indizes;
- Vorhandene Implementierungen.
Was sind also Indizes?
Ein Index ist eine separate Datenstruktur, die wir zusätzlich zu den Hauptdaten halten und aktualisieren. Er 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 enorme Menge an Daten und lineare Komplexität ist zu langsam. Idealerweise würden wir logarithmische oder konstante Komplexität wünschen.
Das ist ein riesiges, komplexes Thema, gefüllt mit Nuancen und Kompromissen, aber nach Jahrzehnten der Entwicklung und Forschung über verschiedene Datenbanken bin ich bereit zu behaupten, dass es nur wenige weithin verwendete Ansätze zur Erstellung von DB-Indizes gibt.
Der erste Ansatz besteht darin, den Suchbereich hierarchisch zu reduzieren und ihn in kleinere Teile zu unterteilen.
In der Regel tun wir dies mithilfe verschiedener Arten von Bäumen. Ein Beispiel könnte eine große Box mit Materialien in Ihrem Schrank sein, in der sich kleinere Kisten mit Materialien zu verschiedenen Themen befinden. Wenn Sie Materialien benötigen, werden Sie sicherlich in der Box mit der Aufschrift "Materialien" suchen, und nicht in der mit der Aufschrift "Kekse", oder?
Der zweite Ansatz besteht darin, das gewünschte Element oder die Gruppe von Elementen sofort zu identifizieren. Wir tun dies in Hash-Maps oder in umgekehrten Indizes. Die Verwendung von Hash-Maps ähnelt sehr dem vorherigen Beispiel: Statt einer Box mit Boxen haben Sie in Ihrem Schrank eine Menge kleiner Kisten mit finalen Objekten.
Der dritte Ansatz besteht darin, die Notwendigkeit einer Suche zu eliminieren. Dies erreichen wir mit Hilfe von Bloom-Filtern oder Cuckoo-Filtern. Die ersten geben sofort eine Antwort, sodass Sie nicht suchen müssen.
Der letzte Ansatz besteht darin, die gesamte Leistung moderner Hardware optimal zu nutzen. Genau das tun wir mit Bitmap-Indizes. Ja, bei ihrer Verwendung müssen wir manchmal den gesamten Index durchlaufen, aber wir tun dies äußerst effizient.
Wie ich bereits sagte, ist das Thema Datenbankindizes umfangreich und voller Kompromisse. Das bedeutet, dass wir manchmal mehrere Ansätze gleichzeitig verwenden können: Wenn wir die Suche noch weiter beschleunigen müssen oder wenn wir alle möglichen Suchtypen abdecken müssen.
Heute werde ich über den am wenigsten bekannten Ansatz aus den genannten sprechen – über 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 bereits über 400 Millionen Nutzer weltweit und viele Funktionen, die darauf abzielen, die besten Partien für sie zu finden. Dies tun wir mit Hilfe von maßgeschneiderten Dienstleistungen, die unter anderem auch Bitmap-Indizes verwenden.
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 solcher Bitmaps, die Entitäten (wie Personen) und ihre Eigenschaften oder Parameter (Alter, Augenfarbe usw.) repräsentieren, sowie aus einem Algorithmus, der bitweise Operationen (AND, OR, NOT) verwendet, um auf eine Suchanfrage zu reagieren.
Es wird gesagt, dass Bitmap-Indizes am besten geeignet und sehr leistungsfähig für Fälle sind, in denen Suchen Anfragen über viele Spalten mit geringer Kardinalität kombinieren (stellen Sie sich 'Augenfarbe' oder 'Familienstand' im Gegensatz zu etwas wie 'Entfernung zum Stadtzentrum' vor). Aber später werde ich zeigen, dass sie auch in Fällen mit hoher Kardinalität hervorragend funktionieren.
Betrachten wir ein einfaches Beispiel für einen Bitmap-Index.
Stellen Sie sich vor, wir haben eine Liste von Moskauer Restaurants mit binären Eigenschaften wie diesen:
- nahe der U-Bahn (near metro);
- mit privatem Parkplatz (has private parking);
- mit Terrasse (has terrace);
- mit Tischreservierungen (accepts reservations);
- vegan-freundlich (vegan friendly);
- teuer (expensive).
Lassen Sie uns jedem Restaurant eine fortlaufende Nummer ab 0 geben und Speicher für 6 Bitmaps reservieren (eine für jede Eigenschaft). Dann füllen wir diese Bitmaps abhängig davon aus, ob das Restaurant diese Eigenschaft hat oder nicht. Wenn das Restaurant 4 eine Terrasse hat, wird das Bit Nr. 4 im Bitmap 'mit Terrasse' auf 1 (wenn keine Terrasse vorhanden ist, auf 0) gesetzt.
Jetzt haben wir den einfachsten möglichen Bitmap-Index, den wir nutzen können, um auf Anfragen wie diese zu antworten:
- „Zeig mir Restaurants, die für Vegetarier geeignet sind“;
- „Zeig mir preiswerte Restaurants mit Terrasse, in denen man einen Tisch reservieren kann.“
Wie? Lassen Sie uns einen Blick darauf werfen. Die erste Anfrage ist sehr einfach. Alles, was wir tun müssen, ist, das Bitmap 'vegan-freundlich' zu nehmen und es in eine Liste von Restaurants umzuwandeln, deren Bits gesetzt sind.
Die zweite Anfrage ist etwas komplizierter. Wir müssen die bitweise NOT-Operation auf die Bitmap „teuer“ anwenden, um eine Liste von günstigen Restaurants zu erhalten, dann müssen wir sie mit der Bitmap „Reservierung möglich“ und das Ergebnis mit der Bitmap „Terrasse vorhanden“ verknüpfen. Die resultierende Bitmap enthält eine Liste von Einrichtungen, die allen unseren Kriterien entsprechen. In diesem Beispiel ist dies nur das Restaurant „Jungend“.
Hier gibt es viel Theorie, aber keine Sorge, wir werden sehr bald den Code sehen.
Wo werden Bitmap-Indizes verwendet?
Wenn Sie nach Bitmap-Indizes googeln, werden 90 % der Antworten mehr oder weniger mit Oracle DB verbunden sein. Aber andere DBMS unterstützen sicherlich auch so etwas Cooles, oder? Nicht ganz.
Lassen Sie uns die Liste der Hauptverdächtigen durchgehen.
MySQL unterstützt derzeit keine Bitmap-Indizes, hat jedoch einen Vorschlag zur Hinzufügung dieser Option gegeben ().
PostgreSQL unterstützt keine Bitmap-Indizes, verwendet jedoch einfache Bitmaps und bitweise Operationen, um Suchergebnisse aus mehreren anderen Indizes zu kombinieren.
Tarantool hat Bitset-Indizes, die eine einfache Suche ermöglichen.
Redis verfügt über einfache bitweise Felder) ohne Suchmöglichkeit.
MongoDB unterstützt derzeit keine Bitmap-Indizes, hat jedoch auch einen Vorschlag zur Hinzufügung dieser Option gemacht.
Elasticsearch verwendet Bitmaps intern).
- Aber in unserem Haus ist ein neuer Nachbar eingezogen: Pilosa. Es handelt sich um eine neue nicht-relationale Datenbank, die in Go geschrieben ist. Sie besteht nur aus bitmap-indizes und basiert alles darauf. Wir werden später darüber sprechen.
Implementierung in Go
Aber warum werden Bitmap-Indizes 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 Grunde einfach Datenstücke. In Go verwenden wir dafür Byte-Slices.
Wir haben eine Bitmap für eine Restaurantmerkmale, und jeder Bit in der 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älligen, aber mit einer bestimmten Wahrscheinlichkeit, dass das Restaurant eine bestimmte Eigenschaft hat. Zum Beispiel glaube ich, dass es in Moskau sehr wenige Restaurants gibt, in denen man keinen Tisch reservieren kann, und ich schätze, dass etwa 20 % der Einrichtungen für Vegetarier geeignet sind.
Die zweite Funktion wird das Bitmap in eine Liste von Restaurants umwandeln.
Um auf die Anfrage „Zeig mir günstige Restaurants, die eine Terrasse haben und in denen man einen Tisch reservieren kann“ zu antworten, benötigen wir zwei bitweise Operationen: NOT und AND.
Wir können unseren Code ein wenig vereinfachen, indem wir eine komplexere Operation, AND NOT, verwenden.
Wir haben Funktionen für jede dieser Operationen. Beide gehen durch die Slices, nehmen die entsprechenden Elemente aus jedem, kombinieren sie mit der bitweisen Operation und legen das Ergebnis in das Ergebnis-Slice.
Und jetzt können wir unsere Bitmaps und Funktionen nutzen, um auf die Suchanfrage zu antworten.
Die Leistung ist nicht besonders hoch, auch wenn die Funktionen sehr einfach sind und wir durch das Vermeiden von neuen Ergebnis-Slices bei jedem Funktionsaufruf recht gut abgeschätzt haben.
Nach ein wenig Profiling mit pprof habe ich bemerkt, dass der Go-Compiler eine sehr einfache, aber sehr wichtige Optimierung übersehen hat: die Funktionsinlining.
Das Problem ist, dass der Go-Compiler große Angst vor Schleifen hat, die über Slices iterieren, und kategorisch verhindert, dass Funktionen, die solche Schleifen enthalten, inlined werden.
Aber ich habe keine Angst und kann den Compiler austricksen, indem ich goto anstelle einer Schleife benutze, wie in alten Zeiten.
Und wie Sie sehen, inline der Compiler nun bereitwillig unsere Funktion! Insgesamt sparen wir etwa 2 Mikrosekunden. Nicht schlecht!
Der zweite Engpass ist leicht zu erkennen, wenn man sich den Assemblerausgang genau ansieht. Der Compiler hat eine Überprüfung der Slice-Grenzen direkt in unsere heißeste Schleife eingefügt. Der Grund ist, dass Go eine sichere Sprache ist, und der Compiler befürchtet, dass meine drei Argumente (drei Slices) unterschiedliche Größen haben. Das würde theoretisch die Möglichkeit eines sogenannten Buffer Overflows schaffen.
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.
Sieht der Compiler dies, überspringt er die Überprüfung erfreut, und wir sparen dadurch noch 500 Nanosekunden.
Große Batches
Okay, wir haben es geschafft, eine gewisse Leistung aus unserer einfachen Implementierung herauszuholen, aber dieses Ergebnis ist in Wirklichkeit viel schlechter, als es mit der derzeitigen 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 byteweise Operationen durch. Wir können unseren Code ganz einfach so optimieren, dass er mit 8-Byte-Stücken arbeitet, indem wir UInt64-Slices verwenden.
Wie Sie sehen, hat diese kleine Änderung unsere Programme um das Achtfache beschleunigt, indem sie die Batch-Größe vergrößert hat. Der Gewinn könnte als linear bezeichnet werden.
Implementierung in Assembly
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 Instruktion, viele Daten) bezeichnet, und der Prozess, der den Code so umformt, dass er solche Operationen verwendet, wird Vektorisierung genannt.
Leider ist der Go-Compiler ein alles andere als ausgezeichneter Schüler in der Vektorisierung. Derzeit ist der einzige Weg, um Go-Code zu vektorisieren, die Datenoperationen manuell unter Verwendung von Go-Assembly zu schreiben.
Go-Assembly ist ein seltsames Tier. Sie wissen wahrscheinlich, dass Assembly etwas ist, das stark an die Architektur des Computers gebunden ist, für den Sie schreiben, aber das ist in Go nicht der Fall. Go-Assembly ähnelt eher einer IRL (Intermediate Representation Language) oder einer Zwischenrepräsentation: Sie ist praktisch plattformunabhängig. Rob Pike hielt vor einigen Jahren einen großartigen Über dieses Thema auf der GopherCon in Denver.
Darüber hinaus verwendet Go ein ungewöhnliches Format namens 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-Assembly nicht die angenehmste Aufgabe ist.
Aber glücklicherweise gibt es bereits zwei hochrangige Tools, die uns beim Schreiben von Go-Assembly helfen: PeachPy und avo. Beide Werkzeuge generieren Go-Assembly aus höhergradigem Code, der in Python bzw. Go geschrieben ist.
Diese Dienstprogramme erleichtern Dinge wie die Registerzuweisung, das Schreiben von Schleifen und insgesamt den Einstieg in die Welt der Assemblersprachen in Go.
Wir werden avo verwenden, sodass unsere Programme fast normale Go-Programme sind.
So sieht das einfachste Beispiel eines Avo-Programms aus. Wir haben eine Funktion main(), die in sich die Funktion Add() definiert, deren Zweck das Addieren von zwei Zahlen ist. Hier gibt es Hilfsfunktionen, um Parameter nach Namen zu erhalten, und um eines der verfügbaren und geeigneten Prozessorregister zu bekommen. Jede Prozessoroperation hat eine entsprechende Funktion in Avo, wie man an ADDQ sehen kann. Und schließlich sehen wir eine Hilfsfunktion zum Speichern des Ergebnisses.
Durch den Aufruf von go generate führen wir das Avo-Programm aus, und am Ende werden zwei Dateien generiert:
- add.s mit dem resultierenden Code in Go-Assembler;
- stub.go mit den Funktionsprototypen für die Verbindung der beiden Welten: Go und Assembler.
Jetzt, da wir gesehen haben, was Avo tut, schauen wir uns unsere Funktionen an. Ich habe sowohl die skalare als auch die vektorielle (SIMD) Version der Funktionen implementiert.
Zuerst schauen wir uns die skalarischen Versionen an.
Wie im vorherigen Beispiel fragen wir nach einem freien und passenden allgemeinen Register, wir müssen keine Offsets und Größen für Argumente berechnen. 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 zu täuschen, aber jetzt machen wir das von Anfang an. Die Sache ist die, dass Schleifen ein höheres Konzept sind. Im Assembly haben wir hingegen nur Labels und Sprünge.
Der verbleibende Code sollte bereits bekannt und klar sein. Wir emulieren die Schleife mit Labels und Sprüngen, nehmen einen kleinen Teil der Daten aus unseren beiden Slices, kombinieren sie mit einer bitweisen Operation (AND NOT in diesem Fall) und legen das Ergebnis dann in den Ergebnisslice. Das ist alles.
So sieht der endgültige Assemblercode aus. Wir mussten keine Offsets und Größen berechnen (grün hervorgehoben) oder auf die verwendeten Register achten (rot hervorgehoben).
Wenn man die Leistung der Assembly-Implementierung mit der besten Implementierung in Go vergleicht, stellt man fest, dass sie gleich ist. Das ist zu erwarten. Wir haben nichts Besonderes gemacht – wir haben nur reproduziert, was der Go-Compiler tun würde.
Leider können wir den Compiler nicht dazu bringen, unsere in Assembly geschriebenen Funktionen zu inlinisieren. Der Go-Compiler hat derzeit diese Möglichkeit nicht, obwohl der Wunsch, sie hinzuzufügen, schon seit einiger Zeit besteht.
Genau aus diesem Grund ist es unmöglich, irgendwelche Vorteile aus kleinen Funktionen in Assembly zu ziehen. Wir müssen entweder große Funktionen schreiben, das neue Paket math/bits verwenden oder Assembly ganz vermeiden.
Lassen Sie uns nun die Vektorversionen unserer Funktionen betrachten.
Für dieses Beispiel habe ich mich entschieden, AVX2 zu verwenden, daher werden wir Operationen verwenden, die mit 32-Byte-Stücken arbeiten. Die Struktur des Codes sieht sehr ähnlich aus wie die skalarer Version: das Laden der Parameter, die Aufforderung, uns ein freies allgemeines Register zur Verfügung zu stellen usw.
Eine der Neuerungen besteht darin, dass breitere Vektoroperationen spezielle breite Register verwenden. Im Falle von 32-Byte-Stücken sind das Register mit dem Präfix Y. Deshalb sehen Sie die Funktion YMM() im Code. Wenn ich AVX-512 mit 64-Bit-Stücken verwendet hätte, wäre das Präfix Z gewesen.
Eine zweite Neuerung besteht darin, dass ich beschlossen habe, eine Optimierung zu verwenden, die als Loop Unrolling bezeichnet wird, also acht Schleifenoperationen manuell auszuführen, bevor ich zum Schleifenanfang springe. Diese Optimierung reduziert die Anzahl der Verzweigungen im Code und ist durch die Anzahl der verfügbaren freien Register begrenzt.
Und wie ist es um die Leistung bestellt? Sie ist hervorragend! Wir haben eine Beschleunigung von etwa sieben Mal im Vergleich zur besten Lösung in Go erzielt. Beeindruckend, oder?
Doch selbst diese Implementierung könnte potenziell durch den Einsatz von AVX-512, Prefetching oder JIT (Just-in-Time-Compiler) für den Anfrageplaner beschleunigt werden. Aber das ist auf jeden Fall ein Thema für einen eigenen Vortrag.
Probleme mit Bitmap-Indizes
Jetzt, da wir die einfache Implementierung des Bitmap-Indexes in Go und die weitaus leistungsfähigere in Assembly 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 behaupten, dass diese nicht mehr relevant sind. Lassen Sie uns nicht tief in jedes dieser Probleme eintauchen, sondern sie oberflächlich betrachten.
Das Problem der hohen Kardinalität
Uns wird gesagt, dass Bitmap-Indizes nur für Felder mit niedriger Kardinalität geeignet sind, also für solche mit wenigen Werten (zum Beispiel Geschlecht oder Augenfarbe), und der Grund dafür ist, dass die gewöhnliche Darstellung solcher Felder (ein Bit pro Wert) bei hoher Kardinalität zu viel Speicherplatz beanspruchen würde und darüber hinaus schlecht (selten) gefüllt wäre.
Manchmal können wir eine andere Darstellung verwenden, zum Beispiel die Standarddarstellung, die wir zur Darstellung von Zahlen verwenden. Aber gerade das Auftreten von Komprimierungsalgorithmen hat alles verändert. In den letzten Jahrzehnten haben Wissenschaftler und Forscher eine Vielzahl von Komprimierungsalgorithmen für Bitmaps entwickelt. Ihr Hauptvorteil besteht darin, dass es nicht erforderlich ist, Bitmaps zum Durchführen von Bitoperationen zu dekomprimieren — wir können Bitoperationen direkt an komprimierten Bitmaps durchführen.
In letzter Zeit sind auch hybride Ansätze aufgetaucht, wie zum Beispiel Roaring Bitmaps. Sie verwenden gleichzeitig drei verschiedene Darstellungen für Bitmaps — eigentliche Bitmaps, Arrays und so genannte Bit Runs — und balancieren zwischen ihnen, um die Leistung zu maximieren und den Speicherverbrauch zu minimieren.
Sie können Roaring Bitmaps in den beliebtesten Anwendungen antreffen. Es gibt bereits eine große Anzahl von Implementierungen für verschiedene Programmiersprachen, einschließlich mehr als drei Implementierungen für Go.
Ein weiterer Ansatz, der uns helfen kann, mit hoher Kardinalität umzugehen, nennt sich Binning. Stellen Sie sich vor, Sie haben ein Feld, das die Körpergröße einer Person darstellt. Größe ist eine Fließkommazahl, aber wir Menschen denken nicht in diesen Begriffen. Für uns gibt es keinen Unterschied zwischen einer Körpergröße von 185,2 cm und 185,3 cm.
Wir können also ähnliche Werte innerhalb von 1 cm gruppieren.
Und wenn wir zudem wissen, dass es sehr wenig Menschen mit einer Größe von 50 cm oder weniger und 250 cm oder mehr gibt, können wir im Wesentlichen ein Feld mit unendlicher Kardinalität in ein Feld mit einer Kardinalität von etwa 200 Werten umwandeln.
Natürlich können wir bei Bedarf zusätzliche Filterungen auch danach durchführen.
Das Problem mit der hohen Bandbreite
Das nächste Problem der Bitmap-Indizes besteht darin, dass deren Aktualisierung sehr kostspielig sein kann.
Datenbanken müssen es ermöglichen, Daten zu aktualisieren, während potenziell Hunderte anderer Anfragen auf diese Daten zugreifen. Wir benötigen Lock-Mechanismen, um Probleme mit gleichzeitigen Datenzugriffen oder andere Probleme des gleichzeitigen Zugriffs zu vermeiden. Wo es ein großes Lock gibt, besteht das Problem der Lock-Konkurrenz, wenn dieses Lock zum Engpass wird.
Dieses Problem kann durch Sharding oder die Verwendung von versionierten Indizes gelöst oder umgangen werden.
Sharding ist ein einfaches und allgemein bekanntes Konzept. Sie können einen Bitmap-Index genauso sharden, wie Sie es mit anderen Daten tun würden. Anstelle eines großen Locks erhalten Sie viele kleine Locks und beseitigen damit die Lock-Konkurrenz.
Eine zweite Lösung für das Problem ist die Verwendung von versionierten Indizes. Sie können eine Kopie des Index haben, die Sie zum Suchen oder Lesen verwenden, und eine andere, die Sie zum Schreiben oder Aktualisieren verwenden. In bestimmten Zeitintervallen (zum Beispiel alle 100 ms oder 500 ms) duplizieren Sie diese und tauschen sie aus. Natürlich ist dieser Ansatz nur dann anwendbar, wenn Ihre Anwendung mit einem etwas veralteten Suchindex arbeiten kann.
Diese beiden Ansätze können gleichzeitig verwendet werden: Sie können einen sharden versionierten Index haben.
Komplexere Anfragen
Das letzte Problem der Bitmap-Indizes besteht darin, dass sie, wie man uns sagt, schlecht für komplexere Anfragearten geeignet sind, z.B. „Intervall“-Anfragen.
Das ist wahr, wenn man darüber nachdenkt, sind bitweise Operationen wie AND, OR usw. nicht besonders geeignet für Anfragen wie „Zeige mir Hotels mit Preisen zwischen 200 und 300 Dollar pro Nacht“.
Eine naive und sehr unüberlegte Lösung wäre es, die Ergebnisse für jeden Dollarbetrag zu nehmen und sie durch eine bitweise OR-Operation zu kombinieren.
Eine etwas bessere Lösung wäre es, Gruppen zu verwenden. Zum Beispiel Gruppen zu je 50 Dollar. Das würde unseren Prozess um das 50-Fache beschleunigen.
Das Problem lässt sich jedoch auch leicht lösen, indem man eine Darstellung verwendet, die speziell für diese Art von Anfragen erstellt wurde. In wissenschaftlichen Arbeiten wird sie als range-encoded bitmaps bezeichnet.
In einer solchen Darstellung setzen wir nicht einfach ein Bit für einen bestimmten Wert (z. B. 200), sondern für diesen Wert und alles, was darüber liegt. 200 und darüber. Dasselbe gilt für 300: 300 und darüber. Und so weiter.
Mit dieser Darstellung können wir auf solche Suchanfragen reagieren, indem wir den Index nur zweimal durchlaufen. Zuerst erhalten wir eine Liste von Hotels, in denen der Zimmerpreis weniger als 300 Dollar beträgt, und werfen dann die heraus, bei denen der Zimmerpreis weniger als 199 Dollar beträgt. Fertig.
Sie werden erstaunt sein, aber sogar Geosuchen sind mithilfe von Bitmap-Indizes möglich. Der Trick besteht darin, eine geographische Darstellung zu verwenden, die Ihre Koordinaten durch eine geometrische Form umschließt. Zum Beispiel S2 von Google. Die Form muss so dargestellt werden, dass sie aus drei oder mehr sich kreuzenden Linien besteht, die nummeriert werden können. So können wir unsere Geosuche in mehrere 'Intervall'-Anfragen (nach diesen nummerierten Linien) umwandeln.
Fertige Lösungen
Ich hoffe, ich habe Ihr Interesse ein wenig geweckt und Sie haben ein weiteres nützliches Werkzeug in Ihrem Arsenal. Wenn Sie jemals etwas Ähnliches tun müssen, werden Sie wissen, in welche Richtung Sie suchen müssen.
Allerdings haben nicht alle die Zeit, Geduld und Ressourcen, um Bitmap-Indizes von Grund auf neu zu erstellen. Besonders die fortgeschritteneren, die SIMD verwenden, zum Beispiel.
Glücklicherweise gibt es einige fertige Lösungen, die Ihnen helfen werden.
Roaring Bitmaps
Zunächst gibt es die erwähnte Roaring Bitmaps-Bibliothek, die alle notwendigen Container und Bitoperationen enthält, die Sie benötigen, um einen vollständigen Bitmap-Index zu erstellen.
Leider verwendet derzeit keine der Go-Implementierungen SIMD, was bedeutet, dass die Go-Implementierungen weniger leistungsfähig sind als die Implementierungen in C, zum Beispiel.
Pilosa
Ein weiteres Produkt, das Ihnen helfen könnte, ist die Datenbank Pilosa, die im Grunde genommen nur Bitmap-Indizes enthält. Es handelt sich um eine relativ neue Lösung, die jedoch schnell an Beliebtheit gewinnt.
Pilosa verwendet Roaring Bitmaps in ihrem Inneren und ermöglicht es Ihnen, diese zu verwenden, und vereinfacht und erklärt all die Dinge, die ich oben erwähnt habe: Gruppierung, range-encoded Bitmaps, das Konzept des Feldes usw.
Lassen Sie uns schnell einen Blick auf ein Beispiel für die Verwendung von Pilosa werfen, um eine Ihnen bereits bekannte Frage zu beantworten.
Das Beispiel ähnelt sehr dem, was Sie zuvor gesehen haben. Wir erstellen einen Client für den Pilosa-Server, definieren einen Index sowie die erforderlichen Felder, fügen dann zufällige Daten mit Wahrscheinlichkeiten in unsere Felder ein und führen schließlich die vertraute Abfrage aus.
Danach verwenden wir NOT auf dem Feld "expensive", schneiden das Ergebnis (oder AND-Verknüpfung) mit dem Feld "terrace" und dem Feld "reservations" zusammen. Schließlich erhalten wir das endgültige Ergebnis.
Ich hoffe sehr, dass in naher Zukunft auch in Datenbanksystemen wie MySQL und PostgreSQL dieser neue Index-Typ – Bitmap-Indizes – verfügbar sein wird.
Fazit
Wenn Sie noch nicht eingeschlafen sind, danke. Ich musste viele Themen nur kurz anreißen aufgrund der begrenzten Zeit, aber ich hoffe, dass der Vortrag hilfreich und vielleicht sogar motivierend war.
Es ist gut, über Bitmap-Indizes Bescheid zu wissen, auch wenn Sie sie gerade jetzt nicht benötigen. Lassen Sie sie ein weiteres Werkzeug in Ihrer Toolbox sein.
Wir haben verschiedene Tricks zur Leistungssteigerung für Go betrachtet und die Dinge, mit denen der Go-Compiler derzeit noch nicht sehr gut zurechtkommt. Das ist auf jeden Fall etwas, das jeder Go-Programmierer wissen sollte.
Das ist alles, was ich erzählen wollte. Vielen Dank!
Quelle: habr.com
