Cache strategy for URL redirects: L1 LRU and L2 Redis

A camada de redirecionamento de um encurtador de URL é um dos poucos sistemas de produção onde a estratégia de cache é a própria arquitetura. Não há outro trabalho significativo acontecendo no hot path — cada requisição resolve uma chave (o slug curto), lê uma URL de destino e emite um 301 ou 302. Todo o resto é observabilidade e bookkeeping. O cache é o que determina se a requisição mediana leva 800 microssegundos ou 12 milissegundos.

Este post documenta a estratégia de cache por trás do serviço edge-redirect da Elido. Duas camadas, uma política de expulsão escolhida para otimizar a latência de cauda (tail latency) em vez da taxa de acerto (hit rate), uma estratégia de warming que é mais simples do que parece e os modos de falha que vimos em 18 meses de produção. O cornerstone de p95 de redirecionamento < 15ms cobre o orçamento total de latência; este é o mergulho profundo específico em cache.

Por que duas camadas#

A arquitetura de cache mais simples para um serviço de redirecionamento é uma única camada: um cluster Redis entre o processo de redirecionamento e o banco de dados de origem. Cada requisição que não atinge o banco de dados atinge o Redis; cada requisição que não atinge o Redis atinge o banco de dados. O salto do Redis adiciona cerca de 1ms quando o Redis está na mesma região.

Caches de duas camadas adicionam uma camada in-process na frente do Redis. A primeira camada — chame-a de L1 — vive dentro do espaço de endereçamento do processo de redirecionamento. Um hit no L1 retorna a URL de destino em algumas centenas de nanossegundos, sem necessidade de ida e volta na rede. Um miss no L1 cai para o Redis (L2), que atende com latência sub-milissegundo. Um miss no L2 cai para a chamada gRPC de origem contra o banco de dados Postgres canônico.

A escolha entre uma camada e duas é essencialmente uma questão de quão estável sua latência de cauda precisa ser. O Redis é rápido, mas não é gratuito. Um p50 de 1ms para o Redis torna-se um p99 de 4-6ms sob carga, e o p99.9 pode exceder 20ms quando há qualquer contenção na rede. Para um SLO que visa p95 < 15ms, cada hit no Redis consome uma fração significativa do orçamento. Para p99.9 < 50ms, a cauda do Redis é o contribuinte dominante.

Um LRU in-process absorve as chaves de maior frequência — aquelas que geram mais de 80% do tráfego. Na distribuição de tráfego da Elido, os 1000 links curtos principais por volume de requisição representam mais de 70% das requisições de redirecionamento. Essas chaves são fáceis de servir in-process; a cauda longa pode cair para o Redis sem degradar o p95.

L1: um LRU por processo#

O cache L1 utiliza Ristretto, o mesmo LRU de política de admissão usado pelo Caddy e pelo Dgraph. Nós o escolhemos por três razões:

Leituras concorrentes escalam linearmente com núcleos de CPU. Um cache sync.Map mais simples trava em cerca de 4M ops/sec em uma máquina POP de borda típica; o Ristretto sustenta mais de 30M em nossos benchmarks.
A política de admissão TinyLFU evita que cargas de trabalho de varredura única (one-shot scan) expulsem chaves quentes. Um rastreamento de bot que toca em 10.000 slugs únicos uma vez cada não desloca os links genuinamente populares do cache.
Memória limitada em vez de contagem de chaves limitada. Podemos definir "use até 256MB" em vez de "armazene até 100.000 entradas", que é a configuração que importa para o planejamento de capacidade.

A configuração que enviamos é:

cache, err := ristretto.NewCache(&ristretto.Config{
    NumCounters: 10_000_000, // 10M counters → tracks ~1M items
    MaxCost:     256 << 20,   // 256MB
    BufferItems: 64,
    Metrics:     true,
})

NumCounters é o tamanho da tabela de rastreamento de frequência TinyLFU; a regra prática nos documentos do Ristretto é 10× a contagem de itens esperada. Com um orçamento de 256MB e um registro de link médio de 200 bytes, o cache armazena cerca de 1.3M entradas quando cheio.

O TTL nas entradas L1 é de 60 segundos. Isso é deliberadamente curto. Um redirecionamento pode ter seu destino alterado no dashboard a qualquer momento, e o cache L1 é a camada mais lenta para invalidar (o Redis pode ser invalidado por publicação; o L1 vive em cada processo e precisa de um caminho de invalidação coordenado).

Um TTL de 60 segundos significa que o pior caso de obsolescência é de 60 segundos após uma atualização de destino. Para a maioria dos casos de uso, isso é aceitável; para os casos em que não é (mudanças imediatas de destino durante uma campanha ao vivo), o botão de invalidação do dashboard emite um fanout que limpa todos os caches L1 em toda a frota. O fanout usa Redis pub/sub em um canal que cada processo de borda assina na inicialização.

L2: Cluster Redis com réplicas de leitura#

O L2 é um cluster Redis, implantado em cada região (FRA, ASH, SGP). As leituras vão para as réplicas locais; as escritas vão para o primário regional e replicam dentro do modelo assíncrono padrão do Redis.

O formato de dados é pequeno. Um registro de redirecionamento no L2 se parece com:

KEY:   redirect:f.elido.me:abc123
VALUE: {"d":"https://shop.example.com/spring","f":0,"v":12}

Três campos: URL de destino, sinalizadores (filtragem de bot ativada, senha necessária, etc., empacotados em um uint16) e versão. A versão é a versão da linha do Postgres; ela nos permite detectar entradas de cache obsoletas na leitura.

O TTL no L2 é de 24 horas. Isso é muito mais longo que o L1 porque o L2 possui um caminho de invalidação funcional: quando um link é criado ou atualizado no banco de dados de origem, a API publica uma mensagem Redis pub/sub para o canal de invalidação regional, e os processos de redirecionamento expulsam suas entradas L1; a entrada L2 é sobrescrita diretamente pela camada de API.

A invalidação pub/sub tem uma propriedade sutil: ela é lossy (sujeita a perdas). Se um processo de redirecionamento estiver reiniciando quando a mensagem de invalidação é publicada, ele não vê a mensagem e seu cache L1 pode servir o valor obsoleto por até 60 segundos. Aceitamos isso porque o TTL é o backstop — a obsolescência é limitada.

O tamanho do cluster Redis em cada POP é pequeno. FRA executa três nós primários mais três réplicas; o conjunto de dados total cabe em cerca de 4GB. Em nossa taxa de acerto de cache (98% L1, 1.8% L2, 0.2% origem sob carga normal), o requisito de taxa de transferência no Redis é moderado — geralmente 5-15k ops/sec no pico por POP, bem dentro da capacidade de um único nó primário se tivéssemos que consolidar.

A escolha da política de expulsão#

A política de admissão TinyLFU do Ristretto é a escolha que mais importa para a latência de cauda.

Um LRU ingênuo expulsa a chave usada menos recentemente sempre que precisa abrir espaço. Isso funciona bem quando o padrão de acesso é razoavelmente uniforme — as chaves que foram usadas mais recentemente são as mais propensas a serem usadas novamente. Isso falha em dois padrões específicos:

Cargas de trabalho de varredura (Scan workloads). Um rastreamento de bot que atinge 50.000 slugs únicos em sucessão rápida irá, sob um LRU ingênuo, expulsar todas as chaves quentes e substituí-las por chaves de rastreamento que nunca mais serão acessadas. A taxa de acerto do cache cai, a origem vê um pico de carga e o p95 salta porque a maioria das requisições agora está atingindo o caminho lento.
Chaves quentes em rajadas (Bursty hot keys). Um link que normalmente é frio, mas de repente recebe 100k requisições em 30 segundos (um post social viral, uma campanha de TV) precisa ser armazenado em cache rapidamente. Sob um LRU ingênuo, ele deslocará uma das chaves quentes existentes.

