MidКейс30 min

URL Shortener

Проектирование сервиса сокращения ссылок: хэширование, base62, коллизии, редиректы, аналитика

SysdesignCase studies

Проектирование сервиса сокращения ссылок -- один из самых популярных кейсов на интервью. Система кажется простой, но скрывает множество интересных инженерных задач.

Шаг 1: Требования

Функциональные требования

  1. Пользователь вводит длинный URL -- система возвращает короткий (7 символов)
  2. Переход по короткому URL -- 301/302 редирект на оригинальный
  3. Короткие ссылки имеют срок жизни (TTL), по умолчанию 5 лет
  4. Опциональный custom alias (пользователь задаёт slug)
  5. Базовая аналитика: количество переходов, география, referrer

Нефункциональные требования

  1. Высокая доступность (99.99%)
  2. Минимальная latency для редиректа (< 50ms)
  3. Короткие ссылки непредсказуемы (нельзя угадать следующую)
  4. Система должна обрабатывать 100M+ DAU

Шаг 2: Оценка нагрузки

<?php

declare(strict_types=1);

final class UrlShortenerEstimation
{
    public static function calculate(): void
    {
        // Assumptions
        $dau = 100_000_000;          // 100M daily active users
        $urlsPerUserPerDay = 0.1;    // 1 URL per 10 users per day
        $readWriteRatio = 100;       // 100 reads per 1 write

        // Write (create short URL)
        $writesPerDay = (int) ($dau * $urlsPerUserPerDay); // 10M/day
        $writeQps = (int) ($writesPerDay / 86400);          // ~116 QPS
        $peakWriteQps = $writeQps * 3;                      // ~348 QPS

        // Read (redirect)
        $readsPerDay = $writesPerDay * $readWriteRatio;     // 1B/day
        $readQps = (int) ($readsPerDay / 86400);             // ~11,574 QPS
        $peakReadQps = $readQps * 3;                         // ~34,722 QPS

        // Storage (per record: ~500 bytes)
        // short_url(7) + long_url(avg 200) + metadata(~293) = ~500 bytes
        $recordSize = 500;
        $storagePerDay = $writesPerDay * $recordSize;        // 5 GB/day
        $storagePerYear = $storagePerDay * 365;              // ~1.8 TB/year
        $storage5Years = $storagePerYear * 5;                // ~9 TB total

        // Total URLs in 5 years
        $totalUrls = $writesPerDay * 365 * 5;               // 18.25 billion

        // Cache (20% hot URLs cover 80% traffic -- Pareto)
        // Cache 20% of daily reads
        $cacheSize = (int) ($readsPerDay * 0.2 * $recordSize); // ~100 GB
    }
}
| Метрика | Значение | |---------|----------| | Write QPS | ~116 (peak: ~350) | | Read QPS | ~11,574 (peak: ~35,000) | | Storage (5 лет) | ~9 TB | | Всего URL (5 лет) | ~18 млрд | | Размер кэша | ~100 GB |

Шаг 3: High-Level архитектура

┌──────────┐      ┌───────────────┐      ┌────────────────────────────────┐
│  Client  │─────>│  Load         │─────>│  Application Servers           │
│          │      │  Balancer     │      │  (PHP-FPM, multiple instances) │
└──────────┘      └───────────────┘      └───────────┬────────────────────┘
                                                     │
                                          ┌──────────┼──────────┐
                                          │          │          │
                                   ┌──────▼──┐ ┌────▼─────┐ ┌──▼──────────┐
                                   │  Redis  │ │ Redis    │ │  Analytics  │
                                   │  Cache  │ │ Counter  │ │  Queue      │
                                   │         │ │ (clicks) │ │  (Kafka)    │
                                   └─────────┘ └──────────┘ └──────┬──────┘
                                                                   │
                          ┌────────────────────────────────────────┐│
                          │           PostgreSQL                   ││
                          │  ┌──────────┐    ┌──────────┐         ││
                          │  │ Primary  │───>│ Replica  │         ││
                          │  └──────────┘    └──────────┘         ││
                          └────────────────────────────────────────┘│
                                                                   │
                                                        ┌──────────▼───────┐
                                                        │  Analytics DB    │
                                                        │  (ClickHouse)    │
                                                        └──────────────────┘

