Проектирование новостной ленты в социальных сетях

26 листопада 2014
Олег Полудненко, Senior PHP Developer

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

Мой рассказ будет о том, как я, превозмогая трудности, решал задачу формирования новостной ленты. А еще расскажу о подходах, которые наработали ребята из проекта Socialite, и которыми они поделились на MongoDB World.

Как формировать ленту?

Итак, для начала абсолютно банальная информация о том, что любая новостная лента формируется из активности пользователей, с которыми мы дружим (либо которых мы фолловим/читаем/etc). Следовательно, задача формирования ленты — задача доставки контента от автора его фолловерам. Лента, как правило, состоит из совершенно разношерстного контента: котиков, коубов, комедийных видео, каких-то текстовых статусов и прочего. Поверх этого мы имеем репосты, комменты, лайки, тегирование пользователей на этих самых статусах/фоточках/видео. Следовательно, основные задачи, возникающие перед разработчиками социальной сети:

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

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

Формируем ленту при чтении

Подход предусматривает формирование ленты на лету. Т. е. когда пользователь запрашивает свою новостную ленту, мы вытягиваем из контент-сервиса записи людей, на которых подписан пользователь, сортируем их по времени и получаем новостную ленту. Вот, в общем-то, и все. Думаю, что это наиболее очевидный и интуитивно понятный подход. На схеме выглядит он примерно так:

2

Когда пользователь постит что-то новое, процесс абсолютно тривиален: необходимо сделать всего одну запись в сервис контента. Эта простота и неудивительна, т. к. доставка ленты идет при чтении, а значит, все самое интересное — именно там.

ОК, переходим к чтению ленты. Чтобы сформировать ленту для конкретного пользователя, нужно взять список людей, на которых он подписан. С этим списком мы идем к контент-сервису и вытягиваем посты этих людей.

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

Но это еще не самая большая проблема подхода. Очевидно, что по мере роста сети быстрее остальных будет расти коллекция контента. И рано или поздно наступит необходимость шардировать эту коллекцию. И, естественно, шардирование будет происходить по авторам контента (например, по их ID). Так вот, самый большой минус подхода заключается в том, что наш запрос будет затрагивать очень большое количество произвольных шардов. Если вы, конечно, не фолловите одного человека.

Давайте теперь тезисно подведем итоги по доставке лены на чтение.

Из плюсов:

  • Простота реализации. Именно поэтому такой подход хорошо использовать по дефолту. Например, чтобы быстро сделать работающую демоверсию, Proof on Concept, etc.
  • Отсутствие необходимости дополнительного хранилища для копий контента у фолловеров.

Теперь о минусах:

  • Чтение ленты затрагивает многие шарды, что, без сомнения, скажется на скорости такой выборки.
  • А это, скорее всего, потянет за собой необходимость дополнительного индексирования.
  • Необходимость выбирать контент с запасом.

Формируем ленту при записи

Давайте подойдем к проблеме немного с другой стороны. Что, если для каждого пользователя хранить уже готовую новостную ленту и обновлять ее каждый раз, когда его друзья будут постить что-то новое? Другими словами, мы будем делать копию каждого поста автора в «материализованную» ленту его подписчиков. Этот подход чуть менее очевиден, но ничего сверхсложного в нем тоже нет. Самое важное в нем — найти оптимальную модель хранения этой самой «материализованной» ленты у каждого пользователя.

3

И так, что же происходит когда пользователь постит что-то новое? Как и в предыдущем случае, пост отправляется в сервис контента. Но теперь мы дополнительно делаем копию поста в ленту каждого подписчика (на самом деле, на этой картинке стрелочки, идущие в сервис ленты, должны начинаться не из поста автора, а из сервиса контента). Таким образом, у каждого пользователя формируются уже готовые для чтения персональные ленты. Очень важно и то, что при шардировании данных из сервиса ленты использоваться будут ID подписчиков, а не авторов (как в случае с сервисом контента). Соответственно, теперь читать ленту мы будем из одного шарда, и это даст значительное ускорение.

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

Есть еще один, куда более ощутимый недостаток — необходимость где-то хранить все наши «материализованные» ленты. Т. е. это необходимость в дополнительном сторадже. И, если у пользователя есть 15.000 фолловеров, весь его контент будет постоянно храниться в 15.000 тысячах копий. И это выглядит уже совсем не круто.

И кратенько о преимуществах и недостатках.

Из плюсов:

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

О минусах:

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

Модели хранения «материализованных» лент

Как вы догадываетесь, просто так мириться с проблемами мы не будем, тем более, скролл еще только на середине статьи :-). И здесь нам на помощь приходят ребята из MongoDB Labs, которые разработали целых три модели хранения «материализованных» лент. Каждая из них, так или иначе, решает описанные выше недостатки.

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

Группируем по времени

Эта модель подразумевает, что все посты в ленте за определенный временной интервал (час/день/etc.), группируются в одном документе. Такой документ ребята из MongoDB Labs называют «бакетом». В нашей же постхэллоуинской стилистике они изображены колбочками:

4

Пример с MongoDB Documents

