CS Fundamentals Trainer · Guias

Projetar um encurtador de URLs

Códigos curtos, 301 vs 302, colisões, cache, abuso e contagem de cliques sem deixar o redirect lento.

24 min de leitura

Um encurtador de URLs transforma https://example.com/some/very/long/path?with=parameters em https://sho.rt/Xk3b9Qa e envia os visitantes que abrem o link curto para o longo. É uma pergunta de design de sistemas favorita porque a ideia cabe em uma frase, e ainda assim toca quase tudo: geração de IDs, escolha do banco de dados, cache, semântica do HTTP, abuso e analytics.

1. Delimite o problema

Comece combinando o que o serviço precisa fazer e o que pode deixar de fora.

Depois, as qualidades que decidem o design:

O caminho de escrita pode ser lento e cuidadoso. O caminho de leitura precisa ser rápido e quase sempre no ar. Projete-os separadamente.

2. Contas de padaria

Suponha 100 milhões de novos links por mês e 100 redirects para cada link criado. São números redondos, então podemos conferir cada passo.

GrandezaCálculoResultado
Novos links por segundo100 milhões / (30 × 86 400 s)cerca de 39 por segundo
Redirects por segundo39 × 100cerca de 3 900 por segundo em média
Pico de redirectssuponha 10 × a médiacerca de 39 000 por segundo
Links em 5 anos100 milhões × 12 × 56 bilhões
Armazenamento6 bilhões × cerca de 500 bytes (URL, código, datas, dono)cerca de 3 TB

O que esses números dizem:

Qual deve ser o tamanho do código?

Um código feito dos 62 caracteres 0-9, A-Z e a-z ("base62") tem 62^n possibilidades para n caracteres:

TamanhoCódigos possíveis
662^6 = 56 800 235 584 (cerca de 57 bilhões)
762^7 = 3 521 614 606 208 (cerca de 3,5 trilhões)

Seis bilhões de links cabem em 6 caracteres, com folga. Sete caracteres dão uma margem de segurança de quase 600 vezes, então 7 é a escolha usual. É curto o bastante para digitar e longo o bastante para que adivinhar um código válido seja inútil.

3. As duas operações

Uma API pequena basta:

POST /api/links      { "url": "https://example.com/a/very/long/path", "alias": "optional", "expires_at": "optional" }
                  →  201 { "code": "Xk3b9Qa", "short_url": "https://sho.rt/Xk3b9Qa" }

GET  /Xk3b9Qa     →  redirect to the long URL (or 404 if unknown)

Diagram: Creating a link and following it

301 ou 302?

O código de status do redirect é uma decisão de design de verdade, não um detalhe. Ambos são definidos na RFC 9110, seção 15.4 [1].

Há também o lado dos mecanismos de busca. Um 301 diz aos crawlers que o destino é o endereço real, então links que apontam para a sua URL curta são creditados a ele, e esse é um motivo comum para times de marketing pedirem um 301. Um 302 pode deixar a URL curta no índice por um tempo. O Google diz que redirects não perdem sinais de ranqueamento [7], então isso é um ponto a favor do 301 e não um desastre para o 302.

Se você oferece estatísticas, edição ou expiração, use um redirect temporário. Escolha 301 apenas para links realmente permanentes e nos quais você não conta cliques. Mesmo assim, lembre-se de que um 301 em cache é muito difícil de desfazer.

4. Gerando o código

Esta é a parte em que entrevistadores gostam de cavar. Há quatro formas comuns, cada uma com uma pegadinha.

AbordagemComo funcionaPegadinha
Hash e corteCalcular o hash da URL longa (MD5, SHA-256), manter os 7 primeiros caracteres em base62URLs diferentes podem colidir depois do corte, então você precisa verificar e tentar de novo. A mesma URL sempre dá o mesmo código, o que é bom para deduplicação e ruim quando dois usuários querem estatísticas separadas
Código aleatórioSortear 7 caracteres base62 aleatóriosColisões são raras, mas reais. Você precisa de uma verificação de unicidade, que o banco de dados faz de graça
Contador, depois base62Pegar o próximo número de um contador e escrevê-lo em base62Nenhuma colisão, mas os códigos são adivinháveis e enumeráveis (1, 2, 3...), e o contador é um recurso compartilhado
IDs no estilo SnowflakeUm número de 64 bits composto por um timestamp, um número de máquina e uma sequência por milissegundo, depois escrito em base62Sem coordenação e sem colisões, mas o código tem 10 ou 11 caracteres e é aproximadamente ordenado no tempo, então não é nem curto nem secreto
Faixas de chaves pré-fabricadasUm serviço de chaves entrega a cada servidor de aplicação um bloco de números (digamos, 1 000 000 de cada vez) para gastar localmenteRápido e sem colisões, mas ainda sequencial a menos que você embaralhe os números. A queda de um servidor desperdiça o resto do seu bloco, o que não importa: temos trilhões

