El sitio web de redes sociales probablemente mantenga tablas para usuarios, amigos y eventos ...¿Cómo los sitios web de redes sociales calculan actualizaciones de amigos?
¿Cómo utilizan estas tablas para calcular eventos de amigos de una manera eficiente y escalable?
Muchos de los sitios de redes sociales como Twitter no hacer use un RDBMS en absoluto excepto una aplicación de Message Queue. Muchos de ellos comienzan con una aplicación ya presente como RabbitMQ. Algunos de ellos crecen lo suficiente como para tener que personalizar o crear su propio diseño. Twitter está en el proceso de hacer esto por segunda vez.
Una aplicación de cola de mensajes funciona manteniendo mensajes de un servicio para uno o más servicios. Por ejemplo, decir servicio Frank está publicando mensajes en una cola foo. Joe y Jill están suscritos a Franks foo queue. la aplicación hará un seguimiento de si Joe o Jill han recibido los mensajes y una vez que cada suscriptor haya recibido el mensaje, lo descartará. Frank dispara mensajes y se olvida de eso. Joe y Jill solicitan mensajes de foo y reciben los mensajes que aún no han recibido. Joe y Jill hacen lo que tienen que hacer con el mensaje. Tal vez mantenerlo tal vez no.
La aplicación de cola de mensajes garantiza que todos los que deben recibir el mensaje pueden recibir el mensaje y lo recibirán cuando lo soliciten. El editor puede enviar los mensajes confiando en que el suscriptor pueda obtenerlos eventualmente. Esto tiene la ventaja de ser completamente asincrónico y no requiere costosas uniones.
EDITAR: También debo mencionar que generalmente el almacenamiento para este tipo de cosas a gran escala está muy desnormalizado. Entonces Joe y Jill pueden estar guardando una copia del mismo mensaje exacto. Esto se considera correcto porque ayuda a la escala de la aplicación a miles de millones de usuarios.
Otras lecturas:
Para la pequeña escala, únete a usuarios.amigos y usuarios. Los eventos y el almacenamiento en caché de consultas probablemente estén bien, pero se ralentizan bastante rápido a medida que crecen tus amigos y tus eventos. También podría probar un modelo basado en eventos en el que cada vez que un usuario crea un evento, se crea una entrada en una tabla de unión (quizás llamada "friends_events"). Por lo tanto, cada vez que un usuario quiere ver qué eventos han creado sus amigos, simplemente puede hacer una combinación entre su propia identificación y la tabla friends_events y averiguarlo. De esta forma evitará atrapar a todos los usuarios con amigos y luego unirse a sus amigos con la tabla de eventos.
La estructura de datos principal de los sitios de redes sociales es graph. En Facebook, el gráfico no está dirigido (cuando eres amigo de alguien, son tus amigos). En twitter, el gráfico está dirigido (sigues a alguien, pero no necesariamente te siguen).
Las dos formas más comunes de representar gráficos son adjacency lists y adjacency matrices.
Una lista de adyacencia es simplemente una lista de bordes en el gráfico. Considere a un usuario con un ID de usuario entero.
User1, User2
1 2
1 3
2 3
La interpretación de estos registros no dirigido es que el usuario 1 es amigo de los usuarios 2 y 3 y el usuario 2 es también amigo de usuario 3.
En representación de esta en una tabla de base de datos es trivial. Es la tabla de unión de muchas a muchas relaciones con la que estamos familiarizados. Las consultas SQL para encontrar amigos de un usuario en particular son bastante fáciles de escribir.
Ahora que conoce a los amigos de un usuario en particular, solo necesita unir esos resultados a la tabla de actualizaciones. Esta tabla contiene todas las actualizaciones del usuario indexadas por ID de usuario.
Mientras todas estas tablas se indexan correctamente, tendría un tiempo bastante fácil diseñar consultas eficientes para responder a las preguntas que le interesan.
Travis escribió un gran post sobre esto,
+1 por mencionar la desnormalización, esto no es obvio para el viejo SQL wor ld donde 3NF ha sido la estrella guía durante mucho tiempo. (http://en.wikipedia.org/wiki/Third_normal_form) – Crypth