spark google fases example caracteristicas mapreduce

google - Buenos ejemplos de MapReduce



mapreduce mongodb (4)

No pude pensar en ningún otro buen ejemplo que no sea la tarea "cómo contar palabras en un texto largo con MapReduce". Descubrí que este no era el mejor ejemplo para dar a otros la impresión de cuán poderosa puede ser esta herramienta.

No estoy buscando fragmentos de código, realmente solo ejemplos "textuales".

De vez en cuando presento conceptos de MR a las personas. Encuentro las tareas de procesamiento familiares para las personas y luego las mapeo al paradigma de MR.

Por lo general, tomo dos cosas:

  1. Agrupar por / Agregaciones Aquí la ventaja de la etapa de barajado es clara. Una explicación de que el barajado también se distribuye sort + una explicación del algoritmo de ordenación distribuida también ayuda.

  2. Unirse de dos tablas. Las personas que trabajan con DB están familiarizadas con el concepto y su problema de escalabilidad. Muestre cómo se puede hacer en MR.

Map reduce es un marco que fue desarrollado para procesar grandes cantidades de datos de manera eficiente. Por ejemplo, si tenemos 1 millón de registros en un conjunto de datos, y se almacena en una representación relacional, es muy costoso derivar valores y realizar cualquier clase de transformaciones en estos.

Por ejemplo, en SQL, dada la fecha de nacimiento, para saber cuántas personas son mayores de 30 años para un millón de registros tomaría un tiempo, y esto solo aumentaría en orden de magnitud cuando la complejidad de la consulta aumenta. Map Reduce proporciona una implementación basada en clúster donde los datos se procesan de forma distribuida

Aquí hay un artículo de wikipedia que explica de qué se trata map-reduce

Otro buen ejemplo es Finding Friends a través de Maps. Reducir puede ser un poderoso ejemplo para comprender el concepto y un caso de uso bien utilizado.

Personalmente, encontré este enlace bastante útil para entender el concepto

http://stevekrenzel.com/finding-friends-with-mapreduce

Copia de la explicación proporcionada en el blog (en caso de que el enlace se quede obsoleto)

Encontrar amigos

MapReduce es un marco desarrollado originalmente en Google que permite una fácil computación distribuida a gran escala en varios dominios. Apache Hadoop es una implementación de código abierto.

Voy a pasar por alto los detalles, pero se trata de definir dos funciones: una función de mapa y una función de reducción. La función de mapa toma un valor y genera una clave: pares de valores. Por ejemplo, si definimos una función de mapa que toma una cadena y saca la longitud de la palabra como la clave y la palabra misma como el valor, entonces map (steve) devolvería 5: steve y map (savannah) devolverían 8: savannah . Puede haber notado que la función del mapa es sin estado y solo requiere el valor de entrada para calcular su valor de salida. Esto nos permite ejecutar la función de mapa contra valores en paralelo y proporciona una gran ventaja. Antes de llegar a la función de reducción, el marco mapreduce agrupa todos los valores por clave, de modo que si las funciones del mapa generan los siguientes pares clave: valor:

3 : the 3 : and 3 : you 4 : then 4 : what 4 : when 5 : steve 5 : where 8 : savannah 8 : research

Se agrupan como:

3 : [the, and, you] 4 : [then, what, when] 5 : [steve, where] 8 : [savannah, research]

Cada una de estas líneas se pasará como un argumento para la función de reducción, que acepta una clave y una lista de valores. En este caso, podríamos estar tratando de averiguar cuántas palabras de ciertas longitudes existen, por lo que nuestra función de reducción solo contará el número de elementos en la lista y generará la clave con el tamaño de la lista, como:

3 : 3 4 : 3 5 : 2 8 : 2

Las reducciones también se pueden hacer en paralelo, proporcionando nuevamente una gran ventaja. Luego podemos ver estos resultados finales y ver que solo había dos palabras de longitud 5 en nuestro corpus, etc.

El ejemplo más común de mapreduce es contar el número de veces que las palabras ocurren en un corpus. Supongamos que tiene una copia de Internet (he tenido la suerte de haber trabajado en esa situación), y quería una lista de cada palabra en Internet, así como cuántas veces ocurrió.

