Кеширане е термин, използван в компютърните науки. Идеята на кеша (произнася се "кеш" /ˈkæʃ/ KASH ) е много проста: Много често получаването на резултат от дадено изчисление отнема много време, така че съхраняването на резултата обикновено е добра идея. Използват се два вида носители за съхранение: Единият обикновено е доста голям, но достъпът до него е "бавен"; другият може да бъде достъпен много по-бързо, но обикновено е малък. Най-основната идея зад кеширането е да се използва носителят, който е бърз за достъп, за да има копия на данните. Няма разлика между копието и оригинала. Достъпът до оригиналните данни може да отнеме много време или да е скъп (например: резултатите от трудна задача, чието решаване отнема много време). По тази причина е много "по-евтино" просто да се използва копието на данните от кеша. Казано по друг начин, кешът е временна област за съхранение, в която има копия на данни, които се използват често. Когато копие на данните се намира в този кеш, по-бързо е да се използва това копие, отколкото да се изтеглят или преизчислят оригиналните данни. Така средното време, необходимо за достъп до данните, става по-кратко. Поставянето на нова стойност в кеша често означава, че трябва да се замени по-стара стойност. Съществуват различни идеи (обикновено наричани "стратегии") за това как да се избере стойността, която да се замени.

Буферът е много подобен на кеша. Той се различава по това, че клиентът, който получава достъп до данните в буфера, знае, че има буфер; буферът се управлява от приложението. При кеша клиентът, който получава достъп до данните, не трябва да знае, че има кеш.

Типичните компютърни приложения имат достъп до данни по много сходни начини. Да предположим, че данните са структурирани в "блокове", до които може да се получи индивидуален достъп. Когато дадено приложение осъществява достъп до блок, много вероятно е да осъществи достъп (или препратка) и до блок, който е "близък" до оригиналния блок. Това е известно като локалност на референцията. Съществуват различни видове такава "локалност". Локалността на препратките е една от причините, поради които кешовете работят добре в много области на изчислителната техника.

За да работят добре, кешовете са малки в сравнение с цялото количество данни. Колкото по-голям е кешът, толкова по-дълго време отнема търсенето на даден запис. Изграждането на по-големи кешове е и по-скъпо.

Какво представлява попадение (hit) и пропуск (miss)

  • Hit (попадение) — когато исканият блок е наличен в кеша и може да бъде върнат незабавно.
  • Miss (пропуск) — когато исканият блок отсъства от кеша и трябва да бъде зареден от по-бавен носител или преизчислен.

Ключови метрики: процент на попадения, време за достъп при попадение, време за пропуск (miss penalty) и средно време за достъп (AMAT)

Типове кешове и примери

  • Процесорни кешове — L1, L2, L3; L1 е най-бърз, но най-малък.
  • Операционна система — страничен кеш на страници (page cache).
  • Уеб кеширане — браузърен кеш, прокси кеш, CDN (съдържателни дистрибуционни мрежи).
  • Кешове в бази данни — buffer pool, мемкеш, Redis.

Структура на кеша и асоциативност

Кешът често е структуриран в блокове (линии). Търсенето включва сравняване на tag и проверка на valid бит.

  • Direct-mapped — всеки блок от паметта има точно едно място в кеша (просто и бързо, но може да води до много конфликти).
  • Set-associative — кешът е разделен на множества (sets); всеки set съдържа няколко линии (асоциативност k). Баланс между скорост и намаляване на конфликтите.
  • Fully-associative — всеки блок може да заеме която и да е линия (подходящо за малки кешове или TLB).

По-голямата асоциативност намалява конфликти, но увеличава сложността и времето за търсене/сравняване на тагове.

Видове кешови пропуски

  • Cold (compulsory) misses — първо изискване за даден блок, който никога не е бил в кеша.
  • Capacity misses — кешът е твърде малък, за да побере работният набор от данни.
  • Conflict misses — при асоциативност недостатъчна за разпределението на адресите (особено директно картографиране).

Стратегии за замяна (replacement)

Когато кешът е пълен, трябва да се избере линия за изхвърляне. Популярни политики:

  • LRU (Least Recently Used) — изтрива се най-рядко използваният елемент. Предимства: добра емпирична ефективност; Недостатъци: скъпа за реализация при висока асоциативност (има оптимизации и приближени LRU).
  • FIFO (First-In, First-Out) — премахва се най-старият в кеша блок. Лесен за имплементация, но може да изхвърли често използвани елементи.
  • LFU (Least Frequently Used) — премахва се блокът с най-малка честота на достъп. Подходящ за случаи с постоянни "горещи" набори, но може да задържи остарели популярни елементи.
  • Random — избира се произволен блок за замяна. Проста и понякога близка по резултат до по-сложните политики, особено при висока конкуренция.
  • ARC, LIRS и други адаптивни алгоритми — комбинират честота и рецентност, адаптират се към работното натоварване; осигуряват добра производителност в гибки сценарии.

Политики за запис (write policies)

  • Write-through — всяка промяна се записва и в кеша, и в главната памет. По-сигурно и по-просто за гарантиране на консистентност, но по-бавно по отношение на латентността и увеличен трафик към бавния носител.
  • Write-back (write-behind) — промяната се записва само в кеша, а в главната памет се записва по-късно (при изваждане на линията). По-бързо и намалява трафика, но изисква управление на "dirty" битове и сложни схеми при грешки/съвпадения.
  • Write-allocate срещу no-write-allocate — при пропуск дали да се зарежда блокът и после да се записва (allocate) или директно да се запише в главната памет без кеширане.

Практически съображения и оптимизации

  • Използване на prefetching (предзаявяване) за зареждане на данни в кеша преди те да бъдат поискани, базирано на модели на достъп.
  • Паралелни и pipelined достъпи, които минимизират латентността при кешови пропуски.
  • Високото ниво на локалност (времева и пространствена локалност) подобрява ефективността на кеша:
    • Времева локалност — ако даден елемент е използван наскоро, вероятно ще бъде използван отново.
    • Пространствена локалност — ако е използван елемент, вероятно ще бъдат използвани и съседните елементи.
  • Баланс между размер, асоциативност и време за търсене. По-големите кешове намаляват честотата на пропуски, но увеличават времето за тагови сравнения и цената.
  • За разпределени системи — управление на консистентност между множество кешове (coherence, invalidation), например при многопроцесорни системи или CDN.

Кога кеширането не помага

  • Когато достъпите са напълно случайни и работният набор е много по-голям от кеша (висока честота на capacity misses).
  • Ако данните се променят постоянно и честото записване обезсмисля кеширането (особено при write-through без write-allocate).
  • Когато кешът не е правилно проектиран спрямо модела на достъп (напр. директно картографиране при конфликтни последователности).

Заключение

Кеширането е фундаментална техника за подобряване на производителността при системи със значителна разлика в скоростта между различни нива на съхранение. Правилният избор на размер, асоциативност, стратегия за замяна и политика за запис зависи от естеството на натоварването и от хардуерните/софтуерните ограничения. В практиката се използват комбинирани и адаптивни решения, които да балансират скоростта, сложността и цената.