URL Shortener (TinyURL, bit.ly) — классическая задача на System Design интервью. Она идеально подходит для начинающих, так как сочетает простоту концепции с интересными архитектурными решениями: генерация уникальных ID, масштабирование базы данных и обработка высокой нагрузки на чтение.
Глава 8
Alex Xu: URL Shortener
Детальный разбор в книге System Design Interview
Зачем нужен URL Shortener
Удобство
Короткие ссылки легче запомнить, поделиться в соцсетях и использовать в SMS
Аналитика
Отслеживание кликов, географии пользователей и источников трафика
Контроль
Возможность отключить ссылку, установить срок действия или пароль
Требования
Функциональные
- FR1Создание короткой ссылки из длинного URL
- FR2Редирект по короткой ссылке на оригинальный URL
- FR3Опциональный TTL (время жизни ссылки)
- FR4Custom alias (опционально)
Нефункциональные
- NFR1100M новых URL в день (write)
- NFR210:1 read/write ratio → 1B redirects/day
- NFR3Latency < 100ms для редиректа
- NFR499.9% availability
Back of the Envelope
Traffic
- Write: 100M/day = 1,160 QPS
- Read: 1B/day = 11,600 QPS
- Peak: ~23,000 QPS (2x average)
Storage
- Avg URL size: 500 bytes
- 100M × 500B = 50GB/day
- 5 years: 50GB × 365 × 5 ≈ 90TB
Длина короткого URL
Сколько символов нужно для уникального идентификатора? Используем base62 (a-z, A-Z, 0-9):
| Длина | Комбинации | URLs (5 лет) |
|---|---|---|
| 6 символов | 62⁶ = 56.8B | Не хватит |
| 7 символов | 62⁷ = 3.5T | ✓ Достаточно |
| 8 символов | 62⁸ = 218T | С запасом |
Вывод: 7 символов base62 = 3.5 триллиона комбинаций. При 100M URL/день хватит на 96 лет.
Стратегии генерации ID
1Hash + Collision Resolution
MD5/SHA256 от URL → взять первые 7 символов → проверить коллизию
- Детерминистично (тот же URL = тот же hash)
- Нет central point of failure
- Коллизии требуют retry + DB lookup
- Сложно с custom aliases
2Unique ID Generator + Base62Рекомендуется
Получить уникальный числовой ID → конвертировать в base62
- Гарантированно уникальный (без коллизий)
- Простая логика
- Легко поддерживать custom aliases
- Нужен ID generator (single point?)
- Одинаковые URL могут дать разные short URLs
Варианты ID Generator
Auto-increment DB
Простое решение с auto_increment primary key.
⚠️ Single point of failure, не масштабируется
Multi-master DB
Два сервера: один генерирует чётные ID, другой — нечётные.
✓ Простое масштабирование, но ограничено количеством мастеров
UUID
128-bit уникальный идентификатор, генерируется на клиенте.
⚠️ Слишком длинный (36 символов), плохо для URL
Snowflake IDРекомендуется
64-bit ID: timestamp + datacenter + machine + sequence.
✓ Распределённый, сортируемый по времени, компактный
Snowflake
Twitter/X: Snowflake ID
Детальный разбор алгоритма генерации ID
High-Level Architecture
Architecture Map
Browser / App
Edge routing
Stateless API
Redis
Snowflake
PostgreSQL / Cassandra
Highlight a flow
Cache miss shown as a dashed line to the database.
Write Path
- 1. Клиент отправляет длинный URL
- 2. ID Generator выдаёт уникальный ID
- 3. Конвертируем ID в base62 → short URL
- 4. Сохраняем mapping в DB
- 5. Возвращаем short URL клиенту
Read Path
- 1. Клиент запрашивает short URL
- 2. Проверяем Cache (Redis)
- 3. Cache miss → запрос в DB
- 4. Обновляем Cache
- 5. HTTP 301/302 Redirect
301 vs 302 Redirect
301 Moved Permanently
Браузер кэширует редирект. Следующие запросы идут напрямую на target URL.
✓ Меньше нагрузки на сервер
✗ Нельзя отслеживать клики
302 FoundРекомендуется
Браузер НЕ кэширует. Каждый клик проходит через сервер.
✓ Полная аналитика кликов
✓ Можно менять target URL
Data Model
urls table
| Column | Type | Description |
|---|---|---|
| short_url | VARCHAR(7) | Primary key, base62 encoded |
| original_url | TEXT | Оригинальный длинный URL |
| user_id | BIGINT | Создатель ссылки (опционально) |
| created_at | TIMESTAMP | Дата создания |
| expires_at | TIMESTAMP | TTL (null = бессрочно) |
Deep Dive
Database Internals
Индексы, B-Trees и оптимизация для read-heavy workloads
Caching Strategy
Read/Write ratio 10:1 делает кэширование критически важным. Используем Redis для хранения hot URLs.
Стратегия
- Cache-aside: читаем из кэша, при miss идём в DB
- LRU eviction: вытесняем редко используемые URL
- Write-through: при создании сразу пишем в кэш
Cache Size
20% daily reads × avg URL size
= 200M × 500B = 100GB
→ Redis cluster с репликацией
CDN
Content Delivery Network
Geo-distributed caching для глобальных систем
Выбор базы данных
PostgreSQL
- ✓ ACID гарантии
- ✓ Простота использования
- ✓ Хорошо для средних нагрузок
- ✗ Сложнее горизонтальное масштабирование
Cassandra / DynamoDBДля масштаба
- ✓ Линейное горизонтальное масштабирование
- ✓ Высокая доступность (no single point)
- ✓ Оптимизирован для write-heavy
- ✗ Eventually consistent
Ключевые выводы для интервью
Покажите понимание
• Base62 encoding и расчёт длины URL
• Trade-offs между hash и ID generator
• 301 vs 302 для аналитики
• Read-heavy system → фокус на кэширование
Частые follow-up вопросы
• Как обрабатывать duplicate URLs?
• Как реализовать custom aliases?
• Как удалять expired URLs?
• Как защититься от abuse?