Vahemälu (caching) – mis see on ja kuidas see arvutis töötab

Caching on termin, mida kasutatakse arvutiteaduses. Vahemälu (hääldatakse "cash" /ˈkæʃ/ KASH) idee on väga lihtne: sageli võtab mingi andme- või arvutustulemuse saamine palju aega või ressursse, seega on mõistlik salvestada selle tulemus ajutiselt edaspidiseks kasutamiseks. Vahemälu on lühiajaline salvestusruum, kus hoitakse koopiad sageli kasutatavatest andmetest, et neid oleks hiljem kiiremini võimalik kätte saada.

Kuidas vahemälu töötab

Üldiselt kasutatakse kahte tüüpi salvestusruume: üks on suur, aga aeglasem; teine on kiire, aga väiksem. Vahemälu hoiab andmete kiiret koopiat kiiremas meediumis. Kui programm vajab andet, kontrollitakse esmalt vahemälu (see on cache lookup). Kui vajalik andmeüksus on vahemälus (cache hit), saab selle kiiresti kätte. Kui see puudub (cache miss), tuleb andmeallikast (originaal) laadida või arvutada tulemus ning sageli salvestada see vahemällu tulevaste päringute jaoks.

Andmed jagatakse tihti plokkideks või lehekülgedeks, millele pääsetakse üksikult juurde. Kui rakendus kasutab ühte plokki, kasutab ta sageli ka naabriplokke — seda nähtust nimetatakse viitamise lokaalsuseks (locality of reference). Lokaalsus võib olla ajaline (sama andmeelement kasutatakse korduvalt lühikese aja jooksul) või ruumiline (kasutatakse andmeid, mis asuvad üksteisele lähedal). See omadus teeb vahemällu salvestamise tõhusaks.

Tüübid ja näited

CPU vahemälu — protsessori sees olevad L1, L2, L3 vahemälud, mis hoiavad sageli vajalikke käsklusi ja andmeid, et vähendada ligipääsu aeglasemale mälule.
Lehekülje- ja kettuvahemälu — operatsioonisüsteemi kasutatav mälu, et vältida sagedasi piirdkäitusid kettaadresst.
Brauseri vahemälu — salvestab veebilehe ressursse (pildid, CSS, JS), et lehti kiiremini laadida.
CDN ja serverivahemälud — sisu edastamise võrgud (CDN) ja veebiserverid hoiavad sageli staatilisi andmeid lähemal kasutajatele.
Rakenduse-taseme vahemälud — nagu Redis või Memcached, mida arendajad kasutavad andmete kiireks salvestamiseks ja lugemiseks.
DNS vahemälu — salvestab domeeninimede vasted IP-aadressidele, et kiirendada nime lahendamist.

Asendamis- ja kirjutusstrateegiad

Kui vahemälu on täis, tuleb otsustada, millist kirjet asendada. Levinud asendamisstrateegiad:

LRU (Least Recently Used) — asendatakse kõige varem kasutatud kirje.
FIFO (First In, First Out) — kasutatakse järjekorra printsiipi.
LFU (Least Frequently Used) — asendatakse kõige vähem kasutatud kirje.
Random — juhuslik valik, lihtne ja kiire rakendada.

Kirjutusstrateegiad määravad, kuidas kirjeid kirjutatakse tagasi originaalallikasse:

Write-through — iga kirjutus jõuab kohe nii vahemällu kui ka põhiandmehoidlasse, mis hoiab andmed järjepidevana, aga on aeglasem.
Write-back — muudatus salvestatakse esmalt ainult vahemällu ja kirjutatakse tagantjärele (eviction või perioodiliselt) põhihoidlasse, mis võib parandada jõudlust, aga lisab keerukust ja riski andmete kaotsimineku korral.

Struktuur ja assotsiatiivsus

Vahemälu struktuur mõjutab otsingukiirust ja keerukust. Levinud mudelid on:

Direct-mapped — iga plokk põhiandmetes vastab ühele kindlale vahemälukohta; lihtne, aga konfliktide oht suurem.
Set-associative — iga plokk võib asuda väheses arvus kohtades (set), hea kompromiss kiiruse ja paindlikkuse vahel.
Fully associative — plokk võib asuda suvalisse vahemälukohta; väldib konflikte, aga otsingu- ja riistvarukulukus suurem.

