Facebook Datenbank Design?

Ich habe mich immer gefragt, wie Facebook die <-> Benutzerbeziehung für Freunde gestaltet hat.

Ich denke, die Benutzertabelle ist ungefähr so:

user_email PK
user_id PK
password 

Ich bilde die Tabelle mit Benutzerdaten (Geschlecht, Alter usw., die per Benutzer-E-Mail verbunden sind, würde ich annehmen).

Wie verbindet es alle Freunde mit diesem Benutzer?

Etwas wie das?

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N 

Wahrscheinlich nicht. Weil die Anzahl der Benutzer unbekannt ist und erweitert wird.

Behalten Sie eine Freundes-Tabelle bei, die die Benutzer-ID und dann die Benutzer-ID des Freundes enthält (wir nennen sie Freund-ID). Beide Spalten wären Fremdschlüssel zurück zur Benutzertabelle.

Etwas nützliches Beispiel:

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)

Anwendungsbeispiel:

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

Dies wird zeigen, dass Bob sowohl mit Jon als auch mit Joe befreundet ist und dass Jon auch mit Joe befreundet ist. In diesem Beispiel wird davon ausgegangen, dass Freundschaft immer zwei Möglichkeiten hat, sodass Sie keine Zeile in der Tabelle wie (2,1) oder (3,2) benötigen, da diese bereits in der anderen Richtung dargestellt sind. In Beispielen, in denen Freundschaft oder andere Beziehungen nicht explizit wechselseitig sind, müssten diese Zeilen auch vorhanden sein, um die wechselseitige Beziehung anzugeben.

Schauen Sie sich das folgende Datenbankschema an, das von Anatoly Lubarsky rückentwickelt wurde :

TL; DR:

Sie verwenden eine Stapelarchitektur mit zwischengespeicherten Diagrammen für alles über dem MySQL-Boden ihres Stapels.

Lange Antwort:

Ich habe selbst einige Nachforschungen angestellt, weil ich neugierig war, wie sie mit ihrer riesigen Datenmenge umgehen und sie schnell durchsuchen. Ich habe Leute gesehen, die sich darüber beschwert haben, dass maßgeschneiderte Skripte für soziale Netzwerke langsam werden, wenn die Benutzerbasis wächst. Nachdem ich mich mit nur 10.000 Benutzern und 2,5 Millionen Freundverbindungen verglichen hatte - ohne mich um Gruppenberechtigungen, Likes und Pinnwandeinträge zu kümmern - stellte sich schnell heraus, dass dieser Ansatz fehlerhaft ist. Ich habe einige Zeit im Internet gesucht, um herauszufinden, wie ich es besser machen kann, und bin auf diesen offiziellen Facebook-Artikel gestoßen:

• TAO: Facebooks verteilter Datenspeicher für den Social Graph
• TAO: Die Kraft des Graphen .

Ich empfehle Ihnen wirklich , sich die Präsentation des ersten Links oben anzuschauen, bevor Sie weiterlesen. Es ist wahrscheinlich die beste Erklärung dafür, wie FB hinter den Kulissen funktioniert.

Das Video und der Artikel erzählen ein paar Dinge:

• Sie verwenden MySQL ganz unten in ihrem Stapel
• Über der SQL-Datenbank befindet sich die TAO-Schicht, die mindestens zwei Caching-Ebenen enthält und zur Beschreibung der Verbindungen Diagramme verwendet.
• Ich konnte nichts darüber finden, welche Software / Datenbank sie tatsächlich für ihre zwischengespeicherten Grafiken verwenden

Werfen wir einen Blick darauf, die Verbindungen zu Freunden sind oben links:

Nun, das ist eine Grafik. :) Es sagt Ihnen nicht, wie Sie es in SQL erstellen sollen. Es gibt verschiedene Möglichkeiten, dies zu tun, aber diese Site bietet eine Reihe unterschiedlicher Ansätze. Achtung: Bedenken Sie, dass eine relationale Datenbank das ist, was sie ist: Es wird angenommen, dass normalisierte Daten gespeichert werden, keine Diagrammstruktur. Es funktioniert also nicht so gut wie eine spezialisierte Grafikdatenbank.

