Conception de la base de données Facebook?
je me suis toujours demandé comment Facebook avait conçu la relation ami-utilisateur.
je suppose que la table d'utilisateur est quelque chose comme ceci:
user_email PK
user_id PK
password
Je chiffre le tableau avec les données de l'utilisateur (sexe, âge, etc connectés via le courrier électronique 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 se développer.
13 réponses
tenir une table d'ami qui tient L'UserID puis L'UserID de l'ami (nous l'appellerons Friend). Les deux colonnes seraient des clés étrangères de retour à la table des utilisateurs.
exemple assez 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'Usage:
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 à la fois avec Jon et Joe et que Jon est aussi ami avec Joe. Dans cet exemple, nous supposerons que l'amitié est toujours de deux façons, de sorte que vous n'aurait pas besoin d'une ligne dans la table tels que (2,1) ou (3,2) parce qu'ils sont déjà représentés dans l'autre sens. Pour les exemples où l'amitié ou d'autres relations ne sont pas explicitement bidirectionnelles, vous devez aussi avoir ces lignes pour indiquer la relation bidirectionnelle.
regardez le schéma de base de données suivant, reverse engineered by 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 leur pile MySQL.
Longue Réponse:
j'ai fait quelques recherches sur ce moi-même parce que j'étais curieux de savoir comment ils gèrent leur énorme quantité de données et la recherche d'une manière rapide. J'ai vu des gens se plaindre des scripts de réseaux sociaux faits sur mesure devenant lents lorsque l'utilisateur la base de pousse. Après que j'ai fait quelques benchmarking moi - même avec juste 10k utilisateurs et 2,5 millions d'amis connexions - sans même essayer de se soucier des permissions de groupe et aime et les poteaux de mur-il s'est vite avéré que cette approche est défectueuse. J'ai donc passé un certain temps à chercher sur le web pour savoir comment faire mieux et je suis tombé sur cet article officiel de Facebook:
je vraiment vous recommandons 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.
la vidéo et l'article vous disent quelques choses:
- ils utilisent MySQL à la très bas de leur pile
- au-dessus de le DB SQL il y a la couche TAO qui contient au moins deux niveaux de cache et utilise des graphiques pour décrire les connexions.
- je ne pouvais pas trouver quoi que ce soit sur ce logiciel / base de données qu'ils utilisent pour leur mise en cache des graphiques
jetons un coup d'oeil à ceci, les liens d'amis sont en haut à gauche:
C'est un graphique. :) Il ne vous dit pas comment pour le construire en SQL, il ya plusieurs façons de le faire, mais ce site a une bonne quantité d'approches différentes. Attention: considérez qu'un DB relationnel est ce qu'il est: il est pensé pour stocker des données normalisées, pas une structure de graphe. Il ne fonctionnera donc pas aussi bien qu'une base de données graphique spécialisée.
également considérer que vous devez faire des requêtes plus complexes que les amis des amis, par exemple, quand vous voulez filtrer tous les emplacements autour d'une coordonnée donnée que vous et vos amis des amis aiment. Un graphique est la solution parfaite ici.
Je ne peux pas vous dire comment le construire pour qu'il fonctionne bien, mais il nécessite clairement un essai et d'erreur et de benchmarking.
Voici mon décevant test pour juste résultats amis des amis:
DB Schema:
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;
les Amis de Amis de Requête:
(
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 vous créer quelques données d'échantillon avec au moins 10k d'enregistrements d'utilisateurs et chacun d'eux ayant au moins 250 amis connexions et puis exécuter cette requête. Sur ma machine (i7 4770k, SSD, 16 Go RAM) le résultat était ~0,18 secondes pour cette requête. Peut-être qu'il peut être optimisé, Je ne suis pas un génie de la base de données (les suggestions sont les bienvenues). Cependant, si cette balance linéaire vous êtes déjà à 1.8 secondes pour seulement 100k utilisateurs, 18 secondes pour 1 million d'utilisateurs.
cela pourrait encore sembler OKish pour les utilisateurs ~100k mais considérer que vous venez de chercher des amis d'amis et n'avez pas fait de requête plus complexe comme " m'afficher seulement les messages des amis d'amis + Faire la vérification de permission si je suis autorisé ou pas autorisé voir certains d'entre eux + faire une sous-requête pour vérifier si j'aimais tout d'eux ". Vous voulez laisser le DB faire la vérification sur si vous avez aimé un poste déjà ou pas ou vous aurez à faire en code. Estiment également que ce n'est pas la seule requête que vous, et que vous avez plus d'utilisateurs actifs dans le même temps, sur une plus ou moins populaire site.
je pense que ma réponse répond à la question comment Facebook conçu leur relation d'amis très bien, mais je suis désolé que je ne peux pas vous dire comment pour le mettre en œuvre d'une manière il fonctionnera rapidement. Mettre en place un réseau social est facile, mais s'assurer qu'il fonctionne bien n'est clairement pas - IMHO.
J'ai commencé à expérimenter avec OrientDB pour faire les requêtes graph-et mapper mes bords à la base de données SQL sous-jacente. Si jamais j'ai la chance il fait, je vais écrire un article sur le sujet.
mon meilleur pari est qu'ils ont créé une structure graphique . Les noeuds sont des utilisateurs et les" amitiés " sont des bords.
garder une table des utilisateurs, garder une autre table des bords. Ensuite, vous pouvez conserver des données sur les bords, comme "le jour où ils sont devenus amis" et "statut Approuvé", etc.
C'est très probablement une relation de plusieurs à plusieurs:
liste d'amis (tableau)
user_id -> users.user_id
friend_id -> users.user_id
friendVisibilityLevel
MODIFIER
la table d'utilisateur n'a probablement pas user_email comme PK, peut-être comme une clé unique cependant.
utilisateurs (table)
user_id PK
user_email
password
jetez un oeil à 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 de données Facebook" qui pourrait être utile:
aussi, il y a cet article qui parle de bases de données non relationnelles et comment elles sont utilisées par certaines entreprises:
http://www.readwriteweb.com/archives/is_the_relational_database_doomed.php
vous verrez que ces entreprises traitent avec des entrepôts de données, partitionné les bases de données, la mise en cache de données et d'autres concepts de plus haut niveau que la plupart d'entre nous ne traitent jamais sur une base quotidienne. Ou du moins, peut-être qu'on ne sait pas que c'est le cas.
Il y a beaucoup de liens sur les deux premiers articles qui devraient vous donner quelques plus de perspicacité.
mise à jour 10/20/2014
Murat Demirbas a écrit un résumé sur
- TAO: Facebook distribué banque de données pour le graphe social (ATC'13)
- F4: le système de stockage en BLOB chaud de Facebook (OSDI '14)
http://muratbuffalo.blogspot.com/2014/10/facebooks-software-architecture.html
HTH
il n'est pas possible de récupérer des données à partir de RDBMS pour des amis Utilisateurs données pour des données qui traversent plus d'un demi-milliard à un moment constant ainsi Facebook a mis en œuvre cela 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 amis détails dans une file d'attente; pour savoir comment cassandra fonctionne regardez ceci:
ce récent article de juin 2013 explique en détail la transition des bases de données relationnelles aux objets avec associations pour certains types de données.
https://www.facebook.com/notes/facebook-engineering/tao-the-power-of-the-graph/10151525983993920
il y a un papier plus long disponible à https://www.usenix.org/conference/atc13/tao-facebook 's-distributed-data-store-social-graph
vous cherchez des clés étrangères. Fondamentalement, vous ne pouvez pas avoir un tableau dans une base de données à moins qu'il n'ait sa propre table.
exemple de schéma:
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
C'est un type de base de données graphique: 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 graph.
garder à 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)
il y a probablement une table, qui stocke la relation utilisateur de l'ami< ->, dites" frnd_list", avec les champs 'user_id','frnd_id'.
Chaque fois qu'un utilisateur ajoute un autre utilisateur comme un ami, deux nouvelles lignes sont créées.
par exemple, supposons que mon id soit 'deep9c' et que j'ajoute un utilisateur ayant l'id 'akash3b' comme ami, alors deux nouvelles lignes sont créées dans la table" frnd_list " avec des valeurs ('deep9c','akash3b') et ('akash3b','deep9c').
Now en montrant la liste d'amis à un utilisateur particulier, un simple sql ferait cela: "sélectionnez frnd_id à partir de frnd_list où user_id=" où est l'id de l'utilisateur connecté (stockés sous une session d'attribut).
en ce qui concerne la performance d'une table many-to-many, si vous avez 2 ints de 32 bits reliant les ID d'utilisateur, votre stockage de données de base pour 200 000 000 d'utilisateurs moyenne de 200 amis par pièce est un peu moins de 300 Go.
évidemment, vous auriez besoin de partitionnement et d'indexation et vous n'allez pas garder cela en mémoire pour tous les utilisateurs.