The memory hierarchy

Why it matters

The single most useful set of numbers in computing is how long it takes to fetch data from each level of storage. They explain why caching works, why databases are organised in pages, why reading a file sequentially is fast and randomly is slow, and why a service that calls another service is so much slower than one that does not. Every design decision about where data lives is a decision about this hierarchy.

The idea

Fast memory is small and expensive; big memory is slow and cheap. So computers stack several levels, each larger and slower than the one above, and keep the data in current use in the faster levels. The CPU looks in the fastest level first and falls through to slower ones on a miss.

Numbers worth memorising

Access	Approximate latency	If one L1 hit were one second
L1 cache hit	~1 ns	1 second
L2 cache hit	~4 ns	4 seconds
L3 cache hit	~15–40 ns	under a minute
Main memory (DRAM)	~80–100 ns	about a minute and a half
NVMe SSD random read	~20–100 µs	half a day to a day
Round trip within a data centre	~0.5 ms	about a week
Hard disk seek	~5–10 ms	two to four months
Round trip across a continent	~80–150 ms	about three to five years

Cache lines and locality

Caches do not move single bytes; they move cache lines, typically 64 bytes. Reading one byte from memory brings its 63 neighbours into the cache for free. Hardware prefetchers watch access patterns and fetch the next lines before you ask. Two kinds of locality make this pay off: temporal (data used now is likely used again soon) and spatial (data near what you used is likely used next). Code that walks memory sequentially gets near-L1 speed; code that jumps around pays a main-memory trip on almost every access.

Pattern	Cache behaviour	Speed
Iterating an array in order	Each 64-byte line serves 16 ints; prefetcher runs ahead	Near peak
Iterating a linked list	Each node may be anywhere in memory; one miss per node	Often 10x or more slower
2D array by rows (row-major language)	Sequential	Fast
2D array by columns	Each access in a different line	Several times slower
Hash table with large values	Lookup hits a random line; value spans several	One or more misses per lookup

When cores share caches

L1 and L2 are usually per core; L3 is shared. When two cores write to different variables that happen to sit in the same cache line, the line ping-pongs between them, each write invalidating the other core's copy: false sharing. Counters updated by many threads are the classic victim; padding each counter to its own line fixes it.

The same idea, all the way up

The hierarchy does not stop at the machine. A service's in-process cache, a Redis cluster, the database's buffer pool, a CDN edge and object storage are the same pattern at larger scale: keep the hot working set in the faster, smaller tier, and accept a miss penalty for the rest. The Caching module in System Design is this lesson applied to distributed systems.

Trade-offs

Caching trades capacity for speed at every level, and only pays off when access has locality. Workloads with no locality (random access over a dataset far larger than cache) run at the speed of the slowest level involved, no matter how much faster the top levels are. Data layout choices that favour the cache (arrays of structs versus structs of arrays, compact representations) often matter more than algorithmic tweaks.

In an interview

Use the numbers to justify placement: "Session lookups happen on every request, so they live in Redis in the same zone, about half a millisecond, not in the primary database across the region. Product data is cached in-process for the hottest 10,000 items, which is memory access, about 100 nanoseconds." Or to explain a data structure: "B-trees use page-sized nodes because each disk or SSD read fetches a whole page anyway."