Veröffentlicht am

MapReduce – Funktionales Programmieren in verteilten Systemen zur Big-Data Analyse

MapReduce Funktionale Programmierung

Funktionale Programmierung hat einen enormen Auftrieb erfahren. Der Grund: Datenanalyse auf verteilten Filesystemen, wie HDFS, basiert auf funktionaler Programmierung. Erst damit wurde Big-Data-Analyse überhaupt möglich.

Was macht funktionale Programmierung aus? Hier ein ganz einfaches Beispiel in Python.

Wer will, kann gleich abtippen im Online-Playground.

Die Kernidee: In der Parameterliste einer Funktion darf eine Funktion stehen.

Funktion in der Programmierung

Zur Erinnerung die Eigenschaften einer Funktion:

  • sie hat eine Bezeichnung
  • sie nimmt Parameter entgegen – wobei die Parameterliste leer sein kann, oder beliebig viele Elemente beliebiger Datentypen enthalten kann
  • und die Funktion gibt immer genau einen Wert zurück.

Die letzte Eigenschaft unterscheidet die Funktion von einer Prozedur in der prozeduralen Programmierung und von einer Methode in der objektorientierten Programmierung – diese brauchen nicht unbedingt einen Wert zurückzugeben.

Wir stehen also vor zwei Herausforderungen:

  • Wie komme ich zu einer Funktion, wo es noch keine gibt?
  • Was passiert mit der Funktion, die wir als Parameter übergeben?

Beispiel einer Funktion

Python ist eine flexible Sprache – mit vielen Funktionen, aber auch mit objektorientierten Elementen. Und so sind viele praktischen Features als Methode eines Objekts implementiert und andere wiederum als Funktion. Den Unterschied merken wir beim Aufruf der bei einer Funktion anders erfolgt als bei einer Methode.

Das Beispiel zeigt es: Wir zählen die Wörter in einem String.

Dazu zerhacken wir zuerst den String in einzelne Wörter.

Die wunderbare Methode split() erfüllt die Aufgabe:

text = 'Hello World'
text.split()

Ausgabe ist die Liste. Die Elemente einer Liste werden in Python ja von eckigen Klammern umschlossen.

['Hello', 'World']

Python ist ja interpretiert und nicht typsicher. Der Interpreter ist Weltmeister im Ausknobeln des passenden Datentyps. Das macht den Code schlank und erlaubt es auch, in einer Shell oder eben im Online Playground, den Code unmittelbar ausführen zu lassen.

Wollen wir jetzt zählen, wie viele Wörter unser Text hat, dann hilft die Funktion len().

Das geht so:

len(text.split())

Ausgabe ist 2.

Die Funktion len() wird also auf die Liste angewendet, die durch Aufruf der Methode split() auf dem String-Objekt text resultiert.

Diese Code-Zeile ist noch nicht geeignet für die funktionale Programmierung. Wir müssen die Bezeichnung der Variablen text noch loswerden, bezeichnet sie doch das Objekt, von dem die Methode split() abhängt. Bei der funktionalen Programmierung kommen wir damit nicht weitern, diese erlaubt nur Funktionen.

Lambdas helfen

splitcount = lambda x: len(x.split())

So einfach definiert man in Python einen Lambda-Ausdruck.

Der Aufruf sieht so aus und kann unabhängig vom Objekt text für alle möglichen Strings erfolgen.

splitcount(text)

Ergebnis ist 2.

Jetzt sind wir bereit für funktionale Programmierung. Wir haben eine Funktion splitcount, die das gewünschte Verhalten aufweist: Wir haben eine Funktion, die wir auf beliebige Strings anwenden können.

Zur Vorbereitung: Wir wollen wiederum Wörter zählen, doch diesmal die Wörter mehrer Strings, die in einer Liste zusammengefasst sind.

textliste = ['Fischers Fritz', 'fischt frische Fische']

Python macht es uns einfach, die eckigen Klammern umschließen die Elemente der Liste – in diesem Beispiel sind es zwei Strings.

