Caching 101

A cache is a small, fast copy of data that is slow or expensive to fetch, kept close to the code that needs it so repeated reads skip the slow path. You add one to cut latency, keep read load off your database and save money. The design work is everything around the copy: how often it is used (the hit ratio), how stale it may get (the TTL), and what happens when it is empty or gone.

Picture it first: the kirana counter

A kirana shop keeps its few thousand products in a godown at the back; fetching one takes the owner two minutes. So beside the counter he keeps the few dozen things people ask for all day: milk, bread, eggs, noodles, biscuits. Most customers are served in ten seconds.

The counter is tiny, yet it handles most sales, because demand is lopsided. Still, milk goes off, so he checks dates. When bread gets dearer, the old price sticker is wrong until someone changes it. After a Diwali clean-up the counter is bare, every customer means a trip to the godown, and the queue spills onto the street. And if he hired fewer helpers because “the counter handles most of it”, a day without the counter is a very bad day.

Map it back: the counter is the cache, the godown the database. A sale from the counter is a hit, a walk to the back a miss, and the share served from the counter the hit ratio. The date check is a TTL, the old sticker stale data, the bare counter a cold start, and the thin staff a cache that became a hidden dependency.

What a cache is, and why you add one

A cache stores a copy of data whose real home is somewhere slower: a database, another service, an origin server, a disk. Crucially, it may lose that copy; Facebook’s memcache paper notes that memcache is not the authoritative source, so it may evict anything. That is what lets a cache be fast, small and simple.

You add one for three reasons:

• Latency. A read from local memory takes about 100 ns. A round trip to a remote cache in the same data centre takes a few hundred microseconds; Facebook measured a median of 333 µs (p95 1.1 ms) for memcache fetches. A database query that does real work takes milliseconds.
• Load shedding. Every hit is a query the database never sees. This is often the bigger win, because the database is the hardest tier to scale.
• Cost. RAM is cheaper than re-running a join, a ranking or a paid API call; fewer queries let the database serve the same data “with a smaller number of nodes” (Redis docs).

Caching pays off when reads repeat: Facebook notes its users consume an order of magnitude more content than they create, and popularity is skewed. If every request is unique, a cache only adds a hop. Skipping a cache the workload begs for is the no caching anti-pattern; caching is the first tool in scaling reads.

How a cached read works

The most common shape is the look-aside read, also called cache-aside or lazy loading. The application asks the cache first; on a miss it reads the source of truth and stores the result for the next reader. Facebook describes its memcache as a “demand-filled look-aside cache”.

Only data somebody asked for gets cached, so memory goes to what is used, and a lost entry is simply refilled by the next reader. The other wirings (read-through, write-through, write-behind, refresh-ahead) and the races between writes and refills are in caching strategies.

Hit ratio: the number that decides everything

The hit ratio, h, is the share of lookups the cache answers: hits ÷ (hits + misses). Redis reports the counters as keyspace_hits and keyspace_misses in INFO stats. Two formulas follow, and you should be able to do both in your head.

Effective latency. A hit costs one cache lookup; a miss costs the lookup plus the database read:

effective latency = T_cache + (1 − h) × T_db

Take a 0.5 ms cache and a 10 ms database:

• No cache: 10 ms per read.
• 80% hits: 0.5 + 0.2 × 10 = 2.5 ms.
• 90% hits: 0.5 + 0.1 × 10 = 1.5 ms.
• 99% hits: 0.5 + 0.01 × 10 = 0.6 ms.

Database load. The database only sees misses: DB reads/s = (1 − h) × reads/s. At 50,000 reads a second, 80% hits leave 10,000 reads/s for the database, 90% leaves 5,000, and 99% leaves 500. Going from 90% to 99% sounds like a small tweak, but it cuts database reads 10×, because the database feels the miss ratio: 10% versus 1%.

The average hides two humps

