URL Shortener — o "hello world" do system design

O URL shortener é frequentemente chamado de "hello world" do system design não porque seja simples — é porque expõe uma densidade surpreendente de problemas interessantes num sistema aparentemente trivial. A superfície é pequena: receba uma URL longa, devolva uma URL curta, redirecione quando a URL curta for acessada. Mas abaixo dessa superfície estão problemas que aparecem em praticamente todo sistema distribuído: geração de IDs únicos sem coordenação central, caching de dados que têm ciclo de vida, pipelines assíncronos que não podem impactar o caminho crítico de latência, e o trade-off entre consistência e throughput em analytics.

O bit.ly em 2022 processava mais de 10 bilhões de clicks por mês — cerca de 4.000 redirects por segundo no pico. Cada redirect precisa ser resolvido em dezenas de milissegundos. Cada click precisa ser contabilizado para analytics sem adicionar latência perceptível ao redirect. E o sistema precisa estar disponível 24/7 porque cada URL que você encurtou agora depende da existência contínua do serviço.

Requisitos e estimation

Requisitos funcionais do sistema:

• Criar uma URL curta a partir de uma URL longa, com expiração opcional
• Suportar aliases customizados ("shr.tt/meu-evento" em vez de "shr.tt/x7k9p")
• Redirecionar acessos à URL curta para a URL original
• Analytics básico: total de clicks, clicks por dia, distribuição geográfica e por device

Requisitos não-funcionais assumidos para este design:

• 100M redirects/dia, razão read:write de 100:1 → ~1.000 writes/dia
• Latência de redirect P99 < 100ms globalmente
• Disponibilidade 99.99% para redirects (analytics pode tolerar eventual consistency)
• URLs criadas devem ser imprevisíveis (não enumeráveis)

# Capacity estimation
# 100M redirects/dia ÷ 86.400s = 1.157 reads/s (média)
# Pico (3× média): ~3.500 reads/s

# Writes: 100M ÷ 100 (razão) = 1M criações/dia
# 1M ÷ 86.400 ≈ 12 writes/s | pico: ~35 writes/s

# Storage por URL: short_code(7B) + original_url(~200B) + metadados(~100B) ≈ 310 bytes
# Crescimento: 1M criações/dia × 310B = 310 MB/dia
# Em 5 anos: 310MB × 365 × 5 ≈ 566 GB (raw) | com replicação 3×: ~1,7 TB

# Memória de cache (hot set):
# Top 20% das URLs = ~200k URLs ativas
# 200k × 310B ≈ 62 MB → cabe em qualquer instância Redis

Os números revelam um sistema de escala moderada: 3.500 redirects/s é dentro da capacidade de um PostgreSQL com cache Redis na frente. Sharding não é necessário neste volume. O problema técnico mais difícil não é escala — é a geração correta de short codes únicos.

O problema central: geração de short codes únicos

Um short code de 7 caracteres em base62 (a-z, A-Z, 0-9) oferece 62⁷ = 3,5 trilhões de combinações. Com 1M de criações por dia, levaria ~9.600 anos para esgotar o espaço — o espaço não é o problema. O problema é gerar esses códigos de forma eficiente, sem colisões, e sem um ponto central de coordenação que se torna gargalo.

Opção A: Hash da URL original (MD5/SHA truncado)

# MD5("https://exemplo.com/artigo-longo") → "5d41402abc4b2a76b9719d911017c592"
# Pegar os primeiros 7 chars → "5d41402"

# Problemas:
# 1. Colisões: duas URLs diferentes podem gerar o mesmo prefixo de 7 chars
#    (birthday problem: com 3,5T de slots, colisão esperada após ~2.6M inserções)
# 2. Mesma URL sempre gera o mesmo código → não permite criar duas URLs curtas
#    diferentes para a mesma URL longa (analytics separado por campanha)
# 3. Se há colisão: re-hash com salt → código muda → URL curta muda → inconsistência

Hash funciona para sistemas pequenos mas tem problemas fundamentais em escala.

Opção B: Base62 de auto-increment ID

# ID sequencial do banco: 1, 2, 3, 4...
# Converter para base62:
# 1 → "000001" | 100 → "000001c" | 1.000.000 → "4c92"

def to_base62(num):
    chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    result = []
    while num:
        result.append(chars[num % 62])
        num //= 62
    return ''.join(reversed(result)).zfill(7)

# Vantagens: sem colisões, único garantido pelo banco, simples
# Problemas:
# 1. Enumerável: shr.tt/0000001, shr.tt/0000002... → scraping trivial de todas as URLs
# 2. Previsível: adversário pode adivinhar URLs criadas próximas no tempo
# 3. Single point of failure: o gerador de ID no banco é gargalo e SPOF

Opção C: KGS — Key Generation Service

A solução mais robusta para sistemas que precisam de IDs únicos, imprevisíveis e gerados sem coordenação em tempo real é o Key Generation Service: um serviço dedicado que pré-gera short codes aleatórios e os armazena em duas tabelas — codes_available e codes_used.

# KGS pré-gera short codes aleatórios e os armazena:
# Tabela codes_available: (code VARCHAR(7), PRIMARY KEY)
# Tabela codes_used:      (code VARCHAR(7), url_id BIGINT, PRIMARY KEY)

# Quando uma URL é criada:
# BEGIN TRANSACTION
#   SELECT code FROM codes_available LIMIT 1 FOR UPDATE
#   DELETE FROM codes_available WHERE code = :code
#   INSERT INTO codes_used (code, url_id) VALUES (:code, :url_id)
# COMMIT

# O KGS pode manter um buffer em memória de códigos já retirados da tabela
# mas ainda não atribuídos — elimina uma trip ao banco no caminho crítico.

# Vantagens:
# - Imprevisível (gerado aleatoriamente)
# - Sem colisão garantida por transação atômica
# - KGS pode ter réplicas para HA
# - Buffer em memória reduz latência de geração

# Desvantagens:
# - Serviço adicional para operar
# - Em crash do KGS sem persistência do buffer: códigos do buffer são perdidos
#   (aceitável — apenas desperdiça alguns códigos, não gera inconsistência)

Opção D: Snowflake ID + base62

# Snowflake (Twitter, 2010): ID de 64 bits composto de:
# [timestamp 41 bits][datacenter 5 bits][worker 5 bits][sequence 12 bits]
# Garante unicidade sem coordenação central para até 4096 IDs/ms por worker

# Conversão para base62 → 7-8 chars imprevisíveis (por causa do timestamp)
# Mas: timestamp no ID torna o código previsível no tempo
# "se eu sei que a URL foi criada agora, o código começa com X bits específicos"
# Mitigação: shuffle dos bits antes da conversão — complica sem resolver completamente

# Conclusão prática:
# Para URL shortener com imprevisibilidade como requisito: KGS é a melhor opção
# Para sistemas internos onde imprevisibilidade não importa: Snowflake é mais simples

Schema e modelo de dados

-- Tabela principal
CREATE TABLE urls (
    id          BIGSERIAL PRIMARY KEY,
    short_code  CHAR(7)      NOT NULL UNIQUE,
    original_url TEXT        NOT NULL,
    user_id     BIGINT       REFERENCES users(id),
    created_at  TIMESTAMPTZ  NOT NULL DEFAULT NOW(),
    expires_at  TIMESTAMPTZ,           -- NULL = nunca expira
    custom_alias BOOLEAN     NOT NULL DEFAULT FALSE,

    -- Índice para o redirect path (hot path)
    -- Hash index para lookup exato por short_code (não precisa de range scan)
    INDEX idx_short_code USING HASH (short_code),

    -- Índice para listagem de URLs de um usuário
    INDEX idx_user_created (user_id, created_at DESC)
);

-- Tabela de analytics (separada do redirect path)
-- Particionada por mês para queries de período e archive eficiente
CREATE TABLE url_clicks (
    click_id    BIGSERIAL,
    short_code  CHAR(7)     NOT NULL,
    clicked_at  TIMESTAMPTZ NOT NULL,
    country     CHAR(2),
    device_type VARCHAR(20),   -- mobile | desktop | bot
    referrer    TEXT,
    PRIMARY KEY (click_id, clicked_at)
) PARTITION BY RANGE (clicked_at);

-- Analytics agregados (pré-computados para dashboard)
CREATE TABLE url_stats_daily (
    short_code  CHAR(7)     NOT NULL,
    stat_date   DATE        NOT NULL,
    click_count BIGINT      NOT NULL DEFAULT 0,
    PRIMARY KEY (short_code, stat_date)
);

A separação em tabelas distintas é deliberada: o redirect path só precisa da tabela urls (leitura por short_code). Analytics nunca aparecem no caminho crítico de latência — são escritos assincronamente e lidos em queries separadas.

O redirect: 301 vs 302

Esta é uma das decisões mais importantes do URL shortener e a que mais candidatos erram — porque a resposta correta é contra-intuitiva:

# 301 Moved Permanently
# → o browser cacheia o redirect indefinidamente
# → na segunda visita, o browser vai direto para a URL original sem passar pelo shortener
# → vantagem: menos carga no servidor | DESVANTAGEM: analytics incompleto
#   (o browser não visita mais o shortener → click não é contabilizado)

# 302 Found (Temporary Redirect)
# → o browser NÃO cacheia
# → toda visita passa pelo shortener
# → vantagem: todo click é contabilizado | desvantagem: mais carga no servidor

# Para um URL shortener com analytics: 302 é a única opção correta.
# O "custo" de mais carga é mitigado pelo cache Redis — o servidor de aplicação
# não vai ao banco em 95%+ dos redirects.

# Exceção: se o usuário explicitamente quer "sem tracking"
# → retornar 301 com Cache-Control: max-age=86400 (TTL de 1 dia)
# → balance entre performance e privacidade

Cache de redirects: o hot path

O redirect é o hot path do sistema — executado 3.500 vezes por segundo no pico. Cada milissegundo conta. A arquitetura do cache precisa ser pensada em camadas:

# Camada 1: Cache local em memória no servidor de aplicação
# Caffeine (Java) / ristretto (Go) / lru-cache (Python)
# Tamanho: top-1000 URLs mais acessadas nos últimos 60s
# TTL: 60 segundos (aceita dados levemente stale)
# Benefício: zero latência de rede; elimina ~80% das idas ao Redis para hot URLs

# Camada 2: Redis (cache centralizado)
# Estrutura: string simples   short_code → original_url
# TTL: alinhado com expires_at da URL (ou 24h para URLs sem expiração)
# Benefício: ~0.5ms vs ~5ms do banco | hit rate esperado: 95%+

# Camada 3: PostgreSQL (source of truth)
# Acessado apenas em cache miss (~5% dos redirects)
# Com hash index em short_code: ~1-3ms por query

# Fluxo completo do redirect:
# 1. Check local cache → HIT: redirect imediato (0ms overhead)
#                     → MISS: continuar
# 2. Check Redis      → HIT: popular local cache + redirect (~0.5ms)
#                     → MISS: continuar
# 3. Query PostgreSQL → popular Redis + local cache + redirect (~3-5ms)
#                     → NOT FOUND: 404
#                     → EXPIRED: 410 Gone

Hot key problem: uma URL viral pode receber 100k requests/segundo — muito acima da capacidade de uma única shard Redis de processar sem saturar. A solução é o local cache no servidor de aplicação absorver o pico: com 10 servidores de aplicação, cada um cacheando a URL viral localmente, o Redis recebe apenas os cache misses iniciais (um por servidor), não os 100k/s.

Pipeline de analytics assíncrono

O problema fundamental de analytics num URL shortener: você precisa registrar cada click, mas o registro não pode adicionar latência ao redirect. A solução é desacoplar completamente o registro de analytics do caminho de redirect:

# No handler de redirect (síncrono, caminho crítico):
func handleRedirect(shortCode string) http.Response {
    url := getFromCache(shortCode)   // Redis/local cache
    if url == nil {
        url = db.Get(shortCode)      // fallback ao banco
    }
    if url == nil { return 404 }
    if url.IsExpired() { return 410 }

    // Publicar evento de click de forma async (fire-and-forget)
    // A goroutine/thread publica para Kafka sem bloquear o response
    go publishClickEvent(ClickEvent{
        ShortCode: shortCode,
        Timestamp: time.Now(),
        IP:        req.RemoteAddr,
        UserAgent: req.Header.Get("User-Agent"),
        Referrer:  req.Header.Get("Referer"),
    })

    return http.Redirect(url.Original, 302)
    // Total: ~2-5ms no steady state com cache quente
}

# Consumer de Kafka (processo separado, não afeta latência do redirect):
# - Lê eventos de click em batches de 1000 a cada segundo
# - Resolve geolocalização do IP (MaxMind GeoIP2, em memória)
# - Detecta bots (User-Agent parsing + rate limiting heurístico)
# - Escreve em url_clicks (raw) e agrega em url_stats_daily
# - Se o consumer atrasar: Kafka mantém o backlog; analytics ficam atrasados
#   mas nenhum click é perdido (garantia de entrega at-least-once)

# Trade-off central:
# Analytics são eventually consistent (atraso de segundos a minutos)
# Redirect é always consistent e sempre disponível
# Esse trade-off é explícito e correto para o domínio

Expiração de URLs

Há três abordagens para tratar URLs expiradas, com trade-offs distintos:

