Predpomnilnik (računalništvo): definicija, delovanje in vrste
Predpomnilnik v računalništvu: definicija, princip delovanja, vrste, strategije izmenjave in koristi za hitrejši dostop do podatkov ter izboljšanje zmogljivosti.
Predpomnjenje je izraz, ki se uporablja v računalništvu. Ideja predpomnilnika (izgovori se "keš" /kæʃ/) je preprosta: pridobivanje ali izračun nekaterih podatkov je lahko zamudno ali računsko drago, zato se pogosto izplača rezultat shraniti in ga ob ponovnem zahtevku uporabiti namesto ponovnega računanja ali počasnega branja iz izvirnega vira. Za predpomnjenje se navadno uporabljata dve vrsti pomnilniških medijev: eden je običajno zelo velik, a počasnejši (npr. disk ali oddaljena strežnica), drugi pa je manjši in hitrejši (npr. DRAM ali registri procesorja). Osnovna zamisel je, da pogosto uporabljene podatke hranimo v hitrem mediju – predpomnilniku – tako da je dostop do njih občutno hitrejši kot dostop do izvirnika. Če je kopija podatkov v predpomnilniku, je hitreje uporabiti to kopijo, kot pa ponovno pridobiti ali izračunati izvirne podatke. Tako se zniža povprečen čas dostopa do podatkov.
V predpomnilniku so kopije podatkov začasne in se občasno zamenjajo z novimi. Vnos nove vrednosti običajno zahteva odstranitev ali zamenjavo starejše vrednosti; za izbiro, kateri vnos zamenjati, obstajajo različne strategije zamenjave (npr. LRU, FIFO, LFU). Poleg tega so pomembne tudi politike zapisovanja (npr. write-through in write-back) ter mehanizmi za ohranjanje doslednosti med predpomnilnikom in izvirnimi podatki.
Predpomnilnik je po funkciji podoben vmesnemu (buffer) pomnilniku, vendar se razlikujeta v namenu in vidnosti za uporabnika oziroma aplikacijo. Vmesni pomnilnik (buffer) se pogosto uporablja za začasno zadrževanje podatkov med prenosom (na primer pri vhodno/izhodnih operacijah) in je lahko za aplikacijo transparenten; predpomnilnik pa je posebej namenjen hitremu ponovnemu dostopu do pogosto uporabljenih podatkov, pri čemer so lahko aplikacije ali sistem zavestni obstoja in upravljanja predpomnilnika.
Princip delovanja: zadetek in zgrešek
Osnovna metrika predpomnilnika je hit rate (delež zadetkov) oziroma miss rate (delež zgreškov). Ko aplikacija zahteva podatek:
- če se podatek nahaja v predpomnilniku (cache hit), se ga hitro vrne;
- če ga ni (cache miss), je treba podatek pridobiti iz počasnejšega vira, ga (običajno) vstaviti v predpomnilnik in nato vrniti aplikaciji.
Razlikujemo tudi vrste zgreškov: compulsory (prvič zahtevani podatki), capacity (zadetek bi bil mogoč, če bi bil predpomnilnik večji) in conflict (pri določenih organizacijah, npr. direct-mapped, ko več podatkov tekmuje za isti prostor).
Vrste in raba predpomnilnikov
- CPU predpomnilniki (L1, L2, L3): hitri (SRAM) predpomnilniki, ki zmanjšajo čas dostopa do navideznega glavnega pomnilnika. L1 je najhitrejši in najmanjši, L2 in L3 pa večji in počasnejši.
- Datotečni/diski predpomnilniki: sistemski predpomnilnik (buffer cache) ali disk cache za pospešitev dostopa do blokov na disku.
- Spletni predpomnilniki (HTTP cache, CDN): shranjujejo kopije spletnih vsebin bliže uporabniku, zmanjšujejo zakasnitev in porabo pasovne širine.
- Baze podatkov in aplikacijski predpomnilniki: npr. podatkovne strukture v pomnilniku (Memcached, Redis) za hitro dostavo rezultatov poizvedb.
- Predpomnilniki na nivoju brskalnika: zmanjšajo ponovno nalaganje statičnih virov (slike, skripte).
Strategije zamenjave
Najpogostejše strategije so:
- LRU (Least Recently Used) – odstrani element, ki ga je sistem najmanj dolgo uporabljal;
- FIFO (First-In, First-Out) – odstrani najdlje prisoten element;
- LFU (Least Frequently Used) – odstrani najmanj pogosto uporabljen element;
- Random – odstrani naključni element (preprosto in hitro);
- ter različne kombinacije in aproksimacije (npr. CLOCK) za učinkovito izvajanje v strojni ali programski opremi.
Politike zapisovanja
Pomembna odločitev je, kako obravnavati pisanje v predpomnilnik:
- Write-through: vsaka sprememba se takoj zapiše tudi v izvirni medij; enostavno zagotovljena konsistenca, a počasnejše pri zapisih.
- Write-back (write-behind): spremembe prvotno ostanejo le v predpomnilniku in se kasneje ujamejo v izvirnik; hitrejše zapisovanje, a zahteva mehanizem za sledenje "umazanih" (dirty) vnosov in več pozornosti pri izgubi energije ali napakah.
Lokalnost sklicevanja
Predpomnilniki temeljijo na principu lokalnosti sklicevanja:
- Temporalna lokalnost: če je nek podatek uporabljen zdaj, bo verjetno uporabljen ponovno kmalu;
- Prostorska (spatialna) lokalnost: če je uporabljen podatek na določenem naslovu, bodo verjetno uporabljeni tudi podatki v njegovi bližini.
Prav ti pojavi omogočajo, da majhen, hiter predpomnilnik zajame velik delež zahtev in znatno pospeši delovanje.
Organizacija in lastnosti
Pri načrtovanju predpomnilnika se upoštevajo:
- velikost (manjši predpomnilniki so hitrejši in cenejši, a imajo nižji hit rate);
- povezljivost (associativity) – direct-mapped, fully associative ali set-associative, kar vpliva na konfliktne zgreške in kompleksnost;
- velikost bloka (block/line size) – vpliva na prostorsko lokalnost in pasovno širino;
- stroški – hitrejši pomnilnik (SRAM) je dražji kot počasnejši (DRAM, disk);
- mehanizmi predhodnega nalaganja (prefetching) – napovedovanje naslednjih zahtev in nalaganje v predpomnilnik za zmanjšanje zgreškov;
- upravljanje vzporednega dostopa in coherence – pri večjedrnih sistemih je treba zagotoviti skladnost med predpomnilniki jeder (coherency protocols, npr. MESI).
Merila uspešnosti
Najpomembnejši kazalniki so hit rate, miss rate in miss penalty (strošek zgreška: čas, potreben za pridobitev podatka iz počasnejšega vira). Cilj je minimizirati povprečni čas dostopa (average memory access time – AMAT) in stroške pri danih stroškovnih omejitvah (poraba silicija, energija, cena).
Praktični nasveti in kompromisi
- Večji predpomnilnik običajno poveča hit rate, a rastejo stroški in latenca iskanja; zato so običajno uporabljeni večstopenjski predpomnilniki (npr. L1, L2, L3).
- Pri aplikacijah je koristno oblikovati dostopne vzorce, ki izkoriščajo lokalnost (npr. zaradi učinkovitega vzorčenja nizov, blokovno obdelavo matrik).
- Pri razvoju sistemov je treba tehtati med doslednostjo, hitrostjo zapisov in tveganji izgube podatkov (izbira med write-back in write-through).
Predpomnilniki so torej temeljni gradnik sodobnih računalniških sistemov: od procesorjev do spletnih strežnikov in baz podatkov. Z ustrezno organizacijo, politiko zamenjave in upoštevanjem lokalnosti lahko predpomnilnik znatno izboljša zmogljivost in odzivnost sistema.
Kako delujejo predpomnilniki
Predpomnilnik je blok pomnilnika za shranjevanje podatkov, ki bodo verjetno ponovno uporabljeni. Predpomnilnik pogosto uporabljata procesor in trdi disk, pa tudi spletni brskalniki in spletni strežniki.
Predpomnilnik je sestavljen iz številnih vnosov, ki se imenujejo bazen. Vsak vnos vsebuje podatek (bit podatkov), ki je kopija podatka na drugem mestu. Predpomnilniki običajno uporabljajo tako imenovano podporno shrambo. V primerjavi s predpomnilnikom je dostop do pomožnih shramb počasen ali drag. Diskovni predpomnilnik na primer uporablja trdi disk kot podporno shrambo. Vsakemu vnosu je priložena tudi majhna informacija, ki se imenuje oznaka. Ta oznaka se uporablja za iskanje lokacije, kjer so shranjeni izvirni podatki.
Predpomnilniki za branje
Odjemalec (procesor, spletni brskalnik, operacijski sistem), ki želi dostopati do podatka, za katerega verjame, da je v varnostni shrambi, najprej preveri, ali je podatek mogoče najti v predpomnilniku. Če je podatek mogoče najti v predpomnilniku, ga odjemalec lahko uporabi in mu ni treba uporabiti glavnega pomnilnika. To je znano kot zadetek predpomnilnika. Tako lahko na primer program spletnega brskalnika preveri svoj lokalni predpomnilnik na disku, da preveri, ali ima lokalno kopijo vsebine spletne strani na določenem naslovu URL. V tem primeru je URL oznaka, vsebina spletne strani pa podatek.
Druga situacija, ki se lahko zgodi, je, da podatka z oznako ni mogoče najti v predpomnilniku. To je znano kot zamujanje predpomnilnika. Podatek je treba pridobiti iz podporne shrambe. Običajno se kopira v predpomnilnik, tako da ga naslednjič ni več treba pobrati iz podporne shrambe.
Velikost predpomnilnika je omejena. Da bi naredili prostor za vnos, ki prej ni bil v predpomnilniku, bo morda treba iz predpomnilnika izbrisati še en vnos v predpomnilniku. Za iskanje vnosa, ki ga je najbolje izbrisati, se uporabljajo posebna pravila. Ta pravila se običajno imenujejo hevristika. Hevristika, ki se uporablja za iskanje vnosa, se imenuje politika zamenjave. Zelo preprosto pravilo, ki se uporablja, se imenuje najmanj nedavno uporabljeno (ali LRU). Preprosto vzame vnos, ki je bil uporabljen pred najdaljšim časom. Druge hevristike so naštete v algoritmu predpomnilnika.
Predpomnilniki za pisanje
Predpomnilniki se lahko uporabljajo tudi za pisanje podatkov; prednost tega je, da lahko odjemalec nadaljuje z delovanjem, ko je vnos zapisan v predpomnilnik; ni mu treba čakati, da se vnos zapiše v varnostno shrambo.
Vendar pa je treba vnos v nekem trenutku zapisati v varnostno shrambo. Čas, v katerem se to zgodi, nadzoruje politika pisanja.
Pri predpomnilniku s prehodnim zapisovanjem se vsak vnos takoj zapiše v podporno shrambo in hkrati shrani v predpomnilnik.
Druga možnost je, da pišete samo v predpomnilnik, v varnostno shrambo pa pišete pozneje. To je znano kot predpomnilnik za pisanje nazaj (ali pisanje za seboj). Predpomnilnik označi vnose, ki še niso bili zapisani v podporno shrambo; oznaka, ki se uporablja, se pogosto imenuje umazana zastavica. Preden se vnosi izbrišejo iz predpomnilnika, se zapišejo v podporno shrambo. To je znano kot leno pisanje. Za zgrešitev v predpomnilniku z zapisom (ki zahteva zamenjavo bloka z drugim) bosta pogosto potrebna dva dostopa do pomnilnika: eden za pridobitev potrebnega podatka, drugi pa za zapis zamenjanih podatkov iz predpomnilnika v shrambo.
Politika predpomnilnika lahko določa tudi, da je treba določen podatek zapisati v predpomnilnik. Odjemalec je morda vnesel veliko sprememb v podatek v predpomnilniku. Po končanem delu lahko predpomnilniku izrecno sporoči, naj ga zapiše nazaj.
Dodeljevanje brez pisanja je politika predpomnilnika, pri kateri se v predpomnilnik shranjuje samo branje. S tem se izognemo potrebi po predpomnilniku za zapisovanje nazaj ali zapisovanje skozi predpomnilnik. Pisanje se ves čas izvaja v varnostno shrambo.
Odjemalec ni aplikacija, ki spreminja podatke v varnostni shrambi. Če se podatki v podporni shrambi spremenijo, bo kopija v predpomnilniku zastarela. Če odjemalec posodobi podatke v predpomnilniku, bodo kopije teh podatkov v drugih predpomnilnikih postale zastarele. Obstajajo posebni komunikacijski protokoli, ki upraviteljem predpomnilnikov omogočajo, da se med seboj pogovarjajo in tako ohranjajo smiselnost podatkov. Ti so znani kot protokoli za koherenco.
Shema predpomnilnika procesorja
Izbira vnosa za zamenjavo
Predpomnilnik je majhen in bo večino časa poln ali skoraj poln. Zato je treba ob dodajanju nove vrednosti odstraniti staro vrednost. To izbiranje je mogoče opraviti na različne načine:
- Prvi vstopi, prvi izstopi: Preprosto zamenjajte vnos, ki je bil v predpomnilnik dodan pred najdaljšim časom.
- Najmanjkrat uporabljeno: Ko je vnos uporabljen, se posodobi njegov časovni žig/starost.
- Najmanjkrat uporabljeno: Podobno kot pri FIFO, namesto časovnega žiga uporabite števec, ki se poveča vsakič, ko je vnos uporabljen.
- Naključno izberite vnos
Zgodovina
Beseda predpomnilnik je bila v računalništvu prvič uporabljena leta 1967, ko je bil pripravljen znanstveni članek za objavo v reviji IBM Systems Journal. Članek je govoril o novi izboljšavi pomnilnika v modelu 85. Model 85 je bil računalnik iz proizvodne linije IBM System/360. Urednik revije Journal je želel boljšo besedo za hitri predpomnilnik, ki je bil uporabljen v članku. Ker ni dobil nobenega predloga, je predlagal predpomnilnik iz francoskega cacher, kar pomeni "skriti". Članek je bil objavljen v začetku leta 1968, IBM pa je avtorje nagradil. Njuno delo je bilo splošno sprejeto in izboljšano. Cache je kmalu postal standardna raba v računalniški literaturi.
Kje se uporabljajo predpomnilniki
Predpomnilniki procesorja
Majhni pomnilniki na procesorskem čipu ali v njegovi bližini so lahko hitrejši od veliko večjega glavnega pomnilnika. Večina procesorjev od osemdesetih let prejšnjega stoletja uporablja enega ali več predpomnilnikov. Sodobni splošni procesorji v osebnih računalnikih jih imajo lahko tudi do pol ducata. Vsak predpomnilnik je lahko specializiran za drug del naloge izvajanja programov.
Diskovni predpomnilniki
Predpomnilnike procesorja običajno v celoti upravlja strojna oprema, druge predpomnilnike pa upravlja različna programska oprema. Operacijski sistem običajno upravlja predpomnilnik strani v glavnem pomnilniku. Uporabniki zunaj računalništva ta predpomnilnik običajno imenujejo virtualni pomnilnik. Upravlja ga jedro operacijskega sistema.
Sodobni trdi diski imajo diskovne predpomnilnike. Včasih jih imenujemo "diskovni predpomnilnik", vendar je to napačno. Glavna funkcija teh predpomnilnikov je urejanje zapisovanja na disk in upravljanje branja. Ponavljajoči se zadetki predpomnilnika so redki, saj je predpomnilnik v primerjavi z velikostjo trdega diska zelo majhen.
Lokalni trdi diski so hitri v primerjavi z drugimi napravami za shranjevanje, kot so oddaljeni strežniki, lokalni tračni pogoni ali optični jukeboxi. Uporaba lokalnih trdih diskov kot predpomnilnikov je glavni koncept hierarhičnega upravljanja shranjevanja.
Spletni predpomnilniki
Spletni brskalniki in spletni posredniški strežniki uporabljajo predpomnilnike za shranjevanje prejšnjih odzivov spletnih strežnikov, na primer spletnih strani. Spletni predpomnilniki zmanjšujejo količino informacij, ki jih je treba prenesti po omrežju. Informacije, ki so bile predhodno shranjene v predpomnilniku, se lahko pogosto ponovno uporabijo. To zmanjša pasovno širino in zahteve spletnega strežnika po obdelavi ter pripomore k boljši odzivnosti uporabnikov spleta.
Sodobni spletni brskalniki uporabljajo vgrajeni spletni predpomnilnik, nekateri ponudniki internetnih storitev ali organizacije pa uporabljajo tudi predpomnilniški posredniški strežnik. To je spletni predpomnilnik, ki si ga delijo vsi uporabniki tega omrežja.
Iskalniki pogosto dajo na voljo tudi spletne strani, ki so jih indeksirali, iz svojega predpomnilnika. Google na primer ob vsakem rezultatu iskanja objavi povezavo "Predpomnilnik". To je uporabno, kadar spletne strani začasno niso dostopne iz spletnega strežnika.
Predpomnjenje z nezanesljivimi omrežji
V nezanesljivih omrežjih (kot je ethernetno omrežje LAN) se pogosto uporablja zapisovanje skozi. Protokol, ki se uporablja za zagotavljanje smiselnosti podatkov v predpomnilniku za pisanje, kadar se uporablja več predpomnilnikov za pisanje, je v takem primeru zelo zapleten.
Na primer, predpomnilniki spletnih strani in predpomnilniki omrežnih datotečnih sistemov na strani odjemalca (kot so predpomnilniki v NFS ali SMB) so običajno namenjeni samo branju ali zapisovanju, da bi omrežni protokol ostal preprost in zanesljiv.
Razlika med medpomnilnikom in predpomnilnikom
Medpomnilnik in predpomnilnik se ne izključujeta; pogosto se uporabljata tudi skupaj. Razlogi za njihovo uporabo so različni. Buffer je mesto v pomnilniku, ki se tradicionalno uporablja, ker navodila procesorja ne morejo neposredno naslavljati podatkov, shranjenih v perifernih napravah. Računalniški pomnilnik se uporablja kot vmesna shramba.
Poleg tega je takšen buffer lahko izvedljiv, kadar se velik blok podatkov sestavlja ali razstavlja (kot to zahteva naprava za shranjevanje) ali kadar se podatki lahko dostavijo v drugačnem vrstnem redu, kot so bili ustvarjeni. Prav tako se celoten predpomnilnik podatkov običajno prenaša zaporedno (na primer na trdi disk), tako da predpomnilnik sam po sebi včasih poveča zmogljivost prenosa. Te prednosti so prisotne tudi, če se podatki, shranjeni v predpomnilnik, enkrat zapišejo v predpomnilnik in enkrat preberejo iz predpomnilnika.
Predpomnilnik poveča tudi zmogljivost prenosa. Del povečanja je tudi posledica možnosti, da se več majhnih prenosov združi v en velik blok. Glavno povečanje zmogljivosti pa nastane, ker obstaja velika verjetnost, da bo isti podatek večkrat prebran iz predpomnilnika ali da bodo zapisani podatki kmalu prebrani. Edini namen predpomnilnikov je zmanjšati število dostopov do osnovnega počasnejšega pomnilnika. Predpomnilnik je običajno tudi abstrakcijska plast, ki je zasnovana tako, da je z vidika sosednjih plasti nevidna. Tako se aplikacije ali odjemalci morda ne zavedajo, da obstaja predpomnilnik.
Vprašanja in odgovori
V: Kaj je predpomnilnik?
O: Predpomnilnik je izraz, ki se uporablja v računalništvu in se nanaša na prakso shranjevanja kopij podatkov, ki se pogosto uporabljajo, da bi do njih dostopali hitreje, kot da bi ponovno poiskali ali izračunali izvirne podatke.
V: Kako deluje predpomnjenje?
O: Predpomnjenje deluje tako, da se uporabljata dve vrsti pomnilniških medijev, eden, ki je običajno precej velik, vendar je dostop do njega počasen, in drugi, do katerega je mogoče dostopati veliko hitreje, vendar je običajno manjši. Ideja predpomnjenja je, da se hitri medij uporabi za shranjevanje kopij podatkov, tako da dostop do izvirnih podatkov traja manj časa ali je cenejši.
V: Kaj je predpomnilnik?
O: Predpomnilnik je podoben predpomnilniku, saj shranjuje kopije podatkov za hitrejši dostop, vendar pri predpomnilniku odjemalec, ki dostopa do podatkov, ve, da obstaja predpomnilnik, in ga upravlja aplikacija, medtem ko pri predpomnilniku odjemalcem ni treba vedeti, da obstaja predpomnilnik.
V: Kaj pomeni lokalnost reference?
O: Lokalnost reference pomeni, da ko aplikacija dostopa do določenih blokov strukturiranih podatkov, bo verjetno dostopala tudi do drugih blokov, ki so blizu tistim, do katerih je prvotno dostopala. To pripomore k dobremu delovanju predpomnilnikov, saj so ti običajno majhni v primerjavi z vsemi razpoložljivimi podatki.
V: Zakaj večji predpomnilniki potrebujejo več časa za iskanje vnosov?
O: Večji predpomnilniki potrebujejo več časa, ker vsebujejo več shranjenih informacij in zato potrebujejo več časa za iskanje. So tudi dražji, saj zahtevajo več virov za shranjevanje.
V: Kako lahko lokalnost pripomore k boljšemu delovanju predpomnilnikov?
O: Lokalnost pripomore k boljšemu delovanju predpomnilnikov, saj bodo aplikacije, ko dostopajo do določenih blokov strukturiranih podatkov, verjetno potrebovale tudi druge bližnje bloke, ki jih lahko hitro pridobijo iz predpomnilnika, namesto da bi jih morale pridobiti od drugod ali jih ponovno izračunati.
Iskati