With a cache, latency has two humps: fast hits and slow misses. If more than 1% of reads miss, your p99 is a miss, about 10.5 ms here, however good the average looks. To promise a tail-latency target you need a hit ratio above that percentile or a faster miss path (see latency vs throughput vs bandwidth).

The hit ratio your database needs

Turn the load formula around and it becomes a requirement: h ≥ 1 − (database read capacity ÷ peak reads/s). Say a Flipkart-style sale pushes product pages to 200,000 reads/s and your database tier comfortably serves 10,000. You need h ≥ 1 − 10,000 ÷ 200,000 = 95%. The same arithmetic shows the stakes: an empty cache asks the database for 20× what it can serve.

Why requests miss

• Cold misses: the item was never loaded, or the cache restarted. Fix: warm it before traffic arrives.
• Capacity misses: the item was evicted for space. Fix: more memory or a smarter eviction policy.
• Expiry and invalidation misses: the TTL ran out or a write deleted the entry. Fix: longer TTLs plus invalidation on write.

The cache hierarchy: from browser to disk

A request can be answered by several caches on its way to the data, and each hides everything behind it.

Three points the drawing can’t show:

• You can’t purge a browser. RFC 9111 calls browser caches private and CDNs shared. Once a response sits on a phone, your only control was the max-age you sent, which is why static files get versioned names such as app.3f9c1.js. CDNs add s-maxage and purge APIs; see content delivery network.
• The database already caches. PostgreSQL’s shared_buffers defaults to 128 MB; its docs suggest about 25% of RAM and say more than 40% rarely helps, because PostgreSQL also leans on the OS page cache. It is the only always-consistent layer, sitting under the database’s own transactions, but a hit still runs the query.
• CPU caches sit inside every box: roughly 1–4 ns for L1 and L2 against about 100 ns for RAM, which is why compact data is fast.

Local or remote?

In-process caches (a hash map or LRU library in your app) are the fastest and need no extra fleet, which is why the Builders’ Library calls them the usual first step. But each server’s copy drifts, so two requests can see different values; database load grows with the fleet, since each server fills its own cache; and every deploy starts cold. A remote cache such as Redis or Memcached fixes all three, at the price of a network hop, another fleet and a new failure mode. Large systems often run both: a small in-process tier for the hottest keys in front of the shared cache (see distributed caching), which Redis supports by sending clients an invalidation message when a key they read changes.

What to cache, and what not to

A good candidate passes four tests:

1. It is reused, ideally across users. Unique-per-request results give a hit ratio near zero.
2. It is read far more often than it changes. The Redis docs advise against caching keys that change continuously or are rarely requested.
3. Some staleness is acceptable. If a wrong answer costs money or double-sells something scarce, read the source of truth.
4. It is expensive to produce and cheap to store: a join, a ranking, a rendered fragment, a slow partner API call.

Don’t skip the last row. The Builders’ Library caches error and “not found” responses with their own TTL, because a service that discards every error keeps hammering a dependency that is already struggling.

Why a small cache goes a long way

Popularity is almost never uniform: a few products, restaurants or videos get most of the traffic, and a long tail gets almost none. Web traffic is often modelled as Zipf-like, where the k-th most popular item is requested in proportion to 1/k^α. Breslau and colleagues fitted six web-proxy traces in 1999 and found α between 0.64 and 0.83; classic Zipf is α = 1.

A small calculation shows what that means for cache size: take a catalogue of 1 million items, draw requests independently from a Zipf distribution with α = 1.0 or α = 0.8, and give the cache exactly the most popular items.

• At α = 1.0, the top 1% of items draws 68% of requests, the top 10% draws 84%, and the top 20% draws 89%.
• At α = 0.8, the same cache sizes draw 36%, 61% and 71%. That last figure lines up with Breslau’s observation that 25–40% of documents drew 70% of accesses in their traces.

