¿Cuál es la novedad en MapReduce?

68

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 mapy está reduceen 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?


  1. Patente de Estados Unidos 7.650.331: "Sistema y método para el procesamiento eficiente de datos a gran escala" (2010)
  2. Modelo de programación MapReduce de Google - Revisado por R. Lämmel (2007)
Rafael
fuente
77
No hay novedad. No responderé a esto, pero creo firmemente que MapReduce no descubrió nada nuevo en computación, ni siquiera computación distribuida.
edA-qa mort-ora-y
@Aryabhata: Si hay novedad, esta pregunta tiene una respuesta buena y constructiva. Si no lo hay, se puede decir poco para demostrarlo (excepto tal vez reducir MapReduce a una técnica más antigua explícitamente), cierto. Pero si te sientes así, por supuesto, ¡vota!
Raphael
@ edA-qamort-ora-y: En ese caso, deberíamos poder expresar MapReduce en términos anteriores, ¡y eso sería una buena respuesta!
Raphael
1
@Raphael, estoy de acuerdo, pero no estoy seguro de poder hacerlo. Sin embargo, puedo observar que, como se describe aquí (primera cita), la ordenación por fusión utiliza el método exacto de mapa / reducción. De hecho, se puede distribuir con cero alteración.
edA-qa mort-ora-y

Respuestas:

47

No puedo evitar pensar: ¡esto es dividir y conquistar, simple y llanamente!

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.


Entonces, ¿hay alguna novedad (conceptual) en MapReduce en alguna parte, o es solo una nueva implementación de viejas ideas útiles en ciertos escenarios?

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

  1. evaluar una tubería de dos operadores ortogonales bien entendidos que se pueden distribuir de manera eficiente y tolerante a fallas en un problema particular: crear un índice de texto de corpus grande
  2. evaluación comparativa del mapa: reduzca ese problema para mostrar cuántos datos se transfieren entre nodos y cómo las diferencias de latencia en las etapas afectan la latencia general
  3. mostrando cómo hacer que el sistema sea tolerante a fallas para que las fallas de la máquina durante el cálculo puedan compensarse automáticamente
  4. identificar optimizaciones y opciones de implementación útiles específicas

Algunas de las críticas caen en estas clases:

  1. "Map / reduce no abre nuevos caminos en la teoría de la computación". Cierto. La contribución del artículo original fue que estos operadores bien entendidos con un conjunto específico de optimizaciones se habían utilizado con éxito para resolver problemas reales con mayor facilidad y tolerancia a fallas que las soluciones únicas.
  2. "Este cálculo distribuido no se descompone fácilmente en operaciones de mapa y reducción". Bastante justo, pero muchos lo hacen.
  3. "Una tubería de n etapas de mapa / reducción requiere una latencia proporcional al número de pasos de reducción de la tubería antes de que se produzcan resultados". Probablemente cierto. El operador de reducción tiene que recibir todas sus entradas antes de que pueda producir una salida completa.
  4. "Mapear / reducir es excesivo para este caso de uso". Tal vez. Cuando los ingenieros encuentran un martillo nuevo y brillante, tienden a buscar cualquier cosa que parezca un clavo. Eso no significa que el martillo no sea una herramienta bien hecha para cierto nicho.
  5. "Map / reduce es un mal reemplazo para una base de datos relacional". Cierto. Si una base de datos relacional escala a su conjunto de datos, entonces maravilloso para usted: tiene opciones.
