Conception de base de données Facebook?

Je me suis toujours demandé comment Facebook avait conçu la relation utilisateur ami <->.

Je pense que la table des utilisateurs ressemble à ceci:

user_email PK
user_id PK
password 

Je figure le tableau avec les données de l'utilisateur (sexe, âge, etc. connecté via l'email de l'utilisateur, je suppose).

Comment connecte-t-il tous les amis à cet utilisateur?

Quelque chose comme ça?

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N 

Probablement pas. Parce que le nombre d'utilisateurs est inconnu et va augmenter.

Gardez une table d'amis qui contient le UserID puis le UserID de l'ami (nous l'appellerons FriendID). Les deux colonnes seraient des clés étrangères de la table Users.

Exemple un peu utile:

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)

Exemple d'utilisation:

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

Cela montrera que Bob est ami avec Jon et Joe et que Jon est également ami avec Joe. Dans cet exemple, nous supposerons que l'amitié est toujours de deux manières, vous n'aurez donc pas besoin d'une ligne dans le tableau comme (2,1) ou (3,2) car elles sont déjà représentées dans l'autre sens. Pour les exemples où l'amitié ou d'autres relations ne sont pas explicitement bidirectionnelles, vous devez également avoir ces lignes pour indiquer la relation bidirectionnelle.

Jetez un œil au schéma de base de données suivant, conçu par Anatoly Lubarsky :

TL; DR:

Ils utilisent une architecture de pile avec des graphiques en cache pour tout ce qui se trouve au-dessus du bas de MySQL de leur pile.

Longue réponse:

J'ai fait des recherches à ce sujet moi-même parce que j'étais curieux de savoir comment ils gèrent leur énorme quantité de données et les recherchent rapidement. J'ai vu des gens se plaindre de la lenteur des scripts de réseaux sociaux personnalisés lorsque la base d'utilisateurs augmente. Après avoir moi-même effectué des analyses comparatives avec seulement 10 000 utilisateurs et 2,5 millions de connexions d' amis - sans même essayer de me soucier des autorisations de groupe, des likes et des publications sur le mur - il s'est rapidement avéré que cette approche était imparfaite. J'ai donc passé du temps à chercher sur le Web comment le faire mieux et je suis tombé sur cet article officiel de Facebook:

• TAO: le magasin de données distribué de Facebook pour le graphe social
• TAO: La puissance du graphique .

Je vous recommande vraiment de regarder la présentation du premier lien ci-dessus avant de continuer la lecture. C'est probablement la meilleure explication du fonctionnement de FB dans les coulisses que vous puissiez trouver.

La vidéo et l'article vous disent plusieurs choses:

• Ils utilisent MySQL tout en bas de leur pile
• Au - dessus de la base de données SQL se trouve la couche TAO qui contient au moins deux niveaux de mise en cache et utilise des graphiques pour décrire les connexions.
• Je n'ai rien trouvé sur le logiciel / la base de données qu'ils utilisent réellement pour leurs graphiques en cache

Jetons un coup d'œil à ceci, les connexions d'amis sont en haut à gauche:

Eh bien, c'est un graphique. :) Il ne vous dit pas comment le construire en SQL, il y a plusieurs façons de le faire mais ce site a un bon nombre d'approches différentes. Attention: Considérez qu'une base de données relationnelle est ce qu'elle est: on pense qu'elle stocke des données normalisées, pas une structure graphique. Il ne fonctionnera donc pas aussi bien qu'une base de données de graphes spécialisée.

Considérez également que vous devez faire des requêtes plus complexes que de simples amis d'amis, par exemple lorsque vous souhaitez filtrer tous les emplacements autour d'une coordonnée donnée que vous et vos amis d'amis aimez. Un graphique est la solution parfaite ici.

Je ne peux pas vous dire comment le construire pour qu'il fonctionne bien, mais cela nécessite clairement des essais et des erreurs et une analyse comparative.

Voici mon test décevant pour trouver juste des amis d'amis:

Schéma de base de données:

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;

Requête des amis d'amis:

(
        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
    )

Je vous recommande vraiment de créer des exemples de données avec au moins 10k enregistrements d'utilisateurs et chacun d'entre eux ayant au moins 250 connexions d'amis, puis d'exécuter cette requête. Sur ma machine (i7 4770k, SSD, 16 Go de RAM), le résultat était d' environ 0,18 seconde pour cette requête. Peut-être qu'il peut être optimisé, je ne suis pas un génie de la DB (les suggestions sont les bienvenues). Cependant, si cela évolue de manière linéaire, vous êtes déjà à 1,8 seconde pour seulement 100 000 utilisateurs, 18 secondes pour 1 million d'utilisateurs.

Cela peut sembler correct pour ~ 100 000 utilisateurs, mais considérez que vous venez de récupérer des amis d'amis et que vous n'avez pas fait de requête plus complexe comme " affichez-moi uniquement les messages d'amis d'amis d'amis + vérifiez les autorisations si je suis autorisé ou non pour voir certains d'entre eux + faire une sous-requête pour vérifier si je les ai aimés ". Vous voulez laisser la base de données vérifier si vous avez déjà aimé un message ou non ou si vous devrez le faire dans le code. Considérez également que ce n'est pas la seule requête que vous exécutez et que vous avez plus d'utilisateurs actifs en même temps sur un site plus ou moins populaire.

