Buenos ejemplos de MapReduce [cerrado]

Map reduce es un marco que fue desarrollado para procesar cantidades masivas de datos de manera eficiente. Por ejemplo, si tenemos 1 millón de registros en un conjunto de datos y está almacenado en una representación relacional, es muy costoso derivar valores y realizar cualquier tipo de transformación en ellos.

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

Aquí hay un artículo de Wikipedia que explica de qué map-reducese trata.

Otro buen ejemplo es Buscar amigos mediante reducción de mapas, que puede ser un ejemplo poderoso para comprender el concepto y un caso de uso bien utilizado.

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

Copiando la explicación proporcionada en el blog (En caso de que el enlace 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.

Pasaré por alto los detalles, pero todo se reduce a 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 pares clave:valor. Por ejemplo, si definimos una función de mapa que toma una cadena y genera la longitud de la palabra como clave y la palabra misma como valor, entonces map(steve) devolvería 5:steve y map(savannah) devolvería 8:savannah . Es posible que hayas notado que la función de mapa no tiene estado y solo requiere el valor de entrada para calcular su valor de salida. Esto nos permite ejecutar la función de mapa con 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, por lo 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]

Luego, cada una de estas líneas se pasaría como argumento a la función de reducción, que acepta una clave y una lista de valores. En este caso, podríamos estar tratando de calcular cuántas palabras de ciertas longitudes existen, por lo que nuestra función de reducción simplemente contará la cantidad 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 pueden realizarse en paralelo, lo que supone una gran ventaja. Luego podemos mirar 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 aparecen palabras en un corpus. Supongamos que tiene una copia de Internet (he tenido la suerte de haber trabajado en una situación así) y desea una lista de cada palabra en Internet y cuántas veces ocurrió.

La forma en que abordaría esto sería tokenizar los documentos que tiene (dividirlos en palabras) y pasar cada palabra a un asignador. Luego, el mapeador escupiría la palabra junto con un valor de 1. La fase de agrupación tomará todas las claves (en este caso, palabras) y hará una lista de unos. Luego, la fase de reducción toma una clave (la palabra) y una lista (una lista de unos por cada vez que la clave apareció en Internet) y suma la lista. Luego, el reductor genera la palabra, junto con su recuento. Cuando todo esté dicho y hecho, tendrás una lista de cada palabra en Internet, junto con cuántas veces 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 algo bidireccional en Facebook. Si soy tu amigo, tú eres mío). También tienen mucho espacio en disco y atienden cientos de millones de solicitudes todos los días. Han decidido realizar cálculos previos cuando puedan para reducir el tiempo de procesamiento de las solicitudes. Una solicitud de procesamiento común es la función "Joe y tú tenéis 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 visite el perfil (seguro que podría usar una estrategia de almacenamiento en caché decente, pero entonces no podría seguir escribiendo sobre mapreduce para este problema). Usaremos mapreduce para poder calcular los amigos comunes de todos una vez al día y almacenar esos resultados. Más adelante será sólo 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 asignador. Para cada amigo en la lista de amigos, el asignador 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á para 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 texto, así que hagámoslo y veamos si puedes ver el patrón. Una vez que todos los mapeadores hayan terminado de ejecutarse, tendrá 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 cruzará las listas de valores y generará la misma clave con el resultado de la intersección. Por ejemplo, reducir((AB) -> (ACDE) (BCD)) generará (AB) : (CD) y significa que los amigos A y B tienen a 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 (B D)y ver que tienen tres amigos en común (A C E).

Sep 11 '2012 18:09 karthikr