O TinyLFU lida com ambos. A política de admissão rastreia as frequências das chaves e só admite uma nova chave no cache se ela for mais frequente do que a candidata à expulsão. Um rastreamento de bot único não desloca as chaves quentes porque as chaves de rastreamento têm uma contagem de frequência de 1. Uma chave quente em rajada entra no cache, mas somente depois que sua frequência excede a da candidata à expulsão — o que acontece em poucas centenas de requisições.

O custo é que as primeiras 100-500 requisições para um link recém-popular são lentas (caem para o L2 ou origem) até que a política de admissão decida armazená-lo em cache. Para a maioria dos casos de uso, este é o compromisso correto; para campanhas em que sabemos antecipadamente que um link terá um pico, temos um endpoint de pre-warm descrito abaixo.

Warming do cache#

O cache L2 faz um cold-start quando um novo cluster Redis entra em operação. Não o aquecemos a partir de um snapshot; os primeiros 5 minutos após o reinício de um cluster veem um tráfego de origem elevado até que o cache seja preenchido naturalmente.

O cache L1 faz um cold-start quando um processo de redirecionamento reinicia (implantações, interrupções por OOM, escalonamento). Os primeiros 30 segundos após a reinicialização de um processo veem a maioria das requisições cair para o L2; os próximos 60 segundos veem o L1 preencher seu conjunto de trabalho de chaves quentes. A contribuição total do cold-start para a carga de origem é pequena (a maioria dos processos de borda reinicia com muito menos frequência do que o TTL do cache).

A exceção: quando um gerente de campanha pré-publica um link que ele sabe que terá um pico — uma URL de anúncio de TV, uma URL de comunicado de imprensa, um anúncio de lançamento — o dashboard oferece uma opção de "pre-warm". Ativá-lo emite um redirecionamento no-op contra o serviço edge-redirect em cada POP, o que preenche o L1 antecipadamente. Isso é pouco sofisticado e raramente necessário; o autoscaler lida adequadamente com picos de tráfego imprevistos. O pre-warm é a resposta para picos antecipados onde os primeiros 60 segundos de latência de cache frio seriam visíveis.

O que acontece na capacidade máxima do L1#

Um cache L1 de 256MB enche em menos de um minuto em um POP de borda típico. Uma vez cheio, cada nova chave exige que a política de admissão TinyLFU decida se deve expulsar uma chave existente.

A observação interessante: em nossa distribuição, a taxa de acerto do L1 estabiliza em torno de 98% quando aquecido. A taxa de miss de 2% é a cauda longa — os cerca de 30% dos links que representam menos de 30% do tráfego e, portanto, não ultrapassam o limite de frequência do TinyLFU. Estes falham no L1 e acertam no L2, onde a taxa de acerto é de aproximadamente 99%. Os 0.2% restantes do total de requisições caem para a origem.

Medimos essa distribuição em três formatos de carga de trabalho — tráfego pesado de bots, pico viral, estado estável — e a taxa de acerto do L1 flutua entre 95% e 99%. A taxa de acerto do L2 é mais estável em 98-99.5%. A carga total de origem da camada de redirecionamento é, portanto, limitada a cerca de 0.5% do volume de requisições de entrada, que é o número que importa para o planejamento de capacidade de origem.

Invalidação de cache em detalhes#

O fluxo de invalidação é a parte mais frequentemente mal compreendida por quem lê a arquitetura de fora. O detalhe:

Quando a API recebe um PATCH /v1/links/{id} que altera a URL de destino, três coisas acontecem em ordem:

