Um algoritmo Cache é um algoritmo utilizado para gerir uma cache ou grupo de dados. Quando a cache está cheia, ele decide qual o item que deve ser apagado da cache. A palavra taxa de acerto descreve a frequência com que um pedido pode ser servido a partir da cache. O termo latência descreve durante quanto tempo um item em cache pode ser obtido. As aloritmos de cache são um compromisso entre a taxa de acerto e a latência.

  • O algoritmo de cache mais eficiente seria sempre descartar a informação que não será necessária durante o maior período de tempo no futuro. Este resultado óptimo é referido como o algoritmo óptimo de Belady ou o algoritmo clarividente. Uma vez que é geralmente impossível prever até que ponto no futuro a informação será necessária, isto não é geralmente implementável na prática. O mínimo prático só pode ser calculado após a experimentação, e pode-se comparar a eficácia do algoritmo de cache realmente escolhido com o mínimo óptimo.
  • Menos Usado Recentemente (LRU): apaga primeiro os artigos menos usados recentemente. Este algoritmo exige que se mantenha um registo do que foi utilizado quando. Isto é caro se se quiser ter a certeza de que o algoritmo descarta sempre o item menos recentemente utilizado. As implementações gerais desta técnica requerem que se mantenha "bits de idade" para linhas de cache e que se rastreie a linha de cache "Menos Usado Recentemente" com base nos bits de idade. Em tal implementação, sempre que uma linha de cache é utilizada, a idade de todas as outras linhas de cache muda. A LRU é na realidade uma família de algoritmos de cache com membros, incluindo: 2Q por Theodore Johnson e Dennis Shasha e LRU/K por Pat O'Neil, Betty O'Neil e Gerhard Weikum.
  • Utilizado mais recentemente (MRU): Este algoritmo apaga primeiro os artigos mais recentemente utilizados. Este mecanismo de cache é normalmente utilizado para caches de memória de bases de dados.
  • Pseudo-LRU (PLRU): Existem certos casos em que a LRU é muito difícil de implementar. Nesses casos, pode ser suficiente saber que na maioria dos casos, um dos artigos menos utilizados é eliminado. O algoritmo PLRU pode ser aí utilizado, porque só precisa de um bit por item de cache para funcionar.
  • Conjunto associativo de 2 vias: para caches de CPU de alta velocidade onde até a PLRU é demasiado lenta. O endereço de um novo item é utilizado para calcular uma de duas localizações possíveis na cache onde é permitido ir. A LRU dos dois é descartada. Isto requer um bit por cada par de linhas de cache, para indicar qual das duas foi a menos utilizada recentemente.
  • Cache directamente mapeada: para as caches de CPU de maior velocidade onde mesmo as caches associativas de 2 vias são demasiado lentas. O endereço do novo item é utilizado para calcular o único local na cache para onde é permitido ir. O que quer que lá estivesse antes, é descartado.
  • Menos Usado com Mínima Frequência (LFU): LFU conta a frequência com que um item é necessário. Os que são utilizados com menos frequência são descartados primeiro.
  • Cache de Substituição Adaptativa (ARC): equilíbrio constante entre LRU e LFU, para melhorar o resultado combinado.
  • Algoritmo de caching Multi Queue (MQ): (por Y. Zhou J.F. Philbin e Kai Li).

Outras coisas a considerar:

  • Artigos com custos diferentes: manter artigos que são caros de obter, por exemplo, aqueles que levam muito tempo a obter.
  • Itens que ocupam mais cache: Se os itens tiverem tamanhos diferentes, a cache pode querer descartar um item grande para armazenar vários itens mais pequenos.
  • Itens que expiram com o tempo: Alguns caches guardam informações que expiram (por exemplo, uma cache de notícias, uma cache DNS, ou uma cache de um navegador web). O computador pode descartar itens porque estão expirados. Dependendo do tamanho da cache, não poderá ser necessário mais nenhum algoritmo de cache para descartar itens.

Existem também vários algoritmos para manter a coerência do cache. Isto aplica-se apenas a situações em que múltiplas caches independentes são utilizadas para os mesmos dados (por exemplo, múltiplos servidores de bases de dados actualizando o único ficheiro de dados partilhado).