Cache (databehandling) - Cache (computing)
I databehandling , en cache ( / k æ ʃ / ( lytt ) 
Kash , eller / k eɪ ʃ / kaysh i australsk engelsk ) er en maskinvare eller programvare komponent som lagrer data slik at fremtidige forespørsler for at data kan serveres raskere; dataene som er lagret i en cache kan være et resultat av en tidligere beregning eller en kopi av data som er lagret andre steder. Et hurtigbuffertreff oppstår når de forespurte dataene kan bli funnet i en hurtigbuffer, mens et cachemiss oppstår når det ikke kan. Cache -treff blir servert ved å lese data fra cachen, som er raskere enn å beregne et resultat på nytt eller lese fra et tregere datalagring; dermed flere forespørsler som kan betjenes fra hurtigbufferen, jo raskere utfører systemet.
For å være kostnadseffektiv og for å muliggjøre effektiv bruk av data må cachene være relativt små. Likevel har cacher bevist seg på mange databehandlingsområder, fordi typiske dataprogrammer får tilgang til data med en høy grad av lokalitet . Slike tilgangsmønstre viser tidsmessig lokalitet, hvor det etterspørres data som nylig er blitt forespurt allerede, og romlig lokalitet, der det blir forespurt data som er lagret fysisk nær data som allerede er blitt etterspurt.
Motivasjon
Det er en iboende avveining mellom størrelse og hastighet (gitt at en større ressurs innebærer større fysiske avstander), men også en avveining mellom dyre, førsteklasses teknologier (som SRAM ) vs billigere, lett masseproduserte varer (for eksempel DRAM eller hard disker ).
Den buffering levert av en hurtigbuffer tjener en eller begge av latens og gjennomstrømning ( båndbredde ):
Ventetid
En større ressurs medfører en betydelig ventetid for tilgang - for eksempel kan det ta hundrevis av klokkesykluser for en moderne 4 GHz -prosessor å nå DRAM . Dette dempes ved å lese i store biter, i håp om at påfølgende lesninger vil komme fra steder i nærheten. Forutsigelser eller eksplisitt forhåndshenting kan også gjette hvor fremtidige lesninger kommer fra og komme med forespørsler på forhånd; hvis det gjøres riktig, er latensen helt omgått.
Gjennomstrømning
Bruken av en hurtigbuffer tillater også høyere gjennomstrømning fra den underliggende ressursen, ved å sette sammen flere finkornoverføringer til større og mer effektive forespørsler. Når det gjelder DRAM -kretser, kan dette betjenes ved å ha en bredere databuss. Vurder for eksempel et program som får tilgang til byte i et 32-biters adresserom , men blir betjent av en 128-bit off-chip databuss; individuelle ikke -bufrede byte -tilganger tillater bare 1/16 av den totale båndbredden, og 80% av databevegelsen ville være minneadresser i stedet for selve dataene. Å lese større biter reduserer brøkdelen av båndbredden som kreves for å overføre adresseinformasjon.
Operasjon
Maskinvare redskaper cache som en blokk med minne for midlertidig lagring av data sannsynlig å bli brukt igjen. Sentrale prosessorenheter (CPUer) og harddiskstasjoner (HDD-er) bruker ofte en maskinvarebasert hurtigbuffer, mens nettlesere og webservere ofte er avhengige av programvarebuffer.
En cache består av en mengde oppføringer. Hver oppføring har tilhørende data , som er en kopi av de samme dataene i en eller annen lagringslager . Hver oppføring har også en tag , som angir identiteten til dataene i backinglageret som oppføringen er en kopi av. Merking gjør at samtidige cache-orienterte algoritmer kan fungere på flerlags måte uten differensiell reléinterferens.
Når hurtigbufferklienten (en CPU, nettleser, operativsystem ) må ha tilgang til data som antas å eksistere i backing -butikken, sjekker den først bufferen. Hvis en oppføring kan bli funnet med en tag som samsvarer med den for de ønskede dataene, brukes dataene i oppføringen i stedet. Denne situasjonen er kjent som en hurtigbuffer. For eksempel kan et nettleserprogram sjekke den lokale hurtigbufferen på disken for å se om den har en lokal kopi av innholdet på en webside på en bestemt URL . I dette eksemplet er URL -en taggen, og innholdet på nettsiden er dataene. Prosentandelen tilganger som resulterer i hurtigbuffertreff er kjent som trefffrekvensen eller treffforholdet til bufferen.
Den alternative situasjonen, når cachen er sjekket og ikke inneholder noen oppføring med ønsket tag, er kjent som en cache -miss. Dette krever en dyrere tilgang til data fra støttebutikken. Når de forespurte dataene er hentet, blir de vanligvis kopiert til bufferen, klar for neste tilgang.
Under en cache -savning blir noen andre tidligere eksisterende cache -oppføringer fjernet for å gi plass til de nylig hentede dataene. Den heuristiske brukes til å velge inngang for å erstatte er kjent som erstatning politikk . En populær erstatningspolicy, "minst nylig brukt" (LRU), erstatter den eldste oppføringen, oppføringen som ble åpnet mindre nylig enn noen annen oppføring (se hurtigbufferalgoritme ). Mer effektive hurtigbufringsalgoritmer beregner bruk-treff-frekvensen mot størrelsen på det lagrede innholdet, samt latensene og gjennomgangene for både hurtigbufferen og backing-butikken. Dette fungerer bra for større datamengder, lengre forsinkelser og langsommere gjennomføringer, for eksempel harddisker og nettverk, men er ikke effektivt for bruk i en CPU -cache.
Skrive politikk
Når et system skriver data til cache, må det på et tidspunkt skrive disse dataene også til backing -butikken. Tidspunktet for denne skrivingen styres av det som kalles skrivepolitikken . Det er to grunnleggende skrivemetoder:
- Gjennomskriving : skriving utføres synkront både til hurtigbufferen og til backing-butikken.
- Tilbakeføring (også kalt skrive-bak ): I utgangspunktet skrives det bare til hurtigbufferen. Skrivingen til støttebutikken blir utsatt til det endrede innholdet er i ferd med å bli erstattet av en annen hurtigbufferblokk.
En tilbakeslagsbuffer er mer kompleks å implementere, siden den må spore hvilke av stedene som er skrevet over, og markere dem som skitne for senere skriving til støttebutikken. Dataene på disse stedene skrives bare tilbake til støttebutikken når de blir kastet ut av hurtigbufferen, en effekt referert til som lat skriving . Av denne grunn vil en lesemiss i en tilbakeføringsbuffer (som krever at en blokk skal erstattes av en annen) ofte kreve to minnetilganger til tjenesten: en for å skrive de erstattede dataene fra bufferen tilbake til butikken, og deretter en for å hente de nødvendige dataene.
Andre retningslinjer kan også utløse tilbakeføring av data. Klienten kan gjøre mange endringer i data i hurtigbufferen, og deretter eksplisitt varsle hurtigbufferen om å skrive tilbake dataene.
Siden ingen data blir returnert til rekvirenten om skriveoperasjoner, må det tas en beslutning om skrivefeil, om data vil bli lastet inn i hurtigbufferen eller ikke. Dette er definert av disse to tilnærmingene:
- Skrivetildeling (også kalt fetch on write ): data på det tapte skrive-stedet lastes inn i hurtigbufferen, etterfulgt av en skrive-hit-operasjon. I denne tilnærmingen ligner skrivefeil på lesemiss.
- Ikke-skrive-allokering (også kalt skrive-nei-tildele eller skrive rundt ): data på det tapte skrive-stedet lastes ikke inn i hurtigbufferen, og skrives direkte til støttebutikken. I denne tilnærmingen blir data lastet inn i hurtigbufferen på bare skrivefeil.
Både gjennomskrivnings- og tilbakekallingspolicyer kan bruke en av disse retningslinjene for glipp av skrivefeil, men vanligvis er de paret på denne måten:
- En tilbakeslagsbuffer bruker skrivefordeling, i håp om påfølgende skriver (eller til og med leser) til samme sted, som nå er bufret.
- En skrivebuffer bruker allokeringsfri tildeling. Her har påfølgende skriver ingen fordel, siden de fremdeles må skrives direkte til støttebutikken.
Andre enheter enn hurtigbufferen kan endre dataene i backing-butikken, i så fall kan kopien i hurtigbufferen bli utdatert eller foreldet . Alternativt, når klienten oppdaterer dataene i hurtigbufferen, blir kopier av dataene i andre hurtigbuffere foreldede. Kommunikasjonsprotokoller mellom hurtigbufferansvarlige som holder dataene konsistente er kjent som koherensprotokoller .
Forhåndshent
På en cache lesefeil, cacher med en etterspørsel paging politikk lese minimumsbeløpet fra kompet butikken. For eksempel leser virtuelt minne med etterspørselssøk en side med virtuelt minne (ofte 4 kBytes) fra disken til diskbufferen i RAM. For eksempel leser en typisk CPU en enkelt L2 -hurtigbufferlinje på 128 byte fra DRAM til L2 -hurtigbufferen, og en enkelt L1 -hurtigbufferlinje på 64 byte fra L2 -hurtigbufferen til L1 -hurtigbufferen.
Cacher med en forhåndsinnhentingskø eller mer generell foregående retningslinjer for personsøking går lenger - de leser ikke bare den forespurte delen, men tipper at den neste delen eller to snart vil bli påkrevd, og derfor forhåndshenter de dataene i bufferen på forhånd. Forventende personsøk er spesielt nyttig når backing -butikken har lang ventetid for å lese den første delen og mye kortere tid for å lese de neste bitene i rekkefølge, for eksempel disklagring og DRAM .
Noen få operativsystemer går videre med en laster (databehandling) som alltid forhåndslaster hele den kjørbare filen til RAM.
Noen få cacher går enda lenger, ikke bare forhåndsinnlasting av en hel fil, men begynner også å laste inn andre relaterte filer som snart kan bli forespurt, for eksempel sidebufferen som er knyttet til en forhåndsinnretning eller nettbufferen som er knyttet til forhåndshenting av lenker .
Eksempler på maskinvarebuffere
CPU -cache
Små minner på eller nær CPU kan operere raskere enn det mye større hovedminnet . De fleste CPUer siden 1980 -tallet har brukt en eller flere cacher, noen ganger i kaskade nivåer ; moderne avanserte innleiret , stasjonære og server mikroprosessorer kan ha så mange som seks typer av hurtigbufferen (mellom nivåer og funksjoner). Eksempler på cacher med en spesifikk funksjon er D-cachen og I-cachen og oversettelsen lookaside buffer for MMU .
GPU -cache
Tidligere grafikkprosessorer (GPU) hadde ofte begrensede skrivebeskyttede tekstur cacher , og introduserte Morton For stokket teksturer å forbedre 2D hurtigbufferkoherensen . Cache -feil ville påvirke ytelsen drastisk, f.eks. Hvis ikke kartlegging ble brukt. Caching var viktig for å utnytte 32-biters (og bredere) overføringer for teksturdata som ofte var så lite som 4 biter per piksel, indeksert i komplekse mønstre av vilkårlige UV-koordinater og perspektivtransformasjoner i invers teksturkartlegging .
Etter hvert som GPU -er avanserte (spesielt med GPGPU computere shaders ) har de utviklet seg gradvis større og stadig mer generelle cacher, inkludert instruksjonsbuffere for shaders , som viser stadig mer vanlig funksjonalitet med CPU -cacher. For eksempel hadde GT200 arkitektur GPUer ikke en L2-cache, mens Fermi GPU har 768 KB siste cache, Kepler GPU har 1536 KB siste cache og Maxwell GPU har 2048 KB cache på siste nivå . Disse cachene har vokst til å håndtere synkroniseringsprimitiver mellom tråder og atomoperasjoner , og grensesnitt med en CPU-stil MMU .
DSP -er
Digitale signalprosessorer har på samme måte generalisert gjennom årene. Tidligere design brukte scratchpad-minne som ble matet av DMA , men moderne DSP-er som Qualcomm Hexagon inkluderer ofte et veldig likt sett med cacher som en CPU (f.eks. Modifisert Harvard-arkitektur med delt L2, delt L1 I-cache og D-cache).
Oversettelse lookaside buffer
En minnestyringsenhet (MMU) som henter sidetabelloppføringer fra hovedminnet, har en spesialisert hurtigbuffer som brukes til å registrere resultatene av virtuell adresse til fysiske adresseoversettelser . Denne spesialiserte hurtigbufferen kalles en translation lookaside buffer (TLB).
Cache i nettverket
Informasjonssentrert nettverk
Informasjonssentrert nettverk (ICN) er en tilnærming for å utvikle Internett- infrastrukturen vekk fra et vertssentrisk paradigme, basert på evig tilkobling og ende-til-ende-prinsippet , til en nettverksarkitektur der fokuspunktet er identifisert informasjon (eller innhold eller data). På grunn av den innebygde hurtigbufringskapasiteten til nodene i et ICN, kan det ses på som et løst tilkoblet nettverk av hurtigbuffere, som har unike krav til hurtigbufrepolicyer. Imidlertid introduserer allestedsnærværende caching av innhold utfordringen med innholdsbeskyttelse mot uautorisert tilgang, noe som krever ekstra forsiktighet og løsninger. I motsetning til proxy-servere er hurtigbufferen i ICN en løsning på nettverksnivå. Derfor har den hurtig skiftende cache -tilstander og høyere ankomsthastigheter for forespørsel. Dessuten stiller mindre bufferstørrelser ytterligere en annen type krav til retningslinjene for utkastelse av innhold. Spesielt bør utkastelsespolitikk for ICN være rask og lett. Ulike cache -replikerings- og utkastingsordninger for forskjellige ICN -arkitekturer og applikasjoner er blitt foreslått.
Retningslinjer
Tidsbevisst minst nylig brukt (TLRU)
Tidsbevisst minst nylig brukt (TLRU) er en variant av LRU designet for situasjonen der det lagrede innholdet i hurtigbufferen har en gyldig levetid. Algoritmen er egnet i nettverksbuffer-applikasjoner, for eksempel informasjonssentrert nettverk (ICN), Content Delivery Networks (CDN) og distribuerte nettverk generelt. TLRU introduserer et nytt begrep: TTU (Time to Use). TTU er et tidsstempel for et innhold/en side som angir brukstid for innholdet basert på lokaliteten til innholdet og innholdsutgiverens kunngjøring. På grunn av dette lokalitetsbaserte tidsstemplet gir TTU mer kontroll til den lokale administratoren for å regulere i nettverkslagring. I TLRU -algoritmen, når et innhold kommer, beregner en hurtigbuffenode den lokale TTU -verdien basert på TTU -verdien som er tilordnet av innholdsutgiveren. Den lokale TTU -verdien beregnes ved å bruke en lokalt definert funksjon. Når den lokale TTU -verdien er beregnet, utføres erstatning av innhold på et delsett av det totale innholdet som er lagret i hurtigbuffernoden. TLRU sikrer at mindre populært og lite livsinnhold skal erstattes med innkommende innhold.
Minst hyppig nylig brukt (LFRU)
Det minst hyppig nylig brukte (LFRU) hurtigbufferutskiftingssystemet kombinerer fordelene med LFU- og LRU -ordninger. LFRU er egnet for 'in network' cache-applikasjoner, for eksempel informasjonssentrert nettverk (ICN), Content Delivery Networks (CDN) og distribuerte nettverk generelt. I LFRU er hurtigbufferen delt inn i to partisjoner kalt priviligerte og uprivilegerte partisjoner. Den privilegerte partisjonen kan defineres som en beskyttet partisjon. Hvis innholdet er svært populært, skyves det inn i den privilegerte partisjonen. Utskifting av den priviligerte partisjonen gjøres som følger: LFRU kaster ut innhold fra den uprivilegerte partisjonen, skyver innhold fra privilegerte partisjoner til uprivilegerte partisjoner, og legger til slutt inn nytt innhold i den privilegerte partisjonen. I prosedyren ovenfor brukes LRU for den priviligerte partisjonen, og en tilnærmet LFU (ALFU) -ordning brukes for den uprivilegerte partisjonen, derav forkortelsen LFRU. Grunnideen er å filtrere ut det lokalt populære innholdet med ALFU -opplegget og skyve det populære innholdet til en av de privilegerte partisjonene.
Værmelding
Tilbake i 2010 foreslo New York Times "Skriv" vær "etterfulgt av postnummeret ditt." I 2011 var bruk av smarttelefoner med alternativer for værvarsling altfor beskattende for AccuWeather -servere; to forespørsler i samme park ville generere separate forespørsler. En optimalisering av kant-servere for å kutte GPS-koordinatene til færre desimaler medførte at de bufrede resultatene fra den tidligere spørringen ville bli brukt. Antall oppslag til serveren per dag falt med halvparten.
Programvare cacher
Diskbuffer
Mens CPU -cacher generelt administreres utelukkende av maskinvare, administrerer en rekke programvarer andre cacher. Den siden cache i hovedminne, som er et eksempel på disk cache, styres av operativsystemet kjernen .
Mens diskbufferen , som er en integrert del av harddiskstasjonen, noen ganger blir villedende referert til som "diskbuffer", er hovedfunksjonene skrivesekvensering og lese forhåndshenting. Gjentatte cache -treff er relativt sjeldne, på grunn av bufferstørrelsen i forhold til stasjonens kapasitet. Imidlertid har high-end diskkontrollere ofte sin egen innebygde hurtigbuffer for harddiskens datablokker .
Til slutt kan en rask lokal harddisk også lagre informasjon som lagres på enda tregere datalagringsenheter, for eksempel eksterne servere ( webbuffer ) eller lokale båndstasjoner eller optiske jukebokser ; et slikt opplegg er hovedbegrepet for hierarkisk lagringsadministrasjon . Raske flash-baserte solid-state-stasjoner (SSD-er) kan også brukes som hurtigbuffere for langsommere harddisker med rotasjonsmedier, som fungerer sammen som hybridstasjoner eller solid-state-hybridstasjoner (SSHD-er).
Nettbuffer
Nettlesere og webproxy -servere bruker nettbuffere for å lagre tidligere svar fra webservere , for eksempel websider og bilder . Nettbuffere reduserer mengden informasjon som må overføres over nettverket, siden informasjon som tidligere er lagret i hurtigbufferen ofte kan brukes på nytt. Dette reduserer båndbredde og behandlingskrav til webserveren, og bidrar til å forbedre responsen for brukere av nettet.
Nettlesere bruker en innebygd hurtigbuffer, men noen Internett-leverandører (ISPer) eller organisasjoner bruker også en hurtigbuffer-proxy-server, som er en nettbuffer som deles mellom alle brukere av nettverket.
En annen form for cache er P2P-bufring , der filene som er mest søkt etter av node-til-node- applikasjoner, lagres i en ISP- buffer for å akselerere P2P-overføringer. På samme måte finnes det desentraliserte ekvivalenter, som gjør at lokalsamfunn kan utføre den samme oppgaven for P2P -trafikk, for eksempel Corelli.
Memoisering
En cache kan lagre data som er beregnet på forespørsel i stedet for å bli hentet fra en backing -butikk. Memoisering er en optimaliseringsteknikk som lagrer resultatene av ressurskrevende funksjonsanrop i en oppslagstabell, slik at påfølgende samtaler kan gjenbruke de lagrede resultatene og unngå gjentatt beregning. Det er relatert til den dynamiske programmeringsalgoritmedesignmetoden , som også kan betraktes som et middel for bufring.
Andre cacher
BIND DNS -demonen bufrer en kartlegging av domenenavn til IP -adresser , det samme gjør et resolverbibliotek.
Gjennomskrivningsoperasjon er vanlig når du opererer over upålitelige nettverk (som et Ethernet LAN), på grunn av den enorme kompleksiteten i koherensprotokollen som kreves mellom flere tilbakeføringsbuffer når kommunikasjon er upålitelig. For eksempel er nettsidebuffere og nettbaserte filsystembuffere på klientsiden (som i NFS eller SMB ) vanligvis skrivebeskyttet eller gjennomskrevet spesielt for å holde nettverksprotokollen enkel og pålitelig.
Søkemotorer gjør også ofte websider de har indeksert tilgjengelige fra hurtigbufferen. For eksempel gir Google en "Bufret" lenke ved siden av hvert søkeresultat. Dette kan være nyttig når nettsider fra en webserver er midlertidig eller permanent utilgjengelige.
En annen type bufring lagrer beregnede resultater som sannsynligvis vil være nødvendige igjen, eller memoisering . For eksempel er ccache et program som lagrer utdataene fra samlingen, for å få fart på senere kompileringskjøringer.
Databasebuffer kan forbedre gjennomstrømningen av databaseapplikasjoner vesentlig , for eksempel ved behandling av indekser , datalitteraturer og ofte brukte undersett av data.
En distribuert cache bruker nettverksverter for å gi skalerbarhet, pålitelighet og ytelse til applikasjonen. Vertene kan være samlokalisert eller spredt over forskjellige geografiske regioner.
Buffer vs. cache
Semantikken til en "buffer" og en "cache" er ikke helt annerledes; Likevel er det grunnleggende forskjeller i intensjon mellom cacheprosessen og bufferen.
Grunnleggende realiserer hurtigbufring en ytelsesøkning for overføringer av data som blir overført gjentatte ganger. Selv om et hurtigbufringssystem kan realisere en ytelsesøkning ved den første (vanligvis skrive) overføringen av et dataelement, skyldes denne ytelsesøkningen buffering som oppstår i hurtiglagringssystemet.
Med lese -hurtigbuffer må et dataelement ha blitt hentet fra sitt sted minst én gang for at senere lesinger av dataelementet skal realisere en ytelsesøkning i kraft av å kunne hentes fra hurtigbufferens (raskere) mellomlagring i stedet for dataens bosted. Med skrivebuffer kan en ytelsesøkning ved skriving av et dataelement realiseres ved første skriving av dataelementet i kraft av at dataelementet umiddelbart blir lagret i hurtigbufferens mellomlagring, og utsetter overføringen av dataelementet til dets eksisterende lagring kl. et senere stadium eller annet som en bakgrunnsprosess. I motsetning til streng buffering, må en hurtigbufringsprosess følge en (potensielt distribuert) cache -koherensprotokoll for å opprettholde konsistens mellom hurtigbufferens mellomlagring og stedet der dataene ligger. Buffering, derimot,
- reduserer antall overføringer for ellers nye data blant kommunikasjonsprosesser, som amortiserer overhead involvert for flere små overføringer over færre, større overføringer,
- gir en mellommann for å kommunisere prosesser som ikke er i stand til direkte overføringer mellom hverandre, eller
- sikrer en minimum datastørrelse eller representasjon som kreves av minst en av kommunikasjonsprosessene som er involvert i en overføring.
Med typiske hurtigbufferimplementeringer blir et dataelement som leses eller skrives for første gang, effektivt bufret; og i tilfelle av skrive, for det meste realisere en ytelsesøkning for applikasjonen der skriveren stammer fra. I tillegg er delen av en hurtigbufferprotokoll hvor individuelle skriver utsettes til en mengde skriver en form for buffering. Delen av en hurtigbufferprotokoll der individuelle avlesninger utsettes til en mengde leser, er også en form for buffering, selv om denne formen kan påvirke ytelsen til minst de første lesningene negativt (selv om det kan påvirke ytelsen til summen den enkelte leser). I praksis innebærer hurtigbufring nesten alltid en form for buffering, mens streng buffering ikke innebærer bufring.
En buffer er en midlertidig minneplassering som tradisjonelt brukes fordi CPU -instruksjoner ikke direkte kan adressere data som er lagret i eksterne enheter. Dermed brukes adresserbart minne som et mellomtrinn. I tillegg kan en slik buffer være mulig når en stor datablokk samles eller demonteres (etter behov fra en lagringsenhet), eller når data kan leveres i en annen rekkefølge enn den der den produseres. Også en hel buffer med data blir vanligvis overført sekvensielt (for eksempel til harddisken), så buffering i seg selv øker noen ganger overføringsytelsen eller reduserer variasjonen eller rystelsen av overføringens latens i motsetning til bufring der hensikten er å redusere latensen. Disse fordelene er tilstede selv om bufrede data skrives til bufferen én gang og leses fra bufferen én gang.
En cache øker også overføringsytelsen. En del av økningen kommer på samme måte fra muligheten for at flere små overføringer kombineres til en stor blokk. Men den viktigste ytelsesøkningen skjer fordi det er en god sjanse for at de samme dataene vil bli lest fra bufferen flere ganger, eller at skrevne data snart vil bli lest. En caches eneste formål er å redusere tilgangen til den underliggende langsommere lagringen. Cache er også vanligvis et abstraksjonslag som er designet for å være usynlig fra perspektivet til de nærliggende lagene.