--- title: Системный дизайн — эталонные разборы (URL shortener, лента, мессенджер, медиа-хостинг) source: подготовлено 2026-09-17, TASK-45.3; §1 — конспект решения из статьи Яндекса (habr 564132, К. Кардаманов); §§2–4 — разборы по тому же 6-этапному фреймворку (System Design Primer, DDIA, производственный опыт) --- # Эталонные разборы: типовые сервисы Четыре билета для тренировок по протоколу `methodology.md` §6. Каждый разбор построен по тем же 6 этапам, что и реальная секция (§1 методички): **требования → потоки и API → крупноблочная схема → детали и БД → ресурсы и узкие места → эксплуатация**. Задача документа — эталон для сверки после раунда и скелет для повторного прогона вслух: формулировки здесь — те, что должны звучать на секции. Как пользоваться: перед раундом свой сервис НЕ перечитывать (раунд засчитывается только «из головы»); после раунда — сверить по чек-листу §6.2 и этому эталону. Числа-константы и формулы — `knowledge-base.md` (KB), речевые паттерны — `methodology.md` §3. Схемы — каркас для доски, не картинка для заучивания: на раунде рисуем сами и проговариваем каждый блок. --- ## §1. URL shortener — эталон Яндекса (полный конспект решения из статьи) Условие задачи из статьи: высоконагруженная система сокращения URL для компании масштаба Facebook, бесплатная и платная версии. Платная не ограничивает RPS, число ссылок и время жизни, даёт более короткие ссылки. Это эталон: вероятный формат нашей секции и образец того, как интервьюер ждёт слышать решение. ### Этап 1. Требования Ключевой ход статьи — **диалог**: кандидат вытягивает числа вопросами. Учим наизусть порядок вопросов и сами числа (они же — скелет расчётов): | Вопрос кандидата | Ответ интервьюера (статья) | |---|---| | Объём переходов по ссылкам? | **500 тыс. RPS в пике** | | HTTP или HTTPS? | Оба, рассчитывать на преимущественно HTTPS | | Сколько ссылок в базе? | **1 млрд всего**, у платных аккаунтов — 1 млн | | Сколько аккаунтов? | Сотни тысяч бесплатных, тысячи платных | | Требование к скорости? | **150 мс для 95 % запросов на чтение** | | Требования к доступности? | **Четыре девятки на чтение** | | Согласованность данных? | **Новые ссылки — строго; модификация существующих — допускается лаг в секунды** | | Лимит для бесплатного аккаунта? | 1000 запросов в минуту | | Как часто появляются новые ссылки? | Сотни тысяч в день (≈ 10–20 RPS записи) | | Анонимные ссылки? | В базовой версии — не реализуем | Производные: чтение/запись ≈ 50 000:1 → весь дизайн про чтение; 4 девятки на чтение при лаге в секунды на модификации → eventual приемлем везде, кроме новых ссылок. ### Этап 2. Потоки и API - **Control plane** (управление, единицы RPS): REST API — авторизация, управление аккаунтом, статистика по ссылкам, поиск/модификация/удаление. Веб-интерфейс + API для сторонних систем из одного REST — просто и достаточно. - **Data plane** (горячий путь, 500k RPS): `GET /{id}` → **HTTP 302 Moved Permanently**. Ничего больше: никаких синхронных вызовов в критическом пути. - **Кодирование ссылок** (спойлерят вопросом «как сделать нельзя перебрать»): идентификаторы — **random, не инкремент**. 1 млрд = 2^30 ≈ 32 бита → base36 (36 символов): `36^6 ≈ 2.2 млрд` → **6 символов + 1 разряд против перебора = 7**. Для платных: 1 млн = 2^20 → `36^4 ≈ 1.7 млн` → **4 + 1 = 5 символов**. - Проговорить: 302 (временное перенаправление), а не 301 (постоянное) — модификация ссылки должна доходить до клиента, у нас есть платные правки. ### Этап 3. Крупноблочная схема Блоки: (1) REST control plane → реляционная СУБД (источник правды); (2) синхронизация СУБД → KV; (3) data plane: IPVS-балансировщики → воркеры (веб-сервер + ко-локальный KV store); (4) асинхронные процессы: LAT actuator, актуализатор RPS limiter, TTL/GC. ``` CONTROL PLANE (единицы RPS) DATA PLANE (500k RPS) ┌────────┐ ┌─────────┐ ┌──────────────────────┐ │ клиенты│──▶│ REST API│───▶│ RDBMS (источник правды)│◀───┐ oplog→apply └────────┘ └─────────┘ │ primary + hot standby │ │ └──────────┬───────────┘ │ │ репликация │ ▼ │ ┌────────┐ ┌──────┐ ┌─────────────────────────────┐ │ │ клиенты│──▶│ IPVS │──▶│ воркер: веб-сервер + L1 кэш │──┘ └────────┘ └──────┘ │ + KV store (L2) │ (×4 ДЦ) (×4) └──────────┬───────────────────┘ │ асинхронно (очередь на базе KV) ┌────────────┼───────────────┐ ▼ ▼ ▼ LAT actuator RPS limiter TTL / GC (accessed) (снимки в СУБД) (фоновые) ``` Проговорить: control и data plane разделены физически; горячий путь — балансировщик → воркер → локальный KV, больше никого; всё остальное — асинхронное. ### Этап 4. Детали + БД **4.1. Хранение (источник правды).** Любая реляционная СУБД, managed-решение. Нагрузка на запись 10–20 RPS — справится один сервер; схема из двух таблиц: ```sql CREATE TABLE Account ( account_id INTEGER NOT NULL PRIMARY KEY, login VARCHAR NOT NULL UNIQUE, type BOOLEAN NOT NULL -- free / paid ); -- сотни тысяч записей, единицы МБ CREATE TABLE Link ( link_id INTEGER NOT NULL PRIMARY KEY, account_id INTEGER NOT NULL REFERENCES Account, ttl INTEGER, created DATETIME NOT NULL, accessed DATETIME NOT NULL, url VARCHAR NOT NULL ); -- ~1 млрд записей × сотни байт = сотни ГБ ``` Объём «сотни гигабайт» → **без шардирования**: primary + hot standby реплики; managed-СУБД с автопереключением primary по консенсусу. Несколько равнозначных веб-серверов control plane → транзакции обязательны (race condition). **4.2. KV-зеркало (контур чтения).** Чтение 500k RPS одну реляционную СУБД не вытянет → read-only зеркало: in-memory KV store, пары `link_id → {url, account_id}`. Прикидка: ~100 ГБ (миллиард × 100 байт), ~100k RPS на сервер, CPU почти не тратит → **данные не шардировать, а реплицировать**. Формулировка: «источник правды — реляционная СУБД, горячее чтение — KV-зеркало; конкретное хранилище не принципиализирую — нужен in-memory KV с репликацией». **4.3. Синхронизация двух хранилищ** — обязательный сюжет секции: - Доставка изменений: штатная репликация выбранного KV **или** собственная через таблицу журнализации: ```sql CREATE TABLE Oplog ( id INTEGER NOT NULL SERIAL PRIMARY KEY, link_id INTEGER NOT NULL, account_id INTEGER NOT NULL, optime DATETIME NOT NULL, url VARCHAR NOT NULL ); ``` - **Частичный отказ** (запись в одной подсистеме прошла, в другой нет): 2PC — дорог; упрощение из статьи: **коммит в основную СУБД только после подтверждения от большинства реплик KV (majority)**; возможный мусор в KV → **фоновая периодическая сборка мусора**. - **Строгая согласованность новых ссылок** при чтении с отстающих secondary: на веб-сервере **L1 LRU-кэш**; промах в KV (L2) → сходить в центральную СУБД, результат — в L1. Это read-your-writes для новых ссылок и ограничение нагрузки на СУБД. Требование «новые — строго» закрыто, «модификации — лаг секунды» — репликацией. **4.4. Горячий путь GET (алгоритм модуля веб-сервера)** — проговаривать по шагам: 1. По `link_id` → из KV: `url` + `account_id`. 2. Активность аккаунта: **не синхронный запрос в RPS limiter** (удлиняет критический путь), а read-only таблица `account_id → RPS` **в разделяемой памяти воркера**, обновляемая спец-процессом раз в секунду. Объём: сотни тысяч ключей × 4 байта + байт на счётчик — сортированный список, единицы МБ. Квота превышена → `HTTP 429 Too Many Requests`, обработка завершена. 3. Зарегистрировать обращение и ответить. Учёт — асинхронно: `account_id → counter` копится в памяти воркера → раз в секунду в RPS limiter; множество затронутых `link_id` → раз в минуту в распределённую очередь. **Формула паттерна: «не нужно для ответа пользователю → из горячего пути — в память воркера, батчами во внешний мир»**. **4.5. LAT actuator (актуализация времени доступа).** Воркеры раз в минуту кладут множества `link_id` в очередь (multiple producers — single consumer; легко реализуется на базе того же KV). Сервисный процесс: забрать всё, слить множества, `UPDATE Link SET accessed = now() WHERE link_id IN (...)`. Отказоустойчивость: несколько равнозначных процессов, на каждой итерации захват служебного поля `SELECT ... FOR UPDATE`. **4.6. RPS limiter.** Выбор: отдельный gRPC-сервис vs состояние в основной СУБД. Критерий — поток обновлений: он умеренный (счётчики приходят батчами раз в секунду) → **состояние в основной СУБД**. Плюсы: не строим ещё один распределённый сервис с репликацией и консенсусом; состояние персистентно и согласовано. Минусы и их адресация (проговорить все три!): задержка актуализации — единицы секунд, приемлемо; риск отказов data plane при переключении primary СУБД — воркеры работают со **снимком в разделяемой памяти**, обновляемым асинхронно; риск нагрузки на СУБД — data plane **никогда не пишет** в СУБД напрямую, только через очередь. ```sql CREATE TABLE RPSLimit ( account_id INTEGER NOT NULL REFERENCES Account, balance SMALLINT NOT NULL, -- остаток квоты limit SMALLINT NOT NULL -- полная квота ); -- тысячи записей (окно малое, нулевые вычищаем) → снимок ~полмегабайта CREATE TABLE RPSLimitSnapshot ( data BYTEA NOT NULL ); -- protobuf + сжатие ``` Воркеры забирают полный снимок раз в ~100 мс (полмегабайта × сотни воркеров — приемлемо; бинарный формат + сжатие). Процесс лимитера: агрегирует события из очереди в памяти, пишет снимок; счётчики — **leaky bucket**: события вычитают `balance`, каждый квант добавляется фиксированная ёмкость, полное ведро (`balance = limit`) → запись удаляется из состояния. Бонус алгоритма — **burst budget**: легальный кратковременный всплеск. **4.7. Фоновые процессы.** По таймеру + блокировка (как LAT actuator): удаление ссылок с истёкшим TTL; сборка мусора от незавершённых транзакций. ### Этап 5. Ресурсы и узкие места - **Control plane:** единицы RPS → минимальные VM с единицами CPU. СУБД: ~10 CPU, доминантный ресурс — **диск** (сотни ГБ) → полноценный сервер, ×3 (managed, консенсус). - **Data plane — дефицит CPU:** HTTPS на порядок дороже plain HTTP; на каждый ID ссылки клиент приходит **с новым TLS-handshake** (session reuse не считаем) → **~20k RPS на сервер**. KV тянет 100k RPS, но CPU не нужен → **ко-локация: по инстансу KV рядом с каждым веб-сервером** — утилизирует память сервера, localhost без проксирования, минус сетевой хоп. Пара «сервер + KV» = **воркер**; `500k / 20k = 25 воркеров` в пике. - **Избыточность:** переживаем отказ целого ДЦ, оставаясь на 25 воркерах → **9 воркеров × 4 ДЦ = 36**; IPVS — по серверу на ДЦ (маршрут не должен выходить за пределы ДЦ) = 4; +3 СУБД. **Итого 43 сервера**; запас — до двух воркеров на обновление при недоступном регионе. Консенсуса в контуре чтения нет → число регионов не критично. - **Бюджет времени ответа:** клиент ↔ сервер — до 120 мс (NY↔Москва); воркер ≤ 10 мс (KV на localhost — единицы мс, сервер — единицы мс, маршрутизация в ДЦ — сотни мкс). Итого ~130 мс < 150 мс p95 → **гео-распределение сверх 4 ДЦ не требуется** — запас сам его отменяет. ### Этап 6. Эксплуатация **Сценарии отказов** (таблица на доске: узел → последствие → действие): | Узел | Последствие | Действие | |---|---|---| | IPVS-балансировщик | Нагрузка на оставшиеся 3 | Многократный запас, ничего не делаем | | Воркер (веб+KV) | Нагрузка на остальных 8 в ДЦ | Если в ДЦ живых воркеров < 6 → **исключить ДЦ из балансировки** | | Secondary СУБД | Нет | — | | Primary СУБД | Замедляется только control plane; GET не задет | Автопереключение managed-СУБД | | RPS limiter, LAT, GC | Основные функции работают | Мониторим отставание, риски — на вспомогательных функциях | **Перегрузка чтения в разы:** короткие пики — очередью на воркерах (запас по латентности есть); антифрод на IPVS — хосты/подсети с аномальной активностью, blacklist, формируемый воркерами; в blacklist — источники, запрашивающие много одинаковых/несуществующих ссылок; понижение криптоустойчивости SSL-сертификатов. **Мониторинг:** агрегация по классам серверов (СУБД primary/secondary, KV, веб-сервер, IPVS, RPS limiter, вспомогательные); ресурсы CPU/RAM/disk IO/net; RPS и латентность **по квантилям**; коды ответов — с защитой от шума (перебор несуществующих ссылок, аккаунты с исчерпанной квотой). **Логи и трассировка:** при 500k RPS логи дороги и сами могут уронить сервис → писать на локальный SSD/NVMe, частая ротация, сжатие → дешёвое холодное хранилище (по возрасту — разные уровни избыточности). Трассировка: каждый k-й запрос и/или по опциональному флагу. **Обновления:** воркеры независимы, до трёх в ДЦ можно терять → катим **по 3 воркера внутри ДЦ, ДЦ — строго последовательно**, сверяя метрики с остальными. Тестовый контур меньшего размера с репликой данных, куда **дублируется каждый k-й запрос прода**. Обновление СУБД — с небольшим даунтаймом: на чтение не влияет, если протестировано на контуре. **Финал — возврат к требованиям:** 150 мс p95 → бюджет 130 мс, запас на пики; 4 девятки чтения → N+1 на каждом ярусе + 4 ДЦ; новые ссылки строго → L1 + majority-коммит; лимиты бесплатных → RPS limiter со снимками; каждое требование контролируется метрикой. ### Чему учит эталон (паттерны статьи — звучат на любой секции) 1. Всё, что не нужно для ответа пользователю, — асинхронно (accessed, счётчики, лимиты). 2. Источник правды один (СУБД), горячее чтение — read-only проекция (KV-зеркало). 3. Вместо 2PC — majority-коммит + фоновая GC; вместо синхронных RPC — снимки состояния в разделяемой памяти. 4. Ко-локация по доминантному ресурсу (CPU у сервера, память у KV — на одной ноде). 5. Ресурсы считаем от дефицитного ресурса (TLS-handshake → 20k RPS/нода), запас закладываем сценариями (9×4), а не «серафами». 6. KISS: лимитер — на существующей СУБД, очередь — на существующем KV; самописное — только то, чего нет в готовом. ### Сверка с Alex Xu (гл. 8, TASK-45.38) — что книга добавляет к эталону Наш эталон использует числовой `link_id`; книга проговаривает выбор схемы короткого кода и его стоимость: - **Два способа генерации кода**: (а) **hash + коллизии**: MD5/CRC32 → первые 7 символов, при коллизии пересчём с добавленной строкой — фиксированная длина, проверка коллизии по БД ускоряется **фильтром Блума**; (б) **base62(ID)**: уникальный ID (например, snowflake) → 62-ричная запись, коллизий нет, но код предсказуем (следующий ID очевиден) — вопрос безопасности. Длина: 365 млрд ссылок за 10 лет → 62^7 ≈ 3.5 трлн — хватает 7 символов. - **301 vs 302 — другая грань трейдоффа**: наш аргумент — модификация ссылки; у книги — аналитика: 301 кэшируется браузером → нагрузка на сервис минимальна, но клики не считываются; 302 → каждый клик через сервис → счётчики и источники переходов. Проговорить обе грани. - **Оценка книги**: 100 млн новых ссылок/день = 1160 QPS запись, чтение ×10 — порядок совпадает с нашими прикидками (KB §2.2). Полный текст с диалогом «кандидат–интервьюер»: `materials/alex-xu-vol1/ch-08-url-shortener.md`. --- ## §2. Лента новостей (Instagram/Twitter) Условие: спроектировать ленту новостей соцсети — заявленный формат нашей секции («крупноблочная схема сервиса класса инстаграм/твиттер + отказоустойчивость»). ### Этап 1. Требования Данных нет — гипотезы вслух (числа совпадают с примером KB §2.3, там же формулы): | Параметр | Гипотеза | Производное | |---|---|---| | DAU | 100 млн | — | | Открытие ленты | 10 раз/сутки | чтение `100M×10/86400 ≈ 11.5k QPS avg`, пик ×3 → **~35k QPS** | | Публикация постов | 2/сутки | запись ≈ **2.3k QPS** | | Подписчики в среднем | 300 | fan-out: `2.3k×300 ≈ 700k вставок/с` в ленты — **узкое место тут, не пост** | | Латентность | p95 отдачи ленты ≤ 200 мс | кэш лент обязателен | | Доступность | 99.9 % на чтение ленты | деградация — свежестью, не недоступностью | | Консистентность | eventual: пост у подписчиков ≤ 5 с; свой пост видим автору сразу (read-your-writes) | fan-out может отставать | | Медиа | фото/видео в постах обязательны | блоб-хранилище + CDN | | Retention | вечно, счётчики eventual | — | ### Этап 2. Потоки и API Сущности: **User, Post (id, author_id, ts, text, media[]), Follow, FeedItem**. API (пара сигнатур на доску): - `POST /posts` (idempotency-key) → пост; `GET /feed?cursor=` → страница ленты; - `POST /users/{id}/follow`, `POST /posts/{id}/like` (eventual-счётчики). Идентификаторы постов — **Snowflake**: время внутри ID → хронология без сортировки, сортировка ленты = сортировка ID. Разделение: постинг и чтение ленты — data plane; профили, подписки, модерация — control plane. ### Этап 3. Крупноблочная схема ``` чтение: клиент → LB → Feed API → кэш лент (Redis) ─┐ (miss: merge из таймлайнов) ─┐ └──▶ посты (шардированная БД) ─┤ реплики постинг: клиент → LB → Post API → БД постов (источник правды) │ │ └── медиа → S3 → транскодинг → CDN │ └── событие → Kafka ──▶ fan-out воркеры ──▶ кэш лент ◀───────┘ (700k вставок/с — load leveling) ``` Проговорить горячий путь чтения: балансер → Feed API → кэш лент → ответ (единицы мс). Путь постинга длинный, но он в 15 раз менее частый — его сложность никому не мешает. ### Этап 4. Детали + БД **Fan-out: on write vs on read** — центральный трейдофф разбора, давать таблицей: | | Fan-out on write (push) | Fan-out on read (pull) | |---|---|---| | Что происходит | При посте вставка во все ленты подписчиков | Лента собирается на запросе: merge последних постов всех подписок | | Чтение | Быстрое: лента готова в кэше | Медленное и дорогое: merge на каждый запрос, пик чтения ×15 к записи | | Запись | Дорогая, отложенная (очередь) | Мгновенная | | Селебрити | Катастрофа: 10M подписчиков = 10M вставок | Норм: читатели сами тянут её посты | | Активные читатели с 1000+ подписок | Норм | Катастрофа: merge 1000+ таймлайнов на запрос | | Мёртвые аккаунты | Пушим в пустоту — впустую | Не платим | **Решение — микс** (так делают Twitter/Instagram): push обычным пользователям (их 99.9 %), **pull для селебрити** (порог, например, > 1M подписчиков). На чтении лента = кэшированный push-список + merge свежих pull-постов подписок-селебрити. Псевдокод публикации: ``` publish(post): save(post) -> posts DB # источник правды emit(PostCreated, post) -> Kafka # ключ = author_id fanout_worker(event): if followers(author) <= 1M: # обычный путь for uid in followers: append(cache[uid], post.id) # батчами, по shard'ам else: nothing # селебрити: читатели вытянут сами ``` **Celebrity problem (двусторонний!):** (а) пост селебрити не пушим — merge на чтении, его последние посты держим в кэше агрессивно (read-mostly, идеальный кэш-кандидат); (б) горячий шард кэша по user_id селебрити — consistent hashing + реплики горячих ключей. Отдельно: пользователь с миллионом подписок пишет → 700k вставок/с среднее по кластеру может превратиться в пик → очередь сглаживает, воркеры шардированы по подписчикам. **Кэш лент:** Redis-кластер, шардирование по user_id (consistent hashing); значение — список post_id глубиной ~800 (полная лента не нужна, дожимаем merge'ем при прокрутке). Память: 80/20 — горячие 20 % пользователей: `20M × 800 × 8 Б ≈ 130 ГБ` чистых ID, с overhead Redis — единицы ТБ на кластер — нормально. **Stampede-защита**: miss обрабатывается с per-user блокировкой; rebuild ленты = merge последних постов подписок + таймлайнов селебрити, результат кэшируется; мягкий TTL. **Read-your-writes**: свой пост вставляется в свою ленту синхронно на Post API + L1-кэш (та же идея, что в эталоне Яндекса §4.3). **Хранилище постов:** источник правды — шардированная по post_id реляционная/ширококолонночная БД (хеш по ID); индексы `(author_id, ts DESC)` для таймлайнов селебрити, PK post_id. Соцграф (Follow) — отдельная БД, шардирование по user_id: единственный запрос в горячем пути постинга — «список подписчиков автора». **Счётчики** (лайки/просмотры): не трогаем транзакцию поста — `INCR` в Redis + периодический батч-флаш в БД (паттерн эталона: «не нужно для ответа → асинхронно»). **Медиапайплайн:** upload → presigned multipart прямо в S3 (мимо API) → событие в очередь → транскодеры (несколько рендиций) → CDN. Метаданные поста пишем сразу; медиа доезжает фоном (плейсхолдер в ленте) — пост откладывать до готовности не будем: трейдофф «свежесть поста > полная комплектность», проговорить. **CDN:** весь медиа-трафик (гигабиты) — с edge; origin shield — один промах в origin на объект; подписанные URL с TTL. ### Этап 5. Ресурсы и узкие места - Чтение 35k QPS пика → Feed API: ~1–10k RPS/ноду → единицы-десятки нод ×4 ДЦ. - **Fan-out 700k вставок/с — это и есть дизайн**: очередь + шардированные воркеры; узкое место не «написать пост», а «доставить 300 подписчикам ≤ 5 с». Метрика — lag очереди. - Storage постов: `2.3k/с × 1 КиБ × 3×10^7 с ≈ 70 ТБ/год` с индексами → шардирование, «в одну ноду не влезает». - Кэш: единицы ТБ Redis; медиа — сотни ТБ/год в S3-класс; bandwidth: медиа → CDN (API-трафик — единицы Гбит, не сравниваем с медиа). - Вывод-формулировка: «две системы с разной природой: лента — это кэш и доставка (миллионы мелких операций), медиа — это блобы и CDN (гигантские объекты); смешивать нельзя». ### Этап 6. Эксплуатация | Узел | Отказ | Поведение / действие | |---|---|---| | Redis-нода | Часть лент ушла | Consistent hashing перераспределяет; miss → rebuild из таймлайнов (медленнее, но работает); метрика hit rate | | Fan-out воркеры | Посты не доставляются в кэш | Лента «стареет» — graceful degradation; **lag очереди — главная метрика**, алерт на порог > X с | | Kafka-партиция | Доставка в партиции стоит | Реплики, min.insync=2; лидер-фейловер прозрачен | | Шард БД постов | Не открываются посты шарда | Replica promotion; чтение через кэш смягчает | | Перегрузка чтения ×10 | Деградация p95 | Приоритет: чтение ленты > постинг > счётчики; load shedding на постинге; **адаптивный fan-out** — пушим только активным за 30 дней подписчикам, остальные дочитывают pull'ом | | Целый ДЦ | — | 4 ДЦ, клиентская геобалансировка; кэш прогревается из постов (источник правды цел) | Мониторинг: kafka lag, fan-out latency p95, cache hit rate, p95 отдачи ленты, глубина очередей; релизы: canary на fan-out-воркерах (самое опасное место — регрессия доставки увидится в lag до полного выката). **Трейдоффы, которые должны прозвучать:** push vs pull vs микс; глубина кэша vs память; своя лента vs merge на лету; пост сразу vs пост после транскодинга; строгие счётчики vs eventual. ### Сверка с Alex Xu (гл. 11, TASK-45.38) — что книга добавляет Наш разбор глубже книжного (у книги 10M DAU и оба сценария — push/pull/микс — совпадают, celebrity-проблема тоже). Взять из книги: - **Графовая БД для соцграфа** — конкретный выбор под запрос «друзья пользователя» (у нас — отдельная шардированная БД соцграфа, формулировка «графовая БД» — ещё один способ назвать выбор вслух). - **Кэш лент хранит только `post_id`, не контент** — у нас так же (`список post_id глубиной ~800`), книга даёт простую формулировку для секции. - **Фильтры перед fan-out** (mute, приватность) читаются из кэша пользователей до раскладки — иначе «размутинг» поста невозможен. - **Consistent hashing fanout-узлов** + очередь перед воркерами fan-out — сглаживание «горячих авторов» (у нас — очередь + шардинг по подписчикам, совпадает). Полный текст: `materials/alex-xu-vol1/ch-11-news-feed.md`. ### Сверка с DDIA 2-е изд. (гл. 2, TASK-45.39) — учебный кейс книги Глава 2 (новая во 2-м издании) разбирает те же домашние ленты как вводный кейс НФТ — наши числа совпадают по духу, книга даёт эталонные величины для доски: - **Математика выбора:** наивный polling (2M читающих ходят в БД авторов) ≈ 2M запросов/с; материализация (fan-out on write): 5,800 постов/с × средний fan-out 200 ≈ **1M записей в кэш лент/с** — порядок тот же, но читатель тянется кэшем, а не БД. Формулировка для этапа 5: «1M лёгких записей в Redis против 2M тяжёлых чтений — обмен выгодный». - **Celebrity:** не раскладывать посты миллионщиков по всем лентам — **merge at read** (нашего гибрида case); тяжёлые подписчики (тысячи подписок) — **семплирование**: часть fan-out записей можно дропать, читатель всё равно не прочитает всё. - **Хвостовая амплификация:** чтение ленты — fan-out по кэшам → один медленный узел тянется в общую p99 — ещё один аргумент за кэш post_id списков, а не контента. Полный текст: `materials/ddia-2ed/ch-02-nfr-timelines-case.md`. --- ## §3. Мессенджер Условие: мессенджер — 1:1 диалоги, группы, онлайн-статусы, история; звонки и медиа отмечаем как «вне скоупа детализации». ### Этап 1. Требования | Параметр | Гипотеза | Производное | |---|---|---| | DAU | 50 млн, одновременно онлайн ~20 % = 10M соединений | gateway-кластер | | Сообщений | 20 отправленных/сутки на пользователя | `50M×20/86400 ≈ 11.5k msg/s avg`, пик ×3 → **~35k msg/s**; доставок в 2–3 раза больше (группы) | | Латентность | p95 доставки ≤ 500 мс (до онлайн-получателя) | push через постоянные соединения | | Доставка | 100 %: at-least-once + дедуп на клиенте | идемпотентность обязательна | | Порядок | **строгий внутри диалога** | seq per dialog | | Консистентность | eventual между устройствами (секунды); история — источник правды | — | | История | навсегда, офлайн-получатели дочитывают при подключении | write-heavy хранилище | | Группы | до 1000 участников; каналы-миллионники отмечаем, не детализируем | ленивая доставка | ### Этап 2. Потоки и API Сущности: **User, Dialog (1:1 или группа), Message (dialog_id, seq, sender, ts, body), Presence**. Протокол: **WebSocket** (постоянные соединения) + protobuf-фреймы: `send(msg, idempotency_key)`, серверные `deliver`, `ack`, `sync(cursor)`; история — обычный REST `GET /dialogs/{id}/messages?before_seq=`. Control plane (профили, контакты, настройки групп) — отдельно от data plane (коннекты, доставка). ### Этап 3. Крупноблочная схема ``` клиент ⇄ gateway (WS, 500k коннектов/нода) ⇄ Kafka (партиции по dialog_id) ⇄ delivery-воркеры │ registry: user_id → gateway_id (Redis, TTL+heartbeat) │ │ ▼ └── push offline: APNs/FCM messages store (источник правды, LSM, партиции по dialog_id) presence: события online/offline → шина → presence-сервис (Redis TTL) ``` Проговорить: сообщение всегда сначала пишется в источник правды и только потом летит в шину — «потеря шины не теряет сообщение». ### Этап 4. Детали + БД **Connection-серверы (gateway).** Нода держит ~500k коннектов (epoll: коннект — это файловый дескриптор и килобайты состояния). Gateway не бизнес-логика: терминирует TLS/WS, шлёт heartbeat'ы, знает своих пользователей. После коннекта пишет в **registry** (Redis): `user_id → gateway_id` с TTL, обновляемым heartbeat'ом. Reconnect после обрыва — с **jitter** (иначе рестарт ноды = шторм из 500k переподключений). **Доставка сообщения (псевдокод — главный алгоритм разбора):** ``` send(from, dialog, body, idem_key): 1. gateway → валидация (участник, лимиты) 2. msg_store.append(dialog, msg) -> seq # источник правды, атомарный seq per dialog 3. emit(MessageSaved) -> Kafka, key=dialog_id # порядок в партиции = порядок диалога delivery_worker(event): 4. for uid in recipients(dialog): # из соцграфа gw = registry.lookup(uid) if gw: gw.push(uid, msg) # онлайн else: push_notification(uid) # офлайн: история догонит по sync(cursor) 5. ack клиента → статус delivered/read → событие обратно в шину ``` **Гарантии и порядок:** шина даёт at-least-once → дедуп по `(dialog_id, seq)` на клиенте (или idempotency_key на входе). Порядок — **монотонный seq внутри диалога**, назначает хранилище при вставке (одна партиция = один писатель на диалог); ключ партиции Kafka = dialog_id → порядок сохраняется на всём пути. «Строгость» нужна только внутри диалога — глобальный порядок сообщений не нужен и не строится (трейдофф). **Online-статус:** gateway публикует online/offline в шину; presence-сервис держит `user_id → {status, last_seen}` с TTL (мертвые коннекты зачищаются сами). Подписка на друзей — через шину событий. **Throttle**: статусы не чаще раза в N секунд, при массовом онлайне — батчи; presence не должен ложить доставку (он первый кандидат на load shedding). **Группы:** доставка — fan-out по участникам из соцграфа (их у группы тысячи, не миллионы — ок). Каналы-миллионники — отдельная история: указатель на сообщение, контент тянем по запросу (как pull в ленте) — проговорить одной фразой и не детализировать. **Хранилище:** write-heavy (35k msg/s пик) → **LSM-движок** (KB §3, DDIA гл. 3: быстрый write ценой компактации); партиционирование по dialog_id; индекс `(dialog_id, seq)`; медиа — ссылки на S3/CDN, не в сообщении. Ретеншн вечный → холодные ярусы по возрасту. ### Этап 5. Ресурсы и узкие места - Gateway: `10M соединений / 500k = 20 нод` → с запасом по сценариям ~9×4 ДЦ (прямая параллель с эталоном Яндекса). - Шина: 35k msg/s пик — тысячи партиций по dialog_id; delivery-воркеры масштабируются горизонтально, узкое место — не throughput, а **lag**. - Storage: `11.5k msg/s × 1 КиБ × 3×10^7 с ≈ 400 ТБ/год` текста + медиа в S3 → LSM-кластер с горизонтальным ростом. - Bandwidth: текст копеечный; медиа/файлы → CDN, как в §4. - Узкое место по_latency: не хранилище (единицы мс), а число хопов gateway→шина→воркер→gateway — считать хопы вслух: «4 хопа внутри ДЦ × ~0.5 мс RT = в бюджете 500 мс лежим с запасом». ### Этап 6. Эксплуатация | Узел | Отказ | Поведение / действие | |---|---|---| | Gateway-нода | 500k переподключений | Клиенты reconnect с jitter; registry TTL протухает; недоставленное ждёт в шине/истории — доставка после reconnect; соединения при релизах — drain плавно | | Партиция Kafka | Доставка в диалогах стоит | Реплики; лидер-фейловер; метрика lag per партиция | | Messages store | Диалоги недоступны | Отправка деградирует в ошибку (честный 5xx), приём — из истории; replica promotion | | Presence/registry | Онлайн-статусы врут, доставка через офлайн-путь | Не влияет на доставку сообщений — приоритизация работает | | Перегрузка ×10 | Растёт lag | Приоритет: сообщения > статусы > typing-индикаторы; shedding на presence; rate limit на отправку | Мониторинг: **end-to-end delivery p95** (от send до deliver онлайн-клиенту), lag шины, reconnect rate (шторм!), глубина очередей, доля офлайн-доставок. Релизы: gateway — drain + canary на одну ноду; воркеры — canary с контролем lag. **Трейдоффы, которые должны прозвучать:** писать в хранилище до шины (надёжность) vs после (латентность); seq в хранилище vs внешний координатор; push всем vs ленивая догрузка для каналов; presence в Redis TTL vs gossip. ### Сверка с Alex Xu (гл. 12, TASK-45.38) — что книга добавляет Ядро совпадает (WebSocket как дефолт, stateful-гейтвеи, история в KV, seq per dialog, push офлайн через APNs/FCM). Из книги: - **Mailbox-модель групп**: копия сообщения в «sync queue» каждого участника — просто и дёшево для групп ≤100–500 (так делает WeChat); наш fan-out по соцграфу — та же идея без отдельного термина; термин знать. - **`message_id` локальный vs глобальный**: достаточно уникальности **в рамках канала** (составной ключ `(channel_id, message_id)`); глобальный snowflake — если нужна сортировка/шардирование по времени. У нас — seq per dialog, совпадает. - **Синхронизация устройств**: каждое устройство держит `cur_max_message_id`, новое = `id > cur` — наш `sync(cursor)` из той же логики. - **Service discovery через Zookeeper** для выбора чат-сервера — у нас registry в Redis с TTL+heartbeat; назвать оба как варианты (KB §13.5). - **Presence через heartbeat с подавлением мигания** — у нас тоже TTL/heartbeat; книга проговаривает, зачем именно heartbeat (кратковременный разрыв ≠ offline). - **Выбор long polling для уведомлений** (гл. 15): события редкие и односторонние — WebSocket избыточен (KB §13.3, §14.5). Полный текст: `materials/alex-xu-vol1/ch-12-chat-system.md`. --- ## §4. Медиа-хостинг (видео) Условие: видеохостинг — загрузка, обработка, отдача; социальные функции (комментарии, каналы) отмечаем и не детализируем. ### Этап 1. Требования Гипотезы из примера KB §2.4 (там формулы — прогоняем вслух): | Параметр | Гипотеза | Производное | |---|---|---| | Загрузки | 10k/сутки × ~1 ГБ исходник | рост storage **30–50 ТБ/сутки** с транскодами → десятки ПБ/год → только объектное хранилище | | Просмотры | 100k/сутки × 5 мин × 3 Mbps | egress ≈ 10 ТБ/сутки ≈ 1 Gbps avg, пик ×3–5 → **CDN обязательна** | | Латентность | p95 старт воспроизведения ≤ 2 с; rebuffer < 1 % | CDN + ABR | | Доступность | 99.9 %+ на просмотр (отдаёт CDN) | origin может lag'ать | | Консистентность | метаданные — строго; **готовность рендиций — eventual, минуты** (обработка отстаёт от загрузки — приемлемо, проговариваем) | статусы в API | ### Этап 2. Потоки и API Сущности: **Video (id, owner, status: uploaded → processing → ready / failed), Rendition (bitrate, resolution, manifest), ViewEvent**. API: `POST /videos` → создаёт запись и отдаёт **presigned multipart upload URL**; `POST /videos/{id}/complete`; `GET /videos/{id}` → статус + манифест; отдача — `GET /cdn/.../{id}/manifest.m3u8`. Control plane (загрузка, метаданные, модерация) отделён от data plane (просмотр через CDN). ### Этап 3. Крупноблочная схема ``` upload: клиент → presigned multipart ──▶ S3 (исходник) ──▶ событие → очередь │ transcode: транскодинг-фарм (сегменты параллельно) ──▶ S3 (рендиции HLS/DASH) │ metadata: RDBMS (status, длительность, счётчики eventual) ◀────────┘ watch: клиент ──▶ CDN (сегменты+манифест) ──▶ origin shield ──▶ S3 counters: клиент ──▶ events API ──▶ очередь ──▶ батч-писатель ──▶ RDBMS ``` ### Этап 4. Детали + БД **Upload:** файлы по 1 ГБ — **resumable multipart**: чанки 5–20 МБ, retry каждого чанка отдельно, докачка после обрыва; загрузка идёт **прямо в S3 по presigned URL** — API-сервис не проксирует гигабайты (он же control plane). После `complete` — валидация/антивирус асинхронно; идемпотентность по upload_id (двойной complete не создаёт второй обработки). **Транскодинг — асинхронный пайплайн:** событие в очередь (at-least-once, воркеры идемпотентны, DLQ для битых видео); исходник режется на **GOP-сегменты → параллельный транскодинг** (часовое видео на десятке нод — минуты); на выходе **ladder битрейтов** (1080/720/480/360 + аудио) в формате **HLS/DASH: сегменты по 4–10 с + манифест**. Сегменты заодно решают адаптивный битрейт (ниже). Статус в метаданных: `processing → ready` (или failed + retry-политика). Оригинал сразу — в холодный класс хранения (он нужен редко: перетранскодинг, жалобы). **Блоб-хранилище:** S3-класс, никакой NAS (расчёт KB §2.4: десятки ПБ/год). Ключи с video_id-префиксом; lifecycle: рендиции — hot, оригиналы — infrequent/cold; версионирование от перезаписи. **CDN:** egress 1 Gbps avg / 3–5 Gbps пик — отдавать из своего кластера глобально дорого и медленно → CDN с offload 90 %+; **origin shield** — один промах в origin на сегмент (иначе N edge-нод ударят одновременно); **signed URLs** против хотлинка; cache-control: сегменты иммутабельны → max-age большой; прогрев первых сегментов популярных видео (старт ≤ 2 с). **Счётчики просмотров:** клиент шлёт heartbeats-события каждые N секунд → очередь → батч-апдейт (паттерн эталона Яндекса: не в горячем пути просмотра); точность ±проценты приемлема, дедуп по (client_id, video, окно). Просмотр никогда не трогает RDBMS синхронно. **Адаптивный битрейт (ABR):** сервер отдаёт манифест со всеми рендициями; клиент выбирает сегмент по текущей пропускной способности и заполнению буфера: быстрый старт с низкого качества → апгрейд. Ключевая фраза: «интеллект ABR — на клиенте, сервер только предлагает лестницу». ### Этап 5. Ресурсы и узкие места - Storage: 30–50 ТБ/сутки → объектное хранилище с lifecycle; стоимость = функция retention (считать вслух: «100 ТБ/сутки × 3 года — это уже эксабайт-класс разговора про холодные ярусы и попросят уточнить retention»). - Egress → CDN: offload 90 % значит origin видит ~1 ТБ/сутки вместо 10. - Транскодинг: минуты CPU-часов на минуту видео × 10k видео/сутки → фарм из десятков нод; очередь сглаживает суточный пик загрузок — **задержка обработки вместо роста фермы** (проговорить как трейдофф: SLA «ready ≤ 30 мин» определяет размер фермы). - Узкое место дизайна — не throughput, а **консистентность статусов**: пользователь видит «обрабатывается» минуты; API отдаёт статус из метаданных, CDN — только готовые сегменты. ### Этап 6. Эксплуатация | Узел | Отказ | Поведение / действие | |---|---|---| | Транскодер-нода | Очередь догоняет | Retry на другом воркере; DLQ; деградация = «обрабатывается дольше», потери нет | | Очередь | Пайплайн стоит | Реплицированная, durability; ретрансляция недообработанных по статусам | | Origin (S3) | Промахи CDN | Origin shield + cache-control: горячее в CDN живёт; холодное — деградация старта | | CDN | Глобальный инцидент | Мульти-CDN/резервный провайдер — отмечаем; локально — origin перегрузим лимитами | | Перегрузка просмотров ×10 | — | CDN масштабируется сам; лимитируем origin (это и есть защита) | | Перегрузка загрузок ×10 | Ферма не справляется | Rate limit на пользователя, приоритет платным/проверенным; очередь — буфер | Мониторинг: **старт-тайм p95 и rebuffer ratio** (пользовательские метрики качества — QoE), CDN offload %, cache hit, lag очереди транскодинга, доля видео `ready < 30 мин` (SLA), ошибки 4xx/5xx по API. Релизы: транскодеры — canary на тестовых роликах с автоматическим сравнением качества (VMAF); upload API — canary обычным порядком; манифесты/сегменты иммутабельны → откат CDN не нужен, откатываем генератор. **Трейдоффы, которые должны прозвучать:** обработка до готовности vs постинг «в обработке»; размер ladder vs storage/качество; сегмент 4 с vs 10 с (старт vs overhead); один CDN vs мульти; точность счётчиков vs цена записи. ### Сверка с Alex Xu (гл. 14, TASK-45.38) — что книга добавляет Совпадает каркас (presigned multipart upload, GOP-сегменты → параллельный транскодинг, HLS/DASH + манифесты, CDN offload, статусы processing→ready, событие по завершении). Взять из книги: - **DAG-модель пайплайна транскодинга** (как у Facebook): препроцессор (нарезка GOP, построение DAG из конфигов, кэш сегментов для ретраев) → планировщик DAG (параллельные ветки: видео/звук/миниатюра/водяной знак) → диспетчер ресурсов (очереди заданий/воркеров) → специализированные воркеры → временное хранилище → готовое видео. Сильная формулировка для секции: «пайплайн — не одна очередь, а DAG специализированных воркеров с очередями между этапами». - **Двойная развязка путей**: загрузка метаданных и загрузка файла — два независимых API-вызова (у нас presigned + complete — совпадает); **обработчик завершения** обновляет метаданные по событию из очереди завершения. - **Аргумент стоимостью**: CDN $0.02/ГБ × 150 ТБ/день ≈ **$150k/день** — главный OPEX видеосервиса; экономия: популярное — в CDN, long tail — из origin-хранилища; региональные CDN. - **Терминология**: контейнер (видео+звук+метаданные) vs кодек (H.264, VP9, HEVC) — не путать на секции. Полный текст: `materials/alex-xu-vol1/ch-14-youtube.md`. --- ## Связанные документы - `methodology.md` — фреймворк 6 этапов, тайминг, речевые паттерны, протокол тренировок (§6) - `knowledge-base.md` — числа, back-of-envelope, паттерны, карта DDIA - `training/` — логи раундов по этим билетам (`round-NN-<дата>/_round.md`) - `../interview-materials.md` — общая карта материалов по вакансии