Дизайн базы данных Facebook?

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

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

user_email PK
user_id PK
password 

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

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

Что-то вроде этого?

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N 

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

Сохраните таблицу друзей, которая содержит UserID, а затем UserID друга (мы назовем его 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), потому что они уже представлены в другом направлении. Для примеров, когда дружба или другие отношения не являются явно двусторонними, вам также понадобятся эти строки для обозначения двусторонних отношений.

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

TL; DR:

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

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

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

• TAO: распределенное хранилище данных Facebook для социальной сети
• ТАО: Сила графа .

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

Видео и статья расскажут вам несколько вещей:

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

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

Что ж, это график. :) Он не говорит вам, как построить это на 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 тыс. Пользователей и 18 секунд для 1 миллиона пользователей.

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

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

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

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

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

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

FriendList (таблица)

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

РЕДАКТИРОВАТЬ

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

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

user_id PK
user_email
password

Взгляните на эти статьи, описывающие, как устроены LinkedIn и Digg:

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

Также может быть полезен «Большие данные: точки зрения команды данных 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

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

На первые две статьи есть много ссылок, которые должны дать вам больше информации.

ОБНОВЛЕНИЕ 20.10.2014

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

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

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

НТН

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

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

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

В этом недавнем сообщении от июня 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.

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

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

    Таблица пользователей
        userID PK
        другие данные
    Стол друзей
        userID - FK для таблицы пользователей, представляющей пользователя, у которого есть друг.
        friendID - таблица FK для пользователей, представляющая идентификатор пользователя друга

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

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

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

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

Что касается производительности таблицы «многие ко многим», если у вас есть 2 32-битных int, связывающих идентификаторы пользователей, ваше базовое хранилище данных для 200000000 пользователей, в среднем по 200 друзей на каждого, составляет чуть менее 300 ГБ.

Очевидно, вам потребуется некоторое разбиение и индексация, и вы не собираетесь хранить это в памяти для всех пользователей.

Вероятно, есть таблица, в которой хранится отношение друг <-> пользователь, скажем «frnd_list», с полями user_id, frnd_id.

Каждый раз, когда пользователь добавляет другого пользователя в друзья, создаются две новые строки.

Например, предположим, что у меня идентификатор 'deep9c', и я добавляю пользователя с идентификатором 'akash3b' в качестве друга, затем в таблице «frnd_list» создаются две новые строки со значениями ('deep9c', 'akash3b') и ('akash3b », 'deep9c').

Теперь при показе списка друзей конкретному пользователю простой sql сделает это: «выберите frnd_id из frnd_list, где user_id =», где - идентификатор вошедшего в систему пользователя (хранится как атрибут сеанса).