Caching & Databases · lesson 3 of 8 · about 30 min
Inside the database engine: pages, the buffer pool, the write-ahead log and fsync, row versions that pile up, B-trees against LSM trees, and when to choose rows, columns or RAM. Tap any for a plain-language card.
Life of a read
A database never reads a single row off the disk. Disks work in blocks, so rows are packed into fixed-size (here 8 KB, roughly 80 rows of 100 bytes). To read one row it loads its whole page into RAM.
Recently used pages stay in the , the database's own cache. Run 60 single-row lookups and watch which pages get fetched, and how much data moves for how little you asked.
You wanted 100 bytes. The disk moved 8,192. That ratio is the database's version of cache lines.
Press Run. Teal = page already in RAM. Coral = disk read.
Why a write costs more
When you commit, the database changes the page in RAM (fast, but ). Rewriting the real data page on disk for every commit would be slow and scattered, so it first appends one small record to the : a sequential write, cheap.
But “appended” may only mean the OS has it in RAM. forces it onto the drive, and waits. Later a writes the changed pages. After a crash, replays the log.
Commit some orders with fsync on, pull the plug, recover. Then do it with fsync off.
Every commit is a promise to a customer. fsync is what makes the promise survive a power cut, and it is the slow part.
RAM buffer pool ⚡ volatile
Write-ahead log sequential
Data file random pages
A quiet database. Commit a few orders, then try the buttons. (Real databases also use group commit: many commits share one fsync, so throughput rises without giving up safety.)
Where the time goes
Below is one UPDATE broken into steps, with a bar for each (log scale: each notch is ten times longer). Change the setup and watch the biggest step. Reads reuse only the first, second and last rows.
Not shown, because they happen later but still cost: the changed page is rewritten at the next , old row versions are cleaned by vacuum, and LSM engines merge files in the background ().
Turn fsync off and watch the write get fast. Then remember what the plug-pulling scene showed you.
Read the statement and pick a plan. Same for reads.
Four page reads, mostly already in RAM. A read does this too.
Stop anyone else changing it at the same moment.
Edit the copy in the buffer pool. Cheap.
Each index is a separate B-tree with its own page to find and change.
One small sequential write describing the change.
Force the log through every cache onto the media and wait. The big one.
Tell the client. Reads also reply.
The biggest step is “fsync: wait for the SATA SSD to confirm”, 72% of the write. That is the price of durability: the answer "committed" is only honest once the data survives a crash.
Updates leave garbage
Many databases (PostgreSQL, MySQL InnoDB, Oracle) use so readers never block writers: an update writes a new version of the row and keeps the old one so that running queries can still see a consistent snapshot.
The cost: dead versions pile up until a cleanup (vacuum) removes them. And every new version also needs a new entry in each index, one reason a single UPDATE can cause many page writes.
Update the rows, run vacuum, then start a long report and try again.
A forgotten open transaction is a classic production bug: it quietly stops cleanup, and the table bloats.
Four rows, one version each. Update them.
Two storage engines
A engine (Postgres, MySQL) finds the right page and rewrites it in place: one small change costs a whole 8 KB page, scattered across the disk.
An engine (RocksDB, Cassandra) just appends: new writes go into an in-memory , which is flushed as one big sorted file. Background merges files later.
Write 100-byte keys into both and compare : bytes physically written per byte you asked to store.
Neither is better. B-trees pay on every write. LSM trees pay later, in the background, and on reads (next scene).
in-place page updates
append, flush, merge
Write some keys into both engines.
The LSM bill on reads
Writes were cheap because new data lands in fresh files. But now the same key could live in the memtable, in any of several recent L0 files, or in the big L1 file. A read must check them newest to oldest until it finds the key. That is .
Add L0 files with Write, then read an old key and a missing key. Missing keys are the worst: every file must be checked. Then turn on and try again. Compact to merge the files.
Compaction trades background work for faster reads. Bloom filters skip files without even opening them.
Try reading different keys. Count how many files get opened.
How the table is laid out
A keeps each row's values side by side. That is ideal for “give me everything about order 7”. A column store keeps each column's values side by side, and compresses them well because neighbours look alike. That is ideal for “average price of everything”.
Pick a layout and a query. Highlighted cells are what the database must read. Below, scale it up to 1 billion rows × 50 columns.
Same data, same query. The layout decides whether you read one column or the whole table.
A row store has to read every column of every row to reach price: about 400 GB, 133 s even on a fast SSD. Right engine, wrong job.
Pick the engine
Seven workloads, four storage designs. You now know what each one is good and bad at. Choose.
Name the access pattern first (point lookups, write firehose, big scans, tiny hot data), then the engine follows.
An online shop's orders and payments: transactions, joins, point lookups, steady mixed reads and writes
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Real teams have rebuilt their storage over exactly these trade-offs. Four stories.
Postgres → MySQL (2016 engineering post)
Uber described moving its main store from Postgres to MySQL, partly over write amplification: in Postgres, updating a row creates a new physical row version and updates every index, and all of that is shipped to replicas. The post is a good case study in how engine internals become operational pain.
app → RocksDB (memtable → SSTables → compaction)
Meta built RocksDB, an embedded LSM-tree store tuned for flash, and used it as the base of MyRocks, a MySQL storage engine that cuts space and write amplification versus a B-tree engine. It now sits inside many databases.
messages → Cassandra-family store (LSM) keyed by channel
Discord has described storing its chat messages in Cassandra-family databases, later moving to ScyllaDB. These are LSM-tree systems, a natural fit for a firehose of appended messages read back by channel and time.
events → compressed column files → scans over billions of rows
ClickHouse is a column-oriented database used for analytics at companies such as Cloudflare. Reading just the columns a query needs, compressed, is what lets it aggregate billions of rows in seconds.
Interview angle
Seven questions, each worth 20 XP. This is where you show you understand what the database is actually doing.
Reach for the mechanism: “it appends to a log and fsyncs” sounds like someone who has looked inside.
A row is about 100 bytes. The database stores data in 8 KB pages. Fetching that one row from disk reads about how much?
Tip: press 1 to 3 to answer, Enter for the next one.
Break It
An LSM database ingests data into small L0 files and merges them in the background. has a speed limit. If writes arrive faster than it can merge, L0 files pile up.
First reads slow down, since every L0 file may need a look (the last scene). Then the engine protects itself: at 12 files it throttles writes, at 24 it stalls them completely. This is the “write stall” operators dread in Cassandra and RocksDB.
Traffic ramps from 5 to 60 MB/s. Give compaction more threads and run it again.
Fast writes are borrowed time. Background work must keep up, or the bill arrives all at once.
L0 files waiting to be merged: 0 · healthy
Press the button. Watch the L0 meter cross the throttle and stall lines.