Case studies¶

Здесь собрали 5 классических задач системного дизайна с разбором: требования → схема → trade-offs → bottlenecks. Учись их рисовать в одну страницу. На собесе у тебя 30 минут на каждую — больше не дадут.

URL shortener (TinyURL)¶

🧩 Кратко. Пользователь даёт длинный URL, получает короткий вид bm.ru/aBc123. По короткому — редирект на длинный. Это write-light, read-heavy система.

Требования¶

100 млн новых ссылок / день, 10:1 read/write → 10 млрд redirect / день ≈ 115k RPS на чтение, 1.2k на запись.
Latency: redirect < 100 ms p99.
Persistence 5 лет.
Storage: 100M × 365 × 5 × ~500 bytes ≈ 90 ТБ.

API¶

POST /api/v1/shorten
  Body:    { "url": "https://...", "custom_alias?": "promo" }
  Headers: Idempotency-Key
  Response: { "short": "bm.ru/aBc123", "expires_at": "..." }

GET /:code
  Response: 302 Location: <original>

Архитектура¶

graph TB
    User -->|GET /aBc| CDN
    CDN -->|cache miss| LB[Load balancer]
    LB --> API[API instances]
    API --> Cache[(Redis cluster<br/>code→url, 1h TTL)]
    Cache -.miss.-> DB[(Postgres<br/>partitioned by hash)]
    DB --> Replicas[Read replicas]
    User -->|POST /shorten| LB
    API --> KGS[Key generator service<br/>pre-issued codes]
    API --> KafkaC[Kafka:<br/>click events]
    KafkaC --> Agg[Click aggregator]
    Agg --> StatsDB[(stats DB)]

Ключевые решения¶

Генерация коротких кодов. Не hash от URL (collisions, длина). Лучше — пред-сгенерированный пул base62-кодов в KGS, выдаются батчами по 1000. 6 символов base62 = 56 млрд комбинаций — хватит надолго.
Hot path = redirect. CDN на 302-ответ почти не подходит (динамика). → Redis cluster c TTL 1 час. Cache hit ratio 95%+.
БД. Postgres достаточно: schema простая, нагрузка на запись низкая. Partitioning по created_at для архивации старых.
Counter кликов. Не SELECT FOR UPDATE на каждом редиректе! Пишем в Kafka, агрегатор раз в минуту батчует UPDATE.

Trade-offs¶

Custom alias. Уникальность проверяется UNIQUE-индексом + retry с другим alias'ом.
Spam URLs. Нужен фильтр malicious URLs (Google Safe Browsing API, внутренний rate-limit per IP).
Privacy. GET с url'ом в логах? — нет, в логах только code.

📊 Уровни ответа¶

L1: API + Postgres + Redis + LB. Без счётчиков.
L2: то же + Kafka для счётчиков, partitioning, capacity estimation.
L3: KGS, multi-region (geo-distributed read), rate-limiting per IP, custom domain support, abuse detection, compaction для редко-используемых.

News feed (Twitter-like)¶

🧩 Кратко. Пользователь подписан на N людей. Когда заходит — видит хронологический (или ranked) feed их постов. Главный вопрос — fan-out on write vs fan-in on read.

Требования¶

300M MAU, 100M DAU.
Avg 500 followers, выбросы — 100M (Justin Bieber problem).
Avg 5 tweets/day, 100M tweets/day total ≈ 1200 RPS write.
Reads: 100M × 200 feed views/day ≈ 230k RPS read.

API¶

POST /tweets         { text, attachments }
GET /feed?cursor=...
POST /follow/:user

Стратегия 1: Fan-out on write¶

При публикации tweet — пишем его в feed-кэш всех followers сразу.

sequenceDiagram
    User->>API: POST /tweet
    API->>Tweets: save
    API->>Bus: TweetCreated(user_id, tweet_id)
    Bus->>Fanout: process
    Fanout->>Followers: SELECT 500 followers
    loop for each
        Fanout->>FeedCache: LPUSH feed:<follower_id>, tweet_id
    end

