Caching in System Design: Patterns, Invalidation, Eviction and Redis

In article 07, Pixly's feed needed about 35,000 metadata lookups per second at peak. Most of those lookups ask for the same few hundred thousand recent photos, over and over. Sending each one to the database is like walking to the library every time you want to re-read a page of a book on your desk.

A cache is the desk: a small, fast store that keeps copies of data you are likely to need again. It is the single most effective performance tool in system design, and also one of the easiest to get subtly wrong, because the moment you keep a copy, the copy can disagree with the original. This article teaches caching as a design decision: when it is worth it, which pattern to use, and how it fails.

• Why caches work, and the layers where caches live.
• Hits, misses and hit ratios, and what to cache and what not to.
• Cache-aside, read-through, write-through, write-back and write-around, compared.
• TTLs, invalidation strategies, and a race condition that serves stale data.
• Eviction policies such as LRU and LFU, with a runnable LRU example.
• Cache stampedes, hot keys and negative caching.
• Distributed caches, Redis and Memcached, and how caches fail.

Two facts make caches effective:

1. Memory is much faster than disks and networks. From article 03: a memory read is about 100 nanoseconds; a database query over the network takes milliseconds. A cache in memory answers hundreds or thousands of times faster than recomputing the answer.
2. Access is skewed. A small fraction of data receives most of the reads: today's photos, the trending product, the popular profile. Caching that fraction serves most traffic with little memory (the working set from article 07).

The cost is equally fundamental: a cache is a copy, and copies go stale. Every caching decision balances three things:

   faster reads  <---->  stale data  <---->  invalidation complexity

Caches appear at every layer of a system. A request may hit several before reaching the database.

Browser / app cache       HTTP caching headers; data the app keeps locally     |CDN edge cache            static files and cacheable responses near users (article 10)     |Reverse proxy cache       whole responses at your edge     |Application in-process    a small map in each server's memory (fastest, not shared)     |Distributed cache         Redis or Memcached, shared by all servers     |Database                  has its own buffer cache of hot pages in memory

Most backend designs use a distributed cache as the main tier, sometimes with a small in-process cache in front for the very hottest keys.

• A hit: the data is in the cache. Fast.
• A miss: it is not. You fetch from the source, and usually store it in the cache for next time.
• The hit ratio = hits / (hits + misses).

As article 07 showed, the database sees total reads x (1 - hit ratio). Going from 90% to 99% hits cuts database reads by ten times. Hit ratio is the number to watch.

Good candidates share three properties:

• Read often relative to how often they change (high read:write ratio).
• Expensive to produce: a multi-table join, a computed recommendation, a call to a slow service.
• Tolerant of some staleness: a few seconds or minutes of old data harms nobody.

Product pages, user profiles, photo metadata, configuration, rendered fragments and results of expensive queries are classic examples.

• Data that must always be exact, such as an account balance used to authorise a payment. Read it from the source of truth.
• Data that changes on almost every read: the hit ratio will be low and the cache only adds work.
• Sensitive data in shared caches. Microsoft's guidance on cache-aside warns that caching may be inappropriate for sensitive or security-related data, especially when several applications or users share the cache (Cache-Aside pattern). A key-naming mistake can show one user's data to another.

A key must include everything that changes the answer. If a product page differs by language and currency, the key is product:9:lang=hi:cur=INR, not product:9. Forgetting an input is how users end up seeing someone else's language, or someone else's data.

Prefixing keys with a version (v3:product:9) lets you invalidate everything of one kind at once when the format changes: deploy code that reads v4: keys, and the old ones simply expire.

The application manages the cache itself. This is the most common pattern and a good default.

Read:

1. Look in the cache.
2. On a hit, return it.
3. On a miss, read the database, put the result in the cache with an expiry, return it.

Write:

1. Write the change to the database.
2. Delete the cached entry (rather than updating it).

Microsoft's description of the pattern follows the same steps, and notes that the order matters: update the data store before removing the item from the cache, otherwise a reader can repopulate the cache with the old value in between (Cache-Aside pattern).

