Cache i datalogi: Hvad er caching? Definition, funktion og strategier
Lær cache i datalogi: hvad caching er, hvordan det fungerer, og effektive erstatningsstrategier til hurtigere adgang, lavere latens og optimeret ydeevne.
Caching er et centralt begreb inden for datalogi. Ideen bag en cache (udtales "cash" /ˈkæʃ/ KASH) er enkel: hvis det er dyrt (i tid eller ressourcer) at beregne eller hente et resultat, kan man gemme en kopi, så efterfølgende forespørgsler kan få svaret meget hurtigere. Ofte findes to slags lagringsmedier: ét, der er stort, men relativt langsomt at få adgang til, og ét, der er lille, men meget hurtigt. Cachen placeres typisk mellem klienten og den langsommere lagerenhed og holder kopier af ofte brugte data. Dermed bliver den gennemsnitlige adgangstid reduceret, fordi mange forespørgsler kan besvares direkte fra den hurtige kopi.
Hvordan fungerer en cache?
Når et system forsøger at læse en bestemt enhed (f.eks. en blok eller et objekt), undersøger cachen først, om der findes en kopi. Hvis kopien findes, kaldes det et cache-hit — ellers et cache-miss. Ved et miss hentes data fra den langsommere kilde, og resultatet kan indsættes i cachen til senere genbrug. De vigtigste mål for en cache er derfor:
- Hitrate: andelen af forespørgsler, der resulterer i hits.
- Miss-penalty: hvor dyrt (i tid) det er at hente data ved et miss.
- Latens: hvor hurtigt cachen kan levere et svar.
Referencelokalitet
Caches virker godt, fordi programmer ofte viser referencelokalitet: når et program tilgår én blok, er det sandsynligt, at det snart tilgår data tæt på denne blok (lokalitet i tid og rum). Denne egenskab øger chancen for, at gemte kopier bliver genbrugt.
Buffer vs. cache
En buffer ligner en cache, men forskellen ligger i ejerforhold og forventning: en buffer bruges ofte som midlertidig lagerplads, hvor klienten ved, at data er buffered, og programmet styrer bufferen eksplicit. En cache er typisk transparent for klienten — klienten behøver ikke at vide, at der findes en cache.
Erstatningsstrategier (eviction policies)
Når cachen er fuld, skal en gammel post fjernes for at give plads til ny data. Almindelige strategier er:
- LRU (Least Recently Used): fjern den post, der er brugt længst tid siden.
- LFU (Least Frequently Used): fjern den, der er brugt mindst hyppigt.
- FIFO (First In, First Out): fjern den ældste post.
- Random: vælg en post tilfældigt — nemt at implementere og nogen gange tilstrækkeligt.
- CLOCK: en effektiv approximation af LRU, der er billig i implementering.
- Adaptive algoritmer som ARC kombinerer fordele fra flere strategier for bedre performance under varierede arbejdsbelastninger.
Skrivemodeller
Ved skrivning er der flere modeller, hver med sine trade-offs:
- Write-through: Skrivninger skrives både til cachen og til den bagvedliggende lagerenhed straks. Fordel: konsistens. Ulempe: langsommere skrivninger.
- Write-back (eller write-behind): Skrivninger markeres i cachen som “dirty” og skrives senere tilbage til hovedlageret. Fordel: hurtigere skrivninger; ulempe: kompleksitet ved flush og større risiko for tab ved fejl.
- Write-around: Skrivninger springer ofte cachen over og går direkte til hovedlageret, hvilket kan forhindre at cache fyldes med data, der sjældent læses.
Cache-arkitektur og associativitet
Caches kan organiseres forskelligt:
- Direct-mapped: hver blok i hovedlageret har én bestemt plads i cachen — enkel og hurtig, men kan give konflikter.
- Fully associative: en blok kan placeres i enhver cache-slot — fleksibelt, men kræver søgning i mange poster.
- Set-associative: kompromis, hvor cachen er delt i sæt, og hver blok kan placeres i et sæt af N slots (f.eks. 4-værelses set-associative).
Typer og lag af caches
Caching anvendes i mange niveauer og i forskellige former:
- CPU-caches (L1, L2, L3): små, hurtige caches tæt på processoren.
- Disk- og sidecacher (f.eks. OS page cache): reducerer disk-I/O.
- Browser-caching: gemmer ressourcer som HTML, CSS og billeder lokalt for at minimere netværksanmodninger.
- Reverse proxy / CDN: cache af webindhold tættere på brugerne for at reducere latenstid og belastning på oprindelsesserveren.
- Applikationscaches (f.eks. in-memory stores som Redis eller Memcached): bruges til hyppigt brugte objekter i dit backend.
Konsistens, invalidering og problemer
Et af de sværeste aspekter ved caching er at holde data konsistente:
- Cache-invalidation er nødvendigt, når data i den langsomme kilde ændres — strategier inkluderer eksplicit invalidering, TTL (time-to-live) og write-through for at minimere inkonsistens.
- I distribuerede systemer kræver cache-konsistens protokoller (f.eks. MESI i multiprocessorsystemer) eller koordinering mellem noder.
- Andre problemer: cache stampede (mange klienter forsøger samtidig at genopbygge en udløbet cache-post), thundering herd, samt memory leaks hvis entries aldrig fjernes uden TTL.
Ydeevneovervejelser og praktische råd
- Mål din hitrate og latency — det er de vigtigste mål for at vurdere cache-effektivitet.
- Vælg erstatningsstrategi ud fra arbejdsprofilen: LRU er ofte et godt udgangspunkt, men LFU kan være bedre for stabilt populære objekter.
- Brug cache-aside-mønsteret i applikationer: applikationen tjekker cachen først, henter fra kilden ved miss og opdaterer cachen.
- Håndter cache-stampede ved at bruge låse, jitterede TTL'er eller "singleflight" mekanismer, som koordinerer genopbygning af en post.
- Overvej forudindlæsning (prefetching) for arbejdsbelastninger med stærk prædiktiv lokalitet, men undgå over-prefetching, som kan forurene cachen.
- Balancer størrelse og adgangstid: større caches kan øge hitrate, men også gøre lookup langsommere og dyrere i hardware.
Opsummering
En cache er et midlertidigt lager med kopier af ofte anvendte data, designet til at reducere den gennemsnitlige adgangstid. Caches bygger på lokalitet i programmer, bruger forskellige arkitekturer og erstatningsstrategier og findes i mange varianter (CPU, disk, web, applikation). De største udfordringer er korrekt invalidering, konsistens og håndtering af corner-cases som cache-stampede. Med de rette strategier og målinger kan caching give dramatisk bedre ydeevne og effektivitet.
Sådan fungerer caches
En cache er en blok af hukommelse til lagring af data, som sandsynligvis vil blive brugt igen. CPU'en og harddisken bruger ofte en cache, og det samme gør webbrowsere og webservere.
En cache består af mange poster, der kaldes en pulje. Hver post indeholder et datum (en bit data), som er en kopi af et datum et andet sted. Caches bruger normalt det, der kaldes et backing store. Backing stores er langsomme eller dyre at få adgang til sammenlignet med cachen. En diskcache bruger f.eks. en harddisk som backing store. Hver post har også en lille oplysning vedhæftet, et såkaldt tag. Dette tag bruges til at finde den placering, hvor de oprindelige data er gemt.
Caches til læsning
Hvis en klient (en CPU, en webbrowser, et operativsystem) ønsker at få adgang til en data, som den tror, at den befinder sig i backup-lageret, kontrollerer den først, om dataet kan findes i cachen. Hvis dataene kan findes i cachen, kan klienten bruge dem og behøver ikke at bruge hovedhukommelsen. Dette kaldes et cachetræf. Et webbrowserprogram kan f.eks. kontrollere sin lokale cache på disken for at se, om det har en lokal kopi af indholdet af en webside på en bestemt URL-adresse. I dette eksempel er URL-adressen tagget, og indholdet af websiden er datumet.
Den anden situation, der kan opstå, er, at datumet med mærket ikke kan findes i cachen. Dette kaldes cache miss. Datoen skal hentes fra backing-lageret. Normalt kopieres det til cachen, så det næste gang ikke længere skal hentes fra backing-lageret.
Cachen har kun en begrænset størrelse. For at gøre plads til den tidligere ikke-cachelagrede post kan det være nødvendigt at slette en anden cachetpost fra cachen for at få plads til den. Der anvendes særlige regler til at finde den post, der bedst kan slettes. Disse regler kaldes normalt heuristikker. De heuristikker, der anvendes til at finde posten, kaldes erstatningspolitik. En meget enkel regel, der anvendes, kaldes Least recently used (eller LRU). Den tager simpelthen den post, der blev brugt for længst tid siden. Andre heuristikker er anført på cache-algoritmen...
Caches til skrivning
Caches kan også bruges til at skrive data; fordelen ved dette er, at klienten kan fortsætte sin operation, når posten er blevet skrevet til cachen; den behøver ikke at vente, indtil posten er skrevet til backing-lageret.
Indtastningen skal dog skrives til backing-lageret på et tidspunkt. Tidspunktet for, hvornår dette sker, styres af skrivepolitikken.
I en write-through-cache skrives hver post til backing-lageret med det samme, samtidig med at den gemmes i cachen.
Den anden mulighed er kun at skrive til cache og skrive til backing-lageret senere. Dette kaldes write-back (eller write-behind) cache. Cachen markerer de poster, der endnu ikke er blevet skrevet til backing-lageret; det anvendte mærke kaldes ofte dirty flag. Før posterne slettes fra cachen, skrives de til backing-lageret. Dette kaldes lazy write (doven skrivning). En fejl i en write-back cache (som kræver, at en blok erstattes af en anden) vil ofte kræve to hukommelsestilgange: en for at hente det nødvendige datum og en anden for at skrive de erstattede data fra cachen til lageret.
Caching-politikken kan også angive, at et bestemt datum skal skrives til cache. Klienten kan have foretaget mange ændringer i datumet i cachen. Når den er færdig, kan den udtrykkeligt bede cachen om at skrive datumet tilbage.
No-write-allokering er en cachepolitik, hvor kun læsninger lagres i cachen. På denne måde undgås behovet for caching med skrive tilbage- eller skrive-gennem-caching. Der skrives hele tiden til backing-lageret.
Klienten er ikke det program, der ændrer data i backup-lageret. Hvis dataene ændres i backing-lageret, vil kopien i cachen være forældet eller forældet. Alternativt vil kopier af disse data i andre caches blive forældede, når klienten opdaterer dataene i cachen. Der findes særlige kommunikationsprotokoller, som gør det muligt for cache-administratorer at tale sammen for at holde dataene meningsfulde. Disse er kendt som kohærensprotokoller.
Diagram over en CPU-hukommelsescache
Valg af den post, der skal erstattes
En cache er lille, og den vil være fuld, eller næsten fuld, det meste af tiden. Så når der tilføjes en ny værdi, skal en gammel værdi fjernes. Der er forskellige måder, hvorpå denne udvælgelse kan foretages:
- Først ind først ud: Du skal blot erstatte den post, der blev tilføjet til cachen for længst tid siden.
- Mindst nylig anvendt: Denne idé svarer til FIFO-princippet ovenfor, men når en post bruges, opdateres dens tidsstempel/alder.
- Mindst hyppigt anvendt: I stedet for at bruge et tidsstempel anvendes en tæller, som øges hver gang en post bruges.
- Vælg en tilfældig post
Historie
Ordet cache blev første gang brugt inden for databehandling i 1967, da en videnskabelig artikel blev forberedt med henblik på offentliggørelse i IBM Systems Journal. Artiklen handlede om en ny forbedring af hukommelsen i Model 85. Model 85 var en computer i IBM System/360-produktserien. Redaktøren af Journal ønskede et bedre ord for high-speed buffer, som blev brugt i artiklen. Han fik ikke noget forslag og foreslog cache, der kommer fra fransk cacher, som betyder "at gemme sig". Artiklen blev offentliggjort i begyndelsen af 1968, og forfatterne blev hædret af IBM. Deres arbejde blev hilst bredt velkommen og forbedret. Cache blev hurtigt standard i computerlitteraturen.
Hvor caches anvendes
CPU-caches
Små hukommelser på eller tæt på CPU-chippen kan gøres hurtigere end den meget større hovedhukommelse. De fleste CPU'er siden 1980'erne har brugt en eller flere caches. Moderne universal-CPU'er i personlige computere kan have op til et halvt dusin. Hver cache kan være specialiseret til en anden del af opgaven med at afvikle programmer.
Disk caches
CPU-caches forvaltes generelt udelukkende af hardware, mens andre caches forvaltes af en anden form for software. Operativsystemet administrerer normalt en sidecache i hovedhukommelsen. Brugere uden for datalogi kalder normalt denne cache for virtuel hukommelse. Den forvaltes af styresystemets kerne.
Moderne harddiske har diskbuffere. Disse kaldes nogle gange "disk cache", men det er forkert. Hovedfunktionen for disse buffere er at ordne diskskrivninger og styre læsninger. Det er sjældent, at der er gentagne cache-hits, fordi bufferen er meget lille i forhold til harddiskens størrelse.
Lokale harddiske er hurtige sammenlignet med andre lagringsenheder, f.eks. fjernservere, lokale bånddrev eller optiske jukebokse. Anvendelse af lokale harddiske som caches er hovedkonceptet i hierarkisk lagerstyring.
Web caches
Webbrowsere og webproxyservere bruger caches til at gemme tidligere svar fra webservere, f.eks. websider. Webcacher reducerer mængden af oplysninger, der skal overføres via netværket. Oplysninger, der tidligere er gemt i cachen, kan ofte genbruges. Dette reducerer webserverens båndbredde og behandlingskrav og bidrager til at forbedre webbrugernes reaktionsevne.
Moderne webbrowsere bruger en indbygget webcache, men nogle internetudbydere eller organisationer bruger også en cache-proxyserver. Dette er en webcache, som deles mellem alle brugere på netværket.
Søgemaskinerne gør også ofte websider, som de har indekseret, tilgængelige fra deres cache. Google har f.eks. et "Cached"-link ved siden af hvert søgeresultat. Dette er nyttigt, når websider midlertidigt er utilgængelige fra en webserver.
Caching med upålidelige netværk
Write-through-drift er almindeligt i upålidelige netværk (som f.eks. et Ethernet LAN). Den protokol, der anvendes til at sikre, at dataene i skrivecachen giver mening, når der anvendes flere skrivecacher, er meget kompleks i et sådant tilfælde.
F.eks. er websidecaches og netværksfilsystemcaches på klientsiden (f.eks. i NFS eller SMB) typisk skrivebeskyttede eller skrivebeskyttede for at holde netværksprotokollen enkel og pålidelig.
Forskellen mellem buffer og cache
Buffer og cache udelukker ikke hinanden; de bruges også ofte sammen. Grunden til, at de bruges, er dog forskellig. En buffer er en placering i hukommelsen, der traditionelt bruges, fordi CPU-instruktioner ikke kan adressere data, der er gemt i perifere enheder, direkte. Computerhukommelse bruges som et mellemlager.
Desuden kan en sådan buffer være anvendelig, når en stor blok af data samles eller adskilles (som krævet af en lagerenhed), eller når data kan leveres i en anden rækkefølge end den, hvori de er produceret. Desuden overføres en hel buffer af data normalt sekventielt (f.eks. til en harddisk), så buffering i sig selv kan undertiden øge overførselsydelsen. Disse fordele er til stede, selv om de bufferede data skrives til bufferen én gang og læses fra bufferen én gang.
En cache øger også overførselsydelsen. En del af denne forbedring skyldes ligeledes, at flere små overførsler kan kombineres til én stor blok. Men den største ydelsesforøgelse opstår, fordi der er en god chance for, at det samme datum vil blive læst fra cachen flere gange, eller at skrevne data snart vil blive læst. Det eneste formål med caches er at reducere adgangen til det underliggende langsommere lager. Cache er også normalt et abstraktionslag, der er designet til at være usynligt set fra de tilstødende lags perspektiv. På den måde er programmerne eller klienterne måske ikke klar over, at der findes en cache.
Spørgsmål og svar
Sp: Hvad er caching?
Svar: Caching er et begreb, der anvendes inden for datalogi, og som henviser til praksis med at gemme kopier af data, der bruges ofte, for at få adgang til dem hurtigere end ved at hente eller beregne de oprindelige data igen.
Spørgsmål: Hvordan fungerer caching?
Svar: Caching fungerer ved at bruge to slags lagringsmedier, et som normalt er ret stort, men langsomt tilgængeligt, og et andet som kan tilgås meget hurtigere, men som generelt er mindre. Idéen bag caching er at bruge det hurtige medie til at gemme kopier af data, så det tager mindre tid eller er billigere at få adgang til de originale data.
Spørgsmål: Hvad er en buffer?
A: En buffer ligner en cache, idet den gemmer kopier af data for at opnå hurtigere adgang, men med en buffer ved klienten, der får adgang til dataene, at der er en buffer, og at den forvaltes af et program, mens klienterne med en cache ikke behøver at være klar over, at der er en cache.
Spørgsmål: Hvad betyder referencelokalitet?
Svar: Lokalitet af reference betyder, at når et program får adgang til visse blokke af strukturerede data, vil det sandsynligvis også få adgang til andre blokke i nærheden af de blokke, der oprindeligt blev tilgået. Dette bidrager til, at caches fungerer godt, da de typisk er små i forhold til alle tilgængelige data.
Spørgsmål: Hvorfor tager det længere tid for større caches at slå poster op?
Svar: Større caches tager længere tid, fordi de indeholder flere lagrede oplysninger og derfor kræver mere tid til opslag. De er også dyrere, da de kræver flere ressourcer til lagring.
Spørgsmål: Hvordan kan lokalitet bidrage til at få caches til at fungere bedre?
Svar: Lokalitet er med til at få cacher til at fungere bedre, fordi når programmerne får adgang til visse blokke af strukturerede data, vil de sandsynligvis også få brug for andre blokke i nærheden, som så hurtigt kan hentes fra cachen i stedet for at skulle hente dem et andet sted fra eller beregne dem igen.
Søge