Encurtador de URLs

"Projete um encurtador de URLs como o bit.ly ou o TinyURL: o usuário envia uma URL longa e recebe uma curta; quem abrir a URL curta é redirecionado para a original."

O encurtador de URLs é o "hello world" das entrevistas de system design, e costuma ser o primeiro problema de um júnior ou o aquecimento numa rodada sênior. Parece trivial — uma consulta chave-valor — e essa é justamente a armadilha: o entrevistador quer ver se você conduz a conversa (requisitos, números, API, dados, design, aprofundamentos) em vez de pular direto para "usa um hash". Ele exercita três ideias que você vai reutilizar em quase todos os outros casos: geração de IDs únicos, cache para leitura intensa e tirar o trabalho secundário (analytics) do caminho crítico.

O BoxOffice também usa um: o SMS "seus ingressos para sábado" traz um link curto como https://bx.example/aB3x9Kq, porque um SMS tem 160 caracteres e uma URL de ingresso assinada tem 300.

1. Esclarecer os requisitos

Mesmo num problema "simples", gaste 3–5 minutos aqui (roteiro de entrevista). Os requisitos decidem se os códigos podem ser previsíveis, se o analytics precisa ser exato e se a mesma URL longa sempre recebe o mesmo código.

Requisitos funcionais

1. Encurtar: dada uma URL longa, devolver uma URL curta com um código único (ex.: 7 caracteres).
2. Redirecionar: GET /{code} manda o navegador para a URL longa.
3. Alias personalizado (opcional): o usuário escolhe o código (/boxoffice-rock-in-rio).
4. Expiração (opcional): links podem expirar numa data.
5. Estatísticas de cliques: número de cliques por link, por dia, por país.

Requisitos não funcionais

Fora do escopo (diga explicitamente)

Contas de usuário e interface de edição de links, cobrança, geração de QR code, testes A/B de destinos. São funcionalidades em cima do mesmo núcleo.

2. Estimativas de guardanapo (back-of-the-envelope)

Declare as premissas e depois calcule. Todos os números são ilustrativos — abra a aba Source, mude um e recalcule.

# URL shortener: assumptions (illustrative)
new_per_month = 100_000_000   # new short links per month
read_write    = 100           # redirects per created link
peak_factor   = 3             # peak / average traffic
years         = 5             # retention
record_b      = 500           # code + long URL + metadata, bytes
hot_fraction  = 0.2           # share of a day's redirects worth caching (80/20 rule)
click_b       = 200           # one click event (code, time, country, referrer)

write_qps  = new_per_month / (30 * 86_400)
read_qps   = write_qps * read_write
peak_read  = read_qps * peak_factor
records    = new_per_month * 12 * years
storage_tb = records * record_b / 1e12
codes_7    = 62 ** 7
used_pct   = records / codes_7 * 100
cache_gb   = read_qps * 86_400 * hot_fraction * record_b / 1e9
clicks_gb  = read_qps * 86_400 * click_b / 1e9

rows = [
    ("write_qps", write_qps, "req/s"), ("read_qps", read_qps, "req/s"),
    ("peak_read", peak_read, "req/s"), ("records", records, "links"),
    ("storage_tb", storage_tb, "TB"), ("codes_7", codes_7, "codes"),
    ("used_pct", used_pct, "%"), ("cache_gb", cache_gb, "GB"),
    ("clicks_gb", clicks_gb, "GB/day"),
]
print("| quantity | value | unit |\n|---|---:|---|")
for name, value, unit in rows:
    v = f"{value:,.0f}" if abs(value) >= 100 else f"{value:,.2f}"
    print(f"| `{name}` | {v} | {unit} |")

O que os números dizem:

• ~40 escritas/s e ~4 mil redirecionamentos/s (pico ~12 mil/s): um único banco aguentaria as escritas; é para as leituras que projetamos. ⇒ cache na frente do armazenamento, servidores de aplicação sem estado atrás de um balanceador de carga.
• 6 bilhões de links, ~3 TB em 5 anos: é demais para ficar confortável num nó só com réplicas e índices, e trivial para um armazenamento chave-valor particionado. O padrão de acesso é uma consulta por chave única, então um banco KV (DynamoDB, Cassandra) ou uma tabela SQL fragmentada funcionam.
• 7 caracteres base62 = 3,5 trilhões de códigos; usamos 0,17% deles em 5 anos. Códigos curtos não são o recurso escasso — unicidade sem coordenação é o problema de design.
• O conjunto quente tem ~33 GB: cabe na RAM de um ou dois nós de cache. Com popularidade do tipo Zipf (poucos links recebem a maioria dos cliques), a taxa de acerto será alta.
• Os eventos de clique somam ~67 GB/dia — mais do que os próprios links. ⇒ eles vão para um stream e um armazenamento de analytics, nunca para a tabela principal.

3. API

POST /v1/urls                          → 201 {code, shortUrl, expiresAt}
     {"longUrl": "https://boxoffice.example/events/42?utm_source=sms",
      "customAlias": null, "expiresAt": "2027-12-31T23:59:59Z"}
     (409 ALIAS_TAKEN, 422 INVALID_URL, 429 TOO_MANY_REQUESTS)

GET  /{code}                           → 302 Found, Location: <longUrl>
                                         (404 not found, 410 Gone when expired)

GET  /v1/urls/{code}/stats?from=…&to=… → 200 {clicks, byDay[], byCountry[]}
DELETE /v1/urls/{code}                 → 204   (owner only)

• A criação é autenticada (chave de API ou token de usuário) e tem rate limit por cliente — encurtadores são uma ferramenta favorita de spammers.
• O redirecionamento é público e faz uma coisa só: consultar e responder. Todo o resto (contagem, geolocalização, detecção de bots) acontece de forma assíncrona.

4. Modelo de dados

O padrão de acesso central é code → longUrl, uma consulta pontual pela chave primária, milhares de vezes por segundo, sobre bilhões de linhas. Sem joins, sem varreduras por faixa.

-- Logical model (a KV/wide-column table, or a sharded SQL table)
CREATE TABLE short_url (
    code        VARCHAR(16) PRIMARY KEY,   -- partition key
    long_url    TEXT        NOT NULL,
    owner_id    BIGINT,
    created_at  TIMESTAMP   NOT NULL,
    expires_at  TIMESTAMP
);

-- Only for the counter-based generator: one row per range allocation
CREATE TABLE id_range (
    name        VARCHAR(32) PRIMARY KEY,   -- 'short_url'
    next_start  BIGINT      NOT NULL
);

5. Design de alto nível

flowchart LR
    u([Navegador / app]) --> dns["DNS"]
    dns --> lb["Balanceador de carga"]
    lb --> app["App encurtador<br/>(sem estado, N réplicas)"]
    app --> cache[("Cache<br/>códigos quentes")]
    app --> db[("NoSQL<br/>code → long_url")]
    app --> ids["Alocador de IDs<br/>(faixas)"]
    app -. evento de clique .-> k[["Kafka<br/>cliques"]]
    k --> agg["Workers de analytics<br/>agregam"]
    agg --> dwh[("Armazenamento de analytics")]

O caminho de escrita pede um código ao alocador de IDs (de uma faixa já reservada em memória — na maioria das vezes sem chamada de rede), grava a linha e devolve a URL curta. O caminho de leitura está abaixo; repare que o evento de clique é disparado depois da resposta e nunca espera.

sequenceDiagram
    autonumber
    participant B as Navegador
    participant A as App encurtador
    participant C as Cache
    participant D as NoSQL
    participant K as Kafka
    B->>A: GET /aB3x9Kq
    A->>C: GET url:aB3x9Kq
    alt acerto no cache (a maioria)
        C-->>A: long_url
    else falta no cache
        C-->>A: nil
        A->>D: get(code = aB3x9Kq)
        D-->>A: long_url, expires_at
        A->>C: SET url:aB3x9Kq long_url EX 86400
    end
    A-->>B: 302 Location: long_url
    A-)K: clique {code, ts, ip, user-agent}

6. Aprofundamentos (deep dives)

6.1 Gerando o código

Este é o aprofundamento que todo entrevistador espera. Quatro famílias, cada uma com um trade-off diferente:

UPDATE id_range SET next_start = next_start + 10000
 WHERE name = 'short_url'
RETURNING next_start - 10000 AS block_start;

A codificação base62 em si são poucas linhas:

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base62(n: int) -> str:
    s = ""
    while n > 0:
        n, r = divmod(n, 62)
        s = ALPHABET[r] + s
    return s or "0"

# 62**7 = 3_521_614_606_208 codes; base62(3_521_614_606_207) == "ZZZZZZZ"

Recomendação para a entrevista: contador com alocação por faixas + embaralhamento para códigos gerados; uma inserção condicional (IF NOT EXISTS) para aliases personalizados. Cite o hash e por que você não o escolheu (colisões, estatísticas compartilhadas).

6.2 O redirecionamento: 301 ou 302, e o cache

A maioria dos encurtadores comerciais responde 302 (ou 301 com um Cache-Control: max-age curto) porque o analytics e a capacidade de desativar um link malicioso fazem parte do produto. Seja qual for a escolha, diga por quê (semântica HTTP).

Cache da consulta (cache-aside):

