Спроектируй ленту новостей
Спроектируй ленту: fan-out-on-write vs fan-out-on-read, проблема знаменитости и гибрид, что её чинит, ранжирование, feed cache, курсорная пагинация и как реально хранятся таймлайны — каноническая read-heavy соцсистема.
Соцприложение запустило feed-on-write: каждый пост жадно копировался в списки лент всех подписчиков автора, так что чтение ленты было одним быстрым лукапом. Работало прекрасно — пока знаменитость с 30 миллионами подписчиков не запостила. Эта одна запись превратилась в 30 миллионов вставок в ленты, сервис write fan-out отстал на часы, и какое-то время половина постов знаменитостей платформы просто не появлялась ни в чьей ленте. Инстинкт инженеров был «ускорить fan-out». Реальный ответ был в том, что ни одна стратегия fan-out не работает и для пользователя с 200 подписчиками, и для пользователя с 30 миллионами — и починка была не в скорости, а в гибриде, использующем одну стратегию для обычных пользователей и противоположную для знаменитостей. Этот урок — про это решение и про хранилище, ранжирование и кеширование вокруг него.
Требования
Когда фиксируешь требования, ты по сути отвечаешь на один вопрос: где живёт дорогая работа — на пути записи или на пути чтения? Всё остальное вытекает из этого ответа.
Функциональные: пользователь постит контент; его подписчики видят это в ленте. Пользователь открывает ленту и получает ранжированный, постраничный список недавних постов от аккаунтов, на которые подписан. Поддержать бесконечную прокрутку. Посты можно лайкать/комментировать (что возвращается в ранжирование). Граф подписок асимметричен (ты подписан на аккаунты, которые могут быть не подписаны на тебя).
Нефункциональные: система массово read-heavy — чтения ленты на порядки превосходят посты, так что дизайн оптимизирует путь чтения превыше всего. Загрузка ленты должна ощущаться мгновенной (десятки миллисекунд на первую страницу). Новые посты должны появляться «вскоре» (секунды-минута норм — eventual consistency тут приемлема; ничей банковский баланс не неверен, если пост всплыл на 20 секунд позже). Она должна тянуть степенное распределение подписчиков: у большинства аккаунтов мало подписчиков, у крошечного числа — десятки миллионов, и этот длинный хвост — вся проблема дизайна.
Определяющее напряжение: делать дорогую работу, когда пост пишется (и сделать чтения дешёвыми), или когда лента читается (и сделать записи дешёвыми)? Этот единственный выбор — сердце дизайна ленты.
Оценка
300M активных в день, каждый открывает ленту ~10 раз/день, даёт 3×10^9 чтений ленты/день, около 35 000 чтений ленты/секунду в среднем, с пиком в несколько раз выше. Посты куда реже — скажем, каждый постит ~дважды/день, то есть ~7 000 постов/секунду. Отношение чтение:запись примерно 100:1, и это единственное самое важное число: оно оправдывает предвычисление лент (сделать работу раз на записи, отдавать дёшево на 100 чтениях).
Теперь стоимость fan-out. Среднее число подписчиков, может, несколько сотен, так что средний пост разворачивается в несколько сотен записей в ленты — норм. Но пост знаменитости с 30M подписчиков под чистым fan-out-on-write — это 30M записей на один пост. Если хотя бы горстка знаменитостей постит в одну минуту, это сотни миллионов записей, молотящих хранилище лент — сбой из hook. Салфетка говорит: fan-out-on-write дёшев в среднем и катастрофичен на хвосте, так что хвост нуждается в другой обработке.
Высокоуровневый дизайн
Две стратегии — зеркала; продакшен запускает обе.
- Fan-out-on-write (push): при создании поста сразу вставить его id в предвычисленную ленту каждого подписчика. Чтения тогда — тривиальный лукап кеша. Цена: усиление записи пропорционально числу подписчиков.
- Fan-out-on-read (pull): хранить посты лишь раз (по автору); когда пользователь читает ленту, запросить недавние посты всех, на кого подписан, и слить. Записи тривиальны. Цена: каждое чтение делает scatter-gather по многим авторам — дорого и повторяется на каждом обновлении.
- Гибрид: push для обычных авторов (дёшево, часто), pull для знаменитостей (избегает шторма записей), слить на чтении.
Глубокое погружение
Социальная лента — 100:1 по чтению (35 000 чтений ленты/сек против 7 000 постов/сек). У большинства пользователей менее 5 000 подписчиков; у небольшого числа знаменитостей — 30 млн+. Чтение ленты должно отвечать менее чем за 100 мс. Какая стратегия fan-out подходит?
Fan-out-on-write vs fan-out-on-read
Это ядро компромисса, и это отношение чтение:запись, ставшее конкретным. При 100:1 делать работу на записи и амортизировать её на 100 чтениях обычно выигрыш — потому push по умолчанию. Предвычисленная лента — просто список id постов на пользователя (Redis sorted set, со скором по времени или ранку); чтение — «взять топ N id, гидрировать посты» — миллисекунды.
Pull — обратная ставка. Он дёшев на записи (одна копия каждого поста), но дорог на чтении: сборка ленты значит запросить недавний таймлайн каждого аккаунта из подписок и слить, на каждом обновлении, без амортизации. Для пользователя, подписанного на 1 000 аккаунтов, это scatter-gather на 1 000 ветвей на каждую загрузку ленты. Pull выигрывает лишь когда записи сильно превосходят чтения или когда подписчики редко читают — противоположность ленты.
Так почему не push всегда? Из-за хвоста.
Проблема знаменитости и гибрид
Push ломается для аккаунтов с высоким числом подписчиков. Пост на 30M подписчиков — 30M записей; «горячий ключ» знаменитостей значит, что несколько аккаунтов генерят непропорциональную долю всей работы fan-out, а всплеск постов знаменитостей — шторм записей из hook. Элегантная починка — инвертировать стратегию для немногих аккаунтов, ломающих общую: не разворачивать посты знаменитостей на записи вовсе. Вместо этого хранить их раз и на чтении, для каждой знаменитости, на которую подписан пользователь, тянуть её недавние посты и сливать в (в основном предвычисленную) ленту.
Это работает, потому что асимметрия идёт в обе стороны: знаменитостей мало (так per-read pull — горстка лишних лукапов, а не тысячи), и на них подписаны многие (так push был бы катастрофичен). Порог (скажем, аккаунты выше ~100k–1M подписчиков) классифицирует автора как push или pull. Путь чтения становится: читать предвычисленную ленту, тянуть недавние посты знаменитостей из подписок, слить, ранжировать, нарезать. Слияние дёшево, потому что число знаменитостей-в-подписках-на-юзера мало.
▸Почему это работает
Почему гибрид реально это решает, а не просто двигает стоимость по кругу? Потому что он сопоставляет каждую стратегию той стороне степенного закона, где она дёшева. Push дёшев, когда число подписчиков мало (большинство авторов) и ты амортизируешь на многих чтениях — так используй его там. Pull дёшев, когда число таких авторов, на которых подписан читатель, мало (ты подписан на немногих знаменитостей) — так используй его там. Аккаунты, делающие push дорогим (огромное число подписчиков), — ровно те аккаунты, что редки на читателя, так что тянуть их на чтении стоит каждому читателю лишь нескольких лишних лукапов. Гибрид — не компромисс, посредственный в обоих; это две оптимальные стратегии, приложенные к двум режимам распределения, где каждая по-настоящему дёшева. Единственная добавленная сложность — слияние и порог, маршрутизирующий автора в push или pull.
Ранжирование, feed cache и пагинация
Ранжирование. Современная лента не строго обратно-хронологическая; она ранжирована по предсказанной вовлечённости (свежесть, аффинность к автору, тип контента, предсказанная вероятность лайка/коммента). Прагматичный дизайн держит разбивку генерация кандидатов, затем ранжирование: fan-out/pull даёт набор кандидатов из недавних id постов (дёшево), а стадия ранжирования скорит их (дороже, приложено к малому набору кандидатов, а не ко всему графу). Ранжирование может идти на чтении по кандидатам или быть частично предвычислено; так или иначе оно оперирует над ограниченным списком кандидатов, никогда над всем таймлайном.
Feed cache. Предвычисленная лента живёт в in-memory хранилище (Redis sorted set на юзера), держа топ несколько сотен id постов — не полные посты. Ты ограничиваешь список (не хранишь всю историю пользователя в кеше; старые записи отпадают), а на промахе кеша или для неактивных пользователей можешь лениво пересобрать из таймлайнов авторов. Хранение id, а не тел, держит кеш малым и позволяет один объект поста гидрировать раз и шарить. Риск горячего ключа (вирусный пост) обрабатывается кешированием самого тела поста за CDN/edge-кешем, так что гидрация популярного поста не штурмует хранилище постов.
Пагинация. Никогда не пагинируй ленту по offset. Offset-пагинация (LIMIT 20 OFFSET 10000) медленнее по мере прокрутки и пропускает или дублирует элементы, когда новые посты приходят между запросами. Используй курсорную (keyset) пагинацию: клиент шлёт скор/id последнего виденного элемента, а сервер возвращает элементы после этого курсора. Это O(1) независимо от глубины и стабильно при вставках — верный примитив для бесконечной прокрутки над постоянно растущим списком.
▸Частая ошибка
Тонкая, но дорогая ошибка — трактовать «ленту» как единый консистентный материализованный список и пытаться держать его идеально в синхроне — пере-fan-out на каждом редактировании, удалении, смене приватности или отписке. На масштабе ленты это разорительно: пользователь, отписавшийся от кого-то, или удаливший пост, триггерил бы ещё одну операцию на N записей. Сеньорный подход — держать предвычисленную ленту приблизительной и на основе id и решать корректность на гидрации/чтении: когда гидрируешь id поста, ты проверяешь текущую видимость (удалён? заблокирован? теперь приватен?) и отбрасываешь его, если он больше не годится, а не вычищаешь из миллионов предвычисленных списков. Feed cache — быстрый индекс кандидатов, а не источник истины; источник истины — посты и граф, а ленте позволено быть eventually consistent и слегка устаревшей. Борьба с этим превращает каждую мутацию в шторм fan-out.
Хранилище таймлайнов
Две вещи хранятся раздельно. Посты (источник истины) живут в долговечном хранилище, шардированном по id автора — таймлайны авторов пишутся раз и читаются путём pull и гидрацией. Ленты (производный вид на потребителя) живут в feed cache, шардированном по id потребителя/пользователя, держа ранжированные id постов с потолком и TTL. Держать их раздельными — это то, что позволяет одному посту быть упомянутым миллионами лент без копирования его тела, позволяет пересобрать ленту из постов по требованию и позволяет шардировать write-heavy таймлайны авторов и read-heavy ленты потребителей по разным ключам под их разные паттерны доступа.
Твоя лента 100:1 read-heavy. Чистый fan-out-on-write даёт мгновенные чтения, но пост знаменитости на 30M подписчиков вызывает шторм записей, стопорящий ленты всех. В чём стандартная починка?
Лента использует LIMIT 20 OFFSET n для бесконечной прокрутки. Глубокие прокрутки медленны, и пользователи сообщают, что посты появляются дважды или пропускаются. В чём причина и починка?
Поскольку лента примерно 100:1 read-heavy, стратегия по умолчанию делает дорогую работу раз, когда пост _______, и амортизирует её на многих чтениях — предвычисляя ленту каждого подписчика, так что чтение — просто лукап кеша; лишь знаменитости, где это взорвалось бы, обрабатываются наоборот (тянутся на чтении).
Узкие места и компромиссы
Доминирующая сила — степенное распределение подписчиков: это почему ни одна стратегия не работает и почему гибрид существует. Ключевые компромиссы:
- Стоимость записи vs стоимость чтения. Push платит на записи, чтобы сделать чтения дешёвыми (верно для read-heavy); pull платит на чтении, чтобы сделать записи дешёвыми (верно лишь когда чтения редки). Отношение чтение:запись решает дефолт, а распределение подписчиков решает исключения.
- Свежесть vs стоимость. Лента eventually consistent — пост, всплывший секундами позже, норм, и принятие этой устарелости — это то, что позволяет предвычислять, кешировать и избегать пере-fan-out на каждой мутации. Требование строгой свежести вынудило бы pull (дорогие чтения) или постоянный пере-fan-out (дорогие записи).
- Дублирование хранилища vs стоимость сборки. Push дублирует id поста во многие ленты (хранилище + усиление записи), чтобы сделать чтения O(1); pull хранит раз, но платит сборкой на чтение. Хранение id (не тел) ограничивает стоимость дублирования.
- Качество ранжирования vs задержка чтения. Тяжёлое ранжирование улучшает вовлечённость, но стоит компьюта на чтении; разбивка генерация-кандидатов/ранжирование ограничивает эту стоимость, ранжируя лишь малый набор кандидатов, а не весь граф.
Глубочайший инсайт: feed cache — это производный, приблизительный, eventually-consistent индекс, а не источник истины. Трактуй его как авторитетный — и каждое редактирование становится штормом fan-out; трактуй его как быстрый список кандидатов, решаемый против реальных постов на гидрации — и система остаётся дешёвой и корректной.
- 01Сопоставь fan-out-on-write и fan-out-on-read и скажи, что дефолт и почему.
- 02Что такое проблема знаменитости и как гибрид её решает, а не просто двигает стоимость?
- 03Почему хранить id постов в feed cache (не тела) и почему курсорная пагинация?
- 04Почему eventual consistency приемлема для ленты и чего стоит трактовать ленту как источник истины?
Лента — каноническая read-heavy соцсистема (~100:1 чтения:записи), так что дефолт — fan-out-on-write (push): при создании поста вставить его id в предвычисленный feed cache каждого подписчика, так что чтение — дешёвый O(1) лукап кеша, амортизирующий работу записи на многих чтениях. Fan-out-on-read (pull) — зеркало: хранить каждый пост раз, собирать на чтении — дёшев на записях, но неамортизированный scatter-gather на каждом чтении, так что неверный дефолт. Ломатель — степенное распределение подписчиков: пост знаменитости под push — шторм на десятки миллионов записей (hook), так что продакшен запускает гибрид — push для обычных авторов, pull для знаменитостей, слитый и ранжированный на чтении. Гибрид — не компромисс; он прикладывает каждую стратегию к режиму, где она по-настоящему дёшева. Вокруг этого — ранжирование (генерация кандидатов, затем скоринг ограниченного набора, никогда всего графа), feed cache (id постов, не тела, ограниченный, пересобираемый), курсорная пагинация (O(1) по глубине, стабильно при вставках — никогда OFFSET) и раздельное хранилище таймлайнов (посты по автору, ленты по потребителю). Объединяющая идея: лента — производный, eventually-consistent, приблизительный индекс, решаемый против реальных постов на гидрации — трактуй его как источник истины, и каждая мутация станет штормом fan-out. Теперь, когда увидишь систему ленты, падающую на постах знаменитостей, первый вопрос звучит так: есть ли гибрид, или кто-то запустил чистый push для всех подряд?
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.
Примени это
Примени этот урок в реальном проекте.