Skip to content
wannacode

Caching

In short: A cache keeps a copy of frequently read data closer to the code; with cache-aside the program looks in the cache first, and when the data changes the copy must be removed or it shows stale data.

Problem

The page that asks the database the same thing

The shop runs a coffee campaign. The product page asks the database about 40 times: the product, the price, the stock, the reviews, the related products. If the page is opened 2,000 times a minute (an example, not a measurement), that is 80,000 queries a minute. And the answers are the same, because the price of coffee does not change every second.

The database is at 100% CPU, the page takes 4 seconds to load, and buyers leave. Here is the same thing in small, with a database that counts its queries:

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("opens: 1000, database queries: " + db.queries);
Output
opens: 1000, database queries: 1000

A thousand opens of three products: a thousand queries for three different answers.

The idea

A copy in front of the database

If the answer does not change often, keep it. The program looks in the cache first. If there is a copy, it returns it (a hit). If not (a miss), it asks the database, puts a copy in the cache and returns the answer. The copy has an expiry, the TTL: after it the cache forgets the copy, and the next read goes to the database again.

You saw the Redis commands for this, TTL and DEL, in the lesson on key-value databases. The question here is a different one: where in the code the cache lives, so that the rest of the code does not know about it.

The answer is a wrapper around the repository. CachedRepository has the same interface as the database (Repository) and wraps the database like a Decorator. The service and the page get a repository and do not know whether it is a cache. The code that assembles the objects decides.

This is called cache-aside: the cache stands to the side of the database, and the code fills it on a miss.

See it

The cache in code

The product, the repository and the database that counts its queries:

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


interface ProductRepository {
    Product find(int id);
    void save(Product product);
}
// the database: counts its queries so we can see them
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);
    }
}

Time is a tick counter. That way the TTL runs out the same way on every run:

// time is a tick counter, not a clock
class Clock {
    int now = 0;
}

The cache: the copy first, the database on a miss, and save writes to the database and drops the copy.

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(); // a copy, not the truth
        }
        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()); // drop the copy
    }
}

The thousand opens, but through the cache, with a TTL of 100 ticks:

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; // every open is one tick
    productPage(products, popular[i % 3]);
}
System.out.println("database queries: " + db.queries);
System.out.println("hits: " + products.hits + ", misses: " + products.misses);
Output
database queries: 30
hits: 970, misses: 30

Thirty queries instead of a thousand. Each of the three products is read once every 100 ticks, and the copy answers the other 970 opens.

Try it

Predict the output

The database and the clock are as in the program above, the TTL is 100 ticks and the clock stays at 0. What does it print?

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

The idea

The old price

Coffee goes down from €14.90 to €12.90. The nightly price import writes straight to the database, past CachedRepository:

Clock clock = new Clock();
Database db = new Database(CATALOG);
CachedRepository products = new CachedRepository(db, clock, 5);
System.out.println("tick 0: " + productPage(products, 7));
// the nightly price import writes straight to the database
db.save(new Product(7, "coffee", 12.90));
for (int t = 1; t <= 6; t++) {
    clock.now = t;
    System.out.println("tick " + t + ": " + productPage(products, 7));
}
Output
tick 0: coffee: €14.90
tick 1: coffee: €14.90
tick 2: coffee: €14.90
tick 3: coffee: €14.90
tick 4: coffee: €14.90
tick 5: coffee: €12.90
tick 6: coffee: €12.90

The database says €12.90, and the page shows €14.90 until tick 5. The cache is a copy, not the truth. Nobody told it that the truth changed, so it answers with the old value until the TTL runs out. In a real shop the TTL is minutes, and the buyer sees one price on the page and another in the cart.

That is why everyone who changes the data also drops the copy. This is called cache invalidation. The same change, but through save:

Clock clock = new Clock();
Database db = new Database(CATALOG);
CachedRepository products = new CachedRepository(db, clock, 5);
System.out.println("tick 0: " + productPage(products, 7));
// the same change, but through save
products.save(new Product(7, "coffee", 12.90));
clock.now = 1;
System.out.println("tick 1: " + productPage(products, 7));
System.out.println("database queries: " + db.queries);
Output
tick 0: coffee: €14.90
tick 1: coffee: €12.90
database queries: 3

The new price shows at once. The three queries are the read on tick 0, the write and the new read after the dropped copy.

The TTL stays as a safety net: if something ever writes past the cache, the lie lives one TTL at most.

See it

The copy, the old price and invalidation

