Hispanopedia Wiki
Articulo de referencia

MapReduce

MapReduce es un modelo de programación y una implementación asociada para procesar y generar grandes conjuntos de datos con un algoritmo paralelo y distribuido en un clúster . [...

Hispanopedia WikiContenido en espanolLectura gratuita

MapReduce es un modelo de programación y una implementación asociada para procesar y generar grandes conjuntos de datos con un algoritmo paralelo y distribuido en un clúster . [ 1 ] [ 2 ] [ 3 ]

Un programa MapReduce se compone de un procedimiento map , que realiza filtrado y ordenación (como ordenar a los estudiantes por nombre en colas, una cola para cada nombre), y un método reduce , que realiza una operación de resumen (como contar el número de estudiantes en cada cola, obteniendo así la frecuencia de los nombres). El "Sistema MapReduce" (también llamado "infraestructura" o "marco") orquesta el procesamiento mediante la organización de los servidores distribuidos, la ejecución de las distintas tareas en paralelo, la gestión de todas las comunicaciones y transferencias de datos entre las distintas partes del sistema, y ​​la provisión de redundancia y tolerancia a fallos .

El modelo es una especialización de la estrategia split-apply-combine para el análisis de datos. [ 4 ] Está inspirado en las funciones map y reduce comúnmente utilizadas en la programación funcional , [ 5 ] aunque su propósito en el marco MapReduce no es el mismo que en sus formas originales. [ 6 ] Las contribuciones clave del marco MapReduce no son las funciones map y reduce propiamente dichas (que, por ejemplo, se asemejan a las operaciones reduce [ 8 ] y scatter [ 9 ] del estándar Message Passing Interface de 1995 ) , sino la escalabilidad y la tolerancia a fallos logradas para una variedad de aplicaciones gracias a la paralelización. Por lo tanto, una implementación de MapReduce de un solo hilo generalmente no es más rápida que una implementación tradicional (no MapReduce); cualquier mejora generalmente solo se observa con implementaciones multihilo en hardware multiprocesador. [ 10 ] El uso de este modelo es beneficioso solo cuando entran en juego la operación de mezcla distribuida optimizada (que reduce el costo de comunicación de red) y las características de tolerancia a fallos del marco MapReduce. Optimizar el costo de comunicación es esencial para un buen algoritmo MapReduce. [ 11 ]

Las bibliotecas MapReduce se han escrito en muchos lenguajes de programación, con diferentes niveles de optimización. Una implementación popular de código abierto que admite mezclas distribuidas forma parte de Apache Hadoop . El nombre MapReduce se refería originalmente a la tecnología propietaria de Google , pero desde entonces se ha convertido en una marca comercial genérica . Para 2014, Google ya no utilizaba MapReduce como su modelo principal de procesamiento de big data , [ 12 ] y el desarrollo de Apache Mahout se había orientado hacia mecanismos más capaces y menos dependientes del disco que incorporaban capacidades completas de mapeo y reducción. [ 13 ]

Descripción general

MapReduce es un marco de trabajo para procesar problemas paralelizable en grandes conjuntos de datos utilizando un gran número de ordenadores (nodos), denominados colectivamente clúster (si todos los nodos se encuentran en la misma red local y utilizan hardware similar) o red (si los nodos se comparten entre sistemas distribuidos geográfica y administrativamente, y utilizan hardware más heterogéneo). El procesamiento puede realizarse sobre datos almacenados en un sistema de archivos (no estructurados) o en una base de datos (estructurados). MapReduce aprovecha la proximidad de los datos, procesándolos cerca de donde se almacenan para minimizar la sobrecarga de comunicación.

Un marco (o sistema) MapReduce generalmente se compone de tres operaciones (o pasos):

  1. Mapa: cada nodo trabajador aplica la mapfunción a los datos locales y escribe el resultado en un almacenamiento temporal. Un nodo maestro garantiza que solo se procese una copia de los datos de entrada redundantes.
  2. Mezcla: los nodos de trabajo redistribuyen los datos en función de las claves de salida (producidas por la mapfunción), de manera que todos los datos pertenecientes a una clave se encuentren en el mismo nodo de trabajo.
  3. Reducción: ahora los nodos de trabajo procesan cada grupo de datos de salida, por clave, en paralelo.

MapReduce permite el procesamiento distribuido de las operaciones de mapeo y reducción. Los mapeos se pueden realizar en paralelo, siempre que cada operación de mapeo sea independiente de las demás; en la práctica, esto está limitado por el número de fuentes de datos independientes y/o el número de CPU cerca de cada fuente. De manera similar, un conjunto de "reductores" puede realizar la fase de reducción, siempre que todas las salidas de la operación de mapeo que comparten la misma clave se presenten al mismo reductor al mismo tiempo, o que la función de reducción sea asociativa . Si bien este proceso a menudo parece ineficiente en comparación con algoritmos más secuenciales (porque se deben ejecutar múltiples instancias del proceso de reducción), MapReduce se puede aplicar a conjuntos de datos significativamente más grandes de lo que un solo servidor "estándar" puede manejar : una gran granja de servidores puede usar MapReduce para ordenar un petabyte de datos en solo unas pocas horas. [ 14 ] El paralelismo también ofrece cierta posibilidad de recuperarse de fallas parciales de servidores o almacenamiento durante la operación: si un mapeador o reductor falla, el trabajo se puede reprogramar , siempre que los datos de entrada aún estén disponibles.  

Otra forma de ver MapReduce es como un cálculo paralelo y distribuido de 5 pasos:

  1. Prepare la entrada de Map() : el "sistema MapReduce" designa los procesadores Map, asigna la clave de entrada K1 con la que trabajará cada procesador y proporciona a ese procesador todos los datos de entrada asociados a esa clave.
  2. Ejecutar el código Map() proporcionado por el usuario: Map() se ejecuta exactamente una vez para cada clave K1 , generando una salida organizada por clave K2 .
  3. "Mezcla" la salida del Map a los procesadores Reduce : el sistema MapReduce designa los procesadores Reduce, asigna la clave K2 con la que debe trabajar cada procesador y proporciona a ese procesador todos los datos generados por el Map asociados a esa clave.
  4. Ejecutar el código Reduce() proporcionado por el usuario : Reduce() se ejecuta exactamente una vez por cada clave K2 producida por el paso Map.
  5. Generar el resultado final : el sistema MapReduce recopila toda la salida de Reduce y la ordena por K2 para producir el resultado final.

Estos cinco pasos pueden considerarse lógicamente como una secuencia lógica, donde cada paso comienza solo después de que se haya completado el anterior; aunque en la práctica pueden intercalarse siempre que el resultado final no se vea afectado.

En muchas situaciones, los datos de entrada podrían estar ya distribuidos ( "fragmentados" ) entre varios servidores, en cuyo caso el paso 1 podría simplificarse enormemente asignando servidores Map que procesen los datos de entrada presentes localmente. Del mismo modo, el paso 3 podría acelerarse asignando procesadores Reduce que estén lo más cerca posible de los datos generados por Map que necesitan procesar.

Visión lógica

Las funciones Map y Reduce de MapReduce se definen con respecto a datos estructurados en pares (clave, valor). Map toma un par de datos con un tipo en un dominio de datos y devuelve una lista de pares en un dominio diferente:

Map(k1,v1)→list(k2,v2)

La función Map se aplica en paralelo a cada par (identificado por k1) en el conjunto de datos de entrada. Esto produce una lista de pares (identificados por k2) para cada llamada. Después, el marco de trabajo MapReduce recopila todos los pares con la misma clave ( k2) de todas las listas y los agrupa, creando un grupo para cada clave.

A continuación, se aplica la función Reduce en paralelo a cada grupo, lo que a su vez produce una colección de valores en el mismo dominio:

Reduce(k2, list (v2))→ list((k3, v3))[ 15 ]

Cada llamada a Reduce suele generar un par clave-valor o un valor vacío, aunque una misma llamada puede devolver más de un par clave-valor. Los resultados de todas las llamadas se recopilan para formar la lista de resultados deseada.

Así, el marco de trabajo MapReduce transforma una lista de pares (clave, valor) en otra lista de pares (clave, valor). [ 16 ] Este comportamiento es diferente de la combinación típica de programación funcional map y reduce, que acepta una lista de valores arbitrarios y devuelve un único valor que combina todos los valores devueltos por map.

Es necesario, pero no suficiente, contar con implementaciones de las abstracciones map y reduce para implementar MapReduce. Las implementaciones distribuidas de MapReduce requieren un medio para conectar los procesos que realizan las fases Map y Reduce. Esto puede ser un sistema de archivos distribuido . Existen otras opciones, como la transmisión directa de datos desde los mappers a los reducers, o que los procesadores de mapeo proporcionen sus resultados a los reducers que los consultan.

Ejemplos

El ejemplo canónico de MapReduce cuenta la aparición de cada palabra en un conjunto de documentos: [ 17 ]

función map (String nombre, String documento): // nombre: nombre del documento // documento: contenido del documento para cada palabra w en documento: emitir (w, 1) función reduce (String word, Iterator partialCounts): // word: una palabra // partialCounts: una lista de recuentos parciales agregados suma = 0 para cada pc en partialCounts: suma += pc emitir (palabra, suma)

Aquí, cada documento se divide en palabras, y cada palabra se cuenta mediante la función `map` , utilizando la palabra como clave del resultado. El marco de trabajo agrupa todos los pares con la misma clave y los pasa a la misma llamada para reducir . Por lo tanto, esta función solo necesita sumar todos sus valores de entrada para encontrar el total de apariciones de esa palabra.

Como otro ejemplo, imaginemos que para una base de datos de 1.100 millones de personas, se desea calcular el número promedio de contactos sociales que tiene una persona según su edad. En SQL , dicha consulta podría expresarse como:

SELECCIONAR edad , PROMEDIO ( contactos ) DE social.persona AGRUPAR POR edad ORDENAR POR edad​​

Utilizando MapReduce, los valores de la clave K1 podrían ser los números enteros del 1 al 1100, cada uno representando un lote de 1 millón de registros, el valor de la clave K2 podría ser la edad de una persona en años, y este cálculo podría lograrse utilizando las siguientes funciones:

La función Map recibe como entrada un entero K1 entre 1 y 1100, que representa un lote de 1 millón de registros de social.person. Para cada registro de social.person en el lote K1, haga lo siguiente: sea Y la edad de la persona, sea N el número de contactos que tiene la persona, produzca un registro de salida (Y, (N, 1)). Repita el proceso.La función Reduce es entrada: edad (en años) Y para cada registro de entrada (Y,(N,C)) hacer Acumula en S la suma de N*C Acumula en C nuevo la suma de C repite sea A sea S/C nuevo produce un registro de salida (Y,(A,C nuevo )) fin función

Tenga en cuenta que en la función Reduce , C es el número de personas que tienen un total de N contactos, por lo que en la función Map es natural escribir C=1 , ya que cada par de salida se refiere a los contactos de una sola persona.

El sistema MapReduce alinearía los 1100 procesadores Map y proporcionaría a cada uno su correspondiente millón de registros de entrada. El paso Map produciría 1.100 millones de registros (Y,(N,1)) , con valores de Y que oscilan entre, por ejemplo, 8 y 103. A continuación, el sistema MapReduce alinearía los 96 procesadores Reduce realizando una operación de mezcla de los pares clave/valor debido a que necesitamos un promedio por edad, y proporcionaría a cada uno sus millones de registros de entrada correspondientes. El paso Reduce daría como resultado un conjunto mucho más reducido de solo 96 registros de salida (Y,A) , que se colocarían en el archivo de resultados final, ordenados por Y.

La información de recuento en el registro es importante si el procesamiento se reduce más de una vez. Si no añadimos el recuento de los registros, el promedio calculado sería incorrecto, por ejemplo:

-- Salida del mapa n.° 1: edad, cantidad de contactos 10, 9 10, 9 10, 9
-- Salida del mapa n.° 2: edad, cantidad de contactos 10, 9 10, 9
-- Salida del mapa #3: edad, cantidad de contactos 10, 10

Si reducimos los archivos n.° 1 y n.° 2 , tendremos un nuevo archivo con un promedio de 9 contactos para una persona de 10 años ((9+9+9+9+9)/5):

-- reducir paso #1: edad, promedio de contactos 10, 9

Si lo reducimos con el archivo n.° 3 , perdemos la cuenta de cuántos registros ya hemos visto, por lo que terminamos con un promedio de 9,5 contactos para una persona de 10 años ((9+10)/2), lo cual es incorrecto. La respuesta correcta es 9,1 66 = 55 / 6 = (9×3+9×2+10×1)/(3+2+1).

Flujo de datos

La arquitectura del marco de software se adhiere al principio abierto-cerrado, donde el código se divide efectivamente en puntos congelados inmodificables y puntos calientes extensibles . El punto congelado del marco MapReduce es una gran ordenación distribuida. Los puntos calientes, que define la aplicación, son:

  • un lector de entrada
  • una función Map
  • una función de partición
  • una función de comparación
  • una función Reducir
  • un escritor de producción

lector de entrada

El lector de entrada divide la entrada en segmentos del tamaño adecuado (en la práctica, normalmente de 64  MB a 128  MB) y el sistema asigna un segmento a cada función Map . El lector de entrada lee los datos de un almacenamiento permanente (normalmente, un sistema de archivos distribuido ) y genera pares clave/valor.

Un ejemplo común consiste en leer un directorio lleno de archivos de texto y devolver cada línea como un registro.

Función de mapeo

La función Map toma una serie de pares clave/valor, procesa cada uno y genera cero o más pares clave/valor de salida. Los tipos de entrada y salida del mapa pueden ser (y a menudo lo son) diferentes entre sí.

Si la aplicación realiza un conteo de palabras, la función map dividirá la línea en palabras y generará un par clave/valor para cada palabra. Cada par de salida contendrá la palabra como clave y el número de veces que aparece esa palabra en la línea como valor.

Función de partición

Cada salida de la función Map se asigna a un reductor específico mediante la función de partición de la aplicación para fines de fragmentación . A la función de partición se le proporciona la clave y el número de reductores, y devuelve el índice del reductor deseado .

Por defecto, lo habitual es aplicar una función hash a la clave y usar el valor hash módulo el número de reductores . Es importante elegir una función de partición que proporcione una distribución de datos aproximadamente uniforme por fragmento para fines de equilibrio de carga ; de lo contrario, la operación MapReduce puede retrasarse esperando a que finalicen los reductores lentos (es decir, los reductores a los que se les asignaron las mayores porciones de los datos particionados de forma no uniforme).

Entre las etapas de mapeo y reducción, los datos se reorganizan (se ordenan en paralelo y se intercambian entre nodos) para trasladarlos del nodo de mapeo que los generó al fragmento donde se reducirán. Esta reorganización puede tardar más que el tiempo de cálculo, dependiendo del ancho de banda de la red, la velocidad de la CPU, la cantidad de datos generados y el tiempo que tardan los cálculos de mapeo y reducción.

Función de comparación

Los datos de entrada para cada Reduce se obtienen de la máquina donde se ejecutó el Map y se ordenan utilizando la función de comparación de la aplicación .

Reducir función

El marco de trabajo llama a la función Reduce de la aplicación una vez por cada clave única en el orden ordenado. La función Reduce puede iterar a través de los valores asociados a esa clave y producir cero o más resultados.

En el ejemplo de conteo de palabras, la función Reduce toma los valores de entrada, los suma y genera una única salida que contiene la palabra y la suma final.

escritor de salida

El escritor de salida escribe la salida de la función Reduce en el almacenamiento permanente.

Fundamentos teóricos

Las propiedades de los monoides son la base para garantizar la validez de las operaciones MapReduce. [ 18 ] [ 19 ]

En el paquete Algebird [ 20 ] una implementación de Map/Reduce en Scala requiere explícitamente un tipo de clase monoide. [ 21 ]

Las operaciones de MapReduce manejan dos tipos: el tipo A de datos de entrada que se mapean y el tipo B de datos de salida que se reducen.

La operación Map toma valores individuales de tipo A y produce, para cada a:A un valor b:B ; la operación Reduce requiere una operación binaria • definida en valores de tipo B ; consiste en plegar todos los b:B disponibles a un solo valor.

Desde el punto de vista de los requisitos básicos, cualquier operación MapReduce debe implicar la capacidad de reagrupar arbitrariamente los datos que se están reduciendo. Este requisito equivale a dos propiedades de la operación:

  • Asociatividad: ( x • y ) • z = x • ( y • z )
  • existencia de un elemento neutro e tal que e • x = x • e = x para todo x:B .

La segunda propiedad garantiza que, al paralelizarse en varios nodos, los nodos que no tengan datos que procesar no tendrán ningún impacto en el resultado.

Estas dos propiedades equivalen a tener un monoide ( B , •, e ) sobre valores de tipo B con operación • y con elemento neutro e .

No hay requisitos sobre los valores de tipo A ; se puede usar una función arbitraria A → B para la operación Map . Esto significa que tenemos un catamorfismo A* → ( B , •, e ). Aquí A* denota una estrella de Kleene , también conocida como el tipo de listas sobre A.

La operación Shuffle en sí misma no está relacionada con la esencia de MapReduce; es necesaria para distribuir los cálculos en la nube.

De lo anterior se deduce que no todas las operaciones Reduce binarias funcionarán en MapReduce. Aquí están los contraejemplos:

  • Construcción de un árbol a partir de subárboles: esta operación no es asociativa y el resultado dependerá de la agrupación;
  • Cálculo directo de promedios: avg tampoco es asociativo (y no tiene elemento neutro); para calcular un promedio, es necesario calcular momentos .

Consideraciones de rendimiento

Los programas MapReduce no tienen garantizada la velocidad. La principal ventaja de este modelo de programación es aprovechar la operación de mezcla optimizada de la plataforma, teniendo que escribir únicamente las partes Map y Reduce del programa. Sin embargo, en la práctica, el autor de un programa MapReduce debe tener en cuenta el paso de mezcla; en particular, la función de partición y la cantidad de datos escritos por la función Map pueden tener un gran impacto en el rendimiento y la escalabilidad. Módulos adicionales, como la función Combiner , pueden ayudar a reducir la cantidad de datos escritos en disco y transmitidos por la red. Las aplicaciones MapReduce pueden lograr aceleraciones sublineales en determinadas circunstancias. [ 22 ]

Al diseñar un algoritmo MapReduce, el autor debe elegir un buen equilibrio [ 11 ] entre los costos de computación y de comunicación. El costo de comunicación suele predominar sobre el costo de computación, [ 11 ] [ 22 ] y muchas implementaciones de MapReduce están diseñadas para escribir toda la comunicación en almacenamiento distribuido para la recuperación ante fallos.

Para optimizar el rendimiento de MapReduce, es necesario considerar la complejidad del mapeo, la mezcla, la ordenación (agrupación por clave) y la reducción. La cantidad de datos producidos por los mappers es un parámetro clave que distribuye la mayor parte del costo computacional entre el mapeo y la reducción. La reducción incluye la ordenación (agrupación de las claves), cuya complejidad no es lineal. Por lo tanto, los tamaños de partición pequeños reducen el tiempo de ordenación, pero esto implica una compensación, ya que un gran número de reductores puede resultar poco práctico. La influencia del tamaño de la unidad de división es marginal (a menos que se elija de forma particularmente inadecuada, por ejemplo, <1 MB). Las ganancias derivadas de que algunos mappers lean la carga desde discos locales son, en promedio, mínimas. [ 23 ]

Para procesos que se completan rápidamente y donde los datos caben en la memoria principal de una sola máquina o un clúster pequeño, el uso de un marco de trabajo MapReduce generalmente no es efectivo. Dado que estos marcos de trabajo están diseñados para recuperarse de la pérdida de nodos completos durante el cálculo, escriben resultados intermedios en almacenamiento distribuido. Esta recuperación ante fallos es costosa y solo resulta rentable cuando el cálculo involucra muchas computadoras y un tiempo de ejecución prolongado. Una tarea que se completa en segundos puede reiniciarse simplemente en caso de error, y la probabilidad de que falle al menos una máquina aumenta rápidamente con el tamaño del clúster. En estos casos, las implementaciones que mantienen todos los datos en memoria y simplemente reinician el cálculo ante fallos de nodos o, cuando los datos son lo suficientemente pequeños, las soluciones no distribuidas, suelen ser más rápidas que un sistema MapReduce.

Distribución y fiabilidad

MapReduce logra confiabilidad al distribuir varias operaciones sobre el conjunto de datos a cada nodo de la red. Se espera que cada nodo informe periódicamente sobre el trabajo completado y las actualizaciones de estado. Si un nodo permanece inactivo durante más tiempo del indicado, el nodo maestro (similar al servidor maestro del sistema de archivos de Google ) lo registra como inactivo y envía el trabajo asignado a otros nodos. Las operaciones individuales utilizan operaciones atómicas para nombrar los archivos de salida, lo que garantiza que no haya hilos paralelos en conflicto. Al renombrar archivos, también es posible copiarlos con otro nombre además del nombre de la tarea (lo que permite efectos secundarios ).

Las operaciones de reducción funcionan de manera muy similar. Debido a sus propiedades inferiores en cuanto a operaciones paralelas, el nodo maestro intenta programar las operaciones de reducción en el mismo nodo o en el mismo rack que el nodo que contiene los datos que se están procesando. Esta característica es deseable, ya que conserva el ancho de banda en la red troncal del centro de datos.

Las implementaciones no son necesariamente altamente confiables. Por ejemplo, en versiones anteriores de Hadoop , el NameNode era un punto único de fallo para el sistema de archivos distribuido. Las versiones más recientes de Hadoop ofrecen alta disponibilidad con conmutación por error activa/pasiva para el NameNode.

Usos

MapReduce es útil en una amplia gama de aplicaciones, incluyendo búsqueda distribuida basada en patrones, ordenación distribuida, inversión de grafos de enlaces web, descomposición en valores singulares, [ 24 ] estadísticas de registros de acceso web, construcción de índices invertidos , agrupamiento de documentos , aprendizaje automático , [ 25 ] y traducción automática estadística . Además, el modelo MapReduce se ha adaptado a varios entornos de computación como sistemas multinúcleo y de muchos núcleos, [ 26 ] [ 27 ] [ 28 ] cuadrículas de escritorio, [ 29 ] clústeres múltiples, [ 30 ] entornos de computación de voluntarios, [ 31 ] entornos de nube dinámicos, [ 32 ] entornos móviles, [ 33 ] y entornos de computación de alto rendimiento. [ 34 ]

En Google, MapReduce se utilizó para regenerar completamente el índice de Google de la World Wide Web . Reemplazó los antiguos programas ad hoc que actualizaban el índice y ejecutaban los diversos análisis. [ 35 ] Desde entonces, el desarrollo en Google ha evolucionado hacia tecnologías como Percolator, FlumeJava [ 36 ] y MillWheel, que ofrecen operaciones y actualizaciones en tiempo real en lugar de procesamiento por lotes, para permitir la integración de resultados de búsqueda "en vivo" sin reconstruir el índice completo. [ 37 ]

Las entradas y salidas estables de MapReduce suelen almacenarse en un sistema de archivos distribuido . Los datos transitorios suelen almacenarse en el disco local y los reductores los recuperan de forma remota.

Crítica

Falta de novedad

David DeWitt y Michael Stonebraker , científicos informáticos especializados en bases de datos paralelas y arquitecturas sin recursos compartidos , han criticado la amplitud de problemas para los que se puede utilizar MapReduce. [ 38 ] Consideraron que su interfaz era demasiado básica y cuestionaron si realmente representaba el cambio de paradigma que sus defensores afirmaban. [ 39 ] Rebatieron las afirmaciones de novedad de los defensores de MapReduce, citando a Teradata como ejemplo de una técnica anterior que existía desde hace más de dos décadas. También compararon a los programadores de MapReduce con los de CODASYL , señalando que ambos "escriben en un lenguaje de bajo nivel y realizan manipulación de registros de bajo nivel". [ 39 ] El uso de archivos de entrada de MapReduce y la falta de soporte de esquema impiden las mejoras de rendimiento que permiten las características comunes de los sistemas de bases de datos, como los árboles B y el particionamiento hash , aunque proyectos como Pig (o PigLatin) , Sawzall , Apache Hive , [ 40 ] HBase [ 41 ] y Bigtable [ 41 ] [ 42 ] están abordando algunos de estos problemas.

Greg Jorgensen escribió un artículo rechazando estas opiniones. [ 43 ] Jorgensen afirma que todo el análisis de DeWitt y Stonebraker carece de fundamento, ya que MapReduce nunca fue diseñado ni pretendido para ser utilizado como una base de datos.

DeWitt y Stonebraker publicaron posteriormente en 2009 un estudio comparativo detallado que comparaba el rendimiento de los enfoques MapReduce y RDBMS de Hadoop en varios problemas específicos. [ 44 ] Concluyeron que las bases de datos relacionales ofrecen ventajas reales para muchos tipos de uso de datos, especialmente en el procesamiento complejo o cuando los datos se utilizan en toda la empresa, pero que MapReduce puede ser más fácil de adoptar para los usuarios en tareas de procesamiento simples o puntuales.

El paradigma de programación MapReduce también se describió en la tesis de Danny Hillis de 1985 [ 45 ] destinada a ser utilizada en la Connection Machine , donde se denominó "xapping/reduction" [ 46 ] y se basó en el hardware especial de esa máquina para acelerar tanto map como reduce. El dialecto finalmente utilizado para la Connection Machine, el StarLisp de 1986 , tenía paralelismo *mapy reduce!![ 47 ] que a su vez se basaba en el Common Lisp de 1984, que tenía paralelismo y no paralelismo incorporados. [ 48 ] El enfoque en forma de árbol que la arquitectura de hipercubo de la Connection Machine utiliza para ejecutar enmapreducereduceO(registro⁡norte){\displaystyle O(\log n)}El tiempo [ 49 ] es prácticamente el mismo que el enfoque mencionado en el artículo de Google como trabajo previo. [ 3 ] : 11

En 2010, Google obtuvo lo que se describe como una patente sobre MapReduce. La patente, presentada en 2004, podría cubrir el uso de MapReduce por software de código abierto como Hadoop , CouchDB y otros. En Ars Technica , un editor reconoció el papel de Google en la popularización del concepto de MapReduce, pero cuestionó la validez y la novedad de la patente. [ 50 ] [ 51 ] En 2013, como parte de su "Compromiso de No Afirmación de Patente Abierta (OPN)", Google se comprometió a utilizar la patente únicamente con fines defensivos. [ 52 ] [ 53 ] Se espera que la patente expire el 23 de diciembre de 2026. [ 54 ]

Marco de programación restringido

Las tareas de MapReduce deben escribirse como programas de flujo de datos acíclicos, es decir, un mapeador sin estado seguido de un reductor sin estado, que son ejecutados por un planificador de trabajos por lotes. Este paradigma dificulta la consulta repetida de conjuntos de datos e impone limitaciones que se perciben en campos como el procesamiento de grafos [ 55 ], donde los algoritmos iterativos que revisitan un único conjunto de trabajo varias veces son la norma, así como, en presencia de datos basados ​​en disco con alta latencia , incluso en el campo del aprendizaje automático , donde se requieren múltiples pasadas a través de los datos, aunque los algoritmos pueden tolerar el acceso serial a los datos en cada pasada. [ 56 ]

Véase también

Implementaciones de MapReduce

Referencias

  1. ↑ "Tutorial de MapReduce" . Apache Hadoop . Consultado el 3 de julio de 2019 .
  2. ↑ "Google pone de relieve el funcionamiento interno de sus centros de datos" . cnet.com . 30 de mayo de 2008. Archivado del original el 19 de octubre de 2013. Consultado el 31 de mayo de 2008 .
  3. 1 2 "MapReduce: Procesamiento de datos simplificado en grandes clústeres" (PDF) . googleusercontent.com .
  4. ↑ Wickham, Hadley (2011). "La estrategia de dividir, aplicar y combinar para el análisis de datos" . Journal of Statistical Software . 40 : 1–29 . doi : 10.18637/jss.v040.i01 .
  5. ↑ "Nuestra abstracción está inspirada en las primitivas map y reduce presentes en Lisp y muchos otros lenguajes funcionales." - "MapReduce: Procesamiento de datos simplificado en grandes clústeres" , por Jeffrey Dean y Sanjay Ghemawat; de Google Research
  6. ↑ Lämmel, R. (2008). "El modelo de programación MapReduce de Google : una revisión". Science of Computer Programming . 70 : 1–30 . doi : 10.1016/j.scico.2007.07.001 .
  7. ↑ http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/mpi2-report.htm Estándar MPI 2
  8. ↑ "MPI Reduce y Allreduce · Tutorial de MPI" . mpitutorial.com .
  9. ↑ "Realizando clasificación paralela con MPI · Tutorial de MPI" . mpitutorial.com .
  10. ↑ "MongoDB: Rendimiento pésimo de MapReduce" . Stack Overflow. 16 de octubre de 2010. La implementación de MapReduce en MongoDB aparentemente tiene poco que ver con map-reduce. Porque, según lo que he leído, es de un solo hilo, mientras que map-reduce está diseñado para usarse en paralelo en un clúster. ... MongoDB MapReduce es de un solo hilo en un solo servidor...
  11. 1 2 3 Ullman, JD (2012). "Diseño de buenos algoritmos MapReduce" . XRDS: Crossroads, la revista ACM para estudiantes . 19 : 30–34 . doi : 10.1145/2331042.2331053 . S2CID 26498063 . 
  12. ↑ Sverdlik, Yevgeniy (25-06-2014). "Google abandona MapReduce en favor de un nuevo sistema de análisis a hiperescala" . Data Center Knowledge . Recuperado el 25-10-2015 ."Ya no usamos MapReduce" [Urs Hölzle, vicepresidente sénior de infraestructura técnica de Google]
  13. ↑ "Por qué MapReduce sigue siendo un enfoque dominante para el aprendizaje automático a gran escala" . Analytics India . 5 de abril de 2019.
  14. ↑ Czajkowski, Grzegorz; Marián Dvorský; Jerry Zhao; Michael Conley (7 de septiembre de 2011). "Clasificación de petabytes con MapReduce: el próximo episodio" . Consultado el 7 de abril de 2014 .
  15. ↑ "Tutorial de MapReduce" .
  16. ↑ "Apache/Hadoop-mapreduce" . GitHub . 31 de agosto de 2021.
  17. ↑ "Ejemplo: Contar ocurrencias de palabras" . Google Research . Consultado el 18 de septiembre de 2013 .
  18. ↑ Fegaras, Leonidas (2017). "Un álgebra para el análisis distribuido de Big Data". Journal of Functional Programming . 28 e27. doi : 10.1017/S0956796817000193 . S2CID 44629767 . 
  19. ↑ Lin, Jimmy (29 de abril de 2013). "¡Monoidify! Monoides como principio de diseño para algoritmos MapReduce eficientes". arXiv : 1304.7544 [ cs.DC ].
  20. ↑ "Álgebra abstracta para Scala" .
  21. ↑ "Codificación de Map-Reduce como un monoide con plegado a la izquierda" . 5 de septiembre de 2016.
  22. 1 2 Senger, Hermes; Gil-Costa, Veronica; Arantes, Luciana; Marcondes, Cesar AC; Marín, Mauricio; Sato, Liria M.; da Silva, Fabrício AB (2015-01-01). "Análisis de costos y escalabilidad de BSP para operaciones MapReduce". Concurrency and Computation: Practice and Experience . 28 (8): 2503– 2527. doi : 10.1002/cpe.3628 . hdl : 10533/147670 . ISSN 1532-0634 . S2CID 33645927 .  
  23. ↑ Berlińska, Joanna; Drozdowski, Maciej (1 de diciembre de 2010). "Programación de cálculos de MapReduce divisibles". Revista de Computación Paralela y Distribuida . 71 (3): 450– 459. doi : 10.1016/j.jpdc.2010.12.004 .
  24. ↑ Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "Dimension Independent Matrix Square Using MapReduce" (PDF) . Universidad de Stanford . arXiv : 1304.1467 . Bibcode : 2013arXiv1304.1467B . Recuperado el 12 de julio de 2014 .
  25. ^ Ng, Andrés Y.; Bradski, Gary; Chu, Cheng-Tao; Olukotun, Kunle; Kim, Sang Kyun; Lin, Yi-An; Yu, YuanYuan (2006). "Map-Reduce para aprendizaje automático en multinúcleo" . NIPS 2006. Archivado desde el original el 20 de junio de 2010 . Consultado el 24 de noviembre de 2009 .
  26. ↑ Ranger, C.; Raghuraman, R.; Penmetsa, A.; Bradski, G.; Kozyrakis, C. (2007). "Evaluación de MapReduce para sistemas multinúcleo y multiprocesador". 2007 IEEE 13th International Symposium on High Performance Computer Architecture . p. 13. CiteSeerX 10.1.1.220.8210 . doi : 10.1109/HPCA.2007.346181 . ISBN   978-1-4244-0804-7. S2CID 12563671 . 
  27. ↑ He, B.; Fang, W.; Luo, Q.; Govindaraju, NK; Wang, T. (2008). "Mars: un marco MapReduce en procesadores gráficos" (PDF) . Actas de la 17.ª conferencia internacional sobre arquitecturas paralelas y técnicas de compilación – PACT '08 . p. 260. doi : 10.1145/1454115.1454152 . ISBN  9781605582825. S2CID 207169888 . 
  28. ↑ Chen, R.; Chen, H.; Zang, B. (2010). "Tiled-MapReduce: optimización del uso de recursos de aplicaciones de datos en paralelo en multinúcleo con segmentación". Actas de la 19.ª conferencia internacional sobre arquitecturas paralelas y técnicas de compilación – PACT '10 . p. 523. doi : 10.1145/1854273.1854337 . ISBN  9781450301787. S2CID 2082196 . 
  29. ↑ Tang, B.; Moca, M.; Chevalier, S.; He, H.; Fedak, G. (2010). "Hacia MapReduce para computación en malla de escritorio" (PDF) . Conferencia Internacional de 2010 sobre Computación P2P, Paralela, en Malla, en la Nube e Internet . pág. 193. CiteSeerX 10.1.1.671.2763 . doi : 10.1109/3PGCIC.2010.33 . ISBN   978-1-4244-8538-3. S2CID 15044391 . 
  30. ↑ Luo, Y.; Guo, Z.; Sun, Y.; Plale, B. ; Qiu, J.; Li, W. (2011). "Un marco jerárquico para la ejecución de MapReduce entre dominios" (PDF) . Actas del segundo taller internacional sobre métodos computacionales emergentes para las ciencias de la vida (ECMLS '11) . CiteSeerX 10.1.1.364.9898 . doi : 10.1145/1996023.1996026 . ISBN  978-1-4503-0702-4. S2CID 15179363 . 
  31. ↑ Lin, H.; Ma, X.; Archuleta, J.; Feng, WC; Gardner, M.; Zhang, Z. (2010). "MOON: MapReduce On Opportunistic eNvironments" (PDF) . Actas del 19.º Simposio Internacional ACM sobre Computación Distribuida de Alto Rendimiento – HPDC '10 . p. 95. doi : 10.1145/1851476.1851489 . ISBN  9781605589428. S2CID 2351790 . 
  32. ↑ Marozzo, F.; Talia, D.; Trunfio, P. (2012). "P2P-MapReduce: Procesamiento de datos en paralelo en entornos de nube dinámicos" . Journal of Computer and System Sciences . 78 (5): 1382– 1402. doi : 10.1016/j.jcss.2011.12.021 .
  33. ↑ Dou, A.; Kalogeraki, V.; Gunopulos, D.; Mielikainen, T.; Tuulos, VH (2010). "Misco: un marco MapReduce para sistemas móviles". Actas de la 3.ª Conferencia Internacional sobre Tecnologías Ubicuas Relacionadas con Entornos de Asistencia – PETRA '10 . p. 1. doi : 10.1145/1839294.1839332 . ISBN  9781450300711. S2CID 14517696 . 
  34. ↑ Wang, Yandong; Goldstone, Robin; Yu, Weikuan; Wang, Teng (mayo de 2014). "Caracterización y optimización de MapReduce residente en memoria en sistemas HPC". 2014 IEEE 28th International Parallel and Distributed Processing Symposium . IEEE. pp. 799–808 . doi : 10.1109/IPDPS.2014.87 . ISBN  978-1-4799-3800-1. S2CID 11157612 . 
  35. ↑ "Cómo funciona Google" . baselinemag.com. 7 de julio de 2006. En octubre, Google ejecutaba aproximadamente 3000 tareas de computación diarias mediante MapReduce, lo que representaba miles de días de máquina, según una presentación de Dean. Entre otras cosas, estas rutinas por lotes analizan las páginas web más recientes y actualizan los índices de Google.
  36. ↑ Chambers, Craig; Raniwala, Ashish; Perry, Frances; Adams, Stephen; Henry, Robert R.; Bradshaw, Robert; Weizenbaum, Nathan (1 de enero de 2010). «FlumeJava». Actas de la 31.ª Conferencia ACM SIGPLAN sobre Diseño e Implementación de Lenguajes de Programación (PDF) . págs. 363–375 . doi : 10.1145/1806596.1806638 . ISBN  9781450300193. S2CID 14888571 . Archivado del original (PDF) el 23 de septiembre de 2016 . Recuperado el 4 de agosto de 2016 . 
  37. ↑ Peng, D., & Dabek, F. (2010, octubre). Procesamiento incremental a gran escala mediante transacciones y notificaciones distribuidas. En OSDI (Vol. 10, pp. 1-15).
  38. ↑ "Los expertos en bases de datos se lanzan al ataque contra MapReduce" .
  39. 1 2 David DeWitt ; Michael Stonebraker . "MapReduce: Un gran paso atrás" . craig-henderson.blogspot.com . Consultado el 27 de agosto de 2008 .
  40. ↑ "Apache Hive – Índice de – Apache Software Foundation" .
  41. 1 2 "HBase – Página principal de HBase – Fundación de Software Apache" .
  42. ↑ "Bigtable: Un sistema de almacenamiento distribuido para datos estructurados" (PDF) .
  43. ↑ Greg Jorgensen . "Los expertos en bases de datos relacionales se lanzan al ataque contra MapReduce" . typicalprogrammer.com . Consultado el 11 de noviembre de 2009 .
  44. ↑ Pavlo, Andrew; Paulson, Erik; Rasin, Alexander; Abadi, Daniel J.; DeWitt, Deavid J.; Madden, Samuel; Stonebraker, Michael. "Una comparación de enfoques para el análisis de datos a gran escala" . Universidad de Brown . Consultado el 11 de enero de 2010 .
  45. ↑ Hillis, W. Danny (1986). The Connection Machine . MIT Press . ISBN 0262081571.
  46. ↑ "Resumen técnico del modelo de máquina de conexión CM-2" (PDF) . Thinking Machines Corporation . 1 de abril de 1987. Consultado el 21 de noviembre de 2022 .
  47. ↑ "Suplemento al *Manual de referencia de Lisp" (PDF) . Thinking Machines Corporation . 1988-09-01 . Consultado el 2022-11-21 .
  48. ↑ "Prospecto de la arquitectura Rediflow" (PDF) . Departamento de Ciencias de la Computación de la Universidad de Utah . 5 de abril de 1986. Consultado el 21 de noviembre de 2022 .
  49. ↑ Ranka, Sanjay (1989). "2.6 Suma de datos". Algoritmos de hipercubo para procesamiento de imágenes y reconocimiento de patrones (PDF) . Universidad de Florida . Recuperado el 8 de diciembre de 2022 .
  50. ↑ Paul, Ryan (20 de enero de 2010). "Patente MapReduce de Google: ¿qué significa para Hadoop?" . Ars Technica . Consultado el 21 de marzo de 2021 .
  51. ↑ "Patente de Estados Unidos: 7650331 - Sistema y método para el procesamiento eficiente de datos a gran escala" . uspto.gov . Archivado del original el 21 de septiembre de 2013. Consultado el 19 de enero de 2010 .
  52. ↑ Nazer, Daniel (28 de marzo de 2013). "Google se compromete abiertamente a no reclamar patentes y propone nuevos modelos de licencia" . Electronic Frontier Foundation . Consultado el 21 de marzo de 2021 .
  53. ↑ King, Rachel (2013). "Google amplía su compromiso de patentes abiertas a 79 más sobre gestión de centros de datos" . ZDNet . Recuperado el 21 de marzo de 2021 .
  54. ↑ "Sistema y método para el procesamiento eficiente de datos a gran escala" . Búsqueda de patentes de Google. 18 de junio de 2004. Consultado el 21 de marzo de 2021 .
  55. ↑ Gupta, Upa; Fegaras, Leonidas (6 de octubre de 2013). "Análisis de grafos basado en mapas en MapReduce" (PDF) . Actas: Conferencia Internacional IEEE de Big Data de 2013. Conferencia Internacional IEEE de Big Data de 2013. Santa Clara, California : IEEE . págs. 24–30 . 
  56. ↑ Zaharia, Matei; Chowdhury, Mosharaf; Franklin, Michael; Shenker, Scott; Stoica, Ion (junio de 2010). Spark: Computación en clúster con conjuntos de trabajo (PDF) . HotCloud 2010.
Lecturas relacionadas
6 articulos
Modelo de programaciónModelo de programaciónUn modelo de programación es un modelo de ejecución acoplado a una API o un patrón particular de código. En este estilo, en realidad hay dos modelo...Grandes datosGrandes datosEl término big data se refiere principalmente a conjuntos de datos que son demasiado grandes o complejos para ser tratados por un software de proce...Computación paralelaComputación paralelaLa computación paralela es un tipo de computación en el que muchos cálculos o procesos se llevan a cabo simultáneamente. [1] Los problemas grandes ...Computación distribuidaComputación distribuidaLa computación distribuida es un campo de la informática que estudia los sistemas distribuidos , definidos como sistemas informáticos cuyos compone...Clúster de ordenadoresClúster de ordenadoresUn clúster de computadoras es un conjunto de computadoras que trabajan juntas de modo que pueden considerarse como un solo sistema. A diferencia de...Función (programación informática)En programación informática , una función (también procedimiento , método , subrutina , rutina o subprograma ) es una unidad invocable [ 1 ] de lóg...