Denken Sie auch daran, dass Sie komplexere Abfragen durchführen müssen als nur Freunde von Freunden, beispielsweise wenn Sie alle Orte um eine bestimmte Koordinate filtern möchten, die Ihnen und Ihren Freunden von Freunden gefallen. Ein Diagramm ist hier die perfekte Lösung.

Ich kann Ihnen nicht sagen, wie Sie es so bauen sollen, dass es gut funktioniert, aber es erfordert eindeutig einige Versuche und Benchmarking.

Hier ist mein enttäuschender Test für nur Befunde Freunde von Freunden:

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;

Freunde von Freunden Abfrage:

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

Ich empfehle Ihnen wirklich, einige Beispieldaten mit mindestens 10.000 Benutzerdatensätzen zu erstellen, von denen jeder mindestens 250 Freundverbindungen hat, und diese Abfrage dann auszuführen. Auf meinem Computer (i7 4770k, SSD, 16 GB RAM) betrug das Ergebnis für diese Abfrage ~ 0,18 Sekunden . Vielleicht kann es optimiert werden, ich bin kein DB-Genie (Vorschläge sind willkommen). Doch wenn diese Skalen linear sind Sie bereits bei 1,8 Sekunden nur 100k Benutzer, 18 Sekunden für 1 Million Benutzer.

Dies mag für ~ 100.000 Benutzer immer noch in Ordnung klingen, aber denken Sie daran, dass Sie gerade Freunde von Freunden abgerufen haben und keine komplexeren Abfragen wie " Nur Beiträge von Freunden von Freunden anzeigen + Berechtigungsprüfung durchführen, ob ich erlaubt oder NICHT erlaubt bin" durchgeführt haben um einige von ihnen zu sehen + mache eine Unterabfrage, um zu überprüfen, ob mir einer von ihnen gefallen hat ". Sie möchten, dass die Datenbank überprüft, ob Ihnen ein Beitrag bereits gefallen hat oder nicht, oder ob Sie dies im Code tun müssen. Bedenken Sie auch, dass dies nicht die einzige Abfrage ist, die Sie ausführen, und dass Sie mehr als aktive Benutzer gleichzeitig auf einer mehr oder weniger beliebten Site haben.

Ich denke, meine Antwort beantwortet die Frage, wie Facebook die Beziehung seiner Freunde sehr gut gestaltet hat, aber es tut mir leid, dass ich Ihnen nicht sagen kann, wie Sie sie so implementieren können, dass sie schnell funktioniert. Die Implementierung eines sozialen Netzwerks ist einfach, aber es ist eindeutig nicht sicher, sicherzustellen, dass es gut funktioniert - IMHO.

Ich habe angefangen, mit OrientDB zu experimentieren, um die Diagrammabfragen durchzuführen und meine Kanten der zugrunde liegenden SQL-Datenbank zuzuordnen. Wenn ich es jemals schaffen sollte, werde ich einen Artikel darüber schreiben.

Meine beste Wette ist, dass sie eine Diagrammstruktur erstellt haben . Die Knoten sind Benutzer und "Freundschaften" sind Kanten.

Behalten Sie eine Benutzertabelle, eine andere Kantentabelle. Dann können Sie Daten über die Kanten speichern, z. B. "Tag, an dem sie Freunde wurden" und "Genehmigter Status" usw.

Es ist höchstwahrscheinlich eine Beziehung von vielen zu vielen:

FriendList (Tabelle)

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

BEARBEITEN

Die Benutzertabelle hat user_email wahrscheinlich nicht als PK, möglicherweise jedoch als eindeutigen Schlüssel.

Benutzer (Tabelle)

user_id PK
user_email
password

Schauen Sie sich diese Artikel an, die beschreiben, wie LinkedIn und Digg aufgebaut sind:

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

Es gibt auch "Big Data: Standpunkte des Facebook-Datenteams", die hilfreich sein könnten:

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

