Imagine you are solving a set of twenty Social Science questions at your study table. Question 3 asks for the capital of Australia. You do not know it offhand, so you get up, walk to the shelf, pull out the atlas, flip to the right page, find "Canberra," and walk back to your desk. Ten minutes later, question 7 asks for the same country's capital again. Do you walk back to the shelf and repeat the entire search? Almost certainly not — if you were even a little bit smart about it, you left the atlas open on your desk after the first lookup, so the second time the answer is simply sitting there. No walk, no page-flipping, just a glance.
That one small habit — keeping something you just used within easy reach because you expect to need it again soon — is the entire idea behind computer caching. A computer's fastest working memory (inside the CPU) is tiny and expensive to build, while the memory that can hold everything (your phone's storage, a hard disk, a remote server) is huge but comparatively slow to reach. A cache is a small, fast storage layer placed in between, holding copies of the data that is most likely to be needed again soon, so that most requests get answered quickly instead of making the long trip to slow storage every single time. This chapter builds that idea up carefully: why the trade-off between speed and size exists at all, how to measure whether a cache is actually helping, why caching works in the first place, and what a computer does when the cache itself fills up.
Why Computers Need a Memory Hierarchy
You might reasonably ask: if fast storage is so useful, why not just build all of a computer's memory to be that fast? The honest answer is cost and physics. The circuitry that makes memory extremely fast (called SRAM, used inside CPU caches) needs far more transistors per stored bit than the circuitry used for ordinary RAM (called DRAM), and far more again than the storage technology used in an SSD or hard disk. More transistors per bit means more silicon area, more heat, and more money for the same number of bytes. So instead of picking one point on the speed-versus-size line, computer designers use several layers at once — tiny and blazing fast at the top, huge and comparatively slow at the bottom — and let data flow between them automatically.
The diagram below shows this memory hierarchy. Notice the shape: each layer you go down is bigger in capacity but slower to access. When the CPU needs a piece of data, it checks the fastest layer first. Only if the data is not there does it move one level down, and so on, until it finally reaches main memory or storage.
These numbers are approximate and vary between specific processors and devices, but the pattern they show is what matters: going from L1 cache to RAM is already roughly a hundred-times slowdown, and going all the way to a hard disk can be ten million times slower than a register access. That gap is precisely why caching strategy — deciding what to keep close and what to leave far away — has such a large effect on how fast a program actually feels.
Cache Hits, Misses, and the Hit Ratio
Every time the CPU (or a browser, or an app) looks for data in a cache, exactly one of two things happens. A cache hit means the data was found in the cache — fast path taken. A cache miss means the data was not in the cache, so the system has to fetch it from the slower layer below, and usually stores a copy in the cache along the way in case it is needed again soon. The fraction of requests that are hits is called the hit ratio:
Hit Ratio = (Number of Hits) ÷ (Total Number of Accesses)
The hit ratio matters because it directly decides how fast the system feels on average. We can calculate the average access time as a weighted mix of the fast (hit) case and the slow (miss) case:
Average Access Time = (Hit Ratio × Cache Access Time) + (Miss Ratio × Memory Access Time)
Let's work this out with real numbers. Suppose a CPU's L1 cache takes 2 ns to access, and on a miss the CPU has to go all the way to RAM, which effectively costs 100 ns. If the hit ratio for a particular program is 90% (so the miss ratio is 10%, since the two must add up to 100%):
Average Access Time = (0.90 × 2) + (0.10 × 100) = 1.8 + 10 = 11.8 ns
Compare that to a system with no cache at all, where every single access costs the full 100 ns. The cache has made the average access roughly 100 ÷ 11.8 ≈ 8.5 times faster — even though 10% of the time, the cache did not help at all. Now watch what happens if better locality (or a smarter replacement policy, discussed shortly) pushes the hit ratio up from 90% to 99%:
Average Access Time = (0.99 × 2) + (0.01 × 100) = 1.98 + 1 = 2.98 ns
Going from a 90% to a 99% hit ratio — which sounds like a small improvement on paper — nearly quadruples the speed (11.8 ÷ 2.98 ≈ 3.96 times faster), and makes the system almost 34 times faster than having no cache at all. This is the single most important number in cache design: because a miss costs so much more than a hit, even small changes in hit ratio produce large changes in real performance. It is also why the rest of this chapter focuses on two questions — why do hit ratios end up high in the first place, and how do we keep them high when the cache is too small to hold everything?
Locality of Reference: Why Caching Works At All
Caching would be a pointless idea if programs accessed data in a completely random, unpredictable order — there would be no way to guess what to keep close by. Fortunately, real programs and real human behaviour are not random. They follow patterns that computer scientists group under the name locality of reference, and it comes in two forms.
Temporal locality means that if a piece of data is used once, it is likely to be used again soon. This is exactly the atlas example: you looked up "capital of Australia" once, and needed it again a few minutes later. A loop variable that is checked on every pass through a loop, a friend's UPI ID you use again to split an auto fare a few minutes after paying for lunch, or a webpage's logo image that appears on every page of the same site — all of these are reused again and again within a short span, so keeping a copy nearby pays off repeatedly.
Spatial locality means that if one memory location is accessed, nearby locations are likely to be accessed soon after. Reading a class's marks stored in consecutive cells of a spreadsheet column, or a program stepping through an array index by index, are classic examples — after position 5, position 6 is very likely to come next. Because of this pattern, a cache does not fetch just the single byte or item you asked for; it typically pulls in a whole neighbouring block at once, called a cache line or block, betting that the next few items will be needed shortly after. This single design decision — fetch a neighbourhood, not just a point — is a direct, deliberate exploitation of spatial locality, and it is a major reason why accessing data in order (row by row through a table) tends to make far better use of a cache than jumping around it in a scattered, unpredictable order, even when the total amount of data touched is identical either way.
Both forms of locality answer the earlier question of why hit ratios can realistically reach 90% or higher in practice: it is not luck, it is because real access patterns are clustered rather than random, and a well-designed cache is built specifically to take advantage of that clustering.
When the Cache Is Full: Replacement Policies
A cache is deliberately much smaller than the storage layer behind it — that smallness is exactly what makes it affordable and fast. That also means it will eventually fill up, and when a new item needs to come in, something already inside must be thrown out to make room. The rule that decides which item gets evicted is called a cache replacement policy, and different rules can produce very different hit ratios for the exact same sequence of requests, even with the exact same cache size.
Two of the simplest policies are:
- FIFO (First-In, First-Out): evict whichever item has been sitting in the cache the longest, regardless of how recently or how often it was actually used. Think of a queue at a canteen counter — first to arrive, first to leave, with no regard for who's hungriest.
- LRU (Least Recently Used): evict whichever item has gone the longest without being accessed, and every hit "refreshes" an item's position so it is not evicted soon. This directly exploits temporal locality — if you used something a moment ago, LRU assumes you will probably want it again soon, and protects it.
Let's compare them directly on the same reference string, with a cache that can hold only 3 items at a time: A, B, C, A, B, D, A, B, C, D.
| Step | Access | FIFO cache state | FIFO result | LRU cache state | LRU result |
|---|---|---|---|---|---|
| 1 | A | [A] | MISS | [A] | MISS |
| 2 | B | [A,B] | MISS | [A,B] | MISS |
| 3 | C | [A,B,C] | MISS | [A,B,C] | MISS |
| 4 | A | [A,B,C] | HIT | [B,C,A] | HIT |
| 5 | B | [A,B,C] | HIT | [C,A,B] | HIT |
| 6 | D | [B,C,D] | MISS | [A,B,D] | MISS |
| 7 | A | [C,D,A] | MISS | [B,D,A] | HIT |
| 8 | B | [D,A,B] | MISS | [D,A,B] | HIT |
| 9 | C | [A,B,C] | MISS | [A,B,C] | MISS |
| 10 | D | [B,C,D] | MISS | [B,C,D] | MISS |
Count the hits: FIFO gets 2 hits out of 10 (a 20% hit ratio), while LRU gets 4 hits out of 10 (a 40% hit ratio) — double, on the identical sequence of requests with the identical cache size. The difference shows up at steps 7 and 8: FIFO had already evicted A and then B purely because they had been sitting in the cache the longest, even though both had just been used at steps 4 and 5. LRU, by tracking actual recency of use, kept them around and turned those two into hits. This is exactly why real hardware caches almost always use LRU or a close, cheaper approximation of it (called "pseudo-LRU," since tracking exact recency for a large cache is itself expensive to build) rather than plain FIFO.
A third common policy is LFU (Least Frequently Used), which evicts whichever item has been accessed the fewest times overall rather than the longest unused. LFU sounds appealing, but it has a specific weakness: a brand-new item that just entered the cache starts with an access count of only 1, so it looks "unpopular" and can get evicted almost immediately — even if it was about to be accessed heavily. This effect is sometimes called cache pollution, and it is one reason LFU needs extra tricks (like slowly "aging" old counts) to work well in practice.
Here is a working Python implementation of LRU that reproduces the exact trace above. It uses a plain dictionary, which in Python (3.7 and later) keeps keys in the order they were inserted — removing and re-inserting a key on every hit is exactly how we mark it as "most recently used":
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {} # dict preserves insertion order in Python 3.7+
def access(self, key):
if key in self.cache:
self.cache.pop(key)
self.cache[key] = True # reinsert at the end (most recently used)
return "HIT"
else:
if len(self.cache) >= self.capacity:
oldest = next(iter(self.cache)) # first key = least recently used
self.cache.pop(oldest)
self.cache[key] = True
return "MISS"
sequence = ["A", "B", "C", "A", "B", "D", "A", "B", "C", "D"]
lru = LRUCache(3)
hits = 0
for item in sequence:
result = lru.access(item)
if result == "HIT":
hits += 1
print(item, result)
print("Hit ratio:", hits, "/", len(sequence))
Running this produces:
A MISS
B MISS
C MISS
A HIT
B HIT
D MISS
A HIT
B HIT
C MISS
D MISS
Hit ratio: 4 / 10
which matches the LRU column of the trace table exactly — 4 hits out of 10 accesses.
A Common Misconception: "Clearing Cache" and "Bigger Is Always Better"
Most students have tapped "Clear Cache" in their phone's app settings, and it is worth correcting a mix-up that this button causes. An app's cache stored on your phone is temporary data saved to your phone's flash storage — things like already-downloaded images, decoded fonts, or previously loaded screens — kept there specifically so the app does not have to re-download or re-process them next time. RAM, on the other hand, is a completely separate kind of memory: the fast, volatile working space holding whatever the CPU is actively running right now, and it empties automatically the moment an app is closed or the phone restarts. Clearing an app's cache does not free up RAM, and it has nothing to do with how much RAM is currently in use. What it actually does is delete those saved files from storage — which is why, right after clearing it, the app often feels noticeably slower: it now has a "cold" cache and must rebuild it from scratch, exactly like walking back to the shelf for the atlas all over again after having put it away.
A second misconception is that a bigger cache is always a faster cache. It is not automatic. Two real costs work against simply growing the cache: a larger cache is slower to search through on every single access (more entries to check means more circuitry or more comparisons before deciding hit or miss), and the fast memory it is built from is expensive, so there is a real cost ceiling on how large it can practically be. More importantly, a bigger cache only helps if the program's actual access pattern has enough locality of reference to fill it usefully — if a program touches a huge amount of data in a genuinely unpredictable order, doubling the cache size may barely move the hit ratio at all, because the extra space just holds more items that will not be revisited before they are evicted anyway. Cache effectiveness is a property of the size, the replacement policy, and the workload's locality of reference all together — not of size alone.
Where You Meet Caching Every Day
Once you know what to look for, caching is everywhere in the software you already use. Your web browser caches images, fonts, and script files from websites you visit, which is why revisiting a page you opened an hour ago loads far faster than the first time — the browser is reusing local copies instead of downloading them again, a direct application of temporal locality. Your device also keeps a DNS cache: the first time it looks up a website's address (say, translating a site name into a numeric IP address), it remembers the answer for a while, so the tenth visit that day does not repeat the same lookup over the internet.
At a larger scale, services that stream video or serve content to large numbers of people at once — for example, viewers rushing to watch highlights of a cricket match within minutes of each other — rely on CDNs (Content Delivery Networks), which place cache servers at multiple locations across the country. Instead of every single viewer's request travelling all the way to one distant origin server, popular content is cached at the data centre nearest to the viewer and served from there, cutting both the distance the data has to travel and the load on the original server.
Everyday apps use the same idea at a smaller scale. UPI payment apps and train-booking apps typically cache things like your saved list of payees or your recently searched routes locally, so those screens appear instantly rather than waiting on a network request. Notice, though, what these apps deliberately do not cache: your account balance or live seat availability is fetched fresh every time, because that data changes constantly and a stale cached copy could be actively misleading. This is an important design lesson hiding inside a familiar app — caching is a great tool for data that is reused often and does not need to be perfectly up-to-the-second, and a poor (even dangerous) tool for data that must always reflect the current truth.
Summary
- A cache is a small, fast storage layer that keeps copies of frequently or recently used data close to where it is needed, because fast memory is expensive and cannot practically hold everything.
- Computers use a memory hierarchy — registers, L1/L2/L3 cache, RAM, SSD, hard disk — where each layer down is bigger but slower; the CPU checks the fastest layer first and only descends on a miss.
- A cache hit is served quickly; a cache miss must fall through to slower storage. Average Access Time = (Hit Ratio × Cache Time) + (Miss Ratio × Memory Time) — and because a miss costs so much more than a hit, even small hit-ratio improvements produce large speedups.
- Caching only works because real access patterns show locality of reference: temporal locality (reuse the same item soon) and spatial locality (nearby items get used soon after).
- Because a cache is smaller than what's behind it, it needs a replacement policy for when it fills up. FIFO evicts the oldest arrival; LRU evicts the least recently used item and generally achieves a higher hit ratio because it tracks actual usage; LFU evicts the least frequently used item but risks evicting brand-new, soon-to-be-popular data.
- "Clearing cache" empties saved storage files, not RAM — the two are different kinds of memory entirely. And a bigger cache only helps when the workload's access pattern has locality worth exploiting.
Practice: Test Yourself
- A cache has a hit ratio of 0.8, a cache access time of 3 ns, and a memory access time of 80 ns on a miss. Calculate the average access time.
- Trace an LRU cache of capacity 2 on the reference string X, Y, X, Z, X, Y. Show the cache state after each access and compute the final hit ratio.
- Two programs touch exactly the same total amount of data. Increasing the cache size from 256 KB to 8 MB nearly eliminates misses for Program 1 but barely changes the hit ratio for Program 2. What property of each program's access pattern most likely explains this difference?
- Which of these is not a cache replacement policy: (a) LRU (b) FIFO (c) LFU (d) RAM?
- A friend says: "I cleared my phone's WhatsApp cache and now photos take longer to load — clearing the cache must have made my RAM fuller, which is why it's slower." What is the mistake in this reasoning?
Answers: (1) (0.8 × 3) + (0.2 × 80) = 2.4 + 16 = 18.4 ns. (2) Step-by-step: X miss [X]; Y miss [X,Y]; X hit, order becomes [Y,X]; Z miss, evict Y (LRU), order [X,Z]; X hit, order [Z,X]; Y miss, evict Z, order [X,Y]. Hits at steps 3 and 5 → hit ratio = 2/6 ≈ 33.3%. (3) Program 1 likely has strong locality of reference confined to a "working set" that fits once the cache reaches 8 MB, so nearly everything it repeatedly touches now stays cached; Program 2 likely accesses data in a pattern with little locality (spread widely or effectively random), so no practical cache size captures enough of it to raise the hit ratio much. (4) (d) — RAM is a memory layer, not a rule for deciding what to evict. (5) The mistake is conflating two different kinds of memory: the app cache lives in phone storage, not RAM, and clearing it does not change how much RAM is in use. The slowdown happens because the cache is now "cold" — WhatsApp has to re-fetch or re-process data (like images) it would otherwise have reused, exactly like walking back to the shelf for the atlas after putting it away.