¿Cómo mantiene Facebook una lista de amigos para cada usuario? ¿Mantiene una tabla separada para cada usuario?

Facebook usa una base de datos de gráficos, llamada Open Graph para organizar las redes sociales con una tecnología de base de datos que es mucho más rápida y más adecuada para la tarea que la tecnología SQL anterior. Para obtener más información sobre bases de datos de gráficos, consulte Base de datos de gráficos. Para obtener más información sobre Open Graph y su protocolo, consulte: Protocolo Open Graph. Una base de datos de gráficos de nivel empresarial de propósito general es Neo4j: los gráficos de Neo4j modelan qué entidades son adyacentes entre sí y se pueden usar para organizar y representar relaciones: teoría de gráficos Las operaciones que usan bases de datos de gráficos son mucho más rápidas que las bases de datos relacionales que usan operaciones de unión SQL y, en primer lugar, normal (1NF). Las bases de datos de gráficos pertenecen a un tipo de tecnología de base de datos llamada No solo SQL (o NoSQL): NoSQL Ejemplos de bases de datos NoSQL son MongoDB, Open Graph de Facebook, Neo4j y programación M (representada por InterSystems Caché (utilizada por la Agencia Espacial Europea) para mapear la Vía Láctea Galaxy) y GT.M).

Trabajo en Serwis społecznościowy nk.pl – platforma komunikacji dla wszystkich internautów – nk.pl, que solía ser la red social más grande de Polonia, y puedo decirte una cosa: tales relaciones deben almacenarse “en ambos sentidos”. Otros han sugerido aquí, que puede usar una sola tabla `amistad` con dos columnas` user_a`, `user_b` y mantener una sola fila para cada envío. Esta es una muy mala idea para la escalabilidad y la simplicidad del código. Como puede ver en la respuesta de Marcus Matos, rápidamente conduce a UNIONES masivas y complicadas “ifologías” en las UNIONES, ya que cada borde debe verificarse en ambas direcciones. Además, esto hace que el fragmentación (división de la base de datos en muchas máquinas) sea casi imposible.
En cambio, lo que hacemos es agregar dos bordes: por ejemplo, si el usuario # 17 agrega el usuario # 36 a su lista de amigos, realizamos dos INSERT para (17,36) y (36,17).
De esta forma, la lista de amigos de un solo usuario se puede recuperar con una única selección simple.
Además, compartimos la base de datos usando `shard_number = user_a MOD number_of_shards` que nos permite recuperar una lista completa de amigos en una sola consulta en una sola máquina.
También hace que los problemas de “amigos de amigos” y “amigos comunes” sean un poco más fáciles, pero, francamente, incluso Serwis społecznościowy nk.pl – platforma komunikacji dla wszystkich internautów – nk.pl tiene más de 4 millones de bordes, y maneja esto en tiempo real es un poco complicado, por lo que en realidad tenemos trabajos por lotes que se ejecutan por la noche, por lo que las propuestas de personas que quizás conozca se almacenan en caché y están disponibles en la mañana.

Para que mi punto sea más convincente: en realidad hemos usado el enfoque con amistad única = fila única, durante dos años IIRC, ¡y fue un desastre!

Una cosa más: puede asegurarse de que siempre realiza los dos INSERT en el mismo orden en que realiza dos DELETEs (por ejemplo, utilizando el orden lexicográfico) y luego si hay algún problema de integridad (una base de datos tiene una fila, pero la fila simétrica falta) puede decir fácilmente cuál fue la última operación que falló y restaurar el estado coherente.
Por ejemplo, si ve que hay una fila (36,17), pero falta (17,36), debe significar que hubo una transacción DELETE (17,36), DELETE (36,17) que falló en el medio.

Ya se han dado muchas respuestas informativas. Además, si desea explorar cómo y en qué orden se almacena exactamente su lista de amigos, como en el núcleo, puede hacerlo de la siguiente manera:

Primero, continúe e inicie sesión en su cuenta de Facebook en cualquier navegador (preferiblemente Firefox). Haga clic derecho en la página y haga clic en ‘Ver código fuente de la página’. Ahora, en el código fuente, presione Ctrl + F y comience a buscar ‘FriendsList’. Encontrará una lista después de esta ‘Lista de amigos’, que sería algo así como una Lista de arreglos, que consta de algunos números grandes de 15 dígitos, encerrados entre llaves y corchetes, separados por comas. Copie el primer número y colóquelo en la barra de direcciones de una nueva pestaña en su navegador, después de escribir ‘ http://www.facebook.com/&#039 ;. Es decir, la barra de direcciones debería verse así:
‘ http://www.facebook.com/&#039 ; (sin las comillas y corchetes angulares). Lo que queda, solo presiona Enter. (Asegúrese de que todavía está conectado a su cuenta de Facebook)
Ahora, serás redirigido a la línea de tiempo de ese amigo tuyo, que Facebook considera que es lo más importante para ti. Siendo más realista, esta sería la línea de tiempo de la persona que tiene el rango de borde más alto contigo.

Cada acción que toman tus amigos es una historia potencial de noticias. Facebook llama a estas acciones “Bordes”. Eso significa que cada vez que un amigo publica una actualización de estado, comenta otra actualización de estado, etiqueta una foto, se une a una página de admiradores o confirma su asistencia a un evento que genera un “Edge”, y una historia sobre ese Edge podría aparecer en el personal del usuario noticias. Sería completamente abrumador si el suministro de noticias mostrara todas las historias posibles de tus amigos. Así que Facebook desarrolló un algoritmo para predecir cuán interesante será cada historia para cada usuario, y llama a este algoritmo “EdgeRank” porque clasifica los bordes. Luego, filtran el suministro de noticias de cada usuario para mostrar solo las historias mejor clasificadas para ese usuario en particular.

Volviendo a lo que habrías visto, siguiendo el truco, esto es lo que forma la base de esas molestas aplicaciones que dicen descubrir quién vio tu perfil o quién está enamorado de ti. Nunca se deje engañar por tales aplicaciones. Ahora puede continuar y probar la lista completa. Simplemente copie los números, uno por uno, y haga lo que se le indique, y descubrirá las filas de sus amigos.

No entremos en detalles acerca de cómo se puede considerar esta acción como objetivación de las emociones, pero si estás interesado en la adolescencia, puedes leer este artículo brillantemente escrito, La relevancia de los algoritmos, del profesor Tarleton Gillespie de la Universidad de Cornell.

Fuente y lectura adicional:
http://edgerank.net/

No sé cómo exactamente Facebook almacena sus datos. Pero según la API Graph de Facebook, puedo explicar la posible forma en que los datos podrían haberse almacenado.

La relación de ‘amistad’ de Facebook

Facebook parece usar estructuras mucho más complejas porque usa listas de amigos para permitir a los usuarios organizar a sus amigos . Primero explicaré una relación de ‘amistad’ mucho más simple.

En primer lugar, necesitamos una entidad de usuario (que represente a los usuarios) que se pueda representar en una sola tabla. Esta tabla podría ser el perfil en sí mismo o uno mucho más simple para representar al usuario.

Esto parece bastante simple para mí (incluya nombre, nombre, etc., si lo desea). Aquí puede encontrar los atributos reales de la tabla de usuario que usa Facebook (o al menos lo que se puede acceder a través de la API): usuario. El atributo UserID (columna) es la clave principal y se hace referencia desde cualquier otro lugar.

Ahora necesitaremos una tabla que represente la amistad de dos usuarios. El diagrama de relación se vería así

Y la mesa se vería así.

En esta tabla, las columnas Usuario_a y Usuario_b son claves foráneas que hacen referencia a la ID de usuario de la tabla de usuario. Ahora, una entrada (1, 123, 456) representaría que el usuario con UserID = 123 es amigo del usuario con UserID = 456 (podemos incluir la entrada (1, 456, 123) para significar que user_456 también es amigo de usuario_123).
Entonces, para verificar si un user_x es amigo de user_y solo necesitamos verificar la existencia de una fila (cualquier ID de Amistad, usuario_x_id, usuario_y_id) o (cualquier ID de Amistad, usuario_y_id, usuario_x_id). Una consulta sql se vería así

SELECCIONE * DE Amistad
DONDE (Usuario_a = usuario_x_id Y Usuario_b = usuario_y_id)
OR (Usuario_a = usuario_y_id Y Usuario_b = usuario_x_id);

Si el resultado de la consulta no está vacío, User_x y User_y son amigos, de lo contrario no lo son.
Y finalmente, para enumerar todos los amigos del usuario con UserID = XYZ, la consulta se vería así

SELECCIONAR Usuario_b
De la amistad
DONDE Usuario_a = XYZ

UNIÓN

SELECCIONAR Usuario_a
De la amistad
DONDE Usuario_b = XYZ;

Espero que esto ayude. Intentaré agregar cómo se puede administrar la lista de amigos más adelante.

Facebook está utilizando TAO, un sistema de almacenamiento de datos distribuido para almacenar y recuperar gráficos sociales. Antes de implementar TAO, Facebook usaba memcache y MySql. Para que las recuperaciones sean rápidas y eficientes, introdujeron TAO, un sistema distribuido optimizado de alta lectura.

TAO implementa una abstracción gráfica directamente, lo que le permite evitar algunas de las deficiencias fundamentales de una arquitectura de caché de aspecto lateral. TAO continúa usando MySQL para el almacenamiento persistente, pero media el acceso a la base de datos y usa su propia caché con capacidad para gráficos.

