Manera eficiente de implementar LinkedIn como la función "¿Cómo estás conectado?"

Question

LinkedIn tiene esta genial característica en la que, al visitar el perfil de algunos usuarios, LinkedIn le indica cómo se está conectando con ese usuario a través de la red.

Suponiendo que el visitante y el propietario del perfil son dos nodos de un gráfico donde los nodos representan a los usuarios y edge representa la amistad, una solución simple podría ser un bfs comenzando desde los nodos hasta cierto nivel y ver si hay intersecciones. Las intersecciones serían los nodos de enlace de red.

Aunque esto suena ordenado, el problema es que para determinar amigos de cada persona, se necesita una consulta de DB por separado. Cuando la red va más allá de 2 niveles, sería un algoritmo que consumirá mucho tiempo. ¿Hay una mejor alternativa eficiente? Si no, ¿cómo podemos agregar mejor soporte de hardware (computación paralela, grillas, bases de datos distribuidas, etc.) para reducir el tiempo requerido para el cálculo?

Answer 1

Puede ver cómo se puede hacer esto en el artículo Graphs in the database: SQL meets social networks de Lorenzo Alberton. El código de ejemplo está escrito para PostgreSQL usando CTE. Sin embargo, dudo que usar un RDBMS para esto funcione bien. Escribí un artículo sobre cómo hacer lo mismo que en el artículo mencionado utilizando una base de datos de gráficos nativos, en este caso Neo4j: Social networks in the database: using a graph database. Además de las diferencias en el rendimiento, una base de datos de gráficos también simplifica la tarea al proporcionar una API de gráficos que facilita el manejo de recorridos que serían extremadamente complejos de escribir en SQL (o mediante el uso de procedimientos almacenados). Escribí un poco más sobre bases de datos de gráficos en this thread y también veo this one.

Answer 2

Sin algún tipo de procedimiento almacenado recursivo (CTE en SQL Server 2005+), necesitará varios viajes de ida y vuelta a medida que los niveles sean más profundos. Sin embargo, una buena infraestructura de caché realmente podría ayudar al rendimiento ya que las listas de conexión de los usuarios más populares/activos permanecerían en la memoria caché. Un mecanismo de caché de lectura/escritura mejoraría las cosas (actualizaciones de caché en cascada a actualizaciones de db, lecturas de caché en cascada a lecturas de db)