Mõõdikud ja terminid

Cache hit — andmeüksus leitakse vahemälust.
Cache miss — andmeüksust vahemälus ei ole ning tuleb laadida originaalist.
Hit rate / Miss rate — hit-rate on osakaal päringutest, mis lõppevad vahemälust leidmisega; kõrge hit-rate tähendab paremat jõudlust.
Latency — ligipääsu aeg; vahemälu vähendab keskmist latentsust.

Kasu ja piirangud

Vahemälu parandab jõudlust ja vähendab koormust aeglasematele süsteemidele. Samas on ka varjuküljed:

Vahemälus võib olla aegunud või mittesünkroniseeritud informatsioon (stale data), eriti kui kasutatakse write-back strateegiat või mitut vahemälu tase paralleelselt.
Vahemälu haldamine lisab keerukust — tuleb valida sobivad suurused, strateegiad ja sünkroonimismehhanismid.
Kui vahemälu on liiga väike, võib tekkida sagedane asendamine (thrashing), mis halvendab jõudlust.

Vahemälu vs puhver

Puhver on vahemäluga sarnane, kuid nende eesmärgid erinevad. Puhverit haldab tavaliselt rakendus ning puhvri kasutaja teab, et andmed asuvad puhvris — puhver koondab andmeid ajutiselt, et töödelda neid järjekorras või ühes tükis. Vahemälu on enamasti läbipaistev: kliendi ei pea teadma, et andmed pärinevad vahemälust, ja vahemälu haldamine toimub madalamal tasemel.

Parimad praktikad

Mõtle välja sobiv vahemälusuurus ja assotsiatiivsus vastavalt andmemustritele.
Kombineeri asendamis- ja kirjutusstrateegiaid vastavalt rakenduse nõudmistele (töökindlus vs jõudlus).
Kasu lokaalsusest: disaini andmestruktuurid ja ligipääsumustrid nii, et need kasutaksid ruumilist ja ajalist lokaalsust.
Monitoori hit-rate’e ja latentsust ning kohanda seadeid vastavalt tegelikule koormusele.

Vahemälu on üks kõige levinumaid ja tõhusamaid tehnikaid arvutisüsteemide kiirendamiseks. Õigesti disainitud vahemälulahendus vähendab ooteaega ja koormust, parandades kogu süsteemi reageerimisvõimet ja läbilaskevõimet.

Kuidas vahemälud töötavad

Vahemälu on mälublokk, kuhu salvestatakse andmeid, mida tõenäoliselt kasutatakse uuesti. Protsessor ja kõvaketas kasutavad sageli vahemälu, samuti veebibrauserid ja veebiserverid.

Vahemälu koosneb paljudest kirjetest, mida nimetatakse koguks. Iga kirje sisaldab andmeid (andmevälja), mis on koopia teises kohas olevast andmestikust. Tavaliselt kasutavad vahemälud nn varusalvestust. Tagavarahoidlad on võrreldes vahemäluga aeglased või kallid. Näiteks ketas-cache kasutab kõvaketast varundussalvestusena kõvaketast. Igale kirjele on lisatud ka väike teave, mida nimetatakse sildiks. Seda sildi kasutatakse selleks, et leida koht, kus algandmed on salvestatud.

Lugemiseks mõeldud vahemälud

Kui klient (protsessor, veebibrauser, operatsioonisüsteem) soovib pääseda ligi andmetele, mis tema arvates on varundussalvestuses, siis kontrollib ta kõigepealt, kas andmed on vahemälus olemas. Kui andmed leitakse vahemälust, saab klient neid kasutada ja ei pea kasutama põhimälu. Seda nimetatakse vahemälu tabamuseks. Nii võib näiteks veebilehitseja programm kontrollida oma kohalikku vahemälu kettal, et näha, kas tal on teatud URL-aadressil oleva veebilehe sisu kohalik koopia. Selles näites on URL-osakond sildiks ja veebilehe sisu on andmestikuks.

