• Entwicklung/Architektur
  • Methoden
  • Programmiersprachen
• Betrieb
  • Datenbanken
  • Server
  • IT-Security
  • Speicher
  • Netzwerke
  • Virtualisierung
  • Verfügbarkeit
  • Künstliche Intelligenz
• Management und Recht
  • Projektmanagement
  • Digitalisierung
  • IT-Recht
  • IT-Selbständige
• Aktuelles
• Termine
• IT-Jobs

☰

• Entwicklung
• Betrieb
• Management und Recht
• News
• IT-Jobs
• Newsletter

Prof. Dr. Oliver Hummel 01. März 2023

Auch mal Fünfe gerade sein lassen

Wie probabilistische Datenstrukturen datenintensive Systeme besser skalierbar machen

Neben den bekannten Problemen verteilter Systeme, wie Synchronisation, Redundanz und Resilienz, spielt allerdings auch die Komplexität der darauf laufenden Verarbeitung eine nicht zu unterschätzende Rolle. Die eben angesprochene Skalierbarkeit funktioniert nur dann, wenn maximal eine lineare Verarbeitungskomplexität (also in O(n)) vorliegt. Einfach gesagt kann dann eine doppelte Datenmenge mit den doppelten Hardware-Ressourcen verarbeitet werden. Hat ein Algorithmus jedoch eine darüberhinausgehende Komplexität, also etwa in O(n²), wird beispielsweise für die doppelte Datenmenge bereits die vierfache Hardware-Kapazität benötigt, schon bei der zehnfachen Datenmenge und einem sich daraus ergebenden Faktor einhundert für die Hardware leuchtet ein, dass eine solche Skalierung nicht lange gut gehen kann. Abhilfe verspricht in einigen Situationen die Verwendung von probabilistischen Techniken aus einer hochskalierbaren Familie von Datenstrukturen mit wohlklingenden Namen wie HyperLogLog oder Bloom-Filter, die ich in diesem Artikel vorstellen und näher erläutern möchte.

Zur Einleitung möchte ich den Grundgedanken dahinter mit einem kleinen Chuck-Norris-Witz illustrieren: Chuck Norris braucht keine log₂(n) Bits zum Zählen, er schafft es mit weniger.

Zugegeben, unser Chuck Norris heißt eigentlich Bob (bzw. Robert) Morris und zählt eben probabilistisch, doch nichtsdestotrotz ist der von ihm erdachte Morris-Counter ein schöner Einstieg in die spannenden Denkweisen der Big-Data-Welt. Wenn Sie nun denken, "Probablistisches Zählen? Wovon redet er bloß?", tauchen Sie mit mir in den nächsten Abschnitt ein, dort werde ich das Geheimnis des Morris-Counters lüften, um auf dessen Grundlage weitere Ansätze, wie die bereits genannten HyperLogLog oder BloomFilter, zu erläutern.

Probabilistisches Zählen: Der Morris-Counter

Der sogenannte Morris-Counter wurde bereits in den Anfangsjahren der Informatik zum Einsparen von Speicherplatz bei der Nutzung von Zählern auf der damals noch sehr bescheidenen Hardware konzipiert [1]. Auch heutige Computer arbeiten bekanntlich mit dem Binärsystem und speichern Zahlen in sogenannten Bits, die entweder auf 0 oder auf 1 gesetzt werden (künftige Quantencomputer einmal ausgenommen). Jedes dieser Bits kann also zwei verschiedene Werte repräsentieren, zwei Bits gemeinsam entsprechend zwei mal zwei, also vier Werte, drei Bits zwei mal zwei mal zwei Werte und so weiter.

Oder andersherum betrachtet, um bspw. bis zur Zahl 1.000 zählen zu können, benötigen wir mindestens 10 Bits, da 2¹⁰ = 1.024 ist. Um für eine Zahl aus dem Dezimalsystem bestimmen zu können, wie viele Bits zu ihrer Speicherung notwendig sind, kann der Zweierlogarithmus verwendet werden: das Ergebnis von log2(1.000) = 9,9658 muss logischerweise auf 10 aufgerundet werden, da Bruchteile von Bits keinen Sinn zur Speicherung von Daten ergeben. Robert Morris sah sich in den 1970er Jahren exakt diesem Problem gegenüber, ihm stand lediglich ein 8-Bit-Register zum Zählen von Events zur Verfügung, er musste damit jedoch deutlich weiter als bis 255 zählen.

