MapReduce

MapReduce

1. Framework MapReduce

   • Componentes
     • Modelo basado en el Paradigma de la Programación Funcional
     • Infraestructura hardware distribuida
     • Núcleo del Framework se en carga de:
       • Particionado de datos
       • Planificación, distribución y balance de ejecución del código
       • Manejo de errores HW
       • Gestión de la comunicación
   • Implementación
     • F. Map para procesar datos en tuplas clave/valor
     • F. Reduce para combinar los valores intermedios
   • Modelo
     • Map
       • Recibe como entrada un par clave/valor Map(k1, v1)
         • Devuelve una lista de pares clave/valor intermedias list(k2, v2).
     • Reduce
       • Recibe una clave intermedia (k2) y una serie de valores list(v2)
         • Procesa los datos de la lista para devolver en salida un único valor asociado a cada clave intermedia (k2, v2).
           • Habitualmente se producen entre 0 y 1 valores de salida por cada invocación

2. Infraestructura HW y rendimiento

   • Arquitectura
     • Maestro (Master):
       • Es el coordinador de todos los procesos y se encarga de asignar tareas a los esclavos
     • Esclavos (Workers)
       • Son nodos de ejecución independientes que realizan las tareas que el maestro les indica
   • Tolerancia a fallos
     • Diseñado para ser ejecutado en clústeres de más de 1000 máquinas
       • Fallos en los Esclavos
         • El maestro envía periódicamente una señal a cada uno de los esclavos, los cuales deben responder en un tiempo determinado, si esta respuesta no se produce, el maestro marca el esclavo como caído, realiza un rollback de la tarea no realizada y se coloca en la cola de tareas pendientes de realizar, para su posterior asignación a otro esclavo que sí se encuentre disponible.
       • Fallos en el Maestro
         • Debido a que solo hay un maestro, si este falla, todo el proceso se perdería. Es por este motivo que el maestro realiza puntos de control del proceso, que un segundo maestro, en estado de espera, retomará en caso de fallo del maestro principal.
   • Rendimiento
     • Búsqueda de patrones
       • El programa realiza la búsqueda de un patrón determinado de tres caracteres en una colección de datos de 1 Terabyte, divididos en ficheros de 64 Mbytes, ejecutando 15.000 tareas Map y una única tarea Reduce en un tiempo total de aproximadamente 150 segundos, dando 92.337 ocurrencias del patrón buscado
     • Ordenación
       • El programa realiza la ordenación por clave de un registro de 1 Terabyte de texto, extrayendo la función Map la clave de 10 bytes de cada una de las líneas de texto, y el valor como la propia línea de texto a la que pertenece la clave. La función Reduce simplemente devuelve a la salida la tupla clave/valor intermedias como clave/valor de salida. Utilizando 15.000 workers como mapeadores y 4000 como reductores, el tiempo total de ordenación aproximado fue de 891 segundos