Teine olukord, mis võib tekkida, on see, et sildiga andmestikku ei leidu vahemälus. Seda tuntakse kui vahemälu puudumist. Andmed tuleb välja otsida varusalvestusest. Tavaliselt kopeeritakse see vahemällu, nii et järgmisel korral ei pea seda enam varusalvestusest välja otsima.

Vahemälu on ainult piiratud suurusega. Selleks, et teha ruumi varem vahemällu salvestamata kirjele, võib tekkida vajadus kustutada vahemälust teine vahemällu salvestatud kirje. Erieeskirju kasutatakse selleks, et leida kirje, mis tuleks kõige paremini kustutada. Neid reegleid nimetatakse tavaliselt heuristikaks. Kirje leidmiseks kasutatavat heuristikat nimetatakse asenduspoliitikaks. Väga lihtsat reeglit, mida kasutatakse, nimetatakse kõige vähem kasutatud reegliks (Least recently used ehk LRU). See võtab lihtsalt selle kirje, mida kasutati kõige kauem tagasi. Muud heuristikud on loetletud vahemälu algoritm..

Kirjutamise vahemälud

Cache'i saab kasutada ka andmete kirjutamiseks; selle eelis on see, et klient saab jätkata oma tegevust, kui kirje on kirjutatud cache'i; ta ei pea ootama, kuni kirje on kirjutatud varusalvestusse.

Siiski tuleb kanne mingil hetkel kirjutada varundussalvestusse. Ajastus, millal see juhtub, on kontrollitud kirjutamispoliitikaga.

Läbikirjutava vahemälu puhul kirjutatakse iga kirje kohe varundussalvestusse ja salvestatakse ka vahemällu.

Teine võimalus on kirjutada ainult vahemällu ja hiljem kirjutada varundussalvestusse. Seda nimetatakse tagasikirjutamiseks (või kirjutamiseks) vahemällu. Vahemälu tähistab kirjed, mida ei ole veel tagavarahoidlasse kirjutatud; kasutatud tähist nimetatakse sageli määrdunud lipukeseks (dirty flag). Enne kui kirjed vahemälust kustutatakse, kirjutatakse need varusalvestusse. Seda nimetatakse laiskaks kirjutamiseks. Kirjutatavas vahemälus (mis nõuab ploki asendamist teise plokiga) on sageli vaja kahte mälukasutust: üks vajaliku andmestiku hankimiseks ja teine asendatud andmete kirjutamiseks vahemälust mällu.

Vahemälupoliitika võib ka öelda, et teatud andmed tuleb kirjutada vahemällu. Klient võib olla teinud vahemälus olevasse andmestikku palju muudatusi. Pärast seda võib ta selgesõnaliselt öelda vahemälule, et ta kirjutaks andmestiku tagasi.

No-write allocation on vahemälupoliitika, mille puhul vahemällu salvestatakse ainult lugemised. Sellega välditakse vajadust tagasikirjutamise või läbikirjutamise vahemälu järele. Kirjutusi tehakse kogu aeg varundussalvestusse.

Klient ei ole rakendus, mis muudab andmeid varundussalvestuses. Kui andmed muutuvad varundussalves, on vahemälus olev koopia aegunud või aegunud. Teise võimalusena, kui klient uuendab andmeid vahemälus, muutuvad nende andmete koopiad teistes vahemäludes aegunuks. On olemas spetsiaalsed suhtlusprotokollid, mis võimaldavad vahemäluhalduritel omavahel suhelda, et hoida andmeid mõtestatuna. Neid nimetatakse sidususe protokollideks.

Protsessori vahemälu skeem

Asendatava kande valimine

Vahemälu on väike ja see on enamasti täis või peaaegu täis. Seega, kui lisatakse uus väärtus, tuleb vana eemaldada. Seda valikut saab teha erinevatel viisidel:

Esimesena sisse, esimesena välja: Lihtsalt asendada kanne, mis lisati vahemällu kõige kauem tagasi
Viimati kasutatud: See idee on sarnane eespool kirjeldatud FIFO-le, kuid kui kirjet kasutatakse, uuendatakse selle ajatemplit/vanust.
Kõige vähem kasutatud: Jällegi, sarnaselt FIFO juhtumile, kasutatakse ajatempli asemel loendurit, mida suurendatakse iga kord, kui kirjet kasutatakse.
Valige juhuslikult üks kanne

