The Memory Hierarchy

A processor can finish an addition in a third of a nanosecond and then wait a hundred nanoseconds for the next number to arrive from RAM. No storage technology is both large and fast, so every computer stacks several of them: registers, three levels of cache, RAM, solid-state drives, spinning disks, and then other machines. Each rung is slower than the one above it, by anything from a few times to about a thousand times.

This topic builds the latency ladder the rest of the book cites. Whenever a later page says "a cache miss" or "a round trip", the price comes from here. Chapter 1 charged every memory access one step; on a real machine one step can cost one nanosecond or a hundred million, depending on which rung answers.

Why Memory Comes in Layers

Fast memory is small, expensive per byte and physically close. A bit of cache is static RAM, built from six transistors that hold their value as long as power is on. A bit of main memory is dynamic RAM, one transistor and one tiny capacitor that leaks and has to be refreshed many times a second. The capacitor design packs far more bits into the same silicon, and pays for it with slower access. Distance matters too: in one nanosecond light itself covers only about 30 centimetres, and a signal on a chip or a circuit board is slower than light in a vacuum.

So the machine keeps a little fast memory beside each core and a lot of slow memory further away, and copies data up the ladder when it is used. The arrangement works only because programs reuse what they touched recently and touch what sits next to it. That habit is called locality, and the next topic is about it.

The Rungs and Their Sizes

At the top are the registers, the processor's working slots: 16 general-purpose registers on an x86-64 core and 31 on a 64-bit ARM core, each 8 bytes wide, plus a bank of wider vector registers: from a few hundred bytes to a few kibibytes in all. Below them, the L1 cache holds tens of kibibytes per core. The L2 cache holds hundreds of kibibytes to a few mebibytes per core. The L3 cache, shared by the cores, holds from several mebibytes to hundreds on large server parts.

Then comes RAM, measured in gigabytes, and storage, measured in terabytes: solid-state drives and spinning disks. Below that are other machines, reached over a network, with no upper limit on size at all. Every step down buys orders of magnitude of capacity and pays orders of magnitude of delay, as the pyramid shows.

The Latency Ladder

These are orders of magnitude drawn from several published tables, not one chip's measurement. The sources are Peter Norvig's timing table, Jeff Dean's "numbers everyone should know", Brendan Gregg's latency table in Systems Performance, and current vendor figures for solid-state drives. Any particular machine will differ by a factor of two or three on any row. The ratios between rows are what hold. To make them feel like time, the right-hand column pretends that one nanosecond lasts one second.

Reading a register takes about 0.3 nanoseconds, a third of a second on the human scale. An L1 cache hit takes about 1 nanosecond, one second. L2 takes about 4 nanoseconds, four seconds. L3 takes 10 to 40 nanoseconds, under a minute. RAM takes about 100 nanoseconds, under two minutes.

Then the scale changes. A random read from an NVMe solid-state drive takes 20 to 100 microseconds, which on the human scale is 6 to 28 hours. A round trip to another server in the same data centre takes 100 to 500 microseconds, one to six days. A random read from a spinning disk, which has to move its head and wait for the platter to turn, takes 5 to 10 milliseconds: two to four months. A round trip across a continent and an ocean, such as California to Europe and back, takes about 150 milliseconds, almost five years.

Two cautions about the scale. Brendan Gregg's version stretches one processor cycle, not one nanosecond, to a second, so his human times run about three times longer than these; do not mix the two tables. And the ladder spans about a hundred million from an L1 hit to a cross-continent round trip, a range the flat cost model of Chapter 1 cannot see.

Latency Is Not Bandwidth

The ladder is the wait for the first byte. After it arrives, bytes stream at the rung's bandwidth, and bandwidth is a second, separate ladder. One megabyte read sequentially costs tens of microseconds from RAM, a few hundred microseconds from an NVMe drive, and several milliseconds from a spinning disk.

The same megabyte read as 256 scattered pieces of 4 kibibytes each can pay the rung's latency 256 times. On a spinning disk that is 256 seeks, more than a second in total, against a few milliseconds for the sequential read. So on every rung below the registers, sequential access beats random access, and two of the most important structures in this book are built on that one fact: the operating system's page cache (Chapter 10) and the B-tree (Chapter 6).

What the Ladder Predicts

Put two operations on their rungs and the ladder answers questions that intuition gets wrong. A read from another server in the same data centre, 100 to 500 microseconds, is faster than a seek on the local spinning disk, 5 to 10 milliseconds. The same network read is a thousand to five thousand times slower than local RAM. That is why a network cache is fast next to a database on disk, and slow next to a dictionary inside the process.

The bottom row is set by physics, not by engineering. Light in optical fibre covers about 200 kilometres per millisecond. The great-circle distance from London to San Francisco is about 8,600 kilometres, so a round trip through perfectly straight fibre takes about 86 milliseconds. Real cables do not run straight and real routers add time, which is how the typical figure reaches 150. No hardware upgrade takes that round trip below those 86 milliseconds, and real routes stay well above them.

A Request's Latency Budget

Hold a request to a budget of 100 milliseconds. It cannot afford even one Europe-to-California round trip. It can afford a few hundred round trips inside one data centre, or about a million reads from RAM. A page that makes 50 database queries one after another spends 5 to 25 milliseconds waiting on the network before the database has done any work at all.

Every cache in the stack is an attempt to answer from a higher rung: the processor's caches, the operating system's page cache (Chapter 10), a cache server, a content delivery network at the edge. Each one is paid for twice, as Chapter 1 put it: in memory to hold the copy, and in staleness when the original changes and the copy does not.