--- title: Системный дизайн — эталонные разборы (URL shortener, лента, мессенджер, медиа-хостинг + 3 решения SDP) source: подготовлено 2026-09-17, TASK-45.3; §1 — конспект решения из статьи Яндекса (habr 564132, К. Кардаманов); §§2–4 — разборы по тому же 6-этапному фреймворку (System Design Primer, DDIA, производственный опыт); §§5–7 — полные конспекты решений System Design Primer в их родном 4-шаговом каркасе (TASK-45.11) --- # Эталонные разборы: типовые сервисы Семь билетов для тренировок по протоколу `methodology.md` §6. §1–4 построены по тем же 6 этапам, что и реальная секция (§1 методички): **требования → потоки и API → крупноблочная схема → детали и БД → ресурсы и узкие места → эксплуатация**. §5–7 — дословные конспекты эталонных решений System Design Primer (`solutions/system_design`) в их 4-шаговом каркасе с back-of-envelope расчётами: это «второе мнение» тех же задач и по ним удобно сверять расчёты (сводная таблица — `knowledge-base.md` §2.6). Задача документа — эталон для сверки после раунда и скелет для повторного прогона вслух: формулировки здесь — те, что должны звучать на секции. Как пользоваться: перед раундом свой сервис НЕ перечитывать (раунд засчитывается только «из головы»); после раунда — сверить по чек-листу §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`. --- ## §5. Pastebin (System Design Primer) — полный конспект решения Источник: `solutions/system_design/pastebin` (TASK-45.11). Задача-родственник URL shortener (§1), но вместо редиректа хранится **контент пасты**: сравнение двух решений — готовый материал для этапа 4. Каркас — 4 шага SDP; соответствие нашим этапам: Step 1 ≈ этап 1 (+ расчёты этапа 5), Steps 2–3 ≈ этапы 2–4, Step 4 ≈ этапы 4–5. ### SDP Step 1. Use cases, constraints, расчёты Use cases (в скоупе): аноним кладёт текст → получает случайную ссылку (экспирация: по умолчанию нет, опционально таймер); открытие пасты по ссылке; аналитика просмотров (месячная, **не realtime**); сервис удаляет просроченное; высокая доступность. Out of scope: аккаунты, логин, редактирование, кастомные ссылки, приватность — вслух помечаем и не детализируем. Допущения: трафик неравномерный; открытие ссылки должно быть быстрым; пасты — только текст; аналитика не realtime. Масштаб: **10 млн пользователей, 10 млн записей/мес, 100 млн чтений/мес → 10:1 read:write**. Расчёт (говорить с формулами): - Паста ~**1.27 KB** = контент 1 KB + `shortlink` 7 B + `expiration_length_in_minutes` 4 B + `created_at` 5 B + `paste_path` 255 B. - Storage: 1.27 KB × 10 млн/мес = **12.7 GB/мес**, ~450 GB за 3 года, **360 млн ссылок**; считаем, что обновлений почти нет — всё новые записи. - RPS (конверсия 1 rps = 2.5 млн/мес): **4 writes/s, 40 reads/s** в среднем, на пике выше. ### SDP Step 2. High level design Клиент → **Web Server как reverse proxy** → разделение на **Write API** и **Read API** (уже на этом шаге — предвестник масштабирования) → **SQL Database** как большая hash-таблица (shortlink → путь) + **Object Store (S3)** для контента пасты. Альтернатива из решения: NoSQL key-value store вместо SQL+Object Store — назвать трейдофф (SQL: транзакции и знакомая модель; KV: проще горизонтальный масштаб), решение дальше идёт по SQL-варианту. ### SDP Step 3. Core components (4 use case'а) **Создание пасты.** Поток: Client → Web Server → Write API: сгенерировать уникальный URL (проверка дубликата в SQL, если дубль — перегенерить), записать строку в таблицу `pastes`, сохранить контент в Object Store, вернуть ссылку. ```sql shortlink char(7) NOT NULL expiration_length_in_minutes int NOT NULL created_at datetime NOT NULL paste_path varchar(255) NOT NULL PRIMARY KEY(shortlink) ``` - PK по `shortlink` = индекс уникальности; дополнительный индекс по `created_at` — «log-time вместо скана всей таблицы и держим данные в памяти»; цитата решения про числа: чтение 1 MB из памяти ~250 µs, SSD в 4×, диск в 80× дольше. - Генерация ссылки: **MD5(ip + timestamp) → Base62 → первые 7 символов**. Почему так: MD5 равномерно распределён; Base62 = `[a-zA-Z0-9]` — не требует экранирования в URL (в отличие от Base64 с `+` и `/`); детерминирован. 7 символов дают 62^7 ≈ 3.5 трлн значений — на 360 млн ссылок за 3 года с огромным запасом. Псевдокод base_encode — O(k), k = 7 цифр. **Просмотр пасты.** Client → Web Server → Read API: lookup `shortlink` в SQL; если есть — забрать контент из Object Store; нет — ошибка. REST: `GET /api/v1/paste?shortlink=foobar`. **Аналитика просмотров.** Не realtime → **MapReduce по логам web-серверов**: mapper эмитит `(год-месяц, url), 1`, редьюсер суммирует; результат — в аналитическое хранилище (Redshift/BigQuery). Формулировка для секции: «агрегации, которым не нужна свежесть, считаем батчем по логам — дешевле онлайн-счётчиков». **Удаление просроченного.** Скан SQL по `expiration` старше текущего времени → удалить или пометить. Дёшево на этом масштабе; проговорить трейдофф с фоновой TTL-задачей. ### SDP Step 4. Scale the design Правило решения — проговорить дословно: **«не прыгаем сразу в финальную схему»: benchmark/load test → profile для узких мест → устраняем с трейдоффами → повторяем** (образец — §7). - LB перед пулом web-серверов; CDN на статику/популярные пасты; master-slave реплики SQL; memory cache для популярного контента. - 40 reads/s (пики выше, трафик неравномерный): популярное — из **memory cache**, он же гасит пики; cache miss закрывают SQL-реплики, «пока не заняты репликацией записей». - 4 writes/s: один SQL Write Master-Slave справляется; если нет — **federation → sharding → denormalization → SQL tuning** (стандартная лесенка всех решений). - Object Store «комфортно» держит 12.7 GB/мес — это не наша проблема масштабирования. Additional talking points (меню на остаток времени): NoSQL-типы и SQL vs NoSQL; где/что/когда кэшировать (cache-aside, write-through, write-behind, refresh-ahead); очереди и task-очереди, back pressure; наружу REST, внутрь RPC; service discovery; security; latency numbers; «scaling — итеративный процесс». ### Что брать на секцию (сверка с §1) - Отличие от shortener (§1): не редирект, а хранение контента → появляется Object Store и разделение «метаданные в SQL, тело в S3»; у §1 — счётчик/хэш-генерация и закодированный ID. - MD5+Base62 — второй аргументированный вариант генерации рядом со счётчиком из §1: на секции называем оба и выбираем с трейдоффом (счётчик: детерминирован и предсказуем, но «считает» объём; хэш: не раскрывает объёмы, но нужна проверка коллизий). - Паттерн «аналитика = MapReduce по логам» и «TTL-скан» — переносимы на любой UGC-сервис. --- ## §6. Twitter timeline + search (System Design Primer) — полный конспект решения Источник: `solutions/system_design/twitter` (TASK-45.11). Родная задача SDP для «ленты» (наш §2): сверка после §6 — обязательная часть подготовки. Facebook feed/search — «the same question». ### SDP Step 1. Use cases, constraints, расчёты Use cases: пользователь постит твит → сервис фанует подписчикам (+ push/email); просмотр **user timeline** (активность пользователя) и **home timeline** (активность подписок); поиск по ключевым словам; HA. Out of scope: firehose/стримы, настройки видимости (@reply, hide retweets), аналитика. Допущения: трафик неравномерный; постинг должен быть быстрым; фанаут всем подписчикам — тоже быстрый, **кроме миллионов подписчиков**; 100 млн активных пользователей. Расчёт (говорить с формулами): - Масштабы: **500 млн твитов/день = 15 млрд/мес**; средний фанаут ×10 → **150 млрд доставок/мес**; 250 млрд чтений/мес; 10 млрд поисков/мес. - Твит ~**10 KB** = tweet_id 8 B + user_id 32 B + text 140 B + медиа 10 KB в среднем → 10 KB × 500M/день × 30 = **150 TB/мес, 5.4 PB за 3 года**. - RPS (400 rps = 1 млрд/мес): **чтения 100k/s; твиты 6k/s; доставки фанаута 60k/s; поиски 4k/s**. - Read-heavy: «оптимизируем быстрые чтения твитов; инжест твитов — write-heavy» — это про разные подсистемы. ### SDP Step 2. High level design Client → Web Server (reverse proxy) → **Write API / Read API / Search API** → сервисы: Timeline Service, Tweet Info, User Info, **Fan Out Service**, Search Service + Search Cluster, Notification Service, User Graph Service. Хранилища: SQL (user timeline), **Memory Cache (home timeline)**, Object Store (медиа), Search Cluster (Lucene-подобный). ### SDP Step 3. Core components (4 use case'а) **Пост твита.** Write API: записать твит в **user timeline в SQL**; обратиться к **Fan Out Service**, который: (1) спрашивает User Graph Service о подписчиках (хранятся в memory cache); (2) вставляет твит в **home timeline каждого подписчика в Memory Cache — O(n): 1000 подписчиков = 1000 вставок**; (3) отправляет твит в Search Index Service; (4) кладёт медиа в Object Store; (5) уведомления — асинхронно через очередь. Структура ленты в Redis — нативный лист с плотной упаковкой: ``` tweet n+2 tweet n+1 tweet n | 8B 8B 1B | | 8B 8B 1B | | 8B 8B 1B | | tweet_id user_id meta | ... | ``` **Чтение home timeline** — сборка на лету: Timeline Service достаёт id-шки из memory cache — **O(1)**; Tweet Info Service и User Info Service добирают детали **multiget'ами — O(n)**. Формулировка: «в кэше лежит только пара id — детали добираем батчем». **User timeline** — просто из SQL (это «архив» пользователя, не пре-вычисленный). **Поиск.** Search Service: парсинг/токенизация запроса (разметку снять, термы выделить, опечатки, регистр, булевы операторы) → **scatter-gather по Search Cluster** (Lucene) → merge, rank, sort, вернуть. ### SDP Step 4. Scale the design - **Селебрити-проблема** — главный bottleneck решения: фанаут миллионам подписчиков занимает минуты → race с @replies; лечится re-ordering при выдаче. Сильнее: **не фанать звёздам вовсе** — их твиты находить поиском при чтении, мерджить с home timeline и сортировать на выдаче (гибрид push/pull). - Гигиена кэша: в home timeline держать **несколько сотен твитов**; в кэше — **только активных за 30 дней** (холодный пользователь — пересобрать ленту из SQL: кто в подписках → твиты → залить в кэш); в Tweet Info — только месяц твитов; в User Info — только активные; поисковому кластеру твиты нужны в памяти ради латентности. - SQL: memory cache снижает нагрузку, но **реплик может не хватить на cache miss**, а объём записей убьёт один master-slave → federation → sharding → denormalization → tuning; часть данных — в NoSQL. ### Сверка с нашей лентой (§2) — что совпало и что добавить Совпадает ядро: пре-вычисленная home timeline (fan-out on write) vs сборка на чтение; push/pull-гибрид для селебрити; медиа в object store; уведомления через очередь. Отличия/дополнения из SDP: - **Числовая рамка фанаута**: 6k твитов/с × фанаут 10 = 60k вставок/с в кэш — готовый расчёт, почему «писать во все ленты» требует кэша, а не SQL. - **Разделение Timeline / Tweet Info / User Info** — мелкие stateless-сервисы поверх хранилищ; у нас слои слиты в «Timeline Service». - **Плотная упаковка Redis-листа** (8+8+1 B на твит) — аргумент ёмкости: сотни твитов × пара МБ активных пользователей. - **Гибрид §2**: push только активным подписчикам, pull звёзд; у SDP — то же самое, но с явной политикой 30 дней активности. - Поисковая половина задачи (у нас в §2 есть только набросок): scatter-gather + merge/rank; «индекс в памяти ради латентности». --- ## §7. Scaling to millions of users on AWS (System Design Primer) — лестница масштабирования Источник: `solutions/system_design/scaling_aws` (TASK-45.11). Это не «сервис», а **эволюция архитектуры по ступеням** — скелет наших этапов 4–6: зачем добавляется каждый блок. AWS-специфика не обязательна («principles apply outside the AWS ecosystem») — проговариваем обобщённо. ### SDP Step 1. Constraints и метод Use case: сервис обслуживает чтение/запись, растёт «от 1 пользователя до десятков миллионов». Допущения: неравномерный трафик; нужны реляционные данные; 10 млн пользователей; **1 млрд writes/мес, 100 млрд reads/мес → 100:1 read:write; 1 KB/запись**. Расчёт: **1 TB/мес, 36 TB за 3 года; 400 writes/s, 40k reads/s** (в среднем; пики выше). Метод решения — цитировать дословно: **итерации «benchmark/load test → profile → узкое место → изменения с трейдоффами → повтор»**. У каждой ступени в решении явно записаны Assumptions (что показало профилирование), Goals (что чиним), Disadvantages (чем платим) — это и есть речевой каркас этапа 4. ### Ступень 0 — single box (Step 3 решения) - Один EC2-бокс: web server + storage + MySQL. **Вертикальное масштабирование**: больше бокс; мониторинг узких мест (CPU, память, IO, сеть; CloudWatch/top/nagios/statsd/graphite). - Платим: дорого; нет redundancy/failover. Альтернатива — горизонтальное масштабирование (следующие ступени). - Пока один бокс: Elastic IP (статичный публичный адрес — при failover просто переставляем DNS), DNS (Route 53), безопасность: наружу только 80/443, SSH 22 — whitelist, запрет исходящих соединений с web-ноды. ### Ступень Users+ — разделить boxing Assumption: MySQL съедает память/CPU, диск забивается; вертикальное масштабирование стало дорогим и не позволяет масштабировать web и БД независимо. Цели и шаги: - **Статику — в Object Store (S3)**: файлы пользователей, JS/CSS, картинки, видео; «scalable, reliable, server-side encryption». - **MySQL — на отдельную машину (RDS)**: просто администрировать, мульти-AZ, шифрование. - Безопасность: шифрование in transit/at rest; **VPC — публичный сабнет только web-серверу, всё остальное в приватном**; порты — только whitelist'нутым компонентам. - Disadvantage: рост сложности, правки web-сервера (новые адреса), новые компоненты надо защищать, AWS-расходы растут — взвешивать против self-hosting. ### Ступень Users++ — LB, горизонтальный масштаб, web/app разделение Assumption: web-сервер душится на пиках, вплоть до даунтайма; хотим HA и redundancy. - **LB (ELB/HAProxy)**: ELB высокодоступен «из коробки»; свой LB — active-active/active-passive по AZ; **SSL-терминация на LB** — разгрузка бэкендов и простое администрирование сертификатов. - Несколько web-серверов по нескольким AZ; **MySQL master-slave failover по AZ**. - **Отделение web от app-слоя**: масштабируются независимо; web = reverse proxy; среди app-серверов можно выделить Read API и Write API. - **CDN (CloudFront)** на статику и часть динамики — минус нагрузка и латентность. ### Ступень Users+++ — кэш и read replicas Assumption: профилирование показало read-heavy (100:1) и деградацию БД на чтениях. - **Memory cache (Elasticache)**: часто читаемый контент из MySQL (**сначала проверить, не хватит ли встроенного кэша самой MySQL** — частая забываемая ступень) + **сессии web-серверов → stateless → открывается автоскейлинг**. - Числа из решения: чтение 1 MB из памяти ~250 µs, SSD ×4, диск ×80 — аргумент кэша. - **MySQL Read Replicas** — снять чтения с мастера; логика разделения read/write в web-сервере; LB перед репликами; «most services are read-heavy». - Ещё web/app-нод — отзывчивость. ### Ступень Users++++ — autoscaling и автоматизация Assumption: пики в бизнес-часы США, ночью простаиваем — можно экономить, включая/выключая ноды автоматически. - **Autoscaling**: группа на каждый тип (web/app) в нескольких AZ; min/max инстансов; триггеры CloudWatch — по времени суток (предсказуемая нагрузка) или по метрикам (CPU, latency, трафик, кастомные). - Disadvantage (назвать!): autoscaling добавляет сложности; система реагирует на рост нагрузки **с задержкой** — и вверх, и вниз. - Автоматизация DevOps: Chef/Puppet/Ansible. - Наблюдаемость — полный список решения: **host level** (один EC2), **aggregate** (статы LB), **логи** (CloudWatch, CloudTrail, Loggly, Splunk, Sumo), **внешний мониторинг** (Pingdom, New Relic), **инциденты** (PagerDuty), **ошибки** (Sentry). Это готовый ответ этапа 6. ### Ступень Users+++++ — финальные паттерны Assumption: упираемся в исходные ограничения; продолжаем итерации профилирования. - БД растёт слишком быстро → **в SQL — только свежий период, хвост — в data warehouse (Redshift)**; «warehouse комфортно держит 1 TB/мес». - 40k reads/s: популярное — в memory cache (он же гасит неравномерность и пики); **реплики могут не справиться с cache miss → SQL scaling patterns: federation, sharding, denormalization, tuning**. - 400 writes/s (пики значительно выше) — «может быть tough» для одного master-slave → те же паттерны + **NoSQL (DynamoDB)** для подходящих данных. - Асинхронность: батч/не-realtime работы — через **очередь + workers**; пример решения: аплоад фото → app-сервер кладёт job в SQS → worker (EC2/Lambda) делает thumbnail, обновляет БД, кладёт в Object Store. ### Сверка с methodology и §1–4 - Ступени — это «почему» наших этапов 4–5: каждый блок (LB, CDN, кэш, реплики, шард) добавляем только по показаниям профилирования, с Assumptions/Goals/Disadvantages. Если на секции спросят «зачем вам LB при 40 rps?» — честный ответ из решения: не нужен, он появляется на ступени Users++, когда web-сервер реально душится. - Кэш сессий → stateless → autoscaling: цепочка «хранение сессий в кэше освобождает горизонтальный масштаб» — короткий и сильный пассаж для этапа 4. - Числа ступеней (1 TB/мес, 100:1, 400/40k rps) — опорные «чувствовалища» масштаба: где что перестаёт работать. --- ## Связанные документы - `methodology.md` — фреймворк 6 этапов, тайминг, речевые паттерны, протокол тренировок (§6) - `knowledge-base.md` — числа, back-of-envelope (§2.6 — расчёты всех 8 решений SDP), паттерны, карта DDIA - `materials/sdp-repo-full.md` — полный обход репозитория SDP (решения, Anki), TASK-45.11 - `training/` — логи раундов по этим билетам (`round-NN-<дата>/_round.md`) - `../interview-materials.md` — общая карта материалов по вакансии