public Product find(int id) {
    Entry entry = cache.get(id);
    if (entry != null && clock.now < entry.expires()) {
        hits++;
        return entry.product(); // a copy, not the truth
    }
    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()); // drop the copy
}
Step by step, in words
  1. Tick 0: the page asks for the coffee (product 7). The cache has no copy: a miss.
  2. On a miss the cache asks the database. That is the only query in this story so far.
  3. The cache keeps a copy until tick 5 (TTL of 5 ticks), and the page shows €14.90.
  4. Tick 1: a hit. The copy answers and the database hears nothing.
  5. The price import writes €12.90 straight to the database. On tick 2 the copy still says €14.90: the old price.
  6. Nobody told the cache. The stale copy lives until its TTL runs out on tick 5.
  7. The fix: the change goes through save. It writes to the database and drops the copy at once.
  8. The next open finds no copy, asks the database and gets €12.90.
  9. The cache is a copy. The truth is in the database, and whoever changes the truth drops the copy.

save does not write the new price into the cache, it only drops the copy. The next read takes the truth from the database. Why that is safer is in the test at the end.

Try it

Fill in

Which method drops the copy when the price changes?

public void save(Product product) {
    db.save(product);
    cache.(product.id());
}

The idea

When a cache hurts

A cache is fast because it lies a little. Here is when the lie costs more than the speed:

  • Values that must be exact. The price and the stock at payment are read from the database, not from the cache. Otherwise you sell the last item twice or charge the old price.
  • Changes past the cache. An import, another program or a manual UPDATE in the database do not drop the copy. The more paths write, the easier it is for one of them to forget.
  • A race between a read and a write. A read on a miss takes €14.90 from the database. Before it puts the copy, save writes €12.90 and drops the (still empty) key. Then the read puts its €14.90, and it lives a whole TTL. That is a race condition between two requests. This is why the TTL is never endless.
  • Everything expires at once. If thousands of copies expire at the same moment, or the cache restarts empty, all requests go to the database at once. The expiry is spread with a little randomness, and the most-read data is loaded in advance.
  • Every server with its own cache. A cache in the memory of the process is fast, but with three copies of the server (in the lesson on scaling) each copy has its own old price. That is why the shared cache is separate (Redis).
  • A cache nobody measured. A cache adds code, memory and bugs. You add it when a counter or a measurement shows that the database is the bottleneck, not just in case.

Try it

Find the bug

A colleague caches the whole finished product page. The tests pass. The next day English buyers see the page in Bulgarian. Which line has the bug?

Pick the line with the bug.

More precisely, if you are curious

Other ways to cache. With read-through the cache asks the database itself on a miss (the code talks only to the cache). With write-through the write goes through the cache and the cache writes to the database. With write-behind the cache writes to the database later, in batches: it is fast, but a crash loses writes. Cache-aside is the most common, because the cache can go down without stopping the shop: everything then goes to the database.

Invalidation with an event. If the price changes in one service and is cached in another, the first cannot drop a key it does not own. Then the change publishes an event "the price of 7 changed", and everyone who caches drops their copy. That is the lesson on events.

The real caches: Redis and Valkey (a shared cache for all servers), Memcached. Inside the process: Caffeine in Java, IMemoryCache and HybridCache in ASP.NET Core, functools.lru_cache in Python (no TTL), the lru-cache package in Node. Frameworks also have a wrapper like the one here: @Cacheable and @CacheEvict in Spring, the Django cache.

Caches along the way. The browser and the CDN also cache responses by the Cache-Control header. Setting up a CDN and proxies is infrastructure and is taught in the DevOps course ZeroToOps.

Phil Karlton said there are two hard things in programming: cache invalidation and naming things. Now you know why the first one is on the list.

Exercise

The delivery price

Solve it in your editor.

The cart asks an outside provider how much delivery to the buyer's city costs. The provider answers slowly and counts the calls. The prices: Sofia €4.90, Plovdiv €5.90, Varna €6.90. Write CachedQuotes: it keeps the price for each city for 10 ticks and asks the provider only on a miss. Run the requests on ticks 0, 1, 2, 5, 11, 12 and 13 for the cities Sofia, Plovdiv, Sofia, Sofia, Sofia, Plovdiv and Varna.

Output
tick 0, Sofia: €4.90
tick 1, Plovdiv: €5.90
tick 2, Sofia: €4.90
tick 5, Sofia: €4.90
tick 11, Sofia: €4.90
tick 12, Plovdiv: €5.90
tick 13, Varna: €6.90
calls to the provider: 5

Five calls instead of seven. Sofia on tick 11 is a miss: the copy from tick 0 lived until tick 10.

More tasks

  • Count the hits. Add a counter of hits and misses and print them at the end.
  • The provider changes a price. Add a method by which the provider says "the price for Varna changed", and drop only that copy.

Test

Check yourself

1. What does cache-aside do on a miss?
2. The price import writes straight to the database. Why does the page show the old price?
3. Why does save drop the copy instead of writing the new price into the cache?
4. Which of these must NOT be read from the cache?
5. The page cache uses the key "page:7", and the page is drawn in Bulgarian or in English. What happens?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·