Projekt bazy danych na Facebooku?

Question 1

Zawsze się zastanawiałem, w jaki sposób Facebook zaprojektował relację między przyjacielem a użytkownikiem.

Myślę, że tabela użytkowników wygląda mniej więcej tak:

user_email PK
user_id PK
password

Obliczam tabelę z danymi użytkownika (płeć, wiek itp. Połączonymi za pośrednictwem adresu e-mail użytkownika).

W jaki sposób łączy wszystkich znajomych z tym użytkownikiem?

Coś takiego?

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N

Prawdopodobnie nie. Ponieważ liczba użytkowników jest nieznana i będzie się zwiększać.

Question 2

Zachowaj tabelę znajomych, która zawiera identyfikator użytkownika, a następnie identyfikator użytkownika znajomego (nazwiemy go FriendID). Obie kolumny byłyby kluczami obcymi z powrotem do tabeli Users.

Dość przydatny przykład:

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)

Przykładowe zastosowanie:

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

To pokaże, że Bob jest przyjacielem zarówno Jona, jak i Joe, a Jon jest również przyjacielem Joe. W tym przykładzie założymy, że przyjaźń jest zawsze dwojakiego rodzaju, więc nie potrzebujesz wiersza w tabeli, takiego jak (2,1) lub (3,2), ponieważ są one już reprezentowane w innym kierunku. W przypadku przykładów, w których przyjaźń lub inne relacje nie są jawnie dwukierunkowe, należy również mieć te wiersze, aby wskazać relację dwukierunkową.

Question 3

Spójrz na następujący schemat bazy danych, odtworzony przez Anatolija Lubarskiego :

Schemat Facebooka

Question 4

TL; DR:

Używają architektury stosu z buforowanymi wykresami dla wszystkiego, co znajduje się powyżej dolnej części stosu MySQL.

Długa odpowiedź:

Zrobiłem kilka badań na ten temat, ponieważ byłem ciekawy, jak radzą sobie z ogromną ilością danych i przeszukują je w szybki sposób. Widziałem ludzi narzekających, że niestandardowe skrypty sieci społecznościowych zwalniają, gdy rośnie liczba użytkowników. Po przeprowadzeniu testów porównawczych z zaledwie 10 tysiącami użytkowników i 2,5 milionami połączeń znajomych - nawet nie próbując zawracać sobie głowy uprawnieniami grupowymi, polubieniami i wpisami na ścianie - szybko okazało się, że to podejście jest wadliwe. Spędziłem więc trochę czasu na przeszukiwaniu sieci i zastanawiałem się, jak to zrobić lepiej, i trafiłem na ten oficjalny artykuł na Facebooku:

I naprawdę polecam do obejrzenia prezentacji pierwszego linku powyżej przed kontynuować czytanie. To prawdopodobnie najlepsze wyjaśnienie, jak działa FB za kulisami, jakie można znaleźć.

Film i artykuł mówią ci o kilku rzeczach:

Używają MySQL na samym dole swojego stosu
Nad bazą danych SQL znajduje się warstwa TAO, która zawiera co najmniej dwa poziomy buforowania i używa wykresów do opisu połączeń.
Nie mogłem znaleźć niczego na temat oprogramowania / bazy danych, której faktycznie używają do swoich buforowanych wykresów

Rzućmy okiem na to, połączenia znajomych są u góry po lewej:

wprowadź opis obrazu tutaj

Cóż, to jest wykres. :) Nie mówi ci, jak zbudować to w SQL, jest na to kilka sposobów, ale ta strona ma wiele różnych podejść. Uwaga: Weź pod uwagę, że relacyjna baza danych jest tym, czym jest: uważa się, że przechowuje znormalizowane dane, a nie strukturę wykresu. Więc nie będzie działać tak dobrze, jak wyspecjalizowana baza danych grafów.

Weź również pod uwagę, że musisz wykonywać bardziej złożone zapytania niż tylko znajomi znajomych, na przykład gdy chcesz odfiltrować wszystkie lokalizacje wokół danej współrzędnej, które lubisz ty i twoi znajomi znajomych. Wykres jest tutaj idealnym rozwiązaniem.

Nie mogę ci powiedzieć, jak go zbudować, aby działał dobrze, ale najwyraźniej wymaga to kilku prób i błędów oraz testów porównawczych.

Oto mój rozczarowujący test tylko dla znalezisk przyjaciół znajomych:

Schemat bazy danych:

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;

Zapytanie o znajomych znajomych:

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

