Case: URL shortener
- ⬜🧮 Back-of-envelope: cálculos que convencem(System Design Interview Prep)
Recomendamos completar os pré-requisitos antes de seguir, mas nada te impede de continuar.
Por que essa pergunta é quase universal em entrevista
URL shortener é a questão canônica de System Design porque toca em todos os trade-offs essenciais em 45 minutos: geração de ID única em escala, read-heavy caching, counter distribuído, analytics assíncrona. Se você domina isso, Twitter feed e Instagram também caem.
O teste não é se você "sabe fazer" — é se você consegue defender decisões quando o entrevistador aumenta escala progressivamente: "e se forem 100M URLs? 1B? 10B?"
Passo 1: estabelecer escala (back-of-envelope)
Sempre começa com premissas. Nunca pule. Premissas típicas:
- 100M URLs criadas/mês (~40/s média, ~120/s pico)
- Razão read:write 100:1 — cada URL criada é clicada 100x
- ~10k QPS de redirect médio, ~30k pico
- Retenção 5 anos = 6B URLs totais
- Short code 7 chars base62 = 62⁷ ≈ 3.5 trilhões (espaço largo pra 6B)
Passo 2: geração de short code — 3 estratégias
📋 Como gerar short codes únicos em escala?
Garante unicidade sem colisão, sem round-trip extra pra checar DB. Counter pode ser auto_increment (até 5k/s) ou Snowflake/Redis batched (milhões/s).
Alt: Hash(long_url) truncado (MD5 → 7 chars) — risco colisão 1/62⁷, precisa checar. Problema: mesmo URL gera mesmo short (user quer controlar)
Alt: Random 7 chars base62 — simples, mas precisa checar colisão em DB antes de inserir. ~1% collision rate após 300M URLs
Alt: Pre-generated batch (10B códigos pré-gerados, pick sequencial) — usado por Bit.ly. Zero latência. Complicado de operar
- Fora da AWS
- Conceito de arquitetura
- IA e machine learning
- Banco de dados
- Segurança e identidade
- Rede e entrega
A pergunta que separa candidato preparado: como você trata colisão? A resposta que impressiona empurra a decisão para a restrição de unicidade do banco, em vez de verificar-e-inserir na aplicação — que parece funcionar e falha sob concorrência.
- 1 · A escolha do código é a decisão de projeto. Ela define se dá para enumerar os links dos outros, quantas colisões você trata e se o mesmo endereço gera sempre o mesmo código.
- 2 · Sequencial é curto e enumerável. Converter um contador para uma base maior dá o código mais curto possível — e permite que qualquer um percorra os links alheios incrementando. É problema de privacidade, não de tamanho.
- 3 · Aleatório resolve isso e cobra verificação. Com espaço grande a colisão é rara, mas "rara" não é "impossível": ainda é preciso detectar. Quem detecta bem é a restrição de unicidade no banco.
- 4 · Verificar-e-inserir é uma corrida; a restrição não é. Consultar se existe e depois inserir permite que duas requisições passem entre os dois passos. A chave única no banco arbitra sem corrida.
- 5 · A leitura domina, e é por isso que o cache resolve. Centenas de leituras por escrita, com forte concentração em poucos links. Cache com expiração absorve quase tudo.
- 6 · O tipo de redirecionamento é decisão de produto. Permanente é cacheado pelo navegador e some da sua contagem de cliques. Temporário passa por você toda vez — mais métrica, mais custo.
Passo 3: storage — schema e escolha de DB
-- Postgres / MySQL — serve confortavelmente até ~1B rows
CREATE TABLE short_urls (
short_code VARCHAR(7) PRIMARY KEY, -- PK compacta, index clustered
long_url TEXT NOT NULL,
user_id BIGINT,
created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
expires_at TIMESTAMPTZ, -- opcional; TTL
click_count BIGINT DEFAULT 0, -- updated async
last_clicked TIMESTAMPTZ
);
CREATE INDEX idx_short_urls_user ON short_urls (user_id, created_at DESC);
CREATE INDEX idx_short_urls_expires ON short_urls (expires_at) WHERE expires_at IS NOT NULL;| Escala | DB sugerido | Por quê |
|---|---|---|
| < 100M URLs | Postgres single primary + read replica | Simples, transacional, aguenta até ~5k write/s |
| 100M-1B | Postgres com table partitioning por mês | Partition pruning acelera queries; drop partition é limpeza instantânea |
| 1B-10B | Cassandra ou Vitess (MySQL sharded) | Escala linear em writes; consistente com quórum |
| > 10B | DynamoDB (key-value) + CDC pra analytics | Escala horizontal sem ops de sharding; custo justifica em escala |
Passo 4: caching — onde está o leverage
Com 100:1 read:write e power law no tráfego (poucas URLs dominam), cache em frente ao DB é decisão óbvia. Sem cache: 10k QPS no DB — viável mas caro. Com cache: 10k QPS no Redis, 50-500 QPS no DB.
# Redis cache-aside pattern
def resolve(short_code: str) -> str | None:
cached = redis.get(f"url:{short_code}")
if cached:
return cached
row = db.query("SELECT long_url FROM short_urls WHERE short_code = %s", short_code)
if not row:
return None
redis.setex(f"url:{short_code}", 86400, row.long_url) # TTL 1 dia
return row.long_urlTTL matters: sem TTL, cache cresce infinitamente. Com TTL de 1 dia + LRU eviction, Redis de 16GB cabe ~16M URLs hot. Power law garante hit rate > 95%.
Qual estratégia de geração de código curto evita colisão sem consultar o banco a cada tentativa?
Passo 5: analytics de cliques — fire and forget
async def redirect_handler(short_code: str, request):
long_url = await resolve(short_code)
if not long_url:
return Response(status=404)
# Fire-and-forget
asyncio.create_task(emit_click_event({
"short_code": short_code,
"ts": time.time(),
"ip": request.headers.get("X-Forwarded-For"),
"ua": request.headers.get("User-Agent"),
"referer": request.headers.get("Referer"),
}))
return RedirectResponse(long_url, status_code=301)
async def emit_click_event(event: dict):
await kafka_producer.send("url.click", event)
# Worker offline enriquece (geo via IP), grava em BigQuery/SnowflakePasso 6: o que entrevistador aumenta progressivamente
| Pergunta | Resposta esperada |
|---|---|
| "E se forem 100B URLs?" | Sharding por hash(short_code). 100+ shards. Consistent hashing para rebalance. DynamoDB ou Cassandra. |
| "E se quiser custom alias?" | Nova tabela custom_aliases (code → url), lookup primeiro em custom depois em generated. Validação contra palavrões. |
| "E se URL tiver malware?" | Scan async (Google Safe Browsing) no write. Bloom filter na hot path para known-bad. Quarantine queue. |
| "E se DB cair?" | Read replica pra redirect (read-only degrade), fila pra writes (Kafka buffer), graceful degrade. RTO/RPO definidos. |
Armadilhas que eliminam candidato
Seis erros que eliminam candidato nessa pergunta. (1) Sair escrevendo código antes de estabelecer escala — sem QPS de leitura, QPS de escrita e storage por ano, nenhuma decisão é defensável. (2) Gerar o short code com hash truncado do URL e não dizer o que faz na colisão. (3) Propor auto-increment global como gerador — é ponto único de contenção e produz ID sequencial, o que permite enumerar links privados de terceiros. (4) Desenhar para escrita quando a razão é ~100:1 de leitura — o sistema é um cache com um banco atrás, não o contrário. (5) Dizer "uso Redis" e parar aí, sem política de eviction, TTL e o que acontece no cache miss simultâneo (stampede). (6) Colocar analytics de clique no caminho crítico do redirect — se o pipeline de métrica cai, o produto inteiro cai; é fire and forget por definição.
Take-aways
URL shortener é canônica porque a resposta sênior mostra 4 habilidades simultaneamente: (1) quantificar com back-of-envelope, (2) escolher geração de ID correta, (3) isolar hot path (redirect) de cold path (analytics), (4) adicionar cache onde há power law.
Perguntas frequentes
❓ Contador ou hash para gerar o código curto?
❓ Onde está o gargalo de um encurtador?
❓ Como lidar com link personalizado e expiração?
Fixando
Qual característica do padrão de acesso domina o projeto desse sistema?
Por que o redirecionamento permanente versus temporário é uma decisão relevante aqui?
Terminou de ler?
Marcar como concluído registra o XP, mantém sua sequência e coloca 3 cartas deste módulo na fila de revisão espaçada.
Próximos passos sugeridos
Temas deste módulo
Discussão
Carregando comentários…