Sketching Algorithmen
Ich freue mich immer wieder, wenn ich was Neues entdecke. Heute bin ich über Sketching Algorithmen gestolpert und möchte diese faszinierende Familie von Algorithmen gleich mit dem geneigten Leser teilen.
Problemstellung für Sketching Algorithmen
Bei der Verarbeitung riesiger Datenmengen möchte man häufig bestimmte statistische Kennzahlen für die Gesamtmenge erheben. Den Anbieter eines Social Networks interessiert es, wie viele Nutzer jeden Tag seinen Dienst nutzen. Damit kann er die Popularität seines Dienstes messen.
Der Social Network Betreiber müsste dazu alle Nutzer-Anmeldungen protokollieren, damit er dann die Liste der eindeutigen Nutzer ermitteln kann.
Für die täglichen Anmeldeversuche kommen ganz schön viele Daten zusammen. Pro Anmeldung sind es mindestens 24 Bytes:
- 16 Bytes für die Nutzer-ID (etwa eine UUID v4)
- 8 Bytes für den Zeitstempel (auf Basis von Postgres)
- …weitere Daten wie Endgerät, etc.
Bei 500 Millionen Anmeldungen täglich wären das mindestens 12 GB an Daten. Um mehrfache Anmeldungen nicht zu zählen, müsste der Social Network Betreiber die gesamten Daten auf eindeutige Nutzer-IDs durchsuchen und am Ende deren Anzahl zählen. Das ist ganz schön viel Aufwand, um am Ende eine einzige Kennzahl zu berechnen:
„X eindeutige Nutzer gestern“
Genau für die Lösung solcher Probleme gibt es Sketching Algorithmen. Diese lösen das Problem über clevere Näherungsverfahren mit bekannten statistischen Fehlerquoten und wesentlich geringerem Speicherverbrauch.
Theta Sketch Algorithmus
Der Theta Sketch Algorithmus wurde genau für dieses Problem entwickelt. Er basiert auf dem Trick mittels eines Hashing Algorithmus Nutzer-IDs in eine gleichverteilte Menge zwischen 0 und 1 zu überführen und dann anhand einer kleinen Stichprobe die Gesamtanzahl näherungsweise zu berechnen.
Damit das funktioniert, muss man eine Nutzer-ID wie „8f75c77b-9471-421c-bcd7-6e8166ce5faa“ in eine Zahl wie 0.461738290 überführen. Aus der Kryptographie gibt es eine Vielzahl entsprechender Hash Algorithmen. Allerdings benötigt man hier gar nicht einen kryptographisch sicheren Algorithmus, sondern kann sich auch mit weniger rechenintensiven Varianten wie MurmurHash3 oder xxHash begnügen.
Würde man sich aber alle Hashes der Nutzer-IDs merken, hätte man nichts gewonnen. Stattdessen merkt man sich während der Nutzeranmeldungen immer nur eine relativ kleine Liste von zum Beispiel den 10.000 kleinsten Hashes. Dies bezeichnet man als die Sketch Größe. Um so größer die Sketch Größe, also die Stichprobengröße, um so genauer wird die Schätzung.
Am Ende des Tages muss man diese Liste nur noch nach dem größten Wert durchsuchen. Diesen Wert bezeichnet man als Theta θ. Die Schätzung berechnet sich dann folgendermaßen:
estimate_unique_user_ids = sketch_size / theta_thresholdCode-Sprache: Python (python)Für die Genauigkeit der Schätzung spielt es keine Rolle, wie viele Nutzer sich tatsächlich an dem Tag angemeldet haben, solange es um Größenordnungen mehr waren als die Stichprobe.
Ich habe auf GitHub einen kleinen Demonstrator für den Sketch Algorithmus abgelegt. Der Demonstrator muss natürlich erst mal eine Liste von zufälligen Nutzer-IDs erzeugen und er prüft am Ende mittels Chi-Quadrat-Test, ob die Hashes wirklich gleichverteilt sind. Der Kern des Algorithmus lässt sich aber auf wenige Zeilen eindampfen:
def count_unique_logins_with_theta_sketch() -> None:
login_attempts = generate_login_attempts()
retained_hashes = SortedList()
theta_threshold = 1.0
for user_id in login_attempts:
normalized_hash = hash_user_id_to_unit_interval(user_id)
if normalized_hash >= theta_threshold:
continue
if normalized_hash in retained_hashes:
continue
retained_hashes.add(normalized_hash)
if len(retained_hashes) > MAX_SKETCH_SIZE:
theta_threshold = retained_hashes[MAX_SKETCH_SIZE]
del retained_hashes[MAX_SKETCH_SIZE:]
estimate_unique_user_ids = len(retained_hashes) / theta_thresholdCode-Sprache: Python (python)Auch die Umwandlung der Nutzer-ID in eine gleichverteilte Zahl zwischen 0 und 1 ist erstaunlich einfach lösbar:
MAX_HASH_SPACE = 2 ** 128
def hash_user_id_to_unit_interval(user_id: str) -> float:
hash_value = xxhash.xxh128(user_id).intdigest()
return hash_value / MAX_HASH_SPACECode-Sprache: Python (python)Die meiste Zeit benötigt das Programm für die Erzeugung der 10.000.000 zufälligen Nutzer-IDs. Der Theta Sketch Algorithmus hingegen ist sehr einfach und der meiste Rechenaufwand fällt für die Erzeugung des Hashwerts an.
Theta Sketch in der Praxis
Für den Betreiber des Social Networks hat sich das Problem stark vereinfacht. Statt 500 Millionen Anmeldungen muss er nur die Liste mit den 10.000 kleinsten Hashes während des Tags aktuell halten.
Tatsächlich ist das aber auch gar kein einfaches Problem, denn vermutlich sind tausende Server gleichzeitig in Betrieb, um das Social Network zu betreiben. Müssten sich all diese Server koordinieren, um die Liste mit den 10.000 kleinsten Hashes aktuell zu halten, hätten wir ein neues Problem.
An dieser Stelle kommt eine weitere schöne Eigenschaft des Theta Sketch Algorithmus hinzu: Jeder Server kann zunächst seine eigene Liste führen und erst am Ende des Tages werden die Listen der einzelnen Server zusammengeführt. Damit das klappt, müssen aber ein paar Dinge erfüllt sein:
- alle Server verwenden den exakt gleichen Hashing Algorithmus
- d.h, die gleiche Nutzer-ID resultiert auf allen Servern im exakt gleichen Hashwert
- alle Server haben die gleiche maximale Sketch Größe konfiguriert
Eine andere Lösung für die Praxis ist eine Streaming Architektur. Die Anmeldungen werden in einen gemeinsamen Datenstream veröffentlicht und dieser wird zentral ausgewertet. Dann muss nicht jeder Server seine eigene Liste führen, aber natürlich benötigt der Social Network Betreiber nun eine skalierbare Lösung für die Verarbeitung des Streams.
Ausblick
Der Theta Sketch Algorithmus löst genau ein Problem: die Anzahl eineindeutiger Werte aus einer Gesamtmenge anhand einer Stichprobe zu schätzen. In der Praxis gibt es viele weitere statistische Kenngrößen, die man ermitteln will, etwa:
- Ausreißer bei Messwerten
- Percentile einer Normalverteilung
- etc.
Auch für diese Probleme gibt es spezialisierte Schätzalgorithmen. Die Apache DataSketches Software-Bibliothek bietet eine Vielzahl von hocheffizienten Algorithmen für unterschiedlichste Problemstellungen.
Ein Schätzalgorithmus ist eine geniale Lösung, wenn ein Schätzwert ausreichend ist. Für den Betreiber eines Social Networks ist es sicher akzeptabel, wenn er die täglichen Nutzer mit einer Fehlerquote von 1-2% schätzt. Eine Bank hingegen wird den Kontostand sicher nicht schätzen wollen und kommt nicht umhin, wirklich alle Transaktionen zu verarbeiten. Aber auch dafür gibt es hochskalierbare Lösungen, die aber natürlich wesentlich mehr Geld für den Betrieb kosten.