Системный дизайн ленты новостей: fan-out, знаменитости и пагинация курсором

Коротко

Лента новостей — классика system design интервью, потому что в ней нет одного правильного ответа. Есть два очевидных подхода, оба ломаются на крайних случаях, и интервьюер ждёт, что вы сами найдёте, где именно.

Общий порядок секции описан в статье про подходы к проектированию систем. Здесь он применён к ленте целиком.

Шаг 1. Требования

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

• Открытие ленты быстрое: p99 не больше 200 мс.
• Лента может отставать на несколько секунд. Строгая согласованность здесь не нужна, а доступность нужна.
• Опубликованный пост не теряется, даже если доставка по лентам задержалась.

Комментарии, лайки, рекламу и поиск обозначаем как «не делаем». Лайки вернутся только как сигнал для ранжирования.

Шаг 2. Оценка нагрузки

Допущения:

• 200 млн активных пользователей в день.
• Каждый открывает ленту 10 раз в день.
• 10% пользователей публикуют по одному посту в день.
• В среднем 200 подписчиков на автора.
• Пик в 3 раза выше среднего.

16 байт — это id поста и оценка в sorted set. Реальный расход памяти у Redis выше из-за служебных структур, поэтому закладываем запас.

Выводы:

1. Чтений в 100 раз больше, чем публикаций. Открытие ленты должно быть дешёвым.
2. Fan-out умножает запись в 200 раз. 230 публикаций превращаются в 46 тыс. записей в секунду. Это много, но для кластера Redis подъёмно.
3. Среднее врёт. 200 подписчиков в среднем, но у знаменитости их 50 млн. Об этом весь следующий раздел.

Шаг 3. Данные и API

CREATE TABLE posts (
  post_id    BIGINT PRIMARY KEY,   -- Snowflake: растёт вместе со временем
  author_id  BIGINT NOT NULL,
  body       TEXT,
  created_at TIMESTAMPTZ NOT NULL
);

CREATE TABLE follows (
  follower_id BIGINT NOT NULL,
  followee_id BIGINT NOT NULL,
  created_at  TIMESTAMPTZ NOT NULL DEFAULT now(),
  PRIMARY KEY (follower_id, followee_id)
);

CREATE INDEX follows_followee_idx ON follows (followee_id, follower_id);

Индекс по followee_id нужен для fan-out: «кому разослать пост этого автора». Первичный ключ отвечает на обратный вопрос: «на кого подписан пользователь».

ID в стиле Snowflake удобен тем, что он сортируется по времени. Хронологическую ленту можно упорядочить прямо по post_id, не храня отдельно время.

API короткий:

POST /api/v1/posts
GET  /api/v1/feed?limit=20&cursor=<непрозрачная строка>

Шаг 4. Fan-out on write и fan-out on read

Fan-out on write (push)

При публикации пост кладётся в заранее собранную ленту каждого подписчика. Открытие ленты сводится к чтению одного списка из кэша.

• Плюс: чтение мгновенное, а чтений в 100 раз больше.
• Минус: публикация знаменитости с 50 млн подписчиков — это 50 млн записей. Даже при миллионе записей в секунду рассылка займёт почти минуту, и всё это время кластер занят одним постом.
• Минус: ленты строятся и для тех, кто не заходит месяцами.

Fan-out on read (pull)

Ничего заранее не собираем. При открытии ленты берём список подписок, достаём последние посты каждого автора и сливаем их.

• Плюс: публикация стоит одну запись, знаменитости никому не мешают.
• Минус: подписан на 500 авторов — 500 запросов на каждое открытие ленты. При 70 тыс. RPS это не работает.

Слияние нескольких отсортированных списков — та же задача, что слияние k отсортированных массивов через кучу: $O(n \log k)$ для $n$ постов из $k$ источников. Хорошая точка, чтобы показать, что вы видите алгоритм внутри архитектуры.

Гибрид

Почти все разборы сходятся на одном: обычным авторам — push, знаменитостям — pull. Порог задаётся числом подписчиков. Знаменитостей среди подписок у пользователя немного, поэтому при чтении подмешивается лишь пара десятков коротких списков.

import heapq
from collections import defaultdict
from itertools import count, islice

FEED_LIMIT = 500  # Сколько id держим в кэше ленты на пользователя
CELEBRITY = 10_000  # Порог подписчиков для «знаменитости»

