Разбор популярных задач
Методология решения
Используйте этот фреймворк для каждой задачи на системный дизайн:
Шаг 1: Уточнить требования (3-5 минут)
Шаг 2: Оценить масштаб (3-5 минут)
Шаг 3: Предложить High-Level Design (10-15 минут)
Шаг 4: Углубиться в детали (10-15 минут)
Шаг 5: Обсудить узкие места (5 минут)Задача 1: Спроектировать URL Shortener (TinyURL)
Требования
Функциональные:
• Создать короткий URL из длинного
• Перенаправить по короткому URL на оригинальный
• Опционально: кастомные alias, TTL, аналитика
Нефункциональные:
• 100M URL создаётся в месяц
• Соотношение чтение:запись = 100:1
• URL должен быть коротким (7-8 символов)
• Высокая доступность
• Минимальная задержка перенаправленияОценка масштаба
Запись: 100M / месяц ≈ 40 URL/сек
Чтение: 40 × 100 = 4000 запросов/сек
Хранение (5 лет): 100M × 12 × 5 = 6B записей
Размер записи: ~500 байт
Общий объём: 6B × 500B = 3TBАрхитектура
┌──────────┐ ┌──────────────┐ ┌──────────────┐
│ Client │────→│ Load Balancer│────→│ API Server │
└──────────┘ └──────────────┘ └──────┬───────┘
│
┌────────┼────────┐
↓ ↓
┌──────────┐ ┌──────────┐
│ Cache │ │ DB │
│ (Redis) │ │(Postgres)│
└──────────┘ └──────────┘Генерация короткого URL
Вариант 1: Base62 encoding
Символы: [a-z, A-Z, 0-9] = 62 символа
7 символов → 62^7 = 3.5 триллиона комбинаций
Подход: auto-increment ID → Base62
ID = 12345 → Base62 → "3d7"
Вариант 2: Хеш (MD5/SHA256) + первые 7 символов
hash("https://example.com/very/long/url")
→ "a1b2c3d" (первые 7 символов)
⚠️ Возможны коллизии → проверять в БД
Вариант 3: Pre-generated keys (Key Generation Service)
┌───────────────────┐
│ KGS (Key Gen) │
│ Заранее генерит │
│ ключи в БД │
│ ┌──────────────┐ │
│ │ used_keys │ │
│ │ unused_keys │ │ ← Атомарная выдача
│ └──────────────┘ │
└───────────────────┘Схема БД
sql
CREATE TABLE urls (
id BIGINT PRIMARY KEY,
short_key VARCHAR(8) UNIQUE NOT NULL,
original_url TEXT NOT NULL,
user_id BIGINT,
created_at TIMESTAMP DEFAULT NOW(),
expires_at TIMESTAMP,
click_count BIGINT DEFAULT 0
);
CREATE INDEX idx_short_key ON urls(short_key);Процесс перенаправления
GET /a1b2c3d
1. Проверить кеш (Redis)
└─ Hit → 301 Redirect
└─ Miss → Шаг 2
2. Запрос к БД
└─ Найден → Сохранить в кеш + 301 Redirect
└─ Не найден → 404 Not Found
301 vs 302:
301 (Permanent) — браузер кеширует, меньше нагрузка
302 (Temporary) — каждый раз идёт на сервер (лучше для аналитики)Задача 2: Спроектировать систему чата (WhatsApp / Telegram)
Требования
Функциональные:
• Отправка и получение сообщений 1-на-1
• Групповые чаты (до 500 участников)
• Статус сообщения (отправлено/доставлено/прочитано)
• Онлайн-статус пользователя
• Push-уведомления
Нефункциональные:
• 500M активных пользователей
• Каждый отправляет ~40 сообщений в день
• Низкая задержка (< 200ms)
• Гарантия доставки
• Порядок сообщенийОценка масштаба
Сообщений в день: 500M × 40 = 20B
Сообщений в секунду: 20B / 86400 ≈ 230K msg/sec
Размер сообщения: ~100 байт
Хранение (1 год): 20B × 365 × 100B ≈ 730TBАрхитектура
┌─────────┐ WebSocket ┌────────────────┐
│ Client A│←───────────→│ Chat Server │
└─────────┘ │ (WebSocket) │
└───────┬────────┘
│
┌─────────┐ WebSocket ┌──────┴─────────┐
│ Client B│←───────────→│ Chat Server │
└─────────┘ │ (WebSocket) │
└───────┬────────┘
│
┌───────────┼───────────┐
↓ ↓ ↓
┌──────────┐ ┌─────────┐ ┌────────┐
│ Message │ │ User │ │ Push │
│ Queue │ │ Presence│ │ Notif. │
│ (Kafka) │ │ (Redis) │ │Service │
└────┬─────┘ └─────────┘ └────────┘
↓
┌──────────┐
│ Message │
│ Store │
│(Cassandra)│
└──────────┘Отправка сообщения
1. Client A отправляет сообщение через WebSocket
2. Chat Server:
a. Валидация
b. Сохранение в Message Store
c. Проверка: Client B онлайн?
3а. Если Client B ОНЛАЙН:
Chat Server → WebSocket → Client B
Статус: "доставлено" ✓✓
3б. Если Client B ОФЛАЙН:
Message Queue → Push Notification Service
При следующем подключении:
Client B ← Fetch unseen messages
Статус: "отправлено" ✓Групповой чат
Отправка в группу (fan-out):
Client A ──msg──→ Chat Server
│
├──→ Client B (online, WebSocket)
├──→ Client C (online, WebSocket)
├──→ Message Queue → Client D (offline)
└──→ Message Queue → Client E (offline)
Для больших групп (>100):
→ Fan-out on read (ленивая загрузка)
→ Клиент запрашивает новые сообщения при входе в чатЗадача 3: Спроектировать ленту новостей (News Feed / Timeline)
Требования
Функциональные:
• Пользователь публикует посты
• Лента содержит посты друзей/подписок
• Посты отсортированы по времени (или рейтингу)
• Поддержка медиа (фото, видео)
Нефункциональные:
• 500M пользователей, 200M DAU
• В среднем 300 подписок на пользователя
• Загрузка ленты < 500ms
• Высокая доступностьFan-out on Write vs Fan-out on Read
Fan-out on Write (Push model):
──────────────────────────────
При создании поста → записать во все ленты подписчиков
User A creates post
→ Write to User B's feed cache
→ Write to User C's feed cache
→ Write to User D's feed cache
→ ... (all 1000 followers)
✓ Чтение быстрое (лента уже готова)
✗ Медленная запись для знаменитостей
✗ Много дискового пространства
Fan-out on Read (Pull model):
──────────────────────────────
При запросе ленты → собрать посты из подписок
User B opens feed
→ Fetch posts from User A
→ Fetch posts from User C
→ Fetch posts from User X
→ Merge & Sort
✓ Быстрая запись
✗ Медленное чтение (много запросов)Гибридный подход (реальные системы)
┌─────────────────────────────────────────────────────────┐
│ Обычные пользователи (< 10K подписчиков): │
│ → Fan-out on Write │
│ → При публикации: записать в ленты подписчиков │
│ │
│ Знаменитости (> 10K подписчиков): │
│ → Fan-out on Read │
│ → При открытии ленты: подтянуть их посты в реальном │
│ времени и смержить с предварительно сформированной │
│ лентой │
└─────────────────────────────────────────────────────────┘Архитектура
┌─────────┐ ┌──────────────┐ ┌──────────────────┐
│ Client │────→│ API Gateway │────→│ Post Service │
└─────────┘ └──────────────┘ │ (создание поста) │
└────────┬─────────┘
│
┌────────▼─────────┐
│ Fan-out Service │
│ (распределение) │
└────────┬─────────┘
│
┌───────────────┼───────────┐
↓ ↓ ↓
┌──────────┐ ┌──────────┐ ┌─────────┐
│ Feed │ │ Post │ │ Media │
│ Cache │ │ Store │ │ Store │
│ (Redis) │ │ (MySQL) │ │ (S3) │
└──────────┘ └──────────┘ └─────────┘
Чтение ленты:
Client → Feed Service → Feed Cache (Redis)
→ Подтянуть посты знаменитостей
→ Merge → ReturnЗадача 4: Спроектировать систему уведомлений
Требования
Функциональные:
• Push-уведомления (iOS, Android)
• SMS-уведомления
• Email-уведомления
• Приоритезация уведомлений
• Настройки пользователя (opt-out)
Нефункциональные:
• 100M уведомлений в день
• Soft real-time (задержка до 30 сек допустима)
• Гарантия доставки (at-least-once)
• Не дублироватьАрхитектура
┌──────────────┐
│ Триггеры: │
│ • Сервисы │
│ • Cron Jobs │
│ • Events │
└──────┬───────┘
│
┌──────▼───────┐ ┌────────────────────┐
│ Notification │────→│ Validation & │
│ Service │ │ Rate Limiter │
└──────────────┘ └────────┬───────────┘
│
┌─────────▼──────────┐
│ Priority Queue │
│ (Kafka / RabbitMQ)│
└─────────┬──────────┘
│
┌──────────────┼──────────────┐
↓ ↓ ↓
┌──────────┐ ┌──────────┐ ┌──────────┐
│ Push │ │ SMS │ │ Email │
│ Worker │ │ Worker │ │ Worker │
└────┬─────┘ └────┬─────┘ └────┬─────┘
↓ ↓ ↓
┌──────────┐ ┌──────────┐ ┌──────────┐
│ APNs / │ │ Twilio / │ │ SendGrid/│
│ FCM │ │ Nexmo │ │ SES │
└──────────┘ └──────────┘ └──────────┘Дедупликация
Проблема: at-least-once может отправить дважды
Решение: Idempotency Key
┌────────────────────────────────────────┐
│ notification_id = hash(user_id + │
│ event_type + │
│ event_id + │
│ timestamp_hour) │
│ │
│ Redis: SETNX notification_id TTL=1h │
│ Если уже есть → пропустить │
└────────────────────────────────────────┘Задача 5: Спроектировать Rate Limiter
Требования
Функциональные:
• Ограничить количество запросов от клиента
• Поддержка разных правил (по IP, по user_id, по API key)
• Возвращать 429 Too Many Requests при превышении
Нефункциональные:
• Низкая задержка (не замедлять обычные запросы)
• Распределённая работа (несколько серверов)
• Точность ограниченийАлгоритмы
1. Fixed Window Counter:
┌──────────┬──────────┬──────────┐
│ 00:00 │ 00:01 │ 00:02 │
│ Count: 8 │ Count: 3 │ Count: 0 │
│ Limit:10 │ Limit:10 │ Limit:10 │
└──────────┴──────────┴──────────┘
⚠️ Проблема: на границе окон может пройти 2x запросов
2. Sliding Window Log:
Хранит timestamp каждого запроса
┌─────────────────────────────────┐
│ [12:00:01, 12:00:15, 12:00:30, │
│ 12:00:45, 12:00:55] │
│ Окно: последние 60 секунд │
│ Count: 5, Limit: 10 → OK │
└─────────────────────────────────┘
✓ Точный, но требует больше памяти
3. Sliding Window Counter:
Комбинация Fixed Window + процент предыдущего окна
Текущее окно (25% прошло): 3 запроса
Предыдущее окно: 8 запросов
Оценка: 8 × 0.75 + 3 = 9 → Лимит 10 → OK
4. Token Bucket:
┌─────────────────────────────────┐
│ Bucket (capacity: 10) │
│ ████████░░ │
│ 8 tokens remaining │
│ │
│ Refill rate: 5 tokens/sec │
│ Запрос: забрать 1 token │
│ Нет tokens → 429 │
└─────────────────────────────────┘
✓ Позволяет burst (всплески) до capacity
5. Leaky Bucket:
┌───────────────┐
│ Входящие │
│ запросы │
│ ↓↓↓ │
│ ┌─────────┐ │
│ │ Queue │ │ ← Фиксированный размер
│ │ (FIFO) │ │
│ └────┬────┘ │
│ ↓ │
│ Обработка │ ← Постоянная скорость
│ с фиксир. │
│ скоростью │
└───────────────┘
✓ Равномерная обработкаРеализация на Redis (Token Bucket)
-- Lua скрипт для атомарности
local key = KEYS[1]
local capacity = tonumber(ARGV[1]) -- 10
local refill_rate = tonumber(ARGV[2]) -- 5 tokens/sec
local now = tonumber(ARGV[3])
local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now
-- Добавить tokens за прошедшее время
local elapsed = now - last_refill
local new_tokens = math.min(capacity, tokens + elapsed * refill_rate)
if new_tokens >= 1 then
new_tokens = new_tokens - 1
redis.call('HMSET', key, 'tokens', new_tokens, 'last_refill', now)
redis.call('EXPIRE', key, 60)
return 1 -- Разрешено
else
return 0 -- Отклонено (429)
endЗадача 6: Спроектировать Distributed Cache
Требования
Функциональные:
• GET(key) → value
• PUT(key, value, TTL)
• DELETE(key)
• Поддержка различных политик вытеснения
Нефункциональные:
• Задержка < 1ms для большинства операций
• Высокая доступность
• Горизонтальное масштабирование
• Поддержка петабайтов данныхАрхитектура
┌──────────┐ ┌──────────────────┐
│ Client │────→│ Cache Proxy │
└──────────┘ │ (Consistent │
│ Hashing) │
└────────┬─────────┘
│
┌─────────────┼─────────────┐
↓ ↓ ↓
┌──────────┐ ┌──────────┐ ┌──────────┐
│ Cache │ │ Cache │ │ Cache │
│ Node 1 │ │ Node 2 │ │ Node 3 │
│ │ │ │ │ │
│ Primary │ │ Primary │ │ Primary │
│ + Replica│ │ + Replica│ │ + Replica│
└──────────┘ └──────────┘ └──────────┘Политики вытеснения (Eviction)
LRU (Least Recently Used):
Удаляет наименее недавно использованный элемент
┌─────────────────────────────────┐
│ Most Recent → ... → Least Recent│
│ [D] [C] [A] [B] [E] │
│ ↑ удалить │
└─────────────────────────────────┘
LFU (Least Frequently Used):
Удаляет наименее часто используемый
Key A: 100 обращений
Key B: 5 обращений ← удалить
Key C: 50 обращений
TTL (Time To Live):
Каждый ключ имеет срок жизни
Key A: expires in 30s
Key B: expired ← удалить
Key C: expires in 120sЧек-лист для System Design интервью
┌─────────────────────────────────────────────────────────┐
│ ☐ Уточнил функциональные требования │
│ ☐ Уточнил нефункциональные требования │
│ ☐ Оценил масштаб (QPS, хранение, пропускная способн.) │
│ ☐ Нарисовал High-Level Architecture │
│ ☐ Определил API endpoints │
│ ☐ Спроектировал схему данных │
│ ☐ Выбрал и обосновал БД │
│ ☐ Обсудил масштабирование │
│ ☐ Обсудил кеширование │
│ ☐ Обсудил отказоустойчивость │
│ ☐ Обсудил мониторинг и observability │
│ ☐ Обсудил компромиссы (trade-offs) │
└─────────────────────────────────────────────────────────┘Резюме
┌─────────────────────────────────────────────────────────┐
│ 1. Всегда начинайте с требований и оценки масштаба │
│ 2. Рисуйте диаграммы — визуализация помогает │
│ 3. Обосновывайте каждое решение │
│ 4. Обсуждайте trade-offs │
│ 5. Знайте типичные задачи и их паттерны решения │
│ 6. Практикуйтесь — решайте 2-3 задачи в неделю │
└─────────────────────────────────────────────────────────┘