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

Question

[StynuBlizz]

Как реализовано хранение ленты событий (имееться в виду хранение информации о событиях людей на которых я подписан) в бд, в популярных сервисах (Insta,yotube,facebook,vk и т.д)?
Слышал про два способа реализации:

1.Хранение всех событий в одной таблице, что-то вроде:
AUTHOR_ID | POST
001 | ...
002 | ...
005 | ...

2.Хранение индивидуальной ленты для, каждого пользователя (все также храниться в одной таблице,но только каждое событие дублируется для каждого пользователя) что-то вроде:
USER_ID | AUTHOR_ID | POST
001 | 002 | ....
001 | 006 | ....
002 | 001 | ....

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

Вообщем как это все сделано в популярных сервисах?

Answer 1

[Иван Корюков]

Чем вас не устраивает первый вариант и в чём плюсы второго?
Логика подсказывает, что дублировать пост для каждого юзера, который на него подписан это абсурд.
Хотите сказать, что если я делаю пост в группу в которой 100к подписчиков, то я сразу создаю 100к записей в базе?
Количество постов в таблице постов будет больше чем в первом варианте на несколько порядков и это только замедлит выборку.

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

select * from posts join subscribe sub on(...) where sub.user_id=123

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

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

Comments

[jasonOk]

GraphQL

[Иван Корюков]

jasonOk: Посмотрите что о GraphQL пишет фейсбук (который его и придумал) GraphQL, a query language created by Facebook in 2...
Т.е. GraphQL это язык запросов, на что намекают буковки "QL".
Этот язык запросов позволяет указать что вы хотите получить от сервера.
Вопрос в том как хранить данные на сервере, а не как получать их.

[StynuBlizz]

Иван Корюков: Спасибо за ответ. А можете рассказать как по первому варианту делать составление ленты пользователя? У меня из идей только брать список людей на которых подписан пользователь и доставать из этой таблицы событие которые сгенерировали люди из этого списка. Но проблема такого запроса в том что он очень тяжелый (если пользователь подписан например на 1000 человек), даже если всю базу поместить в redis. Вообщем как делать запрос для составление ленты?

[StynuBlizz]

Иван Корюков: Или я ошибаюсь и запрос будет не таким уж тяжелым и долгим?

[StynuBlizz]

Иван Корюков: Плюсов второго варианта по сравнению с его минусами очень мало,а если точнее то он всего один - это возможность отдать ленту пользователя в один SQL запрос.Так что от 2 варианта уже отказался)

[Иван Корюков]

StynuBlizz: Смотрите. Есть таблица с постами, есть таблица с пользователями. Пользователи могут подписываться друг на друга. Причём как пользователь может быть подписан на множество других пользователей, так и на пользователя могут быть подписано множество пользователей. Очевидна связь многие-ко-многим. Поэтому делаем такие таблицы:

user{id, name}
post{id, title, text, id_author, views_count}
subscribe{id, id_subscriber, id_author}

Для того, чтобы получить ленту новостей одного пользователя достаточно сделать один запрос:

select post.*
from subscribe join post on(post.id_author = subscribe.id_author)
where subscribe.id_subscriber = 12345 -- id текущего пользователя

[StynuBlizz]

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

[Иван Корюков]

StynuBlizz: Давайте посчитаем сколько строк обойдёт запрос с join'ами и запрос, но к одной таблице в которой дубли постов.
Пусть есть 100 пользователей, у каждого 100 постов, и пусть каждый пользователь подписан на 10 других.
Предположим (СУБД может оптимизировать, а ещё есть индексы. Пока решим задачу в лоб), что когда выполняется такой запрос СУБД проходит один раз по таблице subscribers (100*10=1к строк).
Для каждой строки у которой id_subscriber = 12345 (таких у нас 10) СУБД ищет посты в таблице post (100*100=10к строк)
Итого получаем, что СУБД проходится по 1000 + 10000*10 = 101 000 строк.