Two lessons follow. First, a cache holding a sliver of the data can absorb most reads; that is why caches work at all. Second, returns shrink fast. In the same α = 1.0 model, 80% hits needs the top 5.6% of items, 90% needs 24%, and 95% needs 49%: about 4× the memory from 80% to 90%, then 2× again for 95%. Breslau saw the same flattening in real traces, with hit ratio growing roughly with the log of cache size.

Real policies must guess which items are hot, so they fall short: a plain LRU simulation (100,000 items, 1.5 million Zipf requests, α = 1.0) reached about 74% hits with a 10% cache, against 81% for the ideal cache; better guessing is the job of eviction policies. The flip side of skew is the hot key that overloads the one node holding it.

Keys and TTLs

Designing keys

A cache key must capture everything the cached value depends on, and nothing else.

• Namespace and version first: product:v3:12345. Bumping the version lets you change the stored format without old and new code misreading each other’s entries mid-deploy; the Builders’ Library warns that code choking on an unexpected format turns entries into poison pills.
• Every input that changes the answer: locale, currency, device class, A/B bucket, permissions. Leave one out and you serve one user’s answer to another, at worst leaking personal data; the Builders’ Library also flags cache poisoning and timing side channels. HTTP has the same rule: the key is at least method and URL, plus any request headers named in Vary, and a private response must not be stored by a shared cache.
• Bounded and deterministic: normalise parameters, hash long query strings, and never put a timestamp or request id in a key, or every request misses.

A look-aside read with these rules, in Python-flavoured pseudocode:

import random

TTL_S = 300                 # five minutes
NOT_FOUND = b"\x00nf"       # sentinel for negative caching

def get_product(product_id):
    key = f"product:v3:{product_id}"            # namespace : format version : id
    cached = cache.get(key)
    if cached == NOT_FOUND:
        return None                             # cached "does not exist"
    if cached is not None:
        return decode(cached)                   # hit
    row = db.get_product(product_id)            # miss: ask the source of truth
    if row is None:
        cache.set(key, NOT_FOUND, ex=30)        # short TTL for negatives
        return None
    cache.set(key, encode(row), ex=TTL_S + random.randint(0, 60))  # jittered TTL
    return row

Choosing a TTL

A TTL (time to live) is how long an entry may be served before the cache throws it away. It is your upper bound on staleness when every other mechanism fails.

Pick the TTL from three questions:

• How stale can a reader tolerate? A live score: a few seconds. A menu: minutes. A display name: an hour.
• How often does the data change? AWS suggests hours or days for keys you also invalidate on write, and a few seconds for fast-changing data such as leaderboards. A 5-second TTL around a hammered query is its suggested stopgap: the database then runs that query about once per key every five seconds.
• What does a miss cost? If the query is expensive, keep entries longer and invalidate explicitly.

Three habits make TTLs safer:

• Always set one. AWS advises a TTL on every lazily loaded key, and Redis a maximum TTL on every locally cached key, so a missed invalidation heals itself.
• Add jitter. Keys loaded together with one TTL expire together; AWS’s example adds up to two minutes of randomness to a one-hour TTL.
• Consider two TTLs. The Builders’ Library describes a soft TTL, after which a client tries to refresh, and a hard TTL, until which it may keep serving the old value if the source is down.

HTTP caches use the same idea: a response is fresh while its age is below the max-age (or s-maxage for shared caches). Send neither and a cache may guess; RFC 9111 cites 10% of the time since Last-Modified as a typical heuristic. Set it yourself.

Sizing a cache

Sizing is a short calculation, then measurement:

1. Estimate the working set: distinct items read within a TTL window × average entry size. 10 million products × 2 KB ≈ 20 GB. Sizes vary a lot (Facebook’s memcache responses had a median of 135 bytes and a mean of 954), so measure yours.
2. Decide the hit ratio you need from database capacity, as above: 95% in the sale example.
3. Read the popularity curve. With strong skew, a fraction of the working set suffices; if the working set is only tens of gigabytes, cache all of it.
4. Add headroom for per-key overhead, fragmentation, replicas and growth. Redis also needs free RAM for replication and persistence buffers, which don’t count towards maxmemory.
5. Measure and adjust. Watch hit ratio, evictions and memory; AWS reads steady evictions as a sign to scale up or out.

