Projetando um encurtador de URL: o código curto é a parte fácil

Peça a qualquer pessoa para projetar um encurtador de URL e a primeira resposta chega em segundos: guardar code → url, buscar o código, redirecionar. Essa resposta está correta, e também é a menor parte do design. Um encurtador é um bom exercício justamente porque o núcleo é trivial — toda decisão que importa diz respeito ao que acontece em volta dele: qual caminho precisa ser rápido, qual trabalho pode esperar e qual falha pode chegar até a pessoa que clicou.

Este post constrói uma arquitetura em quatro etapas. Cada etapa parte de um problema que a anterior não resolve, acrescenta só o que esse problema exige e diz quanto isso custa. Se você já conhece o terreno, pule direto para a arquitetura final. Se está aqui para aprender, leia na ordem: o diagrama final só fica óbvio depois que você vê por que cada caixa chegou lá.

As premissas

Números decidem arquitetura, então aqui estão os que este design usa como ponto de partida. São premissas do exercício, redondas de propósito — não medições de nenhum serviço real:

• 50 milhões de links novos por mês, cerca de 20 criações por segundo em média.
• 100 redirecionamentos para cada link criado: aproximadamente 2.000 redirecionamentos por segundo em média, com picos dez vezes maiores quando um link viraliza.
• Cerca de 500 bytes por link (a URL longa, o código, um dono, timestamps): em torno de 25 GB de dados novos por mês, 300 GB por ano.
• Um evento de clique por redirecionamento, guardado para analytics.

Duas coisas já chamam atenção. As escritas são minúsculas: 20 por segundo não é nada para banco de dados nenhum. E o redirecionamento é o produto: é a requisição pela qual pessoas de verdade esperam, milhares de vezes por segundo, parada entre elas e a página que de fato queriam. Criar um link pode levar algumas centenas de milissegundos sem ninguém perceber; um redirecionamento lento assim faz qualquer link parecer quebrado.

O design resolvido no Learn parte de um serviço menor, com números diferentes. O formato da resposta é o mesmo, e é justamente esse o ponto: a estimativa muda os tamanhos, não o raciocínio.

Etapa 1: fazer funcionar

Comece pela menor coisa que está correta. Um cliente conversa com um serviço sem estado, e o serviço guarda os links em um banco de dados relacional. São duas operações: POST /links guarda uma URL longa e devolve um código, e GET /{code} busca o código e responde com um redirecionamento.

Mesmo esta primeira versão roda pelo menos duas instâncias do serviço atrás de um balanceador de carga. Não é questão de escala — uma instância daria conta desse tráfego —, é o mínimo para ter disponibilidade: com uma única instância, todo deploy e toda queda viram indisponibilidade. O serviço não guarda estado próprio, então qualquer instância pode atender qualquer requisição, e adicionar instâncias depois é uma mudança de configuração, não um redesenho.

Saiba maisDesign resolvido: um encurtador de linksBalanceamento de carga e escalonamento horizontalGeração de IDs únicos

O código curto em si

O modelo de dados é uma única tabela — código, URL longa, dono, data de criação — com o código como chave primária. A única decisão de verdade é como os códigos são gerados, e há duas respostas razoáveis.

Códigos aleatórios. Sorteie sete caracteres de um alfabeto de 62 (base62: 26 letras minúsculas, 26 maiúsculas e 10 dígitos), insira e tente de novo se a restrição de unicidade rejeitar a linha. Sete caracteres dão cerca de 3,5 trilhões de combinações, então mesmo depois de um ano com esse tráfego uma colisão é rara e a nova tentativa quase nunca roda. Códigos aleatórios também são impraticáveis de adivinhar, o que importa mais do que parece: com códigos sequenciais, qualquer um que tenha um link pode testar os códigos vizinhos, e muita gente encurta links que nunca pretendia publicar.

Códigos baseados em contador. Pegue o próximo número de uma sequência que o banco de dados já oferece e codifique em base62 — sem colisões, sem novas tentativas. O custo é a previsibilidade, já que números consecutivos geram códigos consecutivos. A correção habitual é passar o número por um embaralhamento reversível, uma permutação com chave, antes de codificá-lo: os códigos continuam únicos, mas deixam de estar em ordem.

Este design usa o contador embaralhado: unicidade por construção, códigos que ninguém consegue enumerar e nenhum componente novo, porque o número vem do banco de dados que já temos, na mesma transação do insert. Códigos aleatórios seriam igualmente defensáveis. O que importa é que a escolha é pequena, isolada e fácil de mudar depois.

Etapa 2: o redirecionamento vira o caminho quente

