MapReduce et le traitement de données en parallèle

MapReduce et ses successeurs sont des modèles de programmation et des frameworks qui traitent de très grands ensembles de données en parallèle sur des clusters de machines standards, gérant automatiquement la distribution, l'ordonnancement et la tolérance aux pannes.

Definition

MapReduce est un modèle de programmation dans lequel un calcul est exprimé comme une fonction de mappage (map) qui émet des paires clé-valeur et une fonction de réduction (reduce) qui agrège les valeurs pour chaque clé, exécuté en parallèle sur des données partitionnées à travers un cluster avec une distribution et une tolérance aux pannes gérées par le framework.

Scope

Ce sujet couvre le modèle MapReduce — exprimant le calcul comme des fonctions de mappage (map) et de réduction (reduce) sur des paires clé-valeur, avec un brassage (shuffle) automatique entre les deux — ainsi que les mécanismes d'exécution associés de partitionnement, d'ordonnancement et de tolérance aux pannes via la réexécution. Il aborde l'évolution vers les moteurs de flux de données (dataflow) généraux et en mémoire (tels que le modèle de jeu de données distribué résilient) et les systèmes de fichiers distribués qui les sous-tendent. Il exclut les modèles de stockage NoSQL et la théorie de la cohérence, qui sont des sujets connexes.

Core questions

• Comment les phases de mappage (map), de brassage (shuffle) et de réduction (reduce) parallélisent-elles un calcul ?
• Comment le framework gère-t-il le partitionnement des données, l'ordonnancement et les tâches lentes (stragglers) ?
• Comment la tolérance aux pannes est-elle obtenue par la réexécution des tâches échouées ?
• Pourquoi les moteurs de flux de données généraux et en mémoire ont-ils succédé à MapReduce pour de nombreuses charges de travail ?
• Quel rôle les systèmes de fichiers distribués jouent-ils dans le traitement de données en parallèle ?

Key concepts

• fonctions de mappage (map) et de réduction (reduce)
• phase de brassage (shuffle) et de tri
• partitionnement des données
• ordonnancement des tâches et tâches lentes (stragglers)
• tolérance aux pannes par réexécution
• système de fichiers distribué
• graphes de flux de données (dataflow)
• jeux de données distribués résilients

Key theories

Le modèle MapReduce

Les programmeurs écrivent une fonction de mappage (map) qui transforme les enregistrements d'entrée en paires clé-valeur intermédiaires et une fonction de réduction (reduce) qui combine toutes les valeurs pour une clé ; le framework gère l'exécution parallèle, le brassage (shuffle) qui regroupe les valeurs par clé, et la récupération après les pannes.

Tolérance aux pannes par réexécution

Étant donné que les tâches sont des fonctions déterministes sur des entrées partitionnées, le framework tolère les pannes de machines simplement en réexécutant les tâches de mappage (map) ou de réduction (reduce) échouées, et il atténue les nœuds lents en lançant des copies de secours (spéculatives) des tâches lentes (straggling tasks).

Moteurs de flux de données en mémoire

Les systèmes ultérieurs ont généralisé MapReduce à des graphes de flux de données (dataflow) arbitraires et ont conservé les données intermédiaires en mémoire ; l'abstraction de jeu de données distribué résilient récupère les partitions perdues en les recalculant à partir de la lignée, accélérant considérablement les charges de travail itératives et interactives.

Clinical relevance

Le traitement de données en parallèle a rendu le calcul à l'échelle des clusters accessible aux programmeurs ordinaires : MapReduce et ses successeurs traitent des journaux, construisent des index de recherche, entraînent des modèles et exécutent des analyses sur des pétaoctets de données, et ils constituent des outils fondamentaux de l'ingénierie des données et de la science des données à grande échelle.

History

Google a introduit MapReduce (2004) au-dessus du Google File System (2003) pour indexer le web sur des clusters de machines standards, et le projet open-source Hadoop a réimplémenté les deux, popularisant ainsi le modèle. Au début des années 2010, les moteurs de flux de données en mémoire construits sur l'abstraction de jeu de données distribué résilient (2012) ont supplanté MapReduce pour les analyses itératives et interactives tout en conservant ses principes de tolérance aux pannes.

Key figures

• Jeffrey Dean
• Sanjay Ghemawat
• Matei Zaharia

Seminal works

• dean2008
• ghemawat2003
• zaharia2012

Frequently asked questions

Pourquoi MapReduce a-t-il été si influent malgré sa simplicité ?

Sa puissance résidait dans ce qu'il masquait. En restreignant le calcul aux fonctions de mappage (map) et de réduction (reduce), le framework pouvait automatiquement partitionner les données, ordonnancer le travail sur des milliers de machines, récupérer après les pannes en réexécutant les tâches, et équilibrer la charge — permettant aux programmeurs de traiter d'énormes ensembles de données sans écrire de code de systèmes distribués.

Pourquoi les moteurs plus récents ont-ils remplacé MapReduce pour de nombreuses tâches ?

Le MapReduce classique écrit les résultats intermédiaires sur disque entre chaque étape, ce qui est lent pour les tâches multi-étapes et itératives telles que l'apprentissage automatique. Les moteurs de flux de données en mémoire conservent les données en mémoire entre les étapes et expriment des graphes de calcul plus riches, offrant des gains de vitesse importants tout en conservant la tolérance aux pannes basée sur la lignée, c'est pourquoi ils sont devenus préférés pour de nombreuses charges de travail analytiques.