Datenanalyse in SQL: Pivot-Tabellen

Wer als Data Scientist etwas auf sich hält, arbeitet heute meist mit Python oder R, um Daten zu analysieren. Was oft übersehen wird, ist die Tatsache, dass viele gängige Datenanalysen auch ganz klassisch unter Verwendung von SQL in relationalen Datenbanken möglich sind, ohne dass ein Export in andere Systeme notwendig wäre. Natürlich stehen nicht immer alle gewünschten Funktionen "out of the box" zur Verfügung, doch gewusst wie, lassen sich auch aus einer Datenbank viele interessante Analysen herauskitzeln.

Ein spannendes Beispiel dafür sind sicher die sogenannten Pivot-Tabellen (engl. to pivot = schwenken, drehen), die vor allem in Tabellenkalkulationen gerne genutzt werden, um Daten zu analysieren. Ich möchte im Folgenden kurz beschreiben, wie sich Pivot-Tabellen in SQL (getestet auf MySQL 5.7) umsetzen lassen. Alle notwendigen SQL-Befehle sind im Verlauf des Posts angegeben und können direkt in einen SQL-Client kopiert und ausprobiert werden.

Beginnen wir mit einer einfachen Tabelle, die einige Daten zu Mitarbeitern vorhalten kann:

  create table Mitarbeiter (
     id int primary key auto_increment, 
     Name varchar(20), 
     Geschlecht char(1),
     Abteilung varchar(10), 
     Standort varchar(20), 
     Gehalt int
  );

Befüllen wir sie im Anschluss mit einigen Beispieldaten. Die dafür notwendigen "Inserts" stehen am Ende des Posts, damit sie hier den Lesefluss nicht unnötig stören. 

Danach können wir uns den Inhalt der Tabelle (DB-Fiddle) wie gewohnt ausgegeben lassen:

  select * from Mitarbeiter;

+----+-----------------------+------------+-----------+------------+--------+

| id | Name                  | Geschlecht | Abteilung | Standort   | Gehalt |
+----+-----------------------+------------+-----------+------------+--------+
|  1 | Müller                | m          | DEV       | Mannheim   |  70000 |
|  2 | Mayer                 | m          | OPS       | Mannheim   |  65000 |
|  3 | Schulze               | m          | DEV       | Heidelberg |  60000 |
|  4 | Norris                | m          | MNMT      | Mannheim   | 100000 |
|  5 | Heinz                 | w          | TEST      | Heidelberg |  75000 |
|  6 | Steiger               | m          | TEST      | Mannheim   |  60000 |
|  7 | Müller-Lüdenscheidt   | m          | DEV       | Frankfurt  |  68000 |
|  8 | Young                 | m          | TEST      | Frankfurt  |  63000 |
|  9 | Stein                 | m          | MNMT      | Mannheim   |  80000 |
| 10 | Pape                  | w          | OPS       | Frankfurt  |  70000 |

| 11 | Müller                | w          | DEV       | Frankfurt  |  70000 |
+----+-----------------------+------------+-----------+------------+--------+

Histogramm

Eine erste interessante statistische Analyse könnte die Erstellung eines (textuellen) Histogramms sein, das uns die Anzahl der Mitarbeiter pro Abteilung ermittelt. Dies funktioniert in SQL noch ohne allzu große Klimmzüge, in dem wir nach der Abteilung gruppieren und die Anzahl der jeweiligen Einträge zählen lassen. Konkret also durch Verwendung von "group by" und "count":

  select Abteilung, count(*) as Anzahl from Mitarbeiter
                                            group by Abteilung;

+-----------+--------+

| Abteilung | Anzahl |

+-----------+--------+
| DEV       |      4 |
| MNMT      |      2 |
| OPS       |      2 |
| TEST      |      3 |
+-----------+--------+

Analog ließe sich eine solche Anfrage natürlich auch für die Standorte oder die Geschlechter erstellen. 

Pivot-Tabelle

Doch wie gehen wir vor, wenn wir beispielsweise die Verteilung der männlichen und weiblichen Mitarbeiter pro Abteilung ermitteln möchten? Dazu müssten die Einträge in der Spalte Geschlecht gezählt und "m" und "w" selbst zu Spaltenüberschriften werden, während die Namen der Abteilungen zu Zeilenbenennungen werden, wie in der folgenden Pivot-Tabelle gezeigt:

 +-----------+---+---+--------+
