Caching & Databases · lesson 4 of 8 · about 25 min
One lookup, the whole machine
Follow a single indexed database lookup through everything you have learned: from a page number, to a track and sector on a spinning disk (or a flash page on an SSD), into RAM, and finally into the CPU cache. See exactly where the time goes, and why each level is fast or slow. Tap any for its meaning.
Where does an index page actually live?
From “page 1,234,567” to a physical place.
Choose HDD or SSD and watch the last layer change. A hard disk needs the track, surface and sector so the arm knows where to go. An SSD uses a to find a channel, chip, block and page.
Then press Rewrite this page on both, and see the biggest difference between them.
The block number never changes. What it points to underneath can.
- 1 · The database's view
index page #1,234,567The B-tree stores nodes as fixed 8 KB pages. The database only ever says: give me page number N of this index file. - 2 · Position in the file
bytes 10,113,572,864 to 10,113,581,055The index is one big file. Page N sits at byte N × 8,192. - 3 · File system blocks
file blocks 2,469,134 and 2,469,135 (4 KB each)The file system cuts the file into 4 KB blocks and keeps a map from each file block to a place on the drive. - 4 · Drive block address (LBA)
sectors 19,755,120 to 19,755,135The OS asks the drive for numbered 512-byte sectors, called logical block addresses (LBA). It has no idea what is physically behind them. - 5 · Where the arm must go
cylinder 2,057 · surface (head) 6 · sector 720The drive turns the block address into geometry: which ring (track 16,462), which side of which platter, which arc. Fixed forever for this block.
Pick a page and a device. The chain below shows where that page physically lives.
A lookup that misses RAM
Four reads in a row, each waiting for the last.
If a page is not in RAM the database must read it from disk. On a hard disk each of those reads moves the arm and waits for the spin. Choose the device and how much is already in RAM, then run one lookup.
An SSD's many flash chips () can serve different lookups at once, but they cannot shorten this chain, because each step waits for the one before.
Try cold on the hard disk, then warm. Two pages in RAM halves the time. All four in RAM makes it microseconds.
- 1. Root pagewill be on disk–
- 2. Level-2 pagewill be on disk–
- 3. Leaf pagewill be on disk–
- 4. Table row pagewill be on disk–
Press Run. Dark pages are read from disk, green ones from RAM.
Inside one page in RAM
Even a page in RAM isn't free to search.
The CPU reads memory in 64-byte , 4 entries each. The first probes land on far-apart lines (each a separate fetch), but the last probes are neighbours inside the same line, which is already in L1, almost free.
Pick where the page is held and run a search. Watch which lines get touched and what each touch costs.
This is why B-tree pages hold hundreds of keys: one expensive fetch buys a search among 500 items, not 2.
Each square is one 64-byte cache line (4 entries). Numbers show the order of first touches.
Press Search. Binary search needs only ~9 probes to find one of 512 entries.
How a CPU cache finds your data
No searching: the address is the map.
That is why a lookup is a nanosecond, not a search. It is also why strides that are multiples of a power of two are dangerous: many addresses share the same index bits and fight over one set while the others sit empty (a ). Each set holds 2 ways ().
Choose an access pattern and step through it. Watch which set is chosen each time.
Compare “same set” and “different sets”. Same number of addresses, very different hit rate.
Reading 8 bytes at a time through 6 cache lines.
Press Next access to send the first address into the cache.
The whole journey
One lookup, four pages, four different places.
Costs per page: in cache or RAM, the ~9 probes touching about 6 new cache lines at the speed of that level. On disk, the device's delay ( for a hard disk, flash sensing for an SSD) plus the search in RAM afterwards.
Compare the presets. The same lookup swings by a factor of thousands, entirely depending on where its pages are. That is the reason caches, buffer pools and indexes exist.
Look at which page dominates the bar. When anything is on a hard disk, it is always the disk page.
- Root page10 ms
- Level-2 page10 ms
- Leaf page10 ms
- Table row page10 ms
40 ms for one row. The slowest step is the root page at 10 ms: a trip to HDD that the lookup had to wait for. A busy server doing this thousands of times a second would collapse.
Check yourself
Trace a lookup in your head.
Seven questions, each worth 20 XP. If you can answer these you can explain, from the arm of the disk to the tag in the cache, exactly why an index makes reads fast.
Follow the dependency: each step waits for the one before. That one idea explains most of the latency.
A cold index lookup on a hard disk costs one seek per tree level. Why can't the disk fetch all four pages at once?
Tip: press 1 to 3 to answer, Enter for the next one.
Break It
Restart the database and watch it limp.
A hard disk manages about 120 reads per second, so it cannot even keep up with the lookups, never mind refill 50,000 hot pages. Requests queue and latency explodes. An SSD fills the cache in seconds. Try pre-warming the cache before sending traffic.
Speed is not only about steady state. How a system behaves in its first minute decides whether it survives a restart.
Press the button to restart the database and watch the first minute.