Introduccion a Hadoop MapReduce
En mi anterior artículo les presente el concepto de Big Data y les comente que una de las mejores herramientas que existen actualmente para trabajar con ella es el framework Hadoop, ya que nos brinda la posibilidad de realizar el analisis de los datos en forma paralela entre miles de computadores distribuídas, y nos ofrece el simple modelo de programacion MapReduce para procesarlos.
En este artículo voy a explicar, a través de un simple ejemplo, en que consiste basicamente MapReduce y en que casos se podría aplicar este modelo.
MapReduce es un modelo de programacion desarrollado por Google, para procesar grandes conjuntos de datos en forma paralela. Como la información con la que trabaja es tan grande, debe ser distribuída entre miles de computadoras para poder ser procesada en un tiempo razonable. El modelo deriva de las funciones Map() y Reduce() que existen en el lenguaje de programacion funcional Lisp.
En Lisp la funcion Map(), recibe como argumentos una funcion y una secuencia de valores y luego aplica esa funcion a cada uno de los valores de la secuencia; luego la funcion reduce() aplica alguna de las operaciones binarias (como por ejemplo la suma) para sumarizar los datos de la secuencia y reducirlos.
En el modelo MapReduce que implementa Hadoop, el usuario debe generar una funcion Map() que genere un conjunto intermedio de pares (clave, valor), y una funcion Reduce() que combine todos los valores intermedios asociados con la misma clave para reducirlos. Hadoop internamente se encargara de distribuir los datos de entrada entre las diferentes CPUs para poder ejecutar las funciones Map() y reduce() en forma paralela y ganar en tiempo y eficiencia. Este modelo, si bien parece muy simple, puede ser aplicado para expresar muchos problemas reales.
Algunos de los casos en los que se podría aplicar este modelos son:
- Coincidencias de un patron: En este caso la funcion Map() emitiría las lineas donde el patron es encontrado y la funcion Reduce() imprimiría el resultado .
- Cuentas de frecuencias variables: Aquí la funcion Map() procesaría el input y daría como resultado una salida de pares tipo (variable, 1), donde cada variable sería la clave del par. Luego la funcion Reduce() sumarizaría los valores para cada variable y nos daría como resultado pares (variable, cuenta total), o sea la variable y su frecuencia de aparición. (Este es el modelo que voy a utilizar en el ejemplo.)
- Indices invertidos: Para estos casos la funcion Map() nos daría como resulta un par (palabra, documento) y luego la funcion Reduce() nos ordenaría los documentos y nos devolvería un output del tipo (palabra, lista de documentos).
- etc.
Si bien el framework Hadoop esta escrito en el lenguaje de programación Java, es tan versatil, que nos permite escribir programas que interactuen con el modelo MapReduce en otros lenguajes diferentes de Java, como ser Python, C++ o Ruby. (En mi ejemplo, las funciones Map() y Reduce() van a ser escritas en Python).
Ejemplo de MapReduce:
Terminada la introduccion, es hora de comenzar con un ejemplo para que quede más claro el modelo. En este ejemplo vamos a intentar responder una pregunta trascendental…
¿Cuantas veces es nombrado Dios en la Biblia?…(Alguno sabe la respuesta?).
Para intentar encontrar la respuesta a esta pregunta vamos a armar un modelo MapReduce que reciba como input el texto de la Biblia y nos devuelva como output el detalle de todas las palabras que posee seguidas de su frecuencia de utilización.
Para armar este modelo vamos a necesitar lo siguiente:
- Un archivo de texto plano con la Biblia; el cual yo descargué del proyecto Gutenberg en el siguiente enlace. (lamentablemente no encontré una traduccion decente de la Biblia en español, por lo que tuve que utilizar la versión en inglés.)
- Una funcion Map() y otra Reduce() para procesar nuestros datos. En este caso yo las voy a implementar en Python.
- El framework Hadoop para ejecutar nuestro modelo MapReduce.
La funcion Map():
Nuestra función Map() nos va a ir leyendo linea por linea el texto de la Biblia y por cada linea se va a quedar con los palabras que la componen. Esta funcion va a devolver un output de pares de las palabras separadas por un tab y el número 1. Su implementación es la siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#!/usr/bin/python ####################################################################### # Map.py # # # # # # Este programa lee el STDIN, por cada linea elimina los espacios # # iniciales y traseros, luego elimina todos los simbolos y convierte # # las palabras a minusculas. Luego se queda con cada una de las # # palabras que componen la linea; y por cada palabra imprime una # # linea con la palabra seguida de un tab y un 1. # # # # Output: palabra\t1 # # ej: foo 1 # # foo 1 # ####################################################################### import sys import re # input viene desde el STDIN (standard input) for line in sys.stdin: # Elimina los espacios atras y adelante de la linea. line = line.strip() # Elimina los puntos, comas y demas simbolos no alfanumericos. line = re.sub(r'[^\w]', ' ', line) # Elimina todos los numeros para quedarme solo con las palabras. line = re.sub('\d+', ' ', line) # Convierte toda la linea a minusculas. line = line.lower() # Divide la linea en palabras. words = line.split() # Incrementa la cuenta. for word in words: # Escribe el resultado en STDOUT (standard output); # delimitado por un tab. # Este output va a ser el input para la funcion reduce. print '%s\t%s' % (word, 1) |
La funcion Reduce():
Nuestra función Reduce() va a recibir el output de la función Map() y va a ir sumarizando por cada clave de los pares (palabras) para devolvernos su frecuencia. El output de la función Reduce() va a ser un listado de todas las palabras (sin repetirse) seguidas por un tab y el número de apariciones que tiene esa palabra (su frecuencia). Su implementación es la siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#!/usr/bin/env python ####################################################################### # Reduce.py # # # # Este programa lee el STDIN que recibe de Map.py y va sumarizando # # por cada clave (palabra) para escribir su frecuencia de aparicion # # El output de este programa son las palabras que recibe de Map.py # # sin repetirse seguidas de un tab y el valor de su frecuencia. # # # # Output: palabra\tfrecuencia # # ej: foo 4 # # raul 2 # ####################################################################### from operator import itemgetter import sys current_word = None current_count = 0 word = None # input viene desde el STDIN for line in sys.stdin: # Elimina los espacios atras y adelante de la linea. line = line.strip() # divide el input recibido desde map.py word, count = line.split('\t', 1) # Convierte count (de momento un string) a int try: count = int(count) except ValueError: # count no es un numero # ignorar/descartar esta linea. continue # Esto funciona porque hadoop ordena map output # por key (o sea, word) antes de pasarlo al reducer if current_word == word: current_count += count else: if current_word: # Escribe el resultado en el STDOUT print '%s\t%s' % (current_word, current_count) current_count = count current_word = word # no olvidar el output de la ultima palabra! if current_word == word: print '%s\t%s' % (current_word, current_count) |
Ahora que ya tenemos el texto de la Biblia y nuestras funciones Map() y Reduce(), solo nos resta ejecutar nuestro modelo MapReduce en Hadoop.
Una vez que termina nuestro trabajo, solo resta revisar el output para encontrar la respuesta a nestra gran pregunta!.
Como vemos la palabra Dios (God en inglés) aparece 4.472 veces en la Biblia!!.
El que quiera puede bajarse el archivo excel con el output de nuestro ejemplo MapReduce del siguiente enlace.
Espero que les haya gustado este artículo y no se pierdan los próximos!
Saludos!!
Ajedrez
Cinco en linea
Pacman
Sudoku
Tetris
Damas