Um nun mit weniger Bits beim Zählen auszukommen, liegt eine einfache Idee auf der Hand: Wir zählen nur jedes zweite Auftreten eines Events und multiplizieren den Zähler am Ende mit zwei, um wieder auf den korrekten Wert zu kommen. Entsprechend kommen wir mit einem Bit weniger Speicher aus. Oder wir zählen nur jedes vierte Auftreten und sparen somit gleich zwei Bits, usw.

Die spannende Idee von Robert Morris war es, einen Pakt mit dem Zufall einzugehen.

Um allerdings zu wissen, ob gerade ein zweites oder viertes Event gezählt werden soll, müsste ein zweiter Zähler angelegt werden, der wiederum genau die eingesparten ein oder zwei Bits benötigen würde. Somit wäre also rein gar nichts gewonnen. Die spannende Idee von Robert Morris war es nun, für seinen Zähl-Algorithmus keinen zweiten Zähler zu verwenden, sondern einen Pakt mit dem Zufall einzugehen.

Bildhaft gesprochen lässt sich ein Bit einsparen, wenn bei jedem Zählschritt eine Münze geworfen und der Zähler bspw. nur dann erhöht wird, falls diese "Kopf" geliefert hat. Im Computer verwenden wir statt einer Münze natürlich lieber einen Zufallszahlengenerator etwa mit ganzen Zahlen zwischen 0 und 2^b-1, wobei b die Anzahl der Bits beschreibt, die wir einsparen möchten. Wird der Zähler immer nur dann erhöht, wenn zufällig eine Null generiert worden ist, wäre die Wahrscheinlichkeit, für eine Zählererhöhung bei b = 2 also ein ¼, was die folgende Tabelle noch einmal anhand eines Beispiels anschaulich macht.

Tabelle 1: Beispielhafter Verlauf eines vereinfachten Morris-Counters

Eventanzahl (fortlaufend)	Zufallswert (zw. 0 und 2b-1)	Zählerstand (Morris-Counter)	Näherung (Stand * 2b)
1	0	1	4
2	2	1	4
3	3	1	4
4	3	1	4
5	1	1	4
6	0	2	8
7	3	2	8

Wie in Tabelle 1 schön zu sehen, wächst der Zählerstand des Morris-Counters deutlich langsamer als die Zahl der Events und spart somit Bits, er hängt dafür aber auch vom jeweils "ausgewürfelten" Zufallswert ab, so dass auch die vom Counter gelieferte Näherung mit einer gewissen Ungenauigkeit behaftet sein wird.

Morris ging damals übrigens noch weiter: Da er mit den ihm zur Verfügung stehenden 8 Bit sehr viel größere Werte speichern wollte, musste er eine noch größere Reduzierung der Bit-Anzahl erreichen: Die Originalversion seines Zählers merkt sich daher nur die (binäre) Größenordnung (also den Exponenten c zur Basis 2) der Event-Anzahl n und benötigt entsprechend nur log₂(log₂(n)) Bits zum Zählen bis n, was sich natürlich insbesondere bei großen Zählerständen mit einer deutlichen Speicherersparnis bemerkbar macht. Chuck Norris wäre sicher beeindruckt.

Der Morris-Zähler hat allerdings auch mit einer deutlich größeren Unschärfe in Bezug auf die tatsächliche Event-Anzahl zu kämpfen. c wird nämlich immer nur dann inkrementiert, wenn eine Zufallszahl zwischen 0 und 2^c genau 0 ergibt, was bei wachsendem c immer seltener vorkommen wird. Tabelle 2 illustriert den Effekt auf die Unschärfe des aus 2^c errechneten Näherungswerts anhand einiger ausgedachter Beispiele.

Tabelle 2: Beispielhafte Werte für die Original-Version eines Morris-Counters, der sich nur die binäre Größenordnung der Eventanzahl merkt

Eventanzahl (beispielhaft)	Größenordnung (Anz. Bits)	Zählerstand c (beispielhaft)	Näherung (2c)
5	3	2	4
42	6	5	32
100	7	7	128
221	8	8	256
3.456	12	11	2.048
53.823	16	15	32.768
34.645.245	26	27	134.217.728

Wie mir vor einiger Zeit nach einem Vortrag zu diesem Thema zurückgemeldet wurde, führt allein dieser Gedanke an die Verwendung von Probabilismus und Unschärfe in einer von Determinismus und Genauigkeit geprägten Computerwelt zu einer spürbaren Disruption gängiger Denkmodelle. Sich im Folgenden auf diesen Gedanken einzulassen, kann sich jedoch lohnen, da damit große Mengen an Speicher gespart und Systeme deutlich leistungsfähiger gemacht werden können.

