Vyrovnávacia pamäť (cache) — definícia, princípy a stratégie
Vyrovnávacia pamäť (cache) — prehľadná definícia, princípy fungovania a efektívne stratégie nahradzovania pre rýchlejšie aplikácie, optimalizáciu výkonu a bezpečné ukladanie dát.
Caching je termín používaný v informatike. Myšlienka cache (vyslovuje sa "cash" /ˈkæʃ/ KASH)) je veľmi jednoduchá: získanie výsledku niektorých operácií alebo prístup k údajom môže byť časovo náročné alebo nákladné, preto sa často oplatí výsledok uložiť a znova ho použiť. Typicky sa pracuje so dvoma druhmi pamäťových médií: jedno je veľké, ale pomalé (napríklad pevný disk alebo diaľkový server), druhé je malé, ale rýchle (napríklad procesorová vyrovnávacia pamäť alebo operačná pamäť). Základným princípom je mať kópiu často používaných údajov v rýchlom médiu, aby sa znížil priemerný čas prístupu a zlepšil výkon systému.
Čo je vyrovnávacia pamäť (cache)
Vyrovnávacia pamäť je dočasné úložisko obsahujúce kópie údajov, ktoré sa často používajú. Ak sa požadované údaje nachádzajú v cache (tzv. cache hit), systém ich získa rýchlejšie než pri opätovnom načítaní alebo prepočítaní z pôvodného zdroja (tzv. cache miss). Ukladanie nových položiek do cache obvykle vyžaduje nahradenie niektorej existujúcej položky podľa určitej stratégie.
Cache vs. buffer (vyrovnávací priestor)
Cache a buffer (vyrovnávací priestor) sú príbuzné pojmy, no líšia sa účelom a tým, ako o nich vie klient:
- Cache spravidla obsahuje kópie už existujúcich údajov s cieľom zrýchliť opakovaný prístup; často je transparentná — klient nemusí vedieť, že cache existuje (napr. CPU cache alebo disk cache v OS).
- Buffer je dočasné miesto pre údaje počas prenosu alebo transformácie (napr. I/O buffer); často ho klient aktívne používa alebo spravuje aplikácia.
Lokalita referencie
Typické aplikácie pristupujú k údajom blokovo a pristup často nasleduje určité vzory. Dva hlavné druhy lokality referencie sú:
- Temporálna lokalita — ak sa k určitému bloku prístupuje, je pravdepodobné, že sa k nemu bude pristupovať znova v blízkej budúcnosti.
- Priestorová (spaciálna) lokalita — ak sa pristupuje k určitému bloku, je pravdepodobné, že sa v krátkom čase pristúpi aj k susedným blokom.
Tieto vlastnosti sú dôvodom, prečo cache fungujú dobre v mnohých oblastiach výpočtovej techniky.
Metriky výkonu cache
- Hit rate — podiel požiadaviek, ktoré skončia v cache (vyšší je lepší).
- Miss rate — doplnok hit rate (1 − hit rate).
- Latencia (čas prístupu) — doba potrebná na servis požiadavky pri hite a pri mise.
- Throughput — počet obslúžených požiadaviek za jednotku času.
Stratégie nahradzovania (eviction)
Keď je cache plná, musí sa rozhodnúť, ktorú položku nahradiť. Bežné stratégie sú:
- LRU (Least Recently Used) — nahradí sa položka, ktorá bola najdlhšie nepoužitá.
- FIFO (First-In, First-Out) — nahradí sa najstaršia vložená položka.
- LFU (Least Frequently Used) — nahradí sa položka s najnižšou frekvenciou prístupov.
- Random — náhodné nahradenie, jednoduché na implementáciu.
- Adaptive a hybridné — kombinujú viacero princípov (napr. CLOCK, ARC).
Organizácia cache (zapojenie)
Dôležitou charakteristikou cache, najmä v CPU a pamäťových systémoch, je asociativita:
- Direct-mapped — každý blok pamäte má presne jednu pozíciu v cache (rýchle, ale môže viesť k častým konfliktom).
- Set-associative — pamäťové bloky sú mapované do menších sád; v každej sade môže byť viacero vložených položiek (vyvážený kompromis medzi výkonom a zložitosťou).
- Fully associative — blok môže byť uložený kdekoľvek v cache (najflexibilnejšie, ale náročnejšie na vyhľadávanie).
Zápisové politiky
Pri zmene údajov existujú dve základné stratégie zápisu do cache:
- Write-through — pri zápise sa údaje zapíšu súčasne do cache i do hlavného úložiska (jednoduché, konzistentné, ale môže byť pomalšie).
- Write-back — zápis mení len kópiu v cache a spätné zapísanie do pomalého úložiska sa vykoná neskôr pri evikcii (efektívnejšie, ale vyžaduje sledovanie „dirty“ bitov a riešenie konzistencie).
Typy cache a príklady použitia
- CPU cache (L1, L2, L3) — malé, veľmi rýchle úrovne cache v procesore, navrhnuté na znižovanie latencie prístupu k inštrukciám a dátam.
- Disková a OS cache — cache v operačnom systéme alebo disku na zrýchlenie prístupu k súborom.
- Webový a proxy cache — ukladanie odpovedí HTTP, znižujú sieťovú záťaž a latenciu.
- CDN (Content Delivery Network) — distribuované cache blízko používateľov pre statický obsah (obrázky, videá).
- Databázové cache — ukladanie výsledkov dotazov, často používané v kombinácii s in-memory kešovaním (napr. Redis, Memcached).
- Príklad v prehliadači — browser cache ukladá obrázky, CSS a JS súbory, aby sa pri ďalších návštevách stránky nemusia znova sťahovať.
Konzistencia, invalidácia a problémy
Cache prinášajú aj výzvy:
- Stále (stale) údaje — kópia v cache môže byť zastaraná, preto treba mechanizmy invalidácie alebo časového vypršania (TTL).
- Cache coherence — v multiprocesorových systémoch a rozložených systémoch je potrebné zabezpečiť, aby viac kópií údaja zostalo konzistentných.
- Cache thrashing — pri nevhodnej veľkosti alebo stratégie sa môže stať, že položky budú často nahrádzané, čím sa zníži efektivita cache.
- Cache invalidation — problém správneho zmazania alebo aktualizácie položiek je často zložitejší než samotné kešovanie („cache invalidation is one of the two hard things in computer science…“).
Rozhodovanie o veľkosti a návrhu cache
Vyrovnávacie pamäte sú zvyčajne oveľa menšie než celý objem údajov, ktorý zastupujú. Väčšia cache zvyšuje pravdepodobnosť hitu, ale môže mať dlhší čas vyhľadávania, vyššie náklady a zložitejšiu správu. Pri návrhu sa teda vyvažuje kapacita, rýchlosť, asociativita a náklady (energie, cena, miesto v čipe).
Tipy pre používanie cache v aplikáciách
- Zvoľte vhodnú stratégiu nahradzovania podľa vzorov prístupov (LRU je často dobrý východiskový bod).
- Určite jasné pravidlá invalidácie alebo TTL pre dynamické údaje.
- Merajte hit rate a latenciu — len meranie ukáže skutočný prínos cache.
- Pri rozložených systémoch zvážte konzistenciu a náklady na synchronizáciu medzi cache uzlami.
- Dbajte na bezpečnosť a citlivé údaje — nie všetky údaje sú vhodné na ukladanie do cache.
Vyrovnávacie pamäte sú kľúčovým nástrojom na zlepšenie výkonu v mnohých oblastiach výpočtovej techniky. Správne navrhnuté a konfigurované dokážu výrazne znížiť latenciu a zvýšiť priepustnosť systémov, no zároveň vyžadujú starostlivé riešenie otázok konzistencie a správy životnosti údajov.
Ako funguje vyrovnávacia pamäť
Vyrovnávacia pamäť je blok pamäte na ukladanie údajov, ktoré sa pravdepodobne použijú znova. Procesor a pevný disk často používajú vyrovnávaciu pamäť, rovnako ako webové prehliadače a webové servery.
Medzipamäť sa skladá z mnohých záznamov, ktoré sa nazývajú fond. Každá položka obsahuje údaj (bit údajov), ktorý je kópiou údaju na inom mieste. Cache zvyčajne používa tzv. záložné úložisko. Prístup k záložným úložiskám je v porovnaní s vyrovnávacou pamäťou pomalý alebo drahý. Napríklad disková vyrovnávacia pamäť používa ako záložné úložisko pevný disk. Ku každému záznamu je pripojená aj malá informácia, ktorá sa nazýva tag. Táto značka sa používa na vyhľadanie miesta, kde sú uložené pôvodné údaje.
Cache na čítanie
Ak chce klient (procesor, webový prehliadač, operačný systém) získať prístup k údaju, o ktorom sa domnieva, že sa nachádza v záložnom úložisku, najprv skontroluje, či sa údaj nachádza v medzipamäti. Ak sa údaje nachádzajú v medzipamäti, klient ich môže použiť a nemusí používať hlavnú pamäť. Tento postup sa nazýva zásah do vyrovnávacej pamäte. Takže napríklad program webového prehliadača môže skontrolovať svoju lokálnu vyrovnávaciu pamäť na disku, aby zistil, či má lokálnu kópiu obsahu webovej stránky na konkrétnej adrese URL. V tomto príklade je adresa URL značkou a obsah webovej stránky je údajom.
Ďalšou situáciou, ktorá môže nastať, je, že údaj so značkou nemožno nájsť v cache. Táto situácia je známa ako zlyhanie vyrovnávacej pamäte. Údaj sa musí načítať zo záložného úložiska. Zvyčajne sa skopíruje do vyrovnávacej pamäte, takže nabudúce sa už nemusí načítať zo záložného úložiska.
Medzipamäť má len obmedzenú veľkosť. Aby sa uvoľnilo miesto pre predtým neuložený záznam, môže byť potrebné odstrániť z vyrovnávacej pamäte iný uložený záznam. Na vyhľadanie záznamu, ktorý by sa mal najlepšie odstrániť, sa používajú špeciálne pravidlá. Tieto pravidlá sa zvyčajne nazývajú heuristika. Heuristika použitá na nájdenie položky sa nazýva politika nahradenia. Veľmi jednoduché používané pravidlo sa nazýva najmenej používané (alebo LRU). Jednoducho sa vyberie záznam, ktorý bol použitý pred najdlhším časom. Ďalšie heuristiky sú uvedené v algoritme vyrovnávacej pamäte.
Medzipamäte na písanie
Medzipamäte sa môžu používať aj na zápis údajov; výhodou je, že klient môže pokračovať v operácii po zápise záznamu do medzipamäte; nemusí čakať, kým sa záznam zapíše do záložného úložiska.
Záznam však musí byť v určitom okamihu zapísaný do záložného úložiska. Čas, kedy sa tak stane, je riadený zásadami zápisu.
Pri priebežnom zápise do vyrovnávacej pamäte sa každý záznam okamžite zapíše do záložného úložiska a zároveň sa uloží do vyrovnávacej pamäte.
Druhou možnosťou je zapisovať len do vyrovnávacej pamäte a do záložného úložiska zapisovať neskôr. Tento postup sa nazýva spätný zápis (alebo zápis za) do vyrovnávacej pamäte. Vyrovnávacia pamäť označuje záznamy, ktoré ešte neboli zapísané do záložného úložiska; značka, ktorá sa používa, sa často označuje ako dirty flag. Pred vymazaním záznamov z vyrovnávacej pamäte sa tieto záznamy zapíšu do záložného úložiska. Tento postup je známy ako lenivý zápis. Pri chýbajúcom zápise do vyrovnávacej pamäte (ktorý si vyžaduje nahradenie bloku iným) budú často potrebné dva prístupy do pamäte: jeden na získanie potrebného údaja a druhý na zápis nahradených údajov z vyrovnávacej pamäte do úložiska.
Zásady ukladania do vyrovnávacej pamäte môžu tiež stanoviť, že určitý údaj sa musí zapísať do vyrovnávacej pamäte. Klient mohol vykonať mnoho zmien v danom údaji v medzipamäti. Po skončení môže výslovne povedať vyrovnávacej pamäti, aby sa údaj zapísal späť.
Prideľovanie bez zápisu je zásada vyrovnávacej pamäte, pri ktorej sa do vyrovnávacej pamäte ukladá iba čítanie. Tým sa zabráni potrebe spätného zápisu alebo zápisu do vyrovnávacej pamäte. Zápisy sa vykonávajú do záložného úložiska po celý čas.
Klient nie je aplikácia, ktorá mení údaje v záložnom úložisku. Ak sa údaje v záložnom úložisku zmenili, kópia v medzipamäti bude neaktuálna alebo zastaraná. Prípadne, keď klient aktualizuje údaje v medzipamäti, kópie týchto údajov v iných medzipamätiach sa stanú neaktuálnymi. Existujú špeciálne komunikačné protokoly, ktoré umožňujú správcom vyrovnávacej pamäte komunikovať medzi sebou, aby sa zachovala zmysluplnosť údajov. Tieto protokoly sú známe ako protokoly koherencie.
Výber položky, ktorá sa má nahradiť
Medzipamäť je malá a väčšinu času bude plná alebo takmer plná. Takže keď sa pridá nová hodnota, stará sa musí odstrániť. Tento výber sa dá vykonať rôznymi spôsobmi:
- First in First out: Jednoducho nahraďte záznam, ktorý bol pridaný do vyrovnávacej pamäte pred najdlhším časom.
- Najmenej používané v poslednom čase: Táto myšlienka je podobná vyššie uvedenému FIFO, ale keď sa položka použije, aktualizuje sa jej časová značka/stáročie.
- Najmenej používané: Opäť, podobne ako v prípade FIFO, namiesto časovej značky sa použije čítač, ktorý sa inkrementuje pri každom použití položky.
- Náhodne vyberte položku
História
Slovo cache bolo prvýkrát použité v oblasti výpočtovej techniky v roku 1967, keď bol pripravený vedecký článok na uverejnenie v časopise IBM Systems Journal. Článok sa týkal nového vylepšenia pamäte v modeli 85. Model 85 bol počítač z produktového radu IBM System/360. Redaktor časopisu Journal chcel lepší výraz pre vysokorýchlostnú vyrovnávaciu pamäť, ktorý sa v článku použil. Nedostal žiadny návrh a navrhol cache, z francúzskeho cacher, čo znamená "schovávať". Článok bol uverejnený začiatkom roka 1968 a autori boli spoločnosťou IBM ocenení. Ich práca bola všeobecne prijatá a vylepšená. Cache sa čoskoro stala štandardným používaním v počítačovej literatúre.
Otázky a odpovede
Otázka: Čo je to vyrovnávacia pamäť?
Odpoveď: Ukladanie do vyrovnávacej pamäte je termín používaný v informatike, ktorý označuje postup ukladania kópií často používaných údajov s cieľom získať k nim rýchlejší prístup ako opätovné načítanie alebo prepočítavanie pôvodných údajov.
Otázka: Ako funguje ukladanie do vyrovnávacej pamäte?
Odpoveď: Ukladanie do vyrovnávacej pamäte funguje tak, že sa používajú dva druhy pamäťových médií, jedno, ktoré je zvyčajne pomerne veľké, ale prístup k nemu je pomalý, a druhé, ku ktorému sa dá pristupovať oveľa rýchlejšie, ale ktoré je spravidla menšie. Myšlienka ukladania do vyrovnávacej pamäte spočíva v použití rýchleho média na ukladanie kópií údajov, aby prístup k pôvodným údajom trval kratšie alebo bol menej nákladný.
Otázka: Čo je vyrovnávacia pamäť?
Odpoveď: Vyrovnávacia pamäť je podobná vyrovnávacej pamäti v tom, že ukladá kópie údajov na rýchlejší prístup, avšak pri vyrovnávacej pamäti klient pristupujúci k údajom vie, že existuje vyrovnávacia pamäť, a spravuje ju aplikácia, zatiaľ čo pri vyrovnávacej pamäti klienti nemusia vedieť, že existuje vyrovnávacia pamäť.
Otázka: Čo znamená lokálnosť referencie?
Odpoveď: Lokalita referencie znamená, že keď aplikácia pristupuje k určitým blokom štruktúrovaných údajov, je pravdepodobné, že bude pristupovať aj k iným blokom, ktoré sú blízko tých, ku ktorým pôvodne pristupovala. To pomáha vyrovnávacím pamätiam dobre fungovať, pretože sú zvyčajne malé v porovnaní so všetkými dostupnými údajmi.
Otázka: Prečo väčším vyrovnávacím pamätiam trvá vyhľadávanie záznamov dlhšie?
Odpoveď: Väčšie vyrovnávacie pamäte trvajú dlhšie, pretože obsahujú viac uložených informácií, a preto vyžadujú viac času na vyhľadávanie. Sú tiež drahšie, pretože vyžadujú viac zdrojov na ukladanie.
Otázka: Ako môže lokálnosť pomôcť zlepšiť fungovanie vyrovnávacích pamätí?
Odpoveď: Lokalita pomáha zlepšiť fungovanie vyrovnávacích pamätí, pretože keď aplikácie pristupujú k určitým blokom štruktúrovaných údajov, pravdepodobne budú potrebovať aj iné blízke bloky, ktoré sa potom môžu rýchlo načítať z vyrovnávacej pamäte namiesto toho, aby ich museli načítať odinakiaľ alebo ich znovu prepočítať.
Súvisiace články
Autor
AlegsaOnline.com Vyrovnávacia pamäť (cache) — definícia, princípy a stratégie Leandro Alegsa
URL: https://sk.alegsaonline.com/art/15884
Zdroje
- oxfordlearnersdictionaries.com : "cache noun"
- dictionary.cambridge.org : "cache definition, meaning"
- merriam-webster.com : "Cache"
- books.google.com : Pro Oracle Database 11g RAC on Linux
- dx.doi.org : dx.doi.org/10.1109/85.646206