O Postgres confirma a alteração com a nova versão da linha (UPDATE links SET destination = ?, version = version + 1 WHERE id = ?).
O Redis é escrito diretamente com o novo valor em cada cluster Redis regional. A escrita faz o fanout da API para o Redis de cada região através de uma camada de write-through.
A invalidação pub/sub é publicada em cada canal regional invalidate:redirect. Os processos de redirecionamento de borda assinam este canal na inicialização e expulsam a entrada L1 da chave.

A ordem importa. Postgres-primeiro garante que o armazenamento canônico tenha o novo valor. Redis-write-through-antes-da-publicação garante que qualquer processo que perca a publicação, mas leia do Redis, veja o novo valor. A publicação é a otimização que mantém o L1 sincronizado; o TTL é o backstop se uma publicação for perdida.

A race condition conhecida: um processo de redirecionamento que está lendo do Redis (devido a um miss no L1) e uma publicação de invalidação concorrente. A leitura pode retornar o novo valor (a publicação aconteceu um pouco antes da leitura) ou o valor antigo (a publicação aconteceu um pouco depois). Se o valor antigo for retornado e armazenado em cache no L1, os próximos 60 segundos poderão servir o valor antigo para esse processo. Isso é aceitável; a alternativa — um bloqueio síncrono em torno da disputa de leitura-publicação — adiciona latência a cada requisição para evitar um caso extremo que afeta menos de 0.01% das invalidações.

Para casos de uso onde a janela de obsolescência é inaceitável (uma URL de destino está sendo removida por motivos legais, um destino é subitamente malicioso), a ação "purge cache" do dashboard emite uma invalidação agressiva: ela pausa todas as leituras L1 por 100ms em toda a frota, expulsa a chave de cada L1 e depois retoma. Isso é raramente usado e fixado a um limite de taxa por segundo.

Modos de falha que realmente vimos#

Três falhas dos 18 meses de histórico de produção que valem a pena documentar porque moldaram a configuração atual.

Failover do primário do Redis com réplicas obsoletas. No mês 4 de produção, um nó primário no cluster de FRA falhou. A réplica foi promovida em 30 segundos (failover orientado pelo Sentinel). As réplicas estavam cerca de 200ms atrás do primário no momento da falha, o que significava que as primeiras centenas de invalidações publicadas pouco antes do failover não chegaram à réplica promovida. Resultado: uma breve janela onde cerca de 0.3% dos redirecionamentos serviram destinos obsoletos. Resolução: agora executamos réplicas com min-replicas-to-write 1 and min-replicas-max-lag 10, o que troca um pequeno impacto na disponibilidade de escrita por uma garantia de atraso de replicação mais rigorosa.

Thrashing do cache L1 durante uma varredura de monitoramento sintético. No mês 9, um serviço de monitoramento de uptime de terceiros foi configurado incorretamente para sondar cada link curto no workspace de um cliente uma vez por minuto. O cliente tinha 18.000 links curtos. O padrão de sondagem era uma varredura completa a cada 60 segundos. Efeito: a taxa de acerto do cache L1 caiu de 98% para 71% em três POPs de borda porque o padrão de varredura admitiu cada chave sondada no cache. Resolução: adicionamos filtragem baseada em User-Agent antes da camada de admissão do cache — User-Agents de monitoramento conhecidos ignoram o cache e servem do L2 diretamente. Este foi um caso extremo do TinyLFU: as chaves de varredura pareciam frequentes o suficiente para deslocar chaves genuinamente quentes.

Desconexão do pub/sub durante uma implantação longa. No mês 13, uma implantação que demorou mais do que o esperado (cerca de 4 minutos) fez com que vários processos de borda permanecessem conectados ao canal pub/sub antigo após o primário do Redis ter sofrido failover. As invalidações publicadas no novo primário não chegaram a esses processos; seus caches L1 serviram valores obsoletos durante a implantação. Resolução: heartbeats de conexão pub/sub com reconexão automática em heartbeats perdidos e um flush de L1 no momento da implantação como precaução.

O que consideramos e rejeitamos#

