frameworks - google - mapreduce mongodb

Explicación simple de MapReduce?

Question

Relacionado con mi pregunta de CouchDB .

¿Alguien puede explicar MapReduce en términos que un numbnuts podría entender?

Answer 1

1. Toma un montón de datos
2. Realice algún tipo de transformación que convierta cada dato a otro tipo de dato
3. Combina esos datos nuevos en datos aún más simples

El paso 2 es Mapa. El paso 3 es Reducir.

Por ejemplo,

1. Obtenga tiempo entre dos impulsos en un par de medidores de presión en la carretera
2. Asigna esos tiempos a velocidades basadas en la distancia de los metros
3. Reduzca esas velocidades a una velocidad promedio

La razón por la que MapReduce se divide entre Map y Reduce es porque diferentes partes se pueden hacer fácilmente en paralelo. (Especialmente si Reduce tiene ciertas propiedades matemáticas).

Para una descripción compleja pero buena de MapReduce, consulte: Modelo de programación de MapReduce de Google - Revisited (PDF) .

Answer 2

Esta es la explicación más simple de MapReduce que encontré.

Mientras menos explique la imagen, más simple queda.

Answer 3

MAP y REDUCE son viejas funciones de Lisp de una época en que el hombre mató a los últimos dinosaurios.

Imagine que tiene una lista de ciudades con información sobre el nombre, el número de personas que viven allí y el tamaño de la ciudad:

(defparameter *cities*
  ''((a :people 100000 :size 200)
    (b :people 200000 :size 300)
    (c :people 150000 :size 210)))

Ahora es posible que desee encontrar la ciudad con la mayor densidad de población.

Primero creamos una lista de nombres de ciudades y densidad de población usando MAP:

(map ''list
     (lambda (city)
         (list (first city)
               (/ (getf (rest city) :people)
                  (getf (rest city) :size))))
     *cities*)

=>   ((A 500) (B 2000/3) (C 5000/7))

Con REDUCE ahora podemos encontrar la ciudad con la mayor densidad de población.

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        ''((A 500) (B 2000/3) (C 5000/7)))

 =>   (C 5000/7)

Combinando ambas partes obtenemos el siguiente código:

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        (map ''list
             (lambda (city)
                (list (first city)
                   (/ (getf (rest city) :people)
                      (getf (rest city) :size))))
             *cities*))

Vamos a introducir funciones:

(defun density (city)
   (list (first city)
         (/ (getf (rest city) :people)
            (getf (rest city) :size))))

(defun max-density (a b)
   (if (> (second a) (second b))
          a
          b))

Entonces podemos escribir nuestro código MAP REDUCE como:

(reduce ''max-density
        (map ''list ''density *cities*))

 =>   (C 5000/7)

Llama a MAP y REDUCE (la evaluación está al revés), por lo que se denomina reducción de mapa .

Answer 4

MapReduce es un método para procesar vastas sumas de datos en paralelo sin requerir que el desarrollador escriba ningún otro código que no sea el mapeador y reducir las funciones.

La función de mapa toma datos y produce un resultado, que se mantiene en una barrera. Esta función se puede ejecutar en paralelo con un gran número de la misma tarea de mapa . El conjunto de datos se puede reducir a un valor escalar.

Entonces, si lo piensas como una declaración de SQL

SELECT SUM(salary)
FROM employees
WHERE salary > 1000
GROUP by deptname

Podemos usar el mapa para obtener nuestro subconjunto de empleados con salario> 1000 que el mapa emite a la barrera en grupos de tamaño de grupo.

Reducir sumará cada uno de esos grupos. Te da tu conjunto de resultados.

Acabo de sacar esto de mis notas de estudio university del documento de Google

Answer 5

No quiero sonar trillado, pero esto me ayudó mucho, y es bastante simple:

cat input | map | reduce > output

Answer 6

Si está familiarizado con Python, seguir es la explicación más simple posible de MapReduce:

In [2]: data = [1, 2, 3, 4, 5, 6]
In [3]: mapped_result = map(lambda x: x*2, data)

In [4]: mapped_result
Out[4]: [2, 4, 6, 8, 10, 12]

In [10]: final_result = reduce(lambda x, y: x+y, mapped_result)

In [11]: final_result
Out[11]: 42

Vea cómo cada segmento de datos sin procesar se procesó individualmente, en este caso, multiplicado por 2 (la parte del mapa de MapReduce). En función de mapped_result , llegamos a la conclusión de que el resultado sería 42 (la parte reducida de MapReduce).

