Metriken mit Bitmaps schneller erfassen
Bitmaps eignen sich als alternatives Verfahren für die Auswertung von Datenbank-Metriken. Am Beispiel von Redis zeigt Bookmark-Serviceanbieter Spool, wie das Verfahren bis 128 Millionen User skaliert.
- Robert Lippert
Spool, Anbieter des gleichnamigen Bookmark-Dienstes, arbeitet an einer optimierten Auswertung seiner Datenbankmetriken. Im Falle des Key-Value-Stores Redis führe der über den Einsatz von Bitmaps (hier: Bitfolgen, keine Rastergrafiken). Mit ihnen könne eine typische Metrik wie "tägliche eindeutige Nutzer" über 128 Millionen User auf einem handelsüblichen MacBook Pro in weniger als 50 Millisekunden errechnet werden, bei einem Speicherbedarf von rund 16 MByte.
Im Beispiel sollen Metriken für die Anzahl der in einem bestimmten Zeitraum an einem System angemeldeten Benutzer ermittelt werden. Für Spool besteht der Trick nun im Wesentlichen darin, dass Nutzer sich leicht in Bitfolgen abbilden lassen – zum Beispiel könne man ein Bit auf 1 setzen, wenn sich ein User zu einem bestimmten Zeitpunkt eingeloggt hat, oder eben auf 0, wenn nicht. Will man anschließend ermitteln, wie viele Nutzer sich zu diesem Zeitpunkt insgesamt am System angemeldet haben, genügt es, das Hamming-Gewicht der Bitfolge zu ermitteln.
(Bild: blog.getspool.com)
Manche CPUs unterstützen diese Berechnung mit eigenen SSE4-Anweisungen, was einen zusätzlichen Leistungsschub für die Berechnung des Hamming-Gewichtes verspricht. Dehne man das Beispiel aus und will die Anzahl der über mehrere Tage hinweg eindeutig angemeldeten Benutzer ermitteln, brauche man schlicht die Vereinigungsmenge der einzelnen Bitfolgen bilden und auch hier wieder das Hamming-Gewicht ermitteln.
Spool hat seine Überlegungen mit einem kleinen Benchmark untermauert, bei dem pro Tag eine aus 128 Millionen Nutzern gebildete Bitfolge angelegt und hieraus das jeweilige Hamming-Gewicht für einzelne Bitmaps berechnet, sowie die Vereinigungsmengen der wöchentlichen und der monatlichen Bitmaps gebildet und ausgewertet wurden. Dabei benötigte ein MacBook Pro für die Analyse der täglichen Bitfolgen jeweils rund 50 Millisekunden, für die wöchentlichen Bitfolgen etwa 390 Millisekunden und für die monatlichen knapp 1625 Millisekunden. Spool betont, dass das Verfahren recht flexibel sei und durch Caching weiter optimiert werden könne.
In der Theorie unterstütze Redis Bitfolgen mit einem Offset bis 2^32 -1, was knapp 4,4 Milliarden Nutzern entspreche. Chandra Patni, Softwareentwickler für Spool, empfiehlt für solche Größenordnungen jedoch auf Sharding und andere Techniken zurückzugreifen. Wer das Verfahren unter Java an einer eigenen Redis-Installation nachvollziehen möchte, findet im Blog des Unternehmens den passenden Beispielcode und weitere Details zum Einsatz von Redis Bitmaps. (rl)
