Caching

A cache keeps a copy of frequently used data somewhere faster than its original source, usually in memory, so most requests never reach the database. It is often the cheapest large performance gain available. But a cache is a second copy of the data, and two copies can disagree. This topic covers how caching is done, and above all what to do so the cache and the database stay consistent, and what to do when they do not.

Why cache

• Speed. Reading from memory takes microseconds; a database query often takes milliseconds.
• Database relief. Most applications read far more than they write. If 90% of reads are served from the cache, the database handles a tenth of the read load.
• Cost. Memory for hot data is far cheaper than a bigger database.

Where caches live

From the user outwards: the browser, a CDN close to the user, memory inside each application server, and a shared cache such as Redis or Memcached that all application servers use. This topic focuses on the shared cache in front of a database, where consistency problems are most common.

The standard pattern: cache-aside

In cache-aside (also called look-aside), the application manages the cache itself:

• Read: look in the cache. On a hit, return it. On a miss, query the database, store the result in the cache, and return it.
• Write: update the database first, then delete the cached copy. The next read misses and fetches the fresh value.

Why delete instead of writing the new value into the cache? Because a delete is safe to repeat and cannot install a wrong value; if two writers race to update the cache, the slower one could overwrite the newer value with an older one. Facebook's memcache paper gives the same reason: "We choose to delete cached data instead of updating it because deletes are idempotent."

Other patterns

• Read-through: the cache itself loads missing data from the database; the application only talks to the cache.
• Write-through: every write goes to the cache and the database together. Reads are always fresh, but every write pays for both.
• Write-behind (write-back): writes go to the cache and are saved to the database later, in batches. Very fast, but data not yet saved is lost if the cache fails, so it suits only data that can be recreated.

Cache hits and misses

A hit is a request answered from the cache; a miss has to go to the database. The hit ratio, hits divided by all requests, is the main health number of any cache: at 95%, the database sees only 5 of every 100 reads. Misses happen for different reasons, and each has a different fix:

• Cold misses. The data was never cached, for example right after a deploy or restart. Fix: accept them, or warm the cache by loading the most popular keys before taking traffic.
• Capacity misses. The data was cached but evicted to make room. Fix: a bigger cache, or a better eviction policy (below).
• Expiry misses. The TTL ran out. Fix: a longer TTL where staleness allows it (see Leases and Time to Live), plus the measures in "Handling misses after expiry and eviction" below.
• Invalidation misses. The data was deleted because it changed. These are intended: they are how the cache stays correct.

Watch the hit ratio alongside database load. A sudden drop usually means a deploy flushed the cache, the cache is too small, or a new access pattern is scanning keys that are never reused.

Eviction policies: what to remove when the cache is full

Memory is limited, so a full cache must choose which entry to remove for each new one. That choice is the eviction policy:

• LRU (least recently used): remove the entry unused for the longest time. Simple and good for most workloads, because recently used data tends to be used again.
• LFU (least frequently used): remove the entry used the fewest times. Better when some items are steadily popular, but slow to forget items that were popular once.
• FIFO (first in, first out): remove the oldest entry, regardless of use. Simple, usually worse than LRU.
• Random: remove any entry. Surprisingly reasonable, and cheap.
• Shortest remaining TTL: remove the entry closest to expiring anyway.

In the example, accessing A again moves it to the front, so when D arrives the least recently used item is B, and B is evicted.

Real caches refine these ideas. Redis chooses its policy with the maxmemory-policy setting, including allkeys-lru, allkeys-lfu, allkeys-random, volatile-ttl and noeviction (refuse new writes instead). Its LRU is deliberately approximate: it "samples a small number of keys at random and then evicts the ones with the longest time since last access", and, as the docs explain, "The reason Redis does not use a true LRU implementation is because it costs more memory." Caffeine, the most widely used Java cache library, uses a policy called Window TinyLFU, which combines recency and frequency for a higher hit ratio than plain LRU.

Handling misses after expiry and eviction