Kardinalitätsabschätzungen mit HyperLogLog

HyperLogLog erreicht bei Verwendung von 1024 Buckets eine durchschnittliche Fehlerrate von etwa 3,25 Prozent – und das bei Verwendung einer 256-Bit-Hashfunktion bei einem konstanten Speicherverbrauch von gerade 1024 Byte. Ferner ist auch das Zusammenführen von Näherungswerten von mehreren parallel laufenden Serverknoten problemlos möglich, hier kann leicht der Mittelwert aus den Werten verschiedener Knoten gebildet werden. Für eine verbesserte Genauigkeit könnten auch leicht die Maximalwerte aus den jeweiligen Buckets aller Knoten gesammelt und direkt auf dem koordinierenden Server für die Berechnung des Schätzwerts verwendet werden.

Es versteht sich fast von selbst, dass die Open-Source-Community bereits zahlreiche Implementierungen des HyperLogLog in den verschiedensten Sprachen entwickelt hat. Um ein Gefühl für seine Verwendung zu bekommen, möchte ich kurz die Verwendung der bekannten Java-HLL-Implementierung von Aggregate Knowledge illustrieren [3]. Diese benötigt noch eine guava-kompatible [4] Implementierung einer Hash-Funktion und schon kann es folgendermaßen losgehen:

HashFunction hf = Hashing.murmur3_128();
HLL hll = new HLL(14, 5);

Dem HyperLogLog-Konstruktor muss die Anzahl der Bits (hier also 14), die für die Zähler in den Buckets verwendet werden sollen, sowie die Anzahl der Buckets (hier 2⁵) übergeben werden. Danach kann die HLL-Instanz beispielsweise über einen Lambda-Ausdruck mit einigen Werten befüllt und nach einem Näherungswert für die Anzahl der gesehenen Werte gefragt werden:

LongStream.range(0, 1000000).forEach(n ->
     hll.addRaw(hf.newHasher().putLong(n).hash().asLong()) );

System.out.println(hll.cardinality());

In diesem Beispiel ergibt sich ein Fehler von gerade einmal rund 0,3 Prozent.

Entsprechend beliebt ist der HyperLogLog bei Zählungen großer Datenmengen in der Praxis. Seine Nutzung drängt sich bei der Auswertung von Textdaten im Information Retrieval oder in Datenbanken gerade zu auf, entsprechende Implementierungen sind beispielsweise in der Suchmaschine Elasticsearch oder auch in PostgreSQL zu finden.

Schon drin oder was? Feststellung von Mengenmitgliedschaft

In großen und verteilten Datenbeständen kann eine Art Cache, der eine Indikation dafür liefert, ob ein Wert in einem Datensatz enthalten sein kann oder nicht, sehr hilfreich sein. Um Letzteres zweifelsfrei bestimmen zu können, müsste ohne ein solches Hilfsmittel der Datenbestand vollständig nach dem gewünschten Wert durchsucht werden. Eine ähnliche Herausforderung stellt sich, wenn bei einem nicht begrenzten Datenstrom beurteilt werden soll, ob ein bestimmter Wert bereits zuvor darin enthalten war. Mit herkömmlichen Mitteln funktioniert das abermals nur durch das speicherplatzintensive Speichern aller gesehenen Werte, beispielsweise wieder in einer Hashtabelle.

Mit einem nach seinem Entwickler benannten Bloom-Filter [5] lässt sich durch die Verwendung von Hash-Funktionen und ihres "Fingerabdrucks" in einem Bit-Array sehr leicht speichern, ob ein Wert schon einmal gesehen wurde, bzw., um genauer zu sein, ob ein Wert schon einmal gesehen worden sein kann. Auf Grund seines Aufbaus kann ein Bloom-Filter nämlich leider gelegentlich auch falsch positive Treffer liefern; immerhin jedoch niemals falsch negative Werte.

Die Mechanik des Bloom-Filters ist dabei hinreichend einfach: Neben dem bereits erwähnten Bit-Array benötigt er einige (gewöhnlich zwischen ca. 3 und 12) Hash-Funktionen. Für letztere bietet sich wieder die Verwendung von Murmur3-Hashes an, da diese mit verschiedenen Seed-Werten initialisiert werden können und somit nur ein einzelner Hash-Algorithmus zur Verfügung gestellt werden muss.

