HyperLogLog zählte Milliarden unterschiedlicher Elemente in Kilobyte

Exakte Kardinalität — wie viele unterschiedliche Nutzer, IP-Adressen oder Suchanfragen aufgetreten sind — erfordert normalerweise Speicher proportional zur Anzahl der unterschiedlichen Elemente, was im Internet-Maßstab unmöglich ist. Im Jahr 2007 veröffentlichten Philippe Flajolet und Kollegen bei INRIA HyperLogLog, ein probabilistisches Sketch, das Kardinalitäten über einer Milliarde mit etwa 2 Prozent Genauigkeit unter Verwendung von rund 1,5 Kilobyte Speicher schätzt.

Der Trick beruht auf einer Münzwurf-Intuition: Man hasht jedes Element zu einer gleichverteilten Zufallszahl und beobachtet die längste Folge führender Nullen. Eine Folge von n Nullen ist selten — Wahrscheinlichkeit 2^-n —, sodass, wenn sie auftritt, die Menge wahrscheinlich groß genug ist, um sie hervorzubringen, und 2^n eine gute Schätzung der Kardinalität ist. HyperLogLog teilt den Strom in viele Teilmengen auf, hält ein Register pro Teilmenge, das deren längste Nullfolge speichert, und kombiniert sie mit einem harmonischen Mittel, damit Ausreißer die Schätzung nicht verzerren.

Die Methode stammt vom Flajolet-Martin-Algorithmus von 1984 und dem LogLog-Algorithmus ab. Die Ingenieursarbeit, die sie produktionsreif machte, kam 2013 mit dem Paper „HyperLogLog in Practice“ von Heule, Nunkesser und Hall bei Google, das Verzerrungs- und Dünnbesetzungsprobleme für große und kleine Kardinalitäten behob.

Redis machte HyperLogLog zu einer Produktfunktion: Seine Befehle PFADD, PFCOUNT und PFMERGE schätzen bis zu 2^64 unterschiedliche Elemente mit bis zu 12 KB Speicher pro Schlüssel und einem Standardfehler von 0,81 Prozent, und Sketches lassen sich zusammenführen, sodass tägliche Zählungen kombiniert werden können, ohne den Rohstrom erneut zu lesen.

Zählungen aus führenden Nullen im Hash schätzen

Ein Hash verwandelt beliebige Daten in eine gleichverteilte Zufallszahl mit derselben Kardinalität

Die längste Folge führender Nullen ist eine natürliche, beobachtbare Schätzung der Mengengröße

Die Aufteilung in Register plus ein harmonisches Mittel hebt das Rauschen auf

Sketches lassen sich zusammenführen, sodass tägliche Zählungen kombiniert werden können, ohne den Rohstrom zu speichern

Wenn die Antwort nur ungefähr sein muss, hört man auf, die Daten zu speichern — man speichert ein winziges Sketch, dessen Zufälligkeit die Größe offenbart, und tauscht einen begrenzten Fehler gegen unbegrenzte Skalierung.

HyperLogLog wurde zu einem Standardbaustein in Analytik und Datenbanken: Redis liefert es als Datentyp aus, und die Verbesserungen des Google-Papers von 2013 machten es erst im Maßstab in Produktionssystemen nutzbar. Die Logik des Sketches — einen kleinen Nachweis behalten, nicht die Daten — verankert auch spätere Strukturen wie MinHash und Count-Min Sketch.