Ajalugu

Sõna vahemälu kasutati arvutiteaduses esmakordselt 1967. aastal, kui IBM Systems Journal'is valmistati ette teadusartiklit, mis avaldati ajakirjas IBM Systems Journal. Artikkel käsitles mälu uut täiustust mudelis 85. Model 85 oli IBM System/360 tootesarja kuuluv arvuti. Ajakirja toimetaja soovis artiklis kasutatud kiire puhvri jaoks paremat sõna. Ta ei saanud vastust ja pakkus välja cache, mis tuleneb prantsuse keelest cacher, mis tähendab "peita". Artikkel avaldati 1968. aasta alguses ja IBM tunnustas autoreid. Nende tööd võeti laialdaselt vastu ja parandati. Cache muutus peagi arvutikirjanduses standardseks kasutuseks.

Kui kasutatakse vahemälusid

CPU vahemälud

Väikesed mälud protsessori kiibil või selle läheduses võivad olla kiiremad kui palju suuremad põhimälud. Enamik protsessoreid alates 1980. aastatest on kasutanud ühte või mitut vahemälu. Kaasaegsetel üldotstarbelistel personaalarvutites olevatel protsessoritel võib olla kuni pool tosinat vahemälu. Iga vahemälu võib olla spetsialiseerunud programmi täitmise eri osale.

Ketta vahemälud

Protsessori vahemälusid haldab üldiselt täielikult riistvara, teisi vahemälusid haldab teistsugune tarkvara. Operatsioonisüsteem haldab tavaliselt põhimälus asuvat lehekülje vahemälu. Kasutajad väljaspool arvutiteadust nimetavad seda vahemälu tavaliselt virtuaalseks mäluks. Seda haldab operatsioonisüsteemi tuum.

Kaasaegsetel kõvakettadel on kettapuhvrid. Neid nimetatakse mõnikord "kettakäskude vahemäluks", kuid see on vale. Nende puhvrite peamine ülesanne on korrastada ketta kirjutamist ja hallata lugemist. Korduvaid vahemälu tabamisi esineb harva, sest puhver on kõvaketta suurusega võrreldes väga väike.

Kohalikud kõvakettad on võrreldes teiste salvestusseadmetega, nagu näiteks kaugserverid, kohalikud lindikettad või optilised jukeboxid, kiired. Kohalike kõvaketaste kasutamine vahemäludena on hierarhilise mäluhalduse põhikontseptsioon.

Veebi vahemälud

Veebibrauserid ja veebivahendusserverid kasutavad vahemälusid, et salvestada veebiserverite eelnevaid vastuseid, näiteks veebilehti. Veebi vahemälud vähendavad võrgu kaudu edastatava teabe hulka. Varem vahemällu salvestatud teavet saab sageli uuesti kasutada. See vähendab ribalaiust ja veebiserveri töötlemisvajadust ning aitab parandada veebi kasutajate reageerimisvõimet.

Kaasaegsed veebibrauserid kasutavad sisseehitatud veebi vahemälu, kuid mõned internetiteenuse pakkujad või organisatsioonid kasutavad ka vahemälu proxy-serverit. See on veebi vahemälu, mida jagavad kõik selle võrgu kasutajad.

Otsingumootorid teevad sageli ka nende poolt indekseeritud veebilehed oma vahemälust kättesaadavaks. Näiteks Google pakub iga otsingutulemuse kõrval linki "Cache". See on kasulik, kui veebilehed on ajutiselt veebiserverist kättesaamatud.

Caching ebausaldusväärsete võrkudega

Läbikirjutamine on tavaline ebausaldusväärsetes võrkudes (nagu Ethernet LAN). Protokolli, mida kasutatakse selleks, et tagada andmete mõttekus kirjutamise vahemälus, kui kasutatakse mitut kirjutamise vahemälu, on sellisel juhul väga keeruline.

Näiteks veebilehtede vahemälud ja kliendipoolsed võrgu failisüsteemide vahemälud (nagu NFS või SMB) on tavaliselt ainult lugemis- või kirjutamispõhised, et hoida võrguprotokoll lihtsana ja usaldusväärsena.

