Cache

Ukládání do mezipaměti je termín používaný v informatice. Myšlenka cache (vyslovuje se "keš" /ˈkæʃ/ KASH ) je velmi jednoduchá: Získání výsledku výpočtu je velmi často časově náročné, takže uložení výsledku je obecně dobrý nápad. Používají se dva druhy paměťových médií: Jedno je obvykle poměrně velké, ale přístup k němu je "pomalý"; druhé je přístupné mnohem rychleji, ale obecně je malé. Úplně základní myšlenka ukládání do mezipaměti spočívá v tom, že se pro kopie dat použije médium, ke kterému je rychlý přístup. Mezi kopií a originálem není žádný rozdíl. Přístup k původním datům může trvat dlouho nebo může být nákladný (například: výsledky složitého problému, jehož řešení trvá dlouho). Z tohoto důvodu je mnohem "levnější" jednoduše použít kopii dat z mezipaměti. Jinak řečeno, mezipaměť je dočasný úložný prostor, který obsahuje kopie často používaných dat. Pokud je v této mezipaměti kopie dat, je rychlejší použít tuto kopii než znovu načítat nebo počítat původní data. Tím se zkrátí průměrná doba potřebná k přístupu k datům. Vložení nové hodnoty do mezipaměti často znamená, že je třeba nahradit starší hodnotu. Existují různé nápady (obvykle nazývané "strategie"), jak vybrat hodnotu, která má být nahrazena.

Vyrovnávací paměť je velmi podobná mezipaměti. Liší se tím, že klient přistupující k datům ve vyrovnávací paměti ví, že existuje vyrovnávací paměť; vyrovnávací paměť spravuje aplikace. U vyrovnávací paměti nemusí klient přistupující k datům vědět, že existuje vyrovnávací paměť.

Typické počítačové aplikace přistupují k datům velmi podobným způsobem. Předpokládejme, že data jsou strukturována do "bloků", ke kterým lze přistupovat jednotlivě. Když aplikace přistupuje k bloku, je velmi pravděpodobné, že bude přistupovat také k bloku, který je "blízký" původnímu bloku (nebo na něj bude odkazovat). Tomuto jevu se říká lokálnost reference. Existují různé druhy této "lokality". Lokalita reference je jedním z důvodů, proč mezipaměti dobře fungují v mnoha oblastech výpočetní techniky.

Aby cache dobře fungovala, je v porovnání s celkovým objemem dat malá. Čím větší je mezipaměť, tím déle trvá vyhledání záznamu. Větší cache jsou také dražší na vytvoření.

Jak fungují mezipaměti

Mezipaměť je blok paměti pro ukládání dat, která budou pravděpodobně znovu použita. Mezipaměť často používá procesor a pevný disk, stejně jako webové prohlížeče a webové servery.

Mezipaměť se skládá z mnoha záznamů, které se nazývají pool. Každá položka obsahuje údaj (bit dat), který je kopií údaje na jiném místě. Mezipaměti obvykle používají tzv. záložní úložiště. Přístup k záložním úložištím je ve srovnání s mezipamětí pomalý nebo drahý. Například disková mezipaměť používá jako záložní úložiště pevný disk. Ke každému záznamu je také připojena malá informace, která se nazývá značka. Tato značka slouží k vyhledání místa, kde jsou uložena původní data.

Keše pro čtení

Klient (procesor, webový prohlížeč, operační systém), který chce přistupovat k datům, o nichž se domnívá, že se nacházejí v záložním úložišti, nejprve zkontroluje, zda je lze nalézt v mezipaměti. Pokud lze data v mezipaměti nalézt, klient je může použít a nemusí využívat hlavní paměť. Tomuto postupu se říká "shoda s mezipamětí". Program webového prohlížeče tedy může například zkontrolovat svou místní mezipaměť na disku, aby zjistil, zda má k dispozici místní kopii obsahu webové stránky na určité adrese URL. V tomto příkladu je adresa URL značkou a obsah webové stránky je datem.

