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

Peça a qualquer pessoa que desenhe um encurtador de URL e a primeira resposta chega em segundos: guardar code → url, procurar o código, redirecionar. Essa resposta está certa, e é também a parte mais pequena do design. Um encurtador é um bom exercício precisamente porque o seu núcleo é trivial — todas as decisões que importam dizem respeito ao que acontece à volta dele: que caminho tem de ser rápido, que trabalho pode esperar e que falha pode chegar à pessoa que clicou.

Este artigo constrói uma arquitetura em quatro etapas. Cada etapa parte de um problema que a anterior não consegue resolver, acrescenta apenas o que esse problema exige e diz quanto custa. Se já conhece o terreno, salte para a arquitetura final. Se está aqui para aprender, leia por ordem: o diagrama final só é óbvio depois de ver porque é que cada caixa lá chegou.

Os pressupostos

Os números decidem a arquitetura, por isso aqui ficam aqueles de que este design parte. São pressupostos do exercício, redondos 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 por cada link criado: aproximadamente 2000 redirecionamentos por segundo em média, com picos dez vezes superiores quando um link se espalha.
• Cerca de 500 bytes por link (o URL longo, o código, um proprietário, marcas temporais): à volta de 25 GB de dados novos por mês, 300 GB por ano.
• Um evento de clique por redirecionamento, guardado para análise.

Há duas coisas que já saltam à vista. As escritas são ínfimas: 20 por segundo não é nada para qualquer base de dados. E o redirecionamento é o produto: é o pedido de que pessoas reais ficam à espera, milhares de vezes por segundo, entre elas e a página que realmente queriam. Criar um link pode demorar umas centenas de milissegundos sem que ninguém dê por isso; um redirecionamento tão lento faz com que todos os links pareçam avariados.

O design desenvolvido no Learn parte de um serviço mais pequeno, com números diferentes. A forma da resposta é a mesma, e é esse o objetivo: a estimativa muda as dimensões, não o raciocínio.

Etapa 1: pôr a funcionar

Comece pela coisa mais pequena que esteja correta. Uma aplicação cliente fala com um serviço sem estado, e o serviço guarda os links numa base de dados relacional. Há duas operações: POST /links guarda um URL longo e devolve um código, e GET /{code} procura o código e responde com um redirecionamento.

Mesmo esta primeira versão corre pelo menos duas instâncias do serviço atrás de um balanceador de carga. Não é uma questão de escala — uma instância bastaria para este tráfego —, é o mínimo para a disponibilidade: com uma única instância, cada deploy e cada crash são uma indisponibilidade. O serviço não guarda estado próprio, por isso qualquer instância pode responder a qualquer pedido, e acrescentar instâncias mais tarde é uma alteração de configuração e não um redesenho.

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

O código curto propriamente dito

O modelo de dados é uma única tabela — código, URL longo, proprietário, data de criação — com o código como chave primária. A única decisão a sério é a forma de gerar os códigos, e há duas respostas razoáveis.

Códigos aleatórios. Escolhem-se sete caracteres de um alfabeto de 62 (base62: 26 letras minúsculas, 26 letras maiúsculas e 10 algarismos), insere-se e tenta-se de novo se a restrição de unicidade rejeitar a linha. Sete caracteres dão cerca de 3,5 biliões de combinações, por isso, mesmo ao fim de um ano com este tráfego, uma colisão é rara e a nova tentativa raramente acontece. Os códigos aleatórios são também impraticáveis de adivinhar, o que importa mais do que parece: com códigos sequenciais, quem tiver um link pode experimentar os códigos vizinhos, e as pessoas encurtam muitas vezes links que nunca tencionaram publicar.

Códigos baseados num contador. Tira-se o número seguinte de uma sequência que a base de dados já fornece e codifica-se em base62 — sem colisões, sem novas tentativas. O custo é a previsibilidade, já que números consecutivos dão códigos consecutivos. A solução habitual é fazer passar o número por um baralhamento reversível, uma permutação com chave, antes de o codificar: os códigos continuam únicos, mas deixam de estar por ordem.

Este design usa o contador baralhado: unicidade por construção, códigos que ninguém consegue enumerar e nenhum componente novo, porque o número vem da base de dados que já temos, na mesma transação que a inserção. Os códigos aleatórios seriam igualmente defensáveis. O que importa é que a escolha é pequena, contida e fácil de mudar mais tarde.

Etapa 2: o redirecionamento torna-se o caminho quente

