Invalidação de Cache – Existe uma Solução Geral?

“Existem apenas dois problemas difíceis em 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 input é obsoleta, então você está garantido para sempre obter novos dados?

Por exemplo, considere uma function getData() que obtém dados de um arquivo. Ele armazena em cache com base no horário da última modificação do arquivo, que ele verifica toda vez que é chamado.
Em seguida, você adiciona uma segunda function transformData() que transforma os dados, e armazena em cache seu resultado para a próxima vez em que a function é chamada. Não tem conhecimento do arquivo – como você adiciona a dependência de que, se o arquivo for alterado, esse cache se tornará inválido?

Você poderia chamar getData() toda vez que transformData() for chamado e compará-lo com o valor que foi usado para construir o cache, mas isso pode acabar sendo muito caro.

O que você está falando é o encadeamento da dependência vitalícia, que uma coisa depende de outra que pode ser modificada fora de seu controle.

Se você tem uma function idempotente de a , b para c onde, se b são iguais, então c é o mesmo, mas o custo de checar b é alto, então você quer:

  1. aceitar que você opere em algum momento com informações desatualizadas e nem sempre verifique
  2. faça o seu melhor para fazer a verificação b mais rápido possível

Você não pode ter seu bolo e comê-lo …

Se você puder colocar em camadas um cache adicional baseado em a over the top, isso afetará o problema inicial e não um bit. Se você escolheu 1, então você tem a liberdade que você deu a si mesmo e pode, assim, armazenar mais, mas deve lembrar-se de considerar a validade do valor em cache de b . Se você escolheu 2, você ainda deve checar b toda vez, mas pode voltar para o cache para a if check-out.

Se você colocar caches em camadas, deverá considerar se violou as ‘regras’ do sistema como resultado do comportamento combinado.

Se você sabe que sempre tem validade se b , então você pode organizar seu cache assim (pseudocódigo):

 private map> cache // private func realFunction // (a,b) -> c get(a, b) { c result; map endCache; if (cache[b] expired or not present) { remove all b -> * entries in cache; endCache = new map(); 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 ) são triviais, desde que, a cada estágio, a validade da input recém-adicionada corresponda à relação a : b para x : b x : a .

No entanto, é bem possível que você consiga três inputs cuja validade seja inteiramente independente (ou seja, cíclica), portanto, nenhuma disposição em camadas seria possível. Isso significaria que a linha marcada // importante teria que mudar para

if (endCache [a] expirou ou não está presente)

O problema na invalidação de cache é que as coisas mudam sem que nós saibamos. Então, em alguns casos, uma solução é possível se houver alguma outra coisa que saiba sobre ela e possa nos notificar. No exemplo dado, a function getData pode ser conectada ao sistema de arquivos, que conhece todas as alterações nos arquivos, independentemente do processo que altera o arquivo, e esse componente, por sua vez, poderia notificar o componente que transforma os dados.

Eu não acho que existe alguma mágica geral para fazer o problema desaparecer. Mas, em muitos casos práticos, pode muito bem haver oportunidades de transformar uma abordagem baseada em “pesquisa” em uma baseada em “interrupção”, o que pode fazer com que o problema simplesmente desapareça.

Se você for getData () toda vez que fizer a transformação, eliminará todo o benefício do cache.

Para o seu exemplo, parece que uma solução seria para quando você gerasse os dados transformados, para também armazenar o nome do arquivo e a hora da última modificação do arquivo que os dados foram gerados (você já armazenou isto em qualquer estrutura de dados retornada por getData ), portanto, basta copiar esse registro na estrutura de dados retornada por transformData ()) e, em seguida, quando você chamar transformData () novamente, verifique a hora da última modificação do arquivo.

IMHO, Programação Reativa Funcional (FRP) é, em certo sentido, uma maneira geral de resolver a invalidação do cache.

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

O FRP é explicado em mais detalhes nesta palestra ‘Essence of FRP’ e nesta resposta SO .

Na conversa, os Cell s representam um Objeto / Entidade em cache e uma Cell é atualizada se uma de suas dependencies for atualizada.

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


Outra maneira (diferente do FRP) que eu consigo pensar é envolver o valor computado (do tipo b ) em algum tipo de um escritor Monad Writer (Set (uuid)) b onde Set (uuid) (notação Haskell) contém todos os identificadores dos valores mutáveis ​​dos quais o valor calculado b depende. Portanto, uuid é algum tipo de identificador único que identifica o valor / variável mutável (digamos, uma linha em um database) do qual depende o b computado.

Combine essa idéia com os combinadores que operam nesse tipo de gravador Monad e isso pode 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 do filter ) tomam as mônadas do Writer e (uuid, a) -s como inputs, onde a é uma variável / dados mutáveis, identificada pelo uuid .

Assim, toda vez que você alterar os dados “originais” (uuid, a) (digamos os dados normalizados em um database a partir do qual b foi computado) do qual o valor computado do tipo b depende, você poderá invalidar o cache que contém b se qualquer valor a em que o valor b calculado depende, porque baseado no Set (uuid) no Writer Monad você pode dizer quando isso acontece.

Então, toda vez que você mutar algo com um dado 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 dito uuid porque a mônada do Writer na qual o b é empacotado pode dizer se b depende do dito uuid ou não.

Claro, isso só vale a pena se você ler muito mais do que escreve.


Uma terceira abordagem, prática, é usar visões materializadas em bancos de dados e usá-las como cache-es. AFAIK eles também visam resolver o problema de invalidação. Isso, obviamente, limita as operações que conectam os dados mutáveis ​​aos dados derivados.

Eu estou trabalhando em uma abordagem agora baseada em funções PostSharp e memoizing . Passei pelo meu mentor e ele concorda que é uma boa implementação do cache de maneira independente do conteúdo.

Cada function pode ser marcada com um atributo que especifica seu período de expiração. Cada function marcada dessa maneira é memoizada e o resultado é armazenado no cache, com um hash da chamada de function e os parâmetros usados ​​como chave. Estou usando o Velocity para o backend, que lida com a distribuição dos dados do cache.

Existe uma solução geral ou método para criar um cache, para saber quando uma input é obsoleta, então você está garantido para obter sempre novos dados?

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

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

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

  • Você cache pode atuar como um proxy (pull). Suponha que seu cache saiba o timestamp da última mudança de origem, quando alguém chamar getData() , o cache solicita a origem do timestamp da última mudança, se o mesmo, retorna o cache, caso contrário atualiza seu conteúdo com o de origem e retorna seu conteúdo . (Uma variação é o cliente para enviar diretamente o registro de data e hora na solicitação, a origem só retornaria conteúdo se seu registro de data e hora fosse diferente.)

  • Você ainda pode usar um processo de notificação (push), o cache observa a fonte, se a fonte mudar, ele envia uma notificação para o cache que é então marcado como “sujo”. Se alguém chamar getData() o cache será primeiro atualizado para a fonte, remova o sinalizador “dirty”; então retorne seu conteúdo.

A escolha de um modo geral depende de:

  • A frequência: muitas chamadas em getData() prefeririam um push para evitar que a fonte fosse inundada por uma function getTimestamp
  • Seu access à fonte: você possui o modelo de origem? Caso contrário, você não poderá adicionar nenhum processo de notificação.

Nota: Como o uso do timestamp é a maneira tradicional como os proxies http estão funcionando, outra abordagem é compartilhar um hash do conteúdo armazenado. A única maneira que eu conheço para duas entidades serem atualizadas é ou eu te chamo (puxa) ou você me liga… (empurra) isso é tudo.

cache é difícil porque você precisa considerar: 1) o cache é de múltiplos nós, precisa de um consenso para eles 2) tempo de invalidação 3) condição de corrida quando o get / set múltiplo acontece

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

Talvez os algoritmos alheios ao cache sejam os mais genéricos (ou, pelo menos, menos dependentes de configuração de hardware), já que eles usarão o cache mais rápido primeiro e continuarão a partir daí. Aqui está uma palestra do MIT sobre ele: Cache Oblivious Algorithms