performance - supernodos - Neo4j problema de súper nodo-patrón de abanico de salida
supernodo 3 fuentes (3)
Soy nuevo en la escena Base de datos de Gráficos, analizando Neo4j y aprendiendo Cypher, estamos tratando de modelar una base de datos de gráficos, es bastante simple, tenemos usuarios y tenemos películas , los usuarios pueden VER películas , CALIFICAR películas , crear listas de reproducción y las listas de reproducción pueden tener películas .
La pregunta es sobre el problema de rendimiento de Super Node. Y citaré algo de un muy buen libro que estoy leyendo actualmente: Aprendiendo Neo4j por Rik Van Bruggen , así que aquí está:
Entonces ocurre un problema muy interesante en los conjuntos de datos donde algunas partes del gráfico están conectadas al mismo nodo. Este nodo, también conocido como nodo denso o supernodo, se convierte en un problema real para los recorridos de gráficos porque el sistema de administración de la base de datos de gráficos tendrá que evaluar todas las relaciones conectadas a ese nodo para determinar cuál será el próximo paso. La gráfica transversal.
La solución a este problema que se propone en el libro es tener un nodo Meta con 100 conexiones, y la conexión 101 se debe vincular a un nuevo nodo Meta que está vinculado al Meta Nodo anterior.
He visto una publicación de blog del blog oficial de Neo4j que dice que solucionarán este problema en el futuro (la publicación del blog es de enero de 2013) - http://neo4j.com/blog/2013-whats-coming-next-in-neo4j/
Más exactamente dicen:
Otro proyecto que hemos planeado alrededor de "datos más grandes" es agregar algunas optimizaciones específicas para manejar los recorridos a través de nodos densamente conectados, teniendo un gran número (millones) de relaciones. (Este problema a veces se conoce como el problema de los "supernodos".)
¿Cuáles son tus opiniones sobre este tema? ¿Deberíamos ir con el patrón de abanico de salida de Meta nodos o con la relación básica que parece estar utilizando cada tutorial? ¿Cualquier otra sugerencia?
(descargo de responsabilidad: no es una respuesta, pero un poco de discusión)
La publicación del blog neo4j de 2013 que mencionó, contiene enlaces a este compromiso de github , donde se analiza el alcance del problema deseado y su solución. Para resumir, no aborda el problema general de supernode . En su lugar, alivia el problema cuando, entre los múltiples tipos de relaciones (y direcciones) que tiene un supernode , algunos de los tipos (direcciones) tienen desproporcionadamente menos bordes que los otros. El motor es capaz de filtrar en función de los tipos y direcciones.
Una solución más genérica es el enfoque vertex centric de Titan ( https://.com/a/21385213/1311956 ), que clasifica los bordes por uno o un conjunto de propiedades, lo que resulta en un rendimiento de búsqueda en O (log (E)) , donde E es el número de bordes dentro / fuera del supernode .
Neo4j tiene el concepto de índice en las relaciones. A diferencia del enfoque vertex centric de Titán, el índice es global. Sin embargo, el índice de relación es un legado en Neo4j. Esto se discute en otro hilo de .
Otro problema con Supernode es el problema de almacenamiento que conduce al problema de almacenamiento y al costo de IO.
Es una buena pregunta. Esto no es realmente una respuesta, pero ¿por qué no podríamos discutir esto aquí? Técnicamente, creo que se supone que debo marcar tu pregunta como "principalmente basada en la opinión", ya que estás solicitando opiniones explícitamente, pero creo que vale la pena discutirlo.
La respuesta aburrida pero honesta es que siempre depende de los patrones de consulta. Sin saber qué tipo de consultas va a realizar con esta estructura de datos, realmente no hay forma de saber cuál es el "mejor" enfoque.
Los supernodos también son problemas en otras áreas. Las bases de datos de gráficos a veces son muy difíciles de escalar de alguna manera, porque los datos en ellas son difíciles de particionar. Si esto fuera una base de datos relacional, podríamos particionar vertical u horizontalmente. En una base de datos gráfica cuando tienes supernodos, todo está "cerca" de todo lo demás. (A un granjero de Alaska le gusta Lady Gaga, al igual que a un banquero de Nueva York). Más que simplemente graficar la velocidad de recorrido, los supernodos son un gran problema para todo tipo de escalabilidad.
La sugerencia de Rik se reduce a animarle a crear "sub-clusters" o "particiones" del super-nodo. Para ciertos patrones de consulta, esto podría ser una buena idea, y no estoy rechazando la idea, pero creo que oculta aquí está la noción de una estrategia de agrupamiento. ¿Cuántos meta nodos asignas? ¿Cuántos enlaces max por meta-nodo? ¿Cómo fue que asignaste a este usuario a este meta nodo (y no a otro)? Dependiendo de sus consultas, esas preguntas serán muy difíciles de responder, difíciles de implementar correctamente o ambas.
Un enfoque diferente (pero conceptualmente muy similar) es clonar a Lady Gaga unas mil veces, duplicar sus datos y mantenerlos sincronizados entre los nodos, y luego afirmar un montón de relaciones "iguales a" entre los clones. Esto no es tan diferente del enfoque "meta", pero tiene la ventaja de que copia los datos de Lady Gaga al clon, y el nodo "Meta" no es solo un marcador de posición para la navegación. Sin embargo, la mayoría de los mismos problemas se aplican.
Sin embargo, aquí hay una sugerencia diferente: aquí tiene un problema de mapeo de muchos a muchos a gran escala. Es posible que si este es un problema realmente grande para usted, sería mejor (from_id, to_id) en una sola tabla relacional con dos columnas (from_id, to_id) , cada una de las cuales hace referencia a un ID de nodo neo4j. Entonces, es posible que tenga un sistema híbrido que sea mayormente gráfico (pero con algunas excepciones). Muchas compensaciones aquí; por supuesto, no se puede cruzar esa información en absoluto, pero se escalaría y particionaría mucho mejor, y la consulta de una versión en particular probablemente sería mucho más rápida.
Una observación general aquí: si estamos hablando de relaciones relacionales, gráficos, documentos, bases de datos K / V, o lo que sea, cuando las bases de datos se vuelven realmente grandes y los requisitos de rendimiento se vuelven realmente intensos, es casi inevitable que las personas terminen con algo. tipo de solución híbrida con más de un tipo de DBMS. Esto se debe a la realidad ineludible de que todas las bases de datos son buenas en algunas cosas y no buenas en otras. Entonces, si necesita un sistema que sea bueno en casi todo, tendrá que usar más de un tipo de base de datos. :)
Probablemente hay mucho que neo4j puede hacer para optimizar en estos casos, pero me parece que el sistema necesitaría algunos tipos de pistas sobre los patrones de acceso para poder hacer un buen trabajo. De las 2,000,000 relaciones presentes, ¿cómo se agrupan los puntos finales? ¿Son las relaciones más antiguas más importantes que las nuevas, o viceversa?
Re. En el blog Neo4j, el soporte de nodos densos debe mejorarse en Neo4j 2.1 (y superior), consulte también http://neo4j.com/blog/neo4j-2-1-graph-etl/