Mapa Reduce

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 de mapa , que realiza el filtrado y la clasificación (como la clasificación de los estudiantes por su nombre en colas, una cola para cada nombre), y un método de reducción , que realiza una operación de resumen (como contar el número de estudiantes en cada cola, lo que produce frecuencias de nombres). El "Sistema MapReduce" (también llamado "infraestructura" o "marco") organiza el procesamiento organizando los servidores distribuidos, ejecutando las distintas tareas en paralelo, administrando todas las comunicaciones y transferencias de datos entre las distintas partes del sistema y proporcionando redundancia y tolerancia a fallas .

El modelo es una especialización de la estrategia de dividir-aplicar-combinar para el análisis de datos. ^[4] Está inspirado en las funciones de mapa y reducción 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 de mapa y reducción reales (que, por ejemplo, se parecen a las operaciones de reducción ^{[8] y} dispersión [ ^9] del estándar Message Passing Interface de 1995 ), sino la escalabilidad y la tolerancia a fallas logradas para una variedad de aplicaciones debido a la paralelización. Como tal, una implementación de un solo subproceso de MapReduce generalmente no es más rápida que una implementación tradicional (no MapReduce); cualquier ganancia generalmente solo se ve con implementaciones de múltiples subprocesos 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 la red) y las características de tolerancia a fallas 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 tiene soporte para mezclas distribuidas es parte de Apache Hadoop . El nombre MapReduce originalmente se refería a la tecnología propietaria de Google , pero desde entonces se ha generalizado . Para 2014, Google ya no usaba MapReduce como su modelo principal de procesamiento de big data ^{, [12]} y el desarrollo en Apache Mahout había pasado a mecanismos más capaces y menos orientados al disco que incorporaban capacidades completas de mapeo y reducción. ^[13]

MapReduce es un marco para procesar problemas paralelizables en grandes conjuntos de datos utilizando una gran cantidad de computadoras (nodos), a los que se hace referencia colectivamente como un clúster (si todos los nodos están en la misma red local y usan hardware similar) o una cuadrícula (si los nodos se comparten en sistemas distribuidos geográfica y administrativamente y usan hardware más heterogéneo). El procesamiento puede ocurrir en datos almacenados en un sistema de archivos (no estructurados) o en una base de datos (estructurados). MapReduce puede aprovechar la ubicación de los datos, procesándolos cerca del lugar donde están almacenados para minimizar la sobrecarga de comunicación.

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

1. Mapa: cada nodo de trabajo aplica la mapfunción a los datos locales y escribe la salida en un almacenamiento temporal. Un nodo maestro garantiza que solo se procese una copia de los datos de entrada redundantes.
2. Mezclar: los nodos de trabajo redistribuyen los datos según las claves de salida (producidas por la mapfunción), de modo que todos los datos que pertenecen a una clave se encuentran en el mismo nodo de trabajo.
3. Reducir: los nodos de trabajo ahora 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 mapas 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 la cantidad de fuentes de datos independientes y/o la cantidad 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 que son 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 los que puede manejar un solo servidor "comercial" ; 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 recuperación ante fallas parciales de servidores o almacenamiento durante la operación: si un mapeador o reductor falla, el trabajo puede reprogramarse, suponiendo que los datos de entrada aún estén disponibles.

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

1. Preparar la entrada de Map() : el "sistema MapReduce" designa los procesadores de Map, asigna la tecla de entrada K1 en la que trabajaría cada procesador y proporciona a ese procesador todos los datos de entrada asociados con esa tecla.
2. Ejecute el código Map() proporcionado por el usuario : Map() se ejecuta exactamente una vez para cada tecla K1 , generando una salida organizada por clave K2 .
3. "Mezclar" la salida del mapa a los procesadores Reduce : el sistema MapReduce designa los procesadores Reduce, asigna la tecla K2 en la que debe trabajar cada procesador y proporciona a ese procesador todos los datos generados por el mapa asociados con esa tecla.
4. Ejecute el código Reduce() proporcionado por el usuario : Reduce() se ejecuta exactamente una vez por cada clave K2 producida por el paso Mapa.
5. Producir el resultado final : el sistema MapReduce recopila todo el resultado de Reduce y lo ordena por K2 para producir el resultado final.

Se puede pensar lógicamente que estos cinco pasos se ejecutan en secuencia (cada paso comienza sólo después de completar el paso anterior), aunque en la práctica se pueden intercalar siempre que no se afecte el resultado final.