Další situací, která může nastat, je, že údaj se značkou nelze v keši nalézt. Tato situace se označuje jako chybějící mezipaměť. Datový údaj je třeba načíst ze záložního úložiště. Obvykle se zkopíruje do mezipaměti, takže příště již není třeba jej ze záložního úložiště načítat.

Velikost mezipaměti je omezená. Aby se uvolnilo místo pro dříve neuložený záznam, může být nutné z mezipaměti odstranit jiný záznam. K vyhledání záznamu, který by měl být nejlépe odstraněn, se používají speciální pravidla. Tato pravidla se obvykle nazývají heuristika. Heuristiky používané k nalezení záznamu se nazývají zásady nahrazení. Velmi jednoduché pravidlo, které se používá, se nazývá Least recently used (neboli LRU). Jednoduše se vezme záznam, který byl použit nejdéle. Další heuristiky jsou uvedeny u algoritmu vyrovnávací paměti ..

Mezipaměti pro zápis

Mezipaměť lze použít i pro zápis dat; výhodou je, že klient může pokračovat v práci, jakmile je záznam zapsán do mezipaměti; nemusí čekat, až bude záznam zapsán do záložního úložiště.

Záznam však musí být v určitém okamžiku zapsán do záložního úložiště. Čas, kdy k tomu dojde, je řízen zásadami zápisu.

Při zápisu do mezipaměti je každý záznam okamžitě zapsán do záložního úložiště a zároveň je uložen do mezipaměti.

Druhou možností je zapisovat pouze do mezipaměti a do záložního úložiště zapisovat později. Tento postup se nazývá write-back (nebo write-behind) cache. Mezipaměť označuje záznamy, které ještě nebyly zapsány do záložního úložiště; použitá značka se často označuje jako dirty flag. Než jsou záznamy z mezipaměti odstraněny, jsou zapsány do záložního úložiště. Tento postup se označuje jako líný zápis. Chybějící zápis do cache (který vyžaduje nahrazení bloku jiným) bude často vyžadovat dva přístupy do paměti: jeden k získání potřebného údaje a druhý k zápisu nahrazených dat z cache do úložiště.

Zásady ukládání do mezipaměti mohou také říkat, že určitý údaj musí být zapsán do mezipaměti. Klient mohl v datové schránce provést mnoho změn. Poté, co s tím skončí, může mezipaměti výslovně říci, aby datum zapsala zpět.

Alokace bez zápisu je zásada mezipaměti, při které se do mezipaměti ukládá pouze čtení. Tím se zabrání potřebě zpětného zápisu nebo zápisu do mezipaměti. Zápisy se do záložního úložiště provádějí neustále.

Klient není aplikací, která mění data v záložním úložišti. Pokud se data v záložním úložišti změnila, kopie v mezipaměti bude zastaralá nebo neaktuální. Případně pokud klient aktualizuje data v mezipaměti, kopie těchto dat v jiných mezipamětech budou zastaralé. Existují speciální komunikační protokoly, které umožňují správcům mezipaměti vzájemně komunikovat, aby byla data smysluplná. Tyto protokoly se nazývají koherenční protokoly.

Schéma paměti cache procesoru

Výběr položky, kterou chcete nahradit

Keš je malá a většinu času je plná nebo téměř plná. Když se tedy přidá nová hodnota, musí se odstranit stará. Tento výběr lze provést různými způsoby:

Kdo dřív přijde, ten dřív odejde: Jednoduše nahraďte záznam, který byl do mezipaměti přidán nejdéle.
Nejméně používané: Tato myšlenka je podobná výše uvedenému FIFO, ale když je položka použita, aktualizuje se její časové razítko/stáří.
Nejméně používané: Opět podobně jako v případě FIFO, místo časového razítka použijte čítač, který se inkrementuje při každém použití položky.
Náhodný výběr položky

