Как сайты социальных сетей вычисляют обновления друзей?

Question

Сайт социальной сети, вероятно, ведет таблицы для пользователей, друзей и событий ...

Как они используют эти таблицы для эффективного и масштабируемого вычисления событий друзей?

Answer 1

Многие сайты социальных сетей, такие как Twitter, вообще не используют СУБД, кроме приложения очереди сообщений. Многие из них начинают с уже существующего приложения, такого как RabbitMQ. Некоторые из них становятся достаточно большими, и им приходится сильно настраивать или создавать свои собственные. Твиттер находится во втором процессе.

Приложение очереди сообщений работает, удерживая сообщения от одной службы для одной или нескольких других служб. Например, скажем, сервис Frank публикует сообщения в очереди foo. Джо и Джилл подписаны на очередь Фрэнкс Фу. приложение будет следить за тем, получили ли Джо или Джилл сообщения, и как только каждый подписчик в очереди получил сообщение, оно отклоняет его. Фрэнк запускает сообщения и забывает об этом. Джо и Джилл просят сообщения от foo и получают те сообщения, которые они еще не получили. Джо и Джилл делают все, что им нужно сделать с сообщением. Возможно держать это вокруг возможно, нет.

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

РЕДАКТИРОВАТЬ: Я должен также упомянуть, что обычно хранилище для таких вещей в больших масштабах сильно денормализовано. Так что Джо и Джилл могут хранить копию одного и того же сообщения. Это считается нормальным, потому что помогает масштабировать приложение до миллиардов пользователей.

Другое чтение:

1. http://www.rabbitmq.com/
2. http://qpid.apache.org/

Answer 2

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

Два популярных способа представления графиков: списки смежности и матрицы смежности .

Список смежности - это просто список ребер на графе. Рассмотрим пользователя с целочисленным идентификатором пользователя.

User1, User2
  1      2
  1      3
  2      3

Ненаправленная интерпретация этих записей заключается в том, что пользователь 1 дружит с пользователями 2 и 3, а пользователь 2 также дружит с пользователем 3.

Представление этого в таблице базы данных тривиально. Мы знакомы с таблицей соединений «многие ко многим». Запросы SQL для поиска друзей определенного пользователя довольно легко написать.

Теперь, когда вы знаете друзей конкретного пользователя, вам просто нужно присоединить эти результаты к таблице обновлений. Эта таблица содержит все обновления пользователя, проиндексированные по идентификатору пользователя.

Если все эти таблицы правильно проиндексированы, вам будет довольно легко разработать эффективные запросы для ответа на интересующие вас вопросы.

Answer 3

Трэвис написал отличный пост на эту тему,

Журналы активности и каналы друзей на Rails & pfeed

Answer 4

В небольших масштабах объединение пользователей users.friends и users.events и кэширования запросов, вероятно, хорошо, но замедляется довольно быстро по мере роста числа друзей и событий. Вы также можете попробовать модель, основанную на событиях, в которой каждый раз, когда пользователь создает событие, в таблице соединений создается запись (возможно, называемая "friends_events"). Таким образом, всякий раз, когда пользователь хочет увидеть, какие события создали его друзья, он может просто сделать соединение между своим идентификатором и таблицей friends_events и выяснить это. Таким образом, вы избегаете захватывать всех пользователей с друзьями, а затем присоединять их к таблице событий.