Diseño de base de datos de Facebook?

Siempre me he preguntado cómo Facebook diseñó la relación amigo <-> usuario.

Me imagino que la tabla de usuarios es algo como esto:

user_email PK
user_id PK
password 

Calculo la tabla con los datos del usuario (sexo, edad, etc. conectado a través del correo electrónico del usuario, supongo).

¿Cómo conecta a todos los amigos con este usuario?

¿Algo como esto?

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N 

Probablemente no. Porque el número de usuarios es desconocido y se expandirá.

Mantenga una tabla de amigos que contenga el ID de usuario y luego el ID de usuario del amigo (lo llamaremos FriendID). Ambas columnas serían claves foráneas para volver a la tabla Usuarios.

Ejemplo algo útil:

Table Name: User
Columns:
    UserID PK
    EmailAddress
    Password
    Gender
    DOB
    Location

TableName: Friends
Columns:
    UserID PK FK
    FriendID PK FK
    (This table features a composite primary key made up of the two foreign 
     keys, both pointing back to the user table. One ID will point to the
     logged in user, the other ID will point to the individual friend
     of that user)

Ejemplo de uso:

Table User
--------------
UserID EmailAddress Password Gender DOB      Location
------------------------------------------------------
1      bob@bob.com  bobbie   M      1/1/2009 New York City
2      jon@jon.com  jonathan M      2/2/2008 Los Angeles
3      joe@joe.com  joseph   M      1/2/2007 Pittsburgh

Table Friends
---------------
UserID FriendID
----------------
1      2
1      3
2      3

Esto demostrará que Bob es amigo de Jon y Joe y que Jon también es amigo de Joe. En este ejemplo asumiremos que la amistad siempre es de dos maneras, por lo que no necesitaría una fila en la tabla como (2,1) o (3,2) porque ya están representadas en la otra dirección. Para ejemplos en los que la amistad u otras relaciones no son explícitamente bidireccionales, también debería tener esas filas para indicar la relación bidireccional.

Eche un vistazo al siguiente esquema de base de datos, diseñado por Anatoly Lubarsky :

TL; DR:

Utilizan una arquitectura de pila con gráficos en caché para todo lo que está por encima de la parte inferior de MySQL de su pila.

Respuesta larga:

Investigué un poco sobre esto yo mismo porque tenía curiosidad sobre cómo manejan su gran cantidad de datos y los buscan de manera rápida. He visto a personas quejarse de que los scripts de redes sociales personalizados se vuelven lentos cuando crece la base de usuarios. Después de hacer una evaluación comparativa con solo 10k usuarios y 2.5 millones de conexiones de amigos , sin siquiera tratar de preocuparme por los permisos de grupo, los me gusta y las publicaciones en el muro, rápidamente resultó que este enfoque es defectuoso. Así que pasé un tiempo buscando en la web cómo hacerlo mejor y encontré este artículo oficial de Facebook:

• TAO: el almacén de datos distribuidos de Facebook para el gráfico social
• TAO: El poder del gráfico .

Yo realmente recomiendo que ver la presentación del primer eslabón anterior antes de continuar leyendo. Probablemente sea la mejor explicación de cómo funciona FB detrás de escena que puedes encontrar.

El video y el artículo te dicen algunas cosas:

• Están usando MySQL en la parte inferior de su pila
• Encima de la base de datos SQL está la capa TAO que contiene al menos dos niveles de almacenamiento en caché y está usando gráficos para describir las conexiones.
• No pude encontrar nada sobre qué software / DB realmente usan para sus gráficos en caché

Echemos un vistazo a esto, las conexiones de amigos están en la parte superior izquierda:

Bueno, esto es un gráfico. :) No te dice cómo construirlo en SQL, hay varias formas de hacerlo, pero este sitio tiene una buena cantidad de enfoques diferentes. Atención: considere que una base de datos relacional es lo que es: se cree que almacena datos normalizados, no una estructura gráfica. Por lo tanto, no funcionará tan bien como una base de datos gráfica especializada.

También considere que tiene que hacer consultas más complejas que solo amigos de amigos, por ejemplo, cuando desea filtrar todas las ubicaciones alrededor de una coordenada dada que les guste a usted y a sus amigos de amigos. Un gráfico es la solución perfecta aquí.

No puedo decirte cómo construirlo para que funcione bien, pero claramente requiere algo de prueba y error y evaluación comparativa.

Aquí está mi prueba decepcionante para solo encontrar amigos de amigos:

Esquema DB:

CREATE TABLE IF NOT EXISTS `friends` (
`id` int(11) NOT NULL,
  `user_id` int(11) NOT NULL,
  `friend_id` int(11) NOT NULL
) ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=utf8;

Consulta de amigos de amigos:

(
        select friend_id
        from friends
        where user_id = 1
    ) union (
        select distinct ff.friend_id
        from
            friends f
            join friends ff on ff.user_id = f.friend_id
        where f.user_id = 1
    )

Realmente le recomiendo que cree algunos datos de muestra con al menos 10k registros de usuario y cada uno de ellos tenga al menos 250 conexiones de amigos y luego ejecute esta consulta. En mi máquina (i7 4770k, SSD, 16 gb de RAM) el resultado fue ~ 0.18 segundos para esa consulta. Tal vez se pueda optimizar, no soy un genio de DB (las sugerencias son bienvenidas). Sin embargo, si esto escala lineal, ya tiene 1,8 segundos para solo 100k usuarios, 18 segundos para 1 millón de usuarios.