A miss caused by expiry or eviction is normal: the next reader fetches the value from the database and puts it back. It becomes a problem only when many readers miss at the same moment, because they all go to the database together. These measures keep that from happening:

• Set a TTL that matches how the data changes. Data that changes rarely can live for hours; data that changes often needs minutes or seconds. The Amazon Builders' Library warns against "the situation where a developer arbitrarily picks some cache size and TTL values" without looking at the data.
• Add jitter to the TTL. If a thousand keys are cached at the same moment with the same TTL, they all expire at the same moment too. Instead of a flat 60 minutes, use 60 minutes plus a random 0 to 5 minutes. Huawei Cloud's Redis guidance says to "add or subtract a random offset from a base expiry time, to prevent a large number of keys from expiring at the same time."
• Let one request refill. When a popular key expires, only the first request goes to the database; the others wait a moment for it, or are given the old value. Amazon calls this request coalescing: the cache ensures "that only one pending request is out for uncached resources." A lock per key does the same within one server, and Facebook's leases do it across a whole cluster (see Leases and Time to Live).

• Serve stale while refreshing. Keep the old value a little past its TTL and return it while one background request fetches the new one. Users never wait for the database. HTTP has a name for this, stale-while-revalidate: RFC 5861 describes it as returning "a stale response while it revalidates it in the background, thereby hiding latency." Amazon describes the same idea as a soft TTL (time to refresh) and a hard TTL (time after which the old value may no longer be used).
• Refresh ahead of expiry. For a few known hot keys, refresh them shortly before they expire, so a reader never sees a miss at all. A published variant, Optimal Probabilistic Cache Stampede Prevention (VLDB 2015), has each reader decide at random to refresh early, with the chance rising as expiry gets closer, so no locks are needed.
• Warm the cache after a deploy or restart by loading the most popular keys before taking traffic, so a new server does not start with an empty cache.
• Size the cache for its working set. If eviction misses are frequent, the cache is too small for the data that is in active use. Give it more memory or cache fewer, more valuable things.

Cache penetration, breakdown and avalanche