En muchas situaciones, los datos de entrada pueden ya haber sido distribuidos ( "fragmentados" ) entre muchos servidores diferentes, en cuyo caso el paso 1 podría a veces simplificarse en gran medida asignando servidores de mapas que procesarían los datos de entrada presentes localmente. De manera similar, el paso 3 podría a veces acelerarse asignando procesadores de reducción que estén lo más cerca posible de los datos generados por mapas que necesitan procesar.

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 (clavedo por k1) en el conjunto de datos de entrada. Esto produce una lista de pares (clavedos por k2) para cada llamada. Después de eso, el marco MapReduce recopila todos los pares con la misma clave ( k2) de todas las listas y los agrupa, creando un grupo para cada clave.

Luego, la función Reducir se aplica 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 de Reduce normalmente produce un par de valores clave o un resultado vacío, aunque se permite que una llamada devuelva más de un par de valores clave. Los resultados de todas las llamadas se recopilan como la lista de resultados deseados.

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

Es necesario, pero no suficiente, tener implementaciones de las abstracciones de mapeo y reducción para implementar MapReduce. Las implementaciones distribuidas de MapReduce requieren un medio para conectar los procesos que realizan las fases de mapeo y reducción. Esto puede ser un sistema de archivos distribuido . Existen otras opciones posibles, como la transmisión directa de los mapeadores a los reductores, o que los procesadores de mapeo entreguen sus resultados a los reductores que los consultan.

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 el documento: emitir (w, 1)función  reduce (String palabra, Iterador partialCounts): // palabra: 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 la función map cuenta cada palabra , utilizando la palabra como clave de resultado. El marco reúne todos los pares con la misma clave y los envía a la misma llamada a reduce . Por lo tanto, esta función solo necesita sumar todos sus valores de entrada para encontrar la cantidad total de apariciones de esa palabra.

Como otro ejemplo, imaginemos que, para una base de datos de 1100 millones de personas, se quisiera calcular la cantidad promedio de contactos sociales que tiene una persona según su edad. En SQL , esta consulta se podría expresar de la siguiente manera:

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

Usando 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 usando las siguientes funciones:

función Mapa es  entrada:  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 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)) repetir fin de funciónLa función Reducir es  la entrada: edad (en años) Y para cada registro de entrada (Y,(N,C) ) Acumula en S la suma de N*C Acumular en C nuevo la suma de C repetir  sea A S/C nuevo  producir un registro de salida (Y,(A,C nuevo )) fin de función

Tenga en cuenta que en la función Reducir , C es el recuento de personas que tienen en total N contactos, por lo que en la función Mapa 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 de ellos su correspondiente millón de registros de entrada. El paso Map produciría 1100 millones de registros (Y,(N,1)) , con valores Y que oscilarían entre, digamos, 8 y 103. El sistema MapReduce alinearía entonces los 96 procesadores Reduce realizando una operación de mezcla de los pares clave/valor debido al hecho de que necesitamos un promedio por edad, y proporcionaría a cada uno de ellos sus millones de registros de entrada correspondientes. El paso Reduce daría como resultado un conjunto muy 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 agregamos el recuento de registros, el promedio calculado sería incorrecto, por ejemplo:

-- mapa de salida n.° 1: edad, cantidad de contactos10, 910, 910, 9

-- Salida del mapa n.° 2: edad, cantidad de contactos10, 910, 9

-- Salida del mapa n.° 3: edad, cantidad de contactos10, 10

Si reducimos los archivos #1 y #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 contactos10, 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).

La arquitectura del marco de trabajo del software se adhiere al principio abierto-cerrado , en el que el código se divide de manera efectiva en puntos congelados no modificables y puntos activos extensibles . El punto congelado del marco de trabajo de MapReduce es una clasificación distribuida de gran tamaño. Los puntos activos, que define la aplicación, son:

• un lector de entrada
• una función de mapa
• una función de partición
• una función de comparación
• una función de reducción
• un escritor de salida

El lector de entrada divide la entrada en "splits" de tamaño apropiado (en la práctica, normalmente, de 64 MB a 128 MB) y el marco asigna un split a cada función de Map . El lector de entrada lee datos de un almacenamiento estable (normalmente, un sistema de archivos distribuido ) y genera pares clave/valor.

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

La función Map toma una serie de pares clave/valor, procesa cada uno de ellos 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 está realizando un recuento de palabras, la función de mapa dividiría la línea en palabras y generaría un par clave/valor para cada palabra. Cada par de salida contendría la palabra como clave y la cantidad de instancias de esa palabra en la línea como valor.

La función de partición de la aplicación asigna cada salida de la función Map a un reductor en particular para fines de fragmentación . La función de partición recibe la clave y la cantidad de reductores y devuelve el índice del reductor deseado .