Una conclusión importante de este ejemplo es el hecho de que cada fragmento de procesamiento no depende de otro fragmento. Por ejemplo, si thread_1 asigna [1, 2, 3] y thread_2 maps [4, 5, 6] , el resultado final de ambos hilos seguiría siendo [2, 4, 6, 8, 10, 12] pero nosotros han reducido a la mitad el tiempo de procesamiento para esto. Lo mismo puede decirse de la operación de reducción y es la esencia de cómo funciona MapReduce en computación paralela.

Answer 7

Tomemos el ejemplo del documento de Google . El objetivo de MapReduce es poder utilizar eficientemente una carga de unidades de procesamiento que trabajan en paralelo para algún tipo de algoritmo. El ejemplo es el siguiente: desea extraer todas las palabras y su recuento en un conjunto de documentos.

Implementación típica:

for each document
    for each word in the document
        get the counter associated to the word for the document
        increment that counter 
    end for
end for

Implementación de MapReduce:

Map phase (input: document key, document)
for each word in the document
    emit an event with the word as the key and the value "1"
end for

Reduce phase (input: key (a word), an iterator going through the emitted values)
for each value in the iterator
    sum up the value in a counter
end for

Alrededor de eso, tendrás un programa maestro que dividirá el conjunto de documentos en "divisiones" que se manejarán en paralelo para la fase del Mapa. Los valores emitidos son escritos por el trabajador en un buffer específico para el trabajador. El programa maestro luego delega a otros trabajadores para que realicen la fase Reducir tan pronto como se les notifique que el búfer está listo para ser manejado.

Cada resultado del trabajador (que es un empleado de Map o Reduce) es, de hecho, un archivo almacenado en el sistema de archivos distribuido (GFS for Google) o en la base de datos distribuida para CouchDB.

Answer 8

Una introducción realmente fácil , rápida y "para tontos" a MapReduce está disponible en: http://www.marcolotz.com/?p=67

Publicando parte de su contenido:

En primer lugar, ¿por qué se creó originalmente MapReduce?

Básicamente, Google necesitaba una solución para hacer que los trabajos de computación grandes fueran fácilmente paralelizables, permitiendo que los datos se distribuyeran en varias máquinas conectadas a través de una red. Además de eso, tenía que manejar la falla de la máquina de una manera transparente y administrar los problemas de equilibrio de carga.

¿Cuáles son las verdaderas fortalezas de MapReduce?

Se puede decir que la magia de MapReduce se basa en la aplicación de funciones Mapa y Reducir. Debo confesar, amigo, que estoy totalmente en desacuerdo. La característica principal que hizo que MapReduce sea tan popular es su capacidad de paralelización y distribución automáticas, combinada con la interfaz simple. Estos factores sumados con el manejo transparente de fallas para la mayoría de los errores hacen que este marco sea tan popular.

Un poco más de profundidad en el papel:

MapReduce fue mencionado originalmente en un documento de Google (Dean & Ghemawat, 2004 - enlace aquí) como una solución para hacer cálculos en Big Data utilizando un enfoque paralelo y clusters de productos básicos. A diferencia de Hadoop, que está escrito en Java, el marco de Google está escrito en C ++. El documento describe cómo se comportaría un marco paralelo usando las funciones de Mapa y Reducir de la programación funcional sobre grandes conjuntos de datos.

En esta solución, habría dos pasos principales, llamados Mapa y Reducir, con un paso opcional entre el primero y el segundo, llamado Combinar. El paso de Mapa se ejecutaría primero, realizar cálculos en el par clave-valor de entrada y generar un nuevo valor-clave de salida. Hay que tener en cuenta que el formato de los pares clave-valor de entrada no necesita necesariamente coincidir con el par de formatos de salida. El paso Reducir ensamblaría todos los valores de la misma clave, realizando otros cálculos sobre ella. Como resultado, este último paso generaría pares clave-valor. Una de las aplicaciones más triviales de MapReduce es implementar recuentos de palabras.

El pseudocódigo para esta aplicación se da a continuación:

map(String key, String value):

// key: document name
// value: document contents
for each word w in value:
EmitIntermediate(w, “1”);

reduce(String key, Iterator values):

// key: a word
// values: a list of counts
int result = 0;
for each v in values:
    result += ParseInt(v);
Emit(AsString(result));

Como se puede notar, el mapa lee todas las palabras en un registro (en este caso, un registro puede ser una línea) y emite la palabra como una clave y el número 1 como un valor. Más tarde, la reducción agrupará todos los valores de la misma clave. Pongamos un ejemplo: imagina que la palabra "casa" aparece tres veces en el registro. La entrada del reductor sería [casa, [1,1,1]]. En el reductor, sumará todos los valores de la casa clave y dará como salida el siguiente valor clave: [casa, [3]].

