Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 37 ยท Caching Concepts

Locality and Working Sets

See why a small cache can serve most requests: skewed popularity (Zipf), the working set, and how hit ratio grows with cache size, with a simulation you can run.

A cache is much smaller than the data behind it, yet it can serve most requests. That only works because requests are not spread evenly: a few items are asked for constantly and most are barely touched. This property is called locality, and it is the reason caching works at all.

In this lesson you will learn the two kinds of locality, meet the skewed popularity pattern found on almost every real site, and use a simulation to see how the hit ratio depends on cache size.

Two kinds of locality

  • Temporal locality: an item used recently is likely to be used again soon. The article that just went viral, the user who is browsing right now.
  • Spatial locality: items near one used item are likely to be needed too. This matters for CPUs fetching memory lines; in web caching it shows up as related keys, such as the other products in a category you just opened.

For a Memcached deployment, temporal locality and popularity skew matter most.

Popularity is skewed

On most sites, request counts per item follow a heavy-tailed shape often modelled by a Zipf distribution: the most popular item gets a large share, the second gets about half of that, the third about a third, and so on. The probability of rank k is proportional to 1 / k^s, where s (around 1 for many sites) controls how steep the skew is.

Python Zipf popularity: share of traffic per rank

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The top 1,000 of 10,000 items, only 10% of the catalogue, carry roughly three quarters of the traffic in this model. Cache just those and most requests never reach the database.

The working set

The working set is the set of distinct items that are actually used during a window of time. If your site has 5 million products but only 40,000 are viewed in an hour, the working set for that hour is 40,000 items. A cache that can hold the working set will have a high hit ratio; one that is much smaller will churn, constantly evicting items it needs again soon.

To size a cache, estimate the working set over a useful TTL window and multiply by the average item size including overhead. You will practice this again in the chapter on sizing.

Simulating hit ratio against cache size

The experiment below generates a stream of requests with Zipf popularity (fixed random seed, so it is repeatable), then runs it through a simple LRU cache of different sizes. LRU, "least recently used", evicts the item that has gone longest without being touched; the next lesson covers it properly.

Python Hit ratio vs cache size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see diminishing returns: the first few hundred items buy a big jump, while doubling an already large cache adds only a little. This curve is the economic heart of caching. At some point more RAM costs more than the database load it saves.

What if popularity is flat?

When every item is equally likely (s = 0), there is no locality to exploit and the hit ratio is simply cache size / catalogue size. Try changing s in the simulation.

Python Skew changes everything

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a flat distribution (s = 0) the same 250-item cache hits only about 5% of the time, because 250 is 5% of 5,000. With a steep skew it hits most of the time. Before sizing a cache, look at your own traffic to see how skewed it really is.

Real-world patterns that break locality

  • Scans. A crawler or a batch job walking through every item floods the cache with items that will never be used again, evicting the hot ones. This is called cache pollution.
  • One-hit wonders. On many sites a big share of cached items are requested exactly once. Admission policies or short TTLs for rarely seen keys help.
  • Time-of-day shifts. The working set at 3 a.m. differs from lunchtime. A cache sized for one may be too small for the other.
  • Flash crowds. A sudden viral item creates a new hot key. See Stampede Protection for what happens when it expires.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the working set?

    A cache that holds the working set serves most requests; one that is much smaller keeps evicting items it needs soon.
  2. 2. In a Zipf distribution with s = 1, how does the second most popular item compare to the first?

    Popularity is proportional to 1/rank, so rank 2 gets about 1/2 of what rank 1 gets.
  3. 3. What happens to the hit ratio when you keep doubling an already large cache?

    The hottest items fit first. Later memory holds colder items that are rarely requested, so each doubling adds less.
  4. 4. Which workload pollutes a cache?

    A full scan inserts items that will never be asked for again, pushing out useful ones.

Summary

  • Caching works because requests are skewed: a small set of items gets most traffic.
  • Zipf-like popularity means a cache holding about 10% of items can serve around 75% of requests (depends on the skew).
  • The working set is what you must fit in memory; hit ratio rises with size but with diminishing returns.
  • With no skew, hit ratio equals cache size divided by catalogue size.
  • Scans, one-hit wonders and flash crowds can break the pattern.

Next: Eviction Policies