Шаг 4: Дизайн API

<?php

declare(strict_types=1);

// POST /api/v1/urls
final readonly class CreateShortUrlRequest
{
    public function __construct(
        public string $longUrl,
        public ?string $customAlias = null,
        public ?int $expiresInDays = 1825, // 5 years
    ) {}
}

final readonly class ShortUrlResponse
{
    public function __construct(
        public string $shortUrl,      // https://short.ly/abc1234
        public string $longUrl,
        public string $createdAt,
        public string $expiresAt,
    ) {}
}

// GET /api/v1/urls/{shortCode}/stats
final readonly class UrlStatsResponse
{
    public function __construct(
        public string $shortUrl,
        public int $totalClicks,
        public array $clicksByCountry,
        public array $clicksByDay,
    ) {}
}
## Шаг 5: Схема данных 
CREATE TABLE urls (
    id          UUID        PRIMARY KEY DEFAULT gen_random_uuid(),
    short_code  VARCHAR(10) NOT NULL UNIQUE,
    long_url    TEXT        NOT NULL,
    user_id     UUID        NULL,
    expires_at  TIMESTAMPTZ NOT NULL,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT now(),
    updated_at  TIMESTAMPTZ NOT NULL DEFAULT now()
);

-- Main lookup index (most frequent query)
CREATE INDEX idx_urls_short_code ON urls (short_code);

-- For cleanup of expired URLs
CREATE INDEX idx_urls_expires_at ON urls (expires_at) WHERE expires_at < now();

-- For user's URLs listing
CREATE INDEX idx_urls_user_id ON urls (user_id) WHERE user_id IS NOT NULL;

-- Analytics (stored in ClickHouse, not PostgreSQL)
-- CREATE TABLE url_clicks (
--     short_code  String,
--     clicked_at  DateTime,
--     ip          String,
--     country     String,
--     referrer    String,
--     user_agent  String
-- ) ENGINE = MergeTree()
-- ORDER BY (short_code, clicked_at);

Шаг 6: Детальный дизайн

6.1 Генерация короткого кода

Существует несколько подходов. Рассмотрим каждый.

Подход 1: Base62 encoding (рекомендуемый)

<?php

declare(strict_types=1);

final class Base62Encoder
{
    private const CHARSET = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
    private const BASE = 62;

    public static function encode(int $number): string
    {
        if ($number === 0) {
            return self::CHARSET[0];
        }

        $result = '';

        while ($number > 0) {
            $result = self::CHARSET[$number % self::BASE] . $result;
            $number = intdiv($number, self::BASE);
        }

        return $result;
    }

    public static function decode(string $encoded): int
    {
        $number = 0;
        $length = strlen($encoded);

        for ($i = 0; $i < $length; $i++) {
            $char = $encoded[$i];
            $pos = strpos(self::CHARSET, $char);

            if ($pos === false) {
                throw new \InvalidArgumentException("Invalid character: {$char}");
            }

            $number = $number * self::BASE + $pos;
        }

        return $number;
    }
}

// 7-character base62 = 62^7 = 3.5 trillion combinations
// Enough for 18 billion URLs with negligible collision risk
**Подход 2: MD5 Hash + Truncation** 
<?php

declare(strict_types=1);

final class HashBasedGenerator
{
    private const SHORT_CODE_LENGTH = 7;

    public function generate(string $longUrl): string
    {
        $hash = md5($longUrl);

        // Take first 43 bits of the hash (enough for 7 base62 chars)
        $hexPart = substr($hash, 0, 11);
        $number = hexdec($hexPart);

        return substr(Base62Encoder::encode($number), 0, self::SHORT_CODE_LENGTH);
    }

