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

Question

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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 и узнать.Таким образом, вы избегаете включения всех пользователей в список друзей, а затем присоединения их друзей к таблице событий.