Algoritmy vyrovnávací paměti: přehled strategií a principů

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.