Привет! Эта статья - текстовая версия моего стрима с разбором задачи на бесконечную ленту по System Design из https://t.me/siliconchannel/141 этого поста.

Рассмотрим классическую задачу из System Design интервью - персональная лента подписок. По сути, мы проектируем упрощённый клон Instagram. Сама задача звучит следующим образом:

Делаем сервис: подписки на авторов, публикации постов, выдача персональной ленты с пагинацией. Нагрузка: чтение доминирует - 30 тыс. RPS; запись постов 1000 RPS; есть “мегапопулярные” авторы.

Этапы

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

1. Сбор требований.
   Здесь мы собираем все вводные данные для нашей системы.

   1. Описание сущностей: Просто конкретно обговариваем, что такое лента, что такое пост, что такое подписка.

   2. Функциональные требования: Те функции, которые требуются от системы.

   3. Нефункциональные требования: Тайминги и нагрузки, которые должна выдерживать система.

2. Расчеты.
   Тут мы рассчитываем трафик и объёмы данных: сколько нам нужно объема в S3 для картинок постов, сколько БД, чтобы хранить сами посты.

3. Проектируем API нашего сервиса.
   Это банальные ручки в псевдокоде, которые нам понадобятся, чтобы понимать возможные краевые случаи.

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

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

Сбор требований.

Сущности

Лента пользователя:

• непрерывная последовательность постов,

• только от авторов, на которых пользователь подписан,

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

• В среднем: не больше ~15 постов смотрит пользователь за раз.

Подписка

• Один пользователь подписывается на другого.

• В среднем: ~150 подписок на пользователя.

• Есть “тяжёлые” пользователи (инфлюенсеры с сотнями тысяч подписчиков).

Пост

• Текст до 500 символов.

• До 3 изображений.

• Время публикации критично для сортировки.

Функциональные требования

• Создание поста

• Получение ленты с пагинацией

• Подписка / отписка

Нефункциональные тр��бования

• 30 млн DAU

• Пользователи по всему миру

• Чтение: до 30 000 RPS

• Запись: до 1 000 RPS

• SLA: не более 2-3 секунд на загрузку ленты

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

Расчеты

Для начала посчитаем, сколько в среднем занимает пост в памяти:

• Текст: 500 символов × 2 байта (в среднем в UTF-8) ≈ 1 КБ.

• Картинки: 1.5 изображения в среднем × 500 КБ ≈ 750 КБ.

• Ссылка на картинку: ≈ 120 байт (0.12 КБ) на ссылку.

Итого один пост: ≈ 751 КБ.

Write Traffic (на запись):

• 1000 RPS × 751 КБ ≈ 751 МБ/с исходящего трафика (в систему хранения медиа).

Read Traffic (на чтение):

• 30 000 RPS × 751 КБ ≈ 22.5 ГБ/с входящего трафика.

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

Давайте прикинем примерные порядки объёмов данных, которые нам придётся хранить на протяжении, например, двух лет:

• Хранение картинок:
  750 КБ × 1000 RPS × 86400 (секунд в дне) × 365 (дней) × 2 (года) ≈ 47 203 200 000 000 КБ ≈ 43 ПБ.

• Хранение метаданных постов (текст и ссылки):
  (1 КБ + 0.12 КБ × 1.5) × 1000 RPS × 86400 × 365 × 2 ≈ 73 745 280 000 КБ ≈ 69 ТБ.

Эти данные помогут нам в будущем определиться с технологиями для хранения каждого типа данных.

Проектируем API нашего сервиса

Наши основные endpoint'ы:

• POST /v1/post – создание поста.

• GET /v1/feed?cursor=&limit=15 – получение ленты.

• POST /v1/image/upload - Загрузка картинки

• GET /v1/image/{url} - Получение картинки

• POST /v1/subscribe/{author_id} – подписка.

• DELETE /v1/subscribe/{author_id} – отписка.

Почему курсорная пагинация, а не offset?

• Offset (LIMIT 10 OFFSET 10000) заставляет базу данных пересчитать все 10010 строк, чтобы отбросить первые 10000. Это "тяжёлая" операция при большом offset.

• Cursor (WHERE created_at < $cursor LIMIT 10) использует индекс по времени. Мы "запоминаем" отметку времени последнего полученного поста и запрашиваем следующие. Это идеально для бесконечной ленты, где пользователь движется последовательно. Быстро и стабильно.

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

Архитектура

Основная дилемма при проектировании ленты упирается в выбор стратегии распространения постов (fan-out). Мы уже выяснили, что чтение доминирует, поэтому наша главная цель - сделать получение ленты максимально быстрым.