Uma escolha simples e sólida para uma primeira versão são códigos aleatórios com uma chave única no banco de dados. Deixe o banco de dados ser o juiz da unicidade.

Com que frequência códigos aleatórios colidem?

Se já existem N códigos armazenados entre os 62^7 possíveis, um novo código aleatório acerta um existente com probabilidade N / 62^7. Com 6 bilhões de links armazenados:

6 000 000 000 / 3 521 614 606 208 ≈ 0.0017  (about 0.17 %)

Cerca de um insert em 600 precisa de uma segunda tentativa bem no final dos cinco anos, e quase nenhum no começo. Então a regra é simples: tente o insert e, se o código já existir, sorteie outro. Depois de algumas tentativas falhas, desista com um erro (ou passe a um código mais longo). Esse é o problema do aniversário numa forma amigável: ele só pesa quando você compara muitos códigos entre si, não quando cada novo código encontra uma tabela que já existe [2].

import secrets

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"


def random_code(length=7):
    # secrets (not random) so that codes cannot be predicted
    return "".join(secrets.choice(ALPHABET) for _ in range(length))


def create_link(db, long_url):
    for _ in range(5):
        code = random_code()
        row = db.execute(
            "INSERT INTO links (code, long_url) VALUES (%s, %s) "
            "ON CONFLICT (code) DO NOTHING RETURNING code",
            (code, long_url),
        ).fetchone()
        if row:                      # the code was free and is now ours
            return code
    raise RuntimeError("could not find a free code")

A chave única faz da verificação e do insert um único passo: a chave primária garante que apenas um de dois inserts do mesmo código pode ter sucesso, e ON CONFLICT DO NOTHING transforma o perdedor em um resultado vazio em vez de um erro. RETURNING devolve apenas as linhas realmente inseridas [3], então um resultado vazio significa "tente outro código". Verificar com um SELECT antes e inserir depois deixaria uma brecha entre as duas instruções por onde duas requisições podem passar.

Contadores e base62

Se você prefere números, precisa escrevê-los em base62. Esta é a conversão em quatro linguagens (escolha uma linguagem nas abas; sua escolha é lembrada):

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"


def encode(n):
    if n == 0:
        return ALPHABET[0]
    digits = []
    while n:
        n, rest = divmod(n, 62)
        digits.append(ALPHABET[rest])
    return "".join(reversed(digits))
const alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

func Encode(n uint64) string {
	if n == 0 {
		return string(alphabet[0])
	}
	var buf [11]byte // the largest uint64 needs 11 base62 digits
	i := len(buf)
	for n > 0 {
		i--
		buf[i] = alphabet[n%62]
		n /= 62
	}
	return string(buf[i:])
}
const ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

// n is a BigInt, so ids above 2^53 stay exact
function encode(n) {
  if (n === 0n) return ALPHABET[0];
  let out = "";
  while (n > 0n) {
    out = ALPHABET[Number(n % 62n)] + out;
    n /= 62n;
  }
  return out;
}
public static string Encode(ulong n)
{
    const string alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    if (n == 0) return alphabet[0].ToString();
    var chars = new char[11];            // the largest ulong needs 11 base62 digits
    int i = chars.Length;
    while (n > 0)
    {
        chars[--i] = alphabet[(int)(n % 62)];
        n /= 62;
    }
    return new string(chars, i, chars.Length - i);
}

Alguns valores para conferir uma implementação: encode(0) é 0, encode(61) é z, encode(62) é 10 e encode(62^7 - 1) é zzzzzzz.

Um contador simples dá 1, 2, 3: qualquer um pode percorrer todos os seus links. Se os links não devem ser adivinháveis, use códigos aleatórios ou embaralhe o número antes com uma mistura reversível (multiplique por um número ímpar grande que não tenha fator em comum com 62^7, módulo 62^7). Não use "segurança por obscuridade" para conteúdo realmente privado: um encurtador não é um sistema de controle de acesso. Coloque segredos de verdade atrás de um login.

IDs no estilo Snowflake

Sistemas que precisam distribuir ids únicos a partir de muitas máquinas sem um contador compartilhado costumam usar o layout Snowflake, que o Twitter popularizou [6]. Um número de 64 bits é cortado em três partes: 41 bits de milissegundos desde uma data de início à sua escolha (cerca de 69 anos), 10 bits para a máquina (1 024 máquinas) e 12 bits para um número de sequência (4 096 ids por milissegundo por máquina). Cada máquina pode gerar ids por conta própria, os ids crescem com o tempo e nunca colidem, desde que duas máquinas não compartilhem um número e nenhum relógio volte para trás.

import threading
import time

EPOCH_MS = 1_700_000_000_000          # your own start date, so the 41 bits last longer