Mike Samuel
fuente
Bueno, llaman al documento original "seminal", así que espero algo nuevo. No entiendo tu primer párrafo: claramente hay muchas técnicas algorítmicas que no se dividen y se conquistan . Si MapReduce es "solo" una implementación eficiente de d & c para un conjunto de problemas específico, ciertamente no es nada seminal o digno de patente en algoritmos (en mi humilde opinión). Eso no dice que no sea un buen sistema. Tenga en cuenta que mi crítica es menos con MapReduce en sí (supongo que es bueno para lo que está hecho) que con su recepción por parte de la comunidad.
Raphael
1
@Raphael, no creo que M / R se divida y conquiste en el sentido en que se vincula. No implica la aplicación repetida de un algoritmo a un subconjunto más pequeño de la entrada original. Es una tubería donde las etapas de la tubería son mapas alternos y reducen las operaciones.
Mike Samuel
Huh, cierto Interpreté "Un nodo de trabajo puede hacer esto de nuevo a su vez, lo que lleva a una estructura de árbol de varios niveles". de esta manera, pero eso no implica, por supuesto, que ocurra lo mismo en todos los niveles.
Raphael
1
@ ex0du5, creo que puede condenarlo por reclamos que no hace. "Muchos sistemas han proporcionado modelos de programación restringidos y han utilizado las restricciones para paralelizar el cálculo automáticamente ... MapReduce puede considerarse una simplificación y destilación de algunos de estos modelos en función de nuestra experiencia con grandes cálculos del mundo real ... En contraste , la mayoría de los sistemas de procesamiento en paralelo solo se han implementado en escalas más pequeñas y dejan los detalles de manejo de fallas de la máquina al programador ". Cita documentos de Rabin y Valiant sobre eso, pero no el de Liskov.
Mike Samuel
1
@ ex0du5, lo suficientemente justo. Pensé "" Map / reduce no abre nuevos caminos en la teoría de la computación ". Verdadero". fue lo suficientemente claro, pero he reescrito la lista de contribuciones.
Mike Samuel
21

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.

O(nϵ)o(logn)

O(1)

  • Particionar la instancia del problema (a menudo al azar)
  • Haga un cálculo en cada partición en paralelo y represente el resultado del cálculo de forma compacta
  • Combine todas las soluciones de subproblemas representadas de forma compacta en un único procesador y termine el cálculo allí

nO(n)n

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.

Sasho Nikolov
fuente
Podría decirse que M / R es un modelo más realista (útil) que PRAM o streams. (Al menos para un conjunto de problemas razonablemente grande.)
Xodarap
"necesita comprimir soluciones de subproblemas para que un único procesador pueda conquistar" - Parece que está diciendo que el conjunto de problemas que puede resolver M / R es un subconjunto de aquellos para los cuales existen caché o caché manejables -Ocultas soluciones. Si es correcto, entonces me parece que esta declaración se aplica igualmente bien a la mayoría de los esquemas de computación distribuidos.
Mike Samuel
1
@Xodarap que bien puede ser. Aquí estoy usando un punto de vista puramente teórico de algoritmos: un modelo es útil si conduce a nuevas perspectivas algorítmicas. en esa medida, la transmisión no es totalmente realista, pero ha llevado a numerosas técnicas nuevas que en realidad son útiles en la práctica. El punto es, cuál es la abstracción correcta que conduce a un nuevo pensamiento. Las abstracciones de MR actuales tienen un éxito mixto (pero supongo que algo de éxito)
Sasho Nikolov
1
@MikeSamuel la "necesidad" en esa oración significa que esto es lo que la técnica requiere para funcionar, no es lo único que se puede hacer. No hay resultados teóricos negativos para MR que yo sepa. mi queja no es que MR sea estrictamente menos poderoso que CO. Es que no hemos visto mucho pensamiento algorítmico nuevo inspirado en el modelo (que está bien para un sistema, pero decepcionante para un modelo de computación). Por otro lado, el olvido del caché en sí mismo es una idea increíble
Sasho Nikolov
@SashoNikolov, Entendido. Gracias por la explicación.
Mike Samuel
6

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.

Massimo Cafaro
fuente
3

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.

NC=P

Xodarap
fuente
No estoy familiarizado con MapReduce, pero su presentación no se ve diferente de lo que recuerdo haber sido presentado como el caso ideal en Parallelism 101 en el siglo anterior.
Gilles 'SO- deja de ser malvado'
@Gilles: ¡Mi intención era solo mostrar que "divide y vencerás"! = " Divide y vencerás distribuible ". M / R es menos trivial, aunque podría decirse que aún no es original.
Xodarap
En la programación funcional, todos los mapas pueden ser paralelos (vergonzosamente), entonces ¿por qué no apegarse a ese paradigma? No veo cómo countes una variable compartida en su pseudocódigo; simplemente pasar su valor actual a do_somethingdeberí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)?
Raphael
@Raphael: reescribí mi respuesta para responder mejor a tu comentario. Puedo agregar un ejemplo de cuándo la pureza es molesta, si todavía quieres.
Xodarap
1
@Raphael: Estoy de acuerdo en que mi respuesta sería mucho mejor si pudiera citar algún artículo que muestre que el tiempo de programación cae de X horas a Y usando M / R, o aumenta de A a B al aplicar la pureza, pero creo que todo lo que puedo hacer es agitar mis manos furiosamente e insistir en que las diferencias no son triviales.
Xodarap