| Abteilung | m | w | Gesamt |
+-----------+---+---+--------+
| DEV       | 3 | 1 |      4 |
| MNMT      | 2 | 0 |      2 |
| OPS       | 1 | 1 |      2 |
| TEST      | 2 | 1 |      3 |
+-----------+---+---+--------+

Dieses Vorgehen verdeutlicht noch einmal die Herkunft des Namens "Pivot" und wirft vermutlich zeitgleich die Frage auf, ob und wie sich eine solche Tabelle in SQL erzeugen lässt? 

Wie wir gleich sehen werden, ist das gar nicht so kompliziert. Es reicht die geschickte Verwendung einer if-Abfrage, die nicht nur in Programmiersprachen, sondern eben auch in SQL zur Verfügung steht:

  select Abteilung, 
         count(if (Geschlecht = 'm', id, null)) as m, 
         count(if (Geschlecht = 'w', id, null)) as w, 
         count(*) as Gesamt 
  from Mitarbeiter group by Abteilung;

Wichtig ist wiederum das "group by" am Ende, um die Zuordnung der Werte zu den Abteilungen zu erhalten. Die farbliche Codierung soll verdeutlichen, welcher Teil der SQL-Abfrage für welches Ergebnis in der vorherigen Tabelle verantwortlich ist. 

Kurz gesagt prüft die Datenbank also, ob der gerade betrachtete Mitarbeiter männlich oder weiblich ist, um ihn oder sie bei der jeweiligen Abteilung zu zählen. Da Null-Werte von der Count-Funktion ignoriert werden, besteht der Kniff schlicht darin, über das If ein Null für den Zähler bei männlich zurückzugeben, wenn es sich um eine Mitarbeiterin handelt und umgekehrt.

Komplexere Pivot-Tabellen?

Diese Vorgehensweise ist für zwei vorab bekannte und sich nicht ändernde Geschlechter sicher praktisch und - einmal verstanden - auch nicht zu kompliziert in der Anwendung. Was aber, wenn wir uns die Verteilung der Mitarbeiter pro Standort wie folgt auflisten möchten? 

+-----------+-----------+------------+----------+--------+
| Abteilung | Frankfurt | Heidelberg | Mannheim | Gesamt |
+-----------+-----------+------------+----------+--------+
| DEV       |         2 |          1 |        1 |      4 |
| MNMT      |         0 |          0 |        2 |      2 |
| OPS       |         1 |          0 |        1 |      2 |
| TEST      |         1 |          1 |        1 |      3 |
+-----------+-----------+------------+----------+--------+

Momentan enthalten unsere Datensätze zwar nur drei verschiedene Standorte und diese ließen sich zur Not noch per Hand in eine Query schreiben, doch das wird mit zunehmender Zahl der Standorte unbestreitbar immer mühseliger.Vor allem wenn wir vorab vielleicht gar nicht wissen, welche Standorte in unseren Daten überhaupt vorkommen.

Variablen

Für diese Herausforderung bietet SQL abermals eine elegantere Lösung: Pivot-Tabellen lassen sich nämlich auch mit Hilfe von Variablen und Prepared Statements ohne allzu großen Aufwand dynamisch erzeugen. Daher zunächst zwei Sätze zu Variablen: diese können beliebige primitive Datentypen (also z.B. Zahlen oder Zeichenketten) aufnehmen und werden durch ein vorangestelltes @ gekennzeichnet. Definiert und belegt werden sie wie folgt:

  set @answer = 42;

Ihr Inhalt kann über ein einfaches Select ausgegeben werden oder auch an passender Stelle innerhalb eines "select ... from ... where":

  select @answer;

+---------+
| @answer |
+---------+
|      42 |
+---------+

Es ist zudem möglich, die Ergebnisse von Abfragen, die einen Einzelwert (also keine Tabelle mit mehreren Spalten) zurückliefern, per "into" in eine Variable zu speichern:

  select count(*) from Mitarbeiter into @rows;

Prepared Statements

Unter Verwendung von Variablen und sogenannten Prepared Statements können wir problemlos auch eine SQL-Abfrage zusammenzubauen, sie speichern und sie erst bei Bedarf ausführen. Auch das ist SQL-typisch sehr pragmatisch machbar:

  set @var =  'select * from Mitarbeiter;'; 

  prepare stmt from @var;

  execute stmt;

Dynamische Pivot-Tabellen