class Snowflake:
    def __init__(self, machine_id):
        assert 0 <= machine_id < 1024
        self.machine_id = machine_id
        self.last_ms = -1
        self.seq = 0
        self.lock = threading.Lock()

    def next(self):
        with self.lock:
            now = int(time.time() * 1000)
            if now < self.last_ms:
                raise RuntimeError("the clock went backwards")   # refuse rather than risk a duplicate
            if now == self.last_ms:
                self.seq = (self.seq + 1) & 4095
                if self.seq == 0:                                # 4 096 ids this millisecond: wait
                    while now <= self.last_ms:
                        now = int(time.time() * 1000)
            else:
                self.seq = 0
            self.last_ms = now
            return ((now - EPOCH_MS) << 22) | (self.machine_id << 12) | self.seq

Para um encurtador, essa é a ferramenta errada, por dois motivos. O número é grande, então sua forma em base62 tem 10 ou 11 caracteres em vez de 7, o que é longo para um link "curto". E ele começa com um timestamp, então qualquer um pode saber quando um link foi criado e adivinhar seus vizinhos. Use-o onde ids únicos importam mais que curtos ou secretos (por exemplo, a chave primária interna de um link ou de um clique), e mantenha o código público separado. O mesmo vale para UUIDs e ULIDs: únicos, mas longos demais.

Aliases personalizados

Para sho.rt/summer-sale, aceite o texto do usuário, mas trate-o como qualquer outro código: a mesma chave única, o mesmo insert atômico e uma resposta clara de "esse nome já está em uso" no conflito. Restrinja os caracteres e o tamanho permitidos e mantenha uma lista de palavras reservadas (api, admin, login, static...) para que um usuário não possa sombrear as suas próprias rotas.

5. Onde os dados vivem

Uma tabela basta:

CREATE TABLE links (
  code        text PRIMARY KEY,                  -- the unique key is also the index we read by
  long_url    text NOT NULL,
  owner_id    bigint,                            -- null for anonymous links
  created_at  timestamptz NOT NULL DEFAULT now(),
  expires_at  timestamptz                        -- null means never
);

A única consulta no caminho quente é "me dê a linha deste código", uma busca pela chave primária. Isso serve a qualquer banco relacional e serve igualmente a bancos chave-valor (DynamoDB, Cassandra, Redis), porque não há joins nem consultas por intervalo. Ambas são respostas válidas. Os motivos honestos para escolher:

Códigos diferenciam maiúsculas de minúsculas: confira a collation

Xk3b9Qa e xk3b9qa são códigos diferentes em base62, e o banco de dados precisa concordar. O PostgreSQL compara text exatamente por padrão, então a tabela acima está correta nele. MySQL e SQL Server usam collations que ignoram a caixa por padrão, então os dois códigos contariam como a mesma chave: as buscas encontrariam a linha errada, e a chave única rejeitaria códigos que na verdade estão livres. No MySQL, declare a coluna com uma collation binária (code VARCHAR(11) CHARACTER SET ascii COLLATE ascii_bin). Em qualquer banco, escreva um teste que armazene aB e Ab e espere duas linhas.

Se o seu armazenamento ignora a caixa e você não pode mudá-lo, use um alfabeto sem maiúsculas (36 caracteres: 0-9a-z). Então 36^7 é só 78 bilhões, o que tornaria as colisões comuns com 6 bilhões de links (cerca de 8 %), então passe para 8 caracteres (2,8 trilhões).

Quando um banco de dados não basta

Leituras são fáceis de escalar: adicione réplicas e coloque um cache na frente (próxima seção). Se as escritas ou o armazenamento superarem uma máquina, divida a tabela pelo código. Como as buscas sempre chegam com o código completo, você pode fazer sharding por um hash do código, e cada requisição vai a exatamente um shard. Use consistent hashing para que adicionar um shard mova apenas uma pequena parte dos dados.

6. Tornando os redirects rápidos

Um redirect é a leitura de um valor pequeno por chave, repetida para os mesmos links populares sem parar. Esse é o caso ideal para um cache.

Diagram: The redirect path, from fastest to slowest

Conferência aproximada: se o cache responde a 95 % das 39 000 requisições por segundo de pico, o banco de dados vê cerca de 2 000 por segundo. Uma única busca por chave primária é barata, então um servidor de banco modesto (ou algumas réplicas) dá conta.

7. Expiração, exclusão e códigos que voltam

8. Abuso e segurança

Um encurtador é uma ferramenta perfeita para esconder um link malicioso, então a segurança faz parte do design, não é um extra.

9. Contando cliques sem deixar o redirect lento

Se você quer estatísticas, o redirect não deve esperar por elas. Em vez de atualizar um contador no banco de dados a cada clique (uma escrita no caminho mais quente), coloque um pequeno evento em uma fila e responda ao visitante imediatamente:

Diagram: Clicks are counted after the visitor has left

Workers somam os eventos em lotes (contagens por código por hora), e o painel lê os totais. Se a fila ficar fora do ar por um momento, você perde algumas contagens e nenhum redirect. Essa é a troca certa para este recurso. Conte de forma aproximada e barata; não faça o produto depender da sua analytics.

Espere que boa parte do tráfego sejam máquinas. Crawlers, scanners de segurança e os buscadores de prévia de links de apps de chat e redes sociais (eles abrem um link no instante em que alguém o cola) seguem links curtos, e um navegador pode fazer prefetch de um. Registre o User-Agent e se a requisição foi um GET ou HEAD, filtre bots conhecidos no worker, não no caminho quente, e relate os "cliques humanos" separadamente de "todas as requisições". Senão, a primeira mensagem que você compartilha parece um link viral.

10. Testes, monitoramento e confiabilidade

Testes que valem a pena escrever

O que acompanhar

SinalPor quê
Latência do redirect (p50, p99) e taxa de erroO produto é o redirect. Alerte no p99, não na média
Taxa de acerto do cacheUma queda significa que um deploy mudou as chaves, ou que um scan está em andamento
Proporção de 404sUm aumento é um scanner ou bot sondando códigos
Retries de criação (colisões) por 1 000 criaçõesA proporção é cerca de N / 62^7, então um aumento é sinal de que o espaço está enchendo ou de que o gerador é enviesado
Atraso da fila de cliquesAs contagens atrasam, nunca o redirect
Disco usado, por réplicaO crescimento é constante, então alerte cedo
Links sinalizados e desativadosQuão bem o processo de abuso funciona

O que acontece quando algo falha

11. Perguntas que entrevistadores gostam de acrescentar

"E se dois usuários encurtarem a mesma URL?"

Ambos os designs são válidos. Dê a cada usuário seu próprio código (simples, e eles recebem estatísticas separadas), ou deduplique calculando o hash da URL e devolvendo o código existente (economiza espaço, mas estatísticas e propriedade ficam embaraçadas). Diga qual você escolheu e por quê.

Um código que recebe uma enorme parcela do tráfego é uma hot key. Uma CDN ou um cache em processo em cada servidor de aplicação o absorve, porque o valor é minúsculo e raramente muda. Nenhum shard deveria ser consultado pela mesma linha 50 000 vezes por segundo.

"O que acontece quando o cache está vazio depois de uma reinicialização?"

Todo o tráfego atinge o banco de dados de uma vez. Aqueça o cache primeiro com os links mais clicados, ou deixe a primeira requisição de cada código preenchê-lo, e garanta que apenas uma requisição por código vá ao banco de dados por vez (veja a seção sobre stampede no guia de cache).

"Como você faria funcionar em várias regiões?"

Leituras são fáceis de replicar: coloque réplicas de leitura e caches perto dos visitantes. As escritas podem ir a uma região, já que são só cerca de 39 por segundo. Links recém-criados precisam de um instante para aparecer em outras regiões, então é comum servir o criador a partir da região de escrita, ou recorrer ao primário quando uma réplica diz "não encontrado".

12. Coisas a mencionar em uma entrevista

Resumo rápido

  1. Leituras são cerca de 100 vezes mais comuns que escritas, então otimize o caminho do redirect.
  2. Um código base62 de 7 caracteres dá 3,5 trilhões de possibilidades: suficiente por anos.
  3. Use um redirect temporário (302 ou 307) se você conta cliques ou permite edições.
  4. Códigos aleatórios com uma chave única e um INSERT ... ON CONFLICT atômico são simples e seguros; contadores não têm colisões, mas são adivinháveis.
  5. Uma tabela com chave pelo código basta. Faça cache dela, replique-a e faça sharding por código só quando for preciso.
  6. Valide URLs, aplique rate limit na criação e mantenha uma chave de emergência para desativar links.
  7. Conte cliques de forma assíncrona.

Fontes

  1. IETF, RFC 9110, section 15.4: Redirection 3xx. O significado de 301, 302, 307 e 308, e quais podem ser colocados em cache.
  2. Wikipedia, Birthday problem. Por que as colisões aparecem antes do que a intuição diz quando os códigos são comparados entre si.
  3. Documentação do PostgreSQL, INSERT: the ON CONFLICT clause. DO NOTHING, e RETURNING devolvendo apenas as linhas realmente inseridas.
  4. OWASP, Unvalidated Redirects and Forwards Cheat Sheet.
  5. Documentação do Redis, Key eviction. Least-recently-used e outras políticas para o cache de redirects.
  6. Wikipedia, Snowflake ID. O layout de 41/10/12 bits.
  7. Google Search Central, Redirects and Google Search. Como os crawlers tratam redirects permanentes e temporários.

Pratique este tema: System Design System Design › Case studies

Mais guias