Map Funktion

Und jetzt – Magie:

map(splitcount, textliste)

Die Python-Funktion map erwartet als ersten Parameter eine Funktion – zu dem Zweck haben wir ja splitcount vorbereitet.

Als zweiten Parameter erwartet sie eine Collection, also beispielsweise eine Liste.

Und map wendet jetzt die Funktion auf jedes Listenelement an.

Ergebnis ist die folgende Liste – sie enthält die Anzahl der Wörter der beiden Strings in der Liste textliste:

[2, 3]

Bemerkung am Rande für alle, die abtippen: das Ergebnis wird erzielt mit list(map(splitcount, textliste)) – ohne Cast auf eine Liste erhalten wir nur ein Iterable.

Reduce Funktion

Wir können auch das Gesamtergebnis ermitteln und die Wörter insgesamt zählen.

Dazu benötigen wir eine Funktion, die zwei Elemente zusammenzählt.

Nichts leichter als das:

addiere = lambda x, y: x + y

Das Lambda erledigt den Job. Wir kontrollieren

addiere(1, 2)

Das Ergebnis ist 3.

Und jetzt wieder ein Trick aus der funktionalen Programmierung. Es versteckt sich in der Python3-Library functools, die wir zuerst importieren

import functools as f

Und jetzt können wir reduce anwenden. Diese Funktion erwartet als ersten Parameter eine Funktion, die zwei Parameter nimmt. Dazu haben wir den Lambda-Ausdruck addiere vorbereitet.

Der zweite Parameter von reduce ist eine Collection – also das Ergebnis von map(splitcount(texte)).

f.reduce(addiere, map(splitcount, textliste))

Ergebnis ist 5.

Das MapReduce Programmierkonzept ist Kernstück der Datenanalyse auf verteilten Systemen.

MapReduce

MapReduce ist ein Programmierkonzept, das bei verteiltem Rechnen zum Zuge kommt. Es bedient sich des funktionalen Programmierparadigmas.

Das MapReduce-Programm im Bild zählt Wörter im Text. Dazu zerlegt der Split-Step den Text in Blöcke. Der Map-Schritt wird für jeden Block gleichzeitig ausgeführt und filtert Hinblick auf die Programmlogik die Input-Daten. Hier wird pro Wort ein Schlüssel-Wert-Paar ausgegeben. Der Wert ist 1, was sich aus dem Ziel der Analyse ergibt.

Konzeptionelle Darstellung von MapReduce
Map Reduce - konzeptionell dargestellt. Das Framework stellt den gesamten Workflow sicher. Entwickler entwerfen und codieren eine Abfolge von Map und Reduce-Schritten. Die Darstellung zeigt, wie Wörter in einem Text gezählt werden.

Sind alle Map-Schritte beendet, dann wird der Shuffle/Sort-Schritt ausgeführt. Sortiert sammelt die Zwischenergebnisse der Map-Steps zusammen und sortiert sie nach  Schlüssel.

Danach werden neue Blöcke gebildet und zwar ein Block pro Schlüssel-Wert. Die Reducer-Logik kann für alle Blöcke wiederum zeitgleich erfolgen.

Im Bild werden die 1en addiert und damit die Wörter gezählt.

Danach wird das das Endergebnis zusammengestellt und ans aufrufende Programm zurückgegeben.

Google hat dieses MapReduce-Framework für verteilte Systeme patentieren lassen.

SQL und MapReduce

SQL wird uns als deklarative Abfragesprache noch lange erhalten bleiben. SQL ist hervorragend geeignet für die Datenanalyse – alle Informatikerinnen und Informatiker kennen SQL.

Bei der Datenanalyse mit SQL stehen Aggregatsfunktionen im Mittelpunkt. Hier ein Beispiel:

ID Kunde Land Umsatz
1 Meyer CH 20
2 Müller DE 10
3 Muster CH 40
4 Berger DE 50
5 Huber AT 60