Außerdem gibt es diesen Artikel, der sich mit nicht relationalen Datenbanken und deren Verwendung durch einige Unternehmen befasst:

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

Sie werden sehen, dass diese Unternehmen mit Data Warehouses, partitionierten Datenbanken, Daten-Caching und anderen Konzepten auf höherer Ebene zu tun haben, mit denen sich die meisten von uns nie täglich befassen. Oder zumindest wissen wir vielleicht nicht, dass wir es tun.

Es gibt viele Links zu den ersten beiden Artikeln, die Ihnen mehr Einblick geben sollen.

UPDATE 20.10.2014

Murat Demirbas schrieb eine Zusammenfassung über

• TAO: Facebooks verteilter Datenspeicher für den Social Graph (ATC'13)
• F4: Facebooks warmes BLOB-Speichersystem (OSDI'14)

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

HTH

Es ist nicht möglich, Daten aus RDBMS für Benutzerfreunde abzurufen. Daten für Daten, die mehr als eine halbe Milliarde zu einem konstanten Zeitpunkt überschreiten. Facebook hat dies mithilfe einer Hash-Datenbank (kein SQL) implementiert und die Datenbank namens Cassandra geöffnet.

So hat jeder Benutzer seinen eigenen Schlüssel und die Details der Freunde in einer Warteschlange. Um zu wissen, wie Cassandra funktioniert, schauen Sie sich das an:

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

In diesem kürzlich veröffentlichten Beitrag vom Juni 2013 wird der Übergang von Beziehungsdatenbanken zu Objekten mit Zuordnungen für einige Datentypen ausführlich erläutert.

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

Unter https://www.usenix.org/conference/atc13/tao-facebook's-distributed-data-store-social-graph ist ein längeres Papier verfügbar

Sie suchen nach Fremdschlüsseln. Grundsätzlich können Sie kein Array in einer Datenbank haben, es sei denn, es hat eine eigene Tabelle.

Beispielschema:

    Benutzertabelle
        Benutzer-ID PK
        andere Daten
    Freundes Tisch
        userID - FK zur Benutzertabelle, die den Benutzer darstellt, der einen Freund hat.
        friendID - FK zur Benutzertabelle, die die Benutzer-ID des Freundes darstellt

Es ist eine Art Diagrammdatenbank: http://components.neo4j.org/neo4j-examples/1.2-SNAPSHOT/social-network.html

Es ist nicht mit relationalen Datenbanken verbunden.

Google für Grafikdatenbanken.

Beachten Sie, dass Datenbanktabellen so konzipiert sind, dass sie vertikal (mehr Zeilen) und nicht horizontal (mehr Spalten) wachsen.

In Bezug auf die Leistung einer Viele-zu-Viele-Tabelle beträgt Ihr grundlegender Datenspeicher für 200.000.000 Benutzer mit durchschnittlich 200 Freunden pro Stück knapp 300 GB, wenn Sie über 2 32-Bit-Ints verfügen, die Benutzer-IDs verknüpfen.

Offensichtlich würden Sie eine Partitionierung und Indizierung benötigen, und Sie werden dies nicht für alle Benutzer im Speicher behalten.

Wahrscheinlich gibt es eine Tabelle, in der die <-> Benutzerbeziehung des Freundes gespeichert ist, z. B. "frnd_list", mit den Feldern 'user_id', 'frnd_id'.

Immer wenn ein Benutzer einen anderen Benutzer als Freund hinzufügt, werden zwei neue Zeilen erstellt.

Angenommen, meine ID lautet 'deep9c' und ich füge einen Benutzer mit der ID 'akash3b' als Freund hinzu. Dann werden in der Tabelle "frnd_list" zwei neue Zeilen mit den Werten ('deep9c', 'akash3b') und ('akash3b' erstellt ',' deep9c ').

Wenn Sie nun die Freundesliste einem bestimmten Benutzer anzeigen, würde ein einfaches SQL Folgendes tun: "Wählen Sie frnd_id aus frnd_list aus, wobei user_id =" wobei die ID des angemeldeten Benutzers ist (als Sitzungsattribut gespeichert).