Why delete instead of update? Updating the cache on every write wastes work for data nobody reads, and two concurrent writers can leave the cache holding the older value if their cache updates arrive in the opposite order to their database writes. Deleting lets the next reader load the truth.

Pros: only data that is actually read gets cached; the cache can fail without breaking reads (they fall back to the database). Cons: the first read after a miss is slow; there is a window of staleness; the application code carries the logic.

The application talks only to the cache; on a miss, the cache itself loads from the database (through a loader you configure). The logic is the same as cache-aside, moved into a library or the cache product. It keeps application code cleaner, at the price of less control.

Every write goes to the cache and the database as one operation (the cache layer writes through to the database before acknowledging). Reads after a write see the new value immediately.

Pros: cache is always fresh for written keys; good for read-after-write. Cons: every write pays both latencies; data written but never read still fills the cache. Usually combined with read-through.

Writes go to the cache only, and the cache flushes them to the database later, often in batches.

Pros: very fast writes; batching reduces database load (useful for counters such as views and likes). Cons: if the cache loses data before flushing, writes are lost; the database lags behind. Use only for data you can afford to lose a little of, or with a durable cache.

Writes go to the database only; the cache is filled on later reads (this is what cache-aside does on writes). Good when written data is rarely read soon after.

Every cached entry needs a way to die. There are two ways, and you usually use both.

Each entry expires after a set time. Choose the TTL from the requirements: how stale may this data be?

Add jitter. If you warm 100,000 keys at the same moment with a TTL of exactly 1 hour, they all expire in the same second an hour later, and the database takes all the misses at once. Use a TTL of "1 hour plus or minus a random few minutes".

When data changes, delete (or update) the affected keys. The hard part is knowing which keys: one product change may affect its page, its listing in three categories, a search result and a "related products" block. Options:

• Delete the obvious keys in the write path, and let TTLs clean up the rest.
• Event-driven invalidation: the write publishes a change event; a consumer deletes affected keys. A variant reads the database's change log (change data capture, article 21) so no write path can forget.
• Versioned keys: store a version number per entity; cache keys include it; bumping the version makes old entries unreachable.

Even with "update the database, then delete the key", cache-aside has a classic race:

Time  Reader                               Writer 1    cache miss for photo:1 2    reads old caption from database 3                                         updates caption in database 4                                         deletes photo:1 from cache 5    writes OLD caption into cache      -> cache now holds stale data until the TTL expires

The reader was slow between steps 2 and 5, and its stale value landed after the delete. Mitigations:

• A TTL bounds how long the stale value lives. This is why cache-aside should always have one.
• Delete again after a short delay (a "double delete").
• Conditional set: only write to the cache if the key was not invalidated since the read began. Facebook's paper on scaling memcache describes "leases" for this purpose: the cache hands out a token on a miss, and a set is accepted only if the token is still valid, which also limits thundering herds (Scaling Memcache at Facebook).
• Version checks: store the row's version with the cached value and refuse to overwrite a newer version.

In interviews, mentioning this race and one mitigation is a clear sign of depth.

Memory is finite. When the cache is full, it must evict something to make room. Common policies:

Redis, for example, offers policies including noeviction, allkeys-lru, allkeys-lfu, allkeys-random, volatile-lru and volatile-ttl. Its documentation suggests allkeys-lru as a good default when you have no reason to prefer another, and explains that Redis approximates LRU by sampling keys rather than tracking exact order, because exact LRU costs more memory (Key eviction).

This Java program builds a tiny LRU cache (Java's LinkedHashMap can keep entries in access order and evict the eldest) and uses it with the cache-aside read and write rules. The "database" is a map, so the run is deterministic. As always, the language is incidental.

// File: CacheAsideDemo.javaimport java.util.LinkedHashMap;import java.util.Map;public class CacheAsideDemo {    // LinkedHashMap in access order: the eldest entry is the least recently used.    static class LruCache<K, V> extends LinkedHashMap<K, V> {        private final int capacity;        LruCache(int capacity) {            super(16, 0.75f, true);            this.capacity = capacity;        }        @Override        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {            return size() > capacity;        }    }    static final Map<String, String> database = new LinkedHashMap<>();    static final LruCache<String, String> cache = new LruCache<>(3);    static int hits = 0;    static int misses = 0;    static String read(String key) {        String value = cache.get(key);        if (value != null) {            hits++;            return value;        }        misses++;        value = database.get(key);          // the slow path        if (value != null) {            cache.put(key, value);          // fill the cache for next time        }        return value;    }    static void update(String key, String value) {        database.put(key, value);           // 1. write the source of truth        cache.remove(key);                  // 2. then invalidate the copy    }    public static void main(String[] args) {        for (int i = 1; i <= 5; i++) {            database.put("photo:" + i, "caption " + i);        }        String[] requests = {"photo:1", "photo:2", "photo:1", "photo:3", "photo:1", "photo:4", "photo:2", "photo:1"};        for (String key : requests) {            read(key);            System.out.println("read " + key + " -> cache " + cache.keySet());        }        update("photo:1", "new caption");        System.out.println("after update: " + read("photo:1"));        System.out.println("hits=" + hits + " misses=" + misses);    }}

read photo:1 -> cache [photo:1]read photo:2 -> cache [photo:1, photo:2]read photo:1 -> cache [photo:2, photo:1]read photo:3 -> cache [photo:2, photo:1, photo:3]read photo:1 -> cache [photo:2, photo:3, photo:1]read photo:4 -> cache [photo:3, photo:1, photo:4]read photo:2 -> cache [photo:1, photo:4, photo:2]read photo:1 -> cache [photo:4, photo:2, photo:1]after update: new captionhits=3 misses=6

Follow the list: each read moves the key to the end (most recent). When photo:4 arrives and the cache is full, the eldest (photo:2) is evicted. photo:1, read often, survives. After the update deletes photo:1, the next read misses and loads the new caption, which is exactly the cache-aside write rule at work.

A very popular key expires. In the next instant, thousands of requests miss at the same time, and all of them query the database for the same row. Suppose a key receives 50,000 requests per second and rebuilding it takes 200 ms: without protection, up to 50,000 x 0.2 = 10,000 identical database queries arrive before the first one refills the cache. The database slows down, rebuilding takes longer, more requests pile in, and the cache never recovers.

Mitigations:

• Request coalescing (single flight): on a miss, only one request rebuilds the value; others wait for it or are served the previous value. Within one server this is a lock per key; across servers, a short-lived lock in the cache itself.
• Serve stale while revalidating: keep the expired value briefly and return it while one background refresh fetches the new one.
• Early refresh: refresh popular keys a little before they expire, for example with a probability that rises as expiry approaches.
• TTL jitter, so keys do not expire together.
• Pre-warming caches before known events and after deployments.

The Amazon Builders' Library article on caching discusses these risks, including how a cache can hide how much load a service would face without it (Caching challenges and strategies).

Sometimes one key is so popular that the single cache node holding it is saturated: a celebrity's profile, a flash-sale product, the score of a final. Adding more cache nodes does not help, because the key lives on one of them.

Mitigations:

• A small in-process cache in each application server for the hottest keys, with a very short TTL (even one second removes most of the traffic).
• Key replication: store copies as product:9#1 to product:9#8 on different nodes and read a random copy.
• Read replicas of the cache node.

If many requests ask for something that does not exist (a deleted photo, a mistyped URL, or an attacker probing random ids), every one misses the cache and hits the database. Cache the "not found" result too, with a short TTL. Combine it with input validation and rate limiting so attackers cannot fill your cache with junk keys.

A distributed cache runs on its own servers and is shared by every application server. That is what stateless application tiers need: any server sees the same cached data.

When one node is not enough, the cache is partitioned (sharded) across nodes, each holding part of the keys, and replicated so that a node failure does not lose its share. Redis Cluster, for example, divides the key space into 16,384 hash slots spread across primary nodes, each with replicas (Redis cluster specification). Article 32 designs a distributed cache from scratch, including consistent hashing.

Redis's data structures make it useful well beyond caching (articles 31 and 35 use sorted sets and atomic counters). That flexibility is also a trap: if you use Redis as the only copy of important data, it is a database and must be treated like one, with persistence, replication and backups.

Managed versions exist on every major cloud (for example Amazon ElastiCache, Google Memorystore, Azure Managed Redis), but the concepts are the same whether you run it yourself or not.

In a Java service, cache-aside with Redis often looks like this. It is an illustration of the pattern; client libraries differ.

public Photo getPhoto(long photoId) {    String key = "v1:photo:" + photoId;    String cached = redis.get(key);    if (cached != null) {        return Photo.fromJson(cached);                 // hit    }    Photo photo = photoRepository.findById(photoId);    // miss: go to the database    if (photo != null) {        int ttlSeconds = 3600 + random.nextInt(300);    // one hour plus jitter        redis.setex(key, ttlSeconds, photo.toJson());    } else {        redis.setex(key, 60, "null");                    // short negative cache    }    return photo;}public void updateCaption(long photoId, String caption) {    photoRepository.updateCaption(photoId, caption);     // source of truth first    redis.del("v1:photo:" + photoId);                    // then invalidate}

A cache adds a second copy, so readers can see older data than the database holds. Decide per feature:

• Eventual consistency is fine for most cached data (profiles, product descriptions, counts).
• Read-your-own-writes for the person who made a change: after a user edits their caption, read their own data from the database (or write through) for a short time, so they never see the old caption.
• Strong consistency is required for decisions with consequences (stock at checkout, balance before payment). Use the cache to display, but decide using the source of truth.

Ask "what happens if the cache disappears?" for every design.

• Cache cluster down. Every read goes to the database. If the database was sized assuming a 95% hit ratio, it now sees twenty times its normal read load. Either size the database to survive this, or degrade gracefully (serve fewer features, rate-limit, show a simplified page) and protect it with circuit breakers (article 23).
• Cold cache after a restart or failover. The same stampede problem, briefly. Warm critical keys before taking traffic, or ramp traffic gradually.
• Cache node loss in a cluster. A share of keys misses until replicas take over or the keys are reloaded.
• Stale or wrong data. Bugs in invalidation or keys show old or wrong data. Keep TTLs on everything so mistakes heal themselves.

A cache can also improve availability: if the database is briefly down, serving slightly stale cached data may be better than serving errors, for content where that is acceptable.

• Keys must include the user or tenant for personal data, so one user's data is never served to another.
• Do not cache authorisation decisions longer than you can tolerate a revoked permission still working.
• Keep the cache on a private network with authentication; an exposed cache can leak data or be filled with poisoned entries.
• Be careful caching responses that vary by cookies or headers at a shared layer (article 10 covers CDN cache keys).

Sizing from article 07: about 14 GB for 7 days of metadata, more if feeds are precomputed, on a small replicated Redis cluster. If Redis fails, the database must handle about 35,000 lookups per second at peak; it cannot, so Pixly protects it with request coalescing and a degraded feed (recent photos from fewer followed users) until the cache is warm again.

• Caching before measuring whether reads are actually the bottleneck. Sometimes an index (article 13) is the right fix.
• No TTL "because we invalidate on write". One missed invalidation and the data is stale forever.
• Updating instead of deleting on writes, and racing writers.
• Keys that omit inputs (language, user, version).
• Treating the cache as the source of truth for data you cannot lose.
• Sizing the database as if the cache can never fail.
• All keys expiring at the same moment.

• Introduce the cache with a reason: "reads are 3,500 per second at peak and mostly repeat; a cache with a 95% hit ratio drops database reads to under 200 per second".
• Name the pattern (usually cache-aside), the TTL, and how writes invalidate.
• Say what may be stale and why that is acceptable.
• Mention one failure: stampede on a hot key, or the database's survival when the cache is down.

• Next: CDNs and Object Storage: Serving Files, Images and Video at Scale applies caching at the edge of the internet, for large files.
• Related: article 32 designs a distributed cache; article 23 covers protecting the database when caches fail; article 35 uses Redis for precomputed feeds.