Historie

Slovo cache bylo poprvé použito v oblasti výpočetní techniky v roce 1967, kdy byl připraven vědecký článek k publikaci v časopise IBM Systems Journal. Článek pojednával o novém vylepšení paměti v modelu 85. Model 85 byl počítač produktové řady IBM System/360. Redaktor časopisu chtěl lepší výraz pro vysokorychlostní vyrovnávací paměť, který byl v článku použit. Nedostal žádný podnět a navrhl cache, z francouzského cacher, což znamená "schovávat". Článek byl publikován počátkem roku 1968 a autoři byli společností IBM vyznamenáni. Jejich práce byla široce přijata a vylepšena. Cache se brzy stala v počítačové literatuře standardně používanou.

Kde se používají mezipaměti

Mezipaměť procesoru

Malé paměti na čipu procesoru nebo v jeho blízkosti mohou být rychlejší než mnohem větší hlavní paměť. Většina procesorů od 80. let 20. století používá jednu nebo více mezipamětí. Moderní univerzální procesory uvnitř osobních počítačů jich mohou mít až půl tuctu. Každá mezipaměť může být specializovaná na jinou část úlohy provádění programů.

Diskové mezipaměti

Mezipaměť procesoru je obecně spravována výhradně hardwarově, ostatní mezipaměti jsou spravovány různými druhy softwaru. Operační systém obvykle spravuje stránkovou mezipaměť v operační paměti. Uživatelé mimo oblast informatiky obvykle nazývají tuto mezipaměť virtuální pamětí. Spravuje ji jádro operačního systému.

Moderní pevné disky mají vyrovnávací paměť disku. Někdy se jim říká "disková vyrovnávací paměť", ale to je špatně. Hlavní funkcí těchto vyrovnávacích pamětí je řazení zápisů na disk a správa čtení. Opakované zásahy do vyrovnávací paměti jsou vzácné, protože vyrovnávací paměť je ve srovnání s velikostí pevného disku velmi malá.

Místní pevné disky jsou rychlé ve srovnání s jinými úložnými zařízeními, jako jsou vzdálené servery, místní páskové jednotky nebo optické jukeboxy. Použití místních pevných disků jako mezipaměti je hlavní koncepcí hierarchické správy úložišť.

Webové mezipaměti

Webové prohlížeče a webové proxy servery používají mezipaměť k ukládání předchozích odpovědí z webových serverů, například webových stránek. Webové mezipaměti snižují množství informací, které je třeba přenášet po síti. Informace dříve uložené ve vyrovnávací paměti lze často znovu použít. Tím se snižuje šířka pásma a nároky webového serveru na zpracování a pomáhá se zlepšit odezva uživatelů webu.

Moderní webové prohlížeče používají vestavěnou webovou mezipaměť, ale někteří poskytovatelé internetových služeb nebo organizace používají také cachovací proxy server. Jedná se o webovou mezipaměť, která je sdílena všemi uživateli dané sítě.

Vyhledávače také často zpřístupňují indexované webové stránky ze své mezipaměti. Například Google u každého výsledku vyhledávání uvádí odkaz "Cached". To je užitečné, když jsou webové stránky dočasně nedostupné z webového serveru.

Ukládání do mezipaměti v nespolehlivých sítích

Zápis skrz je běžný v nespolehlivých sítích (např. Ethernet LAN). Protokol, který se používá k zajištění toho, aby data v zapisovací mezipaměti dávala smysl, když se používá několik zapisovacích mezipamětí, je v takovém případě velmi složitý.

Například mezipaměti webových stránek a mezipaměti síťových souborových systémů na straně klienta (jako jsou mezipaměti v systémech NFS nebo SMB) jsou obvykle určeny pouze pro čtení nebo pro zápis, aby byl síťový protokol jednoduchý a spolehlivý.

Rozdíl mezi vyrovnávací pamětí a mezipamětí

