MapReduce

MapReduce es una técnica popularizada por Google (aquí el documento original) para el tratamiento de grandes cantidades de información en un tiempo razonable.

El nombre proviene de las funciones propias de la programación funcional map y reduce.

En python estas dos funciones se pueden combinar de la siguiente forma para contar el número de números impares de una lista:

reduce(lambda n,m: n+m, map(lambda n: n%2, [1,2,3,4,5,6,7,8,9]))

Primero, map aplica la función n%2 a toda la lista original y cambiandola de dominio (de números naturales a [0,1]), después reduce suma la nueva lista obteniendo el número de elementos impares.

¿Qué ventaja tiene esta manera de hacerlo el recuento a la tradicional?
Lo primero que se nos hubiera ocurrido tradicionalmente sería recorrer la lista en aumentando un contador si un número es impar.
Con MapReduce hacemos un procedimiento intermedio (cambiar la lista de dominio) pero a cambio es un diseño muy sencillo de paralelizar.

Por definición map aplica una función a cada elemento de una lista, implicitamente no hay relación entre cada cálculo realizado por map, así que cada operación la puede realizar un nodo.

Tras eso se necesita almacenar todos los resultados en un nodo central para obtener el resultado final, mayor eficiencia obtendremos en este algoritmo cuanto más porcentaje del cálculo lo hagamos mediante map y menos mediante reduce.