¿Cómo funciona el algoritmo de ordenación MapReduce?

Question

Uno de los principales ejemplos que se utiliza para demostrar el poder de MapReduce es el Terasort benchmark. Tengo problemas para entender los conceptos básicos del algoritmo de clasificación utilizado en el entorno MapReduce.

Para mí, ordenar simplemente implica determinar la posición relativa de un elemento en relación con todos los demás elementos. Así que clasificar implica comparar "todo" con "todo". Su algoritmo de clasificación promedio (rápido, burbuja, ...) simplemente lo hace de una manera inteligente.

En mi opinión, dividir el conjunto de datos en muchas piezas significa que puede ordenar una sola pieza y luego todavía tiene que integrar estas piezas en el conjunto de datos completo "completo". Dado el conjunto de datos de terabytes distribuidos en miles de sistemas, espero que sea una tarea enorme.

Entonces, ¿cómo se hace esto realmente? ¿Cómo funciona este algoritmo de clasificación MapReduce?

Gracias por ayudarme a entender.

Answer 1

A continuación algunos detalles sobre Hadoop's implementation for Terasort:

TeraSort es un mapa estándar/reducir especie, a excepción de un partidor personalizada que utiliza una lista ordenada de N - 1 teclas muestra que definen el rango de teclas para cada reducir . En particular, todas las claves tales como la muestra [i - 1] < = clave < muestra [i] se envían para reducir i. Esto garantiza que la salida de reducir i son todo menos de la salida de reducir i + 1 ".

Por lo que su truco está en la forma que determinen las teclas durante la fase de mapa. Esencialmente se aseguran de que todos los valores de un solo reductor se garantiza que sea 'preseleccionados' contra todos los otros reductores.

encontré la referencia de papel a través de James Hamilton's Blog Post.

Answer 2

Google Referencia: MapReduce: Simplified Data Processing on Large Clusters

Apareció en:
OSDI'04: Sexto Simposio sobre Diseño e implementación del sistema operativo,
San Francisco, CA, Diciembre, 2004.

Ese enlace tiene una referencia de PDF y HTML-Slide.

También hay un Wikipedia page with description con referencias de implementación.

también crítica,

David DeWitt y Michael Stonebraker, los expertos pioneros en bases de datos paralelas y nada arquitecturas compartidas, han hecho algunas afirmaciones polémicas acerca de la amplitud de los problemas que MapReduce se puede utilizar para. Llamaron a su interfaz de muy bajo nivel, y cuestionaron si realmente representa el cambio de paradigma que sus defensores han afirmado que es. Retan los reclamos de novedad de los defensores de MapReduce, citando a Teradata como un ejemplo de arte previo que ha existido por más de dos décadas; 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 la manipulación de registros de bajo nivel". El uso de MapReduce de archivos de entrada y la falta de compatibilidad con esquemas previenen las mejoras de rendimiento habilitadas por las características comunes del sistema de base de datos tales como B-trees y particiones hash, aunque proyectos como PigLatin y Sawzall están comenzando a abordar estos problemas.

Answer 3

sólo una suposición ...

Dado un conjunto enorme de datos, debería dividir los datos en algunos trozos para ser procesado en paralelo (tal vez por número de registro es decir, ficha 1 - 1000 = partición 1, y pronto).

Asignar/programar cada partición a un nodo particular en el clúster.

Cada nodo del clúster romperá (mapeará) la partición en su propia minidivisión, quizás por orden alfabético. Entonces, en la partición 1, consígueme todas las cosas que comiencen con A y déjelas en la mini partición A de x. Crea una nueva A (x) si actualmente ya hay una A (x). Reemplace x con número secuencial (quizás este es el trabajo del planificador para hacerlo). Es decir.Dame la siguiente identificación única de A (x).

Entregar los trabajos completados por el asignador (paso anterior) a los nodos del clúster "reducir". Reducir el grupo de nodos refinará aún más el tipo de cada A (x) partes que solo sucederá cuando se realicen todas las tareas del asignador (No se puede comenzar a ordenar todas las palabras comenzando con A cuando aún existe la posibilidad de que aún exista va a ser otra Una mini partición en preparación). Imprima el resultado en la partición final ordenada (es decir, Sorted-A, Sorted-B, etc.)

Una vez hecho esto, combine la partición ordenada en un solo conjunto de datos nuevamente. En este punto, es solo una simple concatenación de n archivos (donde n podría ser 26 si solo está haciendo A - Z), etc.

Puede haber pasos intermedios intermedios ... No estoy seguro:) Es decir. mapa adicional y reducir después del paso de reducción inicial.

Answer 4

que tenían la misma pregunta durante la lectura de papel MapReduce de Google. @Yuval F 's answer prácticamente resolvió mi rompecabezas.

Una cosa que noté al leer el documento es que la magia ocurre en la partición (después del mapa, antes de reducir).

El documento usa hash(key) mod R como el ejemplo de partición, pero esta no es la única forma de partición de datos intermedios para diferentes tareas de reducción.

Apenas añada condiciones de contorno a @Yuval F 's answer para que sea completa: supongamos min (S) y máximo (S) es la clave mínima y máxima de la clave de las claves de la muestra; todas las claves < min (S) se dividen en una tarea de reducción; viceversa, todas las teclas> = max (S) se dividen en una sola tarea de reducción.

No hay una limitación importante en las teclas muestreadas, como mínimo o máximo. Simplemente, más uniformemente estas claves R se distribuyen entre todas las claves, más "paralelo" es este sistema distribuido y es menos probable que un operador reduzca el problema de desbordamiento de memoria.