Three failure modes have names in the caching world (the terms are widely used in Redis guides, including Huawei Cloud's). All three end the same way: the database takes load that the cache was supposed to absorb.

Cache penetration

Cache-aside only stores values that exist. If someone asks for a key that is not in the database, such as a product id that was never created, the database answers "not found", there is nothing to cache, and the next request for the same key misses again. Each request goes straight through the cache to the database, which is why it is called penetration.

By accident this is rare. On purpose it is an easy attack: a script that requests /item/<random id> thousands of times per second makes the cache useless and puts the whole load on the database, even though every response is a cheap 404.

The defences, usually combined:

1. Cache the "not found" answer too (negative caching). Store a marker meaning "does not exist" with a short TTL, such as 30 to 60 seconds, so repeated requests for the same missing key are answered from the cache. Amazon recommends "a negative cache with a distinct TTL." Keep the TTL short, and delete the marker when the item is created, otherwise a newly created item looks missing until the marker expires. Negative caching alone does not stop an attacker who never repeats a key, because every random key is a new miss.
2. A Bloom filter of every real key, checked before the cache. It answers "definitely not" for almost every random key, so those requests never reach the cache or the database. This handles the never-repeating attacker that negative caching misses. How it works is explained in Bloom Filters.
3. Validate the input. If ids are UUIDs, reject anything that is not a valid UUID before any lookup. If slugs are lowercase words and hyphens, reject anything else.
4. Rate-limit per client. A real user does not open thousands of non-existent pages per minute. A limit per IP address caps how much any single source can generate (see Rate Limiting). Huawei Cloud's guidance for penetration is along these lines: "Limit the rate of access to the database."

Cache breakdown

A single very popular key expires, and the thousands of requests arriving in the next instant all miss and all query the database for the same value. The fixes are the ones above: let one request refill (a lock or lease), serve stale while refreshing, or refresh hot keys before they expire. Huawei Cloud also suggests keeping hot data in a local in-process cache that is refreshed in the background.

Cache avalanche

Many keys expire at the same time, usually because they were all loaded together (by a deploy, a warm-up script or a restart) with the same TTL. Or the cache server itself goes down, and every request becomes a miss. The fixes: TTL jitter so expiries spread out, warming gradually instead of all at once, a small local cache in front of the shared one, and a highly available cache so one failed node does not empty it.

How the cache and the database drift apart

Even with cache-aside, the two copies can disagree. The common causes:

• A failed delete. The database update succeeds, then the application crashes or the network fails before the cache delete. The cache keeps the old value.
• A race between a reader and a writer, called a stale set:

A reader misses and reads x = 1 from the database. Before it stores that in the cache, a writer updates the database to x = 2 and deletes the cached key. Then the reader stores its old x = 1. The cache now holds stale data, and nothing will remove it.

• Replica lag. If cache misses are filled from a database replica that is a moment behind, the cache can be filled with an old value.
• Writes that bypass the application, such as a manual fix run directly in the database, which nothing knows to invalidate.

Keeping them consistent

No single technique covers everything, so production systems layer them:

1. Delete on write, after the database commit. Never update the cache before the database transaction has committed.
2. Always set a TTL. A time to live means any stale value disappears after a known time, however it got there. This is the safety net under everything else (see Leases and Time to Live).
3. Use leases or version checks on fills. A fill is accepted only if no delete happened since the miss, which removes the stale-set race. Leases are explained in the next topic.
4. Invalidate from the database's commit log. Instead of trusting every application server to send deletes, a separate process reads the database's log of committed changes and issues the deletes. A crashed application can no longer skip one.

5. Retry failed deletes. If a delete fails, queue it and try again rather than ignoring the error.

When they are inconsistent anyway

Treat the database as the source of truth and the cache as disposable:

• Repair by deleting. If a cached value is wrong, delete the key. The next read refills it from the database. Never "fix" the cache by writing a guessed value into it.
• Detect drift. Compare a small random sample of cached values with the database in the background, and track the mismatch rate as a metric. A rising rate points to a missing invalidation path.
• Bypass the cache for critical reads. Where a stale answer is unacceptable (a payment status, a balance before a transfer), read from the database's primary.
• Read your own writes. After a user changes something, serve that user's next reads from the database for a short time, so they never see their own change disappear.
• Flush with care. Clearing the whole cache fixes everything at once but sends every request to the database. Do it only for a small cache or in low traffic, ideally in stages.

A real system: Facebook's memcache

Facebook's paper Scaling Memcache at Facebook (NSDI 2013) describes a cache layer that "handles billions of requests per second and holds trillions of items". It uses cache-aside exactly as above: the web server updates the database, then "sends a delete request to memcache that invalidates any stale data".

It also uses commit-log invalidation. Database statements "are amended to include memcache keys that need to be invalidated once the transaction commits", and a daemon called McSqueal reads the database's commit log and sends the deletes to every cache cluster. Its leases, covered in the next topic, solve the stale-set race shown above.

Implementing it in your project

Java: the LinkedHashMap LRU, and why it is not used in production

Java's standard library can build an LRU cache in a few lines. The LinkedHashMap documentation states that a map created in access order "is well-suited to building LRU caches", and that overriding removeEldestEntry lets it delete the oldest entry once it is too big:

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxEntries;

    LruCache(int maxEntries) {
        super(16, 0.75f, true); // true = access order: get() moves an entry to the end
        this.maxEntries = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxEntries; // called after each put; true evicts the least recently used
    }
}

This is a good way to understand LRU, and fine for a single-threaded program. It is not safe in a web server, where many threads read the cache at once. The documentation says plainly: "Note that this implementation is not synchronized." Worse, in access order, "merely querying the map with get is a structural modification": every read reorders the internal list. Two threads calling get at the same moment can corrupt the map's internal links, losing entries or returning wrong results, and such bugs only appear under load, which makes them very hard to find.