Wir analysieren die Umsatztabelle und wollen den Umsatz pro Land ermitteln:

select land, sum(umsatz) from umsatztabelle group by land

Diese Abfrage können wir ein ein MapReduce-Programm umwandeln.

Die Daten in Blöcke aufspalten – der erste Schritt – kommt in einem verteilten Filesystem wie HDFS gratis. Die Daten liegen dort schon in Blöcke aufgespalten vor.

Map für die SQL-Analyse

Input für den Map-Schritt sind einzelne Zeilen – das Framework ist entsprechend gebaut.

Pro Zeile berücksichtigen wir für unser Beispiel nur das Land und den Umsatz. Die anderen Felder tragen ja nicht bei zur Beantwortung der Analyseaufgabe.

Der Map-Schritt gibt also pro Zeile ein Schlüßel-Wert-Paar zurück:

Land -> Umsatz

Auch der Shuffle/Sort-Schritt braucht uns nicht zu kümmern. Das Framework über nimmt den Schritt und sammelt alle Schlüssel-Wert-Paare die alle Mapper errechnet haben, zusammen, sortiert sie, nach Schlüssel, bildet Pakete und zwar eines pro Schlüsselwert.

AT 60

CH 40
CH 20

DE 10
DE 50

Reduce für die SQL-Analyse

Das Framework schickt jedes Paket so gebildete Paket zu einem Reducer. Gleich wie den Mapper, entwerfen wir auch den Reducer, so dass das Analyseziel erreicht wird.

In unserem Fall zählen wir alle Werte zusammen und geben je ein zur Aufgabenstellung passendes Schlüssel-Wert-Paar zurück.

AT 60
CH 60
DE 60

Das Framework sammelt diese Ergebnisse und stellt sie zu einem Endergebnis zusammen.

Für komplexere Analysen, beispielsweise mit Joins, werden wir mehrere Mapper und je nachdem auch mehrere Reducer programmieren und zu einer geeigneten Abfolge zusammenstellen.

MapReduce aus SQL generieren

Kein Datenanalyst wird produktiv sein, wenn er zuerst seine Logik in MapReduce übersetzen muss. Doch das ist auch gar nicht nötig.

Moderne Big-Data Tools übernehmen diese Übersetzung. Als Analysten überlegen wir SQL und das Framework generiert daraus die passenden Analyse-Jobs und führt sie über dem verteilten System aus.

Fazit

Funktionale Programmierung einerseits und das MapReduce-Framework andrerseits legten das Fundament für die moderne Datenanalyse in verteilten Filesystemen. Die Entwicklungen sind noch nicht zu Ende und laufen in Richtung Echtzeitanalyse und praktische Tools zur Bedienung dieser hochkomplexen Systeme.

  • Data Engineering ist ja nicht Selbstzweck. Vielmehr dient es dazu, aus Daten Nutzen zu ziehen. Künstliche Intelligenz wurde möglich, dank sorgfältigem Data Engineering.

  • LLM-Tipps & Fachglossar

    Abonniere meinen Newsletter, erhalte regelmäßig Tipps und Tricks über den produktiven Einsatz von LLMs und ich schenke dir mein umfangreiches Fachglossar Von AI-Engineering bis Zero-Shot

  • Chatbot als Lernassistent
  • Prompt Engineering Personas und Wiederholungen
  • AI-Engineering-Fachglossar
  • EBook Tutorial: Cluster aus virtuellen Maschinen
  • Ebook: Apache ZooKeeper
  • Ebook: Realtime Streaming Pipelines
  • LSM-Trees: Log Structured Merge Trees
  • Aufbau einer Enterprise Search
  • Zeit Stream Analytics
  • B-Tree-Index in Datenbanken
  • Ordering Guarantee in Apache Kafka
  • CAP Theorem
  • MapReduce Funktionale Programmierung
  • Konzepte des HDFS
  • Optimistisches Concurrency Control