Un valor predeterminado típico es aplicar un hash a la clave y utilizar el módulo del valor hash en la cantidad de reductores . Es importante elegir una función de partición que proporcione una distribución aproximadamente uniforme de los datos por fragmento para fines de equilibrio de carga ; de lo contrario, la operación de MapReduce puede demorarse mientras se espera que finalicen los reductores lentos (es decir, los reductores a los que se les asignaron las porciones más grandes de los datos particionados de manera no uniforme).

Entre las etapas de mapeo y reducción, los datos se mezclan (se ordenan en paralelo o se intercambian entre nodos) para moverlos desde el nodo de mapeo que los produjo hasta el fragmento en el que se reducirán. La mezcla a veces puede demorar más que el tiempo de cálculo, según el ancho de banda de la red, las velocidades de la CPU, los datos producidos y el tiempo que tardan los cálculos de mapeo y reducción.

La entrada para cada reducción se extrae de la máquina donde se ejecutó el mapa y se ordena utilizando la función de comparación de la aplicación .

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

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

El escritor de salida escribe la salida de Reduce en el almacenamiento estable.

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

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

Las operaciones de MapReduce tratan con dos tipos: el tipo A de datos de entrada que se están mapeando y el tipo B de datos de salida que se están reduciendo.

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

Desde el punto de vista de los requisitos básicos, cualquier operación de MapReduce debe implicar la capacidad de reagrupar arbitrariamente los datos que se están reduciendo. Este requisito se traduce en 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, cuando se paraleliza en múltiples nodos, los nodos que no tienen datos para procesar no tendrán impacto en el resultado.

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

No hay requisitos sobre los valores del tipo A ; se puede utilizar 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í no está relacionada con la esencia de MapReduce; es necesaria para distribuir los cálculos en la nube.

De lo anterior se desprende que no todas las operaciones de reducción binarias funcionarán en MapReduce. A continuación se muestran los contraejemplos:

• construir 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 ningún elemento neutro); para calcular un promedio, es necesario calcular momentos .

No se garantiza que los programas MapReduce sean rápidos. El principal beneficio de este modelo de programación es aprovechar la operación de mezcla optimizada de la plataforma y tener que escribir únicamente las partes Map y Reduce del programa. En la práctica, sin embargo, el autor de un programa MapReduce tiene que 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. Los módulos adicionales, como la función Combiner, pueden ayudar a reducir la cantidad de datos escritos en el disco y transmitidos a través de la red. Las aplicaciones MapReduce pueden lograr aceleraciones sublineales en circunstancias específicas. ^[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 a menudo domina el costo de computación, ^{[11] [22]} y muchas implementaciones de MapReduce están diseñadas para escribir toda la comunicación en un almacenamiento distribuido para la recuperación ante fallas.

Al ajustar el rendimiento de MapReduce, se debe tener en cuenta la complejidad de mapeo, mezcla, ordenación (agrupación por clave) y reducción. La cantidad de datos producidos por los mapeadores es un parámetro clave que desplaza 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), que tiene una complejidad no lineal. Por lo tanto, los tamaños de partición pequeños reducen el tiempo de ordenación, pero existe una desventaja porque tener una gran cantidad de reductores puede resultar poco práctico. La influencia del tamaño de la unidad dividida es marginal (a menos que se elija particularmente mal, digamos <1 MB). Las ganancias de que algunos mapeadores lean la carga de los discos locales, en promedio, son menores. ^[23]

En el caso de los procesos que se completan rápidamente y en los que los datos caben en la memoria principal de una sola máquina o de un pequeño clúster, el uso de un marco MapReduce no suele ser eficaz. Dado que estos marcos están diseñados para recuperarse de la pérdida de nodos completos durante el cálculo, escriben los resultados provisionales en un almacenamiento distribuido. Esta recuperación de fallos es costosa y solo es rentable cuando el cálculo implica muchas computadoras y un tiempo de ejecución prolongado. Una tarea que se completa en segundos se puede reiniciar 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 este tipo de problemas, las implementaciones que mantienen todos los datos en la memoria y simplemente reinician un cálculo en caso de 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.

MapReduce logra confiabilidad al distribuir una cantidad de operaciones en el conjunto de datos a cada nodo de la red. Se espera que cada nodo informe periódicamente con el trabajo completado y actualizaciones de estado. Si un nodo permanece en silencio durante un intervalo más largo que ese, el nodo maestro (similar al servidor maestro en el Sistema de archivos de Google ) registra el nodo como inactivo y envía el trabajo asignado al nodo a otros nodos. Las operaciones individuales utilizan operaciones atómicas para nombrar las salidas de los archivos como una verificación para garantizar que no haya subprocesos conflictivos en paralelo ejecutándose. Cuando se renombran los 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 forma muy similar. Debido a sus propiedades inferiores con respecto a las operaciones paralelas, el nodo maestro intenta programar operaciones de reducción en el mismo nodo o en el mismo bastidor que el nodo que contiene los datos en los que se está operando. Esta propiedad es conveniente, ya que conserva el ancho de banda en la red troncal del centro de datos.

