Cache Stampedes São um Problema de Capacidade, Não de Locking

O conselho padrão para um cache stampede é um lock distribuído: o primeiro miss pega o lock, recomputa, todos os outros esperam. Reli esse conselho em março, depois que o O'Reilly Radar publicou Why Capacity Planning Is Back, e uma frase ficou comigo. Sob pressão de capacidade, escreve o autor, "a demanda de pico simplesmente se converte em colapso de fila". O texto é sobre pools de GPU, mas a frase descreve todo cache de lock-on-miss que já depurei.

Então montei um pequeno aparato de stampede para checar minhas intuições: um cache em memória na frente de um upstream falso que leva 400 ms por recomputação e permite 8 chamadas concorrentes, com 500 leituras por segundo espalhadas por 1.000 chaves. O que o experimento continuou mostrando é que o stampede nunca é sobre o cache. É sobre um orçamento de capacidade upstream que a camada de cache gasta sem rastrear. Assim que enquadrei dessa forma, a hierarquia de mitigação se inverteu: o lock distribuído — a resposta que a maioria dos posts busca primeiro — virou o último recurso, e dois mecanismos mais baratos cobriram quase tudo.

O que um miss realmente gasta

Um cache na frente de um recurso caro é um amplificador com um orçamento. Cada miss gasta uma recomputação do orçamento de concorrência do upstream. O upstream no meu aparato comporta 8 recomputações concorrentes a 400 ms cada — um teto de throughput de 20 recomputações por segundo. Enquanto os misses chegam abaixo desse teto, ninguém percebe que o cache existe.

Um stampede é o momento em que a demanda de miss excede esse teto, e ele tem dois gatilhos distintos que exigem correções diferentes:

• Expiração sincronizada. Um deploy, um aquecimento de cache em massa, ou um TTL uniforme dão a milhares de chaves o mesmo instante de expiração. Cada chave só precisa de uma recomputação, mas todas precisam dela agora.
• Expiração de chave quente (hot-key). Uma chave servindo centenas de leituras por segundo expira. Toda leitura durante a janela de recomputação dá miss na mesma chave, e cada uma dispara uma recomputação redundante de trabalho idêntico.

No meu aparato, o caso sincronizado se pareceu com isto: todas as 1.000 chaves aquecidas no mesmo instante com um TTL plano de 60 segundos. Na marca do minuto, toda leitura deu miss. O upstream conseguia reconstruir 20 chaves por segundo, então reabastecer o working set levou 50 segundos — 50 segundos durante os quais a latência de leitura ficou em profundidade de fila vezes 400 ms em vez de microssegundos. O caso de hot-key foi mais agudo: uma única chave a 300 leituras por segundo produziu 120 tentativas concorrentes de recomputação dentro de uma janela de 400 ms, contra um orçamento de 8.

Mesmo sintoma num dashboard — saturação do upstream, penhasco de latência — mas dois problemas diferentes. O enquadramento de capacidade torna a diferença visível: a expiração sincronizada é um problema de agendamento (trabalho legítimo, timing terrível), enquanto a expiração de hot-key é um problema de deduplicação (uma unidade de trabalho, 120 requisitantes).

Lock-on-miss transforma um soluço numa fila

O lock distribuído responde ao problema de deduplicação, então parece atraente. Aqui está o que ele custou no meu aparato.

Um design de lock-on-miss precisa de um TTL de lock mais longo que a recomputação de pior caso, ou o lock expira no meio da recomputação e um segundo cliente começa o mesmo trabalho. O p99 de recomputação do meu upstream falso sob carga era 1,8 segundos, então um TTL de lock honesto era 5 segundos. Então matei o detentor do lock no meio da recomputação — um crash de processo, nada exótico. As 300 leituras por segundo da chave quente se empilharam atrás de um lock que ninguém jamais liberaria. Quando o TTL do lock expirou, 1.500 requisições estavam estacionadas, cada uma segurando uma conexão e uma thread upstream do cache. O soluço era de 400 ms de recomputação; o lock o transformou em 5 segundos de crescimento de fila seguidos por uma rajada de retry sincronizada — 1.500 requisições estampedando no momento em que o lock liberou. Esse é o colapso de fila que o texto do O'Reilly descreve, fabricado pela própria mitigação.

A questão mais profunda é o que o lock otimiza. Ele protege o slot do cache — exatamente um escritor por chave — quando o que precisa de proteção é o orçamento do upstream. Soam parecidos mas divergem sob falha: um lock garante no máximo uma recomputação por chave por período de lock, ao preço de acoplar a latência de cada leitor à saúde do detentor do lock.

