Към съдържанието
wannacode

Кеш

Накратко: Кешът пази копие на често четени данни по-близо до кода; при cache-aside програмата първо гледа в кеша, а при промяна копието трябва да се изтрие, иначе показва стари данни.

Проблем

Страницата, която пита базата за едно и също

Магазинът пуска кампания за кафе. Страницата на продукта пита базата около 40 пъти: продукта, цената, наличността, отзивите, свързаните продукти. Ако страницата се отваря по 2 000 пъти в минута (пример, не измерване), това са 80 000 заявки в минута. А отговорите са едни и същи, защото цената на кафето не се мени всяка секунда.

Базата е на 100% процесор, страницата се зарежда за 4 секунди, а купувачите си тръгват. Ето същото в малко, с база, която брои заявките си:

function productPage(products, id) {
  const p = products.find(id);
  return `${p.name}: ${p.price.toFixed(2)} €`;
}
const db = new Database(catalog);
const popular = [7, 9, 12];
for (let i = 0; i < 1000; i++) {
  productPage(db, popular[i % 3]);
}
console.log(`отваряния: 1000, заявки към базата: ${db.queries}`);
Изход
отваряния: 1000, заявки към базата: 1000

Хиляда отваряния на три продукта: хиляда заявки за три различни отговора.

Идеята

Копие пред базата

Ако отговорът не се мени често, пази го. Програмата първо гледа в кеша. Ако там има копие, връща го (попадение). Ако няма (пропуск), пита базата, слага копие в кеша и връща отговора. Копието има срок, TTL: след него кешът го забравя и следващото четене пак отива до базата.

Командите на Redis за това, TTL и DEL видя в урока за key-value базите. Тук въпросът е друг: къде в кода живее кешът, така че останалият код да не знае за него.

Отговорът е обвивка около хранилището. CachedRepository има същия интерфейс като базата (Repository) и обвива базата като Decorator. Услугата и страницата получават хранилище и не знаят дали то е кеш. Решава кодът, който сглобява обектите.

Това се казва cache-aside: кешът стои встрани от базата, а кодът сам го пълни при пропуск.

Виж го

Кешът в код

Продуктът, хранилището и базата, която брои заявките си:

// product: { id, name, price }
// базата: брои заявките си, за да ги видим
class Database {
  queries = 0;


  constructor(products) {
    this.rows = new Map(products.map((p) => [p.id, p]));
  }


  find(id) {
    this.queries++;
    return this.rows.get(id);
  }


  save(product) {
    this.queries++;
    this.rows.set(product.id, product);
  }
}
В JavaScript няма интерфейси: Database и CachedRepository просто имат еднакви методи find и save. В TypeScript ще ги опишеш с interface.

Времето е брояч на тикове. Така изтичането на TTL е едно и също при всяко пускане:

// времето е брояч на тикове, не часовник
class Clock {
  now = 0;
}

Кешът: първо копието, при пропуск базата, а save пише в базата и трие копието.

class CachedRepository {
  cache = new Map();
  hits = 0;
  misses = 0;


  constructor(db, clock, ttl) {
    this.db = db;
    this.clock = clock;
    this.ttl = ttl;
  }


  find(id) {
    const entry = this.cache.get(id);
    if (entry && this.clock.now < entry.expires) {
      this.hits++;
      return entry.product; // копие, не истината
    }
    this.misses++;
    const product = this.db.find(id);
    const expires = this.clock.now + this.ttl;
    this.cache.set(id, { product, expires });
    return product;
  }


  save(product) {
    this.db.save(product);
    this.cache.delete(product.id); // трие копието
  }
}

Хилядата отваряния, но през кеша, с TTL 100 тика:

const clock = new Clock();
const db = new Database(catalog);
const products = new CachedRepository(db, clock, 100);
const popular = [7, 9, 12];
for (let i = 0; i < 1000; i++) {
  clock.now = i; // всяко отваряне е един тик
  productPage(products, popular[i % 3]);
}
console.log(`заявки към базата: ${db.queries}`);
console.log(`попадения: ${products.hits}, пропуски: ${products.misses}`);
Изход
заявки към базата: 30
попадения: 970, пропуски: 30

Тридесет заявки вместо хиляда. Всеки от трите продукта се чете веднъж на 100 тика, а останалите 970 отваряния отговаря копието.

