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



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

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

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


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

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

    2. Доставка пользовательского контента его фолловерам. Поручим этот процесс сервису ленты, который представлен колбочками. Таким образом, когда пользователь хочет почитать свою ленту, он идёт за своей персональной колбочкой, берёт её, с ней подходит к котелку и мы наливаем ему нужный кусочек контента.

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

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


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



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

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

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

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

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

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


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


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



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

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

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

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

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

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


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

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

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

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


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


    Пример с 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Мб.

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


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


    Пример с 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 постов. И так далее. Таким нехитрым образом мы решили проблему с нестабильным и непредсказуемым размером. Но такая модель работает на запись примерно в 2 раза медленнее, чем предыдущая. Связанно это с тем, что при записи каждого нового поста необходимо проверять достигли ли мы установленного лимита или нет. И если достигли, то создавать новый бакет и писать в уже в него.

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

    Кэшируем топ


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


    Пример с 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 сервисов. Клёвый сервис управления лентой живёт здесь.

    На этом у меня всё. Хочу лишь сказать о том, что серебряной пули для решения всех проблем формирования новостной ленты ожидаемо не нашлось. Но мы рассмотрели целую кучу решений и подходов, каждый из которых будет хорошо работать в своей конкретной ситуации.
    DataArt
    113.55
    Технологический консалтинг и разработка ПО
    Share post

    Comments 68

      +3
      не понял а при чем здесь хаб BigData. Ну разбили ленту на шарды — проблема-то? простой паттерн шардирования. Для борьбы с разбуханием данных используем виртуальный шардинг, где данные по шардам разводятся не по алгоритму — остаток от деления иди юзера, а через специальный конфиг, в котором можно задавать вес шарды. Другой вопрос в том, что автор правильно заметил, что новостная лента нужна на определенный срок, и нас на врядли бы заинтересовали новости друзей годичной давности… К сожалению — описываемый подход применим к любителям монги. Однако, при использовании виртуального шардинга, с легкостью можно чистить устаревшие шарды.
        0
        Добавил BigData, т.к. обычно при решении задачи формирования ленты сталкиваешься с большими объёмами данных. И описанные здесь подходы по организации больших данных вполне применимы не только при работе с MongoDB.

        Про виртуальный шардинг — весьма интересно, раньше не слышал о нём. Возможно у вас есть пару полезных ссылок?
          0
          гуглите в сторону virtual buckets
            0
            Спасибо
        +3
        А расскажите, какие нагрузки выдерживали Ваши разработанные соцсети?

        Я вот честно до сих пор воспринимаю MongoDb как сырое решение, не заточенное для production.
        Поэтому первая мысль для решения такой задачи — использовать распределенный индекс для хренения всех постов в виде (user_id, post_id, time) — например ElasticSearch. Пробовали? Какие результаты?
          +2
          ничего ж не мешает пойти на сайт и посмотреть, что ее используют в продакшине очень многие. www.mongodb.org/about/production-deployments/
            +1
            Я прекрасно понимаю, что есть куча компаний, использующие ее. Более того, даже знаю системы, работающие с реальными деньгами, которые имеют только MongoDB на уровне storage (и которые всю транзакционность врукопашную писали). Но это не меняет того факта, что она у меня дико косячила и косячила у других людей — чьими историями завален интернет. И тот же PostgreSQL на порядок быстрее и надежнее (ну да, шардинга нормального нет… но его же можно реализовать, не? и вообще virtual shards сейчас в моде, а монга так вроде не умеет).
              +1
              берите CouchBase
            0
            Где-то до полумилионна записей (постов) в день.

            Что мне особенно нравится в MongoDB, так как отличная динамика развития продукта. И то что было даже год назад, не идёт ни в какое сравнение с тем, что есть сегодня.

            Ваш вариант с ElasticSearch выглядит весьма интересно, но нет, я так не пробовал.
              0
              Тот же wb.ru использует mongo
                0
                Да ладно? А почему они тогда держат целую команду разработчиков SQL Server?
                Или у них монга не основной storage?
                  –1
                  MSSQL используется для других задач.
                  Сам сайт работает на MongoDB

                  Некоторые магазины тоже так делают.
                  К примеру данные в MSSQL для 1С а сайт на MySQL (Percona) с прослойкой redis, не буду говорить какой магазин так работает))
                  Видимо wb примерно так же использует.
                    0
                    Это предположение или факт?
                    Зачем им целый отдел MS SQL под «другие задачи»?
                    Как работает магазин на СУБД, которая не обеспечивает надежность хранения?

                    Объявление о работе недвусмысленно говорит нам, что сайт wb.ru таки на MS SQL работает www.sql.ru/forum/1070106/trebuetsya-programmist-ms-sql

                    Mongo если и есть, то только для кеша.
                      –1
                      Прослойка на redis это всего лишь кеш. От него не требуется ни обслуживать сложные запросы, ни обеспечивать надежное долговременное хранение, ни разруливать транзакционность, ни сохранять консистентность. А от MSSQL\MySQL или любой другой SQL базы все это требуется.

                      Монга же пытается сделать вид что она умеет все, что умеет SQL база, но при этом быстро работает. По факту и работает не быстро, и не умеет нифига толком.
                        0
                        Видимо с redis вы мало работали. Да и с mongo.

                        Данные из магазина в торговом центре, поступают в MSSQL.
                        А теперь давайте подумаем, как нам синхронизировать все операции и в интернет магазине и в оффлайне, да еще не забыть про товарищей из бухгалтерии, склада и т.д.

                        На помощь нам придут другие технологии. В данном случае redis. В других mongo или еще что.
                          0
                          Ага, проблема во мне, конечно.

                          Синхронизировать все операции позволяет SSIS — бесплатный компонент SQL Server. Зачем там Mongo или Redis для меня загадка. Может приведете пример как оно может помочь?
                            0
                            Зачем wb.ru mongo? Это наверное лучше все же у них спросить.

                            В другом проекте, все оч. просто.
                            Прошла операция на кассе, в следствии чего данные обновились в mssql.
                            В тот же момент покупатель приобрел товар (сотни товаров) в интернет магазине (mysql).
                            Т.е. мы имеем 2 БД которые не как не пересекаются и на старте имеют разную структуру данных, после определенных операций, мы имеем еще более разные данные.
                            А еще есть специализированный торговый софт, который имеет свои данные и свою структуру и свою бд.

                            Теперь же, нам надо обновить товары. Так что бы в магазине (оффлай), складе, интернет магазине и т.д., данные совпадали.
                            Вы ведь понимаете, если данные будут разные, то можно продать товар которого уже нет. А это проблемы, которые никому не нужны.

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

                            Почему разные БД и такой зоопарк? Так Москва не сразу строилась, сначала было одно, затем появилось другое/третье… Затем все объединилось.

                            Я ведь не говорю что так надо делать, что это правильно.
                            Я указал что использует wb. Почему это так? Повторюсь: спросите у разработчиков.
                            Но предположения есть, wb, зарождался за долго до их популярности.
                            Сначала там работал один программист, который на коленке сваял что то. Затем их стало больше.
                            Через год пару первых программистов ушло и т.д. За 2-3 года сменилось много разработчиков, и каждый привносил свое.
                            Когда пошли инвестиции, когда компания стала акционерной, то появились уже не только разработчики но и менеджеры, тим лиды, ИТ деректора и все что должно быть в крупных компаниях.
                            Вот тогда то и начали все структурировать, разгонять, чистить. Но основу не убрали.

                            P.S.
                            Замечу что C# ASP.NET (код с нуля без фреймворка) + MongoDB работает и по сей день довольно быстро.
                              0
                              Откуда уверенность что там монга? Я в открытых источниках не нашел такой инфы, а верить на слово как-то не привык.

                              Так вот, при каждых операциях, определенная структура данных ложится в redis

                              А зачем тут redis? Данные просто попадают в базу и периодически синхронизируются в одно хранилище с помощью SSIS.

                              Почему разные БД и такой зоопарк? Так Москва не сразу строилась, сначала было одно, затем появилось другое/третье… Затем все объединилось.

                              Есть подтверждение? Или это фантазии?
                                0
                                Есть.
                                Близкий друг один из первых разработчиков wb с ~2008, сейчас работает там же.
                              0
                              Вы упомянули штат разработчиков SQL Server.
                              У каждого свои запросы.
                              Есть магазин butik.ru — там работает на данный момент 2 программиста и все.
                              Нет штата разработчиков SQL Server, нет около 50 разработчиков front/back — end.
                              Просто 2 разработчика и управляющий проектом.
                              Зато работает так же быстро и хорошо как wb, просто не захотели становится акционерным.
                                0
                                Может нагрузка совершенно разная.
                                  0
                                  Почти что одинаковая. Процентов на 10% меньше.
                  0
                  А для чего группировать записи в первых двух подходах?
                    0
                    Группировать по времени будет удобно, если ваш тайм-лайн как-то сильно завязан на временные интервалы (например, прдеставлен в виде календаря). Второй вариант сгодится для стандартной ситуации, если размер стораджа для вас не критичен.
                      0
                      Нет, вопрос был немного в другом.
                      Почему не использовать 1 запись = 1 документ?

                      Уточню:
                      1 запись в на стене пользователя = 1 запись в коллекции монго
                      Т.е. полностью без группировок.
                        0
                        Такой вариант вполне приемлемый. Скажу более, я именно такой вариант использовал, пока не узнал о новых подходах на MongoDB World. Первые два подхода на практике не использовал, но может кому-то понадобятся, поэтому я о них упомянул. А вот третий подход, с кэшированием, считаю мега крутым.
                          0
                          Да, дело в том, что когда мы делали ленту, мы тоже генерировали в монге ленту под каждого пользователя и хранили в виде 1 запись в ленте = 1 запись в колекции.
                          Вариант с кешированием — возможно да, крутой. С другой стороны, для кеша тогда не обязательно использовать монгу )
                            0
                            Конечно необязательно. Я вот даже примеры монговские в спойлеры попрятал. Но тем не менее, монга очень хорошо подходит и для варианта с кэшем с её capped-массивами и шардированием.
                    0
                    В монге collection-level lock на запись. То есть любая запись в агрегированные ленты лочит всю коллекцию. Учитывая, что писать надо в ленты всех друзей, то это приведет к тому, что большая часть лент будет залочены большую часть времени под нагрузкой.

                    Тут сразу возникает вторая проблема — не атомарность записи. Если по какой-то причине запись прервется, то ленты окажутся не консистентными. Вообще сложно будет добиться консистентной в такой системе.

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

                    В итоге такое решение будет работать при малом объеме связей и постов.

                    Вот тут описана суть проблем — habrahabr.ru/post/231213/ и решение, к которому пришли те, кто это делал.
                      0
                      Даже с локом на коллекцию, система без проблема держала нагрузку до полмиллиона постов в сутки. Это конечно близко не стоит с Diaspora и Facebook, но и вовсе не мало.

                      А в новом релизе уже реализован document-level lock. Вот так сразу снимаются все проблемы.
                        +1
                        Полмиллиона постов или полмиллиона записей? У вас же количество записей будет зависеть от количества связей.
                        Предположим в сети 5000 человек, у каждого по 150 друзей и все написали по посту. У вас в базу улетело 750,000 записей. Система ляжет.
                        Причем писать надо не только посты, но и все лайки\комменты. Поэтому вполне реальный сценарий.

                        Причем надо тестировать не только количество постов, но и отзывчивость системы в этот момент.

                        Можно разрулить через очередь, но может получиться лаг между постом и тем когда его увидели, в минуты или даже часы, что делает соцсеть бесполезной.
                          0
                          Записей в сервис ленты. Да, рулили именно через очереди, поэтому и с отзывчивостью было всё ок.
                            –1
                            А сколько было пользователей\связей? Это ключевой параметр, который причем квадратичный рост нагрузки дает.
                              0
                              Ключевой параметр я уже вам написал. Пользователей и связей может быть сколь угодно много, но все они будут неактивными, это не показатель. И про квадратичную зависимость улыбнуло. Это показывает, что вы далеки от темы и от математики.
                                –1
                                Нет, вы его пропустили. Пока неизвестно сколько у вас связей в системе количество постов ничего не значит. Если пользователь один и связей у него ноль, то максимальное количество постов в единицу времени будет одно, а если тысячи пользователей и сотни связей, то получится совсем другое число.

                                Вот я и спрашиваю: полмиллиона при каком количестве пользователей и связей было.

                                Про квадратичную зависимость не знаю что вас улыбнуло, но в системе с N пользователями у каждого может быть до N-1 связей. Это и получается O(N^2). У вас другие выкладки?
                                  +1
                                  Вы невнимательно читаете. Я написал про полмиллиона записей в сервис ленты, а не контента. Т.е. это записи в персональные ленты пользователей. Самая что ни на есть ключевая метрика.

                                  Вы это серьёзно, про N-1 связей у каждого пользователя? Скажите честно, вы разрабатывали хотя бы одну социальную сеть, живущую в продакшене? В реальности, средняя цифра связей у каждого пользователя — это практически константа, абсолютно не зависящая от общего количества пользователей.

                                    0
                                    А, понял. Запись в сервис ленты не означает, что пост появится у подписчиков. Тогда поставим вопрос по-другому.
                                    500,000 записей в сутки — примерно 6 записей в секунду. Так вот при 5 записях в секунду, при 5000 пользователей и 150 связях в среднем у каждого, а также при равномерном распределении записей по пользователям через сколько времени посты «друзей» появляются в ленте пользователей? Какая средняя длина очереди? Какое время обработки элемента в очереди?

                                    Я разрабатывал соцсеть еще в 2008 году, до кризиса. Тестировал на 2000 пользователей и 100 связей у каждого, сбор ленты прямо из базы с кешированием работал успешно, но нагрузку на запись не тестил, так как по сценариям предполагалось не более одного поста и 10 лайков в день от пользователя.

                                    По поводу связей у каждого пользователя — это очень интересная величина. В современных соцсетях пользователи отслеживают «акторов», каждый из которых может быть как пользователем, так и группой или прозвиольным объектом (open graph например). Так вот в корпоративных соцсетях есть тенденция подписки каждого пользователя на большое количество акторов, причем люди не сами подписываются, а подписка делается по бизнес-правилам. Поэтому при общем количестве акторов N и пользователей M, то количество связей растет как O(M*N). Хотя я лично ограничивал количество подписок на акторов до 500, больше пользователю не надо обычно, а планированию быстродествия очень помогает.
                                      0
                                      А, понял. Запись в сервис ленты не означает, что пост появится у подписчиков.

                                      Не верно. Как раз таки если событи уже попало в сервис ленты, то оно обязательно отобразится у пользователя в его персональной ленте.
                                        0
                                        У какого пользователя? Который добавил или который подписан на того, кто добавил? То есть добавление и репликация происходит синхронно? Если да, то сколько связей между пользователями? Какое распределение записей по пользователям? При тестировании запросы на запись выполнялись параллельно или последовательно?
                      +3
                      Вообще единственное живое решение для 10,000+ активных пользователей — как раз построение ленты при чтении+кеширование.
                      По сути ленты с последними сообщениями всех пользователей\групп лежат в кеше. При запросе ленты из кеша достаются ленты всех друзей и по ним строится агрегированная лента. При записи пост пишется просто в ленту (список постов) в кеша.

                      Если надо показывать ленту со старыми сообщениями, то делается просто запрос к СУБД с целым одним джоином.

                      В качестве стореджа можно использовать любую РСУБД, так как подавляющее большинство запросов не будет долетать до СУБД. СУБД можно будет шардить по пользователям совершенно без проблем.

                      С точки зрения архитектуры получится примерно как монга, но более гибко. В монге кеш получатся прибит к стореджу, а сторедж мягко говоря слабоват. В случае разделенных кеша и базы их можно масштабировать отдельно, база умеет достаточно хорошо делать джоины, а кеш, управляемый приложением, повышает эффективность использования памяти.
                        –1
                        Проблема в том, что в новостной ленте часто показывается много больше активности пользователей, чем отображается на стене этих пользователей. Т.е. помимо постов друзей, в ленту попадает что они лайкали, с кем подружились, во что сыграли, etc.
                          0
                          А в чем проблема? Не показывать часть событий на отдельных лентах? Это сложно?
                            –1
                            Это не сложно, но что это даст? Ведь у каждого фолловера свои персональные настройки того, что он читает. Представьте, что вам надо взять все записи всех ваших друзей, отсортировать их по времени, а потом отфильтровать кастомными фильтрами.
                              –1
                              Если материализовывать ленту ситуация будет еще хуже. Любая смена фильтра — пересборка всей ленты. Если вы умеете пересобирать ленту за приемлемое время, то зачем её материализовывать?
                                0
                                Я ж целую статью написал о том, когда какой подход лучше. А вы двумся строчками комментария авторитетно заявляете, что это не так.
                                  0
                                  ОК, пойдем сначала.
                                  В своей статье вы упустили два критичных момента:
                                  1) Изменение состава «друзей» потребует пересборки ленты, причем быстро. А если есть еще фильтры для ленты, то изменение фильтров также потребует пересборки.
                                  2) Не атомарность процесса сборки ленты приводит к проблемам. Репликация постов может остановиться по куче причин и оставить систему в не консистентном состоянии (особенно если оно рабтает на монге).

                                  Особенно интересно как вы решаете первую проблему. Говорить что это не проблема — не катит. Все соцсети сразу перестают показывать посты тех, от кого вы отписываетесь.
                                    +1
                                    1. В своей статье я сознательно опустил огромную кучу нюансов, с которыми сталкивался лично и описал магистральные идеи. Иначе пришлось бы раздувать статью до неприличных размеров. Но от ответа уходить не стану. Проблема решается довольно просто путём добавления ID автора к ссылке на событие (пост/лайк/etc). Т.е. мы храним не только ID оригинального события, но и юзера, который это событие породил. Таким образом очень легко и быстро можно «отписывать» от пользователей.
                                    2.
                                    особенно если оно рабтает на монге
                                    Огорчает ваше предвязтое отновшение к Монге, в таком ключе тяжело вести конструктивный диалог. Я вот даже отадлённо не представляю, как в более-менее большой сети этот процесс можно реализовать атомарно. Вот честно.
                                      –1
                                      Вы «выплеснули с водой ребенка», потому что опустили самые важные аспекты соцсети, такие как UX и privacy.
                                      1) Предположим вы научилсь быстро удалять пост из ленты при отписке. Но тут снова возникает две проблемы:
                                      а) Как обрабатывается подписка на другого пользователя? Обычно подписавшись человек ожидает все посты\действия пользователей, вы же предлагаете делать это в фоне, что сильно ухудшает UX.
                                      б) Если у вас в ленте есть спамер который запостил 100500 сообщений, вытеснив все остальные (у вас же есть ограничение на размер материализованной ленты). Вы его удаляете и у вас девственно чистая лента.
                                      Вообще проблема спамеров очень серьезно стоит при материализованной ленте.

                                      2) Мое отношение к монге основано на практике использования, когда после пары перезагрузок потерялось несколько записей «очереди» и возникли проблемы. А если в монге накрутить гарантии и write concern, то начинает тормозить, что работать невозможно.

                                      3) Рассказываю тайну: есть NoSQL базы, которые поддерживают multi-document transactions, в том числе в распределенной среде, но монга так не умеет и пока не двигается в этом направлении. Но самое главное что честная атомарность такого процесса будет очень медленной, что сделает фактически бессмысленным материализацию лент.

                                      4) С учетом факторов выше и требований privacy (если я удалил пост — он должен везде исчезнуть) заниматься репликацией ленты не стоит в большинстве случаев, только при очень слабых требованиях consistency\privacy\времени_обновления. Настолько слабые требования мне, например, не встречались.
                                        +1
                                        Из всех веток наших дискуссий я понял, что помимо Монги у вас был неудачный опыт с формированием ленты на запись. Расскажу одну историю. Пару недель назад заводил профиль в Facebook своей бабушке. Добавил ей пару человек из мемьи в друзья. Представьте себе моё удивление, когда после добавления друзей я увидел у неё `девственно чистую ленту` (вы не против заимствования термина). Лента заполнилась, если я не ошибаюсь, на следующий день. Думаю вывод из этого вы можете сделать сами. Хотя я сам не считаю такою ситуацию нормальной, думаю это какая-то перемудрённая система приоритетов в их очередях. Но факт остаётся фактом.

                                        И на счёт столь важной для вас темы приватности и удаления. На самом деле, если после удаления/скрытия поста/фото/etc что-то пойдёт не так, и процесс удаления ссылок на запись в лентах подписчиков оборвётся, то ничего страшного не произойдёт. Объясню почему. В летах подписчиков останется ссылка на запись, но оригинал записи уже будет помечена как удалённая/приватная. Поэтому подписчки её не увидят. А возникшую ситуацию можно использовать с пользой как триггер для перезапуск операции удаления ссылок.
                                          –1
                                          А меня как раз удачный опыт, ибо я делаю примерно тоже самое, что делает монго. Только у меня кешем управляет приложение. Это дает гораздо более эффективное использование памяти и надежное хранение в РСУБД. А ткже автоматически дает возможность получить ленту за любой диапазон времени (возможно небыстро, но без больших усилий). При этом нигода не испытывал тех проблем, на которые можно нарваться с хранением материализованной ленты в монге.

                                          Ваш пример с FB не доказывает правильность вашего подхода ;)
                          +1
                          Представьте, что пользователь может добавлять некоторые посты из своей ленты в черный список, скрывать их, добавлять сложные фильтры для своей ленты. Как вы тогда будете формировать запрос к СУБД? Я сталкивался с этой проблемой и приходилось отказываться от обычных запросов к СУБД, приходилось фильтровать в момент создания поста (в момент формирования индивидуальной ленты подписчика).

                          Вот еще пример фильтра: скрывать из ленты все лайки, скрывать все лайки только от родственников и т.д.
                            0
                            Скрыть некоторые посты вообще не проблема. В кеше лежат например 150 постов со всеми лайками и комментами для каждого пользователя. Для построения агрегированной ленты надо взять из кеша ленты всех друзей, сделать merge по дате поста, выкинуть скрытые и отдать на клиент.

                            Про фильтры не очень понятно. Что надо скрывать, посты или лайки? Лайки можно поправить при агрегации, с постами — зависит от предиката. В чем проблема сделать нужный запрос в СУБД?

                            Почему бы просто не прикрутить к фильтрованным лентам кеш? они же меняться будут реже гораздо и их тупо меньше.
                              +1
                              Представьте ленту которая состоит из различного рода контента — «фото», «текст», «ссылка», «репост». Заказчиком поставлена задача, чтобы пользователь мог добавлять в игнор например обновления типа «фото» от пользователя «Вася пупкин». Или сделать так, чтобы в его ленте появлялись только «фото» и «ссылки» от пользователей находящихся с меткой «родственники». Кеширование не спасает, т.к. это часто обновляемая лента и главная для пользователя. Сделать это через JOINы будет все сложнее и сложнее, т.к. в моей практике заказчик хотел все более сложные фильтры для лент, чтобы у пользователей могло быть несколько тематических лент. Сплошная головная боль.

                              Вариант — на лету формировать ленту в данном случае самый подходящий. Но сложную фильтрацию в данном случае я уже делал не на стороне СУБД.
                                0
                                То есть проблема только в том, что вы не смогли написать запрос к субд или в том, что не смогли прикрутить кеш к этому запросу? Или в чем-то еще?

                                В случае сложных предикатов сформировать ленту при записи все равно недостаточно, ибо предикат поменяется и надо будет ленту пересобрать, причем быстро. А имея быстрый алгоритм сбора ленты достаточно прикрутить простое кеширование и не надо думать о консистентности.
                                  0
                                  Сложности в формировании запроса. Было поставлено условие, что новые фильтры не влияют на ранее добавленные в ленту элементы, поэтому пересобирать ленту не нужно, либо в отложенном режиме.
                                    –1
                                    При таком условии кеширование прикрутить элементарно. В памяти лежит список постов по ИД ленты и набор фильтров. Каждый новый пост проверяется по фильтрам и пишется в список если соответствует. Старые можно со временем отсекать, чтобы объем данных в памяти не пух.

                                    А чем запросы то генерили? Я вот на C# программирую, с появлением Linq вообще отпала проблема создания сложных запросов. Для других языков тоже есть генераторы, хоть и послабее.
                          +1
                          самый большой недостаток системы — неудобная работа с удалением как записей, так и отписки от чтения новостей определенного пользователя, особенно при большом обьеме подписчиков у людей. как вы боретесь с этими проблемами? когда мне надо было писать ленту новостей этот подход я рассматривал одним из самых первых, но осознав описанные выше проблемы решил от него отказаться.
                            –1
                            Решается довольно просто. Записи в ленте помимо ID оригинального события (поста/лайка/etc) должны содержать ID автора этого ивента. Добавляем индекс по ID автора и процессим удаление/отписку в бэкграунде. Запрос конечно получается ощутимо тяжелее чтения, но во-первых такого рода запросы случаются несравнимо реже запросов на чтение. Ну и во-вторых, скорость таких запросов некритична.
                              +1
                              с удалением именно записей — критично, если речь идет о серьезном проекте. взять фб или вк — там все происходит моментально, при этом не совсем уверен на счет фб, но в вк в добавок к моментальному удалению записей на сервере, есть еще и моментальное удаление этих записей из ленте на клиенте с помощью пушей.
                              например я добавил фото, а оказалось что это не то фото, и я его сразу удаляю. а у вас оно будет висеть в ленте пока не сработает скрипт в фоне.
                                –1
                                Охохо, знали бы вы, сколько там всякой всячины с удалением фото. И посты в ленте, которые удалили или сделали приватными, не такая уж и редкость (когда переходишь по ним, попадаешь на страницу с ошибкой). Более того, там и новый посты не моментально появляются. Часто видишь пост «just now», у которого уже несколько десятков лайков.

                                А самое главное, в бизнес требованиях к нашей системе необходимости «моментального» удаления небыло. Так что 10-20-30 секунд это абсолютно ок.
                                  0
                                  Just now имеет фиксированный промежуток времени. Минуту примерно или 30 секунд (не помню точно). 15 лайков собрать за это время легко.
                                    –1
                                    Такая отмазка не катит. Удаление подписки, как и удаление постов (или смена приватности) должна обрабатываться сразу, а не фоновой задачей. Фоновая задача еще может отвалиться и оставить удаленный пост в ленте пользователя, что совсем нехорошо.
                                      0
                                      Стас, это не «отмазка», а пример из рабочих проектов. При чём не только из тех проектов, в которых я участвовал. Поэтому мне совершенно не понятно ваше хейтерство.
                                        –1
                                        У вас спрашивают как вы решаете проблемы. Вы начинаете отвечать что у других тоже есть проблемы, а у вас это вообще не проблема.

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

                                        А теперь перейдем к конкретным вопросам:
                                        Фоновая задача может поломаться удалив часть постов из лент, а другие оставив. Каким образом вы делаете так, чтобы все посты гарантированно удалились?
                                          0
                                          Вы немного перепутали. Я не школьник на экзамене.
                                            –1
                                            То есть ответа на вопрос у вас нет?
                                              –1
                                              Это как выйти на конференции с докладом, а на вопросы по докладу сказать, что вы не на экзамене.
                                0
                                я правильно понял что при последнем подходе мы наполняем кэш опрашивая читаемых пользователей (формируем ленту при чтении), а затем обновляем созданный кэш по модели материализованной ленты, добавляя в него новые записи и удаляя старые?

                                Only users with full accounts can post comments. Log in, please.