MapReduce und datenparallele Verarbeitung

MapReduce und seine Nachfolger sind Programmiermodelle und Frameworks, die sehr große Datensätze parallel über Cluster von Standardrechnern verarbeiten und dabei Verteilung, Zeitplanung und Fehlertoleranz automatisch handhaben.

Definition

MapReduce ist ein Programmiermodell, bei dem eine Berechnung als eine Map-Funktion, die Schlüssel-Wert-Paare ausgibt, und eine Reduce-Funktion, die die Werte für jeden Schlüssel aggregiert, ausgedrückt wird, ausgeführt parallel über Daten, die über einen Cluster partitioniert sind, mit vom Framework verwalteter Verteilung und Fehlertoleranz.

Scope

Dieses Thema behandelt das MapReduce-Modell – die Formulierung von Berechnungen als Map- und Reduce-Funktionen über Schlüssel-Wert-Paare mit einem automatischen Shuffle dazwischen – und die umgebende Ausführungsmaschinerie der Partitionierung, Zeitplanung und Fehlertoleranz durch erneute Ausführung. Es deckt die Entwicklung zu allgemeinen Datenfluss- und In-Memory-Engines (wie dem Modell der resilienten verteilten Datensätze) und den zugrunde liegenden verteilten Dateisystemen ab. Es schließt NoSQL-Speichermodelle und die Konsistenztheorie aus, die angrenzende Themen sind.

Core questions

• Wie parallelisieren die Map-, Shuffle- und Reduce-Phasen eine Berechnung?
• Wie handhabt das Framework Datenpartitionierung, Zeitplanung und Stragglers?
• Wie wird Fehlertoleranz durch erneute Ausführung fehlgeschlagener Aufgaben erreicht?
• Warum haben allgemeine Datenfluss- und In-Memory-Engines MapReduce für viele Workloads abgelöst?
• Welche Rolle spielen verteilte Dateisysteme bei der datenparallelen Verarbeitung?

Key concepts

• Map- und Reduce-Funktionen
• Shuffle- und Sortierphase
• Datenpartitionierung
• Aufgabenplanung und Stragglers
• Fehlertoleranz durch erneute Ausführung
• Verteiltes Dateisystem
• Datenflussgraphen
• Resiliente verteilte Datensätze

Key theories

Das MapReduce-Modell

Programmierer schreiben eine Map-Funktion, die Eingabedatensätze in Zwischen-Schlüssel-Wert-Paare umwandelt, und eine Reduce-Funktion, die alle Werte für einen Schlüssel kombiniert; das Framework übernimmt die parallele Ausführung, das Shuffle, das Werte nach Schlüssel gruppiert, und die Wiederherstellung nach Fehlern.

Fehlertoleranz durch erneute Ausführung

Da Aufgaben deterministische Funktionen über partitionierte Eingaben sind, toleriert das Framework Maschinenfehler einfach durch erneutes Ausführen fehlgeschlagener Map- oder Reduce-Aufgaben und mildert langsame Knoten ab, indem es Backup- (spekulative) Kopien von verzögernden Aufgaben startet.

In-Memory-Datenfluss-Engines

Spätere Systeme verallgemeinerten MapReduce auf beliebige Datenflussgraphen und hielten Zwischenergebnisse im Speicher; die Abstraktion resilienter verteilter Datensätze stellt verlorene Partitionen durch Neuberechnung aus der Herkunft wieder her, was iterative und interaktive Workloads erheblich beschleunigt.

Clinical relevance

Die datenparallele Verarbeitung machte die Cluster-Skalierung für gewöhnliche Programmierer zugänglich: MapReduce und seine Nachfolger verarbeiten Protokolle, erstellen Suchindizes, trainieren Modelle und führen Analysen über Petabytes durch, und sie sind grundlegende Werkzeuge des Data Engineering und der großskaligen Datenwissenschaft.

History

Google führte MapReduce (2004) auf dem Google File System (2003) ein, um das Web auf Commodity-Clustern zu indizieren, und das Open-Source-Hadoop implementierte beides neu, wodurch das Modell populär wurde. Bis Anfang der 2010er Jahre übertrafen In-Memory-Datenfluss-Engines, die auf der Abstraktion resilienter verteilter Datensätze (2012) basierten, MapReduce für iterative und interaktive Analysen, während sie dessen Fehlertoleranzkonzepte beibehielten.

Key figures

• Jeffrey Dean
• Sanjay Ghemawat
• Matei Zaharia

Seminal works

• dean2008
• ghemawat2003
• zaharia2012

Frequently asked questions

Warum war MapReduce trotz seiner Einfachheit so einflussreich?

Seine Stärke lag in dem, was es verbarg. Indem es die Berechnung auf Map- und Reduce-Funktionen beschränkte, konnte das Framework Daten automatisch partitionieren, Arbeit über Tausende von Maschinen planen, sich durch erneutes Ausführen von Aufgaben von Fehlern erholen und die Last ausgleichen – was Programmierern ermöglichte, enorme Datensätze zu verarbeiten, ohne verteilte Systemcode schreiben zu müssen.

Warum haben neuere Engines MapReduce für viele Aufgaben abgelöst?

Klassisches MapReduce schreibt Zwischenergebnisse zwischen jeder Phase auf die Festplatte, was für mehrstufige und iterative Aufgaben wie maschinelles Lernen langsam ist. In-Memory-Datenfluss-Engines halten Daten über Phasen hinweg im Speicher und drücken reichhaltigere Berechnungsdiagramme aus, was große Geschwindigkeitsvorteile bietet, während die auf Lineage basierende Fehlertoleranz beibehalten wird, sodass sie für viele analytische Workloads bevorzugt wurden.