✅ Read очень быстрый: GET /feed = LRANGE из Redis. ❌ Запись дорогая: 500 RPS постов × 500 followers = 250k операций в Redis. ❌ Justin Bieber problem. 100M followers × 1 tweet = 100M write ops!

Стратегия 2: Fan-in on read¶

При запросе feed — собираем последние tweet'ы тех, на кого подписан.

SELECT * FROM tweets WHERE user_id IN (followees) ORDER BY created_at DESC LIMIT 50;

✅ Запись дешёвая. ❌ Read дорогой: O(followees × posts), особенно с большим follow list.

Гибрид (что делает Twitter)¶

Обычный пользователь — fan-out on write. Feed pre-computed.
Celebrity (1M+ followers) — fan-in on read. Их посты не пишутся в каждый feed, читаются on-demand при заходе follower'а.
При formировании feed: твой pre-computed feed + последние посты целебрити, на которых подписан, merged по timestamp.

graph TB
    User --> API
    API --> Pre[Pre-computed feed<br/>Redis: from regular users]
    API --> Cel[On-demand fetch<br/>posts of followed celebrities]
    Pre --> Merge[Merge by timestamp]
    Cel --> Merge
    Merge --> Resp[Final feed]

Ключевые решения¶

Storage: tweets в Cassandra/ScyllaDB (ordering by created_at, partition by user_id) или partitioned Postgres.
Feed cache: Redis cluster, по списку tweet_ids на user. TTL 1 неделя для активных, инвалидация при unfollow.
Search/full text: Elasticsearch, асинхронный index из Kafka.
Notifications: отдельный сервис, Kafka.

📊 Уровни ответа¶

L1: posts + followers tables, fan-in on read.
L2: fan-out on write + Redis pre-computed feed.
L3: гибрид + celebrity handling + Elasticsearch для search + ranking model + cassandra для tweets + edge cases (deleted tweets, privacy).

Чат (WhatsApp-like)¶

🧩 Кратко. Пользователи отправляют сообщения друг другу. Real-time доставка, история, read-receipts, групповые чаты. Главные темы — транспорт (long-poll, WebSocket), ordering, delivery semantics.

Требования¶

500M DAU, 50 сообщений/user/день → 25 млрд msg/day ≈ 290k msg/sec.
Latency: P95 < 500 ms.
Storage: текст + медиа (медиа в S3, метаданные в БД).
История: 1 год minimum.

Архитектура¶

graph TB
    Client -->|WebSocket| GW[WS Gateway<br/>длинные коннекты]
    GW --> Pres[Presence service<br/>online/typing]
    GW --> MsgSvc[Message service]
    MsgSvc --> DB[(Cassandra:<br/>messages by chat_id)]
    MsgSvc --> Bus[Kafka: msg events]
    Bus --> Push[Push service]
    Bus --> Search[Search index]
    Bus --> Read[Read receipts]
    Push --> APNS
    Push --> FCM

Транспорт¶

Long-polling — старый. Клиент держит open HTTP-запрос, сервер отвечает при появлении события. Плохой для batter, плохой for high msg rate.
WebSocket — стандарт. Открытое двустороннее соединение. Сервер пушит сразу.
gRPC streaming — хорошо для нативных клиентов.

📌 WebSocket Gateway — отдельный stateful сервис. Один gateway держит ~50k коннектов. Для 500M users → 10000 gateway pods. Sticky session по user_id через consistent hash.

Ordering¶

Внутри одного чата сообщения должны быть упорядочены.
Cassandra: partition by chat_id, clustering by created_at (или Snowflake-id).
Если 2 человека печатают одновременно — берём server timestamp как авторитет.

Delivery semantics¶

At-least-once доставка через Kafka.
На клиенте — dedup по message_id (UUID, сгенерированный отправителем — retry безопасен).
ACK от receiver-клиента → write read_receipt event.

Read receipts (галочки)¶

sent       — сообщение долетело до сервера
delivered  — сервер передал клиенту получателя (ACK от device)
read       — receiver открыл чат (ACK от UI)

Каждое — отдельный event в Kafka.

Ключевые решения¶

