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

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

Принципиально можно выделить две схемы формирования ленты:

  1. Push on change.

  2. Pull on demand.

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

1. Push on change. Для каждого пользователя создаем отдельный денормализованный фид. При добавлении мема вставляем его для пользователей, подписанных на автора.

Плюсы:

  • очень быстро читать из базы.

Минусы:

  • долгое добавление и удаление: время линейно зависит от количества подписок на автора.

Формирование фида по схеме push on change
Формирование фида по схеме push on change

2. Pull on demand. Формируем на лету: отправляем по запросу на каждого пользователя, на которого подписаны.

Плюсы:

  • нет нужды актуализировать денормализованные представления: константное по времени добавление и удаление.

Минусы:

  • формирование ленты занимает линейно зависимое от количества подписок время;

  • при формировании необходимо обрабатывать избыточное количество данных: чтобы отдать фид из 20 элементов, для каждой подписки приходится выбирать по 20, сортировать и склеивать, а остальное просто выкидывать.

Формирование фида по схеме pull on demand
Формирование фида по схеме pull on demand

Первая итерация: push on change на Cassandra

Мы выбрали механизм push on change, а в качестве БД для хранения денормализованных представлений использовали Cassandra. Она использует подход LSM, что позволяет писать с достаточно внушительной скоростью за счет того, что данные просто последовательно пишутся в память (MemTable), а затем сохраняются на диск и сливаются в многоуровневые отсортированные файлы (SSTables).

Была реализована инфраструктура для обработки асинхронных задач наполнения фидов. Суть этих задач сводится к получению подписчиков автора контента и добавления большими пачками нового мема к каждому из них. Тут все логично и хорошо: кластер Cassandra отлично переваривал здоровенные батчи, и по началу проблем с получением тоже не было.

Но спустя время появились проблемы с доступом к данным. Причин несколько:

  1. Требования сторов удалить определённый контент. Например, нарушение копирайта, 18+ или иногда просто лягушонок Пепе.

  2. Удаление самими пользователями.

  3. Отписка пользователей друг от друга. Иногда они отписывались сразу от всех.

  4. Трим старых данных. Нужно было чистить ооочень длинные фиды, потому что пользователи никогда не прочитают до конца.

Всё это создавало в датасете дырки разного размера, которые вынуждали БД в фоне совершать гигантскую работу. Со временем всё становилось только хуже. Cassandra хранит данные в нескольких слоях, каждый из которых больше предыдущего.

Распределение данных по уровням в Cassandra
Распределение данных по уровням в Cassandra

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

Cassandra написана на Java, поэтому она могла непредсказуемо и надолго уходить в сбор мусора, особенно когда начинала мержить глубокоуровневые SSTable’ы. К тому времени в кластере было уже порядка 25 нод, а суммарное количество данных с учетом репликации перевалило за 20 ТБ. Это послужило сигналом к началу второй итерации.

Вторая итерация: pull on demand на Redis с формированием фида на стороне приложения

Провели большое количество экспериментов для улучшения ситуации, например:

  • Тюнинг GC Cassandra.

  • Другие стратегии Cassandra Compaction, рассматривали вариант написания своей стратегии.

  • Другие структуры хранения и БД (например, блобы в PostgreSQL).

Но ничего хорошего не вышло, и решили перейти к схеме pull on demand.

Поставили кластер из Redis, разложили данные в сортированные множества (sorted sets) и начали строить ленту прямо в момент запроса слиянием на стороне приложения в отдельном сервисе. Это значительно ускорило появление новых мемов: больше не надо итерировать по подпискам, вообще не нужны асинхронные задачи. 

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

Третья и текущая итерация: pull on demand на Redis с формированием на стороне базы

У предыдущего решения была пара недостатков:

  • Redis однопоточный, поэтому не было возможности распараллелить выполнение сотен запросов более чем на количество шардов в кластере;

  • нарушался принцип data locality: тратилось время на транспортировку данных от базы к приложению, бoльшая часть из которых была избыточной.

Redis 4 позволил писать свои модули. Мы решили, что это хороший способ оптимизировать работу фидов. Был написан модуль на C, который на стороне БД получал нужные данные, формировал из них результат, выполняя сортировку на структуре MaxHeap. Команду назвали ZREVMERGE: как понятно из названия, выполняет слияние нескольких сортированных множеств.

Формирование фида на основе модуля с ZREVMERGE
Формирование фида на основе модуля с ZREVMERGE

Появилась возможность распараллелить часть работы. ZREVMERGE добавляет задания в свой пул тредов. Доступ модуля к множествам по-прежнему осуществляется в однопоточном режиме из-за ограничений Redis, но сортировка и слияние не требует блокировки.

В итоге получилось более чем в два раза ускорить процесс: раньше медиана была около 20 мс, с переносом работы в модуль стала менее 10 мс. Получилось бы лучше, если бы не шардирование данных в кластере: приходится всё же отправлять несколько запросов, по одному на каждый шард и доделывать часть работы в приложении. Получилось увеличить лимит на подписки пользователям с 400 до 5000.

Но были и сложности. Так как модули пишутся на C, а я последний раз писал на нем в университете, столкнулся с парой утечек памяти. Также был найден баг в работе Redis с модулями, но его быстро пофиксили после репорта.

Тем не менее решение получилось достаточно стабильным: за полтора года в проде проблем не доставляло. Были нюансы с клиентом Redis на стороне приложения, но это другая история.

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

Вместо заключения

Конечно, пока не получилось решить все проблемы на 100%. Всегда есть возможности улучшить что-то, но из начальной точки проделан достаточно большой путь. Хоть писать на C в прод и было страшно, но свои результаты это принесло. Буду рад почитать, как ленты работают у вас. Удачного итерирования!