La forma en que abordaría esto sería convertir los documentos que tiene en tokens (dividirlos en palabras) y pasar cada palabra a un mapeador. El mapeador escupiría la palabra junto con un valor de 1 . La fase de agrupamiento tomará todas las claves (en este caso palabras), y hará una lista de 1. La fase de reducción toma una clave (la palabra) y una lista (una lista de 1 por cada vez que la clave apareció en Internet), y suma la lista. El reductor luego saca la palabra, junto con su conteo. Cuando todo esté dicho y hecho, tendrá una lista de cada palabra en Internet, junto con la cantidad de veces que apareció.

Fácil, ¿verdad? Si alguna vez has leído sobre mapreduce, el escenario anterior no es nada nuevo ... es el "Hola mundo" de mapreduce. Así que aquí hay un caso de uso del mundo real (Facebook puede o no hacer lo siguiente, es solo un ejemplo):

Facebook tiene una lista de amigos (tenga en cuenta que los amigos son una cosa bidireccional en Facebook. Si soy tu amigo, eres mío). También tienen mucho espacio en disco y atienden cientos de millones de solicitudes todos los días. Han decidido calcular previamente los cálculos cuando pueden para reducir el tiempo de procesamiento de las solicitudes. Una solicitud de procesamiento común es la función "Tú y Joe tienen 230 amigos en común". Cuando visitas el perfil de alguien, ves una lista de amigos que tienes en común. Esta lista no cambia con frecuencia, por lo que sería un desperdicio volver a calcularla cada vez que visitaras el perfil (seguro de que podrías usar una estrategia de almacenamiento en caché decente, pero no podría continuar escribiendo sobre mapreduce para este problema). Vamos a usar mapreduce para que podamos calcular los amigos comunes de todos una vez al día y almacenar esos resultados. Más tarde es solo una búsqueda rápida. Tenemos muchos discos, es barato.

Supongamos que los amigos están almacenados como Persona -> [Lista de amigos], nuestra lista de amigos es entonces:

A -> B C D B -> A C D E C -> A B D E D -> A B C E E -> B C D

Cada línea será un argumento para un mapeador. Para cada amigo en la lista de amigos, el mapeador generará un par clave-valor. La clave será un amigo junto con la persona. El valor será la lista de amigos. La clave se ordenará de modo que los amigos estén en orden, haciendo que todos los pares de amigos vayan al mismo reductor. Esto es difícil de explicar con el texto, así que hagámoslo y veamos si puedes ver el patrón. Después de que todos los mapeadores hayan terminado de ejecutarse, tendrás una lista como esta:

For map(A -> B C D) : (A B) -> B C D (A C) -> B C D (A D) -> B C D For map(B -> A C D E) : (Note that A comes before B in the key) (A B) -> A C D E (B C) -> A C D E (B D) -> A C D E (B E) -> A C D E For map(C -> A B D E) : (A C) -> A B D E (B C) -> A B D E (C D) -> A B D E (C E) -> A B D E For map(D -> A B C E) : (A D) -> A B C E (B D) -> A B C E (C D) -> A B C E (D E) -> A B C E And finally for map(E -> B C D): (B E) -> B C D (C E) -> B C D (D E) -> B C D Before we send these key-value pairs to the reducers, we group them by their keys and get: (A B) -> (A C D E) (B C D) (A C) -> (A B D E) (B C D) (A D) -> (A B C E) (B C D) (B C) -> (A B D E) (A C D E) (B D) -> (A B C E) (A C D E) (B E) -> (A C D E) (B C D) (C D) -> (A B C E) (A B D E) (C E) -> (A B D E) (B C D) (D E) -> (A B C E) (B C D)

Cada línea se pasará como argumento a un reductor. La función de reducción simplemente intersectará las listas de valores y emitirá la misma clave con el resultado de la intersección. Por ejemplo, reduce ((AB) -> (ACDE) (BCD)) dará salida (AB): (CD) y significa que los amigos A y B tienen C y D como amigos comunes.

El resultado después de la reducción es:

(A B) -> (C D) (A C) -> (B D) (A D) -> (B C) (B C) -> (A D E) (B D) -> (A C E) (B E) -> (C D) (C D) -> (A B E) (C E) -> (B D) (D E) -> (B C)

Ahora cuando D visita el perfil de B, podemos buscar rápidamente (BD) y ver que tienen tres amigos en común (ACE) .

Un conjunto de operaciones familiares que puede hacer en MapReduce es el conjunto de operaciones SQL normales: SELECT, SELECT WHERE, GROUP BY, ect.

Otro buen ejemplo es la multiplicación de matrices, donde se pasa una fila de M y todo el vector x y se calcula un elemento de M * x.