Für ein grundlegendes Verständnis betrachten wir uns ein einfaches Beispiel, in dem das Array aus lediglich acht Bits besteht. Wie in der echten Implementierung werden diese initial alle mit Null bzw. false initialisiert:

0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7

Unter den Bits (blau) steht jeweils ihr nullbasierter Indexeintrag (grün) im Array. Dazu überlegen wir uns zwei ganz einfache Hash-Funktion hf₁und hf₂, die jeweils durch eine Modulo-Operation alle Input-Werte auf den Wertebereich zwischen 0 und 7, also auf die Index-Werte unseres Arrays, abbilden:

hf₁(e) = (e + 1) * 3 modulo 8
hf₂(e) = (e + 2) * 2 modulo 8

Verwenden wir als Eingaben nun beispielsweise e1 = 7 und e2 = 13, ergäbe dies folgende Ergebnisse beim Einsetzen in die beiden Hash-Funktionen:

hf₁(7) = 0        hf₁(13) = 2
hf₂(7) = 2        hf₂(13) = 6

Entsprechend müssen nun die Bits 0, 2 und 6 im Array auf Eins gesetzt werden, die Eingabewerte hinterlassen also quasi einen Finger- oder auch Fußabdruck in unserem Bit-Array:

1 0 1 0 0 0 1 0
0 1 2 3 4 5 6 7

Das Bit mit dem Index 2 wird faktisch zweimal auf Eins gesetzt, was allerdings folgenlos bleibt, da ein einmal auf Eins gesetzter Eintrag immer auf Eins gesetzt bleiben wird. Entsprechend können aus einem Bloom-Filter auch keine Einträge mehr gelöscht werden.

Solche Überlappungen können bei der gleich erklärten Abfrage eines Bloom-Filters zu den bereits erwähnten falsch positiven Ergebnissen führen, wenn ein bisher noch nicht gesehener Wert auf bereits komplett auf Eins gesetzte Array-Einträge abgebildet wird.

Die Abfrage funktioniert nämlich nach dem gleichen Prinzip, zunächst wird der gesuchte Wert "durch den Wolf gedreht" (also seine Hash-Werte werden berechnet) und wenn alle dadurch adressierten Bits bereits auf Eins gesetzt sein sollten, wird ein wahrscheinlicher Treffer zurückgemeldet; andernfalls kann der Bloom-Filter diesen Wert mit Sicherheit noch nicht gespeichert haben.

Betrachten wir 7 und 4 als beispielhafte Abfragen. Für die Eingabe 7 errechnen die Hash-Funktionen wie zuvor die Bits 0 und 2, die beide auf Eins gesetzt sind, entsprechend wird ein Treffer zurückgegeben. Für die 4 müssen die Bits 7 und 6 überprüft werden, von denen Ersteres noch den Wert Null enthält, entsprechend kann eine 4 noch nicht in diesem Bloom-Filter gespeichert worden sein.

Ferner illustriert schon dieses einfache Beispiel sehr eindringlich, dass ein Bloom-Filter mit zunehmender Befüllung immer mehr Werte aus dem Bit-Array auf Eins setzen und damit auch immer mehr falsch positive Werte zurückmelden wird. Eine gut zu merkende Daumenregel besagt daher, dass ein Bloom-Filter bei ungefähr 6 Hash-Funktionen etwa sechsmal so viele Bits vorhalten sollte, wie Einträge zu erwarten sein werden, um die Fehlerrate im Bereich von 6 Prozent (bzw. knapp darüber) zu halten. Das wären für eine Million Einträge bspw. 6 Millionen Bits, also ungefähr 750 Kilobyte Speicherplatz und mithin deutlich weniger, als die gut zweistellige Zahl an Megabytes, die zum Abspeichern von einer Million Werten in einer HashMap benötigt werden würden. Zur genaueren Bestimmung der optimalen Größe eines Bloom-Filters bietet sich beispielsweise ein Online-Rechner an [6].

Auch Bloom-Filter-Implementierungen sind für zahlreiche Sprachen als Open-Source im Netz zu finden, beispielsweise enthält Googles Guava-Library eine entsprechende Klasse [4]. Nach ihrer Einbindung kann mit folgendem Konstruktor-Aufruf eine Bloom-Filter-Instanz erzeugt werden:

BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), 1000, 0.01);

