Google publicó tres artículos influyentes entre 2003 y 2006: GFS de SOSP en 2003, MapReduce de OSDI en 2004 y BigTable de OSDI en 2006. SOSP y OSDI son conferencias importantes en el campo de los sistemas operativos y pertenecen a la Categoría A entre las conferencias recomendadas de la Computer Society. SOSP se lleva a cabo en años impares, mientras que OSDI se lleva a cabo en años pares.
Entonces este blog presentará MapReduce.
1.¿Qué hace MapReduce?
Como no puedo encontrar el diagrama esquemático de Google, quiero tomar prestado un diagrama de estructura de un proyecto de Hadoop para ilustrar la ubicación de MapReduce, como se muestra a continuación.
Hadoop es en realidad la implementación de código abierto de Google Sambo. Hadoop MapReduce corresponde a Google MapReduce, HBase corresponde a BigTable y HDFS corresponde a GFS. HDFS (o GFS) proporciona servicios de almacenamiento no estructurados eficientes para la capa superior, HBase (o BigTable) es una base de datos distribuida que proporciona servicios de datos estructurados y Hadoop MapReduce (o Google MapReduce) es un modelo de programación informática paralela para la programación de trabajos.
GFS y BigTable nos han proporcionado servicios de alto rendimiento y alta concurrencia, pero la programación paralela no está disponible para todos los programadores. Si nuestra aplicación no puede ser concurrente, entonces GFS y BigTable no tienen sentido. Lo mejor de MapReduce es que los programadores que no están familiarizados con la programación paralela también pueden aprovechar al máximo el poder de los sistemas distribuidos.
En pocas palabras, MapReduce es un marco que divide un trabajo grande en varios trabajos pequeños (los trabajos grandes y los trabajos pequeños deben ser esencialmente iguales, solo que tienen una escala diferente). Todo lo que el usuario debe hacer es decidir en cuántas partes dividir y definir el trabajo en sí.
A continuación se muestra un ejemplo a lo largo del artículo para explicar cómo funciona MapReduce.
2. Ejemplo: frecuencia estadística de palabras
Si quiero contar las palabras más comunes en artículos de computadora en los últimos 10 años y ver qué están estudiando todos, luego de recopilar las papeles que debo ¿Cómo hacerlo?
Método 1: Puedo escribir un pequeño programa para revisar todos los exámenes en orden, contar el número de veces que aparece cada palabra y finalmente saber qué palabras son las más populares.
Este método es muy efectivo cuando el conjunto de datos es pequeño, además es el más sencillo de implementar y es adecuado para solucionar este problema.
Método 2: escriba un programa multiproceso para recorrer el papel al mismo tiempo.
En teoría, este problema puede ser altamente concurrente, ya que las estadísticas de un archivo no afectarán las estadísticas de otro archivo. Cuando nuestra máquina es multinúcleo o multiprocesador, el método 2 es definitivamente más eficiente que el método 1. Pero escribir programas multiproceso es mucho más difícil que el primer método. Tenemos que sincronizar los datos nosotros mismos, por ejemplo, para evitar que dos hilos dupliquen archivos de estadísticas.
Método 3: Envía el trabajo a varias computadoras para que lo completen.
Podemos utilizar el primer método para implementar el programa en n máquinas, luego dividir la colección en n partes y ejecutar un trabajo en cada máquina. Este método se ejecuta lo suficientemente rápido, pero su implementación es complicada. Tenemos que copiar manualmente el programa a otras máquinas y separar manualmente los artículos cortos. Lo más doloroso es integrar los N resultados en ejecución (por supuesto, también podemos escribir otro programa).
Método 4: ¡Deja que MapReduce nos ayude!
MapReduce es esencialmente el tercer método, pero el marco define cómo dividir el conjunto de archivos, cómo copiar el programa y cómo integrar los resultados. Sólo necesitamos definir esta tarea (programa de usuario) y dejar el resto a MapReduce.
Antes de presentar el principio de funcionamiento de mapreduce, hablemos de las dos funciones principales de Map y reduce, así como del pseudocódigo de MapReduce.
3. Función de mapeo y función de reducción
La función de mapeo y la función de reducción son implementadas por los usuarios, y estas dos funciones definen la tarea en sí.
Función de mapa: acepta un par clave-valor y genera un conjunto de pares clave-valor intermedios. El marco MapReduce pasará valores con la misma clave en los pares clave-valor intermedios generados por la función de mapa a la función Reducir.
Función de reducción: acepta una clave y un conjunto de valores relacionados, y combina estos valores para producir un conjunto más pequeño de valores (generalmente solo un valor o valor cero).
El código central de la función MapReduce que cuenta la frecuencia de palabras es muy corto e implementa principalmente estas dos funciones.
¿[Simple]? Ver texto sin formato
Map(String?Key,?String?Value):
//?Key:? ¿documento? Nombre
//?Valor:? ¿documento? Contenido
¿Para qué? ¿Cada? ¿palabra? ¿w? ¿existir? valor:
emitir intermedio(w, "1");
reducir(string?key,?iterator?value):
// ?key: ? ¿respuesta? Palabras
//?Valores:? ¿respuesta? ¿Lista? ¿de? contar
int? ¿resultado? =?0;
¿Para qué? ¿Cada? v? ¿existir? Valores:
¿Resultados? +=?parse int(v);
emit(AsString(result));
En el ejemplo de contar la frecuencia de palabras, la clave aceptada por la función de mapa es el nombre del archivo. y el valor es el contenido del archivo. El mapa atraviesa las palabras una por una, y cada vez que encuentra una palabra w, un par clave-valor intermedio
4 Cómo funciona MapReduce
La figura anterior es el diagrama de flujo proporcionado. en el papel. Todo comienza desde el programa de usuario de nivel superior, que vincula la biblioteca MapReduce para realizar las funciones de mapas más básicas y las funciones de Reducción. La secuencia de ejecución en la figura está marcada con números.
La biblioteca MapReduce primero divide el archivo de entrada del programa de usuario en m archivos (m lo define el usuario, cada archivo generalmente tiene de 16 MB a 64 MB y se divide en divisiones de 0 a 4, como se muestra en). la figura de la izquierda. Luego use fork para copiar el proceso del usuario a otras máquinas en el clúster.
Una copia del programa de usuario se denomina programa principal y las demás se denominan programas de trabajo. El maestro es responsable de programar y asignar trabajos (asignar trabajos o reducir trabajos) a los trabajadores inactivos. El usuario también puede especificar el número de trabajadores.
El trabajador asignado al trabajo de mapa comienza a leer los datos de entrada del segmento correspondiente. El número de trabajos de mapa está determinado por m, lo que corresponde a dividir el trabajo de mapeo uno por uno; a partir de los datos de entrada, y cada par clave-valor se pasa como parámetro a la función de mapeo, y los pares clave-valor intermedios generados por la función de mapeo se almacenan en caché en la memoria.
Los pares clave-valor intermedios almacenados en caché se escribirán en el disco local con regularidad. Se dividirán en r áreas, el tamaño lo define el usuario y cada área corresponde a un trabajo futuro de Reducción de estos; pares clave-valor intermedios La ubicación será notificada al dispositivo maestro, que será responsable de reenviar la información a los trabajadores de Reduce.
El Maestro notifica al trabajador asignado al trabajo de Reducir dónde está la partición de la que es responsable (debe haber más de un lugar, y los pares clave-valor intermedios generados por cada trabajo de mapeo se pueden asignar a todos R diferentes particiones). Cuando el trabajador de Reducción lee todos los pares clave-valor intermedios de los que es responsable, primero se ordenan para que los pares con la misma clave se agrupen. La clasificación es necesaria porque se pueden asignar diferentes claves a la misma partición, es decir, el mismo trabajo de Reducir (quién quiere menos particiones).
El trabajador Reducir recorre los pares clave-valor intermedios ordenados y, para cada clave única, pasa la clave y el valor asociado a la función Reducir. La salida generada por la función reducir se agregará al archivo de salida. de esta partición.
Cuando se completan todos los trabajos de Map y Reduce, el maestro activa el programa de usuario genuino y la llamada a la función MapReduce devuelve el código del programa de usuario.
Después de todas las ejecuciones, la salida de MapReduce se coloca en los archivos de salida de las particiones R (cada una correspondiente a un trabajo de Reducción). Por lo general, los usuarios no necesitan fusionar estos archivos R, sino que los entregan como entrada a otro programa MapReduce para su procesamiento. Durante todo el proceso, los datos de entrada provienen del sistema de archivos distribuido subyacente (GFS), los datos intermedios se colocan en el sistema de archivos local y los datos de salida finales se escriben en el sistema de archivos distribuido subyacente (GFS). Y preste atención a la diferencia entre los trabajos de Mapa/reducción y las funciones de Mapa/Reducción: los trabajos de Mapa procesan un dato de entrada y es posible que necesiten llamar a la función de Mapa varias veces para procesar cada par clave-valor de entrada. Los trabajos de reducción procesan la clave intermedia; pares de valores de una partición, durante los cuales la función Reducir se llama una vez para cada clave diferente, y el trabajo Reducir finalmente corresponde a un archivo de salida.
Prefiero dividir el proceso en tres etapas. La primera etapa es la etapa de preparación, que incluye 1 y 2, con la biblioteca MapReduce como protagonista, completando tareas como dividir trabajos y copiar programas de usuario, la segunda etapa es la etapa de ejecución, que incluye 3, 4, 5 y 6. Los protagonistas son los mapas definidos por el usuario y las funciones de reducción, y cada pequeño trabajo se ejecuta de forma independiente. La tercera fase es la fase final, cuando el trabajo se completa y los resultados del trabajo se colocan en los archivos de salida, dependiendo de lo que el usuario quiera hacer con la salida.
5. ¿Cómo se calcula la frecuencia de las palabras?
Combinado con la Sección 4, puedes saber cómo funciona el código de la Sección 3. Supongamos que definimos M=5, R=3, hay 6 máquinas y 1 host.
Esta imagen describe cómo MapReduce maneja las estadísticas de frecuencia de palabras. Debido a que la cantidad de Mapworkers no es suficiente, los segmentos 1, 3 y 4 se procesan primero para generar pares clave-valor intermedios. Cuando todos los valores intermedios están listos, el trabajo de Reducción comienza a leer las particiones correspondientes y genera resultados estadísticos.
6. Derechos de usuario
La tarea principal del usuario es implementar el mapa y reducir las interfaces, pero también hay algunas interfaces útiles abiertas a los usuarios.
Lector de entrada. Esta función divide la entrada en m partes y define cómo extraer los pares clave-valor iniciales de los datos. Por ejemplo, en el ejemplo de frecuencia de palabras, el nombre del archivo y el contenido del archivo se definen como pares clave-valor.
Función de distribución. Esta función se utiliza para asignar los pares clave-valor intermedios generados por la función de mapa a una partición. La implementación más simple es aplicar hash a la clave y luego tomar el módulo r.
Función de comparación. Esta función se utiliza para clasificar trabajos reducidos. Esta función define la relación de tamaño de las claves.
Autor de salida. Responsable de escribir los resultados en el sistema de archivos distribuido subyacente.
La función combinadora es en realidad la función de reducción, utilizada para la optimización mencionada anteriormente. Por ejemplo, al contar la frecuencia de palabras, si cada
sin mencionar el mapa y las funciones de alejamiento.
7. Implementación de MapReduce
Actualmente existen muchas implementaciones de MapReduce Además de la implementación propia de Google, también existe el famoso hadoop. La diferencia es que Google usa c++. hadoop usa java. Además, la Universidad de Stanford ha implementado un MapReduce que se ejecuta en un entorno * * * de memoria compartida multinúcleo/multiprocesador, llamado Phoenix (introducción). El artículo correspondiente se publicó en HPCA en 2007 y fue el mejor artículo de ese año.