Invalidação de cache – Existe uma solução geral?
-
19-09-2019 - |
Pergunta
"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.
Solução
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:
- Aceite que você opera com informações desatualizadas e nem sempre verifique
b
- 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)
Outras dicas
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.
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.
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 Cell
s 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 Cell
S.
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.
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.
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
.
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.
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/
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