Porque é que a invalidação do cache é considerada difícil?

Presumo que esteja a referir-se à citação frequentemente repetida sobre as "duas coisas difíceis na Informática: a invalidação do cache e a atribuição de nomes às coisas". (Às vezes humoristicamente estendido como "cache invalidation, naming things, and off-by-one errors")

Isso se aplica tanto em programação quanto em hardware: É fácil reter uma cópia de algo. É muito mais difícil saber quando deixar essa cópia ir, e em vez disso voltar a buscá-la a partir do item original. Porque é um problema geral, eu vou responder a um nível alto.

geralmente, você tem duas razões para armazenar um pedaço de dados:

1. É relativamente caro ir buscar os dados na primeira vez.
2. Você espera ler os mesmos dados várias vezes, então há um benefício em manter os dados localmente para evitar a despesa de ir buscar os dados mais de uma vez.

Isto aplica-se a caches em todos os níveis, quer seja um cache de hardware que retém uma cópia da memória externa perto da CPU, ou um web browser que retém uma cópia de um documento recuperado de um servidor web.

Caching é atractivo porque poupa tempo, eliminando o custo de ler o original quando o lê mais tarde. Mas e se o valor original puder mudar? Como você garante que cada cópia em cache no sistema eventualmente reflete os dados atualizados, sem incorrer em custos que excedam o benefício do cache? E, se os dados podem ser atualizados por vários atores no sistema, como você garante que todos vejam uma série consistente de atualizações?

Por exemplo, suponha que você tenha uma página web que poderia ser colocada em cache por milhares ou milhões de navegadores da web. Isso poupa tanto a latência como a largura de banda: Os browsers vão buscar uma cópia uma vez, e não precisam de consultar o servidor web novamente. Mas e se a página no servidor mudar? Não vai enviar uma mensagem aos milhares ou milhões de navegadores para dizer-lhes para a ir buscar novamente.

Neste exemplo, os navegadores precisam de uma política para saber quando voltar a consultar o servidor para ver se a página mudou. E, a política certa para qualquer URL será diferente dependendo das atualizações esperadas, como ter uma data de validade no cache, enviar um pedido "Ei, isso mudou?" mais leve para o servidor, e assim por diante. A resposta certa nem sempre é óbvia, e é fácil acertar "a maior parte do tempo" e ignorar um modo de falha obscuro.

Likewise para sistemas de arquivos de rede, sistemas de arquivos locais se os programas possuem caches internos, bancos de dados com múltiplos processos lendo o banco de dados, e assim por diante.

Caches de memória de hardware, embora definitivamente difícil, talvez seja mais fácil do que sistemas de computadores distribuídos: Se todos os acessos a uma determinada memória física passarem por um controlador comum, então pelo menos o controlador comum tem uma chance de poder informar a todos os caches acima sobre uma escrita de alguma forma oportuna. O sistema de memória é, pelo menos, auto-contido. Mesmo assim, você ainda precisa garantir que as mensagens de invalidação sejam processadas de uma maneira que garanta que as atualizações de memória pareçam consistentes para todos os leitores, e fazer isso com eficiência ainda é complicado.

Sem aprofundar em todos os protocolos possíveis para invalidação, essa é a essência do problema.