    /**
     * Handle collisions by appending a counter
     */
    public function generateUnique(string $longUrl, \PDO $db): string
    {
        $attempt = 0;
        $maxAttempts = 5;

        while ($attempt < $maxAttempts) {
            $input = $attempt === 0 ? $longUrl : $longUrl . $attempt;
            $shortCode = $this->generate($input);

            // Check if already exists
            $stmt = $db->prepare('SELECT id FROM urls WHERE short_code = ?');
            $stmt->execute([$shortCode]);

            if (!$stmt->fetch()) {
                return $shortCode;
            }

            $attempt++;
        }

        throw new \RuntimeException('Failed to generate unique short code');
    }
}
**Подход 3: Distributed ID Generator (Snowflake-like)** 
<?php

declare(strict_types=1);

final class DistributedIdGenerator
{
    private const EPOCH = 1700000000000; // Custom epoch (milliseconds)
    private const WORKER_ID_BITS = 10;
    private const SEQUENCE_BITS = 12;

    private int $sequence = 0;
    private int $lastTimestamp = -1;

    public function __construct(
        private readonly int $workerId,
    ) {
        $maxWorkerId = (1 << self::WORKER_ID_BITS) - 1;
        if ($workerId < 0 || $workerId > $maxWorkerId) {
            throw new \InvalidArgumentException("Worker ID must be between 0 and {$maxWorkerId}");
        }
    }

    public function nextId(): int
    {
        $timestamp = $this->currentTimeMillis();

        if ($timestamp === $this->lastTimestamp) {
            $this->sequence = ($this->sequence + 1) & ((1 << self::SEQUENCE_BITS) - 1);

            if ($this->sequence === 0) {
                $timestamp = $this->waitNextMillis($this->lastTimestamp);
            }
        } else {
            $this->sequence = 0;
        }

        $this->lastTimestamp = $timestamp;

        return (($timestamp - self::EPOCH) << (self::WORKER_ID_BITS + self::SEQUENCE_BITS))
            | ($this->workerId << self::SEQUENCE_BITS)
            | $this->sequence;
    }

    public function nextShortCode(): string
    {
        $id = $this->nextId();

        return str_pad(Base62Encoder::encode($id), 7, '0', STR_PAD_LEFT);
    }

    private function currentTimeMillis(): int
    {
        return (int) (microtime(true) * 1000);
    }

    private function waitNextMillis(int $lastTimestamp): int
    {
        $timestamp = $this->currentTimeMillis();

        while ($timestamp <= $lastTimestamp) {
            $timestamp = $this->currentTimeMillis();
        }

        return $timestamp;
    }
}
**Сравнение подходов:**
Критерий Base62 + Counter MD5 Hash Snowflake
Коллизии Нет (уникальный counter) Возможны Нет
Предсказуемость Высокая (++) Низкая Средняя
Зависимости Counter service/DB Нет Координация worker ID
Производительность Высокая Высокая Очень высокая
Масштабируемость Нужен атомарный counter Отличная Отличная

6.2 Сервис сокращения (полный)

<?php

declare(strict_types=1);

final class UrlShortenerService
{
    private const CACHE_TTL = 86400; // 24 hours
    private const DEFAULT_EXPIRY_DAYS = 1825; // 5 years

    public function __construct(
        private readonly \PDO $db,
        private readonly \Redis $redis,
        private readonly DistributedIdGenerator $idGenerator,
        private readonly AnalyticsPublisher $analytics,
    ) {}

    public function createShortUrl(
        string $longUrl,
        ?string $customAlias = null,
        ?int $expiresInDays = null,
    ): ShortUrlResponse {
        // Validate URL
        if (!filter_var($longUrl, FILTER_VALIDATE_URL)) {
            throw new \InvalidArgumentException('Invalid URL provided');
        }

        // Check for duplicate long URL (optional: return existing)
        $existing = $this->findByLongUrl($longUrl);
        if ($existing !== null) {
            return $existing;
        }

        // Generate or validate short code
        $shortCode = $customAlias ?? $this->idGenerator->nextShortCode();

        if ($customAlias !== null) {
            $this->validateCustomAlias($customAlias);
        }

        $expiresAt = new \DateTimeImmutable(
            sprintf('+%d days', $expiresInDays ?? self::DEFAULT_EXPIRY_DAYS)
        );

        // Insert into database
        $stmt = $this->db->prepare(
            'INSERT INTO urls (short_code, long_url, expires_at)
             VALUES (:short_code, :long_url, :expires_at)
             ON CONFLICT (short_code) DO NOTHING
             RETURNING id, created_at'
        );

        $stmt->execute([
            'short_code' => $shortCode,
            'long_url' => $longUrl,
            'expires_at' => $expiresAt->format('Y-m-d H:i:s'),
        ]);

        $row = $stmt->fetch(\PDO::FETCH_ASSOC);

        if ($row === false) {
            throw new \RuntimeException('Short code collision. Retry.');
        }

        // Cache the mapping
        $this->redis->setex(
            "url:{$shortCode}",
            self::CACHE_TTL,
            $longUrl,
        );

        return new ShortUrlResponse(
            shortUrl: "https://short.ly/{$shortCode}",
            longUrl: $longUrl,
            createdAt: $row['created_at'],
            expiresAt: $expiresAt->format('c'),
        );
    }

    public function resolve(string $shortCode, array $context = []): string
    {
        // 1. Check cache first
        $longUrl = $this->redis->get("url:{$shortCode}");

        if ($longUrl !== false) {
            $this->trackClick($shortCode, $context);
            return $longUrl;
        }

        // 2. Check database
        $stmt = $this->db->prepare(
            'SELECT long_url, expires_at FROM urls WHERE short_code = :code'
        );
        $stmt->execute(['code' => $shortCode]);
        $row = $stmt->fetch(\PDO::FETCH_ASSOC);

        if ($row === false) {
            throw new UrlNotFoundException("Short URL not found: {$shortCode}");
        }

        // 3. Check expiration
        $expiresAt = new \DateTimeImmutable($row['expires_at']);
        if ($expiresAt < new \DateTimeImmutable()) {
            throw new UrlExpiredException("URL has expired: {$shortCode}");
        }

        $longUrl = $row['long_url'];

        // 4. Populate cache
        $this->redis->setex("url:{$shortCode}", self::CACHE_TTL, $longUrl);

        // 5. Track analytics asynchronously
        $this->trackClick($shortCode, $context);

        return $longUrl;
    }

    private function trackClick(string $shortCode, array $context): void
    {
        // Async: publish to queue, don't block the redirect
        $this->analytics->publish('url.clicked', [
            'short_code' => $shortCode,
            'ip' => $context['ip'] ?? '',
            'user_agent' => $context['user_agent'] ?? '',
            'referrer' => $context['referrer'] ?? '',
            'clicked_at' => date('c'),
        ]);

        // Increment counter in Redis (real-time stats)
        $this->redis->incr("clicks:{$shortCode}");
    }

    private function findByLongUrl(string $longUrl): ?ShortUrlResponse
    {
        $stmt = $this->db->prepare(
            'SELECT short_code, long_url, created_at, expires_at
             FROM urls WHERE long_url = :url AND expires_at > now()'
        );
        $stmt->execute(['url' => $longUrl]);
        $row = $stmt->fetch(\PDO::FETCH_ASSOC);

        if ($row === false) {
            return null;
        }

        return new ShortUrlResponse(
            shortUrl: "https://short.ly/{$row['short_code']}",
            longUrl: $row['long_url'],
            createdAt: $row['created_at'],
            expiresAt: $row['expires_at'],
        );
    }

    private function validateCustomAlias(string $alias): void
    {
        if (strlen($alias) < 3 || strlen($alias) > 20) {
            throw new \InvalidArgumentException('Custom alias must be 3-20 characters');
        }

        if (!preg_match('/^[a-zA-Z0-9_-]+$/', $alias)) {
            throw new \InvalidArgumentException('Custom alias contains invalid characters');
        }

        // Check if already taken
        $stmt = $this->db->prepare('SELECT 1 FROM urls WHERE short_code = ?');
        $stmt->execute([$alias]);

        if ($stmt->fetch()) {
            throw new AliasAlreadyTakenException("Alias already taken: {$alias}");
        }
    }
}
### 6.3 301 vs 302 Redirect
Тип Кэшируется браузером Аналитика Когда использовать
301 Moved Permanently Да Теряем повторные клики SEO, постоянные ссылки
302 Found Нет Каждый клик проходит через нас Аналитика, A/B тесты