Ein Blick auf den Code verrät, dass hier ca. 1.000 Integer-Werte bei einer Fehlerwahrscheinlichkeit von einem Prozent gespeichert werden sollen. Auf dieser Basis berechnet Guava selbständig die optimale Größe des Bit-Arrays, so dass wir direkt mit der Befüllung beginnen können:

filter.put(4);
filter.put(7);

Auch die Überprüfung auf mögliche Treffer ist ähnlich einfach und liefert jeweils true oder false zurück:

bf.mightContain(1);
bf.mightContain(4);

Ähnlichkeiten zur Verwendung einer "normalen" HashMap (bzw. Hash-Tabelle) sind natürlich nicht zufällig, da beide sehr ähnlich verwendet werden können. Zwar kann der der Bloom-Filter im Gegensatz zur HashMap keine Werte, sondern nur die Hash-Codes der Schlüssel "speichern", prinzipiell ist eine HashMap jedoch auch nichts anderes, als ein Bloom-Filter mit nur einer Hash-Funktion und einem weiteren Speicher für die abzulegenden Werte. Auch aus Datenschutz-Gesichtspunkten ist der Bloom-Filter sehr charmant: Er speichert die gesehenen Daten pseudonymisiert, so dass vom Inhalt seines Bit-Arrays nicht auf die gespeicherten Einträge zurückgeschlossen werden kann.

Von den in diesem Artikel vorgestellten Ansätzen hat der Bloom-Filter bisher vermutlich die mit Abstand meiste Verbreitung auch in Mainstream-Systemen gefunden. Es gibt Berichte, dass Bloom-Filter in Routern zum Tracking von Denial-of-Service-Attacken eingesetzt werden. Auch in Datenbanken wie Cassandra oder HBase werden Bloom-Filter genutzt, um vorab abzuschätzen, ob sich ein Festplattenzugriff lohnen könnte oder ein gesuchter Datensatz ohnehin an einer anderen Stelle gespeichert worden ist. Auch in der Zeitreihen-Datenbank InfluxDB oder im inoffiziellen Hadoop-Nachfolger Spark werden Bloom-Filter genutzt.

Frequenzabschätzung

Eine ganz offensichtliche Erweiterungsmöglichkeit für den zuvor beschriebenen Bloom-Filter ist die Verwendung eines Zähler-Arrays (z. B. aus Bytes) als Alternative für das Bit-Array. In Abwägung von Speicherplatz und "Reichweite" beim Zählen sind natürlich auch noch größere Datentypen mit 16 (Short), 32 Byte (Integer) oder gar 64 Bit (Long) möglich. Auf dieser Basis kann statt einer rein bool’schen Wahr/Falsch-Aussage auch eine Abschätzung gegeben werden, wie oft ein Wert in einer Wertemenge aufgetreten sein könnte. Zudem wird durch eine Subtraktion auch ein Löschen von Werten möglich.

Beim Anlegen eines sogenannten Counting-Bloom-Filters wird das Byte-Array, wie zuvor das Bit-Array, initial mit Nullwerten gefüllt und beim Eintragen eines Wertes wird der Byte-Wert an jeder durch die Hash-Funktionen errechneten Stelle um 1 erhöht. Somit kann ein Näherungswert für die Anzahl eines Wertes über den kleinsten Array-Eintrag gegeben werden. Beim Löschen eines Wertes wird entsprechend jeder errechnete Array-Eintrag bis minimal Null dekrementiert. Die folgenden Beispiele illustrieren das anhand des vorherigen Beispiels. Zunächst wird das Byte-Array mit acht Einträgen wieder mit Nullen initialisiert:

0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7

Werden nun die Werte 7 und 13 hineingeschrieben, ändert sich sein Inhalt wie folgt:

hf₁(7) = 0       1 0 1 0 0 0 0 0
hf₂(7) = 2       0 1 2 3 4 5 6 7

hf₁(13) = 2      1 0 2 0 0 0 1 0
hf₂(13) = 6      0 1 2 3 4 5 6 7

Zu beachten ist insbesondere die 2, die nun an Index zwei gespeichert ist. Ein weiteres Speichern einer 7 würde zu folgender Belegung der Array-Werte führen:

hf₁(7) = 0       2 0 3 0 0 0 1 0
hf₂(7) = 2       0 1 2 3 4 5 6 7

Bei einer Anfrage nach der Anzahl der gesehenen Vorkommen einer Sieben würde als Ergebnis das Minimum der Werte an den Positionen 0 und 2, also eine Zwei zurückgeliefert. Würde beispielsweise die 13 einmal aus der Datenstruktur gelöscht, bliebe folgende Array-Belegung zurück:

2 0 2 0 0 0 0 0
0 1 2 3 4 5 6 7

Die Mechanik des Counting-Bloom-Filters ist also ähnlich einfach wie die seines bool’schen Vorfahren, allerdings um den Preis eines deutlich größeren Speicherbedarfs.

Auch der sogenannte CountMin-Sketch schätzt die Frequenzen einzelner Elemente in einer großen Multimenge bzw. in einem großen Datenstrom ab und funktioniert dabei ganz ähnlich zum Counting-Bloom-Filter [7]. Auch er bildet die Input-Daten über eine Anzahl von Hash-Funktionen auf ein Zähler-Array ab, allerdings hat hier jede Hash-Funktion ihr eigenes üblicherweise deutlich kleineres Array. Und auch beim CountMin-Sketch ist der Näherungswert für die Frequenz eines Elements der kleinste Wert, der über alle Hash-Funktionen zu finden ist. Somit neigt auch der CountMin-Sketch zu falsch positiven Aussagen, also zu einem eventuellen Überschätzen der tatsächlichen Frequenzen, wird aber niemals zu niedrige Ergebnisse liefern. Durch eine Vergrößerung der Zähler-Arrays bei gleichzeitiger Erhöhung der Anzahl an Hash-Funktionen lässt sich die Wahrscheinlichkeit für Kollisionen und damit zu hohe Werte auch hier verringern.

Der Namensbestandteil "Sketch" spielt übrigens auf die skizzenhafte Darstellung der Eingabedaten bei der Datenspeicherung im CountMin-Sketch an. Diese ist deutlich speichersparender als bei den Bloom-Filter-Varianten. Während der Speicherbedarf der Letztgenannten linear (also in O(n)) wächst, kommt der CountMin-Sketch mit einem sublinearen Speicherwachstum und generell einem deutlich geringeren Speicherbedarf aus. Die Berechnung der Zahl der Hash-Funktionen d und der Anzahl der jeweils benötigten Zähler w ist beispielsweise in [7] erklärt, kurz gesagt muss 2/w gleich der gewünschten Fehlerwahrscheinlichkeit und (1/2)^d gleich dem gewünschten Konfidenzniveau sein.

Als Beispiel: Möchten wir n Elemente per CountMin-Sketch zählen und dabei eine maximale relative Abweichung in der Zählung von 0,1 Prozent bei 99,5 prozentiger Gewissheit dieser Limitierung tolerieren, erfordert dies folgende Berechnungen:

w = 2 / 0,001 = 2.000
d = log(0,005) / log(1/2) ~ 8

Somit erhalten wir bei 8 Hash-Funktionen und 4 Byte-Integer-Zählern einen Speicherbedarf von w * d * 4 = 64 kByte für das Zählerrarray und z. B. bei n = 100 Millionen eine absolute Zählerabweichung von maximal rund 100.000.

Auch für den CountMin-Sketch finden sich die üblichen Verdächtigen unter den Einsatzbereichen, wie beispielsweise Datenbanken, Text- und Stream-Analysen. Von der In-Memory-Datenbank Redis gibt es etwa einen spannend geschriebenen Blog-Beitrag über die dort verwendete Implementierung [8].

Quantilabschätzungen

Um ein Gefühl für einen nummerischen Datensatz zu bekommen, geben Analysten gerne den Mittelwert und dazu die Standardabweichung an. Das ergibt bei normalverteilten Werten, wie etwa der durchschnittlichen Größe einer Bevölkerung, zumindest ein ungefähres Bild über deren Verteilung. Es erlaubt sogar Aussagen wie "95 Prozent der Bevölkerung sind größer als x und kleiner als y", da in einer Normalverteilung per Definition ca. 95,5 Prozent aller Werte im Bereich von +/- 2 Standardabweichungen um den Mittelwert liegen.

Ab welcher Größe jemand allerdings zu den größten 10 Prozent der Bevölkerung gehört, ist mit diesen Angaben nicht ohne weiteres zu bestimmen. Gerade auch bei schiefen Verteilungen, wie beispielsweise der Latenz von Serverzugriffen ist ein Mittelwert oft wenig aussagekräftig. Bei diesem Beispiel handelt es sich um sogenannte Long-Tail-Verteilungen, bei denen viele Messwerte nahe des Nullpunkts liegen. Doch je weiter sich die Werte von dort entfernen, desto weniger gibt es auch, allerdings existieren immer einige Ausreißer mit sehr hohen Latenzzeiten, die damit auch den Mittelwert erheblich verfälschen können.