Naprawdę zalecam utworzenie przykładowych danych z co najmniej 10 tys. Rekordów użytkowników, z których każdy ma co najmniej 250 połączeń znajomych, a następnie uruchomienie tego zapytania. Na moim komputerze (i7 4770k, SSD, 16GB RAM) wynik dla tego zapytania wyniósł ~ 0,18 sekundy . Może da się to zoptymalizować, nie jestem geniuszem DB (sugestie są mile widziane). Jednakże, jeśli ten Wagi liniowe jesteś już w 1,8 sekundy za jedyne 100k użytkowników, 18 sekund do 1 miliona użytkowników.

Może to nadal brzmieć OK dla ~ 100 000 użytkowników, ale weź pod uwagę, że właśnie pobrałeś znajomych znajomych i nie wykonałeś żadnego bardziej złożonego zapytania, takiego jak „ wyświetlaj mi tylko posty od znajomych znajomych + sprawdź uprawnienia, czy mam pozwolenie czy NIE aby zobaczyć niektóre z nich + wykonaj zapytanie podrzędne, aby sprawdzić, czy któryś mi się podobał ". Chcesz pozwolić DB sprawdzać, czy już polubiłeś post, czy nie, albo będziesz musiał to zrobić w kodzie. Weź również pod uwagę, że nie jest to jedyne zapytanie, które uruchamiasz i że masz jednocześnie więcej niż aktywnych użytkowników w mniej lub bardziej popularnej witrynie.

Myślę, że moja odpowiedź odpowiada na pytanie, w jaki sposób Facebook bardzo dobrze zaprojektował relacje z przyjaciółmi, ale przykro mi, że nie mogę powiedzieć, jak to zaimplementować, aby działało szybko. Wdrożenie sieci społecznościowej jest łatwe, ale upewnienie się, że działa dobrze, zdecydowanie nie jest - IMHO.

Zacząłem eksperymentować z OrientDB w celu wykonywania zapytań grafowych i mapowania moich krawędzi do podstawowej bazy danych SQL. Jeśli kiedykolwiek to zrobię, napiszę o tym artykuł.

Question 5

Moim najlepszym założeniem jest to, że stworzyli strukturę wykresu . Węzły to użytkownicy, a „przyjaźnie” to krawędzie.

Zachowaj jedną tabelę użytkowników, drugą tabelę krawędzi. Następnie możesz zachować dane o krawędziach, takie jak „dzień, w którym się zaprzyjaźnili”, „stan zatwierdzenia” itp.

Question 6

Najprawdopodobniej jest to relacja wiele do wielu:

FriendList (tabela)

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

EDYTOWAĆ

Tabela użytkowników prawdopodobnie nie ma adresu e-mail user_email jako PK, prawdopodobnie jako unikalnego klucza.

użytkownicy (tabela)

user_id PK
user_email
password

Question 7

Zapoznaj się z tymi artykułami opisującymi, jak powstają LinkedIn i Digg:

Jest też „Big Data: Viewpoints from the Facebook Data Team”, które mogą być pomocne:

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

Jest też ten artykuł, który mówi o nierelacyjnych bazach danych i sposobie ich używania przez niektóre firmy:

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

Zobaczysz, że te firmy mają do czynienia z hurtowniami danych, partycjonowanymi bazami danych, buforowaniem danych i innymi koncepcjami wyższego poziomu, z którymi większość z nas nigdy nie ma do czynienia na co dzień. A przynajmniej może nie wiemy, że tak jest.

W pierwszych dwóch artykułach znajduje się wiele linków, które powinny dać ci więcej informacji.

AKTUALIZACJA 20.10.2014

Murat Demirbas napisał podsumowanie

