Kešēšana ir datorzinātnē lietots termins. Kešatmiņas (izrunā "cash" /ˈkæʃ/ KASH ) būtība ir vienkārša: daudzas darbības vai piekļuve datiem ir laikietilpīgas vai dārgas, tāpēc to rezultātu saglabāšana īslaicīgā, ātri pieejamā atmiņā parasti samazina kopējo izpildes laiku. Parasti lieto divu veidu datu glabāšanas līdzekļus: viens ir liels, bet lēnāk pieejams; otrs — mazāks, taču daudz ātrāk piekļūstams. Kešatmiņas pamatideja ir saglabāt datu kopiju uz ātrāka nesēja, tādējādi izmantojot šo kopiju, nevis atkārtoti izgūt vai pārrēķināt oriģinālos datus. Ja kešatmiņā ir vajadzīgā informācija, lietojumprogramma vai sistēma var to izmantot daudz ātrāk — to sauc par kešēšanas "hit". Ja dati kešā nav, ir "miss" un jāpiekļūst lēnākam avotam, pēc tam parasti kešatmiņā tiek ievietota kopija. Tādejādi vidējais piekļuves laiks samazinās.

Jaunas vērtības ievietošana kešatmiņā bieži nozīmē, ka ir jāaizstāj kāda vecāka vērtība. Pastāv dažādas metodes (parasti sauktas par aizvietošanas stratēģijām), kā izlemt, kuru ierakstu noņemt. Kešatmiņu lietojuma piemēri aptver datus operētājsistēmu līmenī, tīmekli, datubāzes, DNS, kā arī procesoru līmeņa kešus.

Buferis ir ļoti līdzīgs kešatmiņai, taču atšķiras ar to, ka buferi pārvalda pašas lietojumprogrammas un klients parasti zina, ka buferis pastāv. Kešatmiņas gadījumā piekļuves klients nav obligāti informēts par kešēšanu.

Tipiskas lietojumprogrammas piekļūst datiem, izmantojot lokalitātes principu: ja tiek piekļūts vienam datublokam, ļoti iespējams, ka drīz tiks piekļūts arī "tuvam" blokam. To sauc par atsauces lokalitāti (temporal un spatial locality), un tā ir viens no galvenajiem iemesliem, kāpēc kešēšana bieži uzlabo veiktspēju.

Kešatmiņas darbības pamati

Galvenie jēdzieni:

  • Hit — pieprasītie dati ir kešatmiņā; piekļuve ātra.
  • Miss — dati nav kešā; jāiegūst no lēnākā avota (miss penalty).
  • Hit rate — daļa pieprasījumu, kas beidzas ar hit; augstāks hit rate nozīmē labāku efektivitāti.
  • Miss penalty — papildu laiks, kas nepieciešams, lai apstrādātu miss (datu ielāde no galvenā avota).
  • Associativity — veids, kā kešatmiņa organizē iespēju, kur saglabāt blokus (tieša adresācija, daļēji asociatīva, pilnīgi asociatīva).

Kešēšanas stratēģijas un aizvietošanas algoritmi

Kad kešatmiņa ir pilna, jāizvēlas, kuru elementu izņemt. Biežāk sastopamie algoritmi:

  • LRU (Least Recently Used) — izņem vismazāk nesen izmantoto ierakstu. Izdevīgs, ja pēdējā piekļuve prognozē nākamo.
  • FIFO (First In, First Out) — izņem visilgāk turēto ierakstu. Vienkāršs, bet ne vienmēr optimāls.
  • LFU (Least Frequently Used) — izņem vismazāk bieži izmantoto ierakstu; noderīgi, ja vēlamība ir ilgtermiņa populāriem elementiem.
  • Random — izlases izvēle; vienkārši un reizēm pietiekami laba liela mēroga sistēmām.
  • CLOCK — efektīva aptuvena LRU īstenošana, populāra operētājsistēmu lapu menedžmentā.
  • ARC/Adaptive — adaptīvi algoritmi, kas kombinē LRU un LFU priekšrocības, piemēram, Redo/Adaptive Replacement Cache.

Pierakstīšanas politikas (write policies)

Bieži jāizlemj, kā rīkoties, ja tiek mainīti dati:

  • Write-through — rakstot kešā, izmaiņas tūlīt tiek ierakstītas arī galvenajā atmiņā. Nodrošina konsekvenci, bet palielina aizkavēšanos.
  • Write-back (Write-behind) — izmaiņas vispirms saglabājas kešā, galvenajā atmiņā tiek atjauninātas vēlāk (kad ieraksts tiek izņemts). Samazina rakstīšanas skaitu, bet sarežģī datu integritāti un prasa sinhronizāciju.
  • Write-around — rakstot dati tiek rakstīti tieši galvenajā avotā, apejot kešu; noderīgi lieliem, reti lasītiem ierakstiem, tomēr var pasliktināt lasīšanas veiktspēju.
  • Write-allocate / No-write-allocate — nosaka, vai pēc rakstīšanas tiek arī ielādēts ieraksts kešā (write-allocate) vai nē (no-write-allocate).