Fan-out-on-read (Pull-модель): При открытии ленты система собирает ID подписок пользователя, запрашивает последние посты у каждого автора, агрегирует и сортирует их. Запись поста дешёвая (O(1)), но чтение очень дорогое (O(количества подписок)). При 150 подписках и 30k RPS система рухнет под нагрузкой запросов к БД.

Fan-out-on-write (Push-модель): При публикации поста он немедленно рассылается (push) в персональные ленты всех подписчиков. Чтение становится тривиальным (O(1) - просто достать готовый список), но запись поста популярного автора превращается в кошмар (O(количества подписчиков)). Пост инфлюенсера с 10M подписчиков заблокирует систему, так как придется пересчитывать ленты для 10М пользователей, что не круто.

Гибридная модель: Лучшее из двух миров

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

Спроектируем необходимые сервисы

После того как мы определились с гибридной парадигмой fan-out, можно спроектировать сервисы, которые будут выполнять всю работу.

1. Image Service

Задача: надежно хранить и отдавать изображения в масштабе десятков петабайт.

Выбор хранилища: AWS S3
Глядя на прогнозируемые 47 ПБ данных, выбор очевиден - объектное хранилище типа Amazon S3. Оно идеально подходит для статичных бинарных данных, отказоустойчиво, бесконечно масштабируется и, что критично, избавляет нас от необходимости самим решать сложные проблемы дистрибуции и надежности хранения больших объемов, Безос уже обо всём подумал за нас.

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

Решение: Двухэтапная загрузка с временным буфером

Процесс выглядит так:

• Фаза 1: Предзагрузка (Pre-Upload)

  • Клиентское приложение запрашивает у Image Service временные одноразовые ссылки для загрузки.

  • Image Service генерирует уникальные ключи для файлов (например, temp/{user_id}/{uuid}.jpg) и возвращает клиенту подписанные URL для записи прямо во временный бакет S3.

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

• Фаза 2: Фиксация (Commit)

  • Когда пользователь окончательно отправляет форму создания поста, Post Service (о нём дальше) вызывает внутренний API Image Service, передавая временные ключи файлов и ID будущего поста.

  • Image Service выполняет атомарную операцию переноса файлов из временного бакета в постоянный, по пути формируя постоянные ключи.

  • После успешного копирования временные файлы удаляются.

  • Image Service возвращает Post Service итоговые, постоянные URL для доступа к изображениям.

Защита и оптимизация:

• TTL для временного бакета: Настраивается правило жизненного цикла в S3, которое автоматически удаляет файлы из временного бакета, скажем, через 24 часа.

• CDN (CloudFront / аналоги): Постоянный бакет должен раздаваться через CDN. Это критически важно для обработки пикового read-трафика в 22.5 ГБ/с и обеспечения низкой задержки для пользователей по всему миру. CDN кэширует картинки на своей сети доставки.

2. Post Service и Feed Service

Дальше подумаем, как мы будем работать с постами. По-хорошему нам разделить Read и Write нагрузку, так как они на порядок различаются и масштабировать их в будущем мы будем по-разному. Получается, нам нужно два сервиса:

Первый - Post Service, который будет хранить в какой-нибудь БД наши посты. Спроектируем модель поста:

type Post struct {
ID int64 json:"id" db:"id"
UserID int64 json:"user_id" db:"user_id"
Text string json:"text" db:"text"
ImageURLs []string json:"image_urls" db:"image_urls"
CreatedAt time.Time json:"created_at" db:"created_at"
UpdatedAt time.Time json:"updated_at" db:"updated_at"
}

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

Второй сервис, который нам понадобится для чтения, назовём Feed Service. Его задача - мгновенно отдавать пользователям их персональные ленты. Для этого мы будем хранить предподготовленные данные в формате, готовом к выдаче: user_id: [{description, url, url}, ...].

Такой формат идеально ложится на key-value хранилище. Поскольку скорость чтения здесь критична, логично выбрать in-memory базу данных, например Redis. Однако просто взять её "наугад" нельзя - нужно хотя бы примерно оценить объём данных.

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

• Средний пост: текст (~1000 байт) + ссылки на картинки (~1.5 * 100 байт) ≈ 1150 байт.

• Постов в ленте на пользователя: 20 (первые 20 записей, которые видны сразу).

• Количество DAU: 30 000 000.

Итого:
1150 байт × 20 постов × 30 000 000 пользователей ≈ 690 ГБ.

690 ГБ - это объём, который вполне укладывается в возможности современного in-memory хранилища. Кластер Redis с несколькими узлами легко справится с такой нагрузкой. Поэтому выбор Redis в качестве хранилища готовых лент выглядит оправданным.

Но у нас бывают пользователи, которым скучно, или которые давно не заходили - таким всё-таки придётся сходить в Post API и оттуда получить новые посты. Встаёт вопрос: надо ли подгружать эти посты в Redis? Я думаю, что не стоит, потому что если пользователи уже видели посты, то обычно дальше не листают. На этом и остановимся.

