효율적인 방법으로 "어떻게 연결되어 있습니까?"기능과 같은 LinkedIn을 구현할 수 있습니까?

Question

LinkedIn은 네트워크를 통해 해당 사용자에게 연결하는 방법을 묻는 일부 사용자의 프로필을 방문하는 동안 멋진 기능을 제공합니다.

방문자와 프로필 소유자가 노드가 사용자를 나타내고 가장자리가 우정을 나타내는 그래프의 두 노드라고 가정하면 간단한 해결책은 두 노드에서 특정 수준까지 시작하여 모든 노드가 있는지 확인하는 bfs 일 수 있습니다 교차로. 교차점은 네트워크 링크 노드입니다.

비록 이것이 깔끔하게 들리지만 문제는 각 사람의 친구를 결정하기 위해 별도의 DB 쿼리가 필요하다는 것입니다. 네트워크가 2 레벨보다 깊어지면 알고리즘에 많은 시간이 소요됩니다. 더 효율적인 대안이 있습니까? 그렇지 않다면 어떻게 계산에 소요되는 시간을 줄이기 위해 더 나은 하드웨어 지원 (병렬 컴퓨팅, 그리드, 분산 데이터베이스 등)을 추가 할 수 있습니까?

Answer 1

Graphs in the database: SQL meets social networks by Lorenzo Alberton에서 볼 수 있습니다. 예제 코드는 CTE를 사용하는 PostgreSQL 용으로 작성되었습니다. 그러나, 이것에 대해 RDBMS을 사용하는 것이 잘 수행 될지는 의문입니다. 네이티브 그래프 데이터베이스 (이 경우 Neo4j : Social networks in the database: using a graph database)를 사용하여 언급 된 기사에서와 동일한 작업을 수행하는 방법에 대한 기사를 썼습니다. 성능 차이와는 별도로 그래프 데이터베이스는 SQL로 작성하는 데 매우 복잡한 트래버스 (또는 저장 프로 시저 사용)를 쉽게 처리 할 수있게 해주는 그래프 API를 제공하여 작업을 단순화합니다. 그래프 데이터베이스에 대해 this thread에 조금 더 썼습니다. this one도 있습니다.

Answer 2

일종의 재귀 저장 프로 시저 (SQL Server 2005 이상에서는 CTE)가 없으면 수준이 높아질수록 여러 왕복이 필요합니다. 그러나 가장 인기있는/활성 사용자의 연결 목록이 캐싱 된 상태로 남아 있기 때문에 좋은 캐시 인프라가 성능에 실제로 도움이 될 수 있습니다. 캐시 메커니즘을 통한 읽기/쓰기는 상황을 더욱 좋게 만듭니다 (캐시 업데이트는 db 업데이트로 캐스 캐 이드합니다. 캐쉬 읽기는 캐스 캐 이드를 읽습니다)