¿Qué tipo de problemas resuelve MapReduce?

He estado leyendo sobre MapReduce por un tiempo, pero lo que no puedo entender es cómo alguien tomaría la decisión de usar (o no usar) MapReduce.

Quiero decir, ¿cuáles son los patrones de problemas que indican que MapReduce podría usarse?

Básicamente, los problemas son enormes, pero no difíciles. El vendedor ambulante depende de manera crucial de la distancia entre cualquier par de ciudades, por lo que si bien se puede dividir en muchas partes, los resultados parciales no se pueden recombinar para que surja la solución óptima global (bueno, probablemente no; si conoce una forma, solicite su medalla Fields ahora).

Por otro lado, contar frecuencias de palabras en un corpus gigantesco es trivialmente divisible y trivialmente recombinable (solo suma los vectores calculados para los segmentos del corpus), por lo que la solución obvia es la reducción del mapa.

En la práctica, más problemas tienden a ser fácilmente recombinables que no, por lo que la decisión de paralelizar una tarea o no tiene más que ver con qué tan grande es la tarea y menos con lo difícil que es.

¿Se puede resolver el problema de manera eficiente utilizando la informática distribuida?

Si la respuesta a esta pregunta es sí, entonces tiene un problema candidato para MapReduce. Esto se debe a que el patrón del problema se presta para dividirse en problemas aislados más pequeños.

Tu tarea: analizar este libro

Un ejemplo funciona bien para ilustrar esto. Tiene un documento grande ( Moby Dick por Herman Melville ) y su trabajo consiste en realizar un análisis de frecuencia de todas las palabras que se utilizan en él.

El enfoque secuencial

Puede hacer esto secuencialmente obteniendo su máquina más rápida (tiene muchas cosas por ahí) y recorriendo el texto de principio a fin manteniendo un mapa hash de cada palabra que encuentre (la clave) e incrementando la frecuencia (valor) cada vez Analizas una palabra. Simple, directo y lento.

El enfoque MapReduce

Al abordar esto desde una perspectiva diferente, observa que tiene todas estas máquinas de repuesto y podría dividir esta tarea en trozos. Dele a cada máquina un bloque de texto de 1Mb para analizar en un mapa hash y luego coteje todos los mapas hash de cada uno en un solo resultado. Esta es una solución de MapReduce en capas.

El proceso de leer una línea de texto y reunir las palabras es la fase del Mapa (se crea un mapa simple que representa las palabras en la línea con su frecuencia 1,2,3, etc.), luego la fase Reducir es cuando cada máquina clasifica su línea mapas en un solo mapa agregado.

La solución general proviene de una fase de reducción adicional donde todos los mapas agregados se agregan (esa palabra nuevamente) en un mapa final. Ligeramente más complejo, masivamente paralelo y rápido.

Resumen

Entonces, para resumir, si su problema se presta a ser representado por claves, valores, operaciones agregadas en esos valores de forma aislada, entonces tiene un problema candidato para MapReduce.

El patrón MapReduce se toma del mundo de la programación funcional. Es un proceso para aplicar algo llamado catamorfismo sobre una estructura de datos en paralelo. Los programadores funcionales usan catamorfismos para casi todas las transformaciones o resúmenes simples.

Suponiendo que sus datos son un árbol, el factor decisivo es si puede calcular un valor para un nodo utilizando solo los datos contenidos en ese nodo y los valores calculados para sus hijos.

Por ejemplo, puede calcular el tamaño de un árbol utilizando un catamorfismo; calcularía la suma de los valores calculados para todos los hijos más uno.

Este WPI - Las aplicaciones de Map Reduce (ppt) pueden ser de su interés. Discute diferentes aplicaciones de MR, y como uno de los casos discutidos, muestra cómo Al usar 100 instancias de EC2 y 24 horas, el New York Times pudo convertir 4TB de artículos escaneados a 1.5TB de documentos PDF.

Otro conjunto de ejemplos en los que MR ayudó a acelerar el rendimiento es: Aster: SQL Map Reduce muestra algunos estudios de caso de la tecnología SQL-Map Reduce, incluida la detección de fraudes, las transformaciones y otros.

Map / Reduce es una forma específica de un tipo específico de algoritmo. Lo usa para transformar un gran conjunto de datos en otro conjunto de datos. (El conjunto de datos de resultados puede o no ser enorme.) Si no desea un conjunto de salida de datos estáticos como resultado de la entrada de datos estáticos, entonces Map / Reduce no es apropiado. Map / Reduce puede decirle fácilmente cuántos John Smiths hay en la guía telefónica de Manhattan, pero no es adecuado para construir un servidor web.

