Ordenando datos grandes usando MapReduce/Hadoop

Question

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 fue la siguiente:

Escribir una función de correlacionador que clasifique 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

Answer 1

Echa un vistazo a la fusión-tipo.

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 ordenadas, solo tiene que buscar el elemento más pequeño de las 4 listas y elegirlo. Si el número de listas es constante, esta reducción es una operación O (N).

También generalmente los reductores también se "distribuyen" en algo así como un árbol, por lo que el trabajo también se puede paralelizar.

Answer 2

creo, que combina múltiples elementos ordenadas es eficiente que la combinación de múltiples sin ordenar artículos. 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.

Answer 3

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 gigante también puede ser prohibitivo. 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.

Answer 4

Así que la forma más sencilla para ordenar el uso de mapas reducir (aunque el no la más eficiente) es hacer lo siguiente

Durante la Fase Mapa (Input_Key, valor_entrada) emiten a cabo (valor_entrada, clave de entrada)

Reductor es una identidad Reduceer

Así por ejemplo, si nuestros datos es un estudiante, base de datos de edad, entonces su entrada asignador 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.

Answer 5

Lo siento por llegar tarde, pero para los futuros lectores, sí Chandler, que está recibiendo mal

lógica es que Reductor puede manejar arrastrando los pies y luego ordenados los datos de su nodo única sobre la 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.

Por lo tanto, para los grandes datos utilizamos Tera sort, que no es más que identificador de identidad y reductor con particionador personalizado. Obtenga más información al respecto aquí. Debe leer más al respecto aquí Hadoop's implementation for Terasort. Establece:

"TeraSort es una clasificación/reducción estándar, excepto por un particionador personalizado que utiliza una lista ordenada de N - 1 claves muestreadas que definen el rango de claves para cada reducción. En particular, todas las claves como esa 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. "

Answer 6

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 usted aludido, el mergesort (con el mapa-reducir) implicaría siguientes pasos:

1. partición de los elementos en grupos pequeños y asigne a cada grupo a los creadores de mapas en forma de round robin
2. Cada mapeador ordenará el subconjunto y devolverá {K, {subconjunto}}, donde K es el mismo para todos los mapeadores
3. 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 ordenados

El problema aquí es que, como usted ha mencionado, no puede haber un único reductor que impide 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.

encontrado la explicación a http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf

Volviendo a fusionar-tipo, esto sería factible si el hadoop (o equivalente) herramienta proporciona jerarquía de reductores donde la producción de un nivel de reductores va al siguiente nivel de reductores o bucle de vuelta al mismo conjunto de reductores