Dzielenie ważony graf skierowany (ponad bazie kluczy/wartość)

Question

Chcielibyśmy shard ważonego reżyserii wykres,

użytkownik może dodawać węzły i krawędzie dynamicznie, początkowo DB/wykres jest pusty.

Zachowujemy węzły i krawędzie w bazie danych klucz/wartość (prawdopodobnie Redis): Dla każdego węzła będziemy mieć identyfikator węzła jako klucz i sortowany zestaw kluczy dla węzłów z odniesieniami Wynik każdego identyfikatora węzła w zestawie sortowanym jest ciężar krawędzi.

(patrz pytanie dotyczące tej tutaj: Redis: Implement Weighted Directed Graph)

Nie mamy ograniczenie równowaga, najczęściej działanie na wykresie jest Dijkstra, a my jak zminimalizować I/O (sieć w naszym przypadek)

Możliwe rozwiązanie: każdy serwer DB zawiera listę innych serwerów z IP:

klucz: serwer1, wartość: .... 250,1

klucz: server2, wartość: .... 250,2

klucz: serwer3, wartość: .... 250.3

i każdy nodeid będą serverX.originalNodeId

Jaki byłby algorytm, który decyduje, które węzeł idzie gdzie? czy powinniśmy wspierać ponowne pozycjonowanie węzła?

Chyba że naiwne podejście byłoby dodać węzeł A do serverX gdzie argmax (liczba węzłów w serwerze X, które mają krawędzie węzła A), tak długo jak serverX nie jest w pełni zajęty ..

Answer 1

Rejestracja przetwarzanie dzieje się po stronie klienta, ten rodzaj danych wykresu nie jest zbyt trudny do odstania - wszystko, czego potrzebujesz na każdym etapie, to pojedynczy zestaw posortowany, więc nie ma znaczenia, z którego węzła jest ładowany zestaw. Uzyskanie aktualnych danych z węzłem odbywa się jako ostatni krok - będzie to proste MGET, jeśli masz tylko jeden węzeł i jest dość łatwe do podzielenia na kilka węzłów.

Aby określić, w którym węźle będzie przechowywany klucz, należy użyć skrótu zamiast próbować ich ręcznie śledzić. Używam tabeli odwzorowującej zakres skrótów do określonego węzła. Jest przechowywany w trybie redis dla długoterminowej trwałości, ale jest naprawdę częścią klienta. Aby uzyskać dostęp do określonego klucza, wystarczy uzyskać skrót klucza, wyszukać go w tabeli i połączyć się z tym węzłem. Korzystanie z tabeli z tysiącami slotów ułatwia przenoszenie danych do innego węzła - aktualizuj tabelę, a żądania dotyczące konkretnego gniazda będą kierowane do innego węzła. Jest to dość podobne, chociaż nie jest dokładnie takie samo, jak podejście stosowane w klastrze Redis.

To powiedziawszy, moim powodem do utworzenia shardu nie były dane graficzne. Małe posortowane zestawy zawierające tylko identyfikatory nie zajmują dużo pamięci - powinieneś być w stanie obsłużyć 100 milionów krawędzi w jednym węźle bez większych problemów.