Wie in Teil 1 der Artikelserie beschrieben, basiert Hadoop im Grundsatz und ursprünglich auf zwei Konzepten von Google:
- einem distribuierten File-System (Hadoop Distributed File System = HDFS)
- einem Algorithmus zur Analyse dieser verteilten Daten
Bevor es um das File-System geht, möchte ich zunächst versuchen, MapReduce zu erklären. Hierfür möchte ich gerne zunächst ein Beispiel aus dem täglichen Leben nehmen und anschließend in Teil 3 der Reihe einen technischen Überblick geben.
Bei jeder Wahl in Deutschland kann theoretisch jeder zu einem Wahlhelfer werden und die Wahlberechtigungen kontrollieren oder die Stimmzettel auszählen. Am Ende eines erfolgreichen Wahltages möchten die Parteien unbedingt und schnell wissen, wer es denn in das Parlament, den Land- oder Bundestag geschafft hat und wieviele Prozentpunkte jede Partei im Vergleich zum Vorjahr gewonnen oder verloren hat.
Das Ergebnis einer Wahl wird üblicherweise als Torten- oder Balkendiagramm dargestellt und verwendet als Datenfundament eine Liste aus Key-Value-Paaren:
Parteiname : Wahlergebnis (in Prozent)
Wie kommt aber die einzelne Stimme in den vielen verschiedenen Bundesländern, Wahlkreisen und Gemeinden zu einer zentralen Aufsummierung der Wahlergebnisse.
Betrachten wir einmal das kleine Wahlbüro um die Ecke und nehmen mal an, dass der ausgewählte Wahlkreis aus 100 Personen und 4 Parteien besteht. Es gibt zudem 4 Wahlhelfer, die bei der Stimmzählung helfen dürfen. Nachdem alle 100 Wahlberechtigte Ihren Stimmzettel abgegeben haben, beginnt die Auswertung. Hierzu wird der große Stapel aus der Wahlurne (bestehend aus 100 Stimmzetteln – alle gültig) an die 4 Wahlhelfer verteilt: jeder erhält demnach 25 Stimmzettel, die er auswerten muss.
Halten wir fest, dass zu diesem Zeitpunkt niemand alle Stimmzettel (Daten) besitzt und alle Wahlhelfer dieselbe Zählung (Rechenoperation) für einen Teilbereich der Gesamtanzahl aller Stimmzettel durchführen. Am Ende der Zählung verfügt jeder der 4 Wahlhelfer über eine Liste von den 4 Parteien und den dazugehörigen aufsummierten Stimmenanzahl. Jeder hat also ein Key-Value-Paar gebildet aus Parteiname und Anzahl der Stimmen.
Dieser Vorgang spielt sich in einem der vielen Wahlbüros parallel ab. In MapReduce wird dieser Vorgang als Map-Phase bezeichnet, d.h. jeder (Cluster-Knoten) führt parallel dieselbe Rechenoperation auf einem Teilbestand der Daten aus.
Die Reduce-Phase besteht in unserem Fall einfach darin, dass jemand die Teilergebnisse der Map-Phase (Teilauszählung) zusammenfasst und ebenfalls als Key-Value-Paar darstellt. Für jedes regionale Wahlbüro gibt es demnach ein Ergebnis, dass aus einer Liste der 4 Parteien und der dazugehörigen Stimmenanzahl besteht.
Gibt nun jedes Wahlbüro diese Daten an die nächst höhere Instanz weiter, können auch dort die Ergebnisse zusammengefast (reduziert) werden, so dass in letzter Instanz auf höchster Ebene das vormals angesprochene Endergebnis als Key-Value-Paar vorliegt.
Halten wir also fest:
- Gerechnet wird immer dort, wo die Daten auch gerade sind. (Auf dem Schreibtisch des Wahlhelfers)
- Es wird parallel gerechnet (Es gibt sehr viele Wahlbüros)
- Die Ergebnisse werden von wenigen Instanzen zusammengefasst
Das beschriebene Konstrukt kann auch auf Daten übertragen werden, wobei Key und Value natürlich vom Programmierer definiert werden können. Als eines der typischen Beispiele wird gerne “Wordcount” benutzt, in dem es darum geht die Anzahl (Value) eines bestimmten Wortes (Key) in einem Text zu bestimmen. Es gibt jedoch noch diverse andere Berechnungen, die mit MapReduce durchgeführt werden können.
Dazu mehr in Teil 3 …