The documented workaround is wrapping it with Collections.synchronizedMap(...), but then every read and write waits for one lock, which becomes a bottleneck under load. So in production Java code, use a cache library instead:

Cache<String, Product> products = Caffeine.newBuilder()
        .maximumSize(10_000)                       // size-based eviction (Window TinyLFU)
        .expireAfterWrite(Duration.ofMinutes(10))  // TTL as a safety net
        .build();

Caffeine is built for concurrent access and evicts with Window TinyLFU, which usually keeps a better hit ratio than plain LRU.

Spring Boot: annotate reads and writes

In Spring, @Cacheable caches a method's result and @CacheEvict deletes it when data changes, which is cache-aside without writing the cache code yourself. Systema itself works this way: Learn topics, tags and the architecture catalog are cached in Redis with @Cacheable, every admin write that changes them carries a matching @CacheEvict, and each cache has a TTL as a backstop in case an eviction is ever missed. Two rules from its configuration are worth copying: never cache a result that depends on who is asking, and never cache a method that performs its own permission check, because a cache hit skips the check.

Redis: set a memory limit and a policy

maxmemory 512mb
maxmemory-policy allkeys-lru

Without a limit, Redis grows until the machine runs out of memory. With allkeys-lru (or allkeys-lfu), it evicts automatically. Always give cached keys a TTL as well, for example SET product:42 "..." EX 600.

Python

functools.lru_cache(maxsize=...) caches a function's results in memory with LRU eviction, which is ideal for expensive pure functions inside one process. Its documentation notes that it is thread-safe, but that the wrapped function may run more than once if two threads ask for the same uncached value at the same moment. For data shared by several server processes, use Redis instead.

How to use this in an interview

When you add a cache, say which pattern (usually cache-aside), what the TTL is, and how the cache is invalidated on writes. Then name one inconsistency risk, such as the stale-set race, and how you would contain it. That shows you treat the cache as a second copy of the data, not as free speed.

---

Sources and credibility

Everything above is written from scratch; the quotes come from the source below, attributed where used.

Primary (highest confidence)

• Scaling Memcache at Facebook, Nishtala et al., USENIX NSDI 2013. Source of the scale figures, the delete-instead-of-update reasoning, the write path and the commit-log invalidation (McSqueal).

• LinkedHashMap, Java 21 API documentation. Source of the LRU suitability, removeEldestEntry and the two thread-safety quotes.

• Eviction and Efficiency, Caffeine wiki. Source of maximumSize and the Window TinyLFU policy.

• Key eviction, Redis documentation. Source of maxmemory, the eviction policies and the approximate LRU quotes.

• functools, Python documentation. Source of the lru_cache behaviour.

• Caching challenges and strategies, Amazon Builders' Library (Jas Chhabra). Source of negative caching, request coalescing, soft and hard TTLs, and the TTL-sizing quote.

• RFC 5861: HTTP Cache-Control Extensions for Stale Content, M. Nottingham, 2010. Source of the stale-while-revalidate quote. It is an Informational RFC, not an IETF standard, but the directive is widely supported.

• Optimal Probabilistic Cache Stampede Prevention, Vattani, Chierichetti and Lowenstein, PVLDB 8(8), 2015. Source of probabilistic early refresh.

Secondary

• Suggestions on Using DCS, Huawei Cloud Distributed Cache Service best practices. Source of the TTL random-offset quote, the penetration rate-limiting quote, and the local-cache advice for breakdown. The page uses the terms penetration and breakdown; "avalanche" for mass expiry is common usage in Redis guides but does not appear there.

Method

• The caching patterns, miss types, eviction policies and consistency techniques are standard practice; the descriptions and the repair checklist are our own. The Spring example describes Systema's own cache configuration.

On copyright: the diagrams on this page were drawn for this article, and the explanations are original. Quoted phrases are short and attributed.