TAO: rozproszony magazyn danych Facebooka dla wykresu społecznościowego (ATC'13)
F4: ciepły system przechowywania BLOB na Facebooku (OSDI'14)

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

HTH

Question 8

Nie jest możliwe pobranie danych z RDBMS dla danych znajomych użytkowników w przypadku danych, które przekraczają ponad pół miliarda w stałym czasie, więc Facebook zaimplementował to za pomocą bazy danych hash (bez SQL) i otworzył bazę danych o nazwie Cassandra.

Tak więc każdy użytkownik ma swój własny klucz i szczegóły dotyczące znajomych w kolejce; aby wiedzieć, jak działa Cassandra, spójrz na to:

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

Question 9

Ten ostatni post z czerwca 2013 r. Zawiera szczegółowe wyjaśnienia dotyczące przejścia od baz danych relacji do obiektów z powiązaniami dla niektórych typów danych.

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

Istnieje dłuższy artykuł dostępny pod adresem https://www.usenix.org/conference/atc13/tao-facebook's-distributed-data-store-social-graph

Question 10

Szukasz kluczy obcych. Zasadniczo nie możesz mieć tablicy w bazie danych, jeśli nie ma własnej tabeli.

Przykładowy schemat:

    Tabela użytkowników
        identyfikator użytkownika PK
        inne dane
    Tabela przyjaciół
        userID - FK do tabeli użytkowników reprezentującej użytkownika, który ma znajomego.
        friendID - FK do tabeli użytkowników reprezentującej identyfikator użytkownika znajomego

Question 11

Jest to rodzaj graficznej bazy danych: http://components.neo4j.org/neo4j-examples/1.2-SNAPSHOT/social-network.html

Nie jest to związane z relacyjnymi bazami danych.

Google dla graficznych baz danych.

Question 12

Pamiętaj, że tabele bazy danych są zaprojektowane tak, aby rosły pionowo (więcej wierszy), a nie poziomo (więcej kolumn)

Question 13

Jeśli chodzi o wydajność tabeli wiele-do-wielu, jeśli masz 2 32-bitowe inty łączące identyfikatory użytkowników, podstawowa pamięć dla 200 000 000 użytkowników, średnio 200 znajomych na osobę, wynosi nieco poniżej 300 GB.

Oczywiście będziesz potrzebować partycjonowania i indeksowania, a nie będziesz tego przechowywać w pamięci dla wszystkich użytkowników.

Question 14

Prawdopodobnie istnieje tabela, która przechowuje relację użytkownika znajomego <->, powiedzmy „frnd_list”, zawierającą pola „user_id”, „frnd_id”.

Za każdym razem, gdy użytkownik doda innego użytkownika jako znajomego, tworzone są dwa nowe wiersze.

Na przykład załóżmy, że mój identyfikator to „deep9c” i dodaję użytkownika o identyfikatorze „akash3b” jako znajomego, a następnie w tabeli „frnd_list” zostaną utworzone dwa nowe wiersze z wartościami („deep9c”, „akash3b”) i („akash3b ',' deep9c ').

Teraz, pokazując listę znajomych konkretnemu użytkownikowi, prosty sql zrobiłby to: "select frnd_id z frnd_list gdzie user_id =" gdzie jest id zalogowanego użytkownika (przechowywany jako atrybut sesji).

Answer 1

133

Zawsze się zastanawiałem, w jaki sposób Facebook zaprojektował relację między przyjacielem a użytkownikiem.

Myślę, że tabela użytkowników wygląda mniej więcej tak:

user_email PK
user_id PK
password

Obliczam tabelę z danymi użytkownika (płeć, wiek itp. Połączonymi za pośrednictwem adresu e-mail użytkownika).

W jaki sposób łączy wszystkich znajomych z tym użytkownikiem?

Coś takiego?

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N

Prawdopodobnie nie. Ponieważ liczba użytkowników jest nieznana i będzie się zwiększać.

sql facebook database-design database-normalization database-table Marin
źródło

13

Istnieje strona inżynieryjna Facebooka, która zawiera wiele tego typu informacji, ale nie do końca o to, o co prosisz. Możesz tam zapytać i zobaczyć, czy możesz uzyskać odpowiedź. facebook.com/FacebookEngineering

John Meagher

1

Google graph database. Na pewno nie jest to RDBMS.

Answer 2

13

Istnieje strona inżynieryjna Facebooka, która zawiera wiele tego typu informacji, ale nie do końca o to, o co prosisz. Możesz tam zapytać i zobaczyć, czy możesz uzyskać odpowiedź. facebook.com/FacebookEngineering

John Meagher

Answer 3

1

Google graph database. Na pewno nie jest to RDBMS.

Answer 4

90

Zachowaj tabelę znajomych, która zawiera identyfikator użytkownika, a następnie identyfikator użytkownika znajomego (nazwiemy go FriendID). Obie kolumny byłyby kluczami obcymi z powrotem do tabeli Users.

Dość przydatny przykład:

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)

Przykładowe zastosowanie:

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

To pokaże, że Bob jest przyjacielem zarówno Jona, jak i Joe, a Jon jest również przyjacielem Joe. W tym przykładzie założymy, że przyjaźń jest zawsze dwojakiego rodzaju, więc nie potrzebujesz wiersza w tabeli, takiego jak (2,1) lub (3,2), ponieważ są one już reprezentowane w innym kierunku. W przypadku przykładów, w których przyjaźń lub inne relacje nie są jawnie dwukierunkowe, należy również mieć te wiersze, aby wskazać relację dwukierunkową.

TheTXI
źródło

8

pomyśl jednak, jakie to nieefektywne - musisz wykonać zapytanie rozłączne w kolumnach wielu do wielu, średnio podwajając czas wyszukiwania.

Anthony Bishopric

2

Osobiście nie chciałbym, aby te dwa pola tworzyły złożony klucz podstawowy. Absolutnie wyjątkowy klucz. Zdecydowanie indeks klastrowy na tym unikalnym kluczu. Ale umieściłbym również jakąś niezłożoną tożsamość jako PK z indeksem nieklastrowym. To pozwoliłoby innym stołom, które potrzebują „identyfikatora relacji przyjacielskiej” FK, na łatwe powiązanie z tym stołem, a różne wyzwalacze mogą uruchamiać kaskadowe zdarzenia, takie jak przyjaźń, defriending itp.

Jesse C. Slicer

1

Mówi się, że Facebook ma około 1 000 000 000 użytkowników. Jeśli przeciętny użytkownik ma 100 znajomych, oznacza to, że tabela zawierałaby 100 000 000 000 wierszy. Partycjonowanie MySQL?

veidelis

Zapomnij o tym podejściu. Jeśli zdobędziesz dużą liczbę użytkowników, z pewnością stanie się to bardzo powolne. Zobacz moją odpowiedź i wypróbuj ją samodzielnie. Przeprowadziłem testy porównawcze z 10 tysiącami użytkowników i 2,5 milionami znajomości i wynik był rozczarowujący. Jeśli prowadzisz małą społeczność, będzie działać dobrze, ale należy wziąć pod uwagę problemy z wydajnością.

burzum

7

możesz być pewien, że facebook nie używa do tego RDBMS, powszechnie wiadomo, że oni, Twitter i wszyscy inni, którzy muszą uruchamiać takie zapytania, używają bazy danych grafów o pewnym smaku. jest co najmniej 69 osób, które nigdy nie pracowały na żadną skalę lub nie wiedzą, jak wykonywać obliczenia matematyczne na dużą skalę.

Answer 5

8

pomyśl jednak, jakie to nieefektywne - musisz wykonać zapytanie rozłączne w kolumnach wielu do wielu, średnio podwajając czas wyszukiwania.

Anthony Bishopric

Answer 6

2

Osobiście nie chciałbym, aby te dwa pola tworzyły złożony klucz podstawowy. Absolutnie wyjątkowy klucz. Zdecydowanie indeks klastrowy na tym unikalnym kluczu. Ale umieściłbym również jakąś niezłożoną tożsamość jako PK z indeksem nieklastrowym. To pozwoliłoby innym stołom, które potrzebują „identyfikatora relacji przyjacielskiej” FK, na łatwe powiązanie z tym stołem, a różne wyzwalacze mogą uruchamiać kaskadowe zdarzenia, takie jak przyjaźń, defriending itp.

Jesse C. Slicer

Answer 7

1

Mówi się, że Facebook ma około 1 000 000 000 użytkowników. Jeśli przeciętny użytkownik ma 100 znajomych, oznacza to, że tabela zawierałaby 100 000 000 000 wierszy. Partycjonowanie MySQL?

veidelis

Answer 8

Zapomnij o tym podejściu. Jeśli zdobędziesz dużą liczbę użytkowników, z pewnością stanie się to bardzo powolne. Zobacz moją odpowiedź i wypróbuj ją samodzielnie. Przeprowadziłem testy porównawcze z 10 tysiącami użytkowników i 2,5 milionami znajomości i wynik był rozczarowujący. Jeśli prowadzisz małą społeczność, będzie działać dobrze, ale należy wziąć pod uwagę problemy z wydajnością.

burzum

Answer 9

7

możesz być pewien, że facebook nie używa do tego RDBMS, powszechnie wiadomo, że oni, Twitter i wszyscy inni, którzy muszą uruchamiać takie zapytania, używają bazy danych grafów o pewnym smaku. jest co najmniej 69 osób, które nigdy nie pracowały na żadną skalę lub nie wiedzą, jak wykonywać obliczenia matematyczne na dużą skalę.

Answer 10

51

Spójrz na następujący schemat bazy danych, odtworzony przez Anatolija Lubarskiego :

Schemat Facebooka

Brad Larson
źródło

7

To jest diagram klas, a nie schemat bazy danych

Lemon Juice

2

Czy zatem każdy „Użytkownik” miałby własną dedykowaną bazę danych? Jak ten powyżej? Jak by to działało? Np. Gdy użytkownik loguje się na FB sprawdza, czy jest to prawidłowy User + Pass, a następnie, czy jest ważny, facebook przekieruje go do tamtejszej bazy danych, która następnie wyświetli wszystko z powyższej bazy danych

James111

To Przechowuje tylko informacje związane z użytkownikiem, konkretnie szukam postu i jego odbiorców?

Waseem Ahmad Naeem

Answer 11

7

To jest diagram klas, a nie schemat bazy danych

Lemon Juice

Answer 12

2

Czy zatem każdy „Użytkownik” miałby własną dedykowaną bazę danych? Jak ten powyżej? Jak by to działało? Np. Gdy użytkownik loguje się na FB sprawdza, czy jest to prawidłowy User + Pass, a następnie, czy jest ważny, facebook przekieruje go do tamtejszej bazy danych, która następnie wyświetli wszystko z powyższej bazy danych

James111

Answer 13

To Przechowuje tylko informacje związane z użytkownikiem, konkretnie szukam postu i jego odbiorców?

Waseem Ahmad Naeem

Answer 14

TL; DR:

Używają architektury stosu z buforowanymi wykresami dla wszystkiego, co znajduje się powyżej dolnej części stosu MySQL.

Długa odpowiedź:

Zrobiłem kilka badań na ten temat, ponieważ byłem ciekawy, jak radzą sobie z ogromną ilością danych i przeszukują je w szybki sposób. Widziałem ludzi narzekających, że niestandardowe skrypty sieci społecznościowych zwalniają, gdy rośnie liczba użytkowników. Po przeprowadzeniu testów porównawczych z zaledwie 10 tysiącami użytkowników i 2,5 milionami połączeń znajomych - nawet nie próbując zawracać sobie głowy uprawnieniami grupowymi, polubieniami i wpisami na ścianie - szybko okazało się, że to podejście jest wadliwe. Spędziłem więc trochę czasu na przeszukiwaniu sieci i zastanawiałem się, jak to zrobić lepiej, i trafiłem na ten oficjalny artykuł na Facebooku:

I naprawdę polecam do obejrzenia prezentacji pierwszego linku powyżej przed kontynuować czytanie. To prawdopodobnie najlepsze wyjaśnienie, jak działa FB za kulisami, jakie można znaleźć.

Film i artykuł mówią ci o kilku rzeczach:

Używają MySQL na samym dole swojego stosu
Nad bazą danych SQL znajduje się warstwa TAO, która zawiera co najmniej dwa poziomy buforowania i używa wykresów do opisu połączeń.
Nie mogłem znaleźć niczego na temat oprogramowania / bazy danych, której faktycznie używają do swoich buforowanych wykresów

Rzućmy okiem na to, połączenia znajomych są u góry po lewej:

wprowadź opis obrazu tutaj

Cóż, to jest wykres. :) Nie mówi ci, jak zbudować to w SQL, jest na to kilka sposobów, ale ta strona ma wiele różnych podejść. Uwaga: Weź pod uwagę, że relacyjna baza danych jest tym, czym jest: uważa się, że przechowuje znormalizowane dane, a nie strukturę wykresu. Więc nie będzie działać tak dobrze, jak wyspecjalizowana baza danych grafów.

Weź również pod uwagę, że musisz wykonywać bardziej złożone zapytania niż tylko znajomi znajomych, na przykład gdy chcesz odfiltrować wszystkie lokalizacje wokół danej współrzędnej, które lubisz ty i twoi znajomi znajomych. Wykres jest tutaj idealnym rozwiązaniem.

Nie mogę ci powiedzieć, jak go zbudować, aby działał dobrze, ale najwyraźniej wymaga to kilku prób i błędów oraz testów porównawczych.

Oto mój rozczarowujący test tylko dla znalezisk przyjaciół znajomych:

Schemat bazy danych:

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;

Zapytanie o znajomych znajomych:

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

Naprawdę zalecam utworzenie przykładowych danych z co najmniej 10 tys. Rekordów użytkowników, z których każdy ma co najmniej 250 połączeń znajomych, a następnie uruchomienie tego zapytania. Na moim komputerze (i7 4770k, SSD, 16GB RAM) wynik dla tego zapytania wyniósł ~ 0,18 sekundy . Może da się to zoptymalizować, nie jestem geniuszem DB (sugestie są mile widziane). Jednakże, jeśli ten Wagi liniowe jesteś już w 1,8 sekundy za jedyne 100k użytkowników, 18 sekund do 1 miliona użytkowników.

Może to nadal brzmieć OK dla ~ 100 000 użytkowników, ale weź pod uwagę, że właśnie pobrałeś znajomych znajomych i nie wykonałeś żadnego bardziej złożonego zapytania, takiego jak „ wyświetlaj mi tylko posty od znajomych znajomych + sprawdź uprawnienia, czy mam pozwolenie czy NIE aby zobaczyć niektóre z nich + wykonaj zapytanie podrzędne, aby sprawdzić, czy któryś mi się podobał ". Chcesz pozwolić DB sprawdzać, czy już polubiłeś post, czy nie, albo będziesz musiał to zrobić w kodzie. Weź również pod uwagę, że nie jest to jedyne zapytanie, które uruchamiasz i że masz jednocześnie więcej niż aktywnych użytkowników w mniej lub bardziej popularnej witrynie.

Myślę, że moja odpowiedź odpowiada na pytanie, w jaki sposób Facebook bardzo dobrze zaprojektował relacje z przyjaciółmi, ale przykro mi, że nie mogę powiedzieć, jak to zaimplementować, aby działało szybko. Wdrożenie sieci społecznościowej jest łatwe, ale upewnienie się, że działa dobrze, zdecydowanie nie jest - IMHO.

Zacząłem eksperymentować z OrientDB w celu wykonywania zapytań grafowych i mapowania moich krawędzi do podstawowej bazy danych SQL. Jeśli kiedykolwiek to zrobię, napiszę o tym artykuł.

Answer 15

więc .. czy kiedykolwiek udało Ci się napisać artykuł?

FlowUI. SimpleUITesting.com

Answer 16

1

Nie, jestem dość zajęty poza programowaniem i nie miałem na to czasu ani nastroju. Odpowiedź tutaj zawiera wszystko, co musisz wiedzieć, jeśli chcesz wdrożyć skuteczne skojarzenia znajomych. Buforuj listy znajomych dla każdego użytkownika lub zamapuj relacyjną bazę danych w częściach lub całości na wykres i zapytaj o tę bazę danych. Możesz do tego użyć OrientDB lub Neo4j. Chciałbym napisać własne oprogramowanie społecznościowe typu open source, ale jest też mnóstwo innych rzeczy do zrobienia. Cokolwiek robisz: wykonuj testy porównawcze. :)

