Probablistische Datenstrukturen bzw. Algorithmen wie HyperLogLog, Bloom-Filter oder ähnliche liegen im Trend, wenn es darum geht, große Datenströme möglichst speichersparend zu analysieren. Dieser Post beschäftigt sich mit HyperLogLog und seinem Vorfahren LogLog, zwei Algorithmen, die Speicheraufwand und Laufzeit für das Zählen von eindeutigen Elementen in einem Datenstrom deutlich reduzieren können, wenn dafür kleine Ungenauigkeiten in Kauf genommen werden.
Für ein besseres Problemverständnis betrachten wir uns beispielsweise den Datenstrom A, C, D, C, B, A, P, P. Wie leicht zu überprüfen, ist die Anzahl unterschiedlicher Elemente darin fünf, nämlich A, C, D, B, P.
Was hier auf den ersten Blick reichlich trivial daherkommt, ist bei Datenmengen, die die Grenzen einer gegebenen Hardware ausreizen, ein nicht zu unterschätzendes Problem. Angenommen wir wollen die Anzahl der eindeutigen IP-Adressen, die ein Router an einem Tag „gesehen“ hat, ermitteln. Die traditionelle Herangehensweise würde dazu eine Hash-Tabelle benutzen, in die jedes bereits vorgekommene Element eingetragen werden müsste. Dazu einen einzelnen Counter, der nach jeder Adresse, die bisher nicht in der Hash-Tabelle enthalten ist, um eins nach oben gezählt wird. Bei einer großen Anzahl Adressen kann also durchaus ein beachtlicher Arbeitsspeicherbedarf von einigen Mega- bis Gigabyte zusammen kommen, die wir in unserem Router mit beschränkter Hardware vielleicht nicht zur Verfügung stellen können. Zumal der Speicherbedarf linear mit der Anzahl der (eindeutigen) Elemente wächst.
Steht also der Speicherverbrauch in keinem Verhältnis zum erwarteten Nutzen bzw. ist es ausreichend, die Anzahl unterschiedlicher Elemente zu schätzen, kann eine probabilistische Kardinalitätsabschätzung unter Verwendung von LogLog oder besser HyperLogLog zum Einsatz kommen. Doch wie funktionieren diese Algorithmen genau? Im Grunde genommen sind sie beide nicht besonders schwierig zu verstehen, ein wenig Grundwissen zu Binärzahlen, Hash-Codes und Statistik sowie die kommende Erklärung sind dazu vollkommen ausreichend.
Stellen wir uns dazu zunächst eine n-stellige Binärzahl, wie beispielsweise ein Integer mit 32 Bit (wie es auch zur Speicherung von IP-Adressen benötigt wird), vor und machen uns klar, dass alle seine 32 Stellen unabhängig voneinander mit einer Wahrscheinlichkeit von 50% entweder eine Null oder eine Eins enthalten können. Die Wahrscheinlichkeit, dass unsere Zahl in Binärdarstellung mit einer Null beginnt (oder auch endet), ist also offensichtlich 1/2, da wir genau die beiden Möglichkeiten Null oder Eins zur Verfügung haben. Dies ist vergleichbar mit dem Werfen einer Münze bei der entweder Kopf oder Zahl erscheinen kann. Die Wahrscheinlichkeit für zwei Nullen am Anfang beträgt also entsprechend 1/2 * 1/2 = 1/4, 1/8 für drei Nullen und so weiter bis 1/232 (bzw. 1/2n) für eine nur aus Nullen bestehende Binärzahl.
Hätten wir nun völlig zufällig verteilte IP-Adressen, bräuchten wir uns nur den kleinsten 32-Bit-Wert, der uns an einem Tag untergekommen ist, zu merken. Damit könnten wir dann (nach einer gewissen Anzahl von Elementen) recht genau auf die Anzahl aller gesehen Elemente zurückschließen, in dem wir 2 mit der Anzahl der führenden Nullen potenzieren. Angenommen, die kleinste bisher gesehene Zahl würde mit vierzehn führenden Nullen beginnen, dann sollte die Anzahl der aufgetretenen eindeutigen IP-Adressen bei knapp über 16.000 (~ 214) liegen.
Ein aufmerksamer Leser mag nun einwenden, dass IP-Adressen in der Praxis niemals gleichverteilt auftreten werden und das Verfahren damit nicht besonders gut funktionieren kann. Dieser Umstand lässt sich jedoch glücklicherweise leicht über die Verwendung einer guten Hash-Funktion beheben, die eine IP-Adresse in eine (pseudo)zufällige Binärzahl wandelt. Unglücklicherweise ist die Varianz der Schätzung in der Praxis dennoch recht groß, da das zufällige Auftreten eines sehr kleinen Hash-Werts für eine nicht unerhebliche Abweichung der Schätzung sorgen kann. Eine einfache Verbesserungsidee an dieser Stelle wäre schlicht, die Ergebnisse mehrerer Hash-Funktionen heranzuziehen oder den Wert der einen Hash-Funktion mit einer Anzahl von (pseudo)zufälligen Konstanten zu XODERn. Damit hätten wir mehrere Schätzwerte zur Verfügung, die wir für ein genaueres Ergebnis mitteln könnten.
Doch es geht noch geschickter. Betrachten wir uns z.B. die ersten b = 6 Bit unseres Hash-Werts, erhalten wir m = 64 mögliche Werte, die wir als Schlüssel für eine Hash-Tabelle mit 64 Buckets verwenden können. Initial werden alle Buckets in dieser Tabelle mit Null befüllt, wie in der folgenden Illustration gezeigt:
00: 0 ... 54: 0
01: 0 ...
02: 0 62: 0
03: 0 63: 0
Als dort zu speichernde Values verwenden wir dann einfach die größte Anzahl führender Nullen, die beim entsprechenden Schlüssel bisher in den restlichen Bits der Hash-Werte aufgetreten sind. Das folgende Beispiel illustriert dieses Vorgehen an Hand beliebig ausgedachter 16-Bit-Hashes.
Beginnen wir mit 1101100011100110. Die blau gedruckten ersten 6 Bits bestimmen den Ziel-Bucket der Hash-Tabelle, in dem die Anzahl der führenden Nullen des roten Teils gespeichert werden soll. Hier ist es also Bucket 54 in dem eine Zwei gespeichert werden muss, es sei denn natürlich, dort wäre bereits ein größerer Wert enthalten. Würde nun der Hash-Wert 1111100011001100 für ein Element geliefert, wird in den Bucket mit der Nummer 62 abermals eine Zwei gespeichert, bei 0000110001100110 erhält entsprechend das Bucket mit der Nummer 3 eine Drei. Und würde zum Abschluss des Beispiels der Wert mit 1101100001111010 geliefert, müsste die Zwei in Bucket 54 mit einer Drei überschrieben werden, so dass sich folgender Inhalt für die Hash-Tabelle ergibt:
00: 0 ... 54: 3
01: 0 ...
02: 0 62: 2
03: 3 63: 0
Potenzieren wir nun 2 mit dem Mittelwert der Werte in allen befüllten Buckets, erhalten wir mit 2(3+2+3)/3 ~ 6 eine brauchbare Näherung für die Anzahl der beobachteten individuellen Datensätze. Unter diesem Link gibt es für diesen Ablauf einen Simulator, der insbesondere das Befüllen der Hash-Buckets noch einmal anschaulich macht (die Binärzahl wird dort von rechts nach links betrachtet).
Der LogLog-Algorithmus funktioniert genau nach diesem Prinzip, verwendet nur für die abschließende Berechnung folgende, etwas kompliziertere Formel zur Ermittlung des Schätzergebnisses E (und addiert jeweils noch eine Eins auf die Anzahl der führenden Nullen):
Dabei ist m wie oben die Anzahl der Buckets (also im Beispiel 64), M(j) der Wert im jeweiligen Bucket und αm eine Konstante (α16 = 0,673, α32 = 0,697, α64 = 0,709, bzw. für m ≥ 128 αm = 0,7213 / (1 + 1,079 / m)), die die Neigung des LogLog-Algorithmus zum „Überschätzen“ der Zählung ausgleicht. Damit liegt der Algorithmus bei einem ungefähren Fehler von etwa 1,30/Wurzel(m), für das obige Beispiel also bei rund 16%. Bei 1024 Buckets erreicht das Verfahren einen Fehler von etwa 4% und das bei einem Speicherbedarf, der in O(log log n) liegt (wobei n die Anzahl der zu zählenden Elemente ist).
Der HyperLogLog-Algorithmus ist bis auf die verwendete Formel identisch zu LogLog. HyperLogLog verwendet das harmonische statt des geometrischen Mittels und entsprechend folgende, leicht abgewandelte Formel:
HyperLogLog drückt damit den erwartbaren Fehler auf etwa 1,04/Wurzel(m), würde in unserem Beispiel also ungefähr 13% daneben liegen und bei 1024 Buckets (bei einem Speicherbedarf von wenigen Kilobyte!) nur noch ganze 3,25%. Zusätzlich sind beide Algorithmen auch auf Datenbeständen moderater Größe unter Umständen deutlich schneller, als beispielsweise ein Scan über alle Zeilen einer Datenbank.
Wichtig für die Skalierbarkeit von Big-Data-Anwendungen ist natürlich die mögliche Parallelisierbarkeit beider Algorithmen: diese können problemlos in identischer Konfiguration parallel auf mehreren Rechnern ausgeführt werden. Wird eine Abschätzung für die Anzahl unterschiedlicher Elemente über alle Maschinen hinweg benötigt, müssen nur die überschaubar großen Hash-Tabellen zusammengeführt werden. Zur Erstellung der "Master-Tabelle" wird schließlich der größte Wert jedes Buckets von allen Rechnern übernommen, woraufhin die Master-Tabelle mit der obigen Formel ausgewertet werden kann.
Auf verschiedene Mengen auf dem gleichen Rechner angewendet ermöglicht dieses Verfahren auch die Abschätzung der Kardinalität der Vereinigungsmenge (z.B. |A ∪ B| der beiden Mengen A und B). Und HyperLogLog kann noch mehr. Mit Hilfe der Mengenlehre lässt sich auch die Größe der Schnittmenge zweier Mengen einfach abschätzen: |A ∩ B| = |A| + |B| – |A ∪ B|.
Zur Beantwortung der Frage nach der Nutzbarkeit des HyperLogLog-Algorithmus hier noch einige Links zu Anwendungsbeispielen aus der Praxis:
- HyperLogLog für Compactions in Cassandra
- Eindeutige Elemente in Googles Big Query
- Kardinalitätsabschätzungen für Suchergebnisse in Elasticsearch
- Verteiltes count(distinct) in Postgres
Keine Kommentare:
Kommentar veröffentlichen