Open Source im professionellen Einsatz
Linux-Magazin Online Artikel/
(c) Amy Harris, 123rf.com

(c) Amy Harris, 123rf.com

Funktionale Programmierung (3): Das MapReduce-Framework

"Hallo Worker! Ein Petabyte Daten bitte."

17.11.2009

Schnell, robust, einfach zu nutzen, skalierbar, weit einsetzbar und inklusive Monitoring: Das verspricht MapReduce, ein Framework von Google zur nebenläufigen Berechnung sehr großer Datenmengen auf Rechnerclustern. Ein mutiges Versprechen. Dieser Artikel wird zeigen, ob MapReduce es einlöst.

916

Die Grundidee von MapReduce ist schnell skizziert: Man verwende die funktionalen Bausteine Map und Reduce (siehe Teil 1 dieser Artikelreihe) und bilde um diese herum ein Framework mit folgenden Eigenschaften:

  • automatische Parallelisierung, Koordinierung und Verteilung von Berechnungen (Jobs)
  • Fehlertoleranz gegenüber Hardware- und Softwareausfällen
  • automatische Lastverteilung
  • Optimierung von Netzwerk und Datentransfer
  • Überblick durch Status- und Monitoringnachrichten

So entsteht eine Anwendung, die für viele Einsatzgebiete geeignet ist. Dies zeigen zum Einen die zahlreichen Implementierungen von MapReduce, die seit 2003 entstanden sind, und zum Anderen die vielen Anwendungsbereiche, in denen MapReduce zum Einsatz kommt:

  • Indizierung großer Datenmengen für die Suchaufbereitung
  • Maschinelles Lernen zur künstlichen Erzeugung von Wissen aus Erfahrung
  • Verteiltes Suchen von Pattern, Sortieren von Daten
  • Auswertung von großen Logdateien
  • Kategorisierung von Daten zur Nachrichtenaufbereitung
  • Datenaufbereitung für häufige Anfragen
  • Erzeugung von Graph über die Aufrufhäufigkeit, über die Verlinkung von Webseiten
  • Extrahieren von Daten aus Webseiten um neue Einsichten zu erlangen

Gemeinsam ist diesen Anwendungen, dass sie mit sehr großen Datenmengen arbeiten müssen - typischerweise im Tera- bis Petabyte-Bereich - und somit von einem einzelnen Rechner nicht in vertretbarer Zeit gelöst werden können.

Zu verdanken ist der weite Einsatzbereich von MapReduce insbesondere der Trennung von Framework- und Anwendungslogik. Die komplexen Details der Berechnung bleiben im Framework verborgen, der Anwender braucht lediglich die Funktionen Map und Reduce für seine Zwecke zu definieren.

Angesichts der Mächtigkeit dieses Konzepts stört es da wenig, dass die Map- und Reduce-Funktionen im MapReduce Framework sich von ihren funktionalen Namensgebern deutlich unterscheiden. Die Unterschiede beschreibt beispielsweise der Microsoft-Entwickler Ralf Lämmel in seinem Aufsatz "Google's MapReduce Programming Model -- Revisited (PDF)". Ein natürlicher Zugang zu dem MapReduce Protokoll ist es, den Datenfluss während der Berechnung genauer zu betrachten (Abbildung 1).

Protokoll

Das Framework verteilt die Eingabedatei auf mehrere Map-Prozesse. Diese Map-Prozesse berechnen in der Map-Phase parallel die Zwischenergebnisse. Ist diese Phase vorbei, beginnt die Reduce-Phase, in der die Reduce-Prozesse mit den passenden Zwischenergebnissen gefüttert werden und jeder dieser Prozesse seine Ergebnisdatei im Dateisystem speichert. Ist die Reduce-Phase absolviert, ist auch die MapReduce-Berechnung abgeschlossen.

Abbildung 1: Datenfluss MapReduce

Der Anwender hingegen definiert seine Anwendungslogik in Form der Map- und Reduce-Funktionen, die in den entsprechenden Phasen angewandt werden. Die Map Funktion (Mapper) nimmt ein Paar "(Schlüssel,Wert)" an und erzeugt aus diesem eine Liste von Paaren in der Form "(Schlüssel,Wert)". Diese dienen als Eingabe für die Reduce-Funktion (Reducer), die alle Werte zu einem Schlüssel als Liste erhält und aus diesen Werten das Ergebnis berechnet und es in das verteilte Dateisystem schreibt.

Wie sehen die konkreten Mapper und Reducer aus? Ein klassische Anwendung für MapReduce besteht darin, die Worthäufigkeit in einer Eingabedatei zu bestimmen. Dazu erhält der Mapper die Liste aller Paare im Format"(Zeilennummer,Zeileninhalt)" und erzeugt für jedes Wort der Zeile ein Paar in der Form "(Wort,1)". Die Reduce-Funktion erhält alle Werte zu dem Schlüsselwort in der Form "(Wort,[1,..,1])" als Eingabe. Diese addiert in der Reduce-Phase die Werte zusammen und schreibt sie in das Dateisystem. Als Ergebnis des MapReduce-Vorgangs steht die Liste "[(Wort,Häufigkeit des Wortes)]" aller Wörter der Eingabedatei zu Verfügung.

