Desain basis data Facebook?

Saya selalu bertanya-tanya bagaimana Facebook merancang hubungan pengguna teman <->.

Saya pikir tabel pengguna adalah sesuatu seperti ini:

user_email PK
user_id PK
password 

Saya pikir tabel dengan data pengguna (jenis kelamin, usia dll terhubung melalui email pengguna saya akan menganggap).

Bagaimana cara menghubungkan semua teman ke pengguna ini?

Sesuatu seperti ini?

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N 

Mungkin tidak. Karena jumlah pengguna tidak diketahui dan akan bertambah.

Simpan tabel teman yang memegang UserID dan kemudian UserID dari teman (kami akan menyebutnya FriendID). Kedua kolom akan menjadi kunci asing kembali ke tabel Pengguna.

Contoh yang cukup berguna:

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)

Contoh penggunaan:

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

Ini akan menunjukkan bahwa Bob berteman dengan Jon dan Joe dan bahwa Jon juga berteman dengan Joe. Dalam contoh ini kita akan menganggap bahwa pertemanan selalu dua arah, jadi Anda tidak perlu baris dalam tabel seperti (2,1) atau (3,2) karena pertemanan itu sudah terwakili di arah yang lain. Untuk contoh di mana persahabatan atau hubungan lainnya tidak secara eksplisit dua arah, Anda juga perlu memiliki baris-baris tersebut untuk menunjukkan hubungan dua arah.

Lihatlah skema database berikut, direkayasa balik oleh Anatoly Lubarsky :

TL; DR:

Mereka menggunakan arsitektur tumpukan dengan grafik yang di-cache untuk semua yang ada di atas bagian bawah tumpukan MySQL mereka.

Jawaban panjang:

Saya melakukan riset sendiri karena saya ingin tahu bagaimana mereka menangani data dalam jumlah besar dan mencarinya dengan cepat. Saya telah melihat orang-orang mengeluh tentang skrip jejaring sosial yang dibuat khusus menjadi lambat ketika basis pengguna bertambah. Setelah saya melakukan benchmark sendiri dengan hanya 10k pengguna dan 2,5 juta koneksi teman - bahkan tidak mencoba untuk peduli tentang izin grup dan suka dan posting dinding - dengan cepat ternyata pendekatan ini cacat. Jadi saya telah menghabiskan waktu mencari di web tentang cara melakukannya dengan lebih baik dan menemukan artikel resmi Facebook ini:

• TAO: Menyimpan Data Terdistribusi Facebook untuk Grafik Sosial
• TAO: Kekuatan grafik .

Saya sangat merekomendasikan Anda untuk menonton presentasi tautan pertama di atas sebelum melanjutkan membaca. Itu mungkin penjelasan terbaik tentang cara kerja FB di balik layar yang dapat Anda temukan.

Video dan artikel memberi tahu Anda beberapa hal:

• Mereka menggunakan MySQL di bagian paling bawah tumpukan mereka
• Di atas SQL DB ada lapisan TAO yang berisi setidaknya dua level caching dan menggunakan grafik untuk menggambarkan koneksi.
• Saya tidak dapat menemukan apa pun pada perangkat lunak / DB apa yang sebenarnya mereka gunakan untuk grafik cache mereka

Mari kita lihat ini, koneksi teman di kiri atas:

Ini adalah grafik. :) Ini tidak memberi tahu Anda bagaimana membangunnya dalam SQL, ada beberapa cara untuk melakukannya tetapi situs ini memiliki sejumlah pendekatan yang berbeda. Perhatian: Pertimbangkan bahwa DB relasional adalah apa adanya: Diperkirakan untuk menyimpan data yang dinormalisasi, bukan struktur grafik. Jadi itu tidak akan berfungsi sebaik basis data grafik khusus.

Juga pertimbangkan bahwa Anda harus melakukan kueri yang lebih kompleks daripada sekadar teman teman, misalnya ketika Anda ingin memfilter semua lokasi di sekitar koordinat yang Anda dan teman teman Anda sukai. Grafik adalah solusi sempurna di sini.

Saya tidak bisa memberi tahu Anda cara membuatnya sehingga kinerjanya baik tetapi jelas membutuhkan beberapa percobaan dan kesalahan serta pembandingan.

Inilah tes mengecewakan saya untuk adil temuan teman teman:

Skema DB:

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;

Pertanyaan Teman dari Friends:

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

Saya benar-benar menyarankan Anda untuk membuat Anda beberapa data sampel dengan setidaknya 10k catatan pengguna dan masing-masing dari mereka memiliki setidaknya 250 koneksi teman dan kemudian jalankan kueri ini. Di mesin saya (i7 4770k, SSD, 16gb RAM) hasilnya adalah ~ 0,18 detik untuk permintaan itu. Mungkin itu bisa dioptimalkan, saya bukan jenius DB (saran dipersilahkan). Namun, jika skala ini linier, Anda sudah berada di 1,8 detik hanya untuk 100 ribu pengguna, 18 detik untuk 1 juta pengguna.

Ini mungkin masih terdengar OK untuk ~ 100k pengguna tetapi pertimbangkan bahwa Anda baru saja menjemput teman teman dan tidak melakukan kueri yang lebih rumit seperti " tampilkan saya hanya posting dari teman teman + lakukan pemeriksaan izin jika saya diizinkan atau TIDAK diizinkan untuk melihat beberapa dari mereka + melakukan sub kueri untuk memeriksa apakah saya menyukai salah satu dari mereka ". Anda ingin membiarkan DB melakukan pemeriksaan apakah Anda sudah menyukai pos atau tidak atau Anda harus melakukannya dalam kode. Juga pertimbangkan bahwa ini bukan satu-satunya kueri yang Anda jalankan dan bahwa Anda memiliki lebih dari pengguna aktif pada saat yang sama di situs yang kurang lebih populer.