Zusammengemischt können diese Zutaten verwendet werden, um Pivot-Tabellen mit vielen Spalten dynamisch zu erzeugen. Das funktioniert mit der Concat-Funktion zur Verkettung von Zeichenketten wie folgt:

  select group_concat(
    distinct concat('count(
      if (Standort=''', Standort, ''', id, null)) as ', Standort)) 
  from Mitarbeiter into @ifs;

Betrachten wir uns den Inhalt der erzeugten Variable, erkennen wir, dass dieses Statement die "count-if"-Statements der Pivot-Tabelle für jeden Standort erzeugt und diese über die group_concat-Funktion wiederum miteinander verkettet:

  count(if (Standort='Frankfurt', id, null)) as Frankfurt,
  count(if (Standort='Heidelberg', id, null)) as Heidelberg,
  count(if (Standort='Mannheim', id, null)) as Mannheim

Zu beachten ist im grün markierten Teil des Statements noch die Verwendungen der Anführungszeichen: zwei ' hintereinander "escapen" ein Anführungzeichen, das in der Ergebniszeichenkette benötigt wird, das dritte ' schließt den String an dieser Stelle ab. D.h. die beiden fett markierten Standorte befinden sich außerhalb der Anführungszeichen und werden iterativ mit jedem Standortnamen befüllt. Entfernt man alle Concat-Operationen wird also nur die folgende einfache Query ausgeführt:

  select distinct Standort from Mitarbeiter;

Nun muss zum Abschluss die gerade in @ifs gespeicherte Zeichenkette in den Rest des Statements zur Erzeugung der Pivot-Tabelle eingesetzt werden...

  set @piv = concat(
                'select Abteilung,', @ifs, ', count(*) as Gesamt
                 from Mitarbeiter group by Abteilung;'
  );

... sowie das Prepared Statement erzeugt und ausgeführt werden:

  prepare stmt from @piv;
  execute stmt;

Das ergibt die oben bereits gezeigte Pivot-Tabelle mit einer Aufstellung der Mitarbeiter pro Standort:

+-----------+-----------+------------+----------+--------+
| Abteilung | Frankfurt | Heidelberg | Mannheim | Gesamt |
+-----------+-----------+------------+----------+--------+
| DEV       |         2 |          1 |        1 |      4 |
| MNMT      |         0 |          0 |        2 |      2 |
| OPS       |         1 |          0 |        1 |      2 |
| TEST      |         1 |          1 |        1 |      3 |
+-----------+-----------+------------+----------+--------+ 

Zum Abschluss sei noch eine etwas spannendere Analyse vorgestellt: um das Durchschnittsgehalt der Mitarbeiter pro Standort und Abteilung zu erhalten, müssten wir unsere Statements von oben nur an drei Stellen wie folgt abändern:

  select group_concat(
    distinct concat('avg(
      if (Standort=''', Standort, ''', Gehalt, null)) as ', Standort)) 
  from Mitarbeiter into @ifs;

und:

  set @piv = concat(
      'select Abteilung,', @ifs, ', avg(Gehalt) as Gesamt
       from Mitarbeiter group by Abteilung;'
  );


Mit ...

  prepare stmt from @piv;
  execute stmt;

... ergibt sich abschließend die folgende Tabelle mit den Durchschnittsgehältern pro Standort, und das ganz ohne Excel, R oder Python:

+-----------+------------+------------+------------+------------+
| Abteilung | Frankfurt  | Heidelberg | Mannheim   | Gesamt     |
+-----------+------------+------------+------------+------------+
| DEV       | 69000.0000 | 60000.0000 | 70000.0000 | 67000.0000 |
| MNMT      |       NULL |       NULL | 90000.0000 | 90000.0000 |
| OPS       | 70000.0000 |       NULL | 65000.0000 | 67500.0000 |
| TEST      | 63000.0000 | 75000.0000 | 60000.0000 | 66000.0000 |
+-----------+------------+------------+------------+------------+

Verwendete Beispiel-Daten:

insert into Mitarbeiter values (null,'Müller','m','DEV','Mannheim',70000);

insert into Mitarbeiter values (null,'Mayer','m','OPS','Mannheim',65000);

insert into Mitarbeiter values (null,'Schulze','m','DEV','Heidelberg',60000);

insert into Mitarbeiter values (null,'Norris','m','MNMT','Mannheim',100000);

insert into Mitarbeiter values (null,'Heinz','w','TEST','Heidelberg',75000);

insert into Mitarbeiter values (null,'Steiger','m','TEST','Mannheim',60000); 

insert into Mitarbeiter values (null,'Müller-Lüdenscheidt','m','DEV','Frankfurt',68000);

insert into Mitarbeiter values (null,'Young','m','TEST','Frankfurt',63000);

insert into Mitarbeiter values (null,'Stein','m','MNMT','Mannheim',80000);

insert into Mitarbeiter values (null,'Pape','w','OPS','Frankfurt',70000);

insert into Mitarbeiter values (null,'Müller','w','DEV','Frankfurt',70000);

Bloom-Filter 2.0: der Count-Min Sketch

Der sogenannte Count-Min Sketch weißt eine deutliche Ähnlichkeit zum zählenden Bloom-Filter auf (daher am besten zuvor diesen Post lesen). Es geht darum, abschätzen zu können, wie oft ein bestimmtes Element in einem sehr großen Datenstrom, den wir  aus Platzgründen nicht in einer HashMap speichern können oder wollen, vorgekommen ist.

Folgendes Beispiel soll die Anwendung illustrieren: angenommen, wir haben A, C, D, C, A, B, B, A, B, A, P, P als Datenstrom, dann ergibt eine Zählung der Elemente folgendes Ergebnis: 4 x A, 3 x B, 2 x C, 1 x D und 2 x P. Eine konkrete Anwendung für dieses Szenario wäre z.B. das Zählen der Page-Impressions auf diversen Unterseiten einer großen Webseite.

Noch einmal anders ausgedrückt: wir möchten in einer sehr großen Multimenge zählen, wie oft jedes Mengenelement vorgekommen ist.

Aufbau und Mechanik

Auch der Count-Min Sketch ist eine probablistische Datenstruktur, die auf Hash-Funktionen basiert. Verwenden wir (wie beim Bloom-Filter) d = 2 beliebige Hash-Funktionen für die ASCII-Werte unserer Buchstaben (A = 65, B = 66, C = 67, D = 68, P = 80) im Datenstrom:

h₁ = ASCII-Wert modulo 8

h₂ = (ASCII-Wert - 65) * 2 modulo 8

Anders als beim Bloom-Filter erhält allerdings jede Hash-Funktion ihr eigenes Zähler-Array za₁ und za₂ mit jeweils w Einträgen. Beide werden initial vollständig mit Nullen befüllt:

za₁: 0 0 0 0 0 0 0 0

 za₂: 0 0 0 0 0 0 0 0 

        0 1 2 3 4 5 6 7

Nun berechnen wir die Hash-Werte für unseren Datenstrom:

h₁:               h₂:

A -> 1          A -> 0

B -> 2          B -> 2

C -> 3          C -> 4

D -> 4          D -> 6

 P -> 0           P -> 6

Und aktualisieren za₁ und za₂ der Reihe nach, indem wir an der entsprechenden Stelle eins hinzu addieren z.B. für das erste A:

za₁: 0 1 0 0 0 0 0 0

 za₂: 1 0 0 0 0 0 0 0 

        0 1 2 3 4 5 6 7

Für das erste C:

za₁: 0 1 0 1 0 0 0 0

 za₂: 1 0 0 0 1 0 0 0 

        0 1 2 3 4 5 6 7

Für das D:

za₁: 0 1 0 1 1 0 0 0

 za₂: 1 0 0 0 1 0 1 0 

        0 1 2 3 4 5 6 7

Für das zweite C:

za₁: 0 1 0 2 1 0 0 0

 za₂: 1 0 0 0 2 0 1 0 

        0 1 2 3 4 5 6 7

Und so weiter, bis wir schließlich folgende beiden Arrays erhalten:

za₁: 2 4 3 2 1 0 0 0

 za₂: 4 0 3 0 2 0 3 0 

        0 1 2 3 4 5 6 7

Wir sehen, dass sich dabei durch die Kollision der Hash-Werte von D und P in h2 eine kleine "Verfälschung" (rot markiert) ergibt. Diese ist allerdings insofern (noch) nicht von Bedeutung, als wir bei einer Abfrage immer den kleinsten Wert aus beiden Arrays zurückgeben, also min(za₁, za₂) an dem Index, der durch die jeweilige Hash-Funktion geliefert wird. 

Für A wäre also za₁[1] = 4 und za₂[0] = 4, hier besteht sogar eine Übereinstimmung. Betrachten wir uns D, ergibt sich folgendes Bild: za₁[4] = 1 und za₂[6] = 3, der Eintrag in za₂ wurde durch D verfälscht, wir geben aber den kleinsten der beiden Werte zurück und erhalten als Abschätzung für die Anzahl der Ds korrekterweise eine Eins.

Dieser günstige Umstand wird leider nicht dauerhaft erhalten bleiben, angenommen, als nächstes taucht ein X (ASCII = 88) im Datenstrom auf, hier errechnet h₁ eine 0 und h₂ eine 6, so dass unsere Arrays nun wie folgt belegt wären:

za₁: 3 4 3 2 1 0 0 0

 za₂: 4 0 3 0 2 0 4 0 

        0 1 2 3 4 5 6 7

Nun würde sowohl eine Abfrage für X, als auch eine Abfrage für P ein überschätztes Ergebnis, nämlich jeweils 3 liefern, womit wir die Schwäche des Count-Min-Sketch-Ansatzes aufgedeckt haben.

Eine weitere interessante Eigenschaft des Count-Min Sketchs ist, dass er durch die Verwendung der Hash-Funktionen die gespeicherten Daten anonymisiert. Unter Datenschutzgesichtspunkten lässt sich das durchaus als Vorteil sehen, da es zwar beispielsweise möglich ist, zu prüfen, ob eine gegebene IP-Adresse bereits gespeichert wurde, es kann aber keine Liste von vorhandenen IP-Adressen generiert werden.

Genauigkeit
Durch eine Vergrößerung des Bit-Arrays und eine Erhöhung der Anzahl an Hash-Funktionen lässt sich die Wahrscheinlichkeit für Kollisionen und damit False Positives natürlich verringern. Die Berechnung der Zahl der Hash-Funktionen d und der Anzahl der jeweils benötigten Zähler w ist beispielsweise in [2] erklärt, kurz gesagt müssen 2/w gleich der gewünschten Fehlerwahrscheinlichkeit und (1/2)^d gleich dem gewünschten Konfidenzniveau sein.

Als Beispiel: wir möchten N Elemente per Count-Min Sketch zählen, dabei eine maximale relative Abweichung in der Zählung von 0,1% bei einer 99,5%igen Sicherheit tolerieren; dies erfordert folgende Berechnungen:

w = 2 / 0,001 = 2.000

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

Somit erhalten wir bei 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 maximale absolute Zählerabweichung von rund 100.000.

Literaturverweise

1. das Original-Paper (schwer verdaulich)
2. ein leichter verdauliches Paper

Was bedeutet Big Data für die Software-Entwicklung?

In diesem Post möchte ich eine Definition von Big Data jenseits der üblichen V⁴-Definitionen versuchen und insbesondere auf die wichtigsten Herausforderungen aus Sicht der Software-Entwicklung eingehen.

Der Vollständigkeit halber, Big Data wird häufig über die folgenden Begriffe definiert:

• Volume: die "übliche" Datenmenge wird heutzutage ungefähr im Terabyte-Bereich angesiedelt; nicht zu vergessen ist sicher auch eine große Menge von Benutzern, die bei der Systementwicklung zu ähnlichen Herausforderungen führen kann, wie eine große Datenmenge
• Velocity: die anfallenden Daten müssen ausreichend schnell verarbeitet werden können, oftmals als Streams in quasi Echtzeit, weil sie nicht komplett gespeichert, geschweige denn sinnvoll wieder abgerufen werden können
• Variety: vielfach fallen Daten aus unterschiedlichen Quellen an, die ggf. auch unterschiedlich gespeichert werden müssen
• Veracity: in vielen Fällen (z.B. bei der Verarbeitung von Sensordaten o.ä.) kann nicht garantiert werden, dass diese Daten vollständig und korrekt sind

Aus betriebswirtschaftlicher Sicht kommt noch Value als fünftes V hinzu, schließlich möchte niemand Daten um ihrer Anmut Willen sammeln, sondern es sollte sich aus ihrer Analyse ein Wert für die Unternehmung generieren lassen. Die ziellose Installation eines Hadoop-Clusters, wie es zumindest in den Anfangsjahren des Big-Data-Hypes häufig in der Industrie zu beobachten war, dient diesem Ziel übrigens nicht.

Eine aus Entwicklersicht pragmatischere Definition für Big Data lautet, dass es sich um Datenmengen handelt, die nicht mehr auf einem Rechner gespeichert oder verarbeitet werden können. Dabei spielt  es zunächst einmal keine Rolle, ob es sich um einen handelsüblichen Laptop, einen ausgewachsenen Server oder einen Minicomputer wie einen Rapsberry Pi handelt. Sobald eine Parallelverarbeitung von Daten auf mehreren Rechnern notwendig ist, ändern sich die Spielregeln bzgl. der Verarbeitung und es tauchen neue Herausforderungen auf. Aus meiner Erfahrung bei der Entwicklung eines großen Informationssystems heraus insbesondere die vier im Folgenden beschriebenen:

1. Zunächst ist natürlich die nachhaltige Skalierbarkeit eines Systems eine zentrale Schwierigkeit. Große Datenmengen haben nämlich oft die unangenehme Eigenschaft beständig weiter zu wachsen. Dieser Herausforderung versuchen wir über ein Skalieren unserer Hardware zu begegnen. Die traditionelle Skalierung über leistungsfähigere Prozessoren (sog. vertikale Skalierung) ist mit der Stagnation der Taktraten ins Stocken geraten. Heute üblich ist meist die sogenannte horizontale Skalierung, also das Hinzunehmen weiterer Rechner und damit die Verteilung der Aufgabenlast auf weitere "Schultern". Grundvoraussetzung, damit dies dauerhaft sinnvoll funktionieren kann, ist eine maximal lineare Komplexität (d.h. eine Komplexität kleiner oder gleich O(n)) der im System ausgeführten Algorithmen. Weißt ein Algorithmus eine höhere Komplexität auf, also beispielsweise O(n log n) oder gar O(n²), benötigen wir bei einer Verdopplung der zu verarbeitenden Datenmenge bei letzterem bereits eine Vervierfachung der Hardware, was auf Dauer offensichtlich nicht gelingen kann (vgl. z.B. auch diesen Blog-Eintrag).
2. Die zweite zentrale Herausforderung liegt in der Parallelverarbeitung der Daten begründet. Hier führt nämlich spätestens das Persistieren von Daten nach klassischen Small-Data-Ansätzen zu den üblichen Wettlauf-Bedingungen, vor denen wir in Vorlesungen zur Parallelverarbeitung immer gewarnt wurden. Betrachten wir uns als Beispiel eine replizierte relationale Datenbank, die das gleiche Tupel auf mehreren Maschinen schreiben oder ändern muss: unter ACID-Garantien ist dieses Unterfangen meist mit einem größeren Locking-Aufwand verbunden, der beim Hinzunehmen von weiteren Servern natürlich nicht geringer wird. Das hat unter dem Eindruck des CAP-Theorems zur weiten Verbreitung des BASE-Prinzips geführt (dieses Thema werde ich bei passender Gelegenheit noch einmal vertiefen). Aber auch das in Hadoop zum Einsatz kommende Map-Reduce-Vorgehen ist vor allem der Notwendigkeit geschuldet, gleiche Einträge (bzw. Schlüssel) an eine Maschine im Cluster zu routen, um sie von dort ggf. lockfrei persistieren zu können. Dieses sogenannte Partitioning zieht sich wie ein roter Faden durch die Big-Data-Frameworks und NoSQL-Datenbanken, sobald Daten nicht mehr auf einer Maschine verarbeitet werden kann, müssen wir uns sehr genau überlegen, wie wir die Daten aufteilen wollen.
3. Die dritte Herausforderung der sich Big-Data-Entwickler gegenüber sehen, ist das beständige Ausreizen der gegebenen Hardware, das häufig eine Umkehrung der Vorgehensweise bei der Systemmodellierung erfordert. Klassische objektorientierte Modellierung baut grob gesprochen die Welt in Software nach und vertraut ihre Persitenz einem O/R-Mapper und einer relationalen Datenbank an. Wie unter Punkt 2 angerissen, sind diese für große Datenmengen oft nicht ausreichend performant, was zunächst einmal der NoSQL-Bewegung Auftrieb gegeben hat. Aber schlimmer noch, selbst eine einzelne NoSQL-Datenbank ist selten in der alle Persistenzanforderungen eines Systems abzudecken. Aufwändige Performance-Tests zur Ermittlung einer ausreichend leistungsfähigen Kombination von Datenbanken und eine "polyglot persistence" sind die logische Folge. Ihre Synchronisation in Fehlersituationen ist unter dem Einfluss des CAP-Theorems ebenfalls kein triviales Problem.
4. Ein vierter herausfordernder Punkt ist in der Komplexität (im Sinne von vielen verschiedenen Komponenten) der erstellten Systeme zu sehen. Auch die oben angesprochene horizontale Skalierung trägt ihr Scherflein dazu bei, dass Big-Data-Systeme immer mit Ausfällen und Problemen einzelner Komponenten rechnen müssen und damit umgehen können sollten (sog. Resilience). Eine weitere schmerzvolle Erfahrung, die wohl jeder Big-Data-Entwickler schon einmal gemacht hat, ist die, dass Skalierbarkeit noch lange nicht bedeutet, dass ein System in der Praxis auch tatsächlich skaliert. Oft sind es Kleinigkeiten, wie fehlende File Handles o.ä., die ein System bei steigender Last kapitulieren lassen. Nichtsdestotrotz müssen die Probleme natürlich behoben werden, so dass Last- und Perfomancetests bis an die Grenzen des Erwarteten und darüber hinaus ein unverzichtbarer Bestandteil der Systementwicklung werden. Dass es oft sehr teuer oder aus Kostengründen gar unmöglich ist, ein zum Produktivsystem identisches Testsystem vorzuhalten und passende Lastszenarien zu simulieren, liegt auf der Hand. Bei Netflix werden entsprechende Tests daher mittlerweile am Produktivsystem ausgeführt (vgl. hier).

Weiterführend habe ich mit einigen Kollegen einen Fachartikel zu dem Thema geschrieben, der hier (als kostenloser Preprint) gelesen werden kann: O. Hummel, H. Eichelberger, A. Giloj, D. Werle, K. Schmid: A Collection of Software Engineering Challenges for Big Data System Development, Euromicro SEAA, 2018.

Bloom-Filter zur Prüfung von Mengenzugehörigkeit

Beginnen wir mit einem einfachen Beispiel, um den Verwendungszweck von Bloom-Filtern zu umreißen. In großen Datenbeständen ist das Durchsuchen bzw. Überprüfen von Listen auf einen bestimmten Eintrag häufig aufwendig. Nämlich insbesondere dann, wenn der Eintrag gar nicht enthalten ist, da in diesem Fall die komplette Liste durchlaufen werden muss. Könnten wir allerdings vorab mit einer platzsparenden Datenstruktur überprüfen, ob ein Eintrag überhaupt in der Datenbank gespeichert sein kann, ließe sich einiges an Aufwand einsparen. 

Dazu im Folgenden ein kurzes Beispiel zur Illustration der Funktionalität eines Bloom-Filters: nehmen wir an, wir hätten den Datenstrom A, C, D, C, B, A, P, P in einer Datenbank gespeichert und möchten danach überprüfen, ob A, C und X in unserem Speicher enthalten sind. Der Bloom-Filter würde das bei A und C bejahen und bei X verneinen. Für X brauchen wir also keine teuere Suche in der Datenbank zu unternehmen. Der klassische ("Small Data") Lösungsansatz wäre die Verwendung einer Hash-Tabelle, die allerdings deutlich mehr Speicherplatz benötigt, als ein Bloom-Filter.

Da Bloom-Filter zu den probabilistischen Datenstrukturen gehören, arbeiten sie zwar speichersparend und schnell, haben aber leider auch eine Schattenseite: sie können False Positives zurückliefern. Es besteht also die Gefahr, dass ein Bloom-Filter angibt, einen Wert gespeichert zu haben, den er tatsächlich noch nicht zu Gesicht bekommen hat. Immerhin kann niemals der umgekehrte Fall vorkommen: Werte, die der Bloom-Filter gespeichert hat, wird er auch definitiv als bekannt markieren. Sogenannte False Negatives sind also ausgeschlossen.

Zur Mechanik
Schauen wir uns als nächstes die "Mechanik" eines Bloom-Filters genauer an: im Wesentlichen besteht er aus einem hinreichend großen Bit-Array der Länge n und einer Reihe von Hash-Funktionen. Soll dem Filter nun ein Wert hinzugefügt werden, wird dieser von allen Hash-Funktionen verarbeitet und jedes Bit, dessen Index im Bit-Array dem Ergebnis einer Hash-Funktion entspricht, auf eins gesetzt. Das folgende, bewusst einfache Beispiel soll dieses Vorgehen illustrieren:

Wir benötigen ein Bit-Array ba mit beispielsweise n = 8 (0..7) Einträgen, die zu Beginn alle mit Nullen (bzw. mit false) belegt werden:

0 0 0 0 0 0 0 0

0 1 2 3 4 5 6 7

Ferner verwenden wir mehrere bzw. im Beispiel genau zwei Hash-Funktionen hf₁ und hf₂, die idealerweise alle Eingaben e_i auf Werte zwischen 0 und 7 abbilden:

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

Ferner benötigen wir natürlich einige beispielhafte Eingaben: e₁ = 7 und e₂ = 13 sollten für den Einstieg genügen:

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

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

In unserem Bit-Array werden entsprechend die Einträge ba[0], ba[2] (zwei Mal!) und ba[6] auf eins gesetzt:

1 0 1 0 0 0 1 0

0 1 2 3 4 5 6 7

Möchten wir nun unseren Bloom-Filter abfragen, wenden wir abermals die Hash-Funktionen an und überprüfen, ob die Einträge bei allen zurückgelieferten Indices auf eins gesetzt sind, also beispielsweise wie folgt für vier und sieben:

hf₁(7) = 0        hf₁(4) = 7

hf₂(7) = 2        hf₂(4) = 6

Für die Sieben sind beide Werte (ba[0] und ba[2]) auf eins gesetzt, weshalb mit hoher Wahrscheinlichkeit davon auszugehen ist, dass eine Sieben bereits im Filter aufgenommen wurde. Obwohl das in unserem Beispiel korrekt ist, könnte sich eine solchen Konstellation auch über Hash-Kollision ergeben haben, was dann zu einem False Positive führen würden. Die Vier wird allerdings auf jeden Fall als unbekannt eingestuft, da hier ist nur der Eintrag ba[6] gesetzt ist. ba[7] steht nach wie vor auf null, so dass noch keine Vier im Filter gespeichert worden sein kann.

Einschränkungen
Leider können derart einfache Bloom-Filter zunächst einmal nur neue Daten aufnehmen, ein Zurücksetzen von Werten auf null ist nicht möglich, da dies das Ergebnis verfälschen würde.

Ferner steigt der "Füllstand" des Filters (also die Anzahl der gesetzen Einsen) immer weiter an, womit gleichzeitig das Risiko für den Erhalt eines False Positives immer weiter ansteigt. Eine offensichtliche Abhilfe für dieses Problem ist es, das Bit-Array mit einer ausreichenden Größe zu initialisieren. Eine brauchbare Orientierung für die Praxis besagt, dass die Anzahl der Hash-Funktionen ca. zwischen drei und acht liegen sollte, während die Anzahl der Bits pro erwartetem Eintrag im Bloom-Filter mindestens sechs betragen sollte, um die Rate der False Positives unter 10% zu halten. Dieser Online-Calculator kann bei der Abschätzung eine gute Hilfe sein.

Erweiterung
Eine naheliegende Erweiterung des Bloom-Filters ist die Verwendung von Zählern (also Zahlen) anstatt von Bits im Array. Das ergibt den sogenannten Counting Bloom Filter, der es ermöglicht abzuschätzen, wie oft ein Element bisher gesehen worden ist. Durch das damit möglich gemachte  Herunterzählen der Zähler im Array erlaubt er sogar das Löschen von Elementen.

Für die Suche nach einem Element in einem zählenden Bloom-Filter muss nur der kleinste Wert in den von den Hash-Funktionen ausgewählten Array-Einträgen gefunden und zurückgegeben werden. Dann wissen wir, wie oft ein Element vermutlich bisher vorgekommen ist. Durch Kollisionen kann es nach wie vor zu Überschätzungen (also False Positives) kommen. Unter der Annahme, dass nur zuvor tatsächlich hinzugefügte Elemente auch gelöscht werden, sind False Negatives (Unterschätzungen) ebenfalls weiterhin nicht möglich.

Ganz ähnlich zu dieser Erweiterung des Bloom-Filters funktioniert übrigens der sogenannte Count-Min Sketch, den ich in diesem Post beschreibe.

Ausprobieren
Um Bloom-Filter schnell und unkompliziert zu testen, bietet sich die Nutzung dieses Tutorials an, dort wird die Nutzung des Bloom-Filters aus der Guava-Library mit wenigen Worten erklärt.

Kardinalitätsabschätzung mit HyperLogLog

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/2³² (bzw. 1/2ⁿ) 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 (~ 2¹⁴) 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 (α₁₆ = 0,673, α₃₂ = 0,697, α₆₄ = 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