System Design

Case Study: URL Shortener

Bit.ly обрабатывает 12 миллиардов кликов в месяц на ссылках длиной в 6 символов. Каждый редирект - это $0.0000003 инфраструктуры. Маржа измеряется в долях микросекунды.

  • Bit.ly: 12B кликов/мес, 600K новых ссылок в день, 99.99% SLA на редирект под 50ms.
  • TinyURL: создан в 2002 одним разработчиком, до сих пор бесплатен, обслуживает миллиарды редиректов на 8 серверах.
  • T.co (Twitter): любой URL в твите проходит через t.co - 500M твитов в день, у каждого ссылка длиной 23 символа.
  • Cloudflare R2 + Workers: можно построить URL shortener на 1B запросов в день за $400/мес - стоимость edge-вычислений упала в 10x за 5 лет.

Цели урока

  • Рассчитать QPS и storage для URL shortener
  • Выбрать стратегию генерации unique short URLs
  • Спроектировать многоуровневую систему кеширования
  • Понять трейдоффы 301 vs 302 redirect
  • Масштабировать систему от 100 до 100K+ QPS

Предварительные знания

  • Кеширование и Redis
  • Основы микросервисной архитектуры
  • Back-of-envelope estimation

Требования и оценки

**Задача**: спроектировать сервис сокращения URL (как bit.ly или tinyurl). Пользователи создают короткие ссылки и отслеживают клики.

Read:Write = 100:1 означает read-heavy систему. Агрессивное кеширование критично для производительности.

100M URL в месяц. Сколько QPS на запись (округлите)?

Генерация Short URL

Ключевое решение: как генерировать уникальные короткие идентификаторы для миллиардов URL?

ПодходПлюсыМинусы
Hash (MD5/SHA256)Stateless, одинаковый URL = одинаковый hashКоллизии, нужно truncate
Counter + Base62Гарантия уникальности, короткие URLНужен distributed counter
UUIDПростота, no coordinationОчень длинные (36 chars)
Snowflake IDDistributed, сортируемыеНужна инфраструктура

Какой подход к генерации ID лучше для distributed системы с 10+ серверами?

High-Level Design

Архитектура URL Shortener - классический пример read-heavy системы с простой моделью данных.

Почему аналитика кликов хранится в ClickHouse, а не в PostgreSQL?

Стратегия кеширования

Read:Write = 100:1 → многоуровневое кеширование критично. 20% URL генерируют 80% трафика (Pareto).

**301 vs 302**: 301 (Permanent) кешируется браузером - меньше трафика, но теряется tracking. 302 (Temporary) - каждый клик проходит через сервер.

Популярный URL истёк в кеше. 1000 пользователей одновременно запрашивают его. Что произойдёт без защиты?

Масштабирование

URL Shortener масштабируется горизонтально благодаря stateless серверам и sharded storage.

**Stateless servers**: вся state в Redis/PostgreSQL. Серверы можно добавлять/удалять мгновенно без потери данных.

6 символов Base62 дают 56 миллиардов комбинаций - запаса хватит навсегда, генерировать можно любым способом.

Запас по комбинациям важен, но реальные bottleneck - hot key partition, аналитика, malicious enumeration. Простой auto-increment counter раскрывает скорость роста бизнеса конкурентам.

Bitly выпускает 1.4 млрд ссылок в год; при последовательном ID любой может посчитать темп выпуска. Hash-схемы дают коллизии после 1B на 32 битах. Snowflake даёт нужную случайность плюс sort по времени для time-series partition.

Система выросла до 50K QPS. PostgreSQL не справляется. Какой первый шаг?

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

  • **ID Generation**: Counter + Base62 (Snowflake для distributed)
  • **Short URL length**: 6-7 символов (62^7 = 3.5T комбинаций)
  • **Caching**: CDN → Redis → PostgreSQL (3 уровня)
  • **Redirect**: 301 для SEO, 302 для tracking каждого клика
  • **Analytics**: Async через Kafka → ClickHouse
  • **Scaling**: Stateless servers, sharded DB, Redis Cluster

Связанные темы

URL Shortener использует многие паттерны System Design

  • Caching — Многоуровневое кеширование - основа производительности
  • Case Study: Twitter — Следующий case study - более сложная система
  • Load Balancer — Распределение трафика между серверами

Вопросы для размышления

  • Если 80% трафика приходится на 20% ссылок, какой алгоритм TTL даст оптимальный hit rate при ограниченной памяти Redis - LRU, LFU или adaptive по click_count?
  • Что меняется в архитектуре, если требование 'never lose a URL' (durability) важнее latency: какой компонент становится bottleneck?
  • Sharding по short_url hash балансирует нагрузку, но как поддерживать аналитику 'top 100 URLs by clicks' без распределённого scan?

Связанные уроки

  • sd-03-scalability — URL shortener - классика scalability: млрд коротких ссылок
  • sd-07-caching — Cache hot URLs - ключевой компонент высоконагруженного shortener
  • sd-04-database — Выбор хранилища (SQL vs KV) критичен для производительности
  • ds-06-hash-intro — Base62 хеш от id - ядро алгоритма генерации короткого URL
  • db-01-intro
Case Study: URL Shortener

0

1

Войти