followers = defaultdict(set)  # автор -> подписчики
following = defaultdict(set)  # пользователь -> на кого подписан
posts_by_author = defaultdict(list)  # автор -> [post_id] по возрастанию
feed_cache = defaultdict(list)  # пользователь -> [post_id] по возрастанию
post_ids = count(1)  # В проде Snowflake: id растут вместе со временем


def follow(user: int, author: int) -> None:
    followers[author].add(user)
    following[user].add(author)


def is_celebrity(author: int) -> bool:
    return len(followers[author]) >= CELEBRITY


def publish(author: int) -> int:
    post_id = next(post_ids)
    posts_by_author[author].append(post_id)
    if not is_celebrity(author):

    # Fan-out on write: кладём id в ленту каждого подписчика
    for user in followers[author]:
        feed = feed_cache[user]
        feed.append(post_id)
        if len(feed) > FEED_LIMIT:
            del feed[0]
return post_id

def get_feed(user: int, limit: int = 20) -> list: pushed = reversed(feed_cache[user]) # Fan-out on read: посты знаменитостей подмешиваем при чтении pulled = [ reversed(posts_by_author[a][-limit:]) for a in following[user] if is_celebrity(a) ] merged = heapq.merge(pushed, *pulled, reverse=True) return list(islice(merged, limit))

follow(1, 100) # обычный автор follow(1, 200) # знаменитость for fan in range(2, CELEBRITY + 2): follow(fan, 200)

publish(100) # 1 publish(200) # 2, в кэш никому не попал publish(100) # 3 print(feed_cache[1]) # [1, 3] print(get_feed(1)) # [3, 2, 1] print(get_feed(5000)) # [2]

Ещё две оптимизации, которые стоит назвать:

- **Не рассылать неактивным.** Если пользователь не заходил 30 дней, его лента не обновляется. При входе она собирается заново через pull, один раз.
- **Асинхронность.** Сервис публикации пишет пост и ставит задачу в [очередь](/ru/blog/message-queues). Рассылкой занимаются воркеры, автору не нужно ждать, пока пост разойдётся по 200 лентам.

Порог «знаменитости» не обязательно жёсткий. Можно учитывать не только число подписчиков, но и долю активных среди них, и частоту публикаций.

## Шаг 5. Кэш ленты

Лента хранится как sorted set в Redis: элемент — id поста, оценка — время или рейтинг. Храним не всю историю, а последние 500 id: дальше почти никто не листает, а при необходимости догружаем через pull.

