Как сайты социальных сетей вычисляют обновления друзей?
Сайт социальной сети, вероятно, поддерживает таблицы для пользователей, друзей и событий...
Как они используют эти таблицы для эффективного и масштабируемого вычисления событий друзей?
4 ответа
Многие сайты социальных сетей, такие как Twitter, вообще не используют СУБД, кроме приложения очереди сообщений. Многие из них начинают с уже существующего приложения, такого как RabbitMQ. Некоторые из них становятся достаточно большими, и им приходится сильно настраивать или создавать свои собственные. Твиттер находится в процессе сделать это во второй раз.
Приложение очереди сообщений работает, удерживая сообщения от одного сервиса для одного или нескольких других сервисов. Например, скажем, сервис Frank публикует сообщения в очереди foo. Джо и Джилл подписаны на очередь Фрэнкс Фу. приложение будет следить за тем, получили ли Джо или Джилл сообщения, и как только каждый подписчик в очереди получил сообщение, которое он отбрасывает. Фрэнк запускает сообщения и забывает об этом. Джо и Джилл просят сообщения от foo и получают те сообщения, которые они еще не получили. Джо и Джилл делают все, что им нужно сделать с сообщением. Возможно держать это вокруг, возможно нет.
Приложение очереди сообщений гарантирует, что каждый, кто должен получить сообщение, может и получит сообщение, когда они его запросят. Издатель может отправлять сообщения с уверенностью, что подписчик может получить их в конце концов. Преимущество состоит в том, что он полностью асинхронный и не требует дорогостоящих соединений.
РЕДАКТИРОВАТЬ: я должен также упомянуть, что обычно хранилище для таких вещей в больших масштабах сильно денормализовано. Так что Джо и Джилл могут хранить копию одного и того же сообщения. Это считается нормальным, потому что помогает приложению масштабироваться до миллиардов пользователей.
Другое чтение:
Основой структуры данных социальных сетей является график. На фейсбуке график не ориентирован (когда вы чей-то друг, он - ваш друг). В твиттере указывается график (вы следуете за кем-то, но они не обязательно следуют за вами).
Два популярных способа представления графов - это списки смежности и матрицы смежности.
Список смежности - это просто список ребер на графе. Рассмотрим пользователя с целочисленным идентификатором пользователя.
User1, User2
1 2
1 3
2 3
Ненаправленная интерпретация этих записей заключается в том, что пользователь 1 дружит с пользователями 2 и 3, а пользователь 2 также дружит с пользователем 3.
Представление этого в таблице базы данных тривиально. Мы знакомы с таблицей соединений "многие ко многим". Запросы SQL для поиска друзей конкретного пользователя довольно легко написать.
Теперь, когда вы знаете друзей конкретного пользователя, вам просто нужно присоединить эти результаты к таблице обновлений. Эта таблица содержит все обновления пользователя, проиндексированные по идентификатору пользователя.
Пока все эти таблицы правильно проиндексированы, вам будет довольно легко разработать эффективные запросы, чтобы ответить на интересующие вас вопросы.
Трэвис написал отличный пост на эту тему,
В небольших масштабах объединение пользователей users.friends и users.events и кэширование запросов, вероятно, хорошо, но замедляется довольно быстро по мере роста числа друзей и событий. Вы также можете попробовать модель, основанную на событиях, в которой каждый раз, когда пользователь создает событие, в таблице соединений создается запись (возможно, называемая "friends_events"). Таким образом, всякий раз, когда пользователь хочет увидеть, какие события создали его друзья, он может просто сделать соединение между своим идентификатором и таблицей friends_events и выяснить это. Таким образом, вы избегаете захватывать всех пользователей с друзьями, а затем присоединять их к таблице событий.