de particiones en un gráfico dirigido ponderado (más de base de datos clave/valor)

Question

Nos gustaría fragmentar un grafo dirigido ponderado,

el usuario puede añadir nodos y los bordes de forma dinámica, en un principio el DB/gráfico está vacío.

Conservamos los nodos y bordes en una base de datos clave/valor (probablemente Redis): para cada nodo, tendremos el nodeId como la clave y un conjunto ordenado de claves de nodos referenciados el puntaje de cada nodeId en sortedSet es el peso del borde.

(Véase la pregunta con respecto a ese aquí: Redis: Implement Weighted Directed Graph)

No tenemos una restricción de equilibrio, la acción más común sobre el gráfico es Dijkstra, y que tenía como para minimizar la E/S (en nuestra red caso)

Posible solución: cada servidor de base de datos contiene una lista de otros servidores con IPs:

clave: server1, valor: .... 250.1

clave: servidor2, valor: .... 250.2

clave: servidor3, valor: .... 250.3

y cada NODEID será serverX.originalNodeId

¿Cuál sería el algoritmo que decide qué nodo va a donde? ¿Deberíamos apoyar el reposicionamiento de un nodo?

supongo que el enfoque ingenuo sería, añadir el nodo A al servidorX donde argmax (# de nodos de servidor X que tienen bordes con el nodo A), siempre y cuando servidorX no está totalmente ocupado ..

Answer 1

Desde el procesamiento ocurre en el lado del cliente, este tipo de datos de gráficos no es demasiado difícil de fragmentar: todo lo que necesita en cada paso es un único conjunto ordenado, por lo que no importa de qué nodo se cargue ese conjunto. Obtener los datos reales para ir con el nodo ocurre como el paso final: será un MGET simple si solo tiene un nodo y es bastante fácil de dividir en varios nodos.

Para determinar en qué nodo se almacenará una clave, debe usar un hash en lugar de intentar rastrearlos manualmente. Uso una tabla mapeando un rango de valores hash a un nodo particular. Se almacena en redis para la persistencia a largo plazo pero es realmente parte del cliente. Para acceder a una tecla en particular, solo obtiene el hash de la clave, búsquelo en la tabla y conéctese a ese nodo. El uso de una tabla con miles de espacios permite mover los datos a otro nodo: actualice la tabla y las solicitudes de un espacio en particular irán a un nodo diferente. Esto es bastante similar a, aunque no exactamente lo mismo que el enfoque utilizado en el cluster redis.

Dicho esto, mi razón para configurar la fragmentación no era la información de gráficos. Los pequeños conjuntos ordenados que contienen solo ID no ocupan mucha memoria: usted debe poder manejar 100 millones de bordes en un solo nodo sin demasiados problemas.