java - función - hdfs
Ordenando datos grandes usando MapReduce/Hadoop (6)
Estoy leyendo sobre MapReduce y lo siguiente me confunde.
Supongamos que tenemos un archivo con 1 millón de entradas (enteros) y queremos ordenarlos usando MapReduce. La forma en que entendí para hacerlo es la siguiente:
Escribe una función de correlacionador que ordena enteros. Por lo tanto, el marco dividirá el archivo de entrada en múltiples fragmentos y los entregará a diferentes mapeadores. Cada mapeador clasificará su fragmento de datos de forma independiente el uno del otro. Una vez que todos los mapeadores hayan terminado, pasaremos cada uno de sus resultados a Reducer y combinará el resultado y me dará el resultado final.
Mi duda es que, si tenemos un reductor, ¿cómo puede aprovechar el marco distribuido si, finalmente, tenemos que combinar el resultado en un solo lugar? El problema se reduce a la fusión de 1 millón de entradas en un solo lugar. ¿Es eso o me falta algo?
Gracias, Chander
Así que la forma más sencilla de ordenar usando map-reduce (aunque no es la más eficiente) es hacer lo siguiente
Durante la fase de mapa (Input_Key, Input_Value) emitir (Input_Value, Input Key)
Reducer es un reductor de identidad
Entonces, por ejemplo, si nuestros datos son una base de datos de edad del estudiante, entonces la entrada del mapeador sería (''A'', 1) (''B'', 2) (''C'', 10) ... y la salida sería (1, A) (2, B) (10, C)
No he probado esta lógica, pero es un paso en un problema de tarea en el que estoy trabajando. Pondrá una actualización de código fuente / enlace lógico.
Como han mencionado otros, la fusión es mucho más simple que la clasificación, por lo que hay una gran victoria allí.
Sin embargo, realizar una operación en serie O (N) en un conjunto de datos gigantes puede ser prohibitivo también. Como correctamente señalas, es mejor encontrar una manera de hacer la fusión en paralelo, también.
Una forma de hacerlo es reemplazar la función de partición del particionador aleatorio (que es lo que normalmente se usa) por algo un poco más inteligente. Lo que hace Pig para esto, por ejemplo, es muestrear su conjunto de datos para obtener una aproximación aproximada de la distribución de sus valores, y luego asignar rangos de valores a diferentes reductores. El reductor 0 obtiene todos los elementos <1000, el reductor 1 obtiene todos los elementos> = 1000 y <5000, y así sucesivamente. Luego puede hacer la fusión en paralelo, y el resultado final se ordena según conoce el número de cada tarea del reductor.
Creo que combinar varios elementos ordenados es eficiente que combinar varios elementos sin clasificar . Entonces los mapeadores hacen la tarea de clasificar trozos y el reductor los fusiona. Si los mapeadores no hubieran hecho la clasificación, el reductor tendrá dificultades para realizar la clasificación.
Echa un vistazo a merge-sort.
Resulta que ordenar listas parcialmente ordenadas es mucho más eficiente en términos de operaciones y consumo de memoria que ordenar la lista completa.
Si el reductor obtiene 4 listas clasificadas, solo necesita buscar el elemento más pequeño de las 4 listas y elegir ese. Si el número de listas es constante, esta reducción es una operación O (N).
También típicamente los reductores también se "distribuyen" en algo así como un árbol, por lo que el trabajo también se puede paralelizar.
La ordenación se puede implementar de manera eficiente utilizando MapReduce. Pero parece que estás pensando en implementar merge-sort usando mapreduce para lograr este propósito. Puede que no sea el candidato ideal.
Al igual que aludió, el mergesort (con map-reduce) implicaría los siguientes pasos:
- Partición de los elementos en pequeños grupos y asignar cada grupo a los mapeadores en forma de round robin
- Cada mapeador clasificará el subconjunto y devolverá {K, {subconjunto}}, donde K es el mismo para todos los mapeadores
- Como se usa la misma K en todos los mapeadores, solo una reduce y, por lo tanto, solo un reductor. El reductor puede combinar los datos y devolver el resultado ordenado
El problema aquí es que, como mencionaste, solo puede haber un reductor que impida el paralelismo durante la fase de reducción. Como se mencionó en otras respuestas, mapreduce implementaciones específicas como terasort se pueden considerar para este propósito.
Encontré la explicación en http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf
Volviendo a merge-sort, esto sería factible si la herramienta hadoop (o equivalente) proporciona una jerarquía de reductores donde la producción de un nivel de reductores va al siguiente nivel de reductores o lo devuelve al mismo conjunto de reductores
Perdón por llegar tarde pero para futuros lectores, sí, chandler, lo estás entendiendo mal
La lógica es que Reducer puede manejar los datos mezclados y luego clasificados de su nodo solo en el que se está ejecutando. Me refiero a que el reductor que se ejecuta en un nodo no puede mirar los datos de otro nodo, sino que reduce el algoritmo solo en sus datos. El procedimiento de fusión SO de tipo de fusión no se puede aplicar.
Entonces, para big data usamos Tera sort, que no es más que mapper de identidad y reductor con particionador personalizado. Obtenga más información al respecto aquí. Debe leer más al respecto desde aquí . Implementación de Hadoop para Terasort . Afirma:
"TeraSort es una ordenación estándar de mapa / reducción, a excepción de un particionador personalizado que utiliza una lista ordenada de claves muestreadas N - 1 que definen el rango de clave para cada reducción. En particular, todas las claves tales como muestra [i - 1] <= la clave <muestra [i] se envía para reducir i. Esto garantiza que la salida de reduce i sea menor que la salida de reducir i + 1. "