Пробвай

Предвиди изхода

Базата и часовникът са като в програмата горе, TTL е 100 тика и часовникът стои на 0. Какво ще отпечата?

const products = new CachedRepository(db, clock, 100);
products.find(7);
products.find(7);
products.find(9);
products.save({ id: 7, name: "кафе", price: 12.90 });
products.find(7);
products.find(7);
console.log(products.hits, products.misses, db.queries);
Отговор

Идеята

Старата цена

Кафето поевтинява от 14,90 € на 12,90 €. Нощният импорт на цените пише направо в базата, покрай CachedRepository:

const clock = new Clock();
const db = new Database(catalog);
const products = new CachedRepository(db, clock, 5);
console.log(`тик 0: ${productPage(products, 7)}`);
// нощният импорт на цените пише направо в базата
db.save({ id: 7, name: "кафе", price: 12.90 });
for (let t = 1; t <= 6; t++) {
  clock.now = t;
  console.log(`тик ${t}: ${productPage(products, 7)}`);
}
Изход
тик 0: кафе: 14.90 €
тик 1: кафе: 14.90 €
тик 2: кафе: 14.90 €
тик 3: кафе: 14.90 €
тик 4: кафе: 14.90 €
тик 5: кафе: 12.90 €
тик 6: кафе: 12.90 €

Базата казва 12,90 €, а страницата показва 14,90 € до тик 5. Кешът е копие, не истината. Никой не му е казал, че истината се е сменила, затова той отговаря със старото, докато TTL не изтече. В истински магазин TTL е минути, а купувачът вижда една цена на страницата и друга в количката.

Затова всеки, който променя данните, трие и копието. Това се казва инвалидиране (cache invalidation). Същата промяна, но през save:

const clock = new Clock();
const db = new Database(catalog);
const products = new CachedRepository(db, clock, 5);
console.log(`тик 0: ${productPage(products, 7)}`);
// същата промяна, но през save
products.save({ id: 7, name: "кафе", price: 12.90 });
clock.now = 1;
console.log(`тик 1: ${productPage(products, 7)}`);
console.log(`заявки към базата: ${db.queries}`);
Изход
тик 0: кафе: 14.90 €
тик 1: кафе: 12.90 €
заявки към базата: 3

Новата цена се вижда веднага. Трите заявки са четенето на тик 0, записът и новото четене след изтритото копие.

TTL остава като предпазна мрежа: ако някой път се пише покрай кеша, лъжата живее най-много един TTL.

Виж го

Копието, старата цена и инвалидирането

find(id) {
  const entry = this.cache.get(id);
  if (entry && this.clock.now < entry.expires) {
    this.hits++;
    return entry.product; // копие, не истината
  }
  this.misses++;
  const product = this.db.find(id);
  const expires = this.clock.now + this.ttl;
  this.cache.set(id, { product, expires });
  return product;
}


save(product) {
  this.db.save(product);
  this.cache.delete(product.id); // трие копието
}
Стъпка по стъпка, с думи
  1. Тик 0: страницата иска кафето (продукт 7). В кеша няма копие: пропуск.
  2. При пропуск кешът пита базата. Това е единствената заявка досега.
  3. Кешът пази копие до тик 5 (TTL от 5 тика), а страницата показва 14.90 €.
  4. Тик 1: попадение. Отговаря копието, а базата не чува нищо.
  5. Импортът на цените пише 12.90 € направо в базата. На тик 2 копието още казва 14.90 €: старата цена.
  6. Никой не е казал на кеша. Старото копие живее, докато TTL изтече на тик 5.
  7. Поправката: промяната минава през save. Той пише в базата и веднага трие копието.
  8. Следващото отваряне не намира копие, пита базата и взима 12.90 €.
  9. Кешът е копие. Истината е в базата, а който я променя, трие копието.

save не пише новата цена в кеша, а само трие копието. Следващото четене взима истината от базата. Защо това е по-безопасно, е в теста накрая.

Пробвай

Попълни

Кой метод трие копието, когато цената се смени?

save(product) {
  this.db.save(product);
  this.cache.(product.id);
}

Идеята

Кога кешът вреди