Kešatmiņu veidi un piemēri

  • CPU kešatmiņas — L1, L2, L3 keši procesoros, kas saglabā instrukcijas un datus, lai samazinātu piekļuves laiku atmiņai.
  • Operētājsistēmas lapu keši un failu keši — diska I/O samazināšanai.
  • Datubāzu starpkārtas (in-memory) keši — Redis, Memcached, ko izmanto, lai ātri atdotu bieži pieprasītus datus.
  • Tīmekļa kešēšana — pārlūkprogrammu keši, CDN (satiksmes satura nodrošināšana), starpniekserveru keši, lai samazinātu atbildes laiku un slodzi uz serveriem.
  • DNS kešēšana — ierakstu saglabāšana ar TTL, lai samazinātu DNS vaicājumu skaitu.

Kešēšana daudzprocesoru/izklātās sistēmās

Daudzprocesoru sistēmās un izklātās platformās parādās papildu problēmas — keškoherences un datu saskaņotība starp vairākiem kešiem. Pastāv protokoli (piem., MESI), kas nodrošina, ka izmaiņas vienā kešā tiek izplatītas vai bloķētas, lai izvairītos no neatbilstībām. Lielos tīmekļa lietojumos tiek izmantotas stratēģijas, lai izvairītos no konfliktējošiem rakstiem, piemēram, shardēšana, reģistru invalidācija vai laika zīmju (versioning) lietošana.

Veiktspējas rādītāji un dizaina kompromisi

Kešēšanas dizainā jāņem vērā vairāki faktori:

  • Kešatmiņas izmērs — lielāks izmērs var uzlabot hit rate, bet palielina izmaksas un meklēšanas laiku (atkarībā no organizācijas).
  • Bloka izmērs — lielāki bloki var uzlabot telpisko lokalitāti, bet radīt nelietderīgu datu pārsūtīšanu.
  • Asociativitāte — palielināta asociativitāte samazina konfliktiem pamatoto miss skaitu, bet palielina sarežģītību un izmaksas.
  • Prefetching — prognozējot nākamos pieprasījumus, sistēma var iepriekš ielādēt datus kešā; tas var uzlabot sniegumu, bet riskē ar lieku trafiku.
  • Kešēšanas "sasilšana" (cache warming) — ja kešs tiek zaudēts (restart), pirmie pieprasījumi būs lēni, līdz kešs "uzsilst".

Datu derīguma un konsekvences jautājumi

Kešēšana var radīt problēmas ar datu svaigumu. Izplatītas pieejas to risināšanai:

  • TTL (time-to-live) — ierobežo, cik ilgi ieraksts tiek uzskatīts par derīgu.
  • Invalidācija — atjaunināšanas laikā tiek noņemtas vai atjauninātas saistītās keškopijas.
  • Versiju numuri un keš-busting — pievieno versijas identifikatorus kešrajām, lai izvairītos no vecu datu izsniegšanas.

Drošība un privātums

Kešēšana var izraisīt datu drošības riskus, īpaši, ja kešā glabā sensitīvu informāciju. Rekomendācijas:

  • Nekešēt sensitīvus personu datus bez šifrēšanas vai atbilstošas piekļuves kontroles.
  • Izvairīties no kešēšanas privātā satura pārlūkprogrammu vai CDN līmenī.
  • Rūpēties par kešainfiltrācijas un kešapoliju drošību, lai novērstu kešatmiņu "poisoning".

Labas prakses un ieteikumi

  • Mēriet pirms optimizējat: analizējiet hit rate, latentci, trafiku un izmaksas, lai izvēlētos pareizo risinājumu.
  • Izvēlieties piemērotu aizvietošanas politiku atkarībā no lietojuma rakstura (piem., LRU bieži der web kešiem, LFU — populārām ilgtermiņa ierakstu kopām).
  • Uzstādiet saprātīgas TTL un invalidācijas stratēģijas, lai sabalansētu veiktspēju un datu svaigumu.
  • Optimizējiet kešatmiņas atslēgas (key normalization, namespaces, versioning) — izvairieties no dubultu atslēgu radīšanas.
  • Automatizējiet monitoringu un brīdināšanu par hit rate kritumiem, kešapopulācijas izmaiņām vai pārmērīgu miss penalty.
  • Izmantojiet CDN un pārlūkprogrammu kešus statiskajam saturam, lai samazinātu serveru slodzi un uzlabotu lietotāja pieredzi.

Kopsavilkums

Kešēšana ir spēcīgs paņēmiens, kas samazina vidējo piekļuves laiku un samazina slodzi uz lēnākām sistēmām, izmantojot īslaicīgas datu kopijas ātrā atmiņā. Tomēr efektīva kešēšana prasa rūpīgu dizainu: pareizu izmēru, aizvietošanas algoritmu, pierakstīšanas politiku, invalidācijas mehānismus un drošības pasākumus. Pareizi pielietota kešēšana var būtiski uzlabot lietojumprogrammu veiktspēju un lietotāja pieredzi; nepareizi — radīt novecojušus datus, drošības riskus vai nevajadzīgas izmaksas.