Дизайн базы данных Facebook? - PullRequest
128 голосов
/ 17 июня 2009

Мне всегда было интересно, как Facebook разработал отношения между друзьями <->.

Я полагаю, что таблица пользователя выглядит примерно так:

user_email PK
user_id PK
password 

Я рисую таблицу с данными пользователя (пол, возраст и т. Д., Связанные с электронной почтой пользователя, я бы предположил)

Как он связывает всех друзей с этим пользователем?

Как то так?

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N 

Вероятно, нет. Потому что количество пользователей неизвестно и будет расширяться.

Ответы [ 13 ]

88 голосов
/ 17 июня 2009

Сохраните таблицу друзей, которая содержит идентификатор пользователя, а затем идентификатор друга (мы назовем его FriendID). Оба столбца будут внешними ключами обратно в таблицу Users.

Несколько полезный пример:

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)

Пример использования:

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

Это покажет, что Боб дружит как с Джоном, так и с Джо, и что Джон тоже дружит с Джо. В этом примере мы будем предполагать, что дружба всегда двухсторонняя, поэтому вам не потребуется строка в таблице, такая как (2,1) или (3,2), потому что они уже представлены в другом направлении. Для примеров, когда дружба или другие отношения явно не являются двусторонними, вам также необходимо иметь эти строки, чтобы указать двусторонние отношения.

47 голосов
/ 13 июля 2009

Взгляните на следующую схему базы данных, в обратном порядке, разработанную Анатолием Любарским :

Facebook Schema

40 голосов
/ 26 февраля 2015

TL; DR:

Они используют стековую архитектуру с кэшированными графами для всего, что находится выше MySQL в нижней части их стека.

Длинный ответ:

Я сам провел некоторые исследования по этому вопросу, потому что мне было любопытно, как они обрабатывают свои огромные объемы данных и быстро их ищут. Я видел людей, жалующихся на то, что пользовательские скрипты в социальных сетях становятся медленными по мере роста базы пользователей. После того, как я провел сравнительный анализ с только 10k пользователями и 2,5 миллионами друзей подключений - даже не пытаясь беспокоиться о групповых разрешениях и лайках и постах на стене - быстро оказалось, что этот подход недостатки. Поэтому я потратил некоторое время на поиск в Интернете, как это сделать лучше, и наткнулся на эту официальную статью в Facebook:

Я действительно рекомендую вам посмотреть презентацию по первой ссылке выше, прежде чем продолжить чтение. Это, вероятно, лучшее объяснение того, как FB работает за кулисами, вы можете найти.

Видео и статья рассказывают вам несколько вещей:

  • Они используют MySQL в самом низе своего стека
  • Выше базы данных SQL находится слой TAO, который содержит как минимум два уровня кэширования и использует графики для описания соединений.
  • Я не смог найти ничего о том, какое программное обеспечение / БД они фактически используют для своих кэшированных графиков

Давайте посмотрим на это, дружеские связи вверху слева:

enter image description here

Ну, это график. :) Он не говорит вам , как построить его в SQL, есть несколько способов сделать это, но этот сайт имеет множество различных подходов. Внимание: Учтите, что реляционная БД - это то, чем она является: считается, что она хранит нормализованные данные, а не структуру графа. Так что он не будет работать так же хорошо, как специализированная графовая база данных.

Также учтите, что вам нужно выполнять более сложные запросы, чем просто друзья друзей, например, когда вы хотите отфильтровать все местоположения вокруг заданной координаты, которые нравятся вам и вашим друзьям друзей. График является идеальным решением здесь.

Я не могу сказать вам, как построить его так, чтобы он работал хорошо, но он явно требует проб и ошибок и тестирования.

Вот мой разочаровывающий тест для просто находок друзей друзей:

Схема БД:

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;

Запрос друзей друзей:

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

Я действительно рекомендую вам создать пример данных с минимум 10 тысячами пользовательских записей, каждая из которых имеет как минимум 250 дружеских соединений, а затем выполнить этот запрос. На моей машине (i7 4770k, SSD, 16 ГБ ОЗУ) результат запроса составил ~ 0,18 секунды . Может быть, это можно оптимизировать, я не гений БД (предложения приветствуются). Тем не менее, , если это линейное масштабирование, вы уже на 1,8 секунды для всего 100 000 пользователей, 18 секунд для 1 миллиона пользователей.

