Part 2 of 7 · 2 min read
A copy that is closer
The basic idea of a cache and the definition of locality.
Think of a cook who keeps salt, oil and pepper on the counter, not in the storeroom down the hall. Most dishes need those three. Walking to the storeroom every time would slow every meal. The counter holds a small, fast copy of the things used most.
The book "Understanding Distributed Systems" defines a cache as a high-speed storage layer that temporarily holds the answers of a slower dependency, so that later requests can be served from it. It calls this a form of best-effort replication: the cache holds a copy, but the copy may be out of date or missing.
Cache
A cache is a small, fast store that keeps copies of data from a slower source, so that repeated reads do not go to the slow source.
Example: a web server keeps the 10,000 most-read product pages in memory. A read for one of them is answered from memory, and the database is not asked.
A cache pays off only if the same data is asked for again. The book states this as a need for a high chance that the requested data is found in the cache. That chance depends on the pattern of requests.
Locality of reference
Locality of reference is the tendency of a workload to ask for the same few items again and again, or for items close to the ones just used.
Example: on a news site, the five stories on the front page get most of the reads in the hour after they are published. The thousands of old stories get very few.
Two kinds of locality matter:
- Repeat in time. An item read now is likely to be read again soon.
- Skew. A small share of the items receives most of the requests.
A worked example of skew, with made-up figures. A shop has 1,000,000 products. In a day, 20 percent of the products (200,000) receive 80 percent of the page views, and the other 800,000 products share the remaining 20 percent. A cache that holds only those 200,000 products can answer about 80 percent of the views. The cache is one fifth of the data and serves four fifths of the requests.
A workload with no locality does not benefit. If every request asks for a different item that was never asked for before, every read is a miss, and the cache only adds a wasted lookup.
Read it as
A cache bets that the future looks like the recent past. The bet wins when requests repeat.
Check yourself:
- A report job reads every row of a table exactly once, in order. Will a cache help? Why?
- In the shop example, what share of the products must the cache hold to serve 80 percent of the views?