Vyrovnávací paměť a mezipaměť se navzájem nevylučují; často se používají i společně. Důvod jejich použití je však odlišný. Vyrovnávací paměť je místo v paměti, které se tradičně používá proto, že instrukce procesoru nemohou přímo adresovat data uložená v periferních zařízeních. Paměť počítače se používá jako mezisklad.

Kromě toho může být taková vyrovnávací paměť použitelná v případě, kdy je velký blok dat sestaven nebo rozebrán (podle požadavků paměťového zařízení), nebo když mohou být data dodána v jiném pořadí, než v jakém byla vytvořena. Také celá vyrovnávací paměť dat se obvykle přenáší postupně (například na pevný disk), takže samotné ukládání do vyrovnávací paměti někdy zvyšuje výkonnost přenosu. Tyto výhody jsou přítomny i v případě, že jsou data z vyrovnávací paměti jednou zapsána do vyrovnávací paměti a jednou přečtena z vyrovnávací paměti.

Mezipaměť také zvyšuje přenosový výkon. Část tohoto zvýšení je podobně způsobena možností, že se více malých přenosů spojí do jednoho velkého bloku. Hlavní nárůst výkonu však vzniká tím, že existuje velká pravděpodobnost, že stejný údaj bude z mezipaměti načten několikrát nebo že zapsaná data budou brzy přečtena. Jediným účelem mezipaměti je omezit přístupy k základnímu pomalejšímu úložišti. Cache je také obvykle abstrakční vrstva, která je navržena tak, aby byla z pohledu sousedních vrstev neviditelná. Aplikace nebo klienti si tak nemusí být vědomi existence mezipaměti.

Otázky a odpovědi

Otázka: Co je to ukládání do mezipaměti?

A: Caching je termín používaný v informatice, který označuje praxi ukládání kopií často používaných dat za účelem rychlejšího přístupu k nim než opětovné načítání nebo přepočítávání původních dat.

Otázka: Jak funguje ukládání do mezipaměti?

Odpověď: Ukládání do mezipaměti funguje tak, že se používají dva druhy paměťových médií, jedno, které je obvykle poměrně velké, ale přístup k němu je pomalý, a druhé, ke kterému lze přistupovat mnohem rychleji, ale které je obvykle menší. Myšlenkou ukládání do mezipaměti je použití rychlého média k ukládání kopií dat, takže přístup k původním datům trvá kratší dobu nebo je méně nákladný.

Otázka: Co je vyrovnávací paměť?

Odpověď: Vyrovnávací paměť je podobná mezipaměti v tom, že ukládá kopie dat pro rychlejší přístup, avšak u vyrovnávací paměti klient přistupující k datům ví, že existuje vyrovnávací paměť, a spravuje ji aplikace, zatímco u mezipaměti klienti nemusí vědět, že existuje mezipaměť.

Otázka: Co znamená lokálnost reference?

Odpověď: Lokalita reference znamená, že když aplikace přistupuje k určitým blokům strukturovaných dat, je pravděpodobné, že bude přistupovat i k dalším blokům, které se nacházejí v blízkosti těch, k nimž původně přistupovala. To napomáhá dobrému fungování mezipaměti, protože je obvykle malá v porovnání se všemi dostupnými daty.

Otázka: Proč větší mezipaměti déle vyhledávají záznamy?

Odpověď: Větší cache trvají déle, protože obsahují více uložených informací, a proto vyžadují více času na vyhledávání. Jsou také dražší, protože vyžadují více prostředků pro ukládání.

Otázka: Jak může lokálnost pomoci zlepšit fungování mezipaměti?

Odpověď: Lokalita pomáhá zlepšit fungování mezipaměti, protože když aplikace přistupují k určitým blokům strukturovaných dat, budou pravděpodobně potřebovat i další blízké bloky, které pak mohou rychle načíst z mezipaměti, místo aby je musely načítat odjinud nebo znovu vypočítávat.