Abhilfe schafft hier der Median, der, wie der Name schon impliziert, der Wert ist, der bei einer (aufsteigenden) Sortierung der Daten genau in der Mitte liegt. Der Median ist gleichzeitig auch das zweite Quartil (Viertel) in einem Datensatz, entsprechend sind 50 Prozent der Werte kleiner und 50 Prozent der Werte größer als der Median. Das 25-Prozent- und 75-Prozent-Quartil sollten in diesem Kontext selbsterklärend sein. Noch allgemeiner können wir von Perzentilen, also Prozentstufen, sprechen: Das 13. Perzentil läge also an der Stelle eines sortierten Datensatzes, an der 13 Prozent aller Werte kleiner und 87 Prozent größer sind.

Da sich Median, Quartile bzw. allgemein Quantile nur auf sortierten Daten bestimmen lassen, sind sie für große, verteilte oder gar unbegrenzte Datenmengen (Datenströme) nur sehr schwer zu bestimmen, da eben alle Daten gespeichert und sortiert gehalten werden müssen. Speziell (NoSQL-)Datenbanken bieten entsprechend des hohen Berechnungsaufwands in einem potenziell verteilten System oft erst gar keine Funktion dafür an. Abhilfe dafür versprechen abermals sogenannte Sketching- oder Digest-Verfahren, die den Verlauf einer Häufigkeitsverteilung anhand von charakteristischen Werten "skizzieren" und zusammen mit statistischen Metadaten abspeichern, um auf dieser Basis nachhaltig skalierbar ungefähre Quantilwerte abschätzen zu können. Oder mit anderen Worten, diese Verfahren speichern intern eine komprimierte Darstellung der kumulierten Verteilungsfunktion (engl. Cumulative Distribution Function (CDF)) der gesehenen Daten ab.

Entsprechende Implementierungen waren bis vor Kurzem noch recht grob, der erstmals 2013 vorgestellte t-digest-Ansatz hat jedoch einen bemerkenswerten Fortschritt gebracht. Er liefert bei einem Speicherverbrauch von nur wenigen Kilobytes auch auf großen Datenbeständen zuverlässig Perzentilwerte mit einem Fehler von üblicherweise unter einem Prozent. t-digest ist im GitHub-Repository seines Entwicklers Ted Dunning frei in einer Java-Implementierung verfügbar [9]. Dort sind auch weitere freie Implementierungen in zahlreichen anderen Sprachen verlinkt.

Die Nutzung des t-digest in Java ist denkbar einfach, aktuell gibt es zwei Implementierungen: eine, die auf AVL-Bäumen basiert (AVLTreeDigest) und eine, die neu gesammelte Daten in eine Liste von Datenpunkten mergt (MergingDigest). Im folgenden Code-Beispiel wird eine AVLTreeDigest-Instanz erzeugt und mit eintausend Zahlen befüllt, um danach das 50-Prozent-Quantil, also den Median abzufragen. Am Ende wird umgekehrt noch die Verteilungsfunktion abgefragt, um zu erfahren, welcher Anteil der gespeicherten Werte kleiner als fünf ist. In diesem Beispiel liefert der t-digest etwa 0,55 Prozent.

TDigest td = new AVLTreeDigest(100);
IntStream.range(0, 1000).forEach(n -> td.add(n));
System.out.println(td.quantile(0.5));
System.out.println(td.cdf(5));

Die 100 im Konstruktor des Code-Beispiels ist ein Kompressionsfaktor, der die Anzahl der Daten-Cluster im t-digest bestimmt (in diesem Fall ca. 5 x 100) und damit auch den Fehler festlegt (laut Quellcode in diesem Beispiel bei maximal etwa 3 Prozent (3 / 100)).

Intern speichert ein t-digest alle übergebenen Zahlenwerte in einer begrenzten Zahl von Daten-Clustern ab und hält diese sortiert. Pro Cluster wird ein Mittelwert (Dunning nennt es Centroid) aller Werte gebildet, die bisher dort eingefügt worden sind. Eine neu übergebene Zahl wird zunächst immer dem Cluster mit dem nächstliegenden Mittelwert zugewiesen. Um die Genauigkeit zu erhöhen, erhalten sowohl die Cluster selbst, als auch die eingefügten Werte zusätzlich einen Gewichtswert, der sich aus der Anzahl der übergebenen Werte ergibt. Dieser erlaubt es insbesondere auch mehrere t-digest-Instanzen miteinander zu mergen und ferner die Größe der Clusters zu beschränken, was von zentraler Bedeutung für den Erhalt der Genauigkeit des Ansatzes ist.

