Проектирую "Ленту событий" для социального проекта?
Постановка задачи следующая:
1) У каждого пользователя есть друзья («максимальный» вариант — все в друзьях у всех)
2) Каждый пользователь может входить в неограниченное количество групп
Пользователь может как генерировать контент самостоятельно (похоже на личную «Стену», как у ВКонтакте и ФБ), так контент может генерироваться компонентами внутри проекта.
Хочется сделать сводную ленту обновлений как статусов/мыслей пользователя, его друзей, внутренних событий и событий групп и вывести их единым списком с возможностью листания.
В бэкэнде у системы крутится СУБД MySQL, но лично для меня вполне очевиден тот факт, что «обычный» реляционный подход к решению задачи в общем случае не применим из-за накладываемых ограничений — если друзей, к примеру, 2500+, то один WHERE разрастается до чудовищных размеров.
Потому смотрю в сторону noSQL решений, но изначально для себя хочу просто уяснить сам алгоритм работы подобной ленты, а потом уже подбирать инструментарий.
Следует ли применять денормализацию — играться с ведением отдельной ленты для каждого пользователя (но в случае выхода из групп или удаления человека из друзей обновление этого списка может занимать огромное время)?
Может, есть какие-то статьи по поводу или признанные варианты реализации?
На всяких фейсбуках и вконтактах данные ленты генерирует демон на компилируемом языке, который к тому же кучу информации кеширует в памяти. Осилите? Ну не знаете Си, можете попробовать на Node или Java написать, ну или на PHP в крайнем случае, если заложить возможность масштабирования, тоже будет ОК до поры до времении.
Алгоритм работы примерно такой: 1) выбираем id друзей юзера 2) выбираем последние события у каждого из них 3) отсеиваем защищенные приватностью 4) склеиваем списки, сортируем по дате и отдаем в браузер.
А на MySQL у вас с ростом нагрузки, числа друзей все это быстро положит сервер. Сделаем простейший расчет: средний юзер делает 10 событий в день, если юзеров хотя бы несколько тысяч, таблица событий быстро подпрыгнет в размере до миллионов записей. А всякие конструкции типа JOIN во-первых, грузят сервер, во-вторых, не шардятся.
Написание демона не есть проблема, потому вопрос был сугубо теоретический — инструмент я выберу уже после осознания нужного пути.
Если я верно Вас понял, то Вы выступаете против денормализации базы в пользу выборок в пользу чего-то похожего на map/reduce (кластеризации видов активности по некоторым первичным признакам, параллельной обработке их отдельными модулями и конечным склеиванием результатов перед выдачей в браузер).
Это довольно близко к тому, что пока вывел для себя я, а именно — хранить долговременные данные в СУБД, кешируя актуальные (например, за последнюю неделю) в noSQL решении типа MongoDB, кластеризируя их, для начала, по типам активности и дате. При новом запросе «на ленту из X событий» изначально запрашивать по X событий из каждого узла данных, сортировать по времени /приватности и сохранять уже в «горячем» кеше приложения.
При обновлении событий менять как сам «горячий» кеш, так и СУБД / noSQL хранилище. В особо сложных случаях «горячий» кеш перегенерируется.
1) с дорогим SELECT, но дешевым INSERT: делаем табличку вида (user_id, event_id, time, event_details), при возникновении события делаем 1 INSERT, а чтобы прочитать ленту событий, выбираем id всех друзей пользователя и делаем SELECT * FROM events WHERE user_id IN :friendIds ORDER BY time DESC LIMIT :limit. Вставка дешевая, но выборка — не оптимизируется: мы либо используем ключ на time, либо на user_id, но не оба. То есть, при большой истории событий, большом числе событий или числе пользователей SELECT будет тормозить, дай бог каждому. Интуиция подсказывает мне что при сколько-либо серьезной нагрузке выборки с Filesort положат базу.
2) С дешевым селект, но дорогим инсертом. Это, когда мы ведем каждому юзеру в таблице свою ленту событий друзей, а при возникновении события вставляем его в ленты всем друзьям. SELECT здесь будет иметь вид SELECT * FROM events WHERE feed_user_id = :userId ORDER BY time DESCLIMIT :limit. При этом варианте, если у юзера есть 100 друзей и он к примеру загрузил фотку. надо сделать 100 INSERT в ленты всем его друзьям. Это вообще проигрышный вариант, хотя если хранение и «добавление в 100 лент нового события» переложить на плечи демона, шансы какие-то появляются.
Вы, как я понимаю, выступаете за вариант 1 с кешированием в noSQL части данных? А как вы кеш обновлять будете? Кто-то загрузил фотку, и вы сбрасываете ключи кеша у всех его друзей? Так в этом случае кеш будет постоянно сброшен и фактически бесполезен. А если делать обновление кеша у 100 друзей, так это 100 запросов к NoSQL хранилищу.
Я не вижу, чем тут поможет NoSQL — и 1) и 2) неэффективны при большом числе пользователей и друзей (хотя, я знаю, есть храбрые индусы, делающие ленты активности на PHP и MySQL, но не знаю, как они себя ведут под нагрузкой).
Потому вариант с демоном — это фактически вариант 1), только вместо использования БД, данные кешируются в памяти демона, если памяти есть гигабайты, а старые события удалять из кеша, то можно закешировать вообще все ленты всех пользователей проекта.
И вообще, NoSQL — это не магическая пуля. Вы точно также либо используете индексы (и получаете те же плюсы и минусы, что SQL), либо тупо используете из как key-value хранилище.
Но важно, конечно, сколько у вас пользователей, какая у них, активность, из этого можно прикинуть объемы и частоту запросов и делать выводы.
Есть такая вешь как кеш. Кеш бывает разных видов, это не только выборка хранящаяся в файлике под рукой. Банальный пример карма на хабре. Я точно уверен что у них в базе хранится все данные, кто кому куда сколько раз ткнул плюсик или минусик, но видим мы лишь 3 (+4- 1). Своеобразный кеш нужных данные в отдельном месте. Вынесите связи отдельно специально для это й ленты, дублируйте данные, не бойтесь, дубли иногда помогают в производительности. Допустим сделайте для начала табличку активности:
id, user_id, event_desc, event_date
И при каждой активности заносите сюда данные, эта до невозможности простая табличка может одним запросом вывести всю активность пользователя в примитивном виде. Дальше уже развивайте мысль как удобно =)
Не понял, если честно задачи. Вроде бы ничего сложного.
В псевдокоде выглядит что-то вроде
select news.*
from news, users_users as friends
where friends.left_user = :currentUser
and friends.right_user = news.user_id
union
select news.*
from news, groups
where groups_users.user_id = :currentUser
and groups_users.group_id = news.group_id
Мне кажется, что производительность такого решения при большом (сотни тысяч, миллионы) количестве пользователей и, соответственно, генерируемого контента и событий является неподъемной ни для одной известной СУБД.
Вот еще один пример где RDBMS не уперся и надо использовать, что-то на подобии MongoDB/CouchDB или Neo4j (если данные сильно связанные).
Сделать сначала массив всех ObjectiveID с которыми связан пользователь (один запрос), а потом разов взять все события где автор события находится в этом массиве. Или через DBRef находим, что у события есть связь с текущим пользователем. Первый вариант будет быстрее, но меньше кода,
В фейсбуках и твиттерах используется денормализация, причем «очистка» ленты после ухожа из группы/друзей у них отсутствует. Банально — что получено в ленту, то получено. Кроме того лента на фб вроде ограничена по времени, это разумно. В твиттере тоже была проблема с огромной лентой пользователей у которых 20k+ подписок, таких одно время просто банили. В целом — кладем так как удобнее доставать, вариантов достать должно быть немного. Нормализация это не для больших объемов. Да и денормализированный mysql не для больших, если только не разбивать по инстансам (скажем, максимум 100 юзеров со всеми их данными/лентами в одной базе).
Взгляние в сторону Redis и из Sorted set. Каждый сет — лента какого-то человека, в качестве score — ID событий (можно время), редис может держать около 200 000 запросов в секунду, и сам на лету сортирует, умеет делать запросы по обычным лимитам/офсетам либо запросы вида ID < x
Сам же объект — сериализованный массив (ну или как вам улдобнее), а сам объект номера уже берется из мемкеша например. Собственно, как писал товарищ denver, используйте денормализацию.
Описанный метод успешно работает на достаточно посещаемом ресурсе, и легко справляется со случаем, когда человек с 30000 фолловеров создает пост.
тоже, в «псевдосоциальной» сети, делали на Redise.
Формировали ленты пользователей — для каждого в отдельности. Хранили индексы данных с типом источника события. Сортировали по score или по id, собственно это и позволяло делать «автоподъём» событий (в scrore хранили time() ) и выводить в хронологическом порядке события.
но почему-то больше 40-50к в секунду нашим админам не удалось подняться. php + Rediska.
При небольших объёмах бегает шустро. Осталась актуальной проблема — как хранить «историю».