Vale notar o que o Facebook de fato construiu quando enfrentou isso em escala. O mecanismo de leases em Scaling Memcache at Facebook (NSDI '13) é regularmente citado como "um lock distribuído", mas lido de perto é um rate limiter com uma política de staleness: o servidor entrega um token de lease para uma chave ausente no máximo uma vez a cada 10 segundos, e clientes que chegam no intervalo ou esperam brevemente ou recebem explicitamente o valor obsoleto para servir. O design protege o orçamento de recomputação do banco de dados e nomeia o trade-off — staleness limitada — no protocolo. Pela minha leitura do artigo, a lição não é "use locks"; é que mesmo a versão disciplinada do locking teve que ganhar formato de orçamento para funcionar.

TTL jitter: a correção certa, geralmente na dose errada

Para expiração sincronizada, a correção de manual é o jitter: adicione aleatoriedade a cada TTL para que as chaves parem de expirar em sincronia. O conselho está correto. O número que viaja com ele — "adicione 10%" — é o que falhou no meu aparato, e a falha tem uma fórmula.

Com ±10% de jitter num TTL de 60 segundos, minhas 1.000 expirações se espalharam por uma janela de 6 segundos: aproximadamente 167 demandas de recomputação por segundo contra um teto de 20. Ainda um stampede — mais educado, cinco vezes mais longo do que o upstream conseguia absorver. A janela de jitter precisa ser larga o suficiente para que o trabalho de recomputação passe pelo throughput do upstream:

required_spread ≥ (keys_expiring × recompute_seconds) / max_concurrency

Para o meu aparato: 1.000 × 0,4 / 8 = 50 segundos de espalhamento mínimo. Num TTL base de 60 segundos isso não é um ajuste de 10% — é jitter na ordem do próprio TTL, algo como ttl × uniform(1.0, 2.0). Assim que dimensionei dessa forma, o stampede sincronizado desapareceu inteiramente: as expirações chegaram abaixo do teto de 20 por segundo e o upstream nunca enfileirou.

Duas coisas tornam o jitter a primeira coisa que busco de qualquer forma. É uma linha de código no momento da escrita, sem custo no caminho de leitura, sem coordenação, sem novos modos de falha. E sua matemática de orçamento é estática — você pode verificar a fórmula acima no papel antes de fazer deploy, o que não é verdade para nenhum lock. O que o jitter não consegue fazer é ajudar a chave quente: uma chave tem uma expiração, e aleatorizar uma única amostra desloca o stampede sem encolhê-lo.

XFetch: um número aleatório por leitura

A chave quente precisa de algo que desacople o refresh da expiração. O mecanismo mais limpo que conheço é a expiração antecipada probabilística — XFetch — de Vattani, Chierichetti e Lowenstein em Optimal Probabilistic Cache Stampede Prevention (VLDB 2015). Armazene dois campos extras ao lado de cada valor: delta, quanto tempo a última recomputação levou, e expiry. Em cada leitura, sorteie um número aleatório:

read(key): value, delta, expiry = cache.get(key) if value is missing or now() - delta * beta * ln(rand()) >= expiry: start = now() value = recompute(key) delta = now() - start cache.set(key, (value, delta, now() + ttl)) return value

rand() é uniforme em (0, 1], então ln(rand()) é negativo e o termo desloca a visão de "agora" do leitor para frente por uma quantidade aleatória escalada ao custo da recomputação. Longe da expiração o deslocamento quase nunca cruza a linha; à medida que a expiração se aproxima, a probabilidade de se voluntariar para o refresh sobe acentuadamente. O artigo prova que a distribuição exponencial é o formato ótimo para essa aposta — minimiza a chance de uma recomputação sincronizada sem inflar refreshes antecipados desperdiçados. beta tem padrão 1; aumentá-lo troca refreshes mais antecipados por proteção mais forte contra stampede.

Contra minha chave quente de 300 leituras por segundo, o XFetch com beta = 1 produziu entre 1 e 3 recomputações concorrentes por ciclo de expiração ao longo de 50 ciclos, contra 120 para a expiração ingênua. Não exatamente uma — o XFetch é probabilístico, e dois leitores podem ambos ganhar na loteria dentro da mesma janela de delta — mas duas ordens de magnitude melhor, com zero coordenação, zero estado compartilhado além dos dois campos extras, e nenhuma mudança de comportamento quando um nó morre.

Três armadilhas que encontrei nos meus próprios testes valem ser nomeadas. Primeira, o envelope: delta e expiry têm que viver com o valor, o que significa tocar o formato de serialização de toda entrada de cache — uma migração, não uma virada de flag. Segunda, chaves frias não ganham nada: uma chave lida uma vez por minuto com um TTL de 60 segundos quase não tem leituras perto da expiração para se voluntariar, então ela simplesmente expira e dá miss como antes. O XFetch protege chaves cuja taxa de leitura é alta em relação a 1/delta, que é exatamente a população de hot-keys — tudo bem, mas vale saber antes de esperar que ele corrija a taxa de miss geral. Terceira, um upstream lento envenena o delta: uma recomputação atípica de 1,8 segundos armazenada como o novo delta faz as leituras subsequentes refrescarem 4,5× mais cedo do que o necessário, e sob degradação sustentada do upstream esse laço de feedback gasta mais orçamento exatamente quando o orçamento está mais escasso. Limitar (clamp) o delta a um teto corrigiu isso no meu aparato.

Para caches em processo a mesma ideia já vem pronta: o refreshAfterWrite do Caffeine serve o valor antigo enquanto exatamente uma recarga assíncrona roda por chave, memoizando tentativas de refresh redundantes. Isso cobre o caso de processo único da forma como o XFetch cobre o caso de cache compartilhado. E se a supressão de duplicatas dentro de um processo for o problema de fato, a coalescência single-flight é a ferramenta precisa — escrevi sobre esse padrão separadamente nas minhas notas de single-flight em Rust, incluindo a matemática de por que ele para de funcionar assim que o processo vira uma frota.

Quando um lock de verdade vale a pena

Depois de tudo isso, restam três situações em que eu ainda faria deploy de um lock distribuído no caminho do miss:

• A recomputação não é idempotente. Se a regeneração tem efeitos colaterais — escreve em algum lugar, incrementa uma cota, dispara um job downstream — então 2 recomputações concorrentes não são trabalho desperdiçado mas um bug de correção. Mecanismos probabilísticos toleram duplicatas por design; aqui duplicatas não são toleráveis.
• O orçamento é tão pequeno que duplicatas o estouram. Uma API de terceiros permitindo 10 chamadas por minuto não tem espaço para os ocasionais 3 refreshes concorrentes do XFetch. Quando o orçamento é de um único dígito, "raramente mais de um" não é uma garantia na qual apostar.
• Exatamente-uma recomputação deve valer entre regiões. Caches multi-região com um único caminho de regeneração autoritativo precisam de coordenação real; nenhuma quantidade de aleatoriedade local fornece isso.

Mesmo então, o lock deve ter formato de lease: um token com taxa de emissão limitada por chave e uma política explícita de servir obsoletos para todos que não o detêm, que é o design do Facebook. Um SETNX simples com um TTL e esperadores bloqueados é a versão que converteu meu soluço de 400 ms numa fila de 5 segundos.

O critério que de fato uso

O diagrama abaixo é o formato que eu fico desenhando em quadros brancos: concorrência do upstream ao longo do tempo para o mesmo evento de expiração sob cada mitigação, contra uma linha de capacidade fixa.

​

A sequência de decisão, em termos de orçamento:

1. Sempre: jitter, dimensionado pela fórmula. Calcule keys × delta / concurrency e faça a janela de jitter pelo menos tão larga quanto isso. Uma linha, sem custo no caminho de leitura, elimina a expiração sincronizada. Se o espalhamento calculado exceder o que sua tolerância a staleness permite, isso não é uma falha do jitter — é o sistema te dizendo que o upstream está subdimensionado para seu working set.
2. Chaves quentes: XFetch, ou refresh-ahead em processo. Dois campos extras e um número aleatório por leitura compram uma redução de 100× nas recomputações duplicadas para chaves de alto tráfego. Limite (clamp) o delta.
3. Supressão de duplicatas dentro de um processo: single-flight. A deduplicação exata mais barata que existe, mas sua garantia termina na fronteira do processo.
4. Exatamente-um na frota inteira: um lease, não um lock. Taxa de emissão limitada por chave, servir obsoletos explícito para não-detentores, e a aceitação de que a latência do leitor agora está acoplada à saúde do detentor.

O que mudou para mim depois do reenquadramento de capacidade é a ordem. Eu costumava começar no passo 4 porque é o mecanismo mais geral. Ele também é o único que adiciona um modo de falha em vez de remover um.

Conclusões

• Um stampede é demanda de miss excedendo o orçamento de recomputação do upstream; identifique se o gatilho é expiração sincronizada (agendamento) ou uma chave quente (deduplicação) antes de escolher uma correção.
• O TTL jitter só funciona quando a janela é larga o suficiente: pelo menos keys × recompute_time / max_concurrency. O folclore dos 10% é um placeholder, não um cálculo.
• O XFetch custa dois campos armazenados e um número aleatório por leitura, e cortou as recomputações duplicadas em duas ordens de magnitude na minha chave quente. Limite (clamp) o delta armazenado contra outliers de recomputação lenta.
• O lock-on-miss acopla a latência de cada leitor à saúde do detentor do lock; um único detentor que crashou estacionou 1.500 requisições no meu aparato. Se você precisa de exatamente-um, construa um lease com uma política de servir obsoletos.
• Recorra ao lock quando a recomputação for não-idempotente, o orçamento do upstream for de um único dígito, ou exatamente-uma-vez tiver que valer entre regiões. Evite-o em todo o resto — os mecanismos mais baratos protegem o orçamento sem adicionar um coordenador ao caminho de leitura.