Die folgende Tabelle fasst alle an der Datenverarbeitung beteiligten Komponenten zusammen:

Die Akteure beim MapReduce Datenfluss

Akteur

Aufgabe

Eingabe-Leser

teilt die Eingabe in große Blöcke auf und weist sie den Mappern zu
transformiert die Blöcke in "(Schlüssel,Wert)"-Paare für den Mapper

Mapper Funktion

nimmt die Liste von "(Schlüssel,Wert)"-Paaren an und erzeugt zu jedem Paar eine neue Listen von neuen "(Schlüssel,Wert)"-Paaren, die auch leer sein kann

Verteilerfunktion

die Ausgabe aller Maps wird den entsprechenden Reducern zur Weiterverarbeitung zugewiesen
typischerweise wird der Hashwert des Keys modulo der Anzahl der Reducer verwendet

Vergleichsfunktion

sortiert die Werte der Mapper-Funktion entsprechend der Schlüssel
dies ist notwendig, da der Reducer in der Regel die Werte mehrerer Schlüssel bearbeitet

Reducer-Funktion

erzeugt zu jedem Schlüssel und dessen Wert als Ergebnis eine Ausgabeliste, die auch leer sein

Ausgabe-Schreiber

speichert das Ergebnis in einer Datei ab

Architektur

Nun ist es Zeit, auf die Architektur des Frameworks einzugehen. Abbildung 2 zeigt die Einzelschritte der MapReduce-Berechnung.

Die MapReduce-Architektur

  1. Das MapReduce Framework teilt die Eingabe in m Teile auf, startet den Master und die Worker Prozesse auf dem Rechencluster.
  2. Der Master weist die m Map-Aufgaben und r Reduce-Aufgaben den entsprechenden Rechnern zu.
  3. Der Map-Prozess liest die Eingabedaten als Paare in der Form "(Schlüssel,Wert)" ein, verarbeitet sie mit der Map- Funktion und schreibt die Zwischenergebnisse in den Speicher.
  4. Der Map-Prozess schreibt die Zwischenergebnisse periodisch in r Dateien auf seine Festplatte und teilt die Namen der Dateien dem Master mit.
  5. Der Reduce-Prozess bekommt vom Master die Adressen der Zwischenergebnisse mitgeteilt, liest alle für ihn bestimmten "(Schlüssel,Wert)"-Paare ein und sortiert die "(Schlüssel,Wert)"-Paare nach deren Schlüsseln.
  6. Der Reduce-Prozess iteriert über die "(Schlüssel,Liste von Werten)"-Paare für jeden Schlüssel, übergibt die "(Schlüssel,Liste von Werten)"-Paare an die Reduce-Funktion, die die Liste von Werten zu einem Ausgabewert akkumuliert.
  7. Das MapReduce-Framework wartet, bis alle Map- und Reduce Prozesse durchlaufen sind und übergibt die Kontrolle wieder an die Applikation.

Was für das Gesamtverständnis nun noch fehlt, ist, sich einzelne Komponenten der Architektur genauer anzuschauen.

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Hadoop

    Datenmengen im Petabyte-Bereich verarbeiten Unternehmen wie Google und Facebook nach dem Map-Reduce-Verfahren. Für bestimmte Analysen dient es als kraftvolle Alternative zu SQL-Datenbanken, und mit Apache Hadoop existiert eine Open-Source-Implementierung.

  • Online-Artikel: Googles MapReduce-Framework und Hadoop

    Der kostenlose Online-Artikel stellt das von Google entwickelte und von vielen Branchengrößen eingesetzte Framework MapReduce vor. Inspiriert von funktionaler Programmierung und mit Hilfe tausender Rechnerknoten kann es enorme Datenmengen verarbeiten.

  • Uni Passau forscht zu MapReduce

    Die Deutsche Forschungsgemeinschaft (DFG) hat der Universität Passau ein Forschungsvorhaben zu Googles Rechen-Framework MapReduce bewilligt.

  • Apache Hadoop 2.0 Alpha

    Mit der Ankündigung der Alpha-Version von Apache Hadoop 2.0 sieht sich das Entwicklerteam für das Framework für den Clusterbetrieb einen wichtigen Schritt weiter.

  • Bücher

    Das eine Buch trägt bewährte Lösungen für das Framework Map-Reduce zusammen, das zweite versammelt Wissenswertes über Erlang. Für beide Werke muss der Leser der englischen Sprache mächtig sein.

comments powered by Disqus

Ausgabe 08/2016

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.