Caching
How do you serve the same answer thousands of times without asking the database each time?
Why do fast systems keep copies, and what does a copy cost?
Almost every fast system you use is fast because it avoids repeating work. Your processor keeps recently used memory in small caches beside each core: reading a value from the first-level cache takes around a nanosecond, while reading it from main memory takes around a hundred. Your laptop remembers the address behind a website name it looked up a minute ago, for as long as the owner of that name’s DNS record allows. In 2013 Facebook described a memcached deployment that served billions of requests a second, so that its databases saw only a small fraction of the reads (Scaling Memcache at Facebook). These are three very different machines applying one idea. A cache keeps a copy of an answer that was expensive to produce, close to where it is needed, so that the next request can use the copy and skip the work.
The idea works because demand is uneven. Programs touch the same memory again and again, a property called locality of reference. People ask for the same few things far more often than for the rest. Breslau and colleagues showed in 1999 that requests for web pages follow a Zipf-like distribution, in which a small set of popular pages accounts for most of the traffic (Web Caching and Zipf-like Distributions). When a small share of the data receives most of the reads, a small cache absorbs most of the load. The measure of this is the hit rate, the share of requests the cache answers. Its arithmetic is unforgiving in a useful way. Raising the hit rate from 90% to 99% cuts the requests that reach the database by a factor of ten, from one in ten to one in a hundred.
The price of a copy is that it can be wrong. The moment the original changes, every copy is out of date until something corrects it or removes it. Phil Karlton, an engineer at Netscape, is usually credited with the remark that there are only two hard things in computer science: cache invalidation and naming things. The joke has lasted because it is accurate. The real design work is deciding when a copy expires, who must delete it, and what happens when thousands of requests find it missing at the same instant. On 23 September 2010 Facebook was down for about two and a half hours because of that last question. An automated system that repaired invalid values in a cache responded to one bad configuration value by sending every client to the same database cluster for the correct one. The cluster received hundreds of thousands of queries a second and could not recover until the site was switched off (Facebook’s account of the outage).
A cache also protects only the reads that can be shared. In June 2017, during India’s opening Champions Trophy match against Pakistan, Hotstar sent a push notification as Virat Kohli walked out to bat, and requests to its login service rose from about 10,000 to 1,25,000 a second within seconds. Hotstar cached heavily at several layers, but a login answer belongs to one person and cannot be served from a shared copy, so every one of those requests reached a database that had not been scaled for the wave (Hotstar’s engineering account). Before you add a cache, ask which of your reads are the same for many people.
Every cache design answers three questions: where the copy lives, how it is filled, and how it is corrected when the truth changes. A processor answers them in hardware. A DNS resolver answers them with a time-to-live chosen by the owner of each name. A web application answers them with code that you write. To keep the questions concrete, we will answer them for one ordinary case, the menu page of a food-ordering service, which is read about 900 times a second at its peak and changes a few times a day. The same reasoning applies unchanged to a product catalogue, a news homepage or a user’s profile.
Pause and predict Before reading on, propose a design. The database can serve 600 menu queries a second, and 900 arrive. Decide where you would keep the copy, when it should be filled, and for how long a customer may be shown a price that has already changed. Then say what your design does at the instant a popular menu’s copy expires while 900 requests a second are arriving.
The database is doing the same work over and over
A kitchen’s menu changes when a price is edited or a dish sells out, a few times a day. Between those moments, every one of the 900 reads a second returns the same rows, and the database, which can serve about 600 menu queries a second, builds the same answer again and again.
- Cache
- A fast store that keeps copies of answers that are expensive to produce, so repeated requests can skip the expensive work.
- For example: The built menu for kitchen 42, kept in memory under the key
menu:42for 10 minutes.
The share of reads the cache answers is the hit rate, and everything that follows comes back to it.
In code, a cache is a hash map you are allowed to lose: hash maps in Coding Patterns.
A mental model
Four ways to wire a cache
The patterns differ in who fills the cache and when writes reach the database.
- Cache-aside (lazy loading). The app checks the cache; on a miss it reads the database and stores the result. Writes go to the database, and the app deletes the cached copy. The most common pattern, and the one used here.
- Read-through. Like cache-aside, but the cache library loads from the database itself on a miss, so the app only talks to the cache.
- Write-through. Every write goes to the cache and the database together, so the cache is always fresh for what was written. Writes get slower, and the cache fills with data nobody may read.
- Write-back (write-behind). Writes go to the cache only and reach the database later, in batches. The fastest writes, and the riskiest: if the cache dies before it flushes, those writes are gone.
Step through cache-aside: one hit, then one miss that fills the cache.
Hit-rate arithmetic
Two formulas carry most cache decisions. With hit rate h, a cache lookup of 1 ms and a database query of 20 ms:
average read time = h x 1 ms + (1 − h) x (1 ms + 20 ms)
database load = total reads x (1 − h)
| Hit rate | Average read | Database load at 900 reads/s |
|---|---|---|
| 0% | 20 ms (no cache) | 900/s: over capacity |
| 50% | 0.5 + 10.5 = 11 ms | 450/s |
| 90% | 0.9 + 2.1 = 3 ms | 90/s |
| 99% | 0.99 + 0.21 = 1.2 ms | 9/s |
Read the last column. Going from 90% to 99% looks like a small step, and it cuts the database’s load by ten times, from 90 queries a second to 9. So judge a cache by its misses, because the misses are what reach the database.
The cache needs only enough memory for the hot data, the entries that are read often. Suppose the service has about 200 kitchens and a built menu is a few kilobytes. All of them together fit in a few megabytes. When those entries do not all fit, the cache must evict something, usually the entry used least recently (LRU). The LRU cache that interviews often ask you to build, a hash map plus a linked list, implements this policy: LRU cache in Coding Patterns.
How long may a copy live?
Suppose the price of a dish changes from ₹120 to ₹130. With a 10-minute TTL, the menu page can show the old price for up to ten minutes after the change, and a customer who orders in that window sees one price and is billed another. One fix is a TTL of 30 seconds. The other is a long TTL, with the copy deleted on every change.
The worry about a forgotten delete is fair: if one write path forgets it, nothing fails visibly and the page stays stale. That is why the decision record keeps the TTL as a safety net and computes every bill from the database. A lost delete can leave the page out of date for up to 10 minutes, but the bill never uses a cached price.
The short TTL wins whenever the writes do not pass through your code, because then there is nothing that could send the delete. A DNS resolver is the clearest case: it cannot know when the owner of a name changes the record, so it relies on the record’s TTL alone, and owners who plan a move lower that TTL to a few minutes a day ahead. The same holds for a cache of another company’s API, such as exchange rates fetched every 60 seconds. If a copy may be at most 60 seconds stale and you cannot see the writes, a 60-second TTL is the whole design.
What to remember
- A cache keeps copies of answers that are read far more often than they change. Its value is measured in misses: 99% versus 90% hits is ten times less database load.
- Cache-aside fills the cache on a miss and deletes on a write; write-through writes both at once; write-back delays the database write and can lose data.
- Every cache needs a freshness story: delete on change, a TTL as a safety net, and nothing that costs money read from a cached copy.
- A popular key expiring can cause a stampede; coalescing, leases and early expiration prevent it. How keys are placed across cache machines decides how much survives adding one.
Every cached copy needs a plan for the moment the truth changes.
In the real world
An LLM keeps the same kind of cache inside the model: the keys and values of every earlier token, computed once and reused for each new one. The KV cache in LLM From First Principles.
The simulator treats the cache as a fixed hit rate. A real hit rate depends on how much memory the cache has, how many distinct keys are hot, the TTLs, and how often writes delete entries. You measure it, and it is one of the first numbers to watch on any system with a cache.