Cache stampede - Cache stampede

Um estouro de cache é um tipo de falha em cascata que pode ocorrer quando sistemas de computação massivamente paralelos com mecanismos de cache ficam sob carga muito alta. Esse comportamento às vezes também é chamado de empilhamento de cães .

Para entender como ocorrem os stampedes de cache, considere um servidor da web que usa memcached para armazenar páginas renderizadas em cache por algum período de tempo, para facilitar a carga do sistema. Sob carga particularmente alta para um único URL, o sistema permanece responsivo enquanto o recurso permanece em cache, com as solicitações sendo tratadas acessando a cópia em cache. Isso minimiza a cara operação de renderização.

Sob carga baixa, perdas de cache resultam em um único recálculo da operação de renderização. O sistema continuará como antes, com a carga média mantida muito baixa devido à alta taxa de acertos do cache.

No entanto, sob carga muito pesada, quando a versão em cache dessa página expira, pode haver simultaneidade suficiente no farm de servidores para que vários threads de execução tentem renderizar o conteúdo dessa página simultaneamente. Sistematicamente, nenhum dos servidores simultâneos sabe que os outros estão fazendo a mesma renderização ao mesmo tempo. Se uma carga suficientemente alta estiver presente, isso pode por si só ser suficiente para causar o colapso do congestionamento do sistema por meio do esgotamento de recursos compartilhados. O colapso do congestionamento impede que a página seja completamente renderizada e armazenada em cache novamente, pois toda tentativa de fazer isso atinge o tempo limite. Assim, o estouro do cache reduz a taxa de acertos do cache a zero e mantém o sistema continuamente em colapso de congestionamento enquanto tenta regenerar o recurso enquanto a carga permanecer muito pesada.

Para dar um exemplo concreto, suponha que a página em consideração leve 3 segundos para renderizar e temos um tráfego de 10 solicitações por segundo. Então, quando a página em cache expira, temos 30 processos simultaneamente recalculando a renderização da página e atualizando o cache com a página renderizada.

Uso típico de cache

Abaixo está um padrão de uso de cache típico para um item que precisa ser atualizado a cada unidade ttl de tempo: 

function fetch(key, ttl) {
    value ← cache_read(key)
    if (!value) {
        value ← recompute_value()
        cache_write(key, value, ttl)
    }
    return value
}

Se a função recompute_value () demorar muito e a chave for acessada freqüentemente, muitos processos irão chamar simultaneamente recompute_value () após a expiração do valor do cache.

Em aplicações web típicas, a função recompute_value () pode consultar um banco de dados, acessar outros serviços ou realizar alguma operação complicada (razão pela qual este cálculo específico está sendo armazenado em cache em primeiro lugar). Quando a taxa de solicitação é alta, o banco de dados (ou qualquer outro recurso compartilhado) sofrerá uma sobrecarga de solicitações / consultas, o que pode, por sua vez, causar um colapso do sistema.

Mitigação de estouro de cache

Diversas abordagens foram propostas para mitigar os estouro de cache. (Também conhecido como prevenção dogpile) Eles podem ser agrupados aproximadamente em 3 categorias principais.

Trancando

Para evitar múltiplas recomputações simultâneas do mesmo valor, em caso de perda de cache, um processo tentará adquirir o bloqueio para aquela chave de cache e recalculá-lo apenas se adquiri-lo.

Existem diferentes opções de implementação para o caso em que o bloqueio não é adquirido:

  • Espere até que o valor seja recomputado
  • Retorne um "não encontrado" e faça com que o cliente trate a ausência do valor adequadamente
  • Mantenha um item obsoleto no cache para ser usado enquanto o novo valor é recomputado

Se implementado corretamente, o bloqueio pode evitar completamente a debandada, mas requer uma gravação extra para o mecanismo de bloqueio. Além de dobrar o número de gravações, a principal desvantagem é uma implementação correta do mecanismo de bloqueio que também cuida de casos extremos, incluindo falha do processo de obtenção do bloqueio, ajuste de um tempo de vida para o bloqueio, condições de corrida , e assim por diante.

Recomputação externa

Esta solução move a recomputação do valor do cache dos processos que precisam dele para um processo externo. A recomputação do processo externo pode ser acionada de diferentes maneiras:

  • Quando o valor do cache se aproxima de sua expiração
  • Periodicamente
  • Quando um processo que precisa do valor encontra uma falha de cache

Essa abordagem requer mais uma parte móvel - o processo externo - que precisa ser mantida e monitorada. Além disso, esta solução requer separação / duplicação de código não natural e é mais adequada para chaves de cache estáticas (ou seja, não geradas dinamicamente, como no caso de chaves indexadas por um id).

Vencimento antecipado probabilístico

Com essa abordagem, cada processo pode recalcular o valor do cache antes de sua expiração, tomando uma decisão probabilística independente, em que a probabilidade de realizar a recomputação antecipada aumenta à medida que nos aproximamos da expiração do valor. Uma vez que a decisão probabilística é feita de forma independente por cada processo, o efeito da debandada é mitigado porque menos processos expirarão ao mesmo tempo.

A implementação a seguir com base em uma distribuição exponencial demonstrou ser ótima em termos de sua eficácia na prevenção de debandada e como recomputações precoces podem acontecer. 

function x-fetch(key, ttl, beta=1) {
    value, delta, expiry ← cache_read(key)
    if (!value || time() - delta * beta * log(rand(0,1)) ≥ expiry) {
        start ← time()
        value ← recompute_value()
        delta ← time() – start
        cache_write(key, (value, delta), ttl)
    }
    return value
}

O parâmetro beta pode ser definido com um valor maior que 1 para favorecer recomputações anteriores e reduzir ainda mais os estampidos, mas os autores mostram que definir beta = 1 funciona bem na prática. A variável delta representa o tempo para recalcular o valor e é usada para dimensionar a distribuição de probabilidade de forma adequada.

Essa abordagem é simples de implementar e reduz com eficácia os stampedes de cache, favorecendo automaticamente as recomputações iniciais quando a taxa de tráfego aumenta. Uma desvantagem é que é preciso mais memória em cache, pois precisamos agrupar o delta de valor com o item de cache - quando o sistema de cache não suporta a recuperação do tempo de expiração da chave, também precisamos armazenar a expiração (ou seja, o tempo ( ) + ttl ) no pacote.

Referências

links externos