{     "_id": {"user": "vasya", "time": 516935},     "timeline": [         {"_id": ObjectId("...dc1"), "author": "masha", "post": "How are you?"},         {"_id": ObjectId("...dd2"), "author": "petya", "post": "Let's go drinking!"}     ]  },  {     "_id": {"user": "petya", "time": 516934},     "timeline": [         {"_id": ObjectId("...dc1"), "author": "dimon", "post": "My name is Dimon."}     ]  },  {     "_id": {"user": "vasya", "time": 516934},     "timeline": [         {"_id": ObjectId("...da7"), "author": "masha", "post": "Hi, Vasya!"}     ]  }  

Все, что мы делаем, — округляем текущее время (например, берем начало каждого часа/дня), берем ID фолловера, и upsert'ом записываем каждый новый пост в свой бакет. Таким образом, все посты за определенный интервал времени будут сгруппированы для каждого подписчика в одном документе.

Если за прошлый день люди, на которых вы подписаны, написали 23 поста, во вчерашнем бакете вашего пользователя будет ровно 23 записи. Если же, например, за последние 10 дней новых постов не было, новые бакеты создаваться не будут. Т. ч. в определенных случаях этот подход будет весьма удобен.

Самый главный недостаток модели — создаваемые бакеты будут непредсказуемого размера. Например, в пятницу все постят пятничные коубы, и у вас в бакете будет несколько сотен записей. А на следующий день все спят, и в вашем субботнем бакете будет 1-2 записи. Это плохо тем, что вы не знаете, сколько документов вам надо прочитать, чтобы сформировать нужную часть ленты (даже начало). А еще можно банально превысить максимальный размер документа в 16 Мб.

Группируем по размеру

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

5

Пример с MongoDB Documents

{     "_id": ObjectId("...122"),     "user": "vasya",     "size": 3,     "timeline": [         {"_id": ObjectId("...dc1"), "author": "masha", "post": "How are you?"},         {"_id": ObjectId("...dd2"), "author": "petya", "post": "Let's go drinking!"},         {"_id": ObjectId("...da7"), "author": "petya", "post": "Hi, Vasya!"}     ]  },  {     "_id": ObjectId("...011"),     "user": "petya",     "size": 1,     "timeline": [         {"_id": ObjectId("...dc1"), "author": "dimon", "post": "My name is Dimon."}     ]  }  

Приведу пример. Установим лимит на бакет в 50 записей. Тогда первые 50 постов мы записываем в первый бакет пользователя. Когда настает черед 51-го поста, создаем второй бакет для этого же пользователя и пишем туда этот и следующие 50 постов. И т. д. Таким нехитрым образом мы решили проблему с нестабильным и непредсказуемым размером. Но такая модель работает на запись примерно в два раза медленнее, чем предыдущая. Связанно это с тем, что при записи каждого нового поста необходимо проверять, достигли ли мы установленного лимита или нет. И, если достигли, создавать новый бакет и писать в уже в него.

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

Кэшируем топ

И наконец, последняя модель хранения ленты, которая должна решить все-все накопившиеся проблемы. Или, по крайней мере, сбалансировать их.

6

Пример с MongoDB Documents

{     "user": "vasya",     "timeline": [         {"_id": ObjectId("...dc1"), "author": "masha", "post": "How are you?"},         {"_id": ObjectId("...dd2"), "author": "petya", "post": "Let's go drinking!"},         {"_id": ObjectId("...da7"), "author": "petya", "post": "Hi, Vasya!"}     ]  },  {     "user": "petya",     "timeline": [         {"_id": ObjectId("...dc1"), "author": "dimon", "post": "My name is Dimon."}     ]  }    

Основная идея этой модели заключается в том, что мы кэшируем некоторое количество последних постов, а не храним всю историю. Т. е. по сути бакет будет представлять собой capped-array, хранящий некоторое количество записей. В MongoDB (начиная с версии 2.4) это делается очень просто с использованием операторов $push и $slice.

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

Далее. Если пользователь длительное время не заходит в наш сервис, мы можем просто удалить его кэш. Таким образом, мы исключим неактивных пользователей из процесса создания «материализованных» лент, высвобождая ресурсы наших серверов. Если же неактивный пользователь вдруг решит вернуться, скажем, через год, мы легко создадим для него новенький кэш. Заполнить его актуальными постами можно, используя fallback в простую доставку на чтение.

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

Embedding vs Linking

И еще один важный момент касательно хранения ленты в кэше: хранить контент постов или только ссылку?

Подход с хранением полной копии постов прямо в бакете будет хорош, если контент постов — небольшого и, главное, известного размера. В качестве идеального примера можно привести Twitter с его 140-символьными статусами.

В общем же случае выигрывает второй подход, когда мы храним ID поста и, возможно, какие-то метаданные (например, ID автора, дату публикации и прочее). Контент же вытягивается только при необходимости. При чем сделать это, имея ID, поста можно очень легко и быстро.

Что, если я очень ленив?

В XXI веке на каждого лентяя существует примерно 100500 приложений на каждый случай жизни. Соответственно, для каждого разработчика существует чуть меньше чем 100500 сервисов. Клевый сервис управления лентой живет здесь.

На этом у меня все. Хочу лишь сказать, что серебряной пули для решения всех проблем формирования новостной ленты ожидаемо не нашлось. Но мы рассмотрели целую кучу решений и подходов, каждый из них будет хорошо работать в конкретной ситуации.