Why Caching Works: Locality & Hit Rates

Your database is the hardest tier to scale, yet most of what it does all day is answer the same questions again and again: the same product page, the same profile, the same front page. Caching means keeping a copy of an answer somewhere much faster, so the next person who asks does not trouble the database at all. Of all the tools in this course it is the cheapest way to lift a large share of load off the data tier, which is why this module comes straight after databases.

A reference librarian is asked for the same few books all day. Walking to the basement stacks each time takes five minutes, so the librarian keeps the most requested books on the desk. Most visitors are served in seconds, and only the odd request for a rare title means a trip downstairs. The desk is small, and that is fine, because it only has to hold what is asked for most often.

• -The desk is the cache: small, fast and close.
• -The basement stacks are the database: large, authoritative and slow to reach.
• -Finding the book on the desk is a cache hit; having to go downstairs is a cache miss.
• -The desk can hold only so many books, just as a cache has limited memory.

The desk only works because requests are not spread evenly. Real traffic is lopsided: a few trending products, viral posts or celebrity profiles account for a large share of all reads, while most items are touched rarely or never. This is called locality, and it comes in two forms. Popular items are asked for again and again (skew), and an item asked for just now is likely to be asked for again soon (recency).

Here is why that matters for size. Say a shop has 10 million products at about 2 KB each, which is 20 GB in total. If the most popular 20% of products draw 80% of the views, caching just that hot 20% means 4 GB. That fits in the memory of one ordinary cache server, and it can serve most of your reads.

Hit ratio is hits divided by hits plus misses. If 1,000 requests are served from the cache and 100 miss and go to the database, the hit ratio is 1,000 / 1,100, about 90.9%, so the database sees roughly 1 request in 11. The ratio deserves attention because the database's load depends only on the misses, and misses shrink quickly as the ratio approaches 100%. Take a steady 10,000 requests per second:

Going from 90% to 99% looks like a small improvement, yet it cuts the database's load by a factor of ten. That is why teams chase the last few points of hit ratio.

A hit is fast, but a miss is slower than having no cache at all, because it pays for the failed lookup and then the database trip. Say a cache lookup takes 1 ms and a database query takes 20 ms, so a miss costs 21 ms. The average is the hit ratio times 1 ms plus the miss ratio times 21 ms. At 50% that is 0.5 x 1 + 0.5 x 21 = 11 ms. At 90% it is 0.9 x 1 + 0.1 x 21 = 3.0 ms. At 99% it is 0.99 x 1 + 0.01 x 21 = 1.2 ms.

These numbers are illustrative and yours will differ, but the shape will not: a cache improves both things you care about, the load on the database and the speed users see, and both depend on the hit ratio.

The diagram shows the flow. The application asks the cache first, and only a miss continues to the database:

• -In the browser: the closest copy of all, and free.
• -At the edge: a CDN keeps copies near users, as the earlier module showed.
• -Inside the application's own memory: the fastest option, but each server has its own copy.
• -In a shared cache such as Redis or Memcached: one copy that every server uses, and the focus of this module.
• -Inside the database itself, which keeps recently used data in memory too.

It is the same idea at every layer: keep a copy closer to whoever is asking.

• -Data that is written constantly: every write makes the cached copy wrong, so it is thrown away before it can be reused.
• -Data nobody asks for twice: if every request is for a different key, the hit ratio stays near zero and the cache is just extra latency and cost.
• -Data that must be perfectly fresh on every read, such as a balance at the moment of payment.

To feel how different the layers really are, the card below lists the typical latency of each, from a CPU cache to a round trip across an ocean: