Кеширане (cache-aside, TTL) в Java

Проблем

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

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

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

static String productPage(ProductRepository products, int id) {
    Product p = products.find(id);
    return p.name() + ": " + String.format("%.2f €", p.price());
}

Database db = new Database(CATALOG);
int[] popular = {7, 9, 12};
for (int i = 0; i < 1000; i++) {
    productPage(db, popular[i % 3]);
}
System.out.println("отваряния: 1000, заявки към базата: " + db.queries);

отваряния: 1000, заявки към базата: 1000

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

Идеята

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

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

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

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

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

Виж го

Кешът в код

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

record Product(int id, String name, double price) {}

interface ProductRepository {
    Product find(int id);
    void save(Product product);
}

// базата: брои заявките си, за да ги видим
class Database implements ProductRepository {
    private final Map<Integer, Product> rows = new HashMap<>();
    int queries = 0;

    Database(List<Product> products) {
        for (Product p : products) rows.put(p.id(), p);
    }

    public Product find(int id) {
        queries++;
        return rows.get(id);
    }

    public void save(Product product) {
        queries++;
        rows.put(product.id(), product);
    }
}

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

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

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

record Entry(Product product, int expires) {}

class CachedRepository implements ProductRepository {
    private final ProductRepository db;
    private final Clock clock;
    private final int ttl;
    private final Map<Integer, Entry> cache = new HashMap<>();
    int hits = 0;
    int misses = 0;

    CachedRepository(ProductRepository db, Clock clock, int ttl) {
        this.db = db;
        this.clock = clock;
        this.ttl = ttl;
    }

    public Product find(int id) {
        Entry entry = cache.get(id);
        if (entry != null && clock.now < entry.expires()) {
            hits++;
            return entry.product(); // копие, не истината
        }
        misses++;
        Product product = db.find(id);
        int expires = clock.now + ttl;
        cache.put(id, new Entry(product, expires));
        return product;
    }

    public void save(Product product) {
        db.save(product);
        cache.remove(product.id()); // трие копието
    }
}

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

Clock clock = new Clock();
Database db = new Database(CATALOG);
CachedRepository products = new CachedRepository(db, clock, 100);
int[] popular = {7, 9, 12};
for (int i = 0; i < 1000; i++) {
    clock.now = i; // всяко отваряне е един тик
    productPage(products, popular[i % 3]);
}
System.out.println("заявки към базата: " + db.queries);
System.out.println("попадения: " + products.hits + ", пропуски: " + products.misses);

заявки към базата: 30
попадения: 970, пропуски: 30

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

Пробвай

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

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

CachedRepository products = new CachedRepository(db, clock, 100);
products.find(7);
products.find(7);
products.find(9);
products.save(new Product(7, "кафе", 12.90));
products.find(7);
products.find(7);
System.out.println(products.hits + " " + products.misses + " " + db.queries);

Отговор

2 3 4

3 2 3

2 3 3

Идеята

Старата цена

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

Clock clock = new Clock();
Database db = new Database(CATALOG);
CachedRepository products = new CachedRepository(db, clock, 5);
System.out.println("тик 0: " + productPage(products, 7));
// нощният импорт на цените пише направо в базата
db.save(new Product(7, "кафе", 12.90));
for (int t = 1; t <= 6; t++) {
    clock.now = t;
    System.out.println("тик " + 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:

Clock clock = new Clock();
Database db = new Database(CATALOG);
CachedRepository products = new CachedRepository(db, clock, 5);
System.out.println("тик 0: " + productPage(products, 7));
// същата промяна, но през save
products.save(new Product(7, "кафе", 12.90));
clock.now = 1;
System.out.println("тик 1: " + productPage(products, 7));
System.out.println("заявки към базата: " + db.queries);

тик 0: кафе: 14.90 €
тик 1: кафе: 12.90 €
заявки към базата: 3

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

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

Виж го

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

public Product find(int id) {
    Entry entry = cache.get(id);
    if (entry != null && clock.now < entry.expires()) {
        hits++;
        return entry.product(); // копие, не истината
    }
    misses++;
    Product product = db.find(id);
    int expires = clock.now + ttl;
    cache.put(id, new Entry(product, expires));
    return product;
}

public void save(Product product) {
    db.save(product);
    cache.remove(product.id()); // трие копието
}

Стъпка по стъпка, с думи

Тик 0: страницата иска кафето (продукт 7). В кеша няма копие: пропуск.
При пропуск кешът пита базата. Това е единствената заявка досега.
Кешът пази копие до тик 5 (TTL от 5 тика), а страницата показва 14.90 €.
Тик 1: попадение. Отговаря копието, а базата не чува нищо.
Импортът на цените пише 12.90 € направо в базата. На тик 2 копието още казва 14.90 €: старата цена.
Никой не е казал на кеша. Старото копие живее, докато TTL изтече на тик 5.
Поправката: промяната минава през save. Той пише в базата и веднага трие копието.
Следващото отваряне не намира копие, пита базата и взима 12.90 €.
Кешът е копие. Истината е в базата, а който я променя, трие копието.

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

Пробвай

Попълни

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

public void save(Product product) {
    db.save(product);
    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. Импортът на цените пише направо в базата. Защо страницата показва старата цена?Базата още не е записала новата ценаНикой не е изтрил копието в кеша, затова то отговаря, докато не изтече TTLБраузърът пази старата страница

3. Защо save трие копието, вместо да запише новата цена в кеша?Кешът не може да записва стойностиСледващото четене взима истината от базата. Ако два записа или неуспешен запис се разминат с кеша, той пак не лъже дългоТриенето е по-бързо от записа

4. Кое от тези НЕ бива да се чете от кеша?Списъкът с най-продаваните за началната страницаОписанието на продукта на страницата муЦената и наличността в момента на плащането

5. Кешът на страниците е с ключ „page:7“, а страницата се рисува на български или на английски. Какво става?Кешът пази две копия под един ключКойто отвори продукта пръв, решава езика за всички до изтичането на копиетоВсеки получава страницата на своя език

Кеш

Бисквитки