yoast open depurer debugger checker sql facebook database-design database-normalization database-table

sql - open - Diseño de base de datos de Facebook?



open graph tags (13)

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

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. conectados 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 la cantidad de usuarios es desconocida y se expandirá.

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

Obviamente, necesitarías algunas particiones e índices, y no vas a mantener eso en la memoria para todos los usuarios.

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

También hay "Big Data: puntos de vista del equipo de datos de Facebook" que pueden ser útiles:

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 las utilizan algunas empresas:

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 memoria caché de datos y otros conceptos de nivel superior de los que la mayoría de nosotros nunca manejamos a diario. O al menos, tal vez no sepamos que sí.

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

ACTUALIZACIÓN 20/10/2014

Murat Demirbas escribió un resumen sobre

  • TAO: 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

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

Esquema de ejemplo:

Users Table userID PK other data Friends Table userID -- FK to users''s table representing the user that has a friend. friendID -- FK to Users'' table representing the user id of the friend

Lo más probable es una relación de muchos a muchos:

FriendList (mesa)

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

EDITAR

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

usuarios (tabla)

user_id PK user_email password

Mantenga una tabla de amigos que contenga el UserID y luego el UserID del amigo (lo llamaremos FriendID). Ambas columnas serían claves externas 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 [email protected] bobbie M 1/1/2009 New York City 2 [email protected] jonathan M 2/2/2008 Los Angeles 3 [email protected] 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 donde la amistad u otras relaciones no son explícitamente bidireccionales, también necesitaría tener esas filas para indicar la relación bidireccional.

Mi mejor opción es que hayan creado una estructura de gráfico . Los nodos son usuarios y las "amistades" son bordes.

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.

No es posible recuperar datos de RDBMS para los datos de los amigos del usuario que cruzan más de medio billón en un tiempo constante, así que Facebook implementó esto usando una base de datos hash (sin SQL) y abrió la base de datos llamada Cassandra.

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

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

Probablemente haya una tabla, que almacene la relación de usuario friend <->, digamos "frnd_list", con los campos ''user_id'', ''frnd_id''.

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

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

Ahora, al mostrar la lista de amigos a un usuario en particular, un simple sql haría eso: "select frnd_id from frnd_list where user_id =" donde está el id del usuario conectado (almacenado como un atributo de sesión).

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)

TL; DR:

Usan 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:

Hice algunas investigaciones sobre esto porque tenía curiosidad sobre cómo manejar su gran cantidad de datos y buscarlos de manera rápida. He visto gente quejándose de que las secuencias de comandos de redes sociales hechas a medida se vuelven lentas cuando crece la base de usuarios. Después de hacer algunos puntos de referencia con solo 10 mil usuarios y 2,5 millones de conexiones de amigos , sin siquiera tratar de preocuparme por los permisos del grupo y los me gusta y las publicaciones en el muro, rápidamente resultó que este enfoque es defectuoso. Así que dediqué un tiempo a buscar en Internet cómo hacerlo mejor y encontré este artículo oficial de Facebook:

Realmente te recomiendo que veas la presentación del primer enlace de arriba antes de seguir leyendo. Probablemente sea la mejor explicación de cómo funciona FB detrás de las escenas que puedes encontrar.

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

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

Echemos un vistazo a esto, las conexiones de amigos están arriba a la 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 un DB 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 de gráficos especializados.

Además, tenga en cuenta que debe realizar consultas más complejas que solo amigos de amigos, por ejemplo, cuando desea filtrar todas las ubicaciones alrededor de una determinada coordenada que usted y sus amigos amigos les gustan. Un gráfico es la solución perfecta aquí.

No puedo decirle 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 los resultados solo 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;

Amigos de amigos consulta:

( 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 te recomiendo que crees algunos datos de muestra con al menos 10k registros de usuarios y cada uno de ellos tenga al menos 250 conexiones de amigos y luego ejecuta esta consulta. En mi máquina (i7 4770k, SSD, 16 gb RAM) el resultado fue ~ 0.18 segundos para esa consulta. Tal vez se puede optimizar, no soy un genio DB (las sugerencias son bienvenidas). Sin embargo, si esto se escala linealmente, ya está a 1.8 segundos para solo 100k usuarios, 18 segundos para 1 millón de usuarios.

Esto todavía puede sonar bien para ~ 100k usuarios, pero considere que acaba de buscar amigos de amigos y no hizo ninguna consulta más compleja como " mostrar solo publicaciones de amigos de amigos + hacer la verificación de permisos si estoy permitido o NO permitido" ver algunos de ellos + hacer una sub consulta para verificar si me gustó alguno de ellos ". Desea dejar que DB controle si le gustó una publicación o no, o tendrá que hacerlo en el código. Además, tenga en cuenta que esta no es la única consulta que ejecuta y que tiene más que usuarios activos 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 la relación de sus amigos, pero lamento que no pueda decirte cómo implementarla de manera que funcione rápido. Implementar una red social es fácil, pero asegurarse de que tenga un buen rendimiento es claramente - en mi humilde opinión.

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