https://www.facebook.com/notes/f …

https://cs.uwaterloo.ca/~brecht/ …

TAO: el almacén de datos distribuidos de Facebook para el gráfico social

Consulte también la respuesta de Venkat Venkataramani para la siguiente pregunta:
¿Para qué se usa el caché TAO en Facebook?

Cada usuario tiene una identificación única en una única “tabla de usuarios”.
Entonces, supongamos que Jane tiene id 1 y Alice tiene id 2.

Hay una “tabla de búsqueda” que tiene columnas (user_id, friend_id).

La tabla de búsqueda solo necesita una entrada con cada una de sus identificaciones, por ejemplo (1,2), para decir que Alice es amiga de Jane, pero requeriría dos consultas para encontrar a los amigos de Jane:
1) encuentre la identificación de amigo donde user_id = 1, y
2) encuentra la identificación del usuario donde friend_id = 1

Para el rendimiento, es probable que inserten dos registros cada vez que se acepte una solicitud de amistad, por ejemplo
(1,2) y (2,1)
luego elimine los mismos dos registros cada vez que el par esté “sin amigos”. De esa forma, obtener una lista de amigos solo requiere la primera consulta anterior.

Sería tentador hacer un inserto cuando se realiza una solicitud, por ejemplo (1,2), y el segundo inserto cuando se acepta la solicitud (2,1). El problema con esto es que una consulta en busca de los amigos de Jane mostrará a Alice, incluso si aún no la acepta.

Cuando las tablas se “unen”, coloca las filas de diferentes tablas una al lado de la otra donde las columnas especificadas coinciden de acuerdo con una consulta (una consulta es un código estructurado que solicita información a una base de datos)

La unión sería (en inglés simple):

Obtenga ID de amigo de la tabla de búsqueda donde ID de usuario = ID de Jane (1)

Luego, únase a la tabla de usuarios donde id = friend_id en la tabla de búsqueda.

Si estas son las tablas (y columnas):
Tabla de búsqueda (user_id, friend_id)
Tabla de usuario (id, nombre)

Aquí hay un resultado de ejemplo
(1,2) (2, Alicia)

Puede ver que la segunda columna (friend_id 2) en la tabla de búsqueda coincide con la columna de identificación (id 2) en la tabla de usuarios.

Puede seleccionar más columnas e incluso unir más tablas para obtener más información sobre los amigos, por ejemplo, cómo se conocen o si también son uno de sus amigos, o un amigo de un amigo, y así sucesivamente. Recomendaría evitar las subconsultas y buscar y “5nf” si está aprendiendo o en el proceso de diseño de una base de datos.

PD: No trabajo para Facebook, aunque sería divertido.

Facebook utiliza bases de datos de gráficos personalizados, el punto de vista es bastante diferente de lo que cabría esperar del diseño tradicional de bases de datos.

Aquí hay un artículo de Facebook TAO: El poder del gráfico

Y aquí hay una base de datos con la que puede jugar: Neo4j, la base de datos de gráficos líder en el mundo

Lo simplificaré un poco, pero desde la perspectiva lógica es muy básico de todos modos.

Hay una tabla con columnas (id1, id2, time), (id1, id2) es un PK, hay un índice secundario en (id1, time).

Eso permite verificar rápidamente si id1 es un amigo con id2, así como darle a X últimos amigos. Técnicamente, leer amigos ordenados por tiempo realmente no importa, ya que TAO generalmente almacena en caché la lista de amigos completa (de todos modos tiene un límite), pero es bueno tener consistencia aquí y allá.

Aunque no hay una “tabla para cada usuario”, es un entorno fragmentado, y cada fragmento tendrá una tabla de ‘amigos’ para los usuarios de ese fragmento, por lo que técnicamente será una tabla por usuario X.

Una consideración importante que considero digna de inclusión es el concepto de “consistencia eventual”.

Muy pocos sistemas distribuidos verdaderamente grandes implementan actualizaciones en tiempo real de datos “no críticos”. (Al igual que la belleza, ¡todo espectador del sistema decide qué pertenece a esta categoría!)

Las relaciones de gráficos grandes son mucho más fáciles de lograr utilizando una arquitectura basada en mensajes desacoplados que aprovecha la “coherencia eventual”.

(Hice una búsqueda rápida en la página y no la encontré mencionada, así que me disculpo si esto ya ha sido cubierto).

Para hacer frente a un volumen de datos sin precedentes, Facebook inventó Apache Hive, una aplicación que se ejecuta en Hadoop y proporciona acceso de tipo SQL a datos muy grandes.

Hay muchas bases de datos de gráficos de código abierto disponibles, como Neo4j, Titan, etc.
Facebook tiene su propio gráfico Db y mecanismo de búsqueda llamado “Unicornio”