Cache
Caching är en term som används inom datavetenskap. Tanken bakom en cache (uttalas "cash" /ˈkæʃ/ KASH ) är mycket enkel: Det är ofta mycket tidskrävande att få fram ett resultat för en beräkning, så det är i allmänhet en bra idé att lagra resultatet. Två typer av lagringsmedier används: Den ena är vanligtvis ganska stor, men det är "långsamt" att komma åt den, medan den andra kan nås mycket snabbare, men den är vanligtvis liten. Den mycket grundläggande idén bakom caching är att använda det medium som är snabbt åtkomligt för att ha kopior av data. Det finns ingen skillnad mellan kopian och originalet. Det kan ta lång tid att få tillgång till originaldata, eller det kan vara dyrt att göra det (t.ex. resultaten av ett svårt problem som det tar lång tid att lösa). Därför är det mycket "billigare" att helt enkelt använda kopian av data från cacheminnet. Med andra ord är en cache ett tillfälligt lagringsområde med kopior av data som används ofta. När en kopia av data finns i denna cache är det snabbare att använda denna kopia än att hämta eller beräkna originaldata på nytt. Detta gör att den genomsnittliga tid som behövs för att komma åt uppgifterna blir kortare. Att lägga ett nytt värde i en cache innebär ofta att ett äldre värde måste ersättas. Det finns olika idéer (vanligen kallade "strategier") om hur man väljer vilket värde som ska ersättas.
En buffert är mycket lik en cache. Den skiljer sig från den i det avseendet att klienten som får tillgång till data i en buffert vet att det finns en buffert. I en cache behöver klienten som får tillgång till data inte veta att det finns en cache.
Typiska datorprogram har tillgång till data på mycket liknande sätt. Anta att uppgifterna är strukturerade i "block" som kan nås individuellt. När ett program får tillgång till ett block är det också mycket troligt att det får tillgång till (eller hänvisar till) ett block som ligger "nära" det ursprungliga blocket. Detta kallas för referenslokalitet. Det finns olika typer av sådan "lokalitet". Referenslokalitet är en av anledningarna till att cacheminnen fungerar bra inom många områden av databehandling.
För att fungera bra är cacheminnena små i förhållande till hela datamängden. Ju större cacheminnet är, desto längre tid tar det att söka upp en post. Större cacher är också dyrare att bygga.
Hur cacheminnen fungerar
En cache är ett minnesblock för lagring av data som sannolikt kommer att användas igen. Processorn och hårddisken använder ofta en cache, liksom webbläsare och webbservrar.
En cache består av många poster som kallas för en pool. Varje post innehåller ett datum (en bit data) som är en kopia av ett datum på ett annat ställe. Cacher använder vanligtvis en så kallad backing store. Backing stores är långsamma eller dyra att komma åt jämfört med cacheminnet. En diskcache använder till exempel en hårddisk som backing store. Varje post har också en liten information bifogad, en så kallad tagg. Denna tagg används för att hitta den plats där den ursprungliga datan är lagrad.
Caches för läsning
Om en klient (en CPU, en webbläsare eller ett operativsystem) vill komma åt en datamängd som den tror finns i cacheminnet, kontrollerar den först om datamängden finns i cacheminnet. Om datan kan hittas i cacheminnet kan klienten använda den och behöver inte använda huvudminnet. Detta kallas för en cacheträff. Ett webbläsarprogram kan till exempel kontrollera sin lokala cache på disken för att se om det finns en lokal kopia av innehållet i en webbsida på en viss URL. I det här exemplet är URL:en taggen och webbsidans innehåll datumet.
En annan situation som kan inträffa är att datumet med märkningen inte kan hittas i cachen. Detta kallas cache miss. Datumet måste hämtas från det stödjande lagret. Vanligtvis kopieras det till cacheminnet, så att det inte längre behöver hämtas från backing store nästa gång.
Cachen har bara en begränsad storlek. För att göra plats för den tidigare ej cachelagda posten kan en annan cachelagd post behöva tas bort från cachen. Särskilda regler används för att hitta den post som bäst bör tas bort. Dessa regler brukar kallas heuristik. Heuristik som används för att hitta posten kallas ersättningspolicy. En mycket enkel regel som används kallas Least recently used (LRU). Den tar helt enkelt den post som användes för längst tid sedan. Andra heuristiker finns förtecknade på cache-algoritmen...
Caches för skrivning
Cacher kan också användas för att skriva data. Fördelen med detta är att klienten kan fortsätta sin operation när posten har skrivits till cacheminnet; den behöver inte vänta tills posten har skrivits till backing store.
Men posten måste skrivas till backing-lagret vid någon tidpunkt. Tidpunkten för när detta sker styrs av skrivpolicyn.
I en skriv-cache skrivs varje post till backing store omedelbart, samtidigt som den lagras i cacheminnet.
Det andra alternativet är att endast skriva till cacheminnet och skriva till backing store senare. Detta kallas write-back (eller write-behind) cache. Cachen markerar de poster som ännu inte har skrivits till backing store; den markering som används kallas ofta dirty flag. Innan posterna raderas från cacheminnet skrivs de till backing store. Detta kallas lazy write. En miss i en write-back-cache (som kräver att ett block ersätts av ett annat) kräver ofta två minnesåtkomster: en för att hämta det nödvändiga datumet och en annan för att skriva ersatta data från cacheminnet till lagret.
Cachelagringspolicyn kan också ange att ett visst datum måste skrivas till cacheminnet. Klienten kan ha gjort många ändringar i datumet i cacheminnet. När den är klar kan den uttryckligen säga till cacheminnet att skriva tillbaka datumet.
No-write-allokering är en cachepolicy där endast läsning lagras i cacheminnet. På så sätt undviker man behovet av caching med skrivning tillbaka eller genomskrivning. Skrivningar görs hela tiden till backing store.
Klienten är inte det program som ändrar data i backup-lagret. Om data ändras i backup-lagret kommer kopian i cacheminnet att vara inaktuell eller inaktuell. Om klienten uppdaterar data i cacheminnet kommer kopior av dessa data i andra cacheminnen att bli inaktuella. Det finns särskilda kommunikationsprotokoll som gör det möjligt för cachehanterare att prata med varandra för att hålla uppgifterna meningsfulla. Dessa är kända som koherensprotokoll.
Diagram över en CPU-memory cache
Val av den post som ska ersättas
En cache är liten och den är full eller nästan full för det mesta. När ett nytt värde läggs till måste ett gammalt värde tas bort. Det finns olika sätt att göra detta urval:
- Först in först ut: Det är bara att ersätta den post som lades till i cachen för längst tid sedan.
- Senast använda: Denna idé liknar FIFO-principen ovan, men när en post används uppdateras dess tidsstämpel/ålder.
- Minst frekvent använt: Istället för att använda en tidsstämpel används en räknare som ökas varje gång en post används.
- Välj ett slumpmässigt bidrag
Historia
Ordet cache användes för första gången inom datateknik 1967, när en vetenskaplig artikel förbereddes för att publiceras i IBM Systems Journal. Artikeln handlade om en ny förbättring av minnet i Model 85. Model 85 var en dator i IBM System/360-produktlinjen. Tidskriftens redaktör ville ha ett bättre ord för höghastighetsbuffert, som användes i artikeln. Han fick inga förslag och föreslog cache, från franskans cacher, som betyder "gömma". Artikeln publicerades i början av 1968 och författarna hedrades av IBM. Deras arbete välkomnades allmänt och förbättrades. Cache blev snart standardanvändning i datalitteraturen.
Var cacheminnen används
CPU-caches
Små minnen på eller nära CPU-chipet kan göras snabbare än det mycket större huvudminnet. De flesta CPU:er sedan 1980-talet har använt en eller flera cacheminnen. Moderna allmännyttiga CPU:er i persondatorer kan ha så många som ett halvt dussin. Varje cacheminne kan vara specialiserat på en annan del av uppgiften att utföra program.
Disk caches
CPU-caches hanteras i allmänhet helt och hållet av hårdvara, medan andra caches hanteras av olika typer av programvara. Operativsystemet hanterar vanligtvis en sidcache i huvudminnet. Användare utanför datavetenskap brukar kalla denna cache för virtuellt minne. Den hanteras av operativsystemets kärna.
Moderna hårddiskar har diskbuffertar. Dessa kallas ibland för "diskcache", men det är fel. Buffertarnas huvudfunktion är att ordna skrivningar på disken och hantera läsningar. Upprepade cacheträffar är sällsynta, eftersom bufferten är mycket liten i förhållande till hårddiskens storlek.
Lokala hårddiskar är snabba jämfört med andra lagringsenheter, t.ex. fjärrservrar, lokala bandstationer eller optiska jukeboxar. Att använda lokala hårddiskar som cacheminnen är huvudkonceptet för hierarkisk lagringshantering.
Webbkakor
Webbläsare och webbproxyservrar använder cacheminnen för att lagra tidigare svar från webbservrar, t.ex. webbsidor. Webbcacher minskar mängden information som behöver överföras via nätverket. Information som tidigare lagrats i cacheminnet kan ofta återanvändas. Detta minskar bandbredden och behandlingskraven för webbservern och bidrar till att förbättra responsen för webbanvändarna.
Moderna webbläsare använder en inbyggd webbcache, men vissa internetleverantörer eller organisationer använder också en proxyserver för caching. Detta är en webbcache som delas mellan alla användare i nätverket.
Sökmotorerna gör också ofta webbsidor som de har indexerat tillgängliga från sin cache. Google tillhandahåller till exempel en länk "Cached" bredvid varje sökresultat. Detta är användbart när webbsidor är tillfälligt otillgängliga från en webbserver.
Cachelagring med opålitliga nätverk
Write-through-operation är vanligt i opålitliga nätverk (t.ex. Ethernet LAN). Protokollet som används för att se till att data i skrivcachen är meningsfulla när flera skrivcacher används är mycket komplicerat i ett sådant fall.
Till exempel är cacher för webbsidor och cacher för nätverksfilsystem på klientsidan (som i NFS eller SMB) vanligtvis skrivskyddade eller skrivskyddade för att hålla nätverksprotokollet enkelt och tillförlitligt.
Skillnaden mellan buffert och cache
Buffert och cache utesluter inte varandra, utan används ofta tillsammans. Anledningen till att de används är dock olika. En buffert är en plats i minnet som traditionellt används eftersom CPU-instruktioner inte direkt kan adressera data som lagras i perifera enheter. Datorminnet används som ett mellanlager.
Dessutom kan en sådan buffert vara användbar när ett stort datablock sätts samman eller tas isär (vilket krävs av en lagringsenhet), eller när data kan levereras i en annan ordning än den i vilken de produceras. En hel buffert med data överförs också vanligtvis sekventiellt (t.ex. till hårddisk), så att buffringen i sig själv ibland ökar överföringsprestandan. Dessa fördelar finns även om de buffrade uppgifterna skrivs till bufferten en gång och läses från bufferten en gång.
En cache ökar också överföringsförmågan. En del av ökningen kommer också från möjligheten att flera små överföringar kombineras till ett stort block. Men den huvudsakliga prestandaförbättringen beror på att det finns en god chans att samma data kommer att läsas från cacheminnet flera gånger, eller att skrivna data snart kommer att läsas. Caches enda syfte är att minska åtkomsten till den underliggande långsammare lagringen. Cache är också vanligtvis ett abstraktionslager som är utformat för att vara osynligt ur angränsande lagers perspektiv. På så sätt kan det hända att programmen eller klienterna inte är medvetna om att det finns en cache.
Frågor och svar
F: Vad är caching?
S: Caching är en term som används inom datavetenskapen och som syftar till att lagra kopior av data som används ofta för att få tillgång till dem snabbare än att hämta eller beräkna originaldata på nytt.
F: Hur fungerar caching?
S: Cachelagring fungerar genom att man använder två typer av lagringsmedier, ett som vanligtvis är ganska stort men långsamt att komma åt, och ett annat som man kan komma åt mycket snabbare men som i allmänhet är mindre. Tanken bakom caching är att använda det snabba mediet för att lagra kopior av data så att det tar mindre tid eller är billigare att komma åt originaldata.
F: Vad är en buffert?
S: En buffert liknar en cache i det avseendet att den lagrar kopior av data för snabbare åtkomst, men med en buffert vet den klient som får tillgång till data att det finns en buffert och att den hanteras av ett program, medan klienterna med en cache inte behöver vara medvetna om att det finns en cache.
F: Vad betyder referenslokalitet?
S: Referenslokalitet innebär att när ett program får tillgång till vissa block av strukturerade data är det troligt att det också får tillgång till andra block i närheten av de block som ursprungligen användes. Detta bidrar till att cacheminnen fungerar bra eftersom de vanligtvis är små jämfört med alla tillgängliga data.
F: Varför tar det längre tid för större cacheminnen att söka upp poster?
S: Större cacheminnen tar längre tid eftersom de innehåller mer lagrad information och därför kräver mer tid för sökning. De är också dyrare eftersom de kräver mer resurser för lagring.
Fråga: Hur kan lokalitet bidra till att cacheminnen fungerar bättre?
S: Lokalitet bidrar till att cacheminnen fungerar bättre eftersom när programmen får tillgång till vissa block av strukturerade data kommer de sannolikt också att behöva andra block i närheten, som då snabbt kan hämtas från cacheminnet i stället för att behöva hämta dem från annat håll eller beräkna dem på nytt.