Это может звучать нормально для пользователей ~ 100k, но учтите, что вы только что выбрали друзей друзей и не сделали более сложный запрос, например ", отображать только сообщения от друзей друзей + проверять разрешение, если я мне разрешено или НЕ разрешено видеть некоторые из них + сделать подзапрос, чтобы проверить, понравился ли мне какой-либо из них". Вы хотите, чтобы БД проверила, понравился ли вам пост или нет, или вам придется делать это в коде. Также учтите, что это не единственный запрос, который вы выполняете, и у вас есть более чем активный пользователь одновременно на более или менее популярном сайте.

Я думаю, что мой ответ отвечает на вопрос, как Facebook очень хорошо спроектировал отношения с друзьями, но мне жаль, что я не могу рассказать вам, как реализовать это так, чтобы это работало быстро. Внедрить социальную сеть легко, но убедиться, что она работает хорошо, явно нет - ИМХО.

Я начал экспериментировать с OrientDB, чтобы выполнять граф-запросы и отображать свои ребра в базовую базу данных SQL. Если я когда-нибудь это сделаю, я напишу об этом статью.

32 голосов
/ 17 июня 2009

Лучше всего, что они создали графическую структуру . Узлы - это пользователи, а "дружба" - ребра.

Держите одну таблицу пользователей, другую таблицу ребер. Затем вы можете сохранить данные о границах, например, «день, когда они стали друзьями» и «утвержденный статус» и т. Д.

20 голосов
/ 17 июня 2009

Скорее всего, это отношение многих ко многим:

FriendList (таблица)

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

EDIT

Таблица пользователей, вероятно, не имеет user_email в качестве PK, возможно в качестве уникального ключа.

пользователи (таблица)

user_id PK
user_email
password
16 голосов
/ 18 июня 2009

Посмотрите на эти статьи, описывающие, как создаются LinkedIn и Digg:

Также могут быть полезны «Большие данные: точки зрения от команды данных Facebook»:

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

Также есть статья, в которой говорится о нереляционных базах данных и о том, как они используются некоторыми компаниями:

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

Вы увидите, что эти компании имеют дело с хранилищами данных, многораздельными базами данных, кэшированием данных и другими концепциями более высокого уровня, чем большинству из нас никогда не приходится сталкиваться ежедневно. Или, по крайней мере, может быть, мы не знаем, что мы делаем.

В первых двух статьях есть много ссылок, которые должны дать вам больше понимания.

ОБНОВЛЕНИЕ 10/20/2014

Мурат Демирбас написал резюме на

  • TAO: распределенное хранилище данных Facebook для социального графа (ATC'13)
  • F4: система хранения больших двоичных объектов Facebook (OSDI'14)

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

НТН

9 голосов
/ 20 августа 2010

Невозможно получить данные из RDBMS для данных друзей пользователя для данных, которые пересекают более полумиллиарда в постоянное время поэтому Facebook реализовал это, используя хеш-базу данных (без SQL), и они открыли базу данных под названием Cassandra.

Таким образом, каждый пользователь имеет свой собственный ключ и данные друзей в очереди; чтобы узнать, как работает Кассандра, посмотрите на это:

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

6 голосов
/ 28 июня 2013

В этой публикации, опубликованной в июне 2013 года, подробно объясняется переход от баз данных отношений к объектам с ассоциациями для некоторых типов данных.

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

Более длинная бумага доступна на https://www.usenix.org/conference/atc13/tao-facebook’s-distributed-data-store-social-graph

5 голосов
/ 17 июня 2009

Вы ищете внешние ключи. По сути, вы не можете иметь массив в базе данных, если у него нет собственной таблицы.


Пример схемы:

    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
4 голосов
/ 12 апреля 2011

Тип графической базы данных: http://components.neo4j.org/neo4j-examples/1.2-SNAPSHOT/social-network.html

Не относится к реляционным базам данных.

Google для графических баз данных.

...