burzum

Answer 17

Nadal nie. Ale dokumentacja OrientDB wyjaśnia znajomość połączeń, a wszystko inne można modelować po zrozumieniu podstaw. orientdb.com/docs/2.1/Tutorial-Working-with-graphs.html Jeśli chcesz użyć relacyjnej bazy danych jako podstawy, wystarczy dodać kod w wywołaniach zwrotnych „po zapisaniu” i „po usunięciu”, aby zaktualizować wykres DB (którego użyjesz do odczytu danych). Jeśli nie masz takich wywołań zwrotnych, zaimplementuj je, ale wydaje mi się, że prawie wszystkie implementacje ORM i frameworki mają coś takiego. Właściwie OrientDB może również przechowywać dokumenty.

burzum

Answer 18

1

więc .. czy kiedykolwiek udało Ci się napisać artykuł?

Connor Gurney

Answer 19

1

Wciąż nie, ale robimy coś podobnego w pracy: mapujemy nasze dane relacyjne do indeksu Elastic Search, jak napisałem w moim wcześniejszym komentarzu, jest to po prostu kwestia uzyskania danych, które chcesz przechowywać w indeksie lub na wykresie po wykonaniu określonej czynności (wywołanie zwrotne afterSave () / afterDelete () w naszym przypadku), a następnie aktualizację indeksu lub wykresu. Dość proste? :) To samo można zrobić z listami znajomych, tak naprawdę nie ma znaczenia, czy przechowujesz je w ES, wykresie czy pamięci podręcznej opartej na pamięci (o ile masz wystarczającą ilość pamięci RAM). To naprawdę nie jest trudne, najtrudniejsze jest skalowanie całości, gdy się rozwijasz.

