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

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

Para mí, clasificar simplemente implica determinar la posición relativa de un elemento en relación con todos los demás elementos. Por tanto, 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 partes significa que puede ordenar una sola pieza y luego todavía tiene que integrar estas partes en el conjunto de datos 'completo' completamente ordenado. Dado el conjunto de datos de terabytes distribuidos en miles de sistemas, espero que esta 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.

Aquí hay algunos detalles sobre la implementación de Hadoop para Terasort :

TeraSort es una clasificación estándar de mapa / reducción, excepto para un particionador personalizado que usa una lista ordenada de claves de muestra N - 1 que definen el rango de claves para cada reducción. En particular, todas las claves tales que muestra [i - 1] <= clave <muestra [i] se envían para reducir i. Esto garantiza que la salida de reduce i sea menor que la salida de reduce i + 1 ".

Entonces, su truco está en la forma en que determinan las claves durante la fase del mapa. Básicamente, aseguran que cada valor en un solo reductor esté garantizado para ser 'preclasificado' contra todos los demás reductores.

Encontré la referencia del artículo a través de la publicación del blog de James Hamilton .

Referencia de Google: MapReduce: procesamiento de datos simplificado en grandes clústeres

Apareció en :
OSDI'04: Sixth Symposium on Operating System Design and Implementation,
San Francisco, CA, diciembre de 2004.

Ese enlace tiene una referencia de diapositiva en PDF y HTML.

También hay una página de Wikipedia con una descripción con referencias de implementación.

También la crítica,

David DeWitt y Michael Stonebraker, expertos pioneros en bases de datos paralelas y arquitecturas de nada compartido, han hecho algunas afirmaciones controvertidas sobre la amplitud de problemas para los que se puede utilizar MapReduce. Llamaron a su interfaz de nivel demasiado bajo y cuestionaron si realmente representa el cambio de paradigma que sus defensores han afirmado que es. Desafían las afirmaciones de novedad de los defensores de MapReduce, citando a Teradata como un ejemplo de la técnica anterior que ha existido durante más de dos décadas; compararon a los programadores de MapReduce con los programadores de Codasyl, notando que ambos "escriben en un lenguaje de bajo nivel realizando manipulación de registros de bajo nivel". El uso de MapReduce de archivos de entrada y la falta de soporte de esquema evita las mejoras de rendimiento habilitadas por características comunes del sistema de base de datos, como árboles B y particiones hash,

Tuve la misma pregunta mientras leía el documento MapReduce de Google. La respuesta de @Yuval F prácticamente resolvió mi rompecabezas.

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

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

Simplemente agregue condiciones de contorno a @Yuval F 's respuesta 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) están divididas en una tarea de reducción; viceversa, todas las claves> = max (S) se dividen en una tarea de reducción.

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

Solo adivinando...

Dado un gran conjunto de datos, los dividiría en algunos fragmentos para procesarlos en paralelo (quizás por número de registro, es decir, registro 1 - 1000 = partición 1, etc.).

Asigne / programe cada partición a un nodo particular en el clúster.

Cada nodo del clúster dividirá (mapeará) la partición en su propia mini partición, tal vez por el orden alfabético clave. Entonces, en la partición 1, consígame todas las cosas que comienzan con A y envíelo a la mini partición A de x. Cree una nueva A (x) si ya existe una A (x). Reemplace x con un número secuencial (tal vez este sea el trabajo del planificador para hacerlo). Es decir, dame la siguiente identificación única A (x).

Entregue (programe) los trabajos completados por el asignador (paso anterior) a los nodos del clúster "reducir". Reducir el clúster de nodos luego refinará aún más el tipo de cada A (x) partes que solo sucederán cuando se realicen todas las tareas del mapeador (en realidad, no se pueden comenzar a ordenar todas las palabras que comienzan con A cuando todavía hay posibilidad de que todavía haya va a ser otra mini partición A en proceso). Envíe el resultado en la partición ordenada final (es decir, Sorted-A, Sorted-B, etc.)

Una vez hecho esto, vuelva a combinar la partición ordenada en un solo conjunto de datos. 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 en el medio ... No estoy seguro :). Es decir, más mapa y reducción después del paso de reducción inicial.