Wydajny sposób wdrożenia LinkedIn w stylu "Jak masz połączenie z"?

Question

LinkedIn ma tę fajną funkcję, dzięki której odwiedzając profil użytkownika, LinkedIn podpowiada w jaki sposób łączysz się z tym użytkownikiem za pośrednictwem sieci.

Zakładając, że użytkownik i właściciel profilu są dwoma węzłami wykresu, na którym węzły reprezentują użytkowników, a krawędź przedstawia przyjaźń, prostym rozwiązaniem może być bfs, zaczynając od obu węzłów do pewnego poziomu i sprawdzając, czy są jakieś skrzyżowania. Skrzyżowania będą węzłami sieciowymi.

Chociaż brzmi to zgrabnie, problemem jest to, że w celu ustalenia przyjaciół każdej osoby potrzebne jest osobne zapytanie DB. Gdy sieć zajmie więcej niż 2 poziomy, będzie to bardzo czasochłonny algorytm. Czy istnieje skuteczniejsza alternatywa? Jeśli nie, jak możemy ulepszyć obsługę sprzętu (przetwarzanie równoległe, sieci, rozproszona baza danych itp.), Aby zmniejszyć czas potrzebny na obliczenia?

Answer 1

Możesz zobaczyć, jak można to zrobić w artykule Graphs in the database: SQL meets social networks autorstwa Lorenzo Albertona. Przykładowy kod jest napisany dla PostgreSQL przy użyciu CTE. Wątpię jednak, że użycie tego modelu będzie dobrze działać. Napisałem artykuł o tym, jak zrobić to samo, co we wspomnianym artykule, korzystając z macierzystej bazy danych wykresów, w tym przypadku Neo4j: . Oprócz różnic w wydajności, baza danych wykresów upraszcza zadanie, udostępniając interfejs API wykresów, który ułatwia obsługę operacji przechodzenia, które byłyby niezwykle złożone w SQL (lub za pomocą procedur przechowywanych). Napisałem trochę więcej na bazach wykresów w this thread i widzę też this one.

Answer 2

Bez jakiejś rekurencyjnej procedury przechowywanej (CTE w SQL Server 2005+), będziesz potrzebował wielu podróży w obie strony, gdy poziomy będą głębsze. Jednak dobra infrastruktura pamięci podręcznej może naprawdę pomóc w wydajności, ponieważ najbardziej popularne/aktywne listy połączeń użytkowników pozostaną w pamięci podręcznej. Mechanizm odczytu/zapisu poprzez pamięć podręczną sprawiłby, że rzeczy byłyby jeszcze lepsze (aktualizacje pamięci podręcznej kaskada aktualizacji db, pamięć podręczna odczytuje kaskadę do odczytów bazy danych)