Com 2.000 redirecionamentos por segundo, a primeira etapa dá conta. No pico — 20.000 por segundo enquanto um link está em todo lugar — cada redirecionamento ainda é uma consulta ao banco de dados, e o banco precisa ser dimensionado para o pior minuto do mês. É um jeito caro de servir uma leitura que quase nunca muda.

O destino de um link é gravado uma vez e lido milhares de vezes, o que faz dele o caso clássico para um cache. O serviço usa cache-aside: num redirecionamento, ele procura o código primeiro no cache. Em caso de hit, responde na hora; em caso de miss, lê o banco de dados, guarda o resultado no cache com um tempo de vida (TTL) e responde.

O serviço consulta o cache primeiro; o banco de dados só responde aos misses.

Saiba maisCamadas de cacheChaves quentes e estouros de cache (cache stampedes)

Três detalhes decidem se esse cache ajuda ou atrapalha:

• O banco de dados continua sendo a fonte da verdade. Criar um link grava no banco de dados e só retorna depois do commit; o cache é preenchido na primeira leitura. Se o cache sumisse, todos os links continuariam existindo — os redirecionamentos só ficariam mais lentos.
• O TTL é uma afirmação sobre mudança. Links raramente mudam, então um TTL longo — horas ou dias — é seguro. Quando um link é apagado ou tem o destino editado, o serviço apaga também a entrada do cache, e o TTL limita quanto tempo uma entrada cuja remoção falhou pode sobreviver.
• Códigos desconhecidos também ganham uma resposta em cache. Scanners pedem códigos aleatórios o tempo todo. Guardar “não encontrado” no cache por um minuto os mantém longe do banco de dados. Só um “não encontrado” de verdade vai para o cache desse jeito — nunca um erro do banco —, e criar um link apaga qualquer entrada de “não encontrado” para o código dele.

O cache também muda o jeito como o sistema falha. Se ele cair, os redirecionamentos passam direto para o banco de dados — ainda corretos, mas mais lentos — e o banco de repente recebe toda a carga que o cache vinha absorvendo. Ou o banco é dimensionado para aguentar isso, ou o serviço descarta carga (responde a algumas requisições com erro imediatamente, em vez de enfileirá-las) até o cache voltar. A popularidade traz um segundo risco: um link viral é uma única chave quente, e se a entrada dele expirar no pior momento, uma multidão de requisições dá miss ao mesmo tempo e cada uma delas vai ao banco de dados atrás da mesma linha. Essa falha tem um post próprio neste blog, com link no final.

Etapa 3: contar cliques sem deixar os redirecionamentos mais lentos

Agora o produto quer analytics: quantas vezes cada link foi clicado, de onde e quando. A implementação óbvia grava uma linha a cada redirecionamento. E é também a errada, porque coloca uma escrita — mais lenta que a leitura em cache ao lado dela — no caminho de latência de cada clique.

A lição desta etapa cabe numa frase: redirecionar o leitor e registrar o clique não precisam do mesmo contrato de latência. O leitor precisa de um redirecionamento em milissegundos. O analytics precisa que o clique chegue em algum momento, contado corretamente. Então o serviço publica um pequeno evento de clique numa fila e responde ao redirecionamento sem esperar por mais nada. Um worker consome a fila e grava os eventos, em lotes, num armazenamento feito para analytics.

Saiba maisFilas de mensagens e workers assíncronosIdempotência e as ilusões do exatamente-uma-vez

As premissas explicam por que os cliques ganham um armazenamento próprio. Os links crescem 25 GB por mês. Os cliques chegam a 2.000 por segundo — cerca de 170 milhões de eventos por dia — e, a aproximadamente 100 bytes cada, isso dá em torno de 500 GB por mês, vinte vezes o volume dos links. O maior conjunto de dados de um encurtador de URL não são os links, e o banco de dados que responde aos redirecionamentos não deveria ser também o que conta cliques por país na semana passada.

A fronteira assíncrona tem custos, e vale dizê-los com todas as letras:

• A entrega acontece pelo menos uma vez. Um worker que cai depois de gravar um lote, mas antes de confirmá-lo, vai receber esse lote de novo. Cada evento carrega um ID e o lado do analytics ignora IDs que já viu, então o consumidor é idempotente e uma nova tentativa não tem como duplicar uma contagem.
• As contagens atrasam. Um clique aparece no analytics segundos depois do redirecionamento, ou mais, se o worker ficar para trás. Para analytics isso é aceitável, e é uma decisão, não um acidente.
• A fila pode falhar. Se a publicação falhar, o redirecionamento ainda dá certo: o serviço pode segurar alguns segundos de eventos localmente e descartar o resto. Perder um punhado de cliques durante uma queda é o preço que este design paga para que um problema de analytics nunca vire um problema de redirecionamento.