Je pense que ma réponse répond à la question de savoir comment Facebook a très bien conçu sa relation entre amis, mais je suis désolé de ne pas pouvoir vous dire comment la mettre en œuvre de manière à ce qu'elle fonctionne rapidement. La mise en œuvre d'un réseau social est facile mais s'assurer qu'il fonctionne bien n'est clairement pas - à mon humble avis.

J'ai commencé à expérimenter avec OrientDB pour faire les requêtes de graphes et mapper mes bords à la base de données SQL sous-jacente. Si jamais je le fais, j'écrirai un article à ce sujet.

Mon meilleur pari est qu'ils ont créé une structure graphique . Les nœuds sont des utilisateurs et les «amitiés» sont des bords.

Gardez une table des utilisateurs, gardez une autre table des arêtes. Ensuite, vous pouvez conserver des données sur les bords, comme "le jour où ils sont devenus amis" et "le statut approuvé", etc.

Il s'agit probablement d'une relation plusieurs à plusieurs:

FriendList (tableau)

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

ÉDITER

La table user n'a probablement pas user_email comme PK, peut - être comme clé unique.

utilisateurs (tableau)

user_id PK
user_email
password

Jetez un œil à ces articles décrivant comment LinkedIn et Digg sont construits:

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

Il y a aussi "Big Data: Points de vue de l'équipe Facebook Data" qui pourrait être utile:

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

En outre, il y a cet article qui parle des bases de données non relationnelles et de la façon dont elles sont utilisées par certaines entreprises:

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

Vous verrez que ces entreprises traitent des entrepôts de données, des bases de données partitionnées, de la mise en cache des données et d'autres concepts de plus haut niveau que la plupart d'entre nous ne traitent jamais quotidiennement. Ou du moins, peut-être que nous ne savons pas ce que nous savons.

Il y a beaucoup de liens sur les deux premiers articles qui devraient vous donner un aperçu supplémentaire.

MISE À JOUR 20/10/2014

Murat Demirbas a rédigé un résumé sur

• TAO: magasin de données distribué de Facebook pour le graphe social (ATC'13)
• F4: le système de stockage BLOB chaleureux de Facebook (OSDI'14)

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

HTH

Il n'est pas possible de récupérer les données du SGBDR pour les données des amis utilisateurs pour les données qui traversent plus d'un demi-milliard à un moment constant, Facebook l'a donc implémenté en utilisant une base de données de hachage (pas de SQL) et ils ont ouvert la base de données appelée Cassandra.

Ainsi, chaque utilisateur a sa propre clé et les détails des amis dans une file d'attente; pour savoir comment fonctionne cassandra regardez ceci:

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

Ce récent article de juin 2013 explique en détail la transition des bases de données de relations vers des objets avec des associations pour certains types de données.

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

Un article plus long est disponible sur https://www.usenix.org/conference/atc13/tao-facebook's-distributed-data-store-social-graph

Vous recherchez des clés étrangères. Fondamentalement, vous ne pouvez pas avoir de tableau dans une base de données à moins qu'il n'ait sa propre table.

Exemple de schéma:

    Table des utilisateurs
        ID utilisateur PK
        autre informations
    Table des amis
        userID - FK à la table des utilisateurs représentant l'utilisateur qui a un ami.
        friendID - FK to Users 'table représentant l'ID utilisateur de l'ami

C'est un type de base de données de graphes: http://components.neo4j.org/neo4j-examples/1.2-SNAPSHOT/social-network.html

Ce n'est pas lié aux bases de données relationnelles.

Google pour les bases de données graphiques.

Gardez à l'esprit que les tables de base de données sont conçues pour croître verticalement (plus de lignes), pas horizontalement (plus de colonnes)

En ce qui concerne les performances d'une table plusieurs-à-plusieurs, si vous avez 2 entiers 32 bits reliant les identifiants utilisateur, votre stockage de données de base pour 200 000 000 d'utilisateurs comptant en moyenne 200 amis chacun est un peu moins de 300 Go.

De toute évidence, vous auriez besoin d'un partitionnement et d'une indexation et vous n'allez pas garder cela en mémoire pour tous les utilisateurs.

Il y a probablement une table, qui stocke la relation utilisateur friend <->, par exemple "frnd_list", ayant les champs 'user_id', 'frnd_id'.

Chaque fois qu'un utilisateur ajoute un autre utilisateur comme ami, deux nouvelles lignes sont créées.

Par exemple, supposons que mon identifiant soit 'deep9c' et que j'ajoute un utilisateur ayant l'identifiant 'akash3b' comme ami, puis deux nouvelles lignes sont créées dans la table "frnd_list" avec les valeurs ('deep9c', 'akash3b') et ('akash3b ',' deep9c ').

Maintenant, lors de l'affichage de la liste d'amis à un utilisateur particulier, un simple sql ferait cela: "sélectionnez frnd_id de frnd_list où user_id =" où est l'id de l'utilisateur connecté (stocké comme attribut de session).