Aquí hay una imagen de cómo se vería en un marco MapReduce:

Como algunos otros ejemplos clásicos de aplicaciones de MapReduce, uno puede decir:

• Recuento de frecuencia de acceso a URL

• Gráfico de enlace web inverso

• Distribuido Grep

• Término Vector por host

A fin de evitar demasiado tráfico de red, el documento describe cómo el marco debe tratar de mantener la localidad de datos. Esto significa que siempre debe intentar asegurarse de que una máquina que ejecuta trabajos Map tenga los datos en su memoria / almacenamiento local, evitando recuperarlos de la red. Con el objetivo de reducir la red mediante la colocación de un asignador, se utiliza el paso de combinador opcional descrito anteriormente. El combinador realiza cálculos en la salida de los mapeadores en una máquina determinada antes de enviarlo a los reductores, que pueden estar en otra máquina.

El documento también describe cómo deben comportarse los elementos del marco en caso de fallas. Estos elementos, en el documento, se llaman como trabajador y maestro. Se dividirán en elementos más específicos en implementaciones de código abierto. Dado que Google solo describió el enfoque en el documento y no lanzó su software propietario, se crearon muchos frameworks de código abierto para implementar el modelo. Como ejemplos, uno puede decir Hadoop o la característica limitada de MapReduce en MongoDB.

El tiempo de ejecución debe ocuparse de detalles de programadores no expertos, como particionar los datos de entrada, programar la ejecución del programa en un gran conjunto de máquinas, manejar fallas de las máquinas (de manera transparente, por supuesto) y administrar la comunicación entre máquinas . Un usuario experimentado puede ajustar estos parámetros, como la forma en que los datos de entrada se dividirán entre los trabajadores.

Conceptos clave:

• Tolerancia a fallas: debe tolerar el error de la máquina con gracia. Para realizar esto, el maestro hace pings a los trabajadores periódicamente. Si el maestro no recibe respuestas de un trabajador determinado en un lapso de tiempo definido, el maestro definirá el trabajo como fallido en ese trabajador. En este caso, todas las tareas de mapa completadas por el trabajador defectuoso se descartan y se entregan a otro trabajador disponible. Algo similar sucede si el trabajador aún estaba procesando un mapa o una tarea de reducción. Tenga en cuenta que si el trabajador ya completó su parte de reducción, todos los cálculos ya se terminaron cuando falló y no es necesario restablecerlos. Como punto principal de falla, si el maestro falla, todo el trabajo falla. Por esta razón, uno puede definir puntos de control periódicos para el maestro, a fin de guardar su estructura de datos. Todos los cálculos que ocurren entre el último punto de control y el fallo maestro se pierden.

• Localidad: para evitar el tráfico de red, el marco intenta asegurarse de que todos los datos de entrada estén disponibles localmente para las máquinas que van a realizar cálculos en ellos. En la descripción original, usa Google File System (GFS) con un factor de replicación establecido en 3 y tamaños de bloque de 64 MB. Esto significa que el mismo bloque de 64 MB (que compone un archivo en el sistema de archivos) tendrá copias idénticas en tres máquinas diferentes. El maestro sabe dónde están los bloques e intenta programar trabajos de mapas en esa máquina. Si eso falla, el maestro intenta asignar una máquina cerca de una réplica de los datos de entrada de tareas (es decir, una máquina de trabajo en el mismo bastidor de la máquina de datos).

• Granularidad de la tarea: suponiendo que cada fase del mapa se divide en M piezas y que cada fase Reducir se divide en R piezas, lo ideal sería que M y R son mucho más grandes que el número de máquinas del trabajador. Esto se debe al hecho de que un trabajador que realiza muchas tareas diferentes mejora el equilibrio dinámico de carga. Aparte de eso, aumenta la velocidad de recuperación en el caso de que el trabajador falle (dado que las muchas tareas de mapa que ha completado pueden distribuirse en todas las demás máquinas).

• Tareas de respaldo: a veces, un trabajador de Mapa o Reductor puede comportarse mucho más lento que los demás en el clúster. Esto puede contener el tiempo de procesamiento total y hacerlo igual al tiempo de procesamiento de esa única máquina lenta. El documento original describe una alternativa llamada tareas de copia de seguridad, que están programadas por el maestro cuando una operación de MapReduce está próxima a completarse. Estas son tareas programadas por el maestro de las tareas en progreso. Por lo tanto, la operación MapReduce se completa cuando finaliza la copia de seguridad o la copia de seguridad.