burzum

Answer 20

32

Moim najlepszym założeniem jest to, że stworzyli strukturę wykresu . Węzły to użytkownicy, a „przyjaźnie” to krawędzie.

Zachowaj jedną tabelę użytkowników, drugą tabelę krawędzi. Następnie możesz zachować dane o krawędziach, takie jak „dzień, w którym się zaprzyjaźnili”, „stan zatwierdzenia” itp.

belgariontheking
źródło

41

Mam przeczucie, że niektórym obecnym tutaj będziecie musieli to trochę bardziej wyjaśnić.

TheTXI

4

Myślę, że bardziej interesującym pytaniem byłoby, jak zachować tak ogromną strukturę (mówimy o 200 milionach węzłów i miliardach krawędzi), aby można było ją łatwo przeszukiwać i aktualizować.

Dirk Vollmar

1

@divo: sprytne wykorzystanie indeksów i partycji.

belgariontheking

Answer 21

41

Mam przeczucie, że niektórym obecnym tutaj będziecie musieli to trochę bardziej wyjaśnić.

TheTXI

Answer 22

4

Myślę, że bardziej interesującym pytaniem byłoby, jak zachować tak ogromną strukturę (mówimy o 200 milionach węzłów i miliardach krawędzi), aby można było ją łatwo przeszukiwać i aktualizować.

