Invalidação de cache – Existe uma solução geral?

Question

"Existem apenas dois problemas difíceis na Ciência da Computação:invalidação de cache e nomeação de coisas."

Phil Karlton

Existe uma solução ou método geral para invalidar um cache;saber quando uma entrada está obsoleta, para garantir que você sempre obterá dados atualizados?

Por exemplo, considere uma função getData() que obtém dados de um arquivo.Ele o armazena em cache com base na hora da última modificação do arquivo, que verifica sempre que é chamado.
Então você adiciona uma segunda função transformData() que transforma os dados e armazena em cache seu resultado para a próxima vez que a função for chamada.Ele não tem conhecimento do arquivo - como você adiciona a dependência de que se o arquivo for alterado, esse cache se torna inválido?

Você poderia ligar getData() toda vez transformData() é chamado e compare-o com o valor que foi usado para construir o cache, mas isso pode acabar sendo muito caro.

Answer 1

O que você está falando é o encadeamento de dependência ao longo da vida, que uma coisa depende de outra que pode ser modificada fora do controle.

Se você tem uma função idempotente de a, b para c onde, se a e b são os mesmos então c é o mesmo, mas o custo da verificação b é alto, então você também:

1. Aceite que você opera com informações desatualizadas e nem sempre verifique b
2. Faça o seu melhor para fazer a verificação b o mais rápido possível

Você não pode ter seu bolo e comer ...

Se você pode colocar um cache adicional com base em a Por cima, então isso afeta o problema inicial nem um pouco. Se você escolheu 1, então você tem qualquer liberdade que você deu e, portanto, pode cache mais, mas deve se lembrar de considerar a validade do valor em cache de b. Se você escolheu 2, você ainda deve verificar b toda vez, mas pode recorrer ao cache para a E se b check -out.

Se você colocar caches, deve considerar se violou as 'regras' do sistema como resultado do comportamento combinado.

Se você sabe disso a sempre tem validade se b Em seguida, você pode organizar seu cache como assim (pseudocode):

private map<b,map<a,c>> cache // 
private func realFunction    // (a,b) -> c

get(a, b) 
{
    c result;
    map<a,c> endCache;
    if (cache[b] expired or not present)
    {
        remove all b -> * entries in cache;   
        endCache = new map<a,c>();      
        add to cache b -> endCache;
    }
    else
    {
        endCache = cache[b];     
    }
    if (endCache[a] not present)     // important line
    {
        result = realFunction(a,b); 
        endCache[a] = result;
    }
    else   
    {
        result = endCache[a];
    }
    return result;
}

Obviamente camadas sucessivas (digamos x) é trivial enquanto, em cada estágio, a validade da entrada recém -adicionada corresponde ao a:b relacionamento para x:b e x:a.

No entanto, é bem possível que você possa obter três entradas cuja validade era totalmente independente (ou foi cíclica), portanto, nenhuma camada seria possível. Isso significaria que a linha marcada // importante teria que mudar para