A 2000 redirecionamentos por segundo, a primeira etapa aguenta-se bem. No pico — 20 000 por segundo enquanto um link está por todo o lado — cada redirecionamento continua a ser uma consulta à base de dados, e a base de dados tem de ser dimensionada para o pior minuto do mês. É uma forma cara de servir uma leitura que quase nunca muda.

O destino de um link é escrito uma vez e lido milhares de vezes, o que faz dele o caso de manual para uma cache. O serviço usa cache-aside: num redirecionamento, procura primeiro o código na cache. Se o encontrar, responde de imediato; se não o encontrar, lê a base de dados, guarda o resultado na cache com um tempo de vida (TTL) e responde.

O serviço pergunta primeiro à cache; a base de dados só responde ao que a cache não tem.

Saiba maisCamadas de cacheChaves quentes e estampidas de cache

Há três pormenores que decidem se esta cache ajuda ou prejudica:

• A base de dados continua a ser a fonte de verdade. Criar um link escreve na base de dados e só devolve depois do commit; a cache é preenchida na primeira leitura. Se a cache desaparecesse, todos os links continuariam a existir — os redirecionamentos seriam apenas mais lentos.
• O TTL é uma afirmação sobre a mudança. Os links raramente mudam, por isso um TTL longo — horas ou dias — é seguro. Quando um link é apagado ou o seu destino é editado, o serviço apaga também a entrada da cache, e o TTL limita o tempo que pode sobreviver uma entrada cuja remoção tenha falhado.
• Os códigos desconhecidos também têm uma resposta guardada em cache. Os scanners pedem códigos aleatórios constantemente. Guardar «não encontrado» em cache durante um minuto mantém-nos longe da base de dados. Só um «não encontrado» verdadeiro é guardado assim — nunca um erro da base de dados — e criar um link apaga qualquer entrada «não encontrado» para o seu código.

A cache muda também a forma como o sistema falha. Se for abaixo, os redirecionamentos passam a ir à base de dados — continuam corretos, mas mais lentos — e, de repente, pede-se à base de dados toda a carga que a cache estava a absorver. Ou a base de dados está dimensionada para aguentar isso, ou o serviço descarta carga (responde de imediato a alguns pedidos com um erro em vez de os pôr em fila) até a cache voltar. A popularidade acrescenta um segundo risco: um link viral é uma única chave quente, e se a sua entrada expirar no pior momento, uma multidão de pedidos não a encontra ao mesmo tempo e todos eles vão à base de dados buscar a mesma linha. Essa falha tem um artigo próprio neste blog, com ligação no fim.

Etapa 3: contar cliques sem abrandar os redirecionamentos

Agora o produto quer análise: quantas vezes cada link foi clicado, de onde e quando. A implementação óbvia escreve uma linha em cada redirecionamento. É também a errada, porque coloca uma escrita — mais lenta do que a leitura em cache ao lado da qual fica — no caminho de latência de cada clique.

A lição desta etapa cabe numa frase: redirecionar o leitor e registar o clique não precisam do mesmo contrato de latência. O leitor precisa de um redirecionamento em milissegundos. A análise precisa que o clique chegue, mais cedo ou mais tarde, contado corretamente. Por isso, 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 escreve os eventos, em lotes, num armazenamento feito para análise.

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

Os pressupostos explicam porque é que os cliques têm direito a armazenamento próprio. Os links crescem 25 GB por mês. Os cliques chegam a 2000 por segundo — cerca de 170 milhões de eventos por dia — e, a uns 100 bytes cada, isso dá à volta de 500 GB por mês, vinte vezes o volume dos links. O maior conjunto de dados num encurtador de URL não são os links, e a base de dados que responde aos redirecionamentos não deve ser também a que conta os cliques por país da semana passada.

A fronteira assíncrona tem custos, e vale a pena dizê-los com clareza:

• A entrega é pelo menos uma vez. Um worker que vá abaixo depois de escrever um lote, mas antes de o confirmar, vai recebê-lo de novo. Cada evento leva um ID e o lado da análise ignora os IDs que já viu, por isso o consumidor é idempotente e uma nova tentativa não pode duplicar uma contagem.
• As contagens chegam com atraso. Um clique aparece na análise segundos depois do redirecionamento, ou mais tarde se o worker se atrasar. Para análise, isso não é problema, e é uma decisão, não um acidente.
• A fila pode falhar. Se a publicação falhar, o redirecionamento continua a ter sucesso: o serviço pode guardar localmente alguns segundos de eventos e descartar o resto. Perder meia dúzia de cliques durante uma indisponibilidade é o preço que este design paga para que um problema de análise nunca se torne um problema de redirecionamento.

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