Esto todavía puede sonar aceptable para ~ 100k usuarios, pero tenga en cuenta que acaba de buscar amigos de amigos y no realizó ninguna consulta más compleja como " mostrarme solo publicaciones de amigos de amigos + hacer la verificación de permisos si estoy permitido o NO permitido para ver algunos de ellos + hacer una subconsulta para verificar si me gustó alguno de ellos ". Desea permitir que la base de datos verifique si ya le gustó una publicación o no, o tendrá que hacerlo en código. También considere que esta no es la única consulta que ejecuta y que tiene un usuario más que activo al mismo tiempo en un sitio más o menos popular.

Creo que mi respuesta responde a la pregunta de cómo Facebook diseñó muy bien su relación de amigos, pero lamento no poder decirle cómo implementarla de una manera que funcione rápidamente. Implementar una red social es fácil, pero asegurarse de que funcione bien claramente no lo es, en mi humilde opinión.

Comencé a experimentar con OrientDB para hacer consultas gráficas y asignar mis bordes a la base de datos SQL subyacente. Si alguna vez lo hago, escribiré un artículo al respecto.

Mi mejor apuesta es que crearon una estructura gráfica . Los nodos son usuarios y las "amistades" son aristas.

Mantenga una tabla de usuarios, mantenga otra tabla de bordes. Luego puede guardar datos sobre los bordes, como "día en que se hicieron amigos" y "estado aprobado", etc.

Es muy probable que sea una relación de muchos a muchos:

Lista de amigos (tabla)

user_id -> users.user_id
friend_id -> users.user_id
friendVisibilityLevel

EDITAR

La tabla de usuarios probablemente no tiene user_email como PK, aunque posiblemente como una clave única.

usuarios (tabla)

user_id PK
user_email
password

Eche un vistazo a estos artículos que describen cómo se crean LinkedIn y Digg:

• http://hurvitz.org/blog/2008/06/linkedin-architecture
• http://highscalability.com/scaling-digg-and-other-web-applications

También hay "Big Data: puntos de vista del equipo de datos de Facebook" que podría ser útil:

http://developer.yahoo.net/blogs/theater/archives/2008/01/nextyahoonet_big_data_viewpoints_from_the_fac.html

Además, hay un artículo que habla sobre bases de datos no relacionales y cómo son utilizadas por algunas compañías:

http://www.readwriteweb.com/archives/is_the_relational_database_doomed.php

Verá que estas empresas se ocupan de almacenes de datos, bases de datos particionadas, almacenamiento en caché de datos y otros conceptos de nivel superior que la mayoría de nosotros nunca tratamos a diario. O al menos, tal vez no sabemos que sí.

Hay muchos enlaces en los dos primeros artículos que deberían darle más información.

ACTUALIZACIÓN 20/10/2014

Murat Demirbas escribió un resumen sobre

• TAO: el almacén de datos distribuidos de Facebook para el gráfico social (ATC'13)
• F4: el cálido sistema de almacenamiento BLOB de Facebook (OSDI'14)

http://muratbuffalo.blogspot.com/2014/10/facebooks-software-architecture.html

HTH

No es posible recuperar datos de RDBMS para datos de amigos de usuarios para datos que cruzan más de 500 millones a la vez, por lo que Facebook implementó esto usando una base de datos hash (sin SQL) y abrieron la base de datos llamada Cassandra.

Por lo tanto, cada usuario tiene su propia clave y los detalles de los amigos en una cola; para saber cómo funciona cassandra mira esto:

http://prasath.posterous.com/cassandra-55

Esta publicación reciente de junio de 2013 entra en algunos detalles para explicar la transición de bases de datos de relaciones a objetos con asociaciones para algunos tipos de datos.

https://www.facebook.com/notes/facebook-engineering/tao-the-power-of-the-graph/10151525983993920

Hay un documento más largo disponible en https://www.usenix.org/conference/atc13/tao-facebook's-distributed-data-store-social-graph

Estás buscando claves foráneas. Básicamente, no puede tener una matriz en una base de datos a menos que tenga su propia tabla.

Esquema de ejemplo:

    Tabla de usuarios
        ID de usuario PK
        otros datos
    Mesa de amigos
        ID de usuario: FK a la tabla de usuarios que representa al usuario que tiene un amigo.
        friendID - FK a la tabla de usuarios que representa la identificación de usuario del amigo

Es un tipo de base de datos de gráficos: http://components.neo4j.org/neo4j-examples/1.2-SNAPSHOT/social-network.html

No está relacionado con bases de datos relacionales.

Google para bases de datos gráficas.

Tenga en cuenta que las tablas de la base de datos están diseñadas para crecer verticalmente (más filas), no horizontalmente (más columnas)

Con respecto al rendimiento de una tabla de muchos a muchos, si tiene 2 entradas de 32 bits que vinculan ID de usuario, su almacenamiento de datos básicos para 200,000,000 de usuarios con un promedio de 200 amigos cada uno es de menos de 300 GB.

Obviamente, necesitaría un poco de particionamiento e indexación y no lo va a mantener en la memoria para todos los usuarios.

Probablemente hay una tabla, que almacena la relación de amigo <-> usuario, digamos "frnd_list", que tiene los campos 'user_id', 'frnd_id'.

Cada vez que un usuario agrega a otro usuario como amigo, se crean dos filas nuevas.

Por ejemplo, supongamos que mi identificación es 'deep9c' y agrego un usuario que tiene la identificación 'akash3b' como mi amigo, luego se crean dos nuevas filas en la tabla "frnd_list" con valores ('deep9c', 'akash3b') y ('akash3b ',' deep9c ').

Ahora, cuando se muestra la lista de amigos a un usuario en particular, un simple sql haría eso: "seleccione frnd_id de frnd_list donde user_id =" donde está la identificación del usuario conectado (almacenado como un atributo de sesión).