Abhängig von der Gesamtanzahl an gespeicherten Werten erhält jeder Cluster entsprechend ein Maximalgewicht, das er nicht überschreiten darf. Dieses ist jedoch nicht gleich verteilt über alle Cluster, wie sich das naiv erwarten ließe, sondern nimmt zu den Rändern hin ab. Dunning begründet das damit, dass etwa bei der Überwachung eines Service Level Agreements (SLA) beispielsweise das am rechten Rand liegende 99,5-Prozent-Quantil eine deutlich höhere Genauigkeit benötigt als etwa der Median.

Praktisch aus Sicht von Big-Data-Anwendungen ist die zuvor schon angesprochene Aggregierbarkeit von t-digests, so dass auch in einem verteilten System, wie beispielsweise in einer MapReduce-Umgebung in Hadoop oder Spark Teile der Gesamtdaten auf einzelnen Maschinen mit Hilfe eines t-digest analysiert werden können und die relativ kleinen Ergebnisse dann auf einer Maschine gesammelt und zum Endergebnis zusammengefasst werden können.

Fazit

Egal ob man sie als Algorithmen oder Datenstrukturen betrachten möchte, die in diesem Beitrag vorgestellten Verfahren haben alle zwei Eigenschaften gemeinsam: Sie ermöglichen den ressourcenschonenden Umgang mit großen Datenmengen, wenn sie dafür auch gewisse Unschärfen bei der Datenqualität billigend in Kauf nehmen (müssen):

There is just no such thing as a free lunch.

Das mag in der an deterministische Verarbeitungen gewöhnten Informatik ein Grund dafür sein, warum die beschriebenen Verfahren nur etwas "verschämt" Eingang in viele Anwendungen wie Datenbanken oder Suchmaschinen gefunden haben und sie der breiten Fachöffentlichkeit noch eher unbekannt sind. Wer will sich schon immer wieder bewusst machen, dass Datenzählungen in vielen Big-Data-Systemen nur näherungsweise genau sein können, da sonst wesentlich mehr Hardware oder Laufzeit gebraucht werden würde? Unterm Strich kommt es bei Milliarden von Daten auf ein paar zehntausend eben oft nicht wirklich an. Wem Eventual Consistency in NoSQL-Datenbanken recht ist, dem kann Probabilistic Accuracy in Datenstrukturen bei den genannten Vorteilen nur billig sein.

Welches Verfahren bei welcher Fragestellung unter welchen Voraussetzungen zum Einsatz kommen kann, fasst Tabelle 3 abschließend noch einmal zusammen.

Tabelle 3: Übersicht der vorgestellten probabilistischen Datenstrukturen

Name	Zweck	Vorteile	Nachteile	Beispielhafte Nutzungen	Quelle
HyperLogLog	Wie viele einzigartige Elemente sind in einer Menge enthalten? (Kardinalität)	Große Speicherersparnis, gute Verteilbarkeit, Pseudonymisierung der Daten	Ungenauigkeit von ca. 3 Prozent	Für Anzahl der Suchergebnisse in Elasticsearch oder für verteiltes count(distinct) in PostgreSQL	[2]
Bloom-Filter	Ist ein Element in einer Menge enthalten? (Mitgliedschaft)	Zeit- und Speicherersparnis, Pseudonymisierung der Daten, gut einstellbare Genauigkeit	Falsch positive Ergebnisse möglich, Löschen von Datensätzen nicht	Zur Vermeidung von Plattenzugriffen in Cassandra und HBase	[5]
CountMin-Sketch	Wie oft ist ein Element in einer Menge enthalten?	Große Zeit- und Speicherersparnis, gut einstellbare Genauigkeit	Bei geringen Frequenzen große Überschätzungen möglich	In der Anfrageoptimierung von Datenbanken	[7]
T-Digest	Bestimmung von Perzentilwerten (wie bspw. Median)	Sehr gut skalierbar, Vermeidung einer zeitraubenden Sortierung von großen Datenmengen	Mögliche Unschärfen außerhalb der Randbereiche, Qualität noch nicht theoretisch bewiesen	Quantil-Berechnung in Postgres und Elasticsearch	[9]

Autor

Das könnte Sie auch interessieren