if (endcache [a expirado ou não presente)

Answer 2

O problema na invalidação do cache é que o material muda sem sabermos sobre isso. Portanto, em alguns casos, é possível uma solução se houver outra coisa que saiba e puder nos notificar. No exemplo dado, a função getData pode conectar -se ao sistema de arquivos, que sabe sobre todas as alterações nos arquivos, independentemente do processo altera o arquivo, e esse componente, por sua vez, pode notificar o componente que transforma os dados.

Eu não acho que exista alguma correção de magia geral para fazer o problema desaparecer. Mas, em muitos casos práticos, pode muito bem haver oportunidades para transformar uma abordagem baseada em "votação" em uma abordagem "interrompida", que pode fazer com que o problema simplesmente desapareça.

Answer 3

Se você vai getdata () toda vez que fizer a transformação, eliminou todo o benefício do cache.

Para o seu exemplo, parece que uma solução seria para quando você gerar os dados transformados, para também armazenar o nome do arquivo e o último tempo modificado do arquivo dos dados foi gerado (você já armazenou isso em qualquer estrutura de dados retornada pelo getData ( ), basta copiar esse registro na estrutura de dados retornada por transformData ()) e, quando você chama o transformData () novamente, verifique o último tempo modificado do arquivo.

Answer 4

IMHO, Programação Reativa Funcional (FRP) é, de certa forma, uma maneira geral de resolver a invalidação de cache.

Aqui está o porquê:dados obsoletos na terminologia FRP são chamados de falha.Um dos objetivos do FRP é garantir a ausência de falhas.

O FRP é explicado com mais detalhes neste Palestra sobre 'Essência do FRP' e neste Então responde.

No falar o Cells representam um objeto/entidade em cache e um Cell é atualizado se uma de suas dependências for atualizada.

O FRP oculta o código de encanamento associado ao gráfico de dependência e garante que não haja nenhum obsoleto CellS.

---

Outra maneira (diferente do FRP) que consigo pensar é agrupar o valor computado (do tipo b) em algum tipo de mônada escritora Writer (Set (uuid)) b onde Set (uuid) (notação Haskell) contém todos os identificadores dos valores mutáveis ​​​​nos quais o valor calculado b depende.Então, uuid é algum tipo de identificador exclusivo que identifica o valor/variável mutável (digamos, uma linha em um banco de dados) no qual o cálculo b depende.

Combine esta ideia com combinadores que operam neste tipo de gravador Monad e que podem levar a algum tipo de solução geral de invalidação de cache se você usar esses combinadores apenas para calcular um novo b.Tais combinadores (digamos uma versão especial de filter) pegue as mônadas do escritor e (uuid, a)-s como entradas, onde a é um dado/variável mutável, identificado por uuid.

Então, toda vez que você altera os dados "originais" (uuid, a) (digamos, os dados normalizados em um banco de dados do qual b foi calculado) no qual o valor calculado do tipo b depende, então você pode invalidar o cache que contém b se você alterar qualquer valor a em que o calculado b o valor depende, pois com base no Set (uuid) no Writer Monad você pode saber quando isso acontece.

Então, sempre que você modifica algo com um determinado uuid, você transmite essa mutação para todos os cache-s e eles invalidam os valores b que dependem do valor mutável identificado com o referido uuid porque a mônada do Escritor na qual o b está embrulhado posso dizer se isso b depende do que foi dito uuid ou não.

Claro, isso só compensa se você ler com muito mais frequência do que escrever.

---

Uma terceira abordagem prática é usar visualizações materializadas em bancos de dados e usá-las como caches.AFAIK eles também pretendem resolver o problema de invalidação.É claro que isso limita as operações que conectam os dados mutáveis ​​aos dados derivados.

Answer 5

Estou trabalhando em uma abordagem agora baseada em PostSharp e funções de memorização.Já passei pelo meu mentor e ele concorda que é uma boa implementação de cache de forma independente de conteúdo.

Cada função pode ser marcada com um atributo que especifica seu período de expiração.Cada função marcada desta forma é memorizada e o resultado é armazenado no cache, com um hash da chamada da função e parâmetros usados ​​como chave.estou a usar Velocidade para o back-end, que lida com a distribuição dos dados do cache.

Answer 6

Existe uma solução ou método geral para criar um cache, para saber quando uma entrada é obsoleta, para que você sempre obtenha novos dados?

Não, porque todos os dados são diferentes. Alguns dados podem ser "obsoletos" depois de um minuto, outros depois de uma hora, e outros podem ficar bem por dias ou meses.

Em relação ao seu exemplo específico, a solução mais simples é ter uma função de 'verificação de cache' para arquivos, que você chama de ambos getData e transformData.

Answer 7

Não há solução geral, mas:

• Seu cache pode atuar como um proxy (pull). Suponha que seu cache saiba o timestamp da última origem, quando alguém liga getData(), o cache pede à origem o registro de data e hora da última alteração, se o mesmo, ele retorna o cache, caso contrário, atualiza seu conteúdo com a fonte um e retorna seu conteúdo. (Uma variação é o cliente para enviar diretamente o registro de data e hora da solicitação, a fonte retornaria apenas o conteúdo se seu carimbo de data / hora for diferente.)

• Você ainda pode usar um processo de notificação (push), o cache observa a fonte, se a fonte mudar, ele enviará uma notificação para o cache que é então sinalizado como "sujo". Se alguém ligar getData() O cache primeiro será atualizado para a fonte, remova o sinalizador "sujo"; Em seguida, retorne seu conteúdo.

A escolha de um modo geral depende de:

• A frequência: muitas chamadas em getData() preferiria um empurrão para evitar que a fonte seja inundada por uma função Gettimestamp
• Seu acesso à fonte: você está possuindo o modelo de origem? Caso contrário, é provável que você não possa adicionar nenhum processo de notificação.

Nota: Como o uso do registro de data e hora é a maneira como os proxies HTTP tradicionais estão funcionando, outra abordagem é compartilhar um hash do conteúdo armazenado. A única maneira que eu conheço para que duas entidades sejam atualizadas juntas são eu chamo você (puxe) ou você me liga ... (empurre) isso é tudo.

Answer 8

O cache é difícil porque você precisa considerar: 1) o cache é vários nós, precisa de consenso para eles 2) Tempo de invalidação 3) Condição de corrida quando o múltiplo Get/Set acontecer

Esta é uma boa leitura:https://www.confluent.io/blog/turning-the-database-inside-tond-with-apache-samza/

Answer 9

Talvez os algoritmos de cache-oblívoros sejam os mais gerais (ou pelo menos, menos dependentes da configuração de hardware), pois eles usarão o cache mais rápido e seguirão em frente. Aqui está uma palestra do MIT: Algoritmos alheios de cache