Mi az a gyorsítótár (cache)? Definíció, működés és stratégiák
Gyorsítótár (cache): mi ez, hogyan működik és mely stratégiák gyorsítják az adatelérést — gyakorlati tippek a hatékony cache-kezeléshez.
A gyorsítótárazás a számítástechnikában használt kifejezés. A gyorsítótár (ejtsd: "cash" /ˈkæʃ/ KASH) lényege nagyon egyszerű: gyakran egy számítás eredményének kinyerése vagy egy erőforráshoz való hozzáférés nagyon időigényes, ezért az eredmény vagy az adat egy gyorsabb adathordozón történő tárolása jelentősen csökkenti a késleltetést. Kétféle adathordozót szokás összevetni: az egyik általában nagy, de a hozzáférése lassabb; a másik sokkal gyorsabb, de kisebb kapacitású. A gyorsítótárazás alapötlete az, hogy az adatok másolatait azt az adathordozót használjuk, amelyikhez gyors a hozzáférés. A másolat és az eredeti logikailag ugyanazt az információt képviseli, de a másolat felhasználása gyakran "olcsóbb", mint az eredeti újralekérése vagy újraszámítása. Másképp fogalmazva, a gyorsítótár egy olyan ideiglenes tárolóterület, amely a gyakran használt adatok másolatait tartalmazza: ha a szükséges adat másolata rendelkezésre áll a gyorsítótárban, gyorsabb a másolat használata, mint az eredeti adat újra-elérése vagy újragenerálása. Ezáltal az adateléréshez szükséges átlagos idő rövidebb lesz.
Egy új érték gyorsítótárba helyezése gyakran azt jelenti, hogy egy régebbi értéket kell helyettesíteni. Különböző elképzelések (általában stratégiáknak nevezik őket) léteznek arra vonatkozóan, hogy hogyan válasszuk ki a helyettesítendő értéket; ezekről később részletesebben lesz szó.
A puffer nagyon hasonlít a gyorsítótárhoz. Abban különbözik, hogy a pufferben lévő adatokhoz hozzáférő ügyfél tudja, hogy van puffer; a puffert az alkalmazás kezeli. A gyorsítótár esetében az adatokhoz hozzáférő ügyfélnek gyakran nem kell tudnia a gyorsítótár létezéséről: a gyorsítótár lehet átlátszó a hozzáférést végező réteg számára, és automatikusan gyorsítja a műveleteket.
A gyorsítótár működése: hit, miss és átlagos hozzáférési idő
Amikor egy rendszer adatra kérdez rá, a gyorsítótár először ellenőrzi, hogy az adattöredék (pl. blokk, objektum, URL) megtalálható-e benne. Ennek három tipikus kimenetele van:
- Cache hit — az adat megtalálható a gyorsítótárban, azonnal visszaadható, így alacsony a késleltetés.
- Cache miss — az adat nincs a gyorsítótárban, ezért az eredeti (lassabb) tárolóból vagy számításból kell beszerezni; ez lassabb, és gyakran az eredmény után bekerül a gyorsítótárba.
- Eviction — amikor helyet kell csinálni, egy meglévő bejegyzést eltávolítanak a gyorsítótárból a helyettesítési stratégia szerint.
A gyorsítótár hatékonyságát jellemzi a hit rate (találati arány) és a miss penalty (a cache miss-hez kötődő többletköltség). Az átlagos hozzáférési idő a hit és miss arányok és azok költségeinek súlyozott átlaga.
Gyorsítótár-típusok és példák
- CPU cache (L1, L2, L3): kis, nagyon gyors memóriák a processzor közelében, amelyek instrukciókat és adatokat tartanak, és jelentősen csökkentik a memória-hozzáférés késleltetését.
- Operációs rendszer/buffer cache: lemezműveletek gyorsítása RAM alapú pufferezéssel.
- Böngésző cache és CDN: webes erőforrások (HTML, CSS, képek) tárolása a kiszolgáláshoz vagy közel a felhasználóhoz való gyorsabb eléréshez.
- Adatbázis- és alkalmazásszintű cache: lekérdezés eredmények, gyakran használt objektumok tárolása (pl. Redis, Memcached).
- Disztribuált cache: több szerveren megosztott gyorsítótár, amely skálázhatóságot és alacsony késleltetést biztosít elosztott rendszerekben.
Gyorsítótár-szerkezet: térfogalmak
- Kapacitás: a gyorsítótár mérete (elemek vagy bájtok). Nagyobb gyorsítótár jobb találati arányt adhat, de drágább és keresése lassabb lehet.
- Asszociativitás: hogyan vannak a bejegyzések leképezve címekhez — közvetlen leképezés (direct-mapped), teljesen asszociatív (fully associative) vagy halmaz-asszociatív (set-associative). Az asszociativitás hatással van a konfliktusok számára és a keresési költségre.
- TTL / lejárat: sok cache-bejegyzés rendelkezik élettartammal (time-to-live), amely után érvénytelenítik, így csökken a régi vagy elavult adat használatának kockázata.
Helyettesítési (eviction) stratégiák
Amikor a gyorsítótár megtelik, dönteni kell, melyik bejegyzést távolítsuk el. Gyakori stratégiák:
- LRU (Least Recently Used) — eltávolítjuk a legrégebben használt elemet; jól működik, ha a hozzáférések lokalitása időben is megvan.
- LFU (Least Frequently Used) — eltávolítjuk a legkevésbé gyakran hivatkozott elemet; hasznos, ha egyes elemek tartósan népszerűek.
- FIFO — elsőként betett elem kerül ki először; egyszerű, de nem mindig hatékony.
- Random — véletlenszerűen választunk egy eltávolítandót; egyszerű és olcsó, néha elfogadható.
- Belépés alapú politikák (pl. MRU, vagy kombinált megoldások): speciális esetekre optimalizált variánsok.
Írási stratégiák (write policies)
A gyorsítótár és az eredeti tároló közötti adatkonzisztencia kezelése kritikus kérdés. A leggyakoribb megoldások:
- Write-through — minden írásnál a gyorsítótárba és az eredeti tárolóba is írunk; egyszerű és konzisztens, de lassabb írásoknál.
- Write-back (write-behind) — az írás először csak a gyorsítótárba kerül, és később ("piszkos" bejegyzéseket flush-olva) íródik vissza az eredeti tárolóba; gyorsabb írás, de bonyolultabb konzisztencia- és hibakezelés.
- Write-around — az írás közvetlenül az eredeti tárolóba megy, a gyorsítótár érintetlen marad; hasznos lehet ritkán olvasott, de gyakran írt adatoknál.
- Cache-aside (lazy loading) — a kliens kezeli a cache-t: olvasáskor először cache-t kérdez, miss esetén betölti az eredetiből és beleteszi; írásnál frissíti az eredetit és opcionálisan invaldálja a cache-t.
Inkokherencia és érvényesítés
Elosztott rendszerekben a gyorsítótárak konzisztenciája kihívás: ha több példány létezik, hogyan biztosítjuk, hogy mindegyik a legfrissebb adatokat adja vissza? Gyakori megoldások:
- Explicit invalidálás — ha az adat változik, minden cache-példányt érvénytelenítenek.
- Lejárati idő (TTL) — a cache-bejegyzések idő után automatikusan lejárnak, így a frissítés garantálása időkorlátosan történik.
- Értesítési/érvényesítési protokollok — üzenet alapú invalidálás vagy koherencia-protokollok (pl. MESI CPU-cache esetén) biztosítják a szinkronizációt.
Gyakori problémák és megoldások
- Stale data (elavult adatok) — TTL, verziózás, vagy explicit invalidálás használata csökkentheti a kockázatot.
- Cache stampede / dog-pile — ha sok kliens egyszerre éri el ugyanazt a miss-t, a háttérrendszer túlterhelődhet; megoldások: lockolás, request coalescing, sztochasztikus TTL-ek vagy kapuzott (rate-limited) újraszámítás.
- Hot spotok — egyes kulcsok túl gyakran kérdeztek; lehetőség: replikáció, shardolás, vagy külön kezelt gyorsítótár a gyakori kulcsoknak.
- Warm-up és cold-start — újraindítás után a gyorsítótár üres; érdemes lehet melegítő (pre-warming) vagy cache filling stratégiákat alkalmazni.
Teljesítménymérések és tervezési szempontok
Tervezéskor fontos a következőket figyelembe venni:
- Hit rate / miss rate — fő mutatók, amelyek alapján értékeljük a cache hasznosságát.
- Latency — hit esetén és miss esetén mért átlagos válaszidők.
- Kapacitás költség vs. teljesítmény — nagyobb cache jobb találati arány, de költségesebb és eltérő késleltetési jellemzőkkel.
- Skálázhatóság — különösen elosztott rendszerekben fontos a hatékony shardolás, replikáció és konzisztencia-kezelés.
Mikor NE használjunk gyorsítótárat?
- Ha az adatok rendkívül dinamikusak és a konzisztencia bármilyen eltérése elfogadhatatlan.
- Ha az adathalmaz teljes egészében belefér a gyorsabb alap-tárolóba úgy, hogy a cache réteg feleslegessé válik.
- Ha a cache kezelése (invalidálás, összhang) nagyobb komplexitást és hibalehetőséget visz be, mint amit a teljesítménynyereség indokolna.
Legjobb gyakorlatok
- Használj megfelelő TTL-eket és invalidálási stratégiát a konzisztencia biztosításához.
- Monitorozd a hit/miss arányt, a késleltetést és a cache használatát, és hangold a méreteket és stratégiákat ennek megfelelően.
- Kezeld a cache stampede-et (például lockokkal vagy request coalescing-gel) a túlterhelés elkerüléséhez.
- Versionálj cache kulcsokat, ha struktúraváltozás vagy visszamenőleges inkompatibilitás fordulhat elő.
- Tervezz a hibákra: ha a cache kiesik, a rendszernek továbbra is működnie kell a háttértárolóval.
Összefoglalás
A gyorsítótár egy alapvető és sokoldalú eszköz a számítástechnikában, amely a gyakran használt adatok másolatainak tárolásával csökkenti a késleltetést és javítja a rendszer teljesítményét. A tervezésnél fontos figyelembe venni a helyettesítési politikákat, írási stratégiákat, konzisztencia-kezelést és a rendszerre jellemző használati mintákat (lokalitás). Megfelelő alkalmazásával a gyorsítótárak jelentős teljesítménynövekedést eredményezhetnek, de rosszul megtervezve inkább hibaforrást jelentenek.
Hogyan működnek a gyorsítótárak
A gyorsítótár egy olyan memóriablokk, amely olyan adatok tárolására szolgál, amelyeket valószínűleg újra felhasználnak. A CPU és a merevlemez gyakran használ gyorsítótárat, akárcsak a webböngészők és a webszerverek.
A gyorsítótár sok bejegyzésből, úgynevezett poolból áll. Minden bejegyzés egy adatot (egy adatdarabot) tartalmaz, amely egy másik helyen lévő adat másolata. A gyorsítótárak általában úgynevezett háttértárolót használnak. A háttértárolók elérése a gyorsítótárhoz képest lassú vagy drága. A lemezes gyorsítótár például merevlemezt használ háttértárolóként. Minden bejegyzéshez egy kis információ is tartozik, amelyet címkének nevezünk. Ez a címke arra szolgál, hogy megtaláljuk az eredeti adat tárolási helyét.
Cache-ek olvasáshoz
Ha egy ügyfél (CPU, webböngésző, operációs rendszer) hozzá akar férni egy olyan adathoz, amelyről azt hiszi, hogy a háttértárban van, akkor először ellenőrzi, hogy az adat megtalálható-e a gyorsítótárban. Ha az adat megtalálható a gyorsítótárban, az ügyfél használhatja azt, és nem kell a főmemóriát használnia. Ezt nevezzük gyorsítótár-találatnak. Így például egy webböngésző program ellenőrizheti a lemezen lévő helyi gyorsítótárát, hogy van-e helyi másolata egy adott URL-cím alatt található weboldal tartalmának. Ebben a példában az URL a címke, a weboldal tartalma pedig az adat.
A másik lehetséges helyzet az, hogy a címkével ellátott adat nem található meg a gyorsítótárban. Ezt nevezzük cache miss-nek. Az adatot a háttértárolóból kell előhívni. Általában bemásoljuk a gyorsítótárba, így a következő alkalommal már nem kell a háttértárból előhívni.
A gyorsítótár csak korlátozott méretű. Ahhoz, hogy helyet csináljon a korábban nem gyorsítótárazott bejegyzésnek, előfordulhat, hogy egy másik gyorsítótárazott bejegyzést kell törölni a gyorsítótárból. Speciális szabályok segítségével meg lehet találni azt a bejegyzést, amelyet a legjobb törölni. Ezeket a szabályokat általában heurisztikáknak nevezik. A bejegyzés megtalálásához használt heurisztikákat nevezzük cserepolitikának. Egy nagyon egyszerű szabályt használnak, amelyet Least recently used (vagy LRU) névvel illetnek. Ez egyszerűen azt a bejegyzést veszi, amelyet a legrégebben használtak. Egyéb heurisztikák a cache algoritmusnál találhatók.
Cache-ek íráshoz
A gyorsítótárak adatok írására is használhatók; ennek előnye, hogy az ügyfél folytathatja a műveletet, miután a bejegyzés a gyorsítótárba íródott; nem kell megvárnia, amíg a bejegyzés a háttértárolóba kerül.
A bejegyzést azonban valamikor a háttértárolóba kell írni. Ennek időzítését az írási házirend szabályozza.
Az átírásos gyorsítótárban minden egyes bejegyzés azonnal a háttértárolóba íródik, és a gyorsítótárban is tárolódik.
A másik lehetőség, hogy csak a gyorsítótárba írunk, és később írunk a háttértárolóba. Ez az úgynevezett write-back (vagy write-behind) cache. A gyorsítótár megjelöli azokat a bejegyzéseket, amelyeket még nem írtak a háttértárolóba; a használt jelölést gyakran dirty flagnek nevezik. Mielőtt a bejegyzések törlődnének a gyorsítótárból, a bejegyzéseket a háttértárolóba írja. Ezt nevezzük lusta írásnak. Az író-visszaíró gyorsítótárban történő hiba (amelyhez egy blokkot egy másikkal kell helyettesíteni) gyakran két memória-hozzáférést igényel: egyet a szükséges adat megszerzéséhez, egy másikat pedig a helyettesített adatoknak a gyorsítótárból a háttértárba történő írásához.
A gyorsítótárazási szabályzat azt is megmondhatja, hogy egy bizonyos adatot a gyorsítótárba kell írni. Előfordulhat, hogy az ügyfél sok módosítást hajtott végre a gyorsítótárban lévő adaton. Miután végzett, kifejezetten megmondhatja a gyorsítótárnak, hogy írja vissza az adatot.
Az írás nélküli kiosztás egy olyan gyorsítótár-szabályzat, ahol csak az olvasások kerülnek gyorsítótárba. Ezzel elkerülhető a visszaírásos vagy átírásos gyorsítótárazási eljárás. Az írások mindig a háttértárolóba történnek.
Az ügyfél nem az az alkalmazás, amelyik módosítja az adatokat a háttértárolóban. Ha az adatok a háttértárolóban megváltoztak, akkor a gyorsítótárban lévő másolat elavult vagy elavult lesz. Vagy, ha az ügyfél frissíti a gyorsítótárban lévő adatokat, akkor az adatok más gyorsítótárakban lévő másolatai is elavulnak. Vannak speciális kommunikációs protokollok, amelyek lehetővé teszik a gyorsítótár-kezelők számára, hogy beszéljenek egymással az adatok értelmességének megőrzése érdekében. Ezek az úgynevezett koherencia protokollok.
A CPU memória gyorsítótárának diagramja
A helyettesítendő bejegyzés kiválasztása
A gyorsítótár kicsi, és a legtöbbször tele lesz, vagy majdnem tele lesz. Tehát amikor egy új értéket adunk hozzá, egy régit el kell távolítani. Ezt a kiválasztást különböző módon lehet elvégezni:
- Az első beérkezése az első kimenetele: Egyszerűen cserélje ki azt a bejegyzést, amelyik a legrégebben került a gyorsítótárba.
- Legutóbb használták: Ez az elképzelés hasonló a fenti FIFO-hoz, de amikor egy bejegyzést használnak, annak időbélyege/kora frissül.
- Legkevésbé gyakran használt: A FIFO esethez hasonlóan, az időbélyegző helyett használjon számlálót, amely minden egyes bejegyzés használatakor növekszik.
- Véletlenszerűen válasszon ki egy bejegyzést
Történelem
A gyorsítótár szót először 1967-ben használták a számítástechnikában, amikor egy tudományos cikket készítettek elő az IBM Systems Journal című folyóiratban való közzétételre. A cikk a 85-ös modell memóriájának új fejlesztéséről szólt. A 85-ös modell az IBM System/360 termékcsalád egyik számítógépe volt. A Journal szerkesztője egy jobb szót szeretett volna a cikkben használt nagysebességű pufferre. Nem kapott választ, és a francia cacher szóból származó, "elrejteni" jelentésű cache-t javasolta. A cikk 1968 elején jelent meg, és a szerzőket az IBM kitüntette. Munkájukat széles körben üdvözölték és továbbfejlesztették. A cache hamarosan a számítógépes szakirodalomban standard használatba került.
Ahol a gyorsítótárakat használják
CPU gyorsítótárak
A CPU-chipen vagy annak közelében lévő kis memóriák gyorsabbak lehetnek, mint a sokkal nagyobb főmemória. Az 1980-as évek óta a legtöbb CPU egy vagy több gyorsítótárat használ. A személyi számítógépekben lévő modern általános célú CPU-k akár fél tucatnyi is lehet. Mindegyik gyorsítótár a programvégrehajtási feladat más-más részére specializálódhat.
Lemez gyorsítótárak
A CPU gyorsítótárakat általában teljes egészében a hardver kezeli, más gyorsítótárakat különböző szoftverek kezelnek. Az operációs rendszer általában a főmemóriában lévő lap gyorsítótárat kezeli. Az informatikán kívüli felhasználók ezt a gyorsítótárat általában virtuális memóriának nevezik. Ezt az operációs rendszer rendszermagja kezeli.
A modern merevlemezek lemezpufferrel rendelkeznek. Ezeket néha "lemez gyorsítótárnak" nevezik, de ez téves. Ezeknek a puffereknek a fő funkciója a lemezes írások rendezése és az olvasások kezelése. A gyorsítótár ismételt elérése ritka, mivel a puffer nagyon kicsi a merevlemez méretéhez képest.
A helyi merevlemezek más tárolóeszközökhöz, például távoli kiszolgálókhoz, helyi szalagos meghajtókhoz vagy optikai zenegépekhez képest gyorsak. A helyi merevlemezek gyorsítótárként való használata a hierarchikus tároláskezelés fő koncepciója.
Webes gyorsítótárak
A webböngészők és a webes proxykiszolgálók gyorsítótárakat használnak a webkiszolgálók korábbi válaszainak, például weboldalaknak a tárolására. A webes gyorsítótárak csökkentik a hálózaton keresztül továbbítandó információk mennyiségét. A gyorsítótárban korábban tárolt információk gyakran újra felhasználhatók. Ez csökkenti a sávszélességet és a webkiszolgáló feldolgozási igényeit, és segít javítani a web felhasználóinak válaszkészségét.
A modern webböngészők beépített webes gyorsítótárat használnak, de egyes internetszolgáltatók vagy szervezetek gyorsítótárazó proxy-kiszolgálót is használnak. Ez egy olyan webes gyorsítótár, amelyet az adott hálózat összes felhasználója megoszt.
A keresőmotorok gyakran a gyorsítótárukból is elérhetővé teszik az általuk indexelt weboldalakat. A Google például minden keresési eredmény mellett egy "Cache" linket ad meg. Ez akkor hasznos, ha a weboldalak átmenetileg nem érhetők el egy webszerverről.
Tárolás megbízhatatlan hálózatokkal
Az átírási művelet nem megbízható hálózatokban (például Ethernet LAN) gyakori. Ilyen esetben nagyon összetett az a protokoll, amely biztosítja, hogy az írási gyorsítótárban lévő adatoknak értelme legyen, ha több írási gyorsítótárat használnak.
Például a weboldalak gyorsítótárai és az ügyféloldali hálózati fájlrendszerek gyorsítótárai (mint például az NFS vagy az SMB) általában csak olvashatóak vagy átírhatóak, hogy a hálózati protokoll egyszerű és megbízható maradjon.
A különbség a puffer és a gyorsítótár között
A puffer és a gyorsítótár nem zárják ki egymást; gyakran együtt is használják őket. A használatuk oka azonban eltérő. A puffer egy olyan memóriahely, amelyet hagyományosan azért használnak, mert a CPU-utasítások nem tudják közvetlenül megszólítani a perifériás eszközökön tárolt adatokat. A számítógépes memóriát köztes tárolóként használják.
Ezenkívül egy ilyen puffer akkor is megvalósítható, ha egy nagy adatblokkot összeszerelnek vagy szétszednek (ahogyan azt egy tárolóeszköz megköveteli), vagy ha az adatokat az előállítási sorrendtől eltérő sorrendben kell átadni. Emellett egy teljes adatpuffer általában szekvenciálisan kerül átvitelre (például merevlemezre), így maga a pufferelés néha növeli az átviteli teljesítményt. Ezek az előnyök akkor is fennállnak, ha a pufferelt adatokat egyszer írják a pufferbe, és egyszer olvassák a pufferből.
A gyorsítótár szintén növeli az átviteli teljesítményt. A növekedés egy része ugyancsak abból a lehetőségből ered, hogy több kis átvitel egyetlen nagy blokkban egyesül. A fő teljesítménynövekedés azonban azért következik be, mert jó esély van arra, hogy ugyanazt az adatot többször is kiolvassuk a gyorsítótárból, vagy hogy az írott adatokat hamarosan beolvassuk. A gyorsítótárak egyetlen célja, hogy csökkentsék a mögöttes lassabb tárolóhoz való hozzáféréseket. A gyorsítótár általában egy absztrakciós réteg is, amelyet úgy terveztek, hogy a szomszédos rétegek szempontjából láthatatlan legyen. Így az alkalmazások vagy az ügyfelek esetleg nem is tudnak a gyorsítótár létezéséről.
Kérdések és válaszok
K: Mi az a gyorsítótárazás?
V: A gyorsítótárazás az informatikában használt kifejezés, amely a gyakran használt adatok másolatainak tárolására utal annak érdekében, hogy azokhoz gyorsabban lehessen hozzáférni, mintha az eredeti adatokat újra le kellene hívni vagy újra ki kellene számítani.
K: Hogyan működik a gyorsítótárazás?
V: A gyorsítótárazás úgy működik, hogy kétféle adattárolót használ: az egyik általában elég nagy, de lassan hozzáférhető, a másik pedig sokkal gyorsabban hozzáférhető, de általában kisebb. A gyorsítótárazás lényege, hogy a gyors adathordozót az adatok másolatainak tárolására használjuk, így az eredeti adatok elérése kevesebb időt vesz igénybe vagy kevésbé költséges.
K: Mi az a puffer?
V: A puffer hasonló a gyorsítótárhoz, mivel az adatok másolatait tárolja a gyorsabb hozzáférés érdekében, azonban a puffer esetében az adatokhoz hozzáférő ügyfél tudja, hogy van egy puffer, és azt egy alkalmazás kezeli, míg a gyorsítótár esetében az ügyfeleknek nem kell tudniuk a gyorsítótár létezéséről.
K: Mit jelent a hivatkozás helyzete?
V: A hivatkozás lokalitása azt jelenti, hogy amikor egy alkalmazás hozzáfér a strukturált adatok bizonyos blokkjaihoz, akkor valószínűleg más, az eredetileg elért blokkokhoz közeli blokkokhoz is hozzáfér. Ez segíti a gyorsítótárak jó működését, mivel ezek jellemzően kicsik az összes rendelkezésre álló adathoz képest.
K: Miért tart tovább a nagyobb gyorsítótáraknak a bejegyzések keresése?
V: A nagyobb gyorsítótárak azért tartanak tovább, mert több tárolt információt tartalmaznak, és ezért több időre van szükségük a kereséshez. Emellett drágábbak is, mivel több erőforrást igényelnek a tároláshoz.
K: Hogyan segíthet a lokalitás abban, hogy a gyorsítótárak jobban működjenek?
V: A lokalitás segít a gyorsítótárak jobb működésében, mivel amikor az alkalmazások hozzáférnek bizonyos strukturált adatblokkokhoz, valószínűleg más, közeli blokkokra is szükségük lesz, amelyeket gyorsan le lehet hívni a gyorsítótárból, ahelyett, hogy máshonnan kellene azokat lekérni vagy újra kiszámítani.
Keres