Dirk Vollmar

Answer 23

1

@divo: sprytne wykorzystanie indeksów i partycji.

belgariontheking

Answer 24

20

Najprawdopodobniej jest to relacja wiele do wielu:

FriendList (tabela)

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

EDYTOWAĆ

Tabela użytkowników prawdopodobnie nie ma adresu e-mail user_email jako PK, prawdopodobnie jako unikalnego klucza.

użytkownicy (tabela)

user_id PK
user_email
password

Nathan Koop
źródło

4

Chociaż z pewnością ma to największy sens, myślę, że wydajność byłaby przerażająca, biorąc pod uwagę, ilu użytkowników ma Facebook i ilu znajomych ma każdy użytkownik Facebooka.

Kevin Pang

Answer 25

4

Chociaż z pewnością ma to największy sens, myślę, że wydajność byłaby przerażająca, biorąc pod uwagę, ilu użytkowników ma Facebook i ilu znajomych ma każdy użytkownik Facebooka.

Kevin Pang

Answer 26

Zapoznaj się z tymi artykułami opisującymi, jak powstają LinkedIn i Digg:

Jest też „Big Data: Viewpoints from the Facebook Data Team”, które mogą być pomocne:

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

Jest też ten artykuł, który mówi o nierelacyjnych bazach danych i sposobie ich używania przez niektóre firmy:

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