# Abordagem 1: Verificação no momento do redirect
# → verificar expires_at em toda leitura do banco/cache
# → vantagem: simples, sem background jobs
# → desvantagem: URLs expiradas ficam no banco indefinidamente, desperdiçando storage
#   (mas ao longo de 5 anos: 566 GB raw — gerenciável sem limpeza ativa)

# Abordagem 2: TTL no Redis + soft delete com background job
# → Redis TTL = tempo até expiração → Redis remove automaticamente
# → background job nocturno: DELETE FROM urls WHERE expires_at < NOW()
#   e DELETE FROM url_clicks WHERE short_code IN (expired codes)
# → vantagem: storage se mantém limpo
# → desvantagem: complexidade de um job adicional; race conditions se o job
#   rodar enquanto um redirect está acontecendo (tratar com soft delete + grace period)

# Abordagem 3: Particionamento por data com archive
# → URLs expiradas são movidas para tabela de archive (cold storage)
# → redirect path nunca lê de archive (404 imediato para URLs arquivadas)
# → vantagem: performance do banco principal não degrada com o tempo
# → desvantagem: complexidade de archive pipeline
# → faz sentido apenas para volume muito alto (> 100M URLs criadas/dia)

Custom aliases e colisões

# Criação com alias customizado:
POST /urls
Body: { original_url: "https://...", custom_alias: "black-friday-2024" }

# Validação:
# 1. Alias deve ter 3-50 chars, apenas [a-zA-Z0-9-_]
# 2. Verificar se alias já está em uso:
#    SELECT 1 FROM urls WHERE short_code = :alias LIMIT 1
#    → se existe: 409 Conflict com mensagem clara
#    → se não existe: INSERT com o alias como short_code

# Race condition: dois usuários tentam criar o mesmo alias simultaneamente
# → a UNIQUE constraint em short_code garante que apenas um vai suceder
# → o segundo recebe um erro de constraint violation → retornar 409

# Namespace reservado:
# Certos aliases são reservados para uso interno: "api", "admin", "help"
# → tabela de aliases bloqueados OU prefixo reservado (e.g., __ para internos)
# → verificar no momento da criação antes de tentar inserir

Considerações de segurança

Um URL shortener cria anonimidade para qualquer URL — o que pode ser abusado para distribuir malware, phishing, e spam. Ignorar esse vetor de abuso resulta em bloqueio do domínio por provedores de email e browsers.

# 1. Scanning de URLs na criação
# → integrar com Google Safe Browsing API ou VirusTotal
# → URLs identificadas como maliciosas: rejeitar na criação (422 com razão)
# → URLs já criadas que são depois identificadas: soft-block + notificação

# 2. Rate limiting por IP e por usuário autenticado
# → IP não autenticado: 10 criações/hora (previne abuso anônimo)
# → usuário autenticado: 1000 criações/hora (uso legítimo de API)
# → implementar com Redis + sliding window counter
# → 429 Too Many Requests com Retry-After header

# 3. Detecção de bot no redirect
# → User-Agent + comportamento (muitos clicks em ms)
# → bots não devem ser contabilizados em analytics
# → identificar com heurísticas simples + listas de User-Agents conhecidos de bots

# 4. URL original: sanitização e validação
# → rejeitar javascript:, data:, e outros schemas não-HTTP(S)
# → verificar que o domínio resolve (DNS lookup opcional)
# → limitar tamanho da URL original (ex: 2048 chars)

Arquitetura final

Usuário → CDN (estáticos + UI)
        → Load Balancer
        → App Servers (stateless, autoscalável)
              ↓ redirect hot path (leitura)
              ├── Local Cache (Caffeine/ristretto, top-1000)
              ├── Redis Cluster (short_code → original_url, TTL)
              └── PostgreSQL Primary + 2 Read Replicas
                    (hash index em short_code)

              ↓ analytics (fire-and-forget, fora do hot path)
              └── Kafka (topic: url-clicks, retenção 7 dias)
                    └── Analytics Consumer
                          ├── GeoIP lookup (MaxMind, em memória)
                          ├── Bot detection
                          ├── PostgreSQL: url_clicks (raw, particionado por mês)
                          └── PostgreSQL: url_stats_daily (agregado)

KGS (Key Generation Service):
  → PostgreSQL: codes_available (pré-gerados, 100M códigos = ~700MB)
  → PostgreSQL: codes_used (short_code → url_id)
  → Buffer em memória: 10k códigos pré-carregados para baixa latência

Decisões de engenharia

Perguntas de entrevista

HINCRBY url:clicks:2024-01-01T14:30 "abc1234" 147
EXPIRE  url:clicks:2024-01-01T14:30 3600  # TTL de 1 hora

Exercícios práticos