- MapReduce
-
MapReduce es un framework introducido por Google para dar soporte a la computación paralela sobre grandes colecciones de datos en grupos de computadoras.
El nombre del framework está inspirado en los nombres de dos importantes métodos, macros o funciones en programación funcional: Map y Reduce
Se han escrito implementaciones de MapReduce en C++, Java, Python y otros lenguajes.
Introducción
Las funciones Map y Reduce están definidas ambas con respecto a datos estructurados en pares (clave, valor). Map toma uno de estos pares de datos con un tipo en un dominio de datos, y devuelve una lista de pares en un dominio diferente:
Map(k1,v1) -> list(k2,v2)
La función de mapeo es aplicada en paralelo para cada ítem en la entrada de datos. Esto produce una lista de pares (k2,v2) por cada llamada. Después de eso, el framework de MapReduce junta todos los pares con la misma clave de todas las listas y los agrupa, creando un grupo por cada una de las diferentes claves generadas.
La función reduce es aplicada en paralelo para cada grupo, produciendo una colección de valores para cada dominio:
Reduce(k2, list (v2)) -> list(v2)
Cada llamada a Reduce típicamente produce un valor v2 o una llamada vacía, aunque una llamada puede retornar más de un valor. El retorno de todas esas llamadas se recoge como la lista de resultado deseado.
Por lo tanto, el framework MapReduce transforma una lista de pares (clave, valor) en una lista de valores. Este comportamiento es diferente de la combinación "map and reduce" de programación funcional, que acepta una lista arbitraria de valores y devuelve un valor único que combina todos los valores devueltos por mapa.
Ejemplo
Este ejemplo de MapReduce es un proceso para contar las apariciones de cada palabra en un conjunto de documentos:
map(String name, String document): // clave: nombre del documento // valor: contenido del documento for each word w in document: EmitIntermediate(w, 1); reduce(String word, Iterator partialCounts): // word: una palabra // partialCounts: una lista parcial de la cuenta agregada int result = 0; for each v in partialCounts: result += ParseInt(v); Emit(result);
Aquí, cada documento es dividido en palabras, y cada palabra se cuenta con valor inicial "1" por la función Map, utilizando la palabra como el resultado clave. El framework reúne todos los pares con la misma clave y se alimenta a la misma llamada Reduce, por lo tanto, esta función sólo necesita la suma de todos los valores de su entrada para encontrar el total de las apariciones de esa palabra.
Categorías:- Partes de programas
- Computación distribuida
Wikimedia foundation. 2010.