The Builders’ Library’s warning: don’t pick a size and TTL on day one and never revisit them. For the arithmetic, see back-of-envelope estimation.

Going deeper: what goes wrong

The Builders’ Library describes a familiar arc: a cache is added, latency and costs drop, the database is scaled down, and the service is now “addicted” to its cache. Most cache incidents start from one of these problems; each has a deeper article.

Stale data and invalidation

The cache and the database are two copies with no transaction spanning them, so every write must update or remove the cached copy, and order matters. Facebook writes to the database and then deletes the key rather than updating it, because deletes are idempotent. Even then, a slow reader can put an old value back after the delete. The fixes (leases, versioned values, invalidation driven by the database’s change log) live in caching strategies and hot keys, cache stampede and invalidation. Local caches and multiple regions multiply the copies to reach; the TTL stays the backstop.

Stampedes and hot keys

When a popular key expires, every request that misses at that moment goes to the database together: a stampede, thundering herd or dogpile. Facebook’s fix was leases: a memcached server hands out at most one lease token per key every 10 seconds, so one client refills the key while the others wait briefly and retry. For keys prone to herds, peak database queries fell from 17K/s to 1.3K/s. Request coalescing, serving stale while one caller refreshes, and jittered TTLs attack the same problem. Skew also concentrates load: Facebook notes a single key can take 20% of a server’s requests.

Cold starts

An empty cache sends everything to the database. Caches go cold on new clusters, restarts and deploys (for in-process caches), flushes, failover to an empty replica, and key-format changes.

Warm-up is slower than people expect. Facebook reports that a memcached server reaches 90% of its peak hit rate within a few hours, so upgrading a set of cache servers could take over 12 hours. Its Cold Cluster Warmup let a new cluster fill from a warm peer instead of the databases, reaching full capacity in hours rather than days. Simpler versions: replay real requests against a new node before it takes traffic (AWS), ramp traffic slowly (Google SRE), and stagger restarts of servers with in-process caches.

When the cache itself fails

The Google SRE book draws the line that matters. With a latency cache, the service carries its load even with the cache empty, just more slowly. With a capacity cache, it cannot, so losing the cache is an outage. Caches are often added as the first kind and quietly become the second; the sale example is a capacity cache.

Falling straight back to the database sounds safe, but the Builders’ Library warns that in a long cache outage the spike can brown the database out. Better options:

• Replicate the cache and fail over (see distributed caching).
• Keep a small in-process cache as a fallback for the hottest keys.
• Cap the fallback rate and shed the excess, returning errors or degraded pages instead of toppling the database.
• Serve stale data where acceptable, up to a hard TTL.
• Absorb failed nodes deliberately. Facebook sends requests for a failed memcached server to Gutter, a pool of about 1% of the cluster’s servers with short-lived entries, which cut client-visible failures by 99%. It avoided rehashing keys onto the surviving servers, where one hot key could overload a neighbour.
• Test it with load tests that run with the cache disabled.

Cheat sheet

How to say it in the interview

“I’d put Redis in front of the product database, cache-aside: read Redis; on a miss, read Postgres and write the row back with a five-minute TTL plus jitter; delete the key whenever the product changes. The number that matters is the hit ratio. At 200,000 reads a second in a sale, with a database good for 10,000, I need at least 95% hits, and then an average read is about 1 ms instead of 10. Product data is read far more than written and a minute of staleness is fine, so it fits; stock checks at checkout and payments always read the database. Then I plan for failure: request coalescing for hot keys, pre-warming before the sale, and if Redis goes down, a capped fallback with load shedding rather than 200,000 reads a second hitting Postgres.”