Algumas alternativas avaliadas e não escolhidas:

Um único cache in-process, sem Redis. Testado. A taxa de miss-para-origem em qualquer processo único é muito alta sem um L2; o banco de dados de origem precisaria de 3 a 5 vezes mais capacidade. O custo marginal do Redis é pequeno em relação à economia de capacidade de origem.

Uma CDN como Cloudflare ou Fastly para cache de redirecionamento. Testado em staging. A latência regional de 1-2ms da CDN em um acerto de cache é aproximadamente a mesma do Redis, mas a história da invalidação é materialmente pior (as limpezas de CDN têm latência de escala de minutos e custos de limpeza por URL). A CDN adicionou complexidade sem melhorar a latência ou a taxa de acerto.

Um L1 maior. O orçamento de 256MB é dimensionado para o envelope de memória por processo; dobrá-lo não dobra a taxa de acerto porque o conjunto de trabalho quente já cabe. Os retornos decrescentes começam em cerca de 128MB em nossa distribuição; 256MB têm margem para crescimento de tráfego.

Observabilidade#

As métricas que rastreamos por processo de borda:

cache_l1_hit_total, cache_l1_miss_total — taxa de acerto derivada por processo.
cache_l2_hit_total, cache_l2_miss_total — taxa de acerto derivada por região.
cache_origin_request_total — volume de requisições de origem; a meta do SLO é < 1% do total de requisições.
cache_invalidation_total{source="pubsub|ttl|purge"} — contagens de invalidação por mecanismo.
cache_l1_memory_bytes — memória real usada pelo cache L1; alertado em 90% do orçamento configurado.

Todas as métricas são coletadas pelo Prometheus e visualizadas no conjunto de dashboards do guia de observabilidade. Os dashboards do Grafana no nível regional mostram a taxa de acerto do cache regional ao longo do tempo; os dashboards por processo (usados durante incidentes) mostram a taxa de acerto do L1 e o uso de memória por processo.

Quando usar esta estratégia e quando não#

Um cache de duas camadas faz sentido quando:

A carga de trabalho é de leitura intensa com uma distribuição de chaves de cauda longa.
O conjunto de trabalho quente cabe na memória por processo (algumas centenas de megabytes).
Os misses de cache são caros o suficiente para que a segunda camada economize carga no banco de dados.
O orçamento de obsolescência é apertado o suficiente para que apenas o TTL do L1 não seja aceitável.

Não faz sentido quando:

O conjunto de trabalho quente não cabe na memória do processo. Nesse caso, os misses do L1 caem para o L2 com frequência suficiente para que o L1 contribua pouco.
As escritas são frequentes em relação às leituras. O custo de invalidação domina.
Os dados são únicos por requisição (nenhum benefício de armazenamento em cache).

Para a carga de trabalho do encurtador de URL, todas as quatro condições "sim" são válidas e a configuração acima se manteve ao longo de 18 meses de crescimento na produção. Para outras cargas de trabalho, a contagem de camadas e a política de expulsão precisam de reavaliação.

Leituras relacionadas#

Atingindo p95 < 15ms para redirecionamentos de FRA, ASH e SGP — o cornerstone para o cluster de engenharia; este post é o mergulho profundo específico em cache.
Por que usamos ClickHouse para análise de cliques (não Postgres) — decisão de engenharia adjacente na mesma arquitetura.
Ingestão de cliques 'fire-and-forget' com Redpanda — o pipeline de eventos de clique que roda junto com o cache de redirecionamento.
Links curtos como Terraform — o passo a passo operacional para a configuração da camada de redirecionamento.
Arquitetura de borda (edge): /docs/architecture/edge-redirect.
Guia operacional: /docs/guides/observability — o conjunto de dashboards de métricas referenciado acima.
Superfície do produto: /solutions/developers e /solutions/analytics.
Externo: Documento de design do Ristretto e o documento TinyLFU para a teoria da política de admissão.