RSS

Introducción a MapReduce

21 Ago

hadoop-logoComo ya habíamos visto en el anterior post de Introducción a Big Data y HadoopHadoop se basa en dos conceptos fundamentalmente, el modelo de computación MapReduce y el sistema de ficheros distribuidos HDFS. En este post vamos a profundizar un poco más en el modelo MapReduce.

MapReduce es un modelo de computación que permite paralelizar el cómputo de problemas donde contamos con grandes volúmenes de datos. Una de las ventajas de MapReduce es que podemos resolver este tipo de problemas utilizando para ello lo que se conoce como commodity hardware, es decir, computadores de gama básica. Esto permite no tener que invertir en grandes equipos como antiguamente para solucionar problemas tipo Big Data.

Si quieres seguir leyendo esta post en mi otro blog java4developers.com pulsa sobre este enlace. Si lo quieres leer en este mismo blog continua leyendo más abajo.

Fases de MapReduce

Las fases de MapReduce son obviamente las asociadas a la función Map y a la función Reduce, pero también existen otra serie de fases intermedias que deben ser realizadas de forma correcta para que se tenga éxito en la resolución del problema.

  1. Input. Es una fase (previa) a la función Map. Consiste en preparar y dividir (spliting) los datos de entrada del problema en pares claves/valor que son distribuidos entre los distintos nodos que componen el cluster de computadores. Estos bloques parciales suelen ser almacenados en un sistema distribuido de ficheros como HDFS para mejorar la eficiencia del procesamiento. En HDFS estos bloques suelen tener un tamaño de 64 MB. Es normal que además de distribuir esta información haya algún tipo de replicación de datos entre nodos para asegurarnos una buena tolerancia ante fallos.
  2. Map. En esta fase se ejecutará un función de mapeo escrita por el usuario por cada par clave/valor que se encuentre en cada nodo. Tomará como entrada una de las claves y su valor asociado obtenido desde la fase de splitting. La salida de está función será un conjunto de pares clave/valor que más tarde será la entrada de la fase Reduce. Como ya hemos comentado en el post anterior es que una de las ventajas de MapReduce es que es el algoritmo el que va a los datos. Esto evita que exista una transferencia continua de datos entre los distintos nodos del cluster que es uno de los cuellos de botellas más comunes en otros tipos de computación paralela.
  3. Shuffle. Durante esta fase se ordenará de manera local a cada nodo los resultados de la fase anterior. Es conveniente garantizar por parte de la implementación que utilicemos de MapReduce que todos los pares creados en la fase anterior sean enviados como entrada al mismo nodo reducer en la fase posterior. Una manera sencilla de lograr esto es utilizar una función de hash que asocie cada clave a un nodo reducer. Al terminar esta fase se tendrán que distribuir se tendrá un conjunto formado por n claves y una lista de valores asociados a cada una de estas claves.
  4. Reduce. En esta fase se tomará como datos de entrada cada una de las claves y la lista de valores asociados a ella obtenida durante la fase de Shuffeling. Sobre esta lista de valores aplicaremos el algoritmo a través del cual que queramos resolver nuestro problema. La salida de la fase de Reduce es una lista de pares clave/valor.
  5. Output. Los datos obtenidos en la fase de Reduce deberán ser movidos a un sistema de ficheros HDFS, una base de datos o cualquier otro sistema al cualquier queramos consultar el resultado del problema.

El siguiente diagrama obtenido de la Universidad de Washington creo que ilustra muy bien como se suceden las distintas fases en MapReduce:

hadoop_washington_edu

Vamos a ver en la siguiente página un ejemplo concreto de problema resuelto mediante la técnica de MapReduce.

Contador de palabras con MapReduce

Vamos a ver en un ejemplo típico de problema solucionado con la técnica de MapReduce como se van sucediendo las distintas fases. Para ello vamos a solucionar el problema de contar el número de apariciones de cada palabra dentro de un texto plano.

  1. Input. En esta fase vamos a transformar el texto plano en una lista de claves/valor donde la clave podría ser el desplazamiento del primer carácter de cada sentencia del texto y la lista de valores estaría formada por las palabras que conforman cada una de estas sentencias. Esta lista de claves/lista de valores será distribuida entre los distintos nodos del cluster.
  2. Map. La función Map cogerá un elemento de la lista clave/valor. En este caso la clave no es de utilidad por lo que no será utilizada. La lista de valores será tratada de la siguiente forma:
    • Iteraremos sobre la lista de valores/palabras.
    • Si la palabra aparece por primera vez crearemos un par clave/valor, donde la clave será la palabra y el valor se pondrá a cero.
    • Si la palabra ya ha aparecido aumentaremos en una unidad el valor asociado a esa palabra.
    • Finalmente la función de Map emitirá un conjunto de pares clave/valor donde la clave será una palabra y el valor será el número de apariciones de esa palabra dentro de cada una de las sentencias.
  3. Shuffle. En este momento del MapReduce tendremos la siguiente situación. Tendremos en cada nodo del cluster un conjunto formado por pares donde cada clave será una palabra y el valor será el número de apariciones de esta en una sentencia concreta del texto plano original. Durante esta fase vamos a asegurar que cada par que comparte la misma clave sea enviada al mismo nodo reduce. Como se ha explicado anteriormente esto se puede lograr mediante una sencilla función de hash.
  4. Reduce. A cada función Reduce en cada uno de los nodos se le pasará como parámetro una clave (en este caso una palabra) y una lista con el valor de las apariciones en cada una de las sentencias del texto plano. El algoritmo aplicado será sumar dicha lista de valores para obtener el número de apariciones de cada una de las palabras dentro del texto original.
  5. Output. Una vez obtenido el número de apariciones de cada palabra se deberá escribir su resultado a salida estándar, un sistema de ficheros HDFS o a otro tipo de sistema como una base de datos para evaluar dicho resultado.

La siguiente figura ilustra las distintas fases que se dan para el ejemplo de averiguar el número de apariciones de cada palabra en un texto:

MapReduceWordCountOverview

MapReduce en Hadoop

Todas están fases van a estar coordinadas por un nodo maestro que en Hadoop llamaremos Jobtracker y Namenode, el primero se encargará de la gestión de tareas Map y Reduce y el segundo del espacio de nombres y el sistema de ficheros donde se almacena cada uno de los datos/bloques. Normalmente el Jobtracker y el Namenode pueden ser encontrados en el mismo nodo. Además se tendrán varios nodos que se encargarán del almacenamiento y procesamiento local llamados Datanodes y Tasktrackers.

El siguiente diagrama obtenido del paper de Google sobre MapReduce define muy bien los distintos nodos y los procesos de lectura y escritura:

mapreduce-google
Hay mucha bibliografía sobre el tema. Recomiendo un vistazo al paper de Google y como libro el que más me ha gustado ha sido MapReduce Design Patterns: Building Effective Algorithms and Analytics for Hadoop and Other Systems

Enlaces relacionados en este blog:

 
3 comentarios

Publicado por en 21 agosto, 2013 en Big Data

 

Etiquetas: , , ,

3 Respuestas a “Introducción a MapReduce

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

 
A %d blogueros les gusta esto: