Ein einzelner SETBIT-Aufruf mit Offset vier Milliarden benötigt der Bitmap-Inhalt rund 500 Millionen Byte, auch wenn danach nur ein einziges Bit gesetzt ist. Der Grund liegt in der Speicherform: Redis legt Bitmaps als gewöhnlichen String ab, bei dem Bit i der Bitmap dem Bit i des Strings entspricht.
Mit Redis 8.12 soll sich das ändern. Komprimierte Bitmaps im Roaring-Format kommen als eigener Typ in die Datenbank, aktivierbar über eine Konfigurationszeile. Wer Bitsets für Nutzergruppen, Kohorten oder Feature-Flags verwendet, bekommt damit eine Alternative zum unkomprimierten String.
Der folgende Text erklärt, wie Redis Bitmaps funktionieren, was Roaring anders macht, wie sich das Format aktivieren lässt und wo die Grenzen liegen. Ein Bild als roter Faden: Bitmaps sind ein Regal mit nummerierten Fächern, und die Frage ist, ob man immer das ganze Regal baut oder nur die belegten Fächer notiert.
Warum Redis Bitmaps schlichte Strings sind
Redis ist eine In-Memory-Datenbank, die Salvatore Sanfilippo 2009 startete und die heute zu den meistgenutzten Serverprogrammen gehört. Häufig läuft sie als Cache vor einer langsameren Datenbank. Angesprochen wird sie über kurze Textbefehle im Netzwerk, etwa SET user:42 Alice und GET user:42. Jeder Schlüssel bildet auf einen Wert ab, und dieser Wert kann mehr sein als ein String: Redis kennt Listen, Hashes, Sets, Sorted Sets, Streams und weitere Typen, jeder mit eigenen Befehlen.
Mengen von Ganzzahlen werden oft als Bitmaps dargestellt, manchmal auch Bitsets genannt. Das einfachste Bitmap ist ein Maschinenwort von acht Bit, damit lassen sich alle Mengen von Zahlen kleiner als acht abbilden. Hängt man weitere Wörter an, deckt man 16 Positionen ab, danach 24, und so weiter. Schnelle Mengenoperationen wie Schnittmenge und Vereinigung werden dadurch auf ein paar bitweise Operationen reduziert: AND, OR, XOR.
Im Bild des Regals heißt das: Ein gesetztes Bit markiert ein belegtes Fach, und die Mengenoperationen vergleichen zwei Regale Fach für Fach. In Redis lautet der Befehl dafür SETBIT key offset 1, und intern liegt ein gewöhnlicher Redis-String vor. Der Haken: Das Regal wird bis zum höchsten berührten Fach gebaut, egal wie viele Fächer tatsächlich belegt sind. Ein einziges Bit weit hinten im Wertebereich erzwingt die volle Länge – und jedes BITCOUNT oder BITOP muss anschließend alle Fächer durchlaufen.
Wie Roaring den Speicher an die Daten anpasst
Eine komprimierte Bitmap vermeidet diesen Aufwand, weil sie eine Menge von Ganzzahlen so ablegt, dass dünn besetzte Daten kaum Platz brauchen und Zählungen, Schnitte und Vereinigungen ohne Dekompression berechnet werden können. Roaring ist das verbreitetste komprimierte Bitmap-Format. Der entscheidende Gedanke: Nicht ein langer Bitstring wird nachträglich komprimiert, sondern die Ablage passt sich an die Daten an.
Roaring unterscheidet drei Fälle. Dünn besetzte Regionen landen als kurze Liste von Ganzzahlen, dicht besetzte Regionen als reines Bitset, und lange Strecken aufeinanderfolgender Werte als Läufe, also als Paare aus Startpunkt und Länge. Im Regal-Bild: Statt das komplette Regal zu bauen, hängt Roaring für leere Bereiche nur einen Zettel mit den belegten Fächern auf, stellt für dicht belegte Bereiche doch das Regal hin und notiert für zusammenhängende Blöcke, ab hier soundsoviele Fächer am Stück. Das Ergebnis ist häufig kleiner und schneller als ein unkomprimiertes Bitset.
Technisch zerlegt Roaring einen 32-Bit-Wert in einen oberen und einen unteren Teil und fasst die Werte in Containern zusammen, deren Typ sich nach der Dichte richtet. Weil jeder Container für sich ausgewertet werden kann, lassen sich AND und OR Container für Container ausführen, ohne den Gesamtbestand zu dekomprimieren. Elasticsearch, Apache Spark und ClickHouse setzen auf Roaring.
Redis Roaring Bitmaps aktivieren: ein neuer Typ hinter einem Schalter
Antonio Viggiano hat Roaring in Redis selbst gebracht, und die Funktion soll mit Redis 8.12 ausgeliefert werden. Sichtbar wird das an zwei Stellen. TYPE key gibt für solche Schlüssel bitmap zurück, und OBJECT ENCODING key meldet bitmap-roaring. Die komprimierte Bitmap ist damit ein Typ neben Strings, Listen und Sets.
Die Aktivierung ist als Opt-in angelegt: CONFIG SET bitmap-default-roaring yes genügt, danach werden neu angelegte Bitmaps in der komprimierten Kodierung gespeichert. Die Wahl der Kodierung verändert Speicherverbrauch und Laufzeitverhalten, und beides hängt von der jeweiligen Last ab. Bestehende Schlüssel bleiben unverändert als String liegen, eine Migration ist nicht nötig.
Für Anwendungen ändert sich an der Oberfläche nichts. SETBIT, GETBIT, BITCOUNT und BITOP mit AND, OR, XOR und NOT arbeiten weiterhin wie gewohnt, unabhängig von der Kodierung eines Schlüssels. Redis Roaring Bitmaps verwenden heißt also nicht, Code umzuschreiben, sondern eine Einstellung zu setzen und die Wirkung zu messen.
Die Messungen: Redis BITCOUNT Performance und BITOP AND OR im Vergleich
Daniel Lemire hat Redis am Merge-Commit selbst gebaut und den Server auf einem einzelnen Kern eines Intel Xeon Gold 6548N betrieben. Für jede Last erzeugte er zwei Bitmaps, a und b, einmal als String und einmal als Roaring-Bitmap, jeweils mit identischem Inhalt, und stoppte die Zeit für die Befehle BITCOUNT, BITOP AND und BITOP OR. Gemessen wurde derselbe Datenbestand in zwei Kodierungen.
Vier Lasten kamen zum Einsatz. Bei 0,1 Prozent verteilen sich 100.000 zufällige IDs über 100 Millionen mögliche Werte, was der Frage entspricht, welche Nutzer ein Feature heute verwendet haben. Bei 50 Prozent sind es 50 Millionen zufällige IDs aus 100 Millionen, also ein dicht besetztes Feld. Die Last der Läufe besteht aus zehn Abschnitten von je einer Million aufeinanderfolgender IDs in einem Bereich von 100 Millionen, ähnlich den Kohorten der Nutzer, die sich in derselben Woche angemeldet haben. Die vierte Last verwendet 100.000 zufällige 32-Bit-Werte, wodurch der String auf 512 Megabyte anwächst.
Die Diagramme zeigen, dass Roaring bei dünn besetzten und bei laufartigen Daten deutlich schneller sein kann als ein unkomprimiertes Bitmap. Besonders groß fällt der Unterschied bei den gehashten 32-Bit-IDs aus: Der String muss alle vier Milliarden Bitpositionen überspannen, und jedes BITOP tastet die vollen 512 Megabyte ab. Dort trifft die komprimierte Ablage auf eine Datenverteilung, für die sie gebaut wurde, während der String Leerlauf in Rechenzeit umsetzt.
Wo komprimierte Bitmaps gegenüber Strings verlieren
Roaring ist nicht automatisch besser; Daniel Lemire weist ausdrücklich auf Abwägungen hin. Die folgenden Überlegungen erklären allgemeine Grenzen der Datenstruktur und sind keine zusätzlichen Messwerte seines Versuchs. Bei einem dicht besetzten Feld wie der 50-Prozent-Last bringt die Kompression kaum etwas, weil die Hälfte der Positionen gesetzt ist; der zusätzliche Verwaltungsaufwand pro Container kann den Vorsprung aufzehren. Wer dichte Mengen über einen kleinen Wertebereich hält, gewinnt wenig.
Auch die Größe ist kein Selbstläufer. Bei sehr kleinen Bitmaps kann die komprimierte Struktur mehr Platz brauchen als der schlichte String, weil jeder Container seine eigene Beschreibung mitbringt. Bei den Operationen gilt dasselbe Muster: Ein BITOP über Roaring-Bitmaps muss Container zusammenführen und dabei Typen abgleichen, was bei gleichförmig dichten Daten mehr Arbeit sein kann als ein einfacher Scan. Redis komprimierte Bitmaps mit Strings zu vergleichen, ist deshalb keine Grundsatzfrage, sondern eine Frage der Datenverteilung.
Für den Betrieb heißt das, dass der globale Schalter nur der Anfang ist. Wer mehrere sehr unterschiedliche Bitsets hält – dünn besetzte Nutzerkohorten neben dichten Aktivitätsfiltern –, sollte die Wirkung getrennt betrachten. Die Entscheidung fällt dort, wo die Offsets weit streuen und die Dichte niedrig bleibt.
Was komprimierte Bitmaps in Redis 8.12 konkret bedeuten
Bisher mussten Teams, die komprimierte Bitmaps wollten, entweder eigene Kodierungen bauen oder auf ein anderes System ausweichen. Mit Redis 8.12 wird diese Bauform Teil des Kerns, erreichbar über eine Konfigurationseinstellung und sichtbar in TYPE und OBJECT ENCODING. Das senkt die Hürde, ohne bestehende Daten oder Anwendungen zu berühren.
Praktisch lohnt ein Blick auf die eigene Last. Wenn du Bitsets für Nutzergruppen über Millionen möglicher IDs pflegst, ist das ein Kandidat für einen Vergleichstest: dieselben zwei Bitmaps einmal als String, einmal als Roaring, danach BITCOUNT sowie BITOP AND beziehungsweise OR messen. Wenn die Daten ohnehin dicht liegen, kannst du den Schalter aus lassen. Weitere Details zur Struktur stehen auf der Website des Roaring-Bitmap-Projekts.
Der Gewinn liegt in der Wahlfreiheit. Redis gibt Entwicklern zwei Kodierungen für dieselbe Denkweise an die Hand, und die Entscheidung richtet sich nach dem, was in den Schlüsseln steckt. In einer In-Memory-Datenbank, in der Speicher und Antwortzeit zusammenhängen, ist das oft die richtige Art von Fortschritt.
Quelle: lemire.me