Cassandra/ScyllaDB. Чёткие query patterns: «дай N последних сообщений чата X». Идеально для column-family DB.
Redis для presence, typing-indicator, online-counter.
S3 для media. Подписанные URL для upload/download.
Push через FCM/APNS.

📊 Уровни ответа¶

L1: WebSocket + Postgres + Redis. Простой 1-1 чат.
L2: + Kafka для пушей и асинхронной доставки, group chat, read receipts.
L3: + e2e encryption (signal protocol), multi-device sync, offline storage with retry, capacity estimation для 500M, multi-region.

🧩 Кратко. Водители на машинах ездят по городу. Пассажиры заказывают. Сервис матчит пассажира с ближайшим свободным водителем. Главные темы — геопространственный поиск, dispatch, surge pricing.

Требования¶

5M активных водителей, 20M активных пассажиров.
Driver pings каждые 4 сек → 1.25M RPS на location updates.
1M поездок/час → 280 RPS на match.
Latency матча: < 5 сек.

Архитектура¶

graph TB
    Driver -->|location update<br/>каждые 4с| Loc[Location service<br/>geo index]
    Pass[Passenger] -->|request ride| Disp[Dispatch service]
    Disp --> Loc
    Loc -->|nearby drivers| Disp
    Disp --> Match[Match: notify drivers<br/>round-robin / auction]
    Match --> Driver
    Driver -->|accept| Trip[Trip service]
    Trip --> DB[(Postgres trips)]
    Trip --> Bus[Kafka: events]
    Bus --> Pricing
    Bus --> Notifications
    Bus --> Analytics
    Pricing --> Surge[Surge index<br/>by area]

Геопоиск¶

🧩 Простыми словами. Дано: миллионы точек (водителей) и одна точка (пассажир). Найти ближайших K — за миллисекунды.

⚙️ Подходы.

Geohash. Координата → строка типа dr5ru. Префикс = регион. Поиск ближайших — поиск по prefix-индексу. Просто и быстро. Используется в Redis (GEOADD, GEOSEARCH).
S2 cells (Google). Иерархическая сетка из квадратов. Используется в Uber (h3 — гексы, не квадраты).
R-tree. PostGIS реализует. Для PostgreSQL backed систем.
Quad-tree. Для in-memory.

📌 Uber H3 — гексагональная сетка. Hex'ы лучше отражают «равные расстояния» во всех направлениях. Open-source, есть Go-биндинг.

Dispatch¶

Когда пассажир делает запрос:

Получить geohash/h3 пассажира.
Найти всех свободных водителей в этой ячейке + соседних (1–2 уровня).
Отсортировать по ETA (через road network) или по расстоянию.
Послать запрос ближайшему. Если не принял за 10 сек — следующему.

Surge pricing¶

Считается per-area, per-time-window. Пример:

surge_factor = max(1, demand / supply)

Кэшируется per-h3-cell в Redis, обновляется каждую минуту.

Ключевые решения¶

Location: Redis с GEO-командами + write-behind в Cassandra для history.
Trip: Postgres (ACID, состояния).
Real-time updates: WebSocket / GCM.

📊 Уровни ответа¶

L1: Postgres + Redis GEO. Простой match.
L2: + dispatch logic, ETA через road graph, surge.
L3: + h3 / geo-sharding, fault tolerance при отказе ячейки, multi-region, cost optimization.

Web crawler¶

🧩 Кратко. Систематично обходить URLs, скачивать контент, индексировать для поиска. Distributed, дедуп, rate limit вежливости (robots.txt).

Требования¶

1 млрд страниц в месяц → ≈ 400 страниц/сек.
Каждая страница ≈ 100 KB → 100 ТБ/месяц.
Дедуп: одну и ту же страницу не качать N раз.
Вежливость: не больше 1 RPS на один домен.

Архитектура¶