La forma en que Map / Reduce funciona es:

• Map toma pares de claves (k1) y valores (v1) y los asigna a un nuevo conjunto de claves (k2) y valores (v2).
• Reducir toma todos los valores v2 con la misma clave k2 y produce un nuevo valor (v3).

El resultado es que una lista de pares (k1, v1) se transforma en una lista de (v3) s. (Por supuesto, el valor "v3" puede ser un compuesto que incluya k2, que podría definirse como igual a k1).

Entonces lo usas:

1. Si tiene tantos datos para comenzar, ejecutarlos secuencialmente a través de uno o dos servidores llevaría demasiado tiempo, y

2. Puede concebir los datos de salida como una lista de valores o pares de valores clave (generalmente no demasiado difícil cuando recuerda que "clave" solo significa "etiqueta única"), y

3. Cualquiera sea la relación, está seguro de que cada pieza de datos de entrada solo afecta el valor de salida para una clave de salida.

Si todos sus datos pueden ser procesados ​​secuencialmente por un solo servidor, entonces, dado que ese es el paradigma informático dominante (aquellos para los que los servidores están diseñados y los programadores están capacitados), use un solo servidor.

La etapa del mapa debe dividir todos los datos de entrada por clave de salida. No tiene que producir el valor de salida asociado con la clave de salida (que se realiza mediante la etapa de reducción), pero sí tiene que asignar de forma exclusiva cada par de valores de clave de entrada para contribuir al máximo al valor de una clave de salida. Si los datos están demasiado interrelacionados, la reducción de mapas podría no ser capaz de manejar el problema. Por otro lado, puede ser que necesites usar múltiples rondas de mapa / reducción.

Si no puede encontrar la manera de convertir su transformación de datos en un mapa / reducir, entonces, por supuesto, no es una solución.

Hay un verdadero arte en descubrir si un problema puede descomponerse en algo que Map / Reduce pueda manejar. Por ejemplo, v1 y v2 podrían no estar en los conjuntos de datos de entrada o salida en absoluto. Si solo desea contar elementos únicos en los datos de entrada, entonces k1 = k2 = un elemento y v1 = v2 = 1 o 0 o realmente cualquier cosa. Reducir solo produce v3 como la suma de la cantidad de k2 que se le dio.

Por lo tanto, es difícil decir con certeza que una transformación de datos no se puede hacer usando Map / Reduce, pero lo anterior le brinda algunas pautas.

MapReduce funciona en cualquier problema que se compone de exactamente 2 funciones en algún nivel de abstracción. La primera función se aplica a cada uno de los elementos del conjunto de entrada, y la segunda función agrega los resultados.

Por lo tanto, cada vez que desee obtener el resultado (1) de (n) entradas, y todas las entradas pueden ser examinadas / utilizadas por la función (1), puede usar MapReduce. Nuevamente, esto está en algún nivel específico de abstracción. La función (1) puede ser alguna función de agrupación que verifica la entrada y decide cuál de varias otras funciones usar.

Esto es útil cuando no sabe de antemano la cantidad de información que tendrá, cuando necesite compartir "unidades" discretas de trabajo, o cuando desee que una sola devolución represente el resultado completo (IE ejecuta cinco mil pruebas unitarias) , y si menos del x% falla, devolverá el éxito).

La mayoría de las respuestas aquí parecen ser una variación de la explicación de lo que hace la reducción de mapas, lo cual es válido. Pero para responder a la pregunta, cuál fue el patrón que indicaría dónde podría usar el mapa de reducción no se aborda realmente con eso.

Si la implementación ingenua, no funcional, del problema que está viendo implica hacer un bucle sobre algo y luego actualizar algo fuera del bucle con algún estado desde el interior del bucle, es probable que tenga algo que los puertos pueden reducir. Especialmente si puede generalizar la actualización del estado central a una función que funciona con solo dos parámetros y puede garantizar que esta función sea conmutativa y asociativa.

La razón por la que podría desear usar map reduce si eso es cierto es doble: 1) podría ser un poco más limpio y más fácil de probar y depurar si divide cosas en map y reduce funciones. 2) las funciones de reducción de mapas no tienen estado y pueden ejecutarse simultáneamente, lo que acelera las cosas si tiene múltiples cpus disponibles y algo como hadoop o spark que hace uso de eso para ejecutar cosas en un clúster.

