Caching

Think of a tea shop. A customer asks for a cup of tea. The cook can make it from scratch each time: boil water, add leaves, wait, strain. Or the cook can keep a big flask of tea ready on the counter and pour from it.

The flask is a cache. It is a small, quick place where you keep an answer you already worked out, so you do not have to work it out again.

That is the whole idea. Everything else in this note is about the details: where the flask sits, when you refill it, what happens when it goes cold, and what happens when a hundred people ask for tea at the same moment.

Why caches exist

Two reasons, and they are different.

The first is speed. Some things are slow to get. A database query that joins three tables might take 50 milliseconds. A call to another service across the network might take 100. Reading from the memory of a nearby machine takes about 1 millisecond or less. If you can answer from memory, the user waits less.

The second is protection. Your database can only do so many queries a second. If the same popular data is asked for 10,000 times a second, the database does the same work 10,000 times. A cache answers most of those, and the database sees only a trickle. Often this is the real reason you add a cache. Speed is nice, but "my database was on fire" is what actually gets one added.

The trade is that a cache might hold something old. The data changed in the database, and the cache still has the previous version. Every decision in caching comes back to this: you buy speed and lower load, and you pay with the risk of stale data and some extra complexity.

Two words you will hear a lot:

• A cache hit means the answer was in the cache. Good.
• A cache miss means it was not, so you had to go to the slower place, usually the database.

Where a cache can sit

There is not one cache. There is a chain of them, from the user's phone to your database. Each one saves a trip to the next.

From closest to the user to furthest away:

The browser cache. The user's own browser keeps copies of images, scripts and sometimes API answers. A request that never leaves the phone is the fastest request there is. You control it with headers on the response that say how long a copy may be reused.

The CDN. A CDN (content delivery network) is a set of servers spread around the world that hold copies of your files. A user in Mumbai gets the image from a server in Mumbai instead of one in Virginia. This is the right place for images, videos, scripts and any page that is the same for everyone.

Memory inside the app server. The server keeps a small map in its own memory, such as a list of countries or the settings of a feature. It is the fastest cache you can run yourself because there is no network trip at all. The catch is that each server has its own copy, and the copies can disagree. If you have 10 servers, you have 10 separate caches.

A shared cache such as Redis. Redis is a program that keeps data in memory and answers very quickly. All your app servers talk to the same one, so they all see the same data. This is what people usually mean when they say "add a cache" in an interview. It sits between the app and the database.

The database's own cache. Databases keep recently used data in memory too. You get that for free, and it is why a repeated query is often faster the second time. You do not manage it, but it is good to know it exists.

When someone says "cache" with no more detail, they mean Redis or something like it. In an interview, say which level you mean. "I would put images behind a CDN, and cache the user profile lookups in Redis."

The four ways to use a cache

Now the part that interviewers love. When your app reads or writes data, who talks to the cache and who talks to the database? There are four common patterns.

Each one has a cost.

Cache aside is the one I would reach for first. It is simple and you can see everything the code does. The cost is that the app has to write the cache logic, and the first request for any item is slow (the cache starts empty). Also, if the cache is down, the app still works, just slower, because the app can go straight to the database.

Read through moves that logic into the cache layer, so the app code is shorter. The cost is that you need a cache that supports it, and the cache now has to know how to load your data.

Write through keeps the cache and the database in step, because every write goes to both. The cost is that writes are slower (you wait for two places), and you may fill the cache with data nobody reads again.

Write back is the fast and risky one. Writes are quick because only memory is touched. But if the cache machine dies before it saves to the database, those writes are gone. Use it only when losing a little is acceptable, like counting page views. Never for an order or a payment.

In practice, many systems use cache aside for reads and a plain database write that then removes the cache entry. If someone asks "which would you use", cache aside is a safe answer as long as you can say why.

Cache aside, step by step

The first request pays the full price. Every request after that, until the entry expires, is fast. TTL here means "time to live", how long the entry may stay before it is thrown away. More on that below.

Here is the same thing in code, kept as small as possible.

def get_user(user_id):
    key = f"user:{user_id}"
    data = cache.get(key)
    if data is not None:
        return data

    data = db.read_user(user_id)
    cache.set(key, data, ttl_seconds=60)
    return data


def update_user(user_id, new_data):
    db.write_user(user_id, new_data)
    cache.delete(f"user:{user_id}")

Look at the update. We write the database first, and then delete the cache entry instead of updating it. The next read will miss and fill it with fresh data. Deleting is safer than updating, because there is less that can go out of order.

Eviction: what to throw away when the cache is full

A cache is small on purpose. Memory costs more than disk. So sooner or later it fills up, and to add something new you must remove something old. The rule for choosing is called an eviction policy.

LRU, least recently used. Throw away the item nobody has touched for the longest time. The thought is "if you have not used it lately, you probably will not use it soon". This is the most common choice and a good default.

LFU, least frequently used. Throw away the item that was used the fewest times overall. The thought is "keep the popular things". It handles a long term favourite well, but a newly popular item can get kicked out because it has not built up a count yet.

TTL, time to live. Not really a choice of who to remove, but a rule on top: every entry gets an expiry time, and when it passes, the entry is dropped. TTL is how you limit how stale a value can be. A 60 second TTL means the data is at most about a minute old.

Most real setups use TTL and LRU together. The TTL puts an upper limit on staleness, and LRU decides what goes when memory runs out.

Others exist (first in first out, random). You rarely need them in an interview. If you can explain LRU and LFU, you are covered.

A tiny LRU by hand

Say the cache can hold only 3 items. Think of a stack of cards. The card on top is the one used most recently. The card at the bottom is the one to throw away.

We ask for these keys in order: A, B, C, A, D, A, B.

I write the stack with the most recent on the left.

Look at step 5. B is evicted, not A. A was used again at step 4, so it moved up. That is what makes it LRU.

Two hits out of seven requests. About 29 percent. That is a poor hit ratio, and the reason is plain: the cache holds 3 items while we keep asking for 4 different ones. A bigger cache or less varied requests would raise it. Hit ratio is mostly a question of how big the cache is compared to how much data people actually ask for.

If you were asked to build it, the usual answer is a hash map plus a doubly linked list. The map finds an item in one step. The list keeps the order of use, so moving an item to the front and removing the last are both quick.

Invalidation: the hard part

There is a joke that the two hard problems in computer science are naming things and cache invalidation. It is a joke, but it points at something real.

Invalidation means getting rid of a cached value when the real data changes. The cache cannot know the database changed unless you tell it. If you forget, users see old data.

You have three simple tools.

1. Expire it with a TTL. Lowest effort. You accept that data may be old for up to the TTL. For a product description, 5 minutes is fine. For a stock count at checkout, it is not.
2. Delete it when you write. When the app updates the database, it also deletes the cache key. The next read refills it. Fresher, but you have to remember to do it everywhere data changes. One missed code path and you have a stale bug that only shows up sometimes.
3. Put a version in the key. Instead of product:42, use product:42:v7. When the product changes, bump the version, so new reads use a new key. Old entries just fade out through TTL. This is common for files and pages.

Why is it hard? Because of timing. Here is a real trap, with two users, Reader and Writer, and one item whose value is 1.

1. Reader asks the cache. It misses. Reader reads the database and gets 1.
2. Before Reader writes to the cache, Writer updates the database to 2.
3. Writer deletes the cache key. (There is nothing in it yet, so nothing happens.)
4. Reader now puts the value 1 into the cache.

The database says 2. The cache says 1. And it will say 1 until the TTL runs out. No code was wrong in the usual sense. The two steps simply happened in an unlucky order.

This is rare, but at high traffic rare things happen every day. What do you do about it? Two honest answers: always set a TTL so any stale value dies on its own, and accept that a short window of old data is part of the deal. If the data cannot be stale even for a moment, do not cache it, or read it straight from the database.

A good thing to say out loud: "I will use cache aside with a TTL, and delete the key on write. A short window of stale data is okay for this feature, and the TTL keeps it bounded."

Cache stampede

Say a very popular item is cached with a 60 second TTL. Thousands of users ask for it every second. At second 60 the entry expires.

At that exact moment, 5,000 requests arrive, see a miss, and all go to the database to fetch the same item. The database gets 5,000 identical queries in a blink. It slows down, the requests take longer, more pile up, and the database falls over. That pile up is called a cache stampede. The cache did its job for 59 seconds and then caused an outage in the 60th.

There are a few ways to stop it. You can combine them.

• Only let one request rebuild it. When a miss happens, one request takes a lock (a note saying "I am fetching this") and goes to the database. The others wait a moment or return the old value, then read the new one from the cache. This is sometimes called single flight.
• Add jitter to the TTL. If 10,000 keys were all loaded at the same time with a 60 second TTL, they all expire together. Use 60 plus a random 0 to 10 seconds, so expiries spread out.
• Refresh before it expires. A background job reloads a popular key a little before its TTL ends, so it never goes empty.
• Serve stale for a moment. Keep the old value for a few extra seconds after expiry and hand it out while one request fetches the new one. Users see slightly old data instead of a slow page.
• Warm the cache. If you restart a cache or deploy a new one, it begins empty and everything misses at once. Pre fill the popular keys first.

The first one, a lock per key, is the one I would explain in an interview. It is easy to say and easy to draw.

Hot keys

A hot key is one cache entry that gets a huge share of all the traffic. Think of a celebrity profile, a viral video or the home page config during a sale.

A cache like Redis spreads keys across many machines, but one key lives on one machine. So if one key gets 100,000 requests a second, that one machine is overloaded while the others sit idle. Adding more cache machines does not help, because the key still lives on only one of them.

What to do:

• Keep a tiny copy in each app server's memory for a few seconds. The app server answers from its own copy and rarely asks Redis. With 20 app servers, the cache machine sees at most a few requests a second for that key instead of 100,000.
• Store several copies under different names, like video:9:a, video:9:b, video:9:c, and have each request pick one at random. Now the traffic spreads across machines.
• Put it on a CDN, if the data is the same for everyone.

The price of all of these is that copies can go stale. For a hot key, that is nearly always an acceptable price. A viral video's view count being 3 seconds old hurts nobody.

What not to cache

Caching everything is a common beginner move. It is not free. Each cached item takes memory, needs invalidation, and might be wrong. So ask before adding.

Skip caching when:

• The data is rarely read. If something is read once a day, a cache just holds it for nothing.
• The data changes on nearly every request. It would be invalid before anyone reuses it.
• It must be exactly right every time. Account balances, stock left at checkout, seat availability. A small mistake costs real money.
• It is cheap to get anyway. If the database answers a primary key lookup in 1 millisecond, a cache adds complexity for tiny gain.
• It is private and could leak. Data that is different per user must have the user in the key. If you cache a page without that, one person might see another person's data. This one is a real security bug, not just a slow page.
• The object is huge and seldom reused. It will push out many smaller useful items.

The best things to cache are data that is read a lot, changes rarely, and is expensive to produce. Product pages, user profiles, configuration, the result of a slow calculation, the top 10 list.

Talking about hit ratio with numbers

Hit ratio is the share of requests the cache answers.

hit ratio = hits / (hits + misses)

In an interview, do not say "the cache will help a lot". Say a number, and show what it does.

Say you have 10,000 reads a second.

Look at how the database load changes. Going from 90 to 95 percent halves the load. It looks like a small step, but it is half the work. That is why people chase the last few percent of hit ratio.

The effect on speed. Say a hit takes 1 ms, and a miss takes 11 ms (1 ms for the failed lookup, then 10 ms for the database).

• At 90 percent: 0.9 x 1 + 0.1 x 11 = 0.9 + 1.1 = 2.0 ms on average.
• At 95 percent: 0.95 x 1 + 0.05 x 11 = 0.95 + 0.55 = 1.5 ms on average.

Where does a good hit ratio come from? Mainly from the shape of the traffic. If a small part of the data gets most of the requests, then a small cache can reach 90 percent or more. If every request is for something different, no cache will help. This is why you ask, during your estimate, whether the traffic is uneven. A rough rule used often is that 20 percent of the items get 80 percent of the traffic. Sizing a cache for that 20 percent is a sensible start.

Do not forget to say how you would watch it. "I would track the hit ratio, and if it drops, I would look at the cache size, the TTL and the eviction rate." A cache you do not measure is a cache you cannot trust.

Putting it together in an answer

Say you are designing a service where reads are about 100 times the writes. A natural thing to say:

"Reads are 10,000 a second at peak, and the same items get requested again and again, so I will add Redis in front of the database using cache aside. Entries get a TTL of 5 minutes plus some random jitter, so they do not all expire together. When we update an item, we write the database and delete the key. I expect about a 90 percent hit ratio, so the database sees about 1,000 reads a second, which one machine can handle. For a very popular item I would also keep a copy in app memory for a few seconds to protect the cache from a hot key. The cost is that a user may see data a few minutes old, which is fine for this feature."

Short, with numbers, a reason for each choice and one tradeoff stated. That is the shape you are after.

Interview questions to check yourself

"Name two reasons to add a cache. Speed, because memory is faster than a database or a remote call. And protection, because a cache absorbs repeated reads so the database does not get overloaded."

"In cache aside, what happens on a miss?"

The app reads the database, puts the result in the cache with a TTL, and returns it. The next request for the same key is a hit.

"A cache holds 3 items and the order of use is A, B, C, A, D. Which item is evicted when D arrives, using LRU?"

B. After A, B, C, the request for A moves A up, so B is now the least recently used.

"What is a cache stampede and how would you stop it?"

A popular key expires and thousands of requests all miss and hit the database together. Let only one request rebuild it using a lock, add random jitter to TTLs, or refresh the key before it expires.

"Your hit ratio goes from 90 to 95 percent at 10,000 reads a second. What happens to the database?"

Database reads drop from 1,000 to 500 per second. Half the load, from what looks like a small improvement.