graph TB
    Seed[Seed URLs] --> Q[URL queue<br/>Kafka by domain hash]
    Q --> Fetcher[Fetcher workers]
    Fetcher --> Robots{robots.txt<br/>cache}
    Robots --> Fetch[HTTP GET]
    Fetch --> Dedup[Content hash<br/>seen?]
    Dedup -->|new| Store[Blob storage<br/>S3]
    Dedup -->|new| Parser[HTML parser]
    Parser --> Q
    Parser --> Index[Search index<br/>Elasticsearch]
    Store --> Replay

Ключевые компоненты¶

URL frontier (queue). Kafka, partitioned by hash(domain) — все URL одного домена идут к одному воркеру → проще соблюдать rate-limit.
Fetcher. HTTP-клиент с per-domain rate limit, обработка robots.txt, user-agent.
Content dedup. Хэш SHA-256 контента → bloom-filter + DB.
Parser. Из HTML извлекаются URLs, добавляются обратно в queue.
Storage. Blob storage (S3) для raw HTML, Elasticsearch для индекса.

Дедупликация¶

URL dedup. Bloom filter (False positive ok, false negative no) для быстрой проверки + DB для точной.
Content dedup. SHA-256 контента. Если уже видели — не парсим заново.
Near-duplicate. SimHash / MinHash для «почти одинаковых» страниц.

Politeness¶

robots.txt — кэшируется per домен на 24 часа.
Rate limit: 1 RPS per domain (или то, что в Crawl-Delay).
Adaptive: снижаем rate, если домен начал отвечать 429/503.

Crawl prioritization¶

Page rank.
Last-modified date (свежее > старого).
Depth from seed.

📊 Уровни ответа¶

L1: queue + workers + S3.
L2: + dedup, robots.txt, partition by domain, parser → queue cycle.
L3: + multi-region (regional crawlers), adaptive politeness, near-duplicate detection, crawl prioritization, antitracker / cloaking detection.

Что делать дальше¶

Прорешай эти 5 задач самостоятельно за 30 минут каждую: открой пустой лист, включи таймер, нарисуй и проговори вслух. Запиши, где «провалился» — и вернись к соответствующей странице раздела.

После — иди в interview-playbook.md: тайминг, шаги, что говорить и не говорить.

📝 Подумай¶

Для TinyURL — почему лучше pre-issued коды через KGS, а не hash от URL?
Для feed — что станет узким местом, если все пользователи fan-out on write?
Чем Cassandra лучше Postgres для history сообщений в чате?

Ответ

Hash от URL даёт коллизии (нужно retry с salt) и пустые коды для коротких URL. KGS пред-генерирует уникальные base62-коды, выдаёт батчами — никаких коллизий, distributed-friendly. Также позволяет custom alias (отдельный flow).
Justin Bieber problem: пользователи с миллионами follower'ов. Один tweet = миллион Redis writes. Fan-out становится нелинейным. Решение: hybrid (см. выше).
Cassandra оптимизирована под partition by chat_id, ordered by ts: linear write throughput, дешёвое чтение последних N. Postgres шардить сложнее, master стопорится на write. Cassandra держит миллиарды строк без забот.

Дальше: interview-playbook.md.

Case studies¶

URL shortener (TinyURL)¶

Требования¶

API¶

Архитектура¶

Ключевые решения¶

Trade-offs¶

📊 Уровни ответа¶

News feed (Twitter-like)¶

Требования¶

API¶

Стратегия 1: Fan-out on write¶

Стратегия 2: Fan-in on read¶

Гибрид (что делает Twitter)¶

Ключевые решения¶

📊 Уровни ответа¶

Чат (WhatsApp-like)¶

Требования¶

Архитектура¶

Транспорт¶

Ordering¶

Delivery semantics¶

Read receipts (галочки)¶

Ключевые решения¶

📊 Уровни ответа¶

Ride-sharing (Uber-like)¶

Требования¶

Архитектура¶

Геопоиск¶

Dispatch¶

Surge pricing¶

Ключевые решения¶

📊 Уровни ответа¶

Web crawler¶

Требования¶

Архитектура¶

Ключевые компоненты¶

Дедупликация¶

Politeness¶

Crawl prioritization¶

📊 Уровни ответа¶

Что делать дальше¶

📝 Подумай¶