Actualmente estoy implementando algoritmos de análisis de gráficos iterativos en Hadoop (en MapReduce). Desafortunadamente, mi código es extremadamente lento, principalmente porque cada iteración es un paso de MapReduce separado. ¿Existe un buen enfoque para implementar estos algoritmos iterativos en MapReduce? ¿Hay alguna manera de evitar MapReduce por completo y calcular los datos que residen en HDFS usando MPI, etc.?

Answer 1

Nota: El mundo ha cambiado desde que inicialmente respondí la pregunta. Lo estoy actualizando para reflejar el estado del arte. – 5 de marzo de 2014

Descargo de responsabilidad: soy miembro de PMC de Apache Spark.

Sí, use Apache Spark ™: computación en clúster ultrarrápida

Apodado el sucesor principal de Hadoop MapReduce, Apache Spark es un sistema de cómputo de clúster que hace que el análisis de datos sea rápido, tanto rápido como rápido para escribir.

Algunos factores relacionados con su pregunta:

1. Con su compatibilidad con gráficos de ejecución general y un mejor almacenamiento en memoria, los programas en Spark pueden superar a los de Hadoop MapReduce en uno o dos órdenes de magnitud.
2. Puede expresar su algoritmo de manera concisa y comprensible utilizando las API de alto nivel e integradas en el lenguaje de Spark. Su programa será 10 veces más corto que los de MapReduce.
3. Hay una nueva biblioteca de cálculo gráfico llamada GraphX ​​en Spark para simplificar su vida.
4. El proyecto presenta uno de los ecosistemas de código abierto más activos en proyectos de Big Data. Cuenta con más de 150 colaboradores de más de 30 empresas.

Como ejemplo, vea una variante de la implementación de PageRank en Spark:

val links = // RDD of (url, neighbors) pairs var ranks = // RDD of (url, rank) pairs for (i  links.map(dest => (dest, rank/links.size)) } ranks = contribs.reduceByKey(_ + _) .mapValues(0.15 + 0.85 * _) } ranks.saveAsTextFile(...) 

Answer 2

Recientemente estaba rediseñando un enorme sistema de gráficos MR. No diría que fui lento por MapReduce sino por mala arquitectura. Pude reducir la cantidad de información en más del 90%.

Si desea tener un procesamiento gráfico iterativo rápido en M / R, es bueno tener un buen preprocesamiento. Intente eliminar / comprimir tanta información como sea posible antes de la primera iteración y capture la mayor cantidad de datos que pueda. Una buena idea es cambiar el nombre de los nodos del gráfico a enteros de 32/64 bits y luego usar la compresión delta. Es mejor que tratar de usar hashing. Encuentre alguna heurística que capture la localidad de datos de su dominio y úsela para cambiar el nombre. Si puede, no almacene el peso del flotador en cada borde, intente recalcularlo con más información comprimible.

(Usar Apache Giraph es una buena idea si tienes mucha memoria)

Answer 3

Si desea seguir con HDFS, tal vez considere Giraph: http://incubator.apache.org/giraph/ .
Alternativamente, eche un vistazo a GraphLab: http://graphlab.org/ .