• Cache-aside com TTL de horas: o mapeamento quase nunca muda, então dados desatualizados não são problema; ao apagar ou expirar, remova a chave explicitamente.
• Cache negativo: guarde "não encontrado" por pouco tempo (url:zzzzzzz → ∅, 60 s); senão um bot varrendo códigos aleatórios vai direto ao banco.
• Popularidade Zipf: um link viral pode receber milhares de cliques por segundo — uma chave quente num shard do cache. Mitigue com um pequeno cache em processo (L1, alguns segundos) em cada servidor de aplicação, na frente do cache compartilhado.
• Expiração: verifique expires_at em toda leitura (guardado no cache junto com a URL) e responda 410 Gone; um job em segundo plano apaga as linhas expiradas depois.

6.3 Analytics de cliques fora do caminho crítico

Contar cliques de forma síncrona (UPDATE stats SET clicks = clicks + 1) transformaria cada leitura numa escrita sobre uma linha quente. Em vez disso:

flowchart LR
    app["App encurtador"] -->|"dispara e esquece<br/>evento de clique"| k[["Tópico Kafka clicks<br/>particionado por code"]]
    k --> s["Agregação em stream<br/>janelas de 1 min"]
    s --> olap[("Armazenamento de analytics<br/>cliques por código/dia/país")]
    k --> lake[("Object store<br/>eventos brutos")]
    olap --> api["GET /stats"]

• O app produz o evento depois de responder (ou acumula em memória e envia em lotes): o redirecionamento não depende do Kafka estar saudável. Se o Kafka cair, descarte ou acumule — o analytics pode perder alguns eventos; os redirecionamentos não podem falhar (semântica de mensageria).
• Um job de stream agrega por código por minuto e grava contadores num armazenamento de analytics; os eventos brutos vão para o object storage para análises posteriores.
• Visitantes únicos exigem uma contagem distinta: use HyperLogLog (≈1–2% de erro, alguns kB por contador) em vez de guardar cada ID de visitante.

7. Gargalos, modos de falha e trade-offs

Os trade-offs para dizer em voz alta: disponibilidade e latência acima de consistência estrita no caminho de redirecionamento (um link apagado há poucos segundos ainda pode redirecionar pelo cache), 302 em vez de 301 porque analytics e controle importam, e faixas de contador em vez de hash porque unicidade sem repetição por colisão é mais simples de raciocinar.

8. Experimente no playground

O cenário url-shortener tem o caminho de leitura desta página: balanceador de carga, réplicas do app, um cache na frente do armazenamento e um stream de eventos para os cliques.

Abrir o playground completo

9. Perguntas de follow-up que o entrevistador faz

10. Rubrica de autoavaliação

Relacionados: Caching, Hands-on 5 (cache-aside e taxa de acerto), Mensageria, problemas de prática para entrevista.

Como se conecta

Quais aulas este caso testa? Cada ramo é uma aula cujas ideias o design usa (azul), com os componentes da paleta em que elas aparecem (verde):

flowchart LR
    CASE(["URL shortener"]) --> EST["Estimation<br/>reads ≫ writes, hot set"]:::tech
    CASE --> DIS["Distributed<br/>unique IDs: ranges, Snowflake"]:::tech
    CASE --> EDG["Edge<br/>DNS, LB, 301 vs 302"]:::tech
    CASE --> DB["Databases<br/>key-value: code → long URL"]:::tech
    CASE --> CAC["Caching<br/>cache-aside for hot codes"]:::tech
    CASE --> MSG["Messaging<br/>clicks as events"]:::tech
    EDG -.-> k1["dns · lb · app"]:::comp
    DB -.-> k2["nosql"]:::comp
    CAC -.-> k3["cache"]:::comp
    MSG -.-> k4["kafka · analytics"]:::comp
    classDef comp fill:#1e9e5a22,stroke:#1e9e5a
    classDef tech fill:#2f6fed22,stroke:#2f6fed

Aulas que ele testa: Estimativas — números · Distribuídos — tempo e relógios (IDs únicos) · Borda — protocolos (redirecionamentos) · Bancos de dados — modelos · Caching — padrões · Mensageria — semântica. Componentes da paleta: dns · lb · app · cache · nosql · kafka · analytics · dwh. Cenários: url-shortener, read-heavy-cache.

Referências

• XU, A. System Design Interview — An Insider's Guide, vol. 1, cap. 7 "Design a Unique ID Generator in Distributed Systems" e cap. 8 "Design a URL Shortener"¹.
• O anúncio e o código do Snowflake do Twitter².
• Semântica dos redirecionamentos HTTP (301, 302, 307, 308)³.
• KLEPPMANN, M.; RICCOMINI, C. Designing Data-Intensive Applications, 2ª ed., capítulos sobre particionamento e processamento de streams⁴.