Кешът е бърз, защото лъже малко. Ето кога лъжата струва повече от скоростта:

  • Стойности, които трябва да са точни. Цената и наличността при плащането се четат от базата, а не от кеша. Иначе продаваш последната бройка два пъти или таксуваш по старата цена.
  • Промяна покрай кеша. Импорт, друга програма или ръчен UPDATE в базата не трият копието. Колкото повече пътища пишат, толкова по-лесно някой забравя.
  • Състезание между четене и запис. Четене при пропуск взима 14,90 € от базата. Преди да сложи копието, save пише 12,90 € и трие (още празния) ключ. После четенето слага своето 14,90 € и то живее цял TTL. Това е race condition между две заявки. Затова TTL никога не е безкраен.
  • Всичко изтича наведнъж. Ако хиляди копия изтекат в един момент или кешът се рестартира празен, всички заявки отиват до базата наведнъж. Срокът се разпръсква с малко случайност, а най-четеното се зарежда предварително.
  • Всеки сървър със свой кеш. Кеш в паметта на процеса е бърз, но при три копия на сървъра (в урока за мащабирането) всяко копие има своя стара цена. Затова общият кеш е отделен (Redis).
  • Кеш, който не е измерен. Кешът добавя код, памет и грешки. Слагаш го, когато брояч или измерване покажат, че базата е тясното място, а не за всеки случай.

Пробвай

Намери грешката

Колега кешира цялата готова страница на продукта. Тестовете минават. На следващия ден английските купувачи виждат страницата на български. На кой ред е грешката?

Избери реда с грешката.

По-точно, за любопитните

Други начини за кеш. При read-through кешът сам пита базата при пропуск (кодът говори само с кеша). При write-through записът минава през кеша и той пише в базата. При write-behind кешът пише в базата по-късно, на партиди: бързо е, но при срив губиш записи. Cache-aside е най-честият, защото кешът може да падне, без да спре магазина: тогава всичко отива до базата.

Инвалидиране със събитие. Ако цената се сменя в една услуга, а се кешира в друга, тя не може да трие чужд ключ. Тогава промяната пуска събитие „цената на 7 се смени“ и всеки, който кешира, трие своето копие. Това е урокът за събитията.

Истинските кешове: Redis и Valkey (общ кеш за всички сървъри), Memcached. В процеса: Caffeine в Java, IMemoryCache и HybridCache в ASP.NET Core, functools.lru_cache в Python (без TTL), пакетът lru-cache в Node. Рамките имат и обвивка като тук: @Cacheable и @CacheEvict в Spring, кешът на Django.

Кеш по пътя на заявката. Браузърът и CDN-ът също кешират отговори по заглавката Cache-Control. Настройката на CDN и proxy е инфраструктура и се учи в DevOps курса ZeroToOps.

Фил Карлтън казва, че в програмирането има две трудни неща: инвалидирането на кеша и имената. Сега знаеш защо първото е в списъка.

Упражнение

Цената за доставка

Реши задачата в редактора си.

Количката пита външния доставчик колко струва доставката до града на купувача. Доставчикът отговаря бавно и брои заявките. Цените: София 4,90 €, Пловдив 5,90 €, Варна 6,90 €. Напиши CachedQuotes: пази цената за всеки град 10 тика и пита доставчика само при пропуск. Пусни заявките на тикове 0, 1, 2, 5, 11, 12 и 13 за градовете София, Пловдив, София, София, София, Пловдив и Варна.

Изход
тик 0, София: 4.90 €
тик 1, Пловдив: 5.90 €
тик 2, София: 4.90 €
тик 5, София: 4.90 €
тик 11, София: 4.90 €
тик 12, Пловдив: 5.90 €
тик 13, Варна: 6.90 €
заявки към доставчика: 5

Пет заявки вместо седем. София на тик 11 е пропуск: копието от тик 0 е живяло до тик 10.

Още задачи

  • Брой попаденията. Добави брояч на попаденията и пропуските и ги отпечатай накрая.
  • Доставчикът сменя цената. Добави метод, с който доставчикът казва „цената за Варна се смени“, и изтрий само нейното копие.

Тест

Провери се

1. Какво прави cache-aside при пропуск?
2. Импортът на цените пише направо в базата. Защо страницата показва старата цена?
3. Защо save трие копието, вместо да запише новата цена в кеша?
4. Кое от тези НЕ бива да се чете от кеша?
5. Кешът на страниците е с ключ „page:7“, а страницата се рисува на български или на английски. Какво става?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·