Veja o que continua sozinho. O serviço corre várias instâncias. A cache pode desaparecer sem perder dados. A fila absorve um worker lento ou avariado. A base de dados é uma máquina com a única cópia de cada link: se falhar, a criação para e todos os pedidos que não estão na cache falham, e um disco perdido leva consigo tudo o que foi escrito desde a última cópia de segurança.

A solução é uma réplica de reserva que recebe uma cópia de cada escrita pouco depois de ela ser confirmada e que pode ser promovida para ocupar o lugar da primária. Repare para que serve: disponibilidade e durabilidade, não capacidade de leitura. A cache já tirou a carga de leitura à base de dados, por isso uma réplica acrescentada «para leituras» ficaria quase sempre parada. Uma réplica e uma cache respondem a perguntas diferentes, e outro artigo deste blog explica essa distinção.

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

A replicação aqui é assíncrona, o que é um compromisso por si só: a primária confirma uma escrita sem esperar pela réplica. Se a primária falhar, os últimos instantes de escritas podem nunca chegar à réplica, pelo que um link criado um segundo antes da falha pode perder-se. A replicação síncrona fecha essa lacuna à custa de escritas mais lentas e de um caminho de criação que depende de duas máquinas. A 20 criações por segundo, qualquer uma das opções é comportável; a escolha depende de saber se «o seu link novo desapareceu» é aceitável muito de vez em quando.

O que esta etapa deliberadamente não acrescenta é sharding. Repartir os links por várias bases de dados resolve um problema diferente — mais dados ou mais escritas do que uma primária aguenta — e, a 300 GB por ano e 20 escritas por segundo, esse problema está a anos de distância. Quando chegar, a chave de partição já é óbvia: todas as consultas são por código, por isso particionar por um hash do código faz com que cada redirecionamento toque exatamente numa partição. Particionar, em vez disso, por intervalos do número de sequência em bruto mandaria cada link novo para a mesma partição, a mais recente; é o hash da chave que espalha as escritas.

A arquitetura final, lida pelas suas falhas

Quatro etapas e nove caixas, cada uma delas presente por uma razão que as etapas deram. A forma mais útil de ler o diagrama final é pelas falhas — o que se avaria e quem dá por isso:

• Uma instância do serviço morre → o balanceador de carga deixa de lhe enviar tráfego. Ninguém dá por nada.
• O balanceador de carga falha → tudo falha. Está desenhado como uma só caixa porque normalmente é um serviço gerido e redundante, e não uma máquina que se opera; se for uma máquina operada por si, precisa de estar duplicada.
• A cache está em baixo → os redirecionamentos são servidos a partir da base de dados, mais devagar, enquanto a base de dados aguentar a carga. Nada fica incorreto.
• A fila ou o worker estão em baixo → os redirecionamentos não são afetados; os cliques ficam em buffer, atrasados ou, numa indisponibilidade longa, parcialmente perdidos.
• O armazenamento de análise está lento → o worker atrasa-se e as contagens também. Os redirecionamentos nem dão por isso.
• A base de dados primária falha → a criação de links para até a réplica de reserva ser promovida. Os links populares continuam a redirecionar a partir da cache; os restantes falham até a promoção terminar.

Essa lista é o verdadeiro design. As caixas são os meios; as decisões são até que caminho cada falha pode chegar. O redirecionamento depende do mínimo possível — o balanceador de carga, o serviço, a cache e a base de dados só para o que a cache não tem — e tudo o resto está ligado a ele de forma assíncrona.

O que este design deixa em aberto

Algumas decisões pertencem ao produto e não à arquitetura, e uma revisão de design deve nomeá-las em vez de fingir que estão resolvidas:

• Abuso. Um encurtador esconde para onde um link vai, o que o torna apelativo para phishing e malware. Os serviços reais verificam os destinos quando um link é criado e impõem limites de taxa a quem pode criar links.
• Aliases personalizados. Deixar as pessoas escolherem o seu próprio código transforma-o numa chave única fornecida pelo utilizador, com palavras reservadas e ocupação abusiva de nomes para gerir.
• Expiração e eliminação. Os links que expiram precisam de uma tarefa de limpeza e de uma cache que os esqueça a tempo.
• Regiões. Leitores em vários continentes quereriam a cache, e talvez o próprio redirecionamento, mais perto de si. O tráfego deste exercício ainda não precisa disso.

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