MapReduce y procesamiento paralelo de datos

MapReduce y sus sucesores son modelos y marcos de programación que procesan conjuntos de datos muy grandes en paralelo a través de clústeres de máquinas básicas, manejando automáticamente la distribución, la programación y la tolerancia a fallos.

Definition

MapReduce es un modelo de programación en el que un cálculo se expresa como una función de mapeo que emite pares clave-valor y una función de reducción que agrega los valores para cada clave, ejecutado en paralelo sobre datos particionados en un clúster con distribución y tolerancia a fallos gestionadas por el marco.

Scope

Este tema cubre el modelo MapReduce —que expresa el cálculo como funciones de mapeo y reducción sobre pares clave-valor, con una mezcla automática entre ellas— y la maquinaria de ejecución circundante de particionamiento, programación y tolerancia a fallos mediante la reejecución. Cubre la evolución hacia motores de flujo de datos generales y en memoria (como el modelo de conjunto de datos distribuidos resilientes) y los sistemas de archivos distribuidos que los sustentan. Excluye los modelos de almacenamiento NoSQL y la teoría de la consistencia, que son temas adyacentes.

Core questions

• ¿Cómo las fases de mapeo, mezcla y reducción paralelizan un cálculo?
• ¿Cómo maneja el marco el particionamiento de datos, la programación y los rezagados?
• ¿Cómo se logra la tolerancia a fallos mediante la reejecución de tareas fallidas?
• ¿Por qué los motores de flujo de datos generales y en memoria tuvieron éxito sobre MapReduce para muchas cargas de trabajo?
• ¿Qué papel juegan los sistemas de archivos distribuidos en el procesamiento paralelo de datos?

Key concepts

• funciones de mapeo y reducción
• fase de mezcla y clasificación
• particionamiento de datos
• programación de tareas y rezagados
• tolerancia a fallos por reejecución
• sistema de archivos distribuido
• grafos de flujo de datos
• conjuntos de datos distribuidos resilientes

Key theories

El modelo MapReduce

Los programadores escriben una función de mapeo que transforma los registros de entrada en pares clave-valor intermedios y una función de reducción que combina todos los valores para una clave; el marco maneja la ejecución paralela, la mezcla que agrupa los valores por clave y la recuperación de fallos.

Tolerancia a fallos por reejecución

Debido a que las tareas son funciones deterministas sobre la entrada particionada, el marco tolera los fallos de las máquinas simplemente volviendo a ejecutar las tareas de mapeo o reducción fallidas, y mitiga los nodos lentos lanzando copias de respaldo (especulativas) de las tareas rezagadas.

Motores de flujo de datos en memoria

Sistemas posteriores generalizaron MapReduce a grafos de flujo de datos arbitrarios y mantuvieron los datos intermedios en memoria; la abstracción de conjunto de datos distribuidos resilientes recupera las particiones perdidas volviéndolas a calcular a partir del linaje, acelerando enormemente las cargas de trabajo iterativas e interactivas.

Clinical relevance

El procesamiento paralelo de datos hizo que la computación a escala de clúster fuera accesible para los programadores comunes: MapReduce y sus sucesores procesan registros, construyen índices de búsqueda, entrenan modelos y ejecutan análisis sobre petabytes, y son herramientas fundamentales de la ingeniería de datos y la ciencia de datos a gran escala.

History

Google introdujo MapReduce (2004) sobre el Google File System (2003) para indexar la web en clústeres de productos básicos, y el Hadoop de código abierto reimplementó ambos, popularizando el modelo. A principios de la década de 2010, los motores de flujo de datos en memoria construidos sobre la abstracción de conjuntos de datos distribuidos resilientes (2012) reemplazaron a MapReduce para análisis iterativos e interactivos, manteniendo sus ideas de tolerancia a fallos.

Key figures

• Jeffrey Dean
• Sanjay Ghemawat
• Matei Zaharia

Seminal works

• dean2008
• ghemawat2003
• zaharia2012

Frequently asked questions

¿Por qué MapReduce fue tan influyente a pesar de su simplicidad?

Su poder residía en lo que ocultaba. Al restringir el cálculo a funciones de mapeo y reducción, el marco podía particionar automáticamente los datos, programar el trabajo en miles de máquinas, recuperarse de fallos volviendo a ejecutar tareas y equilibrar la carga, permitiendo a los programadores procesar enormes conjuntos de datos sin escribir código de sistemas distribuidos.

¿Por qué los motores más nuevos reemplazaron a MapReduce para muchas tareas?

El MapReduce clásico escribe los resultados intermedios en el disco entre cada etapa, lo cual es lento para trabajos de varios pasos e iterativos como el aprendizaje automático. Los motores de flujo de datos en memoria mantienen los datos en memoria entre etapas y expresan grafos de cálculo más ricos, ofreciendo grandes aceleraciones mientras conservan la tolerancia a fallos basada en el linaje, por lo que se convirtieron en la opción preferida para muchas cargas de trabajo analíticas.