Estoy tratando de comprender los límites de hadoop y map/reduce y sería útil conocer un problema no trivial, o clase de problemas, que sepamos que map/reduce no puede ayudar.¿Hay algún problema canónico que no pueda ser ayudado con map/reduce?
It sin duda sería interesante si cambiar un factor del problema permitiría la simplificación de map/reduce.
Gracias
Dos cosas vienen a la mente:
Cualquier cosa que requiere tiempos de respuesta de latencia interactivos/baja en tiempo real /. Hay un costo fijo incurrido por cualquier trabajo enviado a Hadoop.
Cualquier problema que no sea embarrassingly parallel. Hadoop puede manejar una gran cantidad de problemas que requieren una interdependencia simple entre los datos, ya que los registros se unen durante la fase de reducción. Sin embargo, ciertos algoritmos de procesamiento de gráficos y aprendizaje automático son difíciles de escribir en Hadoop porque hay demasiadas operaciones que dependen unas de otras. Algunos algoritmos de aprendizaje automático requieren una latencia muy baja, acceso aleatorio a un gran conjunto de datos, que Hadoop no proporciona de manera predeterminada.
pensaría que cualquier problema que no pueda ser resuelto a un divide and conquer no funcionaría tan bien con Hadoop. Si el algoritmo se puede modificar para poder crear subtareas, entonces supongo que puede ejecutarse bajo hadoop.
Para agregar a su pregunta (en lugar de la respuesta, ¿hago esta parte de un comentario?), ¿Qué pasa si hay subtareas que puedo desglosar el problema, pero no hay manera clara de hacer la fase filter de hadoop? Supongo que todavía se puede usar hadoop para la fase map y hacer la reducción en una sola máquina.
Según lo expresado por otros: El problema debe ser fácil de cortar en piezas que se pueden procesar de forma independiente.
Déjeme darle dos ejemplos de mi pasado como arquitecto de WebAnalytics (esencialmente estaba tratando de hacer lo que Hadoop ofrece ahora ... sin hadoop ... usar scripts de shell bash en un solo sistema con múltiples núcleos de CPU) . Espero que estos dos te den una idea de cómo se verán esos límites en la vida real.
Contexto:
Suponga que tiene un gran cuerpo de loglines desde un servidor web. Y usted quiere analizar el comportamiento de los visitantes . Necesita una propiedad que le indique de manera confiable qué solicitud fue realizada por cada usuario.
Mis dos ejemplos:
En el pasado, alguien me dijo una vez que las ecuaciones de dinámica de fluidos (Navier-Stokes) no se pueden dividir en partes "Mapreducable". Aunque veo cierta lógica en por qué esto sería cierto (cada parte del fluido influye en cualquier otra parte del fluido); Debo aclarar que ni siquiera voy a tratar de entender estas ecuaciones.
Espero que estos ejemplos lo ayuden a encontrar los límites.
Respuesta a Gangadhar (lo siento, no hay suficiente espacio en el cuadro de comentarios):
me gusta su respuesta acerca de divide y vencerás, pero tengo una advertencia para agregar. Mapreduce no maneja muy bien el aspecto recursivo de los algoritmos de división y conquista porque la combinación de subproblemas para ciertos algoritmos de d/c depende eventualmente de la reducción a una clave. Tome el merge sort algorithm por ejemplo (ignorando por el momento que la ordenación es trivial en Hadoop debido a las propiedades clave de ordenamiento de su implementación de Mapreduce): usaría su asignador para dividir sus datos en dos partes, usando una identificación arbitraria para una clave. su fase de reducción fusionaría las listas de valores para sus respectivas claves juntas.
7 3 2 4 1 5 8 9 would map to
1->[[7],[3]] 2->[[2],[4]] 3->[[1],[5]] 4->[[8],[9]] would reduce to
3,7 2,4 1,5 8,9 would map to
1->[[3,7],[2,4]] 2->[[1,5],[8,9]]
etc.
se ve que el número de teclas se reduce en dos (o lo que sea factor de fragmentación que utiliza para su algoritmo de d/c) y, finalmente, debe bajar a una de las claves para una lista ordenada. Esto es malo para el paralelismo.
Por lo tanto, el aspecto dividido de dividir y conquistar es claramente necesario para mapreduce, pero también necesitamos paralelismo de datos en nuestra fase de conquista de modo que el resultado sea una colección de elementos paralelos de datos. FFT es un buen ejemplo de un algoritmo de división y conquista que funciona bien con mapreduce.
No está del todo claro a qué se refiere con "sabemos que map/reduce no puede ayudar". Las otras respuestas parecen estar contenidas con algunos ejemplos cuando no es trivial, fácil o no demasiado difícil cómo usar map reduce para obtener una velocidad significativa, pero lo que es fácil para uno puede no serlo para otra persona y lo mismo con significante. Personalmente me sentiría más satisfecho con un teorema que dice que algo no se puede hacer. Si observamos la complejidad computacional, existe una clase de problemas difíciles de paralelizar, problemas P-completos. Bien conocidos tales problemas son el reconocimiento gramatical sin contexto (importante para los compiladores), la programación lineal y algunos problemas de compresión. La entrada de wikipedia tiene más.
Algunas personas están creando nuevas clases de complejidad para reducir el mapa. Soy extremadamente escéptico, pero el jurado explica qué tan útiles serán.
La otra pregunta es: ¿podemos simular cualquier algoritmo paralelo en la reducción de mapa? Claro que no podemos hacer un mapa para reducir nuestro camino más allá de los problemas P-completos, pero tal vez hay algunos problemas que se pueden resolver en paralelo pero no en mapreduce. No conozco ninguno de esos problemas, pero conozco un documento que apunta en la dirección opuesta, aunque bajo algunas suposiciones "Simulando algoritmos paralelos en el Framework MapReduce con aplicaciones para geometría computacional paralela" por Michael T. Goodrich
En la práctica, tuvimos muy poco tiempo para pensar en el modo de reducir mapas y desarrollar técnicas algorítmicas específicas para este modelo, y veo que se reducen los problemas para reducir las soluciones de mapas. Cuando el polvo se asiente, podríamos encontrar que mapreduce tiene más poder de lo que parecía al principio.