Saya pikir jawaban saya menjawab pertanyaan bagaimana Facebook merancang hubungan teman-teman mereka dengan sangat baik, tetapi saya minta maaf karena saya tidak bisa memberi tahu Anda bagaimana menerapkannya dengan cara yang akan bekerja cepat. Menerapkan jaringan sosial itu mudah tetapi memastikan kinerjanya baik jelas tidak - IMHO.

Saya sudah mulai bereksperimen dengan OrientDB untuk melakukan query grafik dan memetakan tepi saya ke SQL DB yang mendasarinya. Jika saya menyelesaikannya, saya akan menulis artikel tentang itu.

Taruhan terbaik saya adalah mereka membuat struktur grafik . Node adalah pengguna dan "persahabatan" adalah ujung.

Simpan satu tabel pengguna, simpan tabel tepi lainnya. Kemudian Anda dapat menyimpan data tentang tepinya, seperti "hari mereka menjadi teman" dan "status yang disetujui," dll.

Kemungkinan besar hubungan banyak ke banyak:

Daftar Teman (tabel)

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

EDIT

Tabel pengguna mungkin tidak memiliki user_email sebagai PK, mungkin sebagai kunci unik.

pengguna (tabel)

user_id PK
user_email
password

Lihatlah artikel-artikel ini yang menjelaskan bagaimana LinkedIn dan Digg dibangun:

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

Ada juga "Data Besar: Sudut Pandang dari Tim Data Facebook" yang mungkin membantu:

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

Juga, ada artikel ini yang membahas tentang database non-relasional dan bagaimana mereka digunakan oleh beberapa perusahaan:

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

Anda akan melihat bahwa perusahaan-perusahaan ini berurusan dengan gudang data, basis data yang dipartisi, penyimpanan data dan konsep tingkat tinggi lainnya daripada kebanyakan dari kita tidak pernah berurusan dengan setiap hari. Atau setidaknya, mungkin kita tidak tahu bahwa kita tahu.

Ada banyak tautan pada dua artikel pertama yang seharusnya memberi Anda lebih banyak wawasan.

UPDATE 10/20/2014

Murat Demirbas menulis ringkasan tentang

• TAO: Menyimpan data terdistribusi Facebook untuk grafik sosial (ATC'13)
• F4: Sistem penyimpanan BLOB hangat Facebook (OSDI'14)

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

HTH

Tidak mungkin untuk mengambil data dari RDBMS untuk data teman-teman pengguna untuk data yang melintasi lebih dari setengah miliar pada waktu yang konstan sehingga Facebook menerapkan ini menggunakan database hash (tidak ada SQL) dan mereka membuka database yang disebut Cassandra.

Jadi setiap pengguna memiliki kunci sendiri dan rincian teman dalam antrian; untuk mengetahui cara kerja cassandra lihat ini:

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

Posting Juni 2013 baru-baru ini masuk ke beberapa detail dalam menjelaskan transisi dari database hubungan ke objek dengan asosiasi untuk beberapa tipe data.

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

Ada makalah lagi tersedia di https://www.usenix.org/conference/atc13/tao-facebook's-distributed-data-store-social-graph

Anda sedang mencari kunci asing. Pada dasarnya Anda tidak dapat memiliki array dalam database kecuali memiliki tabel sendiri.

Contoh skema:

    Tabel Pengguna
        userID PK
        data yang lain
    Meja Teman
        userID - FK ke tabel pengguna yang mewakili pengguna yang memiliki teman.
        friendID - FK ke tabel Users yang mewakili id ​​pengguna dari teman tersebut

Ini adalah jenis basis data grafik: http://components.neo4j.org/neo4j-examples/1.2-SNAPSHOT/social-network.html

Ini tidak terkait dengan database Relasional.

Google untuk basis data grafik.

Perlu diingat bahwa tabel database dirancang untuk tumbuh secara vertikal (lebih banyak baris), bukan horizontal (lebih banyak kolom)

Mengenai kinerja tabel banyak-ke-banyak, jika Anda memiliki 2 int 32-bit yang menghubungkan ID pengguna, penyimpanan data dasar Anda untuk 200.000.000 pengguna dengan rata-rata 200 teman masing-masing hanya di bawah 300GB.

Jelas, Anda akan membutuhkan beberapa partisi dan pengindeksan dan Anda tidak akan menyimpannya di memori untuk semua pengguna.

Mungkin ada tabel, yang menyimpan hubungan pengguna teman <->, katakan "frnd_list", yang memiliki bidang 'user_id', 'frnd_id'.

Setiap kali pengguna menambahkan pengguna lain sebagai teman, dua baris baru dibuat.

Misalnya, id saya adalah 'deep9c' dan saya menambahkan pengguna yang memiliki id 'akash3b' sebagai teman saya, maka dua baris baru dibuat di tabel "frnd_list" dengan nilai ('deep9c', 'akash3b') dan ('akash3b' ',' deep9c ').

Sekarang ketika menampilkan daftar teman ke pengguna tertentu, sql sederhana akan melakukan itu: "pilih frnd_id dari frnd_list di mana user_id =" di mana id dari pengguna yang masuk (disimpan sebagai atribut sesi).