What if the cache goes down? Every read becomes a miss. If the database can carry that, you just get slower. If not, it’s a capacity cache: replicate it, keep a small in-process fallback, cap fallback queries and shed the rest, serve stale where allowed, and prove it with a cache-off load test.

How do you pick a TTL? From the staleness readers tolerate and how often the data changes: seconds for a live score, minutes for product pages, hours if you also invalidate on write. Always set one, add jitter, and consider soft and hard TTLs.

How do you keep the cache and the database consistent? You bound the gap rather than close it. Write the database, then delete the key (deletes are idempotent), with a TTL as backstop. For the race where a slow reader writes an old value back, use leases or versioned values, or invalidate from the database’s change stream. Anything that must never be stale isn’t read from a cache.

Local or remote cache? Local has no network hop, but copies drift between servers, database load grows with the fleet, and deploys start cold. Remote gives one shared copy that survives deploys, at the cost of a round trip and another fleet. At scale, use both: a small local cache with a short TTL for the hottest keys, in front of Redis.

How big should the cache be? Start from the working set (distinct items per TTL window × size) and the hit ratio the database needs. Skew lets a fraction of the data earn most hits, but each extra nine costs far more memory; add headroom, then tune from measured hit ratio and evictions.

Where to go next

• Caching strategies: every way to wire reads and writes, and the races between them.
• Cache eviction policies: LRU, LFU, TinyLFU, and what Redis does at maxmemory.
• Distributed caching: partitioning, replication and two-tier caches.
• Hot keys, cache stampede and invalidation: the failure modes above, in depth.
• Content delivery network: edge caching, HTTP headers and purges.
• Redis: the most common remote cache.
• Scaling reads: caching next to replicas and denormalisation.
• Design a distributed cache: all of this as an interview problem.
• Numbers to know: the latencies behind the arithmetic here.

References and further reading

1. Caching challenges and strategies (Amazon Builders’ Library)aws.amazon.comWhen to cache, local versus external caches, soft and hard TTLs, negative caching, request coalescing, and services that become “addicted” to their cache.
2. Caching best practices (AWS)aws.amazon.comLazy loading, TTL on every key, few-second TTLs for fast-changing data, TTL jitter, pre-warming new nodes, and what frequent evictions mean.
3. Scaling Memcache at Facebook (Nishtala et al., NSDI 2013)usenix.orgDemand-filled look-aside caching, delete-on-write, leases (17K/s to 1.3K/s), Gutter, cold cluster warm-up, measured fetch latency and warm-up times.
4. Addressing Cascading Failures (Google SRE book, chapter 22)sre.googleCold caches, the latency-cache versus capacity-cache distinction, and ramping load slowly so caches can warm.
5. Web Caching and Zipf-like Distributions: Evidence and Implications (Breslau et al., INFOCOM 1999)pages.cs.wisc.eduZipf-like popularity with exponents 0.64 to 0.83 across six proxy traces; 25–40% of documents drew 70% of accesses; hit ratio grows roughly with the log of cache size.
6. RFC 9111 — HTTP Cachingrfc-editor.orgPrivate versus shared caches, cache keys and Vary, freshness lifetime, max-age and s-maxage, the 10% heuristic, and the private directive.
7. Redis client-side caching referenceredis.ioServer-assisted invalidation (tracking), what to cache and what not to, and putting a maximum TTL on every locally cached key.
8. Redis key evictionredis.iomaxmemory and eviction policies, why allkeys-lru suits skewed access, and measuring hit ratio from keyspace_hits and keyspace_misses.
9. PostgreSQL documentation: Resource Consumption (shared_buffers)postgresql.orgThe database’s own buffer cache: 128 MB default, 25% of RAM as a starting point, and reliance on the OS page cache.
10. Latency Numbers Every Programmer Should Know, by year (Colin Scott)colin-scott.github.ioOrder-of-magnitude latencies for L1/L2 cache, main memory, SSD random reads, data-centre and cross-continent round trips.