Las implementaciones no son necesariamente muy confiables. Por ejemplo, en versiones anteriores de Hadoop , el NameNode era un único punto de falla para el sistema de archivos distribuido. Las versiones posteriores de Hadoop tienen alta disponibilidad con conmutación por error activa/pasiva para el "NameNode".

MapReduce es útil en una amplia gama de aplicaciones, incluyendo búsquedas distribuidas basadas en patrones, ordenamiento distribuido, inversión de enlaces web-gráficos, 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 informáticos como sistemas multinúcleo y de muchos núcleos, ^{[26] [27] [28]} cuadrículas de escritorio, ^[29] multiclúster, ^[30] entornos informáticos voluntarios, ^[31] entornos de nube dinámicos, ^[32] entornos móviles, ^[33] y entornos informáticos de alto rendimiento. ^[34]

En Google, MapReduce se utilizó para regenerar por completo el índice de Google de la World Wide Web . Reemplazó a los antiguos programas ad hoc que actualizaban el índice y ejecutaban los diversos análisis. ^[35] Desde entonces, el desarrollo en Google ha pasado a 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 un disco local y los reductores los obtienen de forma remota.

David DeWitt y Michael Stonebraker , científicos informáticos especializados en bases de datos paralelas y arquitecturas de nada compartido , han criticado la amplitud de los problemas para los que se puede utilizar MapReduce. ^[38] Llamaron a su interfaz demasiado de bajo nivel y cuestionaron si realmente representa el cambio de paradigma que sus defensores han afirmado que es. ^[39] Cuestionaron las afirmaciones de novedad de los defensores de MapReduce, citando a Teradata como un ejemplo de técnica anterior que ha existido durante más de dos décadas. También compararon a los programadores de MapReduce con los programadores de CODASYL , señalando que ambos están "escribiendo en un lenguaje de bajo nivel que realiza una manipulación de registros de bajo nivel". ^[39] El uso de archivos de entrada de MapReduce y la falta de soporte de esquemas impiden las mejoras de rendimiento habilitadas por las características comunes del sistema 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 estos puntos de vista. ^[43] Jorgensen afirma que todo el análisis de DeWitt y Stonebraker carece de fundamento ya que MapReduce nunca fue diseñado ni pensado para ser utilizado como base de datos.

En 2009, DeWitt y Stonebraker publicaron 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 una empresa, pero que MapReduce puede ser más fácil de adoptar para los usuarios para tareas de procesamiento simples o de una sola vez.

El paradigma de programación MapReduce también se describió en la tesis de Danny Hillis de 1985 ^[45] destinada a su uso en la Connection Machine , donde se lo llamó "xapping/reduction" ^[46] y dependía del hardware especial de esa máquina para acelerar tanto el mapa como la reducción. El dialecto que se utilizó finalmente para la Connection Machine, el StarLisp de 1986 , tenía *mapy paralelos reduce!!, ^[47] que a su vez se basaba en el Common Lispmap de 1984, que tenía y no paralelos reduceintegrados. ^[48] El enfoque en forma de árbol que utiliza la arquitectura de hipercubo de la Connection Machine para ejecutarse reduceen el tiempo ^[49] es efectivamente el mismo que el enfoque al que se hace referencia en el artículo de Google como trabajo previo. ^{[3] :  11}${\displaystyle O(\log n)}$

En 2010, Google obtuvo lo que se describe como una patente sobre MapReduce. La patente, presentada en 2004, puede 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ó si la patente era válida o novedosa. ^{[50] [51]} En 2013, como parte de su "Promesa de no aserción de patente abierta (OPN)", Google se comprometió a utilizar la patente solo de manera defensiva. ^{[52] [53]} Se espera que la patente expire el 23 de diciembre de 2026. ^[54]

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 se ejecutan mediante un programador de trabajos por lotes. Este paradigma dificulta la consulta repetida de conjuntos de datos e impone limitaciones que se sienten en campos como el procesamiento de gráficos ^[55] donde los algoritmos iterativos que revisan un solo conjunto de trabajo varias veces son la norma, así como, en presencia de datos basados ​​en disco con alta latencia , incluso el campo del aprendizaje automático donde se requieren múltiples pasadas a través de los datos a pesar de que los algoritmos pueden tolerar el acceso en serie a los datos en cada pasada. ^[56]

• Formalismo de Bird-Meertens
• Contrato de paralelización

• Base de datos Apache CouchDB
• Apache Hadoop
• Infinitamente
• Riak

Wikimedia Commons tiene medios relacionados con MapReduce .