Algoritmus vyrovnávací paměti rozhoduje, kterou položku odstranit, když je mezipaměť plná. Jde o formu algoritmu mezipaměti, která vyvažuje úspěšnost zásahů (hit rate) a dobu odezvy — tedy latenci při získání položky.

Základní principy

Cílem je minimalizovat počet chyb (miss) při současném respektování omezení zdrojů. Ideál představuje znalost budoucích požadavků, avšak v praxi se používají heuristiky, které sledují frekvenci nebo nedávné použití položek.

Hlavní strategie

  • Beladyho optimální algoritmus: teoretický optimální postup, který vždy zvolí položku, kterou nejdříve v budoucnu nepotřebujeme — Beladyho optimální algoritmus slouží jen jako referenční minimum.
  • LRU (Least Recently Used): vyřadí položku, která byla nejdéle nepoužita; vyžaduje sledování pořadí použití. Do této rodiny patří více variant a v literatuře je často diskutována jako součást širší rodiny LRU.
  • MRU (Most Recently Used): naopak odstraní nejnověji použité položky; někdy výhodné v určitých typech databázových cache MRU.
  • LFU (Least Frequently Used): udržuje čítače přístupů a odstraňuje položky s nejnižší frekvencí použití.
  • PLRU (Pseudo-LRU): aproximace LRU s nízkými náklady, obvykle jeden bit na položku nebo pár položek, vhodná tam, kde plné LRU není praktické.
  • Asociativní přístupy: dvoucestné (2-way) asociativní sety a přímo mapované cache nabízejí kompromis mezi rychlostí a složitostí řízení náhrad; dvoucestné používají jeden bit pro výběr z dvojice, přímo mapované okamžitě přepíše dané místo.
  • Adaptivní a vícekolejné: algoritmy jako ARC (Adaptive Replacement Cache) nebo vícefrontové MQ kombinují principy LRU a LFU a adaptují se podle pracovního zatížení.

Další faktory ovlivňující volbu

  • Různé náklady na získání položky — upřednostnit drahé položky.
  • Proměnlivá velikost položek — velké objekty mohou vyžadovat jiné metody vyřazování.
  • Platnost dat (TTL) — u cache s expirační dobou nemusí být potřeba složitý náhradní algoritmus.

Koherence a více cache

V prostředích s více nezávislými cache (např. více serverů sdílejících data) je třeba řešit koherenci mezipaměti a synchronizaci aktualizací; viz otázky týkající se koherence mezipaměti.