MapReduce: Programación sencilla para Resultados Grandes

MapReduce es un modelo de programación para el ecosistema Hadoop. Se basa en YARN para planificar y ejecutar el procesamiento en paralelo sobre los bloques de ficheros distribuidos en HDFS. Hay varias herramientas que utilizan el modelo MapReduce para proporcionar una interfaz de alto nivel a otros modelos de programación.

• Hive tiene una interfaz de tipo SQL que añade capacidades que ayudan con el modelado de datos relacionales.

• Pig es un lenguaje de alto nivel de flujo de datos que añade capacidades que ayudan con el modelado de mapas de proceso.

Situación de MapReduce en la pila del ecosistema Hadoop

La programación paralela tradicional requiere experiencia en una serie de conceptos de informática de sistemas. Por ejemplo, son importantes los mecanismos de sincronización como bloqueos, semáforos y monitores, de manera que usarlos de manera incorrecta puede dañar el programa o afectar gravemente al rendimiento. Esta curva alta de aprendizaje complica la programación. También es propensa a errores, ya que el código se puede ejecutar en cientos o miles de nodos, cada uno con muchos núcleos, y nuestro programa debe gestionar cualquier problema relacionado con estos procesos paralelos.

El modelo de programación Map-Reduce simplifica en gran medida la ejecución de código en paralelo, ya que no tiene que tratar con todos estos problemas. Lo único que tenemos que hacer es crear una tarea "map" y una tarea "reduce" sin preocuparnos de los problemas con los múltiples subprocesos (hilos), sincronización o problemas de concurrencia.

Entonces, ¿En que consisten map y reduce? Map y Reduce son dos conceptos basados en la programación funcional, donde la función lambda se basa únicamente en la entrada, al igual que en una función matemática f(x) = y, donde y depende de x. Nosotros proporcionamos una función u operación para Map y otra para Reduce, y el motor en tiempo de ejecución la ejecuta sobre los datos. Para la función Map, la operación se aplica sobre cada elemento de datos, y para la función Reduce, la operación resume o sintetiza los elementos de alguna manera. Obviamente, el uso de Map-Reduce se va a entender mejor con un ejemplo.

Cuando empezamos a aprender un lenguaje de programación solemos comenzar por el clásico programa "Hola Mundo". En el caso de Map-Reduce, ese primer programa de aprendizaje suele ser el contador de palabras, cuya funcionalidad consiste en leer uno o más ficheros de texto y contar el número de ocurrencias de cada palabra en estos ficheros. La salida será un fichero de texto con una lista de palabras y sus frecuencias de ocurrencia en los datos de entrada. Vamos a estudiar cada paso de este programa contador de palabras. Para simplificar vamos a suponer que tenemos un único fichero grande como entrada.

Paso 0: Antes de que se ejecute muestro programa contador de palabras, el fichero de entrada se almacena en HDFS. Como ya sabes, HDFS particiona los bloques a través de múltiples nodos del cluster, en este caso, cuatro particiones etiquetadas A, B, C y D.

Paso 1: El primer paso de Map-Reduce consiste en ejecutar una operación Map en cada nodo. A medida que las particiones de entrada se leen de HDFS, se llama a la función Map para cada línea de la entrada. Observa las primeras líneas de las particiones de entrada A y B, y empieza a contar las palabras. La primera línea en la partición del nodo A dice "My apple is red and my rose is blue". Del mismo modo, la primera línea de la partición B dice "You are the apple of my eye". 

Ahora vamos a ver lo que sucede en el map del primer nodo para la partición A. La función map crea una clave-valor para cada palabra de la línea que contiene la palabra como clave y 1 como valor. En este ejemplo se lee de la línea la palabra "apple" en la partición A, por lo que map genera una clave-valor (apple, 1). Del mismo modo, se observan dos apariciones de la palabra "my" en la primera línea de A, por lo que se crean las entradas de clave-valor (my, 1). Tenemos que tener en cuenta que la función map va a cada nodo que contiene un bloque de datos del fichero, en lugar de que los datos se muevan a la función map. Esto es lo que se entiende como "mover el procesamiento a los datos".

Vamos a ver ahora lo que genera la misma operación map para la partición B. Puesto que cada palabra solo ocurre una vez, se genera una lista de todas las palabras con una pareja clave-valor cada una. Te animo a que le dediques un poco de tiempo a observar las salidas de la función map y cada pareja clave-valor asociada a una palabra.

