Bitmaps (auch als Bit-Arrays, Bit-Vektoren usw. bezeichnet) sind die Datenstruktur, die Ihnen sofort in den Sinn kommt, wenn es darum geht, boolesche Informationen für eine riesige Domäne in eine Kompaktdatei abzubilden Darstellung. Es ist eine sehr beliebte Datenstruktur, wenn Speicherplatz knapp ist:Betriebssystemkerne (Speicherseiten, Inodes usw.), digitale Bildverarbeitung usw.
Redis ist ein In-Memory-Datenstrukturserver und bietet Unterstützung für Bitmanipulationsoperationen. Allerdings gibt es in Redis keine spezielle Datenstruktur für Bitmaps. Stattdessen werden Operationen auf Bitebene auf der grundlegenden Redis-Struktur unterstützt:Strings. Jetzt beträgt die maximale Länge für Redis-Strings 512 MB. Somit ist die größte Domäne, die Redis als Bitmap abbilden kann, 2 (512 MB =2 Bytes =2 Bits).
Bitbezogene Operationen in Redis sind von zweierlei Art:Konstante Zeit (O(1)) z.B. Operationen zum Holen/Setzen eines bestimmten Bits und Operationen, die O(N) sind, die im Grunde auf einer Gruppe von Bits operieren. N ist in diesen Fällen die Länge der Bits, an denen die Operation arbeiten muss. Sehen wir uns einige Beispiele an.
Befehle
# SETBIT key offset value: Store bit value 'value' at offset 'offset' for 'key'. O(1) # Returns the original bit value stored at that offset. 127.0.0.1:6379> setbit k 10 1 (integer) 0 # GETBIT key offset: Fetch value of 'offset' in 'key'. O(1) 127.0.0.1:6379> getbit k 10 (integer) 1 127.0.0.1:6379> getbit k 11 (integer) 0 127.0.0.1:6379> getbit k 0 (integer) 0 127.0.0.1:6379> setbit k 9 1 (integer) 0 127.0.0.1:6379> setbit k 8 1 (integer) 0 # And since it is still a generic String, here's a get. 127.0.0.1:6379> get k "\x00\xe0" # "\x00\xe0" -> "0000 0000 111" # BITCOUNT key [start end]: Number of set bits in the range. O(N) # IMPORTANT: start & end are bytes not bits 127.0.0.1:6379> bitcount k (integer) 3 127.0.0.1:6379> set m "meow" OK # meow -> 01101101 01100101 01101111 01110111 127.0.0.1:6379> bitcount m (integer) 21 # BITPOS key bit [start] [end]: 1st position of 1 or 0 in the key in range. O(N) 127.0.0.1:6379> SET mykey "\xff\xf0\x00" OK 127.0.0.1:6379> BITPOS mykey 0 (integer) 12
Außerdem gibt es Operatoren, die auf dem Schlüssel selbst arbeiten, dem BITOP Der Operator wird für bitweise logische Operationen zwischen mehreren Schlüsseln verwendet.
# BITOP operation destkey key [key ...]. O(N) # operation can be AND, OR, XOR and NOT 127.0.0.1:6379> set a "\xff\xff" OK 127.0.0.1:6379> bitop not nota a (integer) 2 127.0.0.1:6379> get nota "\x00\x00" 127.0.0.1:6379> set b "\x0f\x0f" OK 127.0.0.1:6379> set c "\xf0\xf0" OK 127.0.0.1:6379> BITOP OR orbc b c (integer) 2 127.0.0.1:6379> get orbc "\xff\xff" 127.0.0.1:6379> BITOP AND andbc b c (integer) 2 127.0.0.1:6379> get andbc "\x00\x00" 127.0.0.1:6379> BITOP XOR xorbc b c (integer) 2 127.0.0.1:6379> get xorbc "\xff\xff"
Interna
Da Bitmap-Operationen keine eigene Datenstruktur haben, muss keine spezielle Datenstruktur beschrieben werden. Die Redis-Strings selbst sind als binäre sichere Strings implementiert. Die String-Datenstruktur von Redis wird intern als Simple Dynamic String (SDS) bezeichnet. Es ist im Wesentlichen ein natives char [] mit einigen zusätzlichen Buchhaltungsinformationen. Einzelheiten zur Implementierung finden Sie hier.
Die Implementierung der Bitmap-Funktionen befindet sich in der Datei bitops.c .
P.S.:Angesichts der Bedeutung von Bitmanipulationsalgorithmen für kritische Betriebssystem- und Grafikfunktionen bieten die meisten Architekturen spezielle Anweisungen für solche Operationen. Ein guter Ort, um sich über verschiedene interessante Computerarithmetikalgorithmen zu informieren, ist der zeitlose Klassiker Hacker’s Delight.
Anwendungen
Dieser beliebte GetSpool-Blog ist ein großartiges Beispiel für die Verwendung von Bitmaps für Echtzeitanalysen über einen großen Datensatz. Es ist auch ein Beispiel für den klassischen Anwendungsfall einer Bitmap:boolesche Informationen einer extrem großen Domain auf (relativ) kleinem Raum zu speichern und dabei eine anständige Leistung beizubehalten.
Größe ist normalerweise ein Problem für wirklich große Bitmaps, da die nützlichsten Operationen darüber O(N) sind. Um das Arbeiten mit großen Schlüsseln zu vermeiden, empfiehlt die Redis-Dokumentation, große Schlüssel in mehrere kleinere aufzuteilen. Die BITCOUNT-Leistung bleibt akzeptabel, bis der Schlüssel groß wird. An diesem Punkt wird empfohlen, entweder die Schlüssel aufzuteilen oder die Bereichsargumente für die inkrementelle Abfrage zu verwenden. Die Empfehlung zum Umgang mit langsamen BITOP-Vorgängen besteht darin, sie auf Slaves auszuführen. Daher ist es im Allgemeinen sinnvoll, mit mittelgroßen Schlüsseln umzugehen und zukünftiges potenzielles Wachstum zu planen, indem Schlüssel in mehrere Schlüssel aufgeteilt werden.
Redis-Sets vs. Redis-Bitmap
Die Art der Funktionalität, die von Redis-Sets und den Bitmap-Operationen bereitgestellt wird, ist ähnlich. Daher ist es oft verwirrend, welcher der beiden Ansätze besser ist. Nun, es hängt wirklich von der genauen Art des Anwendungsfalls ab. Offensichtlich gilt diese Diskussion nur für die Art von Operationen, die sowohl Mengen als auch Bitmaps erreichen können.
Redis Sets sind im Allgemeinen effizient und lassen sich gut skalieren und sollten die Datenstruktur der Wahl sein, bis ihre Größe unhaltbar wird. Redis-Sets sind auch einfacher zu verwalten, Programmieren und Debuggen würde für die meisten Anwendungen gut funktionieren. Die Benutzerfreundlichkeit von Sets sollte nicht unterschätzt werden:Code, der Bitmaps manipuliert, ist normalerweise schwer zu lesen, zu verstehen, zu debuggen und zu warten. Selbst wenn die Domäne sehr groß ist, können Sätze immer noch angemessen sein. Für z.B. Wenn eine Anwendung die täglichen Besuche einer beliebten E-Commerce-Website verfolgen soll, können die Ergebnisse dennoch gut in eine Reihe passen, da normalerweise nur 5-10 % der gesamten Benutzerbasis die Website täglich besuchen. Dies ändert sich offensichtlich für eine Website, bei der erwartet wird, dass sich 60 % der gesamten Benutzerbasis täglich anmelden. Dann werden Bitmaps angesichts der Größe und Leistung logischer bitweiser Operationen über eine große Anzahl von Schlüsseln relevanter. Redis-Sets haben auch den entscheidenden Vorteil, dass IDs nicht auf Bit-Offsets abgebildet werden müssen. Wenn Ihre Werte aus einer Domäne stammen, die größer als 2 ist, müssen Redis-Sätze ebenfalls einfacher zu verwenden sein, als Mechanismen zum Aufteilen der Domäne für Bitmaps herauszufinden.
Analytics für ein MOOC
Hier ist ein erfundenes (aber echtes!) Beispiel für einen Ort, an dem man Redis-Bitmap-Operationen anwenden könnte. Angenommen, Sie betreiben ein sehr beliebtes Online-MOOC, für das sich Hunderttausende von Studenten eingeschrieben haben. Das akademische Team, das den Kurs moderiert, möchte ein Dashboard, auf dem es den Echtzeitstatus des Fortschritts der Studenten sowie den allgemeinen Hintergrund der eingeschriebenen Studenten sehen kann. Sie entscheiden sich, dies über Redis-Bitmap-Operationen zu implementieren. Hier ist ein Schritt-für-Schritt-Ansatz dafür.
- Erstellen Sie einen Plan für die Zuordnung zwischen Schüler-ID und Bitmap-Offset. Es könnte so einfach sein, dass die ID der Offset in der Bitmap ist.
- Erstellen und füllen Sie verschiedene demografische Bitmaps, sobald der Kurs beginnt. Für z.B. Studierende, die in anderen MOOCs derselben Universität, Bildungsstufe, Geschlecht usw. eingeschrieben sind
- Während der Kurs fortschreitet, können Sie jetzt neue Bitmaps erstellen, um den Kursfortschritt aufzuzeichnen. Für z.B. Studenten, die alle Vorlesungen der 1. Woche angeschaut haben, Studenten, die alle Aufgaben der 1. Woche erledigt haben usw.
- Das Erstellen von Echtzeitanalysen basierend auf diesen Schlüsseln wäre eine sehr einfache Übung und kann auf einer Drag-and-Drop-Benutzeroberfläche durchgeführt werden. Für z.B.
- Ein Professor, der sehen möchte, wie viele Studenten die Vorlesungen für Woche 1 (A) gesehen, aber die Aufgabe für Woche 1 (B) nicht abgeschlossen haben:Betreiber:BITOP. Operation:A UND (NICHT B).
- Schüler, der alle Aufgaben für Woche 1 (A), Woche 2 (B), Woche 3 (C) und Woche 4 (D) abgeschlossen hat:Bediener:BITOP. Operation A UND B UND C UND D. Angenommen, das sind die Leute, die den Kurs bestanden haben.
- Alle männlichen Studenten (M), die den Kurs bestanden haben (wie oben berechnet, sagen wir P):Operator:BITOP. Betrieb:M UND P.
- Anzahl der Schüler, die den Kurs bestanden haben:BITCOUNT P.
In ähnlicher Weise können beliebig viele interessante Kohorten als Bitmaps eingerichtet und solche Permutationen darauf ausgeführt werden.
Fußnote
Andere Posts in unserer Reihe Redis-Datenstrukturen:
- Sätze
- Hashes
- Sortierte Sätze
