sábado, 28 de abril de 2012

MapReduce, con que se come?



Mucha gente habla de MapReduce, pero que es MapReduce? Porque estan importante?
MapReduce fue introducido por google en 2004 y consiste en una técnica para procesamiento de grandes cantidades de datos ditribuidos. Sigue la filosofía “divide y venceras!”
La implementación de este algoritmo fue escrito en varios lenguajes de programación.
MapReduce es un algoritmo para la resolución de problemas los cuales es necesario procesar  enormes conjuntos de datos utilizando un gran número de equipos (nodos), denominados clusters (si todos los nodos están en la misma red local y el uso de hardware similar) o grid (si los nodos esta distribuidos geográfica   o  no son tan similares). Procesamiento computacional puede ser en cualquiera de los datos almacenados en un sistema de archivos (no estructurada) o en una base de datos(estructurados).

El algoritmo cuenta con 2 pasos Map y Reduce:

  • Map: El nodo maestro toma la entrada, la divide en pequeños sub-problemas, y los distribuye a los nodos. Un nodo puede hacer esto de nuevo a su vez, conduce a una estructura de árbol multi-nivel. El nodo procesa el problema más pequeño, y pasa a la parte posterior respuesta a su nodo maestro. 
  • Reduce: El nodo maestro a continuación recoge las respuestas a todos los sub-problemas y los combina de alguna manera para formar la salida, la respuesta al problema que fue originalmente tratando de resolver.


Parece fácil, y bastante lógico. MapReduce permite el procesamiento distribuido de los nodos hoja y las operaciones de reducción. Siempre que cada operación de asignación es independiente de los demás, todos los mapas se puede realizar en paralelo, aunque en la práctica está limitada por el número de fuentes de datos independientes y / o el número de CPU cerca de cada fuente. De manera similar, un conjunto de 'reductores' puede realizar la fase de reducción, proporcionan todas las salidas de la operación de mapa que se presentan comparten la misma clave para el reductor mismo al mismo tiempo. Si bien este proceso pueden aparecer a menudo ineficientes en comparación con los algoritmos que son más secuencial, MapReduce se puede aplicar a conjuntos de datos significativamente mayores que "commodity" servidores pueden manejar una granja de servidores de gran tamaño se puede utilizar MapReduce para ordenar petabytes de datos en tan sólo unas pocas horas. El paralelismo también ofrece alguna posibilidad de recuperarse de una falla parcial de servidores o almacenamiento durante la operación: si un asignador o reductor falla, el trabajo se puede reprogramar, asumiendo que los datos de entrada aún está disponible.

Los datos de entrada están formadas por una (clave, valor) y a cada dato es aplicada la función map, la cual produce una serie de resultados intermedios (de 0 a N), dichos resultados también están formados por (clave, valor). Luego, una vez finalizado todas las funciones map el proceso de MapReduce agrupa por clave los resultados intermedios, y a cada dato (clave, [resultado1, resultado2, ... resultadoN]) aplica la función reduce. De esta forma obtiene el resultado del problema inicial.

Hadoop es la implementación MapReduce más usada en el mundo del software libre, proveyendo no solo una implementación MapReduce sino toda una infraestructura distribuida.

Dejo links:

http://hadoop.apache.org/mapreduce/