3. Relation Service

Для работы с подписками создадим отдельный сервис - Relation Service. Он будет отвечать за хранение информации о том, кто на кого подписан. Для начала подумаем, в каком формате хранить эти данные. Самый простой вариант - запись вроде:

user_id1: user_id2, user_id3, user_id4
user_id2: user_id1, user_id99

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

Событийная модель

Давайте подумаем над тем, что при подписке, отписке или новом посте нам нужно пересчитывать ленты затронутых пользователей. Можно было бы отправлять прямые запросы из сервиса подписок или из сервиса постов в Feed Service с требованием немедленно обновить ленту. Однако такой подход создаёт жёсткие циклические зависимости между сервисами: Relation Service → Feed Service, Post Service → Feed Service, а в будущем, возможно, и обратные вызовы. Такие циклы сложно разрывать, поддерживать и масштабировать.

Чтобы избежать этой проблемы и сделать систему отвязанной и устойчивой, возьмём надёжный брокер сообщений, который легко масштабируется в будущем, - например, Kafka. Создадим в ней два основных топика: Posts (для событий о новых постах) и Subs (для событий о подписках и отписках). Теперь сервисы будут просто публиковать события в эти топики, а Feed Service (или отдельный Fan-out Worker) будет асинхронно обрабатывать их и пересчитывать ленты. Так мы разорвём прямые зависимости и получим масштабируемую, отказоустойчивую архитектуру на основе событий.

Краевой случай: Пост от инфлюенсера

Давайте вспомним краевой случай из задания - инфлюенсеры. При посте от автора с миллионами подписчиков, если мы будем пытаться по классическому сценарию fanout-on-write, это просто положит наш сервис.

Поэтому мы не стали выбирать чистый fanout-on-write, а пошли на гибрид. Вот как мы это сделали:

Мы ввели понятие порога, скажем, 100 тысяч подписчиков. Авторы, у которых подписчиков больше этого порога, считаются инфлюенсерами. Для них мы меняем логику фан-аута:

• Не закидываем пост в ленту каждого подписчика
  Вместо этого сохраняем пост в отдельный кэш постов инфлюенсеров (просто ещё один Redis, где ключ - influencer_posts:{author_id}, а значение - список последних постов).

• В ленте подписчика храним не пост, а указатель
  Когда фан-аут воркер видит, что автор - инфлюенсер, он кладёт в ленту подписчика не post_id, а специальную метку, например influencer:{author_id}.

• Мёржим при чтении
  Когда Feed Service формирует ленту для пользователя, он:

  • Достаёт обычные посты из своего Sorted Set

  • Ищет такие метки инфлюенсеров

  • Для каждой метки дёргает последние посты из кэша инфлюенсеров

  • Всё это мержит в один отсортированный список и отдаёт

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

По сути, для обычных авторов мы используем fanout-on-write, а для инфлюенсеров - fanout-on-read, только читаем не из PostgreSQL, а из горячего кэша.

Масштабирование и отказоустойчивость

В целом рабочая модель нашего бэкенда уже готова. Давайте накинем Load Balancer перед клиентом, чтобы он правильно проксировал запросы и распределял нагрузку между шардами наших API.

Интересно обговорить один момент: мы добавили условие, что пользователи со всего мира, и мы не привязываем��я к региону. Без дополнительных мер мы можем не уложиться в требуемые 2 секунды ответа. Разумеется, мы разместим наши инстансы в дата-центрах по всему миру, но этого недостаточно - нужно ещё настроить DNS-балансировку, чтобы пользователя автоматически направляло на ближайший к нему сервер.

В целом тут всё прозрачно: добавим шарды, настроим асинхронные репликации (поскольку у нас нет критичных требований к синхронности). Единственный нюанс: в Redis мы можем столкнуться со "скачками" в ленте, когда данные обновились на мастере, но ещё не успели попасть на слейв, и пользователь будет получать то новые, то старые данные. Эту проблему можно решить, закрепляя пользователя за определённым шардом, - тогда она в целом уйдёт.

Есть ещё проблема с масштабированием графовой БД. Графы в целом плохо масштабируются горизонтально: может оказаться, что одна вершина графа лежит в одном шарде, а другая - в другой, и связь между ними окажется разорванной. Можно отказаться от графового подхода и рассмотреть, например, запись в формате user_id: user_id, user_id, но использовать для этого что-то вроде ScyllaDB, где горизонтальное масштабирование реализовано изначально и работает надёжнее.

Если хотите попасть на следующий стрим по System Design, разбору алгоритмов или просто задать вопросы - подписывайтесь на канал: https://t.me/siliconchannel и на канал c анонсами: https://t.me/silliconanouncment