MapReduce

Das war der Start von Big Data (Hadoop). Heute nutzt man es selten direkt (zu viel Java-Code). Man nutzt Tools wie Spark oder Hive (SQL), die im Hintergrund aber oft ähnliche Prinzipien verwenden. Das Konzept der funktionalen Programmierung (map, reduce, filter) ist aber in jeder Sprache (JS, Python) Alltag.

1. Data Locality

Der Trick von Google: "Bring den Code zu den Daten, nicht die Daten zum Code." Das Netzwerk ist der Flaschenhals. MapReduce startet das Programm auf genau dem Server, auf dem die Festplatte mit den Daten liegt. Kein Netzwerk-Traffic!

2. Stragglers (Trödler)

Ein Server ist langsam (alte Festplatte). Er hält alle auf (weil Reduce warten muss, bis alle Maps fertig sind). Lösung: Speculative Execution. Google startet die gleiche Aufgabe kurz vor Ende nochmal auf einem schnellen Server. Wer zuerst fertig ist, gewinnt.

1. Das "Shuffle and Sort" Nadelöhr und IOPS-Kill

Der verborgenste Magie- und zugleich Flaschenhalstrick des MapReduce Papiers ist die Brücke. "Map" ist peinlich parallel, "Reduce" aggregiert trivial. Doch das Zwischenstück – das Shuffling – ruiniert Netzwerke. Wenn 10.000 Mapper ihre Output-KVPairs (Wort, Zähler) ins RAM flushen, schreiben sie diese Zwischenergebnisse in lokale kreisförmige OS-Buffer der Linux-Disk, rigoros sortiert nach Hash(Key) % Reduce_Num. Anschließend ziehen sich 1000 Reducer quer über die Top-of-Rack Switches gigantische HTTP-GET Anfragen von allen 10.000 Mappern gleichzeitig herunter ("Pull-Phase"). Dieser $M \times R$ Verbindungs-Sturm überflutet Datacenter BGP-Links massivst. Wenn die Partitionierungsparameter schlecht gewählt sind (Data Skew - das Wort der liegt auf Reducer 5), empfängt Node 5 eine Lawine an Bytes, was zu exzessivem Disk-Spilling führt (die Merken-Arrays in Node 5 stürzen ab ins Paging Filesystem), was oft Laufzeiten von Stunden via OOM Kills terminiert.

2. Spekulative Ausführung (Straggler Mitigation)

Google entdeckte in verteilten $10.000$-Node Farmen ein stochastisches Gesetz: Die letzten 5% der Berechnungs-Tasks verschossen bis zu 50% der Gesamtlaufzeit. Grund waren "Straggler" – Nodes, deren Festplatten fehlerhafte Sektoren überlebten (Lese-Retries im Kernel) oder bei denen CPU-Throttling durch Thermo-Drosselung anlief. Ein MapReduce-Job ist aber ein Blockier-Damm; Phase 2 (Reduce) kann niemals starten, bis 100% der Mapper-Pakete da sind. Die Lösung im Paper: Der asynchrone Master (JobTracker) analysiert Telemetrie-Pings. Ist Task-X 40% unter dem Median, feuert der Master ohne Abbrechen prophylaktisch Duplicate-Tasks (Speculative Execution) auf freien "schnellen" Reservern-CPUs ab. Wer iterativ sein Output-File ins NFS/HDFS zuerst verifiziert (als COMMIT_FILE), gewinnt den Sprint. Der Straggler wird dann gnadenlos SIGTERM-gekillt.

3. Fault Tolerance und Lineage Resilience

Im puren MapReduce wird Hardwareausfall vorausgesetzt ("Hardware failure is the norm, not the exception"). Crasht ein Reducer bei 99%, wird er auf Replika-Node neugestartet, liest das HDFS und shuffelt den Map-Output stupide neu. Spark (RDD-Paradigma) wandelte dies ab: Spark verlor MapReduce-Diskkills und hielt Puffer im Heap-RAM Memory. Wenn in Spark Node B stirbt, greift das Framework ins Lineage Graph Directory ("Welche Matrix-Map Funktion formte dieses RDD?"). Spark rekonstruiert reaktiv nur den toten RAM-Split dynamisch aus den puren Root-HDFS-Blöcken durch "Nachrechnen" anstatt permanent alle Zwischenschritte zwanghaft nach jedem Funktions-Block wie Hadoop auf plattenbasierten Festplatten für den Katastrophenfall hart abzuspeichern.