He estado leyendo acerca de 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 utilizarse?
He estado leyendo acerca de 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 utilizarse?
Básicamente, los problemas son enormes, pero no difíciles. El vendedor ambulante depende fundamentalmente de la distancia entre un par de ciudades dado, por lo que si bien puede dividirse en muchas partes, los resultados parciales no se pueden combinar de modo que surja la solución óptima a nivel mundial (bueno, probablemente no ; si conoce alguna manera, solicite su medalla Fields ahora).
Por otro lado, contar frecuencias de palabras en un corpus gigantesco es particionable de manera trivial, y se puede recombinar de forma trivial (solo se suman los vectores calculados para los segmentos del corpus), por lo que se reduce el mapa Es la solución obvia.
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 qué tan difícil es.
¿Se puede resolver el problema de manera eficiente utilizando computación distribuida?
Si la respuesta a esta pregunta es sí, entonces tiene un problema candidato para MapReduce. Esto se debe a que el patrón de problemas se presta a ser dividido 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 es realizar un análisis de frecuencia De todas las palabras utilizadas en ella.
El enfoque secuencial
Puedes hacer esto de forma secuencial obteniendo tu máquina más rápida (tienes muchas opciones) y corriendo sobre el texto de principio a fin, manteniendo un mapa hash de cada palabra que encuentres (la tecla) e incrementando la frecuencia (valor ) cada vez que analizas una palabra. Sencillo, directo y lento.
El enfoque de MapReduce
Al abordar esto desde una perspectiva diferente, observa que tiene todas estas máquinas de repuesto y que podría dividir esta tarea en partes. Dé 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 recopilar las palabras es la fase del Mapa (creas un mapa simple que representa las palabras en la línea con su frecuencia 1,2,3, etc.), luego la fase de Reducir es cuando cada máquina recopila sus mapas de líneas en un solo mapa agregado.
La solución general proviene de una fase de reducción adicional en la que todos los mapas agregados se agregan (esa palabra nuevamente) en un mapa final. Ligeramente más complejo, masivamente paralelo y rápido.
Summary
Entonces, para resumir, si su problema se presta para 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 utilizan 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, puedes calcular el tamaño de un árbol usando un catamorfismo; calcularía la suma de los valores calculados para todos los hijos más uno.
Este WPI - Aplicaciones de Map Reduce (ppt) pueden ser de interés para usted. Discute diferentes aplicaciones de MR, y como uno de los casos discutidos, muestra cómo Utilizando 100 instancias de EC2 y las 24 horas, el New York Times pudo convertir 4 TB de artículos escaneados a 1,5 TB de documentos PDF.
Otro conjunto de ejemplos en los que MR ayudó a acelerar el rendimiento se encuentra en: Aster - Reducción de mapa SQL muestra algunos estudios de caso de tecnología SQL-Map Reduce, incluida la detección de fraudes, transformaciones y otros.
Mapa / Reducir es una forma específica de un tipo específico de algoritmo. Se usa para transformar un conjunto de datos enorme en otro conjunto de datos. (El conjunto de datos de resultados puede o no ser enorme). Si no desea que se establezca una 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 Smith están en la guía telefónica de Manhattan, pero no es adecuado para crear un servidor web.
La forma en que Map / Reduce funciona es:
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 k1).
Así que lo usas:
Si tiene tantos datos para comenzar, ejecutar todo secuencialmente a través de uno o dos servidores tomaría demasiado tiempo, y
Puede concebir que los datos de salida sean una lista de valores o pares de valores clave (en general, no es tan difícil cuando recuerda que "clave" solo significa "etiqueta única"), y
Independientemente de la relación, está seguro de que cada parte de los datos de entrada solo afecta el valor de salida de una clave de salida.
Si todos los datos pueden procesarse secuencialmente por un solo servidor, entonces, dado que ese es el paradigma de computación dominante (los servidores están diseñados para los programadores), use un solo servidor.
La etapa del mapa tiene que particionar 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 en la etapa de reducción), pero sí tiene que asignar de forma única cada par de valores de clave de entrada para contribuir a la mayoría del valor de una clave de salida. Si los datos están demasiado interrelacionados, la reducción de mapa podría no ser capaz de manejar el problema. Por otro lado, puede ser que necesite utilizar varias rondas de mapa / reducir.
Si no puede descubrir cómo convertir su transformación de datos en un mapa / reducir, entonces, por supuesto, no es una solución.
Hay un arte real para averiguar si un problema se puede descomponer en algo que Map / Reduce pueda manejar. Por ejemplo, v1 y v2 podrían no estar en absoluto en los conjuntos de datos de entrada o salida. 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 del número 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 Mapa / Reducir, pero lo anterior le da 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 en el conjunto de entrada, y la segunda función agrega los resultados.
Entonces, cada vez que desee obtener (1) el resultado de (n) entradas, y todas las entradas pueden ser examinadas / utilizadas por la función (1), puede usar MapReduce. Nuevamente, esto está en un 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 las otras funciones usar.
Esto es útil cuando no sabe de antemano la cantidad de información que tendrá, cuando necesite compartir "unidades" de trabajo discretas o cuando desee que una sola devolución represente el resultado completo (IE ejecuta cinco pruebas de mil unidades, y si menos del x% falla, devuelve el éxito).
La mayoría de las respuestas aquí parecen ser una variación de la explicación de qué reduce el mapa, lo cual es válido. Pero para responder a la pregunta, cuál era el patrón que indicaría dónde podría utilizar el mapa reducido, no se aborda realmente con eso.
Si la implementación ingenua, no funcional, del problema que estás viendo implica realizar un bucle sobre algo y luego actualizar algo fuera del bucle con algún estado dentro del bucle, es probable que tengas algo que los puertos puedan mapear 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 es conmutativa y asociativa.
La razón por la que querría usar la reducción de mapas si es cierto es doble: 1) podría ser un poco más limpio y más fácil de probar y depurar si divide las cosas en el mapa y reduce las 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 CPU disponibles y algo como hadoop o spark que hace uso de eso para ejecutar cosas en un clúster.
Esto es bueno si recorres muchas cosas, pero tu kilometraje puede variar dependiendo de lo complejo que sea tu mapa / reducciones. Es bastante común terminar con una cadena secuencial o árbol de reducciones de mapa donde, al final, todo aún se encuentra en un punto de reducción complejo 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 mapa, es contar cosas, lo cual es una reducción muy barata. Esta es la razón por la que el recuento de palabras es un ejemplo de uso frecuente para reducir el mapa. Puede esperar bastante escalabilidad lineal para el rendimiento con esa base de datos: cada CPU que agregue lo hace más rápido.
Si realiza mucha programación funcional, comienza a ejecutarse en situaciones que requieren un mapa general y se reducen. Es probable que incluso los vea en la 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 emitir de mis resultados para ver si se analiza correctamente. Para que se vea como:
--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 concat no es necesario porque Haskell ya incluye unlines que hace [String]->String ). Mi punto principal fue que no anticipé el uso de un mapa / reducción cuando empecé, simplemente se ajustaba a mis necesidades. Quería hacer algunas cosas con listas, luego convertir mi lista en un solo elemento de salida. El uso del mapa / reducir surgió naturalmente.
El procesamiento de cadenas (como el análisis) es un uso muy obvio de la reducción de mapas, el mapeo es la aplicación de varias transformaciones en el texto de entrada, y lo reduce al volver a unir el texto resultante como salida. Del mismo modo, un compilador podría ser similar, utilizando pliegues para convertir una corriente de elementos del árbol de sintaxis abstracta en una mejor forma (optimización).
¿Es paralelizable?
Cualquier problema paralelizable es esencialmente mapear y plegar; a la inversa, el paso del mapa es inherentemente paralelizable (y el paso del pliegue 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, al no poder acceder a ese nodo del árbol al Mapa más grande, lo reprogramará para más adelante y luego realizará el Mapa o la Reducción. 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 utilizo para probar la decisión de usar (o no usar) MapReduce.
¿El problema que estoy tratando de resolver se descompone en el Mapa y reduce la operación?
en efecto, es un patrón genérico de "divide y vencerás", por lo que las soluciones para distribuir el cálculo se pueden escribir de forma genérica.
un ejemplo simple es como un documento grande. el problema es que quiere contar el número de letras en ese documento. en lugar de ejecutarse en una sola máquina, puede dividirla en una matriz de todas las palabras del documento. luego, puede procesar cada palabra individualmente y los resultados volverán a unirse.
el patrón es útil, porque una vez que obtenga un mapa genérico / reduzca el trabajo de implementación, puede resolver cualquier problema usando la misma capa de software, solo necesita expresar su problema en términos de ello.
Lea otras preguntas en las etiquetas programming-practices parallel-programming