Vahe puhvri ja vahemälu vahel

Puhver ja vahemälu ei välista üksteist; neid kasutatakse sageli ka koos. Põhjus, miks neid kasutatakse, on siiski erinev. Puhver on asukoht mälus, mida traditsiooniliselt kasutatakse seetõttu, et protsessori käsud ei saa otse adresseerida välisseadmetes salvestatud andmeid. Arvutimälu kasutatakse vahepealse hoidjana.

Lisaks sellele võib selline puhver olla otstarbekas, kui suur andmeplokk on kokku- või lahti ühendatud (nagu nõuab salvestusseade) või kui andmed võidakse edastada erinevas järjekorras kui see, milles need on toodetud. Samuti edastatakse kogu puhver andmete kogumit tavaliselt järjestikku (näiteks kõvakettale), nii et puhverdamine ise suurendab mõnikord andmeedastuse jõudlust. Need eelised on olemas isegi siis, kui puhverdatud andmed kirjutatakse puhvrisse üks kord ja loetakse puhvrist üks kord.

Vahemälu suurendab ka ülekande jõudlust. Osa suurenemisest tuleneb samuti võimalusest, et mitu väikest ülekannet ühendatakse üheks suureks plokiks. Kuid peamine jõudluse suurenemine tuleneb sellest, et on suur tõenäosus, et sama andmestik loetakse vahemälust mitu korda või et kirjutatud andmed loetakse peagi. Vahemälu ainus eesmärk on vähendada ligipääse aluseks olevale aeglasemale mälule. Cache on tavaliselt ka abstraktsioonikiht, mis on kavandatud nii, et see on naaberkihi seisukohast nähtamatu. Nii ei pruugi rakendused või kliendid olla teadlikud, et on olemas vahemälu.

Küsimused ja vastused

K: Mis on vahemälu?

V: Vahemälu on arvutiteaduses kasutatav termin, mis viitab praktikale, mille kohaselt salvestatakse sageli kasutatavate andmete koopiaid, et neile kiiremini ligi pääseda kui originaalandmete uuesti otsimine või uuesti arvutamine.

K: Kuidas vahemälu töötab?

V: Caching töötab, kasutades kahte liiki salvestusvahendeid, millest üks on tavaliselt üsna suur, kuid aeglane juurdepääs, ja teine, millele on võimalik palju kiiremini ligi pääseda, kuid mis on üldiselt väiksem. Vahehoidmise idee on kasutada kiiret andmekandjat andmete koopiate säilitamiseks, nii et juurdepääs originaalandmetele võtab vähem aega või on vähem kulukas.

K: Mis on puhver?

V: Puhver sarnaneb vahemäluga selles mõttes, et see salvestab andmete koopiaid kiiremaks juurdepääsuks, kuid puhvri puhul teab andmeid kasutav klient, et on olemas puhver ja seda haldab rakendus, samas kui vahemälu puhul ei pea kliendid teadma, et on olemas vahemälu.

K: Mida tähendab viitamise lokaalsus?

V: Viidete lokaalsus tähendab seda, et kui rakendus kasutab teatavaid struktureeritud andmete plokke, siis tõenäoliselt kasutab ta ka teisi plokke, mis asuvad algselt kasutatud plokkide läheduses. See aitab vahemälu hästi toimida, kuna need on tavaliselt väikesed võrreldes kõigi kättesaadavate andmetega.

K: Miks võtab suuremate vahemälude kirjete otsimine kauem aega?

V: Suuremad vahemälud võtavad kauem aega, sest need sisaldavad rohkem salvestatud teavet ja nõuavad seetõttu rohkem aega otsingute tegemiseks. Samuti on need kallimad, kuna nõuavad rohkem ressursse salvestamiseks.

K: Kuidas saab lokaalsus aidata vahemälusid paremini tööle panna?

V: Lokaalsus aitab vahemälu paremini tööle panna, sest kui rakendused pääsevad ligi teatud struktureeritud andmeplokkidele, vajavad nad tõenäoliselt ka teisi läheduses asuvaid plokke, mida saab kiiresti vahemälust välja otsida, selle asemel et neid mujalt välja otsida või uuesti arvutada.