Если мы при публикации поста сразу копируем его подписчикам, то у нас получается, что в таблице постов будет 100*100*10 = 100 000 строк
Да, тут вы правы. Стоит ещё добавить накладные расходы на подтягивание других таблиц и второй способ получается .

Однако стоит, во-первых, раскопать доки о том как СУБД работает с join'ами, а во вторых - как это происходит, когда на столбце есть индекс.
Мне даже стало интересно и я займусь этим когда будет время. Если вы раскопаете это раньше меня, напишите пожалуйста)

[StynuBlizz]

Иван Корюков: По поводу индексов: для индексов лучше использовать второй вариант, так как из 100к строк бд пойдет сразу к дубликатам постов для пользователя (если сделать индексы по id юзера для которого создаются дубликаты) и там уже остается только 1к строк (100 постов * на 10 подписок) из которых и составлять ленту.Но проблема в том что этот вариант очень и очень проигрышный (трата памяти в сотни раз больше (из-за дублирования поста для каждого подписчика),невозможность вести учет для конкретной публикации (количество лайков,просмотров и тд) и прочее неприятности).

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

Вот я и стою в ступоре,так как в 1 варианте трудно и накладно делать выборку, а во втором туева хуча минусов.

[StynuBlizz]

Есть еще вариант совместить эти 2 варианта т.е создать таблицу со всеми событиями и таблицу которая дублирет каждый пост для каждого подписчика,но вместо того чтобы хранить весь пост хранить только его идентификатор. Тогда будет проще делать выборку по 1 таблице. Но что-то мне кажеться не сильно от этого можно в плюс уйти

[StynuBlizz]

Странно что в интернете нету нормальных статей на эту тему

[Иван Корюков]

StynuBlizz:

джоинов,то про них я думаю лучше вообще забыть,так как будет страдать производительность да и шардиться будет невозможно

шта?)

У меня на работе мы вовсю используем джоины. Там в таблицах минимум 5-10к записей, а в особо тяжёлых уже два ляма. Два-три джоина большого проседания не создают.

[Иван Корюков]

StynuBlizz:

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

Поздравляю, вы изобрели таблицу связи многие-ко-многим, просто решили делать не join а отдельный запрос)
Вообще, чем гадать, лучше сделать тестовую базу и на неё опробовать все варианты)

[StynuBlizz]

Иван Корюков: Ну даже если и производительность страдает не сильно то с шардингом у джоинов большие проблемы

[StynuBlizz]

Иван Корюков: А как сделать тестовую базу с 100к уникальных записей?

[Иван Корюков]

StynuBlizz: очевидно - написать скрипт, который, используя rand() и некоторые предопределённые массивы данных, будет забивать базу "уникальным" контентом.
Нам что важно? Пользователи, посты и их связи. Говно-вопрос, в цикле пишем в базу 100 пользователей. потом для каждого с помощью rand() получаем число людей на кого он подписан - пусть будет от 0 до 20.
Далее в цикле по количеству подписок генерируем число от 1 до 100 (исключая свой id), которое будет id пользователя на кого мы подписаны.
далее для каждого пользователя забиваем посты, по такой же схеме - определяем великим рандомом сколько у каждого юзера постов, и вставляем строки в БД. Нам же не важна суть текста постов. Можно просто случайные строки случайной длинны пихать.
Изи.

[StynuBlizz]

Иван Корюков: Окей,спасибо,как сделаю отпишусь о результатах)

[Иван Корюков]

StynuBlizz: Помимо бенчмарка (ну запускаем выборку 100к раз и замеряем время), который можно провести на такой БД, полезно будет проанализировать исполнение запроса. Например для MySQL можно использовать MySQL Workench

[Иван Корюков]

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

Answer 2

[RidgeA]

Поищите доклад Arsen Kostenko How Twitter Works, вот например https://www.youtube.com/watch?v=tlPkM0lxMKc

Если коротко - лента для каждого пользователя рассчитана заранее.
Но

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

- 100%