3.1 · El paradigma MapReduce

¿Qué es MapReduce?

MapReduce es un modelo de programación para procesar conjuntos de datos masivos en un clúster de servidores, popularizado por Google (2004) e implementado en Hadoop. Su gran idea es que el programador solo escribe dos funciones —map y reduce— y el framework se encarga de todo lo difícil: paralelizar, distribuir datos, tolerar fallos y reintentar tareas.

En lugar de mover los datos hacia el programa, MapReduce mueve el cómputo hacia los datos: cada nodo procesa la porción de datos que ya tiene almacenada en su disco local (HDFS).

Las tres fases

Un job de MapReduce atraviesa tres fases:

El shuffle & sort lo hace el framework automáticamente: es la fase más costosa porque implica transferir datos por la red entre nodos.

Word count: el “Hola Mundo” de MapReduce

El ejemplo canónico es word count: contar cuántas veces aparece cada palabra en un corpus de documentos. Supongamos dos líneas de entrada:

"gato persa gato"
"perro gato"

Paso a paso:

1. Map: cada línea se divide en palabras y se emite (palabra, 1):
   • (gato,1) (persa,1) (gato,1) y (perro,1) (gato,1)
2. Shuffle & Sort: el framework agrupa por clave:
   • (gato, [1,1,1]), (persa, [1]), (perro, [1])
3. Reduce: se suman los valores de cada clave:
   • (gato, 3), (persa, 1), (perro, 1)

graph LR
subgraph Entrada
  L1["gato persa gato"]
  L2["perro gato"]
end
subgraph Map
  M1["(gato,1) (persa,1) (gato,1)"]
  M2["(perro,1) (gato,1)"]
end
subgraph Shuffle["Shuffle and Sort"]
  S1["(gato, [1,1,1])"]
  S2["(persa, [1])"]
  S3["(perro, [1])"]
end
subgraph Reduce
  R1["(gato, 3)"]
  R2["(persa, 1)"]
  R3["(perro, 1)"]
end
L1 --> M1
L2 --> M2
M1 --> S1
M1 --> S2
M2 --> S1
M2 --> S3
S1 --> R1
S2 --> R2
S3 --> R3

Combiners: reducir el tráfico de red

El shuffle es caro: cada par (palabra, 1) viaja por la red. Un combiner es una “mini-reducción” que se ejecuta localmente en cada nodo después del map y antes del shuffle.

Si un nodo emite (gato,1) cien veces, el combiner lo compacta a (gato, 100) antes de enviarlo. Así se reduce drásticamente el volumen de datos transferidos.

El combiner usa la misma función que el reduce, pero solo es válido si la operación es conmutativa y asociativa (suma, máximo, conteo). No sirve para un promedio calculado de forma ingenua: el promedio de promedios no es el promedio global.

Limitaciones de MapReduce

Aunque fue revolucionario, MapReduce tiene limitaciones importantes que motivaron a Spark:

• Todo pasa por disco: entre map y reduce, y entre jobs encadenados, los resultados intermedios se escriben a HDFS. El disco es órdenes de magnitud más lento que la memoria RAM.
• Solo batch: está diseñado para procesamiento por lotes; no sirve para consultas interactivas ni streaming en tiempo real.
• Modelo rígido: cualquier algoritmo debe expresarse como map + reduce. Algoritmos iterativos (machine learning, grafos) requieren muchos jobs encadenados, cada uno leyendo y escribiendo disco.
• Latencia alta: un job tarda decenas de segundos solo en arrancar y distribuirse.

Ejercicio: word count con map/reduce simulado

texto = [
  "gato persa gato",
  "perro gato",
  "persa perro gato",
]

# Fase MAP: emite pares (palabra, 1)
def mapper(linea):
  pares = []
  for palabra in linea.split():
      pares.append((palabra, 1))
  return pares

# Fase SHUFFLE & SORT: agrupa valores por clave
def shuffle(todos_los_pares):
  agrupado = {}
  for clave, valor in todos_los_pares:
      agrupado.setdefault(clave, []).append(valor)
  return agrupado

# Fase REDUCE: suma los valores de cada clave
def reducer(clave, valores):
  return (clave, sum(valores))

# Ejecución del job
pares_intermedios = []
for linea in texto:
  pares_intermedios.extend(mapper(linea))

agrupado = shuffle(pares_intermedios)

for clave in sorted(agrupado):
  palabra, total = reducer(clave, agrupado[clave])
  print(f"{palabra}: {total}")

Comprueba lo aprendido

Resumen

• MapReduce = dos funciones del programador (map y reduce) + framework que paraleliza, distribuye y tolera fallos.
• El shuffle & sort agrupa los valores por clave entre ambas fases; es la parte más costosa por el tráfico de red.
• Word count es el ejemplo canónico: map emite (palabra, 1), reduce suma.
• Los combiners hacen pre-agregación local para aliviar la red; solo valen para operaciones asociativas y conmutativas.
• Limitaciones: resultados intermedios en disco, solo batch, latencia alta → abrió el camino a Spark.

📚 Lecturas y fuentes