Conception de la base de données de Facebook ?

Question

J'ai toujours demandé comment Facebook a conçu la relation ami <-> utilisateur.

Je suppose que la table utilisateur est quelque chose comme ceci:

user_email PK
user_id PK
password 

Je suppose que la table avec les données de l'utilisateur (sexe, âge, etc. connecté via l'e-mail de l'utilisateur je suppose).

Comment relie-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 s'étendre.

Answer 1

Gardez une table d'amis qui contient l'ID utilisateur et ensuite l'ID de l'ami (nous l'appellerons FriendID). Les deux colonnes seraient des clés étrangères renvoyant à la table Users.

Exemple quelque peu utile:

Nom de la table: User
Colonnes:
    UserID PK
    Adresse email
    Mot de passe
    Genre
    Date de naissance
    Lieu

Nom de la table: Amis
Colonnes:
    UserID PK FK
    FriendID PK FK
    (Cette table comporte une clé primaire composite composée des deux clés 
     étrangères, pointant toutes deux vers la table utilisateur. Un ID pointera vers
     l'utilisateur connecté, l'autre ID pointera vers l'ami individuel
     de cet utilisateur)

Exemple d'utilisation:

Table Utilisateur
--------------
UserID Adresse email Mot de passe Genre Date de naissance Lieu
------------------------------------------------------
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 Amis
---------------
UserID FriendID
----------------
1      2
1      3
2      3

Cela montrera que Bob est ami à la fois avec Jon et Joe et que Jon est également ami avec Joe. Dans cet exemple, nous supposerons que l'amitié est toujours réciproque, donc vous n'auriez pas besoin d'une ligne dans la table telle que (2,1) ou (3,2) car elles sont déjà représentées dans l'autre sens. Pour des exemples où l'amitié ou d'autres relations ne sont pas explicitement réciproques, vous devriez également avoir ces lignes pour indiquer la relation réciproque.

Answer 2

TL;DR:

Ils utilisent une architecture de pile avec des graphiques mis en cache pour tout ce qui se trouve au-dessus de la base de données MySQL au bas de leur pile.

Réponse longue:

J'ai fait quelques recherches moi-même car j'étais curieux de savoir comment ils gèrent leur énorme quantité de données et les recherchent de manière rapide. J'ai vu des gens se plaindre que les scripts de réseaux sociaux personnalisés deviennent lents lorsque la base d'utilisateurs s'agrandit. Après avoir fait quelques tests avec seulement 10k utilisateurs et 2,5 millions de connexions d'amis - sans même essayer de me soucier des permissions de groupe et des likes et des publications sur le mur - il s'est rapidement avéré que cette approche est défectueuse. J'ai donc passé du temps à chercher sur le web comment faire mieux et je suis tombé sur cet article officiel de Facebook :

• TAO: Magasin de données distribué de Facebook pour le graphique social
• TAO: Le pouvoir du graphique.

Je vous recommande vraiment de regarder la présentation du premier lien ci-dessus avant de continuer à lire. C'est probablement la meilleure explication de comment FB fonctionne en coulisses que vous puissiez trouver.

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

• Ils utilisent MySQL tout en bas de leur pile
• Au-dessus de la base de données SQL, il y a 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 BD qu'ils utilisent réellement pour leurs graphiques mis en cache.

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

Eh bien, c'est un graphique. :) Cela ne vous dit pas comment le construire en SQL, il existe plusieurs façons de le faire mais ce site propose différentes approches. Attention : Considérez qu'une BD relationnelle est ce qu'elle est : elle est conçue pour stocker des données normalisées, pas une structure de graphique. Donc, elle ne fonctionnera pas aussi bien qu'une base de données de graphiques spécialisée.

Considérez également que vous devez effectuer des requêtes plus complexes que simplement des amis d'amis, par exemple lorsque vous voulez filtrer tous les emplacements autour d'une coordonnée donnée que vous et vos amis d'amis aiment. 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 des tests de performance.

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

Schéma de BD :

CREATE TABLE IF NOT EXISTS `amis` (
`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 des 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 quelques données d'exemple avec au moins 10k enregistrements d'utilisateurs et chacun 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 de ~0,18 secondes pour cette requête. Peut-être peut-elle être optimisée, je ne suis pas un génie de la BD (les suggestions sont les bienvenues). Cependant, si cela évolue de manière linéaire, vous êtes déjà à 1,8 seconde pour seulement 100k utilisateurs, 18 secondes pour 1 million d'utilisateurs.

Cela peut encore sembler OK pour ~100k utilisateurs, mais considérez que vous venez de rechercher des amis des amis et que vous n'avez pas effectué de requête plus complexe comme "affichez-moi uniquement des publications des amis des amis + effectuez la vérification des autorisations pour voir si je suis autorisé ou NON autorisé à en voir certaines + effectuez une sous-requête pour vérifier si j'ai aimé l'une d'elles". Vous voulez laisser la BD vérifier si vous avez aimé une publication ou non, sinon 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'un utilisateur actif en même temps sur un site plus ou moins populaire.

Je pense que ma réponse explique bien comment Facebook a conçu sa relation d'amis, mais je suis désolé de ne pas pouvoir vous dire comment l'implémenter de manière à ce qu'elle fonctionne rapidement. Mettre en place un réseau social est facile, mais s'assurer qu'il fonctionne bien clairement pas - à mon avis.

J'ai commencé à expérimenter avec OrientDB pour effectuer des requêtes de graphiques et mapper mes arêtes à la BD SQL sous-jacente. Si j'y parviens, j'écrirai un article à ce sujet.

Comment puis-je créer un site de réseau social performant ?

Mise à jour 10/04/2021 : Je n'écrirai probablement jamais l'article ;) mais voici quelques points principaux sur la manière dont vous pourriez essayer de le mettre à l'échelle :

• Utiliser des référentiels de lecture et d'écriture différents
• Construire des référentiels de lecture spécifiques basés sur des systèmes de BD non relationnelles plus rapides conçus à cet effet, ne pas avoir peur de dénormaliser les données. Écrire dans une BD normalisée mais lire à partir de vues spécialisées.
• Utiliser la cohérence éventuelle
• Jeter un œil au CQRS
• Pour un réseau social, des référentiels de lecture basés sur des graphiques peuvent également être une bonne idée.
• Utiliser Redis en tant que référentiel de lecture dans lequel vous stockez des ensembles de données entièrement sérialisées

Si vous combinez les points de la liste ci-dessus de manière intelligente, vous pouvez construire un système très performant. La liste n'est pas une liste de tâches à faire, vous devrez toujours comprendre, réfléchir et l'adapter ! https://microservices.io/ est un site intéressant qui couvre quelques-uns des sujets que j'ai mentionnés auparavant.

Ce que je fais, c'est stocker des événements générés par des agrégats et utiliser des projets et des gestionnaires pour écrire dans des BD différentes comme mentionné ci-dessus. L'avantage de cela est que je peux reconstruire mes données selon les besoins à tout moment.

Answer 3

Jetez un œil au schéma de base de données suivant, reverse engineered by Anatoly Lubarsky:

Answer 4

Ma meilleure hypothèse est qu'ils ont créé une structure de graphe. Les nœuds sont des utilisateurs et les "amitiés" sont des arêtes.

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

Answer 5

C'est probablement une relation de nombreux à plusieurs :

Liste d'amis (table)

user_id -> utilisateurs.user_id
friend_id -> utilisateurs.user_id
friendVisibilityLevel

MODIFICATION

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

utilisateurs (table)

user_id PK
user_email
password