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) e insere-se. A restrição de unicidade é a verificação de colisão: quando rejeita a linha, escolhe-se de novo, poucas vezes no máximo — nunca se consulta o código antes de inserir, porque dois pedidos podem ambos encontrá-lo livre. Sete caracteres dão cerca de 3,5 biliões de combinações. Ao fim de um ano com este tráfego estão ocupados 600 milhões, por isso cerca de uma escolha em 6000 calha num código que já existe: uma inserção isolada quase nunca tem de repetir, mas o sistema no seu conjunto ainda repete umas 50 000 vezes nesse ano. As colisões são rotina para o sistema e inofensivas para cada pedido, e é exatamente para isso que serve a nova tentativa. Os códigos aleatórios também não têm ordem: 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 antes de o codificar — uma permutação com chave sobre o intervalo de sete caracteres: os códigos continuam únicos, mas deixam de estar por ordem.
Este design usa o contador baralhado: unicidade por construção, códigos que não revelam nem a ordem nem os vizinhos, e nenhum componente novo, porque o número vem da base de dados que já temos. Uma inserção que é revertida deixa o seu número por usar — as sequências não devolvem números, nem precisam: os códigos têm de ser únicos, não consecutivos. Nenhum dos esquemas torna um link privado, no entanto. Com 600 milhões dos 3,5 biliões de códigos em uso, cerca de uma tentativa em 6000 acerta num link real, por isso quem varre códigos encontra links de qualquer forma; um código curto é um endereço, não uma permissã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.
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. Links apagados, links expirados e gralhas são pedidos vezes sem conta. Guardar «não encontrado» em cache durante um minuto responde a essas repetições sem passar pela base de dados. Não trava um scanner que tenta um código diferente de cada vez: cada tentativa é um novo miss, e a defesa aí é limitar a rapidez com que um cliente pode perguntar. 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. As correções não precisam de uma caixa nova: deixa-se um pedido reabastecer a entrada enquanto os outros esperam por ele (coalescência de pedidos, ou request coalescing), ou continua-se a servir o valor antigo enquanto é atualizado em segundo plano (stale-while-revalidate). 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 dos cliques dentro de um minuto ou pouco mais, cada um contado uma só vez, e pode dar-se ao luxo de perder alguns. Por isso, o serviço coloca um pequeno evento de clique num buffer em memória e responde logo ao redirecionamento; uma tarefa em segundo plano, no mesmo serviço, publica os eventos do buffer numa fila. O redirecionamento nunca espera pela fila — nem sequer pela sua confirmação. 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:
- Da fila em diante, 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.
- Antes da fila, podem perder-se cliques. Se a fila estiver inacessível, os redirecionamentos continuam e os eventos esperam no buffer, que guarda alguns segundos deles; quando enche, os novos eventos são descartados e contabilizados como descartados. Uma instância que vá abaixo perde o que o seu buffer ainda tinha. 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.
301 Moved Permanently permite que os browsers memorizem o redirecionamento e saltem o encurtador na visita seguinte: é mais barato, mas esses cliques repetidos nunca são vistos, e um destino editado não chega a um browser que guardou o antigo em cache até essa entrada expirar — o que, sem cabeçalhos de cache, pode ser nunca. Um 302 Found mantém cada clique observável e cada edição efetiva. (308 e 307 são o mesmo par, preservando o método do pedido; para um link que só é pedido com GET, comportam-se da mesma forma.) Se a análise faz parte do produto, o 302 encaixa melhor; a escolha oposta é defensável, desde que seja feita de propósito.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. Com códigos baseados num contador, essa perda tem um segundo gume: a sequência da réplica promovida pode estar atrás de números que a antiga primária já entregou, pelo que o código de um link perdido pode voltar a ser atribuído a outro destino — enquanto o link antigo ainda está na mensagem de alguém, ou ainda na cache. Avançar a sequência bem para lá do seu último valor, como parte de cada promoção, fecha essa lacuna. A replicação síncrona fecha a primeira lacuna, a da escrita perdida, à 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 — por um gestor de failover ou por um operador, depois de garantir que a antiga primária já não aceita escritas. 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.