Vahemälu

Caching on termin, mida kasutatakse arvutiteaduses. Vahemälu (hääldatakse "cash" /ˈkæʃ/ KASH ) idee on väga lihtne: Väga sageli on mingi arvutuse tulemuse saamine väga aeganõudev, seega on tulemuse salvestamine üldiselt hea mõte. Kasutatakse kahte liiki salvestusvahendeid: Üks on tavaliselt üsna suur, kuid juurdepääs sellele on "aeglane"; teisele on juurdepääs palju kiirem, kuid üldiselt on see väike. Kopeerimise väga põhiline idee on kasutada andmete koopiate saamiseks meediumit, millele on kiirem juurdepääs. Koopia ja originaali vahel ei ole mingit vahet. Ligipääs originaalandmetele võib võtta kaua aega või see võib olla kallis (näiteks: keerulise probleemi tulemused, mille lahendamine võtab kaua aega). Sel põhjusel on palju "odavam" lihtsalt kasutada andmete koopiat vahemälust. Teisiti öeldes on vahemälu ajutine salvestusruum, kus on koopiad sageli kasutatavatest andmetest. Kui andmete koopia on selles vahemälus, siis on kiirem kasutada seda koopiat kui originaalandmeid uuesti välja otsida või uuesti arvutada. See muudab andmete kättesaamiseks kuluva keskmise aja lühemaks. Uue väärtuse panemine vahemällu tähendab sageli seda, et vanem väärtus tuleb asendada. On olemas erinevaid ideid (tavaliselt nimetatakse neid "strateegiateks"), kuidas valida asendatav väärtus.

Puhver on väga sarnane vahemäluga. Erinevus seisneb selles, et klient, kes kasutab puhvris olevaid andmeid, teab, et puhver on olemas; puhvrit haldab rakendus. Vahemälu puhul ei pea andmeid kasutav klient teadma, et tegemist on vahemäluga.

Tüüpilised arvutirakendused pääsevad andmetele ligi väga sarnasel viisil. Oletame, et andmed on struktureeritud "plokkideks", millele saab ükshaaval juurde pääseda. Kui rakendus kasutab plokki, siis suure tõenäosusega kasutab ta ka plokki, mis on algsele plokile "lähedal" (või viitab sellele). Seda nimetatakse viitamise lokaalsuseks (locality of reference). Sellist "lokaalsust" on eri liiki. Viidete paiknemine on üks põhjusi, miks vahemälud paljudes arvutivaldkondades hästi toimivad.

Selleks, et hästi toimida, on vahemälud väikesed, võrreldes kogu andmehulgaga. Mida suurem on vahemälu, seda kauem võtab kirje otsimine aega. Suuremaid vahemälusid on ka kallim ehitada.

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.