Algoritmus vyrovnávací paměti

Algoritmus mezipaměti je algoritmus používaný ke správě mezipaměti nebo skupiny dat. Když je mezipaměť plná, rozhodne, která položka má být z mezipaměti odstraněna. Slovo hit rate popisuje, jak často může být požadavek z mezipaměti obsloužen. Výraz latence popisuje, za jak dlouho lze získat položku z mezipaměti. Aloritmy mezipaměti jsou kompromisem mezi rychlostí zásahu a latencí.

Nejefektivnějším algoritmem ukládání do mezipaměti by bylo vždy zahodit informace, které nebudou v budoucnu nejdéle potřeba. Tento optimální výsledek se označuje jako Beladyho optimální algoritmus nebo jasnovidný algoritmus. Vzhledem k tomu, že obecně nelze předpovědět, jak daleko v budoucnosti bude informace potřebná, není tento postup v praxi obecně realizovatelný. Praktické minimum lze vypočítat až po experimentování a lze porovnat účinnost skutečně zvoleného algoritmu kešování s optimálním minimem.
Nejméně používané (LRU): nejprve odstraní nejméně používané položky. Tento algoritmus vyžaduje sledování toho, co bylo kdy použito. To je nákladné, pokud chceme zajistit, aby algoritmus vždy vyřadil nejméně používanou položku. Obecné implementace této techniky vyžadují uchovávat "bity stáří" řádků mezipaměti a sledovat "nejméně používaný" řádek mezipaměti na základě bitů stáří. V takové implementaci se při každém použití řádku cache změní stáří všech ostatních řádků cache. LRU je vlastně rodina algoritmů ukládání do mezipaměti, jejímiž členy jsou: 2Q od Theodora Johnsona a Dennise Shashy a LRU/K od Pata O'Neila, Betty O'Neilové a Gerharda Weikuma.
Nejčastěji používané (MRU): Tento algoritmus odstraní nejprve naposledy použité položky. Tento mechanismus ukládání do mezipaměti se běžně používá pro mezipaměť databáze.
Pseudo-LRU (PLRU): V některých případech je implementace LRU velmi obtížná. V takových případech může stačit vědět, že ve většině případů se odstraní jedna z nejméně používaných položek. Tam lze použít algoritmus PLRU, protože ke své činnosti potřebuje pouze jeden bit na položku mezipaměti.

2-cestná asociativní sada: pro vysokorychlostní mezipaměti CPU, kde je i PLRU příliš pomalá. Z adresy nové položky se vypočítá jedno ze dvou možných míst v cache, kam se smí umístit. LRU z těchto dvou míst je vyřazeno. To vyžaduje jeden bit na dvojici řádků cache, aby se označilo, které z těchto dvou míst bylo nejméně používané.
Přímo mapovaná mezipaměť: pro nejrychlejší mezipaměti procesoru, kde jsou i dvoucestné asociativní mezipaměti příliš pomalé. Z adresy nového prvku se vypočítá jedno místo v mezipaměti, kam smí jít. Cokoli, co tam bylo předtím, je vyřazeno.
Nejméně často používané (LFU): LFU počítá, jak často je položka potřebná. Ty, které se používají nejméně často, se vyřazují jako první.
Adaptive Replacement Cache (ARC): neustále vyvažuje mezi LRU a LFU, aby zlepšila kombinovaný výsledek.
Algoritmus ukládání do mezipaměti více front (MQ): Philbin a Kai Li).

Další věci, které je třeba vzít v úvahu:

Předměty s různou cenou: ponechte si předměty, jejichž získání je drahé, např. ty, jejichž získání trvá dlouho.
Položky zabírající více mezipaměti: Pokud mají položky různou velikost, může se stát, že keš bude chtít vyřadit velkou položku, aby mohla uložit několik menších.
Položky, jejichž platnost časem vyprší: Některé mezipaměti uchovávají informace, jejichž platnost vyprší (např. mezipaměť zpráv, mezipaměť DNS nebo mezipaměť webového prohlížeče). Počítač může položky vyřadit, protože jejich platnost vypršela. V závislosti na velikosti mezipaměti nemusí být nutný žádný další algoritmus pro vyřazování položek.

Existují také různé algoritmy pro udržování koherence mezipaměti. To se týká pouze situace, kdy se pro stejná data používá více nezávislých mezipamětí (například více databázových serverů aktualizujících jeden sdílený datový soubor).

Která místa paměti lze ukládat do mezipaměti pomocí kterých míst mezipaměti

Otázky a odpovědi

Otázka: Co je to algoritmus vyrovnávací paměti?

Odpověď: Algoritmus vyrovnávací paměti je algoritmus používaný ke správě vyrovnávací paměti nebo skupiny dat. Rozhoduje o tom, která položka má být z mezipaměti odstraněna, když je plná.

Otázka: Co je to hit rate?

Odpověď: Hit rate popisuje, jak často může být požadavek z mezipaměti obsloužen.

Otázka: Co popisuje latence?

Odpověď: Latence popisuje, za jak dlouho lze získat položku z mezipaměti.

Otázka: Co je Beladyho optimální algoritmus?

Odpověď: Beladyho optimální algoritmus, známý také jako jasnovidný algoritmus, je efektivní algoritmus ukládání do mezipaměti, který vždy vyřazuje informace, které nebudou v budoucnu nejdéle potřeba. Tento výsledek nelze v praxi obecně realizovat, protože vyžaduje předvídat, co bude potřeba v daleké budoucnosti.

Otázka: Jak funguje metoda LRU (Least Recently Used)?

Odpověď: LRU odstraňuje nejméně používané položky jako první a vyžaduje sledování toho, co bylo kdy použito, pomocí "bitů stáří" pro každý řádek mezipaměti a sledování, který z nich byl použit nejméně nedávno na základě bitů stáří. Při každém použití řádku cache se odpovídajícím způsobem změní stáří všech ostatních řádků cache.

Otázka: Jak funguje funkce MRU (Most Recently Used)?

Odpověď: MRU odstraní nejprve naposledy použité položky a tento mechanismus ukládání do mezipaměti se běžně používá pro mezipaměť databáze.

Otázka: Jaké další algoritmy existují pro udržení koherence mezipaměti?

Odpověď: Existují různé algoritmy pro udržení koherence mezipaměti, když se pro sdílená data používá více nezávislých mezipamětí, například když více databázových serverů aktualizuje jeden sdílený datový soubor.