Esto es bueno si está recorriendo muchas cosas, pero su kilometraje puede variar según la complejidad de su mapa / reducción. Es bastante común terminar con una cadena secuencial o un árbol de reducciones de mapas, donde al final todo sigue bloqueado en algún paso complejo de reducción al final de la cadena. Por ejemplo, muchos algoritmos de gráficos son difíciles de escalar de manera eficiente con solo reducir mapa.

El ejemplo más simple que funciona bien con la reducción de mapas es contar cosas, que es una reducción muy barata. Esta es la razón por la cual el conteo de palabras es un ejemplo de uso frecuente para reducir mapa. Puede esperar una escalabilidad lineal para el rendimiento con ese caso de uso: cada CPU que agregue lo hace más rápido.

Si hace mucha programación funcional, comienza a encontrarse con situaciones que requieren un mapa general y reducir. Probablemente incluso los vea en una programación imperativa, pero no los reconozca detrás de la máscara de bucles y acumuladores.

Como ejemplo de uno que se me ocurrió recientemente, he estado trabajando en un analizador en Haskell. Para probar mi analizador, bombeo una lista de fragmentos de cadena a través del analizador, y luego quiero obtener una sola cadena que pueda mostrar mis resultados para ver si se analizó correctamente. Entonces eso se ve así:

--my initial set of test data, a list
tests = ["string1", "string2", "string3", ...]

--Map Step: turn strings into parsed results
--note the type, which demonstrates the map
applyParser :: [String] -> [Token]
--The actual function
applyParser input = map parser input

--Second map, turn tokens into output
showTokens :: [Token] -> [String]
showTokens t = map show t

--Reduce step, concat the results
combineResults :: [String] -> String
--In haskell, reduce is the foldl function, which takes an operation to fold with, a starting element, and a list to fold on
combineResults strings = foldl concat "" strings

--Finished program
testParser = print (combineResults(showTokens(applyParser tests)))

Por supuesto, esto es solo pedagógico. Mi código real se ve un poco diferente y usa más funciones internas (como fold concatno es necesario ya que Haskell ya incluye unlineseso [String]->String). Mi punto principal fue que no anticipé el uso de un mapa / reducción cuando comencé, simplemente se alineó con mis necesidades. Quería hacer algunas cosas con listas, luego convertir mi lista en un solo elemento de salida. El uso de map / reduce surgió naturalmente.

El procesamiento de cadenas (como el análisis) es un uso muy obvio de la reducción del mapa, el mapeo es la aplicación de varias transformaciones en el texto de entrada, y lo reduce volviendo a unir el texto resultante como salida. Del mismo modo, un compilador podría ser similar, utilizando pliegues para convertir una secuencia de elementos del Árbol de sintaxis abstracta en una mejor forma (optimización).

¿Es paralelizable?

Cualquier problema paralelizable es esencialmente mapear y plegar; por el contrario, el paso del mapa es inherentemente paralelizable (y el paso de plegado puede ser, dependiendo de la estructura sobre la que se pliega), por lo que esta es una propiedad bidireccional.

Supongamos que está buscando un grupo de servidores y uno no puede responder en ese momento. Lo que hará mapReduce es que no podría acceder a ese nodo de árbol al Mapa más grande, lo reprogramará para más tarde y realizará el Mapa o la Reducción en ese momento. Esencialmente trata de garantizar que toda la información esté disponible con la imprevisibilidad del software y el hardware en los entornos.

Estas son las principales preguntas que uso para probar una decisión de usar (o no usar) MapReduce.

• ¿Es importante lograr un rendimiento razonable de ejecución paralela con un mínimo esfuerzo del programador para un problema determinado?
• ¿Tengo disponible un gran número (cientos) de elementos de ejecución paralelos?
• ¿Existe un excelente ancho de banda / rendimiento de comunicación entre los elementos de ejecución paralelos?
• ¿Necesito procesar una gran cantidad (TB) de datos?

• ¿El problema que estoy tratando de resolver se descompone en la operación Map and Reduce?

  • Mapa: ejecute la misma operación en todos los datos.
  • Reducir: ejecute la misma operación en cada grupo de datos producido por Map.

en efecto, es un patrón genérico de "divide y vencerás", por lo que las soluciones para distribuir el cálculo pueden escribirse genéricamente.

Un ejemplo simple es como un documento grande. El problema es que desea contar la cantidad de letras en ese documento. en lugar de ejecutarlo en una sola máquina, puede dividirlo en una matriz de todas las palabras del documento. entonces puede procesar cada palabra individualmente y los resultados nuevamente.

el patrón es útil, porque una vez que obtiene un mapa genérico / reduce la implementación en funcionamiento, puede resolver cualquier problema usando esa misma capa de software, solo necesita expresar su problema en términos de él.