algorithm - mas - ordenamiento por seleccion pseint
¿Cómo funciona el algoritmo de ordenación MapReduce? (4)
Aquí hay algunos detalles sobre la implementación de Hadoop para Terasort :
TeraSort es una ordenación estándar de mapa / reducción, a excepción de un particionador personalizado que utiliza una lista ordenada de N - 1 claves muestreadas que definen el rango de clave para cada reducción. En particular, todas las claves tales que la 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 reducir 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 ''preordenado'' contra todos los demás reductores.
Encontré la referencia en papel a través de la publicación de blog de James Hamilton .
Uno de los principales ejemplos que se utiliza para demostrar el poder de MapReduce es el punto de referencia de Terasort . 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 pieza y luego todavía tiene que integrar estas piezas en el conjunto de datos completamente 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
Referencia de Google: MapReduce: procesamiento de datos simplificado en clústeres grandes
Apareció en :
OSDI''04: Sexto Simposio sobre Diseño e Implementación de Sistemas Operativos,
San Francisco, CA, diciembre de 2004.
Ese enlace tiene una referencia de PDF y HTML-Slide.
También hay una página de Wikipedia con una descripción con referencias de implementación.
También crítica,
David DeWitt y Michael Stonebraker, expertos pioneros en bases de datos paralelas y sin compartir arquitecturas, han hecho algunas afirmaciones controvertidas sobre la amplitud de los problemas que MapReduce puede utilizar. 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.
Solo adivinando...
Dado un gran conjunto de datos, usted dividiría los datos en algunos fragmentos para procesarlos en paralelo (quizás por número de registro, es decir, registro 1 - 1000 = partición 1, y así sucesivamente).
Asignar / programar cada partición a un nodo particular en el clúster.
Cada nodo del cluster romperá (mapeará) la partición en su propia mini partición, quizás por orden alfabético clave. 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).
Entregue 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). Muestra el resultado en la partición ordenada final (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, mapee y reduzca después del paso de reducción inicial.
Tuve la misma pregunta al leer el documento de MapReduce de Google. La answer @Yuval F prácticamente resolvió mi rompecabezas.
Una cosa que noté al leer el artículo es que la magia ocurre en la partición (después del mapa, antes de reducir).
El documento utiliza 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.
Simplemente agregue condiciones de contorno a la respuesta de @Yuval F para completarlo: suponga que min (S) y max (S) es la clave mínima y la clave máxima entre las claves muestreadas; 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 estricta 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.