Cache
Caching er et begreb, der anvendes inden for datalogi. Ideen bag en cache (udtales "cash" /ˈkæʃ/ KASH ) er meget enkel: Meget ofte er det meget tidskrævende at opnå et resultat for en beregning, så det er generelt en god idé at gemme resultatet. Der anvendes to slags lagringsmedier: Det ene er normalt ret stort, men det er "langsomt" at få adgang til det; det andet kan tilgås meget hurtigere, men er generelt lille. Den helt grundlæggende idé bag caching er at bruge det medie, der er hurtigst at tilgå, til at have kopier af data. Der er ingen forskel mellem kopien og originalen. Det kan tage lang tid at få adgang til de originale data, eller det kan være dyrt at gøre det (f.eks. resultaterne af et vanskeligt problem, som det tager lang tid at løse). Derfor er det meget "billigere" blot at bruge en kopi af dataene fra cachen. Sagt på en anden måde er en cache et midlertidigt lagerområde med kopier af data, der bruges ofte. Når der findes en kopi af dataene i denne cache, er det hurtigere at bruge denne kopi i stedet for at hente eller beregne de oprindelige data igen. Dette gør den gennemsnitlige tid, der er nødvendig for at få adgang til dataene, kortere. Når en ny værdi lægges i en cache, betyder det ofte, at en ældre værdi skal erstattes. Der findes forskellige idéer (normalt kaldet "strategier") om, hvordan man vælger den værdi, der skal erstattes.
En buffer minder meget om en cache. Den adskiller sig ved, at den klient, der får adgang til dataene i en buffer, ved, at der er en buffer; bufferen forvaltes af programmet. Med en cache behøver klienten, der får adgang til dataene, ikke at være klar over, at der er en cache.
Typiske computerprogrammer har adgang til data på meget lignende måder. Lad os antage, at dataene er struktureret i "blokke", som kan tilgås individuelt. Når et program får adgang til en blok, er det også meget sandsynligt, at det får adgang til (eller henviser til) en blok, der er "tæt på" den oprindelige blok. Dette er kendt som referencelokalitet. Der findes forskellige former for denne "lokalitet". Referencelokalitet er en af grundene til, at caches fungerer godt på mange områder inden for edb.
For at kunne fungere godt er cacheslagre små i forhold til den samlede mængde data. Jo større cachen er, jo længere tid tager det at slå en post op. Større caches er også dyrere at opbygge.
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.