```text
ZADD feed:42 1700000100 5 1700000200 7 1700000300 9
ZREMRANGEBYRANK feed:42 0 -501
EXPIRE feed:42 1209600
ZREVRANGE feed:42 0 19 WITHSCORES

ZREMRANGEBYRANK ... 0 -501 оставляет 500 элементов с наибольшими оценками. EXPIRE на две недели освобождает память от лент тех, кто перестал заходить. По публичным докладам Twitter начала 2010-х, их домашние ленты так и жили в Redis, с ограничением в несколько сотен твитов на пользователя.

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

Путь чтения целиком:

клиент -> API ленты -> Redis feed:<user>        (id из push)
                    -> посты знаменитостей       (id из pull)
                    -> слияние, ранжирование
                    -> кэш постов по id          (hydration)
                    -> фильтр: удалено, скрыто, заблокировано

Кэш постов — классический горячий ключ: пост знаменитости одновременно читают миллионы. Помогает локальный кэш на серверах API на несколько секунд и реплики горячих ключей.

Шаг 6. Ранжирование

Хронология честная и простая, но когда подписок сотни, интересное тонет. Ранжированная лента устроена в несколько этапов:

1. Отбор кандидатов. Сотни свежих постов из push-ленты и pull-источников.
2. Оценка. Каждому кандидату модель ставит число: насколько вероятно, что человек провзаимодействует с постом.
3. Пересортировка. Правила поверх модели: не больше двух постов одного автора подряд, разнообразие форматов, уже показанное вниз.

На интервью модель не строят, достаточно простой формулы с понятными сигналами: близость к автору, вовлечённость, возраст поста. Старые ленты Facebook описывали как раз такой набор под названием EdgeRank.

import math


def score(age_hours: float, likes: int, comments: int, affinity: float) -> float:
    engagement = math.log1p(likes + 3 * comments)
    decay = (age_hours + 2) ** 1.5
    return affinity * (1 + engagement) / decay


# Свежий пост друга без реакций против вирусного поста малознакомого автора
print(round(score(1, 0, 0, affinity=0.9), 4))  # 0.1732
print(round(score(24, 5000, 300, affinity=0.3), 4))  # 0.0219
print(round(score(3, 5000, 300, affinity=0.3), 4))  # 0.2598

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

Где считать оценку? Сигналы вроде лайков меняются постоянно, поэтому в sorted set при fan-out кладут время, а финальный порядок считают при чтении для нескольких сотен кандидатов. Это десятки миллисекунд, укладываемся в бюджет.

Шаг 7. Пагинация курсором

OFFSET 20 LIMIT 20 в ленте ломается сразу. Пока человек читал первую страницу, сверху появилось три поста, вся лента сдвинулась, и на второй странице он увидит три уже прочитанных. Кроме того, большой OFFSET в базе означает прочитать и выбросить все предыдущие строки.

Курсор запоминает не номер страницы, а последний показанный элемент. Следующая страница — «всё, что строго ниже этого элемента». Пару (score, post_id) используют, потому что оценки могут совпадать, а post_id уникален и разрывает ничью.

import base64
import json


def encode_cursor(score: float, post_id: int) -> str:
    raw = json.dumps([score, post_id]).encode()
    return base64.urlsafe_b64encode(raw).decode().rstrip("=")


def decode_cursor(cursor: str) -> tuple:
    raw = base64.urlsafe_b64decode(cursor + "=" * (-len(cursor) % 4))
    score, post_id = json.loads(raw)
    return score, post_id


def page(feed: list, cursor: str | None, limit: int) -> tuple:
    # feed отсортирован по (score, post_id) по убыванию
    if cursor:
        last = decode_cursor(cursor)
        feed = [item for item in feed if item < last]
    items = feed[:limit]
    next_cursor = encode_cursor(*items[-1]) if len(items) == limit else None
    return items, next_cursor


feed = [(1700000300, 9), (1700000200, 8), (1700000200, 7), (1700000100, 5)]
items, cur = page(feed, None, 2)
print(items, cur)
# Пока читали первую страницу, сверху появился новый пост
feed.insert(0, (1700000400, 10))
items, cur = page(feed, cur, 2)
print(items, cur)  # [(1700000200, 7), (1700000100, 5)] без дублей и пропусков

Курсор для клиента непрозрачен: он не должен его разбирать, и вы можете менять формат. В проде строку ещё подписывают, чтобы курсор нельзя было подделать.

В Redis то же самое делает ZREVRANGEBYSCORE feed:42 (1700000300 -inf LIMIT 0 20, где скобка означает «строго меньше». В SQL — условие WHERE (score, post_id) < (:score, :post_id) ORDER BY score DESC, post_id DESC, которое работает по индексу на эту пару. Про такие индексы есть статья про индексы в базах данных.

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

Узкие места и вопросы вглубь

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

Подписка и отписка. После подписки старые посты автора в ленте не появятся сами: fan-out был до подписки. Можно догрузить несколько последних постов автора в ленту сразу. После отписки посты чистятся на этапе подтягивания по актуальному списку подписок.

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

Шардирование. Ленты шардируются по user_id, посты по post_id. Fan-out одного поста пишет во множество шардов, поэтому он и асинхронный. Про выбор ключей — в статье про шардирование и репликацию.

Отказ кэша. Если шард Redis потерян, ленты его пользователей восстанавливаются через pull. Это медленнее, но лента не пропадает, поэтому кэш здесь ускоритель, а не источник истины.

Типичные ошибки

• Выбрать только push или только pull и не заметить знаменитостей.
• Хранить в ленте полные копии постов вместо id.
• Строить ленты для пользователей, которые давно не заходят.
• Пагинировать через OFFSET и получать дубли при прокрутке.
• Пересчитывать ранжирование всей ленты при каждом лайке.
• Не сказать, что лента может отставать на секунды: именно это и позволяет сделать fan-out асинхронным.

Если вы объяснили, почему гибрид, где лежат id и где тексты, как устроен курсор и что ломается у знаменитостей, — это сильный ответ. Ранжирование на этом уровне достаточно назвать этапами и показать одну понятную формулу.