• Contadores: a veces uno puede desear contar las ocurrencias de eventos. Por este motivo, cuenta dónde fue creado. Los valores de contador en cada trabajador se propagan periódicamente al maestro. Luego, el maestro agrega (Sí. Parece que los agregadores Pregel vinieron de este lugar) los valores de contador de un mapa exitoso y reduce la tarea y los devuelve al código de usuario cuando se completa la operación de MapReduce. También hay un valor de contador actual disponible en el estado maestro, por lo que un humano que observa el proceso puede realizar un seguimiento de cómo se comporta.

Bueno, supongo que con todos los conceptos anteriores, Hadoop será pan comido para ti. Si tiene alguna pregunta sobre el artículo original de MapReduce o algo relacionado, hágamelo saber.

Answer 9

Yendo hasta lo básico para Mapa y Reducir.

El mapa es una función que "transforma" los elementos en algún tipo de lista a otro tipo de elemento y los coloca de nuevo en el mismo tipo de lista.

supongamos que tengo una lista de números: [1,2,3] y quiero duplicar cada número, en este caso, la función para "duplicar cada número" es función x = x * 2. Y sin asignaciones, podría escribir un simple bucle, por ejemplo

A = [1, 2, 3]
foreach (item in A) A[item] = A[item] * 2

y tendría A = [2, 4, 6] pero en lugar de escribir bucles, si tengo una función de mapa podría escribir

A = [1, 2, 3].Map(x => x * 2)

x => x * 2 es una función que se ejecutará contra los elementos en [1,2,3]. Lo que ocurre es que el programa toma cada elemento, ejecuta (x => x * 2) contra él haciendo que x sea igual a cada elemento, y genera una lista de los resultados.

1 : 1 => 1 * 2 : 2  
2 : 2 => 2 * 2 : 4  
3 : 3 => 3 * 2 : 6  

entonces, después de ejecutar la función de mapa con (x => x * 2) tendría [2, 4, 6].

Reducir es una función que "recopila" los elementos en las listas y realiza algunos cálculos en todos ellos, reduciéndolos a un solo valor.

Encontrar una suma o encontrar promedios son todas las instancias de una función de reducción. Por ejemplo, si tiene una lista de números, digamos [7, 8, 9] y los quiere resumir, podría escribir un ciclo como este

A = [7, 8, 9]
sum = 0
foreach (item in A) sum = sum + A[item]

Pero, si tiene acceso a una función de reducción, podría escribirla así

A = [7, 8, 9]
sum = A.reduce( 0, (x, y) => x + y )

Ahora es un poco confuso por qué hay 2 argumentos (0 y la función con xey) pasados. Para que una función de reducción sea útil, debe poder tomar 2 elementos, calcular algo y "reducir" esos 2 elementos a un solo valor, por lo que el programa podría reducir cada par hasta que tengamos un solo valor.

la ejecución sería la siguiente:

result = 0
7 : result = result + 7 = 0 + 7 = 7
8 : result = result + 8 = 7 + 8 = 15
9 : result = result + 9 = 15 + 9 = 24

Pero no desea comenzar con ceros todo el tiempo, por lo que el primer argumento está ahí para permitirle especificar un valor inicial, específicamente el valor en el primer result = línea.

supongamos que quiere sumar 2 listas, podría verse así:

A = [7, 8, 9]
B = [1, 2, 3]
sum = 0
sum = A.reduce( sum, (x, y) => x + y )
sum = B.reduce( sum, (x, y) => x + y )

o una versión que es más probable que encuentres en el mundo real:

A = [7, 8, 9]
B = [1, 2, 3]

sum_func = (x, y) => x + y
sum = A.reduce( B.reduce( 0, sum_func ), sum_func )

Es algo bueno en un software de base de datos porque, con el soporte de Map / Reduce, puede trabajar con la base de datos sin necesidad de saber cómo se almacenan los datos en un DB para usarlo, para eso está el motor de DB.

Solo necesita poder "decirle" al motor lo que desea al proporcionarle una función de Mapa o Reducir y luego el motor de DB podría encontrar su camino alrededor de los datos, aplicar su función y obtener los resultados que quiero todo sin que sepas cómo pasa por todos los registros.

Existen índices, claves, combinaciones, vistas y una gran cantidad de productos que una sola base de datos podría contener, por lo que protegiéndolo contra la forma en que se almacenan realmente los datos, su código es más fácil de escribir y mantener.

Lo mismo ocurre con la programación en paralelo, si solo especifica qué desea hacer con los datos en lugar de implementar realmente el código de bucle, entonces la infraestructura subyacente podría "paralelizar" y ejecutar su función en un bucle paralelo simultáneo para usted.