Для URL shortener с аналитикой -- 302 (или 307).

<?php

declare(strict_types=1);

final class RedirectController
{
    public function __construct(
        private readonly UrlShortenerService $service,
    ) {}

    public function redirect(string $shortCode): void
    {
        try {
            $longUrl = $this->service->resolve($shortCode, [
                'ip' => $_SERVER['REMOTE_ADDR'] ?? '',
                'user_agent' => $_SERVER['HTTP_USER_AGENT'] ?? '',
                'referrer' => $_SERVER['HTTP_REFERER'] ?? '',
            ]);

            // 302 for analytics tracking
            header("Location: {$longUrl}", true, 302);
            header('Cache-Control: no-cache, no-store, must-revalidate');
            exit;
        } catch (UrlNotFoundException) {
            http_response_code(404);
            echo '404 - URL Not Found';
        } catch (UrlExpiredException) {
            http_response_code(410);
            echo '410 - URL Expired';
        }
    }
}
## Шаг 7: Масштабирование

Кэширование

Read flow:
Client -> LB -> App -> Redis Cache (HIT) -> 302 Redirect
                          |
                    Cache MISS
                          |
                       PostgreSQL -> Populate Cache -> 302 Redirect
  • Кэш покрывает 80% трафика (правило Парето)
  • Используем LRU eviction policy
  • TTL = 24 часа для популярных URL

Шардирование базы данных

При 9 TB за 5 лет -- нужно шардировать:

Shard Key: first 2 chars of short_code
  aa-az -> Shard 1
  ba-bz -> Shard 2
  ...
  za-zz -> Shard N

Или: hash(short_code) % num_shards

Очистка истёкших URL

<?php

declare(strict_types=1);

final class UrlCleanupJob
{
    public function __construct(
        private readonly \PDO $db,
        private readonly \Redis $redis,
    ) {}

    /**
     * Run periodically (e.g., every hour via cron)
     */
    public function cleanup(int $batchSize = 1000): int
    {
        $totalDeleted = 0;

        do {
            $stmt = $this->db->prepare(
                'DELETE FROM urls
                 WHERE id IN (
                     SELECT id FROM urls
                     WHERE expires_at < now()
                     LIMIT :batch
                 )
                 RETURNING short_code'
            );
            $stmt->execute(['batch' => $batchSize]);
            $deleted = $stmt->fetchAll(\PDO::FETCH_COLUMN);

            // Invalidate cache
            foreach ($deleted as $shortCode) {
                $this->redis->del("url:{$shortCode}", "clicks:{$shortCode}");
            }

            $count = count($deleted);
            $totalDeleted += $count;
        } while ($count === $batchSize);

        return $totalDeleted;
    }
}
## Возможные вопросы интервьюера

  1. Как обеспечить уникальность short code в распределённой системе?

    • Snowflake ID (каждый сервер имеет worker_id)
    • Заранее выделенные диапазоны ID (range-based)
    • Атомарный counter в Redis

  2. Что если один URL станет вирусным?

    • Redis кэш поглощает нагрузку
    • CDN кэширует 302 redirect (с осторожностью)
    • Rate limiting per short code

  3. Как предотвратить abuse (спам, фишинг)?

    • Rate limiting на создание URL
    • Проверка URL через Google Safe Browsing API
    • Captcha для анонимных пользователей
    • Блокировка по IP

  4. 301 или 302 redirect?

    • 302 -- если нужна аналитика
    • 301 -- если нужен SEO и меньше нагрузки

  5. Как масштабировать до миллиардов URL?

    • Шардирование по hash(short_code)
    • Read replicas для чтения
    • Redis Cluster для кэша
    • Отделение аналитики в ClickHouse/Kafka

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

Rate Limiter

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

Web Crawler

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

Live streaming (Twitch-like)

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

Google Calendar

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