¿MapReduce es algo más que una simple aplicación de divide y vencerás?

Dividir un problema en otros más pequeños hasta que los problemas individuales se puedan resolver de forma independiente y luego combinarlos para responder la pregunta original se conoce como la técnica de diseño de algoritmos de división y conquista . [Ver: Introducción a los algoritmos por CLR]

Recientemente, este enfoque para resolver problemas computacionales, especialmente en el dominio de conjuntos de datos muy grandes, se ha denominado MapReduce en lugar de dividir y conquistar.

Mi pregunta es la siguiente: ¿MapReduce es algo más que un marco propietario que se basa en el enfoque de dividir y conquistar, o hay detalles que lo hacen único en algún aspecto?

Si está preguntando acerca de la arquitectura MapReduce, entonces es en gran medida una técnica de divide y vencerás . Sin embargo, cualquier arquitectura útil de MapReduce tendrá montañas de otra infraestructura para "dividir", "conquistar" y finalmente "reducir" el conjunto de problemas. Con una implementación grande de MapReduce (miles de nodos de cómputo), estos pasos para dividir el trabajo, calcular algo y finalmente recopilar todos los resultados no son triviales. Cosas como el equilibrio de carga, la detección de nodos muertos, guardar el estado intermedio (para problemas de larga duración), son problemas difíciles por sí mismos.

MapReduce es un marco para implementar algoritmos de divide y vencerás de una manera extremadamente escalable , distribuyendo automáticamente unidades de trabajo a nodos en un grupo arbitrariamente grande de computadoras y manejando automáticamente fallas de nodos individuales redistribuyendo la unidad de trabajo a otro nodo.

No es un concepto súper sofisticado, sino una pieza de infraestructura muy útil.

MapReduce diverge de la mayoría de los sistemas de división y conquista de una manera bastante fundamental, pero es tan simple que muchas personas casi lo pierden. El verdadero genio de esto está en etiquetar los resultados intermedios.

En un sistema típico de división y conquista (anterior), divide el trabajo en serie, ejecuta paquetes de trabajo en paralelo y luego combina los resultados de ese trabajo en serie nuevamente.

En MapReduce, divide el trabajo en serie, ejecuta paquetes de trabajo en paralelo y etiqueta los resultados para indicar qué resultados van con qué otros resultados. La fusión es en serie para todos los resultados con la misma etiqueta, pero se puede ejecutar en paralelo para obtener resultados que tengan etiquetas diferentes.

En la mayoría de los sistemas anteriores, el paso de fusión se convirtió en un cuello de botella para todas las tareas, excepto las más triviales. Con MapReduce todavía puede ser así si la naturaleza de las tareas requiere que todas las fusiones se realicen en serie. Sin embargo, si la tarea permite cierto grado de fusión paralela de resultados, entonces MapReduce ofrece una manera simple de aprovechar esa posibilidad. La mayoría de los otros sistemas hacen una de dos cosas: ejecutan todas las fusiones en serie solo porque puede ser necesario para algunas tareas, o bien definen estáticamente la fusión paralela para una tarea en particular. MapReduce le brinda suficientes datos en el paso de fusión para programar automáticamente tanto en paralelo como sea posible, sin dejar de garantizar (suponiendo que no haya cometido errores en el paso de mapeo) que se mantenga la coherencia.

También tenga en cuenta que en MapReduce, está implícito que todos los pasos pueden ser recursivos, por lo que podría tener un paso de mapeo inicial que divide una gran tarea en 5 tareas más pequeñas que se pueden ejecutar en paralelo, pero cada una de ellas podría (en a su vez) se asignan a una serie de otras tareas paralelas más pequeñas, y así sucesivamente.

Esto lleva a una estructura de árbol tanto en el mapeo como en los lados reductores para dividir rápidamente una tarea grande en partes suficientes para aprovechar muchas máquinas.

MapReduce no es simplemente una técnica de dividir y conquistar, aunque se ve así en muchos ejemplos.

En el paso de mapeo, puede y con frecuencia desea hacer una relación de uno a muchos. Por lo tanto, no se está dividiendo simplemente en casos.

Entre el mapa y reducir hay (según la implementación) un paso de clasificación o hashing. La eficiencia de esta operación es extremadamente importante para los requisitos generales de recursos. Sus detalles son invisibles para el programador de la aplicación, pero este paso es el corazón del marco.

La operación de reducción es un tipo de fusión. Lo que puede considerarse como una conquista, pero en la práctica tiende a ser "emitir datos para su uso posterior" o "guardar datos en un almacén de datos". (Tenga en cuenta que si tiene grandes conjuntos de datos, realmente desea que todo se distribuya, incluida la entrada y los resultados finales. Por lo tanto, un almacén distribuido de clave / valor tiene sentido tanto como un lugar para obtener la entrada como para almacenar la salida).