Paso 2: A continuación, todas la parejas clave-valor generadas por el map se ordenan por clave, y las parejas con la misma clave se mueven o se reorganizan al mismo nodo. Para simplificar este gráfico, cada nodo solo tiene una única palabra en recuadros naranja, pero en general un nodo tendrá muchas palabras diferentes, al igual que con nuestro ejemplo de las dos líneas en las particiones A y B. Aquí vemos que "you" y "apple" se asignan al primer nodo, la palabra "is" al segundo nodo, y las palabras "rose" y "red" al tercero. Aunque por simplicidad se hayan representado cuatro nodos para el map y tres nodos para reorganizar, el número de nodos se puede extender tanto como requiera la aplicación.

Paso 3: A continuación, la operación "reduce" se ejecuta en estos nodos para sumar los valores de las parejas clave-valor. Por ejemplo, (apple, 1) y el otro (apple, 1) se convierte en (apple, 2). El resultado de este "reduce" es una pareja de clave única para cada palabra que se ha leído del fichero de entrada. La clave es la palabra y el valor es el número de ocurrencias.

Haciendo un balance de nuestro ejemplo del contador de palabras, observamos entonces que hay tres etapas distintas, a saber, la etapa de mapeo (map), la etapa de ordenación y reorganización (shuffle and sort), y la etapa de reducción (reduce). Aunque el ejemplo del contador de palabras es bastante simple, representa a un gran número de aplicaciones en las que se pueden aplicar estas tres etapas con el fin de lograr la escalabilidad de datos en paralelo. Por ejemplo, ahora que hemos visto esta aplicación del contador de palabras, podemos reflexionar sobre cómo modificar el algoritmo para indexar todas las direcciones URL por palabras después de un rastreo web. Esto significa que en lugar de indicar un número, las claves harían referencia a las URLs. Esta es una nueva función definida por el usuario en la cual, después de la etapa de mapeo, la salida de la etapa de ordenación y reorganización se parecería a la siguiente:

De una forma parecida a esta es como funciona, de hecho, un motor de búsqueda como el de Google, de manera que si ahora alguien se conectara a la interfaz construida para esta aplicación para buscar la palabra "manzana", e introdujese "manzana", sería fácil obtener todas las direcciones URL que contienen la misma palabra. No es de extrañar que Google escribiera el primer artículo sobre MapReduce ;) Puedes ver el artículo original de Google de 2004 sobre Map-Reduce en este enlace. Es bastante técnico, pero ofrece una visión sencilla sin las implementaciones de los sistemas actuales.

Acabamos de ver como se puede utilizar Map-Reduce en los motores de búsqueda además de contar palabras y documentos. Aunque se pueden añadir muchas más aplicaciones, me voy a detener un momento para discutir como se pueden utilizar en general los elementos del paralelismo de datos en las búsquedas con este patrón de tres etapas. Sin duda hay paralelización durante la etapa de mapeo. Esta paralelización se aplica sobre la entrada, a medida que cada una de las particiones se procesan línea por línea. Para lograr este tipo de paralelismo de datos hay que tomar una decisión sobre la granularidad o nivel de detalle de datos en cada procesamiento en paralelo. En este caso, el grano es de una línea.

También observamos agrupamiento en paralelo de datos en la etapa de ordenación y reorganización. En esta ocasión la paralelización se aplica sobre los productos intermedios, es decir, las parejas individuales de clave-valor. Y después de la agrupación de los productos intermedios se paraleliza la etapa de reducción para construir un fichero de salida. Seguramente habrás observado que los datos se reducen a un conjunto más pequeño en cada etapa.

Esta visión de conjunto nos da una idea del tipo de tareas en que es adecuado aplicar Map-Reduce. Mientras que Map-Reduce destaca en tareas batch independientes, existen determinados tipos de tareas en las que no conviene utilizar Map-Reduce. Por ejemplo, si nuestros datos cambian con frecuencia, Map-Reduce es lento ya que siempre lee todos los datos de entrada. El modelo Map-Reduce requiere que los mapeos y las reducciones se ejecuten de manera independiente unos de otros. Esto simplifica en gran medida nuestro trabajo como diseñadores, ya que no es necesario ocuparse de los problemas de sincronización. Sin embargo, esto significa que los procesos que tienen dependencias no se pueden expresar con Map-Reduce. Por último, Map-Reduce no devuelve ningún resultado hasta que se termine todo el proceso. Debe leer el conjunto de datos de entrada al completo. Esto hace que no sea adecuado para aplicaciones interactivas en las que se deben presentar los resultados al usuario a mucha velocidad, esperando un retorno por parte del usuario.

Resumiendo:

Map-Reduce oculta la complejidad de la programación paralela y simplifica en gran medida la construcción de aplicaciones paralelas. Existen muchos tipos de tareas adecuadas para Map-Reduce incluyendo el posicionamiento en buscadores y el mapeo de conceptos.