Etapa 4: quando o banco de dados é o ponto único de falha

Veja o que ainda está sozinho. O serviço roda várias instâncias. O cache pode desaparecer sem perder dados. A fila absorve um worker lento ou quebrado. O banco de dados é uma máquina com a única cópia de cada link: se ele falhar, a criação para e todo miss de cache falha, e um disco perdido leva junto tudo o que foi gravado desde o último backup.

A correção é uma réplica em standby que recebe uma cópia de cada escrita pouco depois do commit e pode ser promovida para assumir o lugar do primário. Repare para que ela serve: disponibilidade e durabilidade, não capacidade de leitura. O cache já tirou a carga de leitura do banco de dados, então uma réplica adicionada “para leituras” ficaria quase sempre ociosa. Uma réplica e um cache respondem a perguntas diferentes, e outro post deste blog explica essa diferença.

Saiba maisReplicação e réplicas de leituraSharding e particionamento

A replicação aqui é assíncrona, o que é um trade-off por si só: o primário confirma uma escrita sem esperar pela réplica. Se o primário falhar, os últimos instantes de escritas podem nunca chegar à réplica, então um link criado um segundo antes da falha pode se perder. A replicação síncrona fecha essa brecha ao preço de escritas mais lentas e de um caminho de criação que depende de duas máquinas. Com 20 criações por segundo, qualquer uma das duas cabe no orçamento; a escolha depende de “seu link novo sumiu” ser aceitável muito de vez em quando.

O que esta etapa deliberadamente não adiciona é sharding. Dividir os links entre vários bancos de dados resolve outro problema — mais dados ou mais escritas do que um primário aguenta — e, com 300 GB por ano e 20 escritas por segundo, esse problema está a anos de distância. Quando ele chegar, a chave de particionamento já é óbvia: toda busca é por código, então particionar por um hash do código faz cada redirecionamento tocar exatamente uma partição. Particionar por faixas do número sequencial bruto, em vez disso, mandaria todo link novo para a mesma partição, a mais recente; é o hash da chave que espalha as escritas.

A arquitetura final, lida pelas falhas

Quatro etapas e nove caixas, cada uma ali por um motivo que as etapas deram. O jeito mais útil de ler o diagrama final é pela falha — o que quebra e quem percebe:

• Uma instância do serviço morre → o balanceador de carga para de mandar tráfego para ela. Ninguém percebe.
• O balanceador de carga falha → tudo falha. Ele aparece como uma caixa só porque normalmente é um serviço gerenciado e redundante, não uma máquina que você opera; se for uma máquina que você opera, ela precisa ser duplicada.
• O cache está fora do ar → os redirecionamentos são servidos pelo banco de dados, mais devagar, enquanto o banco aguentar a carga. Nada fica incorreto.
• A fila ou o worker está fora do ar → os redirecionamentos não são afetados; os cliques ficam em buffer, atrasam ou, numa queda longa, se perdem em parte.
• O armazenamento de analytics está lento → o worker fica para trás e as contagens atrasam. Os redirecionamentos nem ligam.
• O banco de dados primário falha → a criação de links para até a réplica em standby ser promovida. Links populares continuam redirecionando a partir do cache; o resto falha até a promoção terminar.

Essa lista é o design de verdade. As caixas são o meio; as decisões são até qual caminho cada falha pode chegar. O redirecionamento depende do mínimo possível — o balanceador de carga, o serviço, o cache e o banco de dados só para os misses — e todo o resto se liga a ele de forma assíncrona.

O que este design deixa em aberto

Algumas decisões são do produto, não da arquitetura, e uma revisão de design deveria nomeá-las em vez de fingir que estão resolvidas:

• Abuso. Um encurtador esconde para onde um link leva, o que o torna atraente para phishing e malware. Serviços reais verificam o destino quando o link é criado e limitam a taxa de quem pode criar links.
• Aliases personalizados. Deixar as pessoas escolherem o próprio código transforma esse código numa chave única fornecida pelo usuário, com palavras reservadas e squatting para administrar.
• Expiração e remoção. Links que expiram precisam de uma rotina de limpeza e de um cache que os esqueça na hora certa.
• Regiões. Leitores em vários continentes iriam querer o cache, e talvez o próprio redirecionamento, mais perto deles. O tráfego deste exercício ainda não precisa disso.

O código curto ocupou dois parágrafos. Todo o resto — o caminho quente, a fronteira assíncrona, a fonte da verdade, a falha que cada caixa pode causar — é o design de verdade, e é a parte que se aplica a qualquer outro sistema que você for desenhar.