Zobaczysz, że te firmy mają do czynienia z hurtowniami danych, partycjonowanymi bazami danych, buforowaniem danych i innymi koncepcjami wyższego poziomu, z którymi większość z nas nigdy nie ma do czynienia na co dzień. A przynajmniej może nie wiemy, że tak jest.

W pierwszych dwóch artykułach znajduje się wiele linków, które powinny dać ci więcej informacji.

AKTUALIZACJA 20.10.2014

Murat Demirbas napisał podsumowanie

TAO: rozproszony magazyn danych Facebooka dla wykresu społecznościowego (ATC'13)
F4: ciepły system przechowywania BLOB na Facebooku (OSDI'14)

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

HTH

Answer 27

9

Nie jest możliwe pobranie danych z RDBMS dla danych znajomych użytkowników w przypadku danych, które przekraczają ponad pół miliarda w stałym czasie, więc Facebook zaimplementował to za pomocą bazy danych hash (bez SQL) i otworzył bazę danych o nazwie Cassandra.

Tak więc każdy użytkownik ma swój własny klucz i szczegóły dotyczące znajomych w kolejce; aby wiedzieć, jak działa Cassandra, spójrz na to:

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

user362541
źródło

Bardzo interesujące, dziękuję przyjacielu. Kiedy przeszli na Cassandrę z SQL? nie wiesz przypadkiem?

Marin

1

Uwaga: Posterous Spaces jest martwy ... więc łącze.

TechNyquist,

Answer 28

Bardzo interesujące, dziękuję przyjacielu. Kiedy przeszli na Cassandrę z SQL? nie wiesz przypadkiem?

Marin

Answer 29

1

Uwaga: Posterous Spaces jest martwy ... więc łącze.

TechNyquist,

Answer 30

Ten ostatni post z czerwca 2013 r. Zawiera szczegółowe wyjaśnienia dotyczące przejścia od baz danych relacji do obiektów z powiązaniami dla niektórych typów danych.

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

Istnieje dłuższy artykuł dostępny pod adresem https://www.usenix.org/conference/atc13/tao-facebook's-distributed-data-store-social-graph

Answer 31

5

Szukasz kluczy obcych. Zasadniczo nie możesz mieć tablicy w bazie danych, jeśli nie ma własnej tabeli.

Przykładowy schemat:

    Tabela użytkowników
        identyfikator użytkownika PK
        inne dane
    Tabela przyjaciół
        userID - FK do tabeli użytkowników reprezentującej użytkownika, który ma znajomego.
        friendID - FK do tabeli użytkowników reprezentującej identyfikator użytkownika znajomego

Malfist
źródło

5

Dlaczego głosy przeciw? Przynajmniej daj komuś znać, dlaczego go przegłosowałeś.

Sasha Chedygov

3

@freak: Dlaczego? Cała koncepcja głosowania na tej stronie polega na anonimowości. Dlaczego uważasz, że Malfist ma prawo do czegokolwiek?

GEOCHET

4

Zwłaszcza, gdy jest to prawidłowa odpowiedź i odzwierciedlają ją inne odpowiedzi (chociaż nie kopiowałem z nich, kiedy odpowiedziałem, tam nie ma odpowiedzi)

Malfist

4

@TheTXI: Myślę, że komentarze dotyczące głosów przeciw są uprzejmości, zwłaszcza w przypadku odpowiedzi, które w oczywisty sposób na nie nie zasługują, ale zgadzam się również, że komentarze nie powinny być wymagane.

Robert S.

2

Osoby, które anonimowo głosują przeciw nieoczywistym odpowiedziom, to ci, którzy obawiają się, że ich płytkie rozumowanie zostanie ujawnione, jeśli zostawią komentarz wyjaśniający negatywny głos.

Vinayak

Answer 32

5

Dlaczego głosy przeciw? Przynajmniej daj komuś znać, dlaczego go przegłosowałeś.

Sasha Chedygov

Answer 33

3

@freak: Dlaczego? Cała koncepcja głosowania na tej stronie polega na anonimowości. Dlaczego uważasz, że Malfist ma prawo do czegokolwiek?

GEOCHET

Answer 34

4

Zwłaszcza, gdy jest to prawidłowa odpowiedź i odzwierciedlają ją inne odpowiedzi (chociaż nie kopiowałem z nich, kiedy odpowiedziałem, tam nie ma odpowiedzi)

Malfist

Answer 35

4

@TheTXI: Myślę, że komentarze dotyczące głosów przeciw są uprzejmości, zwłaszcza w przypadku odpowiedzi, które w oczywisty sposób na nie nie zasługują, ale zgadzam się również, że komentarze nie powinny być wymagane.

Robert S.

Answer 36

2

Osoby, które anonimowo głosują przeciw nieoczywistym odpowiedziom, to ci, którzy obawiają się, że ich płytkie rozumowanie zostanie ujawnione, jeśli zostawią komentarz wyjaśniający negatywny głos.

Vinayak

Answer 37

Jest to rodzaj graficznej bazy danych: http://components.neo4j.org/neo4j-examples/1.2-SNAPSHOT/social-network.html

Nie jest to związane z relacyjnymi bazami danych.

Google dla graficznych baz danych.

Answer 38

1

Pamiętaj, że tabele bazy danych są zaprojektowane tak, aby rosły pionowo (więcej wierszy), a nie poziomo (więcej kolumn)

Neil N.
źródło

24

NIGDY NIE ZAPOMNIJ! Mój tata zmarł z powodu stołu db, który urósł zbyt wysoko w stosunku do kolumn. Będę za tobą tęsknić tato.

belgariontheking

1

hmm, dlaczego głos przeciw? A komentarz nad tym nie ma sensu.

Neil N

2

Nie, komentarz nie ma sensu. Wygląda na to, że ktoś próbował być zabawny, więc nie przejmuj się.

Dirk Vollmar

Answer 39

24

NIGDY NIE ZAPOMNIJ! Mój tata zmarł z powodu stołu db, który urósł zbyt wysoko w stosunku do kolumn. Będę za tobą tęsknić tato.

belgariontheking

Answer 40

1

hmm, dlaczego głos przeciw? A komentarz nad tym nie ma sensu.

Neil N

Answer 41

2

Nie, komentarz nie ma sensu. Wygląda na to, że ktoś próbował być zabawny, więc nie przejmuj się.

Dirk Vollmar

Answer 42

Jeśli chodzi o wydajność tabeli wiele-do-wielu, jeśli masz 2 32-bitowe inty łączące identyfikatory użytkowników, podstawowa pamięć dla 200 000 000 użytkowników, średnio 200 znajomych na osobę, wynosi nieco poniżej 300 GB.

Oczywiście będziesz potrzebować partycjonowania i indeksowania, a nie będziesz tego przechowywać w pamięci dla wszystkich użytkowników.

Answer 43

Prawdopodobnie istnieje tabela, która przechowuje relację użytkownika znajomego <->, powiedzmy „frnd_list”, zawierającą pola „user_id”, „frnd_id”.

Za każdym razem, gdy użytkownik doda innego użytkownika jako znajomego, tworzone są dwa nowe wiersze.

Na przykład załóżmy, że mój identyfikator to „deep9c” i dodaję użytkownika o identyfikatorze „akash3b” jako znajomego, a następnie w tabeli „frnd_list” zostaną utworzone dwa nowe wiersze z wartościami („deep9c”, „akash3b”) i („akash3b ',' deep9c ').

Teraz, pokazując listę znajomych konkretnemu użytkownikowi, prosty sql zrobiłby to: "select frnd_id z frnd_list gdzie user_id =" gdzie jest id zalogowanego użytkownika (przechowywany jako atrybut sesji).

Projekt bazy danych na Facebooku?

Odpowiedzi:

Przykładowy schemat: