Un algorithme de cache est un algorithme utilisé pour gérer un cache ou un groupe de données. Lorsque la mémoire cache est pleine, il décide quel élément doit être supprimé de la mémoire cache. Le terme "taux de réussite" décrit la fréquence à laquelle une demande peut être traitée à partir du cache. Le terme latence décrit la durée pendant laquelle un élément mis en cache peut être obtenu. Les alorithmes du cache sont un compromis entre le taux de réussite et la latence.

  • L'algorithme de mise en cache le plus efficace serait de toujours rejeter les informations qui ne seront plus nécessaires le plus longtemps à l'avenir. Ce résultat optimal est appelé l'algorithme optimal de Belady ou l'algorithme de clairvoyance. Comme il est généralement impossible de prédire jusqu'à quand les informations seront nécessaires dans l'avenir, cette méthode n'est généralement pas applicable dans la pratique. Le minimum pratique ne peut être calculé qu'après expérimentation, et on peut comparer l'efficacité de l'algorithme de cache réellement choisi avec le minimum optimal.
  • Les moins récemment utilisés (LRU) : supprime d'abord les articles les moins récemment utilisés. Cet algorithme nécessite de garder une trace de ce qui a été utilisé et à quel moment. Cela coûte cher si l'on veut s'assurer que l'algorithme élimine toujours l'article le moins récemment utilisé. Les implémentations générales de cette technique nécessitent de conserver des "bits d'âge" pour les lignes de cache et de suivre la ligne de cache "Le moins récemment utilisé" en fonction des bits d'âge. Dans cette implémentation, chaque fois qu'une ligne de cache est utilisée, l'âge de toutes les autres lignes de cache change. LRU est en fait une famille d'algorithmes de mise en cache dont les membres comprennent : 2Q de Theodore Johnson et Dennis Shasha et LRU/K de Pat O'Neil, Betty O'Neil et Gerhard Weikum.
  • Le plus récemment utilisé (MRU) : Cet algorithme supprime d'abord les éléments les plus récemment utilisés. Ce mécanisme de mise en cache est couramment utilisé pour les caches de la mémoire des bases de données.
  • Pseudo-LRU (PLRU) : Il y a certains cas où la LRU est très difficile à mettre en œuvre. Dans ces cas, il peut suffire de savoir que, dans la plupart des cas, l'un des éléments les moins récemment utilisés est supprimé. L'algorithme PLRU peut être utilisé dans ce cas, car il n'a besoin que d'un bit par élément de cache pour fonctionner.
  • Ensemble associatif bidirectionnel : pour les caches CPU à grande vitesse où même le PLRU est trop lent. L'adresse d'un nouvel élément est utilisée pour calculer l'un des deux emplacements possibles dans le cache où il est autorisé à aller. Le LRU des deux est éliminé. Cela nécessite un bit par paire de lignes de cache, pour indiquer lequel des deux a été le moins récemment utilisé.
  • Direct-mapped cache : pour les caches CPU les plus rapides où même les caches associatifs bidirectionnels sont trop lents. L'adresse du nouvel élément est utilisée pour calculer le seul endroit du cache où il est autorisé à aller. Tout ce qui était là avant est jeté.
  • Le moins fréquemment utilisé (LFU) : LFU compte le nombre de fois qu'un article est nécessaire. Ceux qui sont utilisés le moins souvent sont d'abord jetés.
  • Adaptive Replacement Cache (ARC) : équilibre constamment entre LRU et LFU, pour améliorer le résultat combiné.
  • Algorithme de mise en cache de la multiplicité des files d'attente (MQ) : (par Y. Zhou J.F. Philbin et Kai Li).

Autres éléments à prendre en compte :

  • Articles de coût différent : conservez les articles qui sont chers à obtenir, par exemple ceux qui prennent beaucoup de temps à obtenir.
  • Les objets occupant plus de place dans la mémoire cache : Si les objets ont des tailles différentes, la mémoire cache peut vouloir jeter un grand objet pour en stocker plusieurs plus petits.
  • Les articles qui expirent avec le temps : Certains caches conservent des informations qui expirent (par exemple, un cache de nouvelles, un cache DNS ou un cache de navigateur web). L'ordinateur peut se débarrasser des éléments parce qu'ils sont expirés. En fonction de la taille du cache, aucun autre algorithme de mise en cache n'est nécessaire pour éliminer les éléments.

Divers algorithmes existent également pour maintenir la cohérence du cache. Cela ne s'applique qu'aux situations où plusieurs caches indépendants sont utilisés pour les mêmes données (par exemple, plusieurs serveurs de base de données mettant à jour le même fichier de données partagé).