Hace unos años, MapReduce fue aclamado como la revolución de la programación distribuida. También ha habido críticas, pero en general hubo un entusiasmo exagerado. ¡Incluso se patentó! [1]
El nombre recuerda map
y está reduce
en la programación funcional, pero cuando leo (Wikipedia)
Paso del mapa: el nodo maestro toma la entrada, la divide en subproblemas más pequeños y los distribuye a los nodos de trabajo. Un nodo de trabajo puede hacer esto nuevamente a su vez, lo que lleva a una estructura de árbol de varios niveles. El nodo trabajador procesa el problema más pequeño y devuelve la respuesta a su nodo maestro.
Reduzca el paso: el nodo maestro luego recopila las respuestas a todos los subproblemas y los combina de alguna manera para formar la salida, la respuesta al problema que originalmente estaba tratando de resolver.
o [2]
Elementos internos de MAP: [...] MAP divide el valor de entrada en palabras. [...] MAP está destinado a asociar cada par clave / valor dado de la entrada con potencialmente muchos pares clave / valor intermedios.
Elementos internos de REDUCIR: [...] [REDUCIR] realiza una agregación imperativa (por ejemplo, reducción): tome muchos valores y reduzca a un solo valor.
No puedo evitar pensar: ¡esto es dividir y conquistar (en el sentido de Mergesort), simple y llanamente! Entonces, ¿hay alguna novedad (conceptual) en MapReduce en alguna parte, o es solo una nueva implementación de viejas ideas útiles en ciertos escenarios?
Respuestas:
M / R no es dividir y conquistar. No implica la aplicación repetida de un algoritmo a un subconjunto más pequeño de la entrada anterior. Es una tubería (una función especificada como una composición de funciones más simples) donde las etapas de la tubería son mapas alternos y operaciones reducidas. Diferentes etapas pueden realizar diferentes operaciones.
MapReduce no abre nuevos caminos en la teoría de la computación: no muestra una nueva forma de descomponer un problema en operaciones más simples. Muestra que las operaciones más simples particulares son prácticas para una clase particular de problema.
La contribución del documento MapReduce fue
Algunas de las críticas caen en estas clases:
fuente
EDITAR (marzo de 2014) Debo decir que desde entonces he trabajado más en algoritmos para modelos de cómputo tipo MapReduce, y siento que estaba siendo demasiado negativo. La técnica Divide-Comprime-Conquista de la que hablo a continuación es sorprendentemente versátil, y puede ser la base de algoritmos que creo que no son triviales e interesantes.
Permítanme ofrecer una respuesta que será muy inferior a la de Mike en términos de exhaustividad, pero desde un modelo de computación / punto de vista de la teoría algorítmica.
Ahora, creo que esto es realmente un giro interesante en dividir y conquistar, el giro es que después de la etapa de división necesita comprimir las soluciones de subproblemas para que un solo procesador pueda conquistar. Sin embargo, esta parece ser la única técnica que hemos ideado hasta ahora. Falla en problemas con gráficos dispersos, como conectividad dispersa, por ejemplo. Compare esto con el modelo de transmisión, que generó una gran cantidad de nuevas ideas, como el ingenioso algoritmo de muestreo de Flajolet y Martin, el algoritmo determinista de emparejamiento de Misra y Gries, el poder de las técnicas simples de dibujo, etc.
Como paradigma de programación, la reducción de mapas ha tenido mucho éxito. Mis comentarios consideran el mapa reducir como un modelo interesante de computación. Los buenos modelos teóricos son un poco extraños. Si siguen la realidad demasiado de cerca, son difíciles de manejar, pero lo más importante (para tomar prestado un término del aprendizaje automático) los teoremas probados para modelos que son demasiado específicos no se generalizan, es decir, no se mantienen en otros modelos. Es por eso que queremos abstraer tantos detalles como sea posible, sin dejar de tener suficiente como para desafiarnos a crear nuevos algoritmos. Finalmente, esas nuevas ideas deberían poder eventualmente encontrar su camino de regreso al mundo real. PRAM es un modelo poco realista que condujo a ideas interesantes, pero esas ideas demostraron ser raramente aplicables a la computación paralela del mundo real. Por otro lado, la transmisión tampoco es realista, pero inspiró ideas algorítmicas que en realidad se emplean en el mundo real. Verboceto de recuento min . De hecho, las técnicas de dibujo también se utilizan en sistemas basados en la reducción de mapas.
fuente
Estoy totalmente de acuerdo con usted. Desde una perspectiva conceptual, no hay nada realmente nuevo: Map / Reduce se conocía originalmente en Parallel Computing como un modelo de programación de flujo de datos. Sin embargo, desde un punto de vista práctico, Map / Reduce, según lo propuesto por Google y con las posteriores implementaciones de código abierto, también ha impulsado la computación en la nube y ahora es bastante popular para las descomposiciones y el procesamiento en paralelo muy simples. Por supuesto, no es adecuado para nada que requiera un dominio complejo o descomposiciones funcionales.
fuente
Creo que has dado en el clavo con tu comentario.
No es cierto que en cualquier lenguaje funcional los mapas puedan ser paralelos, el lenguaje debe ser puro . (Creo que Haskell es el único lenguaje puramente funcional vagamente convencional. Lisp, OCaml y Scala son todos no puros).
Conocemos los beneficios del código puro incluso antes del tiempo compartido, cuando los ingenieros primero canalizaron sus procesadores. Entonces, ¿cómo es que nadie usa un lenguaje puro?
Es muy, muy, muy difícil. La programación en un lenguaje puro a menudo se siente como programar con ambas manos atadas a la espalda.
Lo que hace MR es relajar un poco la restricción de pureza y proporcionar un marco para otras piezas (como la fase aleatoria), lo que facilita la escritura de código distribuible para una gran fracción de problemas.
fuente
count
es una variable compartida en su pseudocódigo; simplemente pasar su valor actual ado_something
debería funcionar. ¿Puede dar un ejemplo de un algoritmo "real" de d & c (Mergesort, Quicksort, ...) para el cual las llamadas recursivas dependen unas de otras (después de emitir la llamada)?