En Hadoop Map-Reduce, ¿alguna clase ve la lista completa de claves después de ordenar y antes de particionar?

Question

Estoy usando Hadoop para analizar una distribución de datos muy desigual. Algunas teclas tienen miles de valores, pero la mayoría tiene solo una. Por ejemplo, el tráfico de red asociado con las direcciones IP tendría muchos paquetes asociados con algunas IP hablativas y solo algunos con la mayoría de las IP. Otra forma de decir esto es que el Gini index es muy alto.

Para procesar esto de manera eficiente, cada reductor debe obtener unas pocas teclas de alto volumen o un montón de teclas de bajo volumen, de forma tal que se obtenga una carga más o menos pareja. Sé cómo haría esto si estuviera escribiendo el proceso de partición: Tomaría la lista ordenada de keys (incluidas todas las claves duplicadas) producida por los correlacionadores, así como el número de reductores N y poner divisiones en

split[i] = keys[floor(i*len(keys)/N)] 

Reductor i obtendría teclas k tal que split[i] <= k < split[i+1] para 0 <= i < N-1 y split[i] <= k para i == N-1.

Estoy dispuesto a escribir mi propio particionador en Java, pero la clase Partitioner<KEY,VALUE> solo parece tener acceso a un registro de clave-valor a la vez, no a toda la lista. Sé que Hadoop clasifica los registros que produjeron los mapeadores, por lo que esta lista debe existir en alguna parte. Podría distribuirse entre varios nodos del particionador, en cuyo caso yo haría el procedimiento de división en una de las sublistas y de alguna manera comunicaría el resultado a todos los demás nodos del particionador. (Suponiendo que el nodo del particionador elegido ve un subconjunto aleatorizado, el resultado aún sería aproximadamente equilibrado de la carga). ¿Alguien sabe dónde se almacena la lista ordenada de claves y cómo acceder a ella?

No quiero escribir dos trabajos de reducción de mapa, uno para encontrar las divisiones y otro para usarlas realmente, porque eso parece un desperdicio. (Los cartógrafos tendrían que hacer el mismo trabajo dos veces.) Esto parece un problema general: las distribuciones desiguales son bastante comunes.

Answer 1

Según tengo entendido, no hay un solo lugar en el procesamiento MR donde estén presentes todas las claves. Más que esto, no hay garantía de que una sola máquina pueda almacenar esta información. Creo que este problema no tiene la solución ideal en el marco MR actual. Creo que sí, porque para tener la solución ideal, tenemos que esperar al final del último mapeador y solo luego analizar la distribución de claves y parametrizar el particionador con este conocimiento.
Este enfoque complicará significativamente el sistema y aumentará la latencia.
Creo que una buena aproximación podría ser hacer un muestreo aleatorio sobre los datos para obtener la idea de la distribución de las claves y luego hacer que partiotioner funcione de acuerdo con ella.
Por lo que entiendo la implementación de Terasort está haciendo algo muy similar: http://sortbenchmark.org/YahooHadoop.pdf

Answer 2

He estado pensando en este problema, también. Este es el enfoque de alto nivel que tomaría si alguien me obligara.

• Además de la lógica asignador que tiene en lugar de resolver el problema de la empresa, código de alguna lógica para reunir estadísticas lo que necesita en el partidor para distribuir pares de valores clave de una manera equilibrada. Por supuesto, cada mapeador solo verá algunos de los datos.
• Cada asignador puede encontrar su ID de tarea y usar esa ID para construir un nombre de archivo único en una carpeta hdfs especificada para contener las estadísticas recopiladas. Escriba este archivo en el método de limpieza() que se ejecuta al final de la tarea.
• usa la inicialización lenta en el particionador para leer todos los archivos en el directorio hdfs especificado. Esto te proporciona todas las estadísticas recopiladas durante la fase de mapeo. A partir de ahí, le queda implementar cualquier lógica de particionamiento que necesite para dividir correctamente los datos.

Todo esto supone que no se llama al particionador hasta que todos los mapeadores hayan finalizado, pero eso es lo mejor que he podido hacer hasta ahora.