Chapitre 2 : MapReduce

MapReduce est un modèle de programmation pour traiter de grands jeux de données en parallèle sur un cluster de machines, en cachant au programmeur la complexité de la distribution (partitionnement, communication, tolérance aux pannes). C’est le socle du big data (Hadoop, Spark).

Objectifs

À la fin de ce chapitre, vous devez pouvoir :

  • Décrire les trois temps de MapReduce : Map → regroupement par clé → Reduce

  • Modéliser un problème en mappers et reducers

  • Connaître des patrons classiques (word count, matrice-vecteur, opérations relationnelles)

1. Le modèle

Les données sont vues comme des paires (clé, valeur). Le calcul se fait en trois temps :

  1. Map : chaque mapper traite un fragment des données en entrée et émet des paires intermédiaires (clé, valeur).

  2. Regroupement par clé (shuffle & sort) : le système regroupe toutes les valeurs partageant la même clé : (clé, [valeurs]). (Pris en charge automatiquement.)

  3. Reduce : chaque reducer reçoit une clé et la liste de ses valeurs, et émet le résultat agrégé.

\[\text{map}: (k_1, v_1) \rightarrow \text{list}(k_2, v_2) \qquad \text{reduce}: (k_2, \text{list}(v_2)) \rightarrow \text{list}(v_3)\]

2. Exemple canonique : word count

Compter les occurrences de chaque mot dans une énorme collection de documents.

def map(doc_id, texte):
    for mot in texte.split():
        emit(mot, 1)                 # (mot, 1)

def reduce(mot, comptes):            # comptes = [1, 1, 1, ...]
    emit(mot, sum(comptes))          # (mot, total)

Déroulé sur deux documents d1="le chat le" et d2="le chien" :

  • Map(d1) → (le,1) (chat,1) (le,1) ; Map(d2) → (le,1) (chien,1)

  • Regroupement → (le,[1,1,1]) (chat,[1]) (chien,[1])

  • Reduce → (le,3) (chat,1) (chien,1)

Tip

Un combiner (mini-reduce local côté mapper) réduit le volume transféré : Map(d1) émettrait directement (le,2)(chat,1). Possible quand l’agrégation est associative et commutative (somme, max…).

3. Produit matrice-vecteur

Calculer \(x_i = \sum_j m_{ij} v_j\) (utile pour PageRank, chap8).

  • Map : pour chaque élément non nul \(m_{ij}\), émettre (i, m_ij * v_j) (le vecteur v est diffusé à tous les mappers).

  • Reduce : pour chaque ligne i, sommer les valeurs reçues → (i, x_i).

Si v ne tient pas en mémoire, on découpe M et v en bandes.

4. Opérations relationnelles

MapReduce exprime aussi les opérations de l’algèbre relationnelle :

Opération

Idée MapReduce

Sélection σ

Map émet les tuples satisfaisant la condition ; pas de reduce

Projection π

Map émet les attributs gardés ; reduce déduplique

Jointure R ⋈ S sur a

Map émet (a, (R, reste)) et (a, (S, reste)) ; reduce combine les tuples R×S de même clé a

Group-by / agrégation

Map émet (clé_de_groupe, valeur) ; reduce agrège (somme, count…)

5. Exécution et tolérance aux pannes

Le framework gère : le découpage des entrées, l’ordonnancement des tâches sur les nœuds, le shuffle & sort, et la reprise sur panne (une tâche échouée est ré-exécutée ailleurs, car map/reduce sont des fonctions sans état).

Écosystème : Hadoop (HDFS + MapReduce) puis Spark (calcul en mémoire, RDD/DataFrame, bien plus rapide pour les algorithmes itératifs comme K-means ou PageRank).

Exercices

Exercice 1 — Map/Reduce d’une moyenne

On a des relevés (ville, température). Écrivez les fonctions map et reduce qui calculent la température moyenne par ville. Attention au piège du combiner.

▶ Voir la correction

map(_, (ville, temp)) → emit(ville, (temp, 1)) puis reduce(ville, liste) → emit(ville, somme(temps)/somme(comptes)).

Piège : la moyenne n’est pas associative ; un combiner naïf qui ferait la moyenne des moyennes serait faux. Il faut transporter des paires (somme, compte) et n’effectuer la division qu’au reduce final.

Exercice 2 — Jointure

Soit Ventes(produit, montant) et Produits(produit, catégorie) réparties sur plusieurs serveurs. Décrivez la jointure en MapReduce pour obtenir le montant total par catégorie.

▶ Voir la correction

Job 1 (jointure) : map émet (produit, ("V", montant)) et (produit, ("P", catégorie)) ; le reduce, pour chaque produit, associe la catégorie à chaque montant → (catégorie, montant). Job 2 (agrégation) : map relaye (catégorie, montant) ; reduce somme par catégorie. (On peut aussi fusionner en chaînant les deux étapes.)