Storage engines

  • Lesson 11 of 40
  • 14 min
  • Intermediate
  • 13 steps

From “saved” to disk: how an engine splits data between memory and disk, and why each design favours either reads or writes.

Writes lost in a crash
0
Writes per second
200,000
fsyncs per second
5,000
Reads per lookup
1
Columns read
—
AppAppMemoryRAMMemoryWAL logsequentialWAL logData file · 8 KB pagesSSTable 1 (oldest)SSTable 2SSTable 3SSTable 4 (newest)AnalyticsqueryAnalytics queryColumn storepages in use · nanosecondspower cut · 4 s losttorn pagefsync before “saved”1 fsync for 8 transactionsThe durability dialfsync on every commitloses nothing · slowestgroup commitloses nothing · shared fsyncfsync every 100 msfast · loses up to 100 msno fsync of its ownfastest · loses secondsexample valuescheckpoint: writing pagesold log discarded4 page readsB-tree · one copy per row100%200,000 writes/sfull of changed pagessorted memtableflush: one sequential writenewestSSTables · oldestmemtable: GET user:42 · not herefilter: not herefilter: not herefilter: not heremaybe → foundsorted memtablemerged · newest values onlynewestflushfiles never modifiedB-tree or LSM-treeB-treeLSM-treewritesscattered pagessequentialreadsfew pagesfiles + filterspacepages with gapscompactbackgroundcheckpointscompactionrows: reads all 40 columnsreads 1 column of 40sorted memtablenewestflush
  • request
  • response
  • batch
  • waiting in queue

Step 1 of 13

Concept

Memory and disk

A database server keeps data in two places. Memory (RAM) answers in nanoseconds, but it is wiped when the process dies or the power goes. Disk keeps everything through an outage, but confirming that data is physically written (an fsync call) costs thousands of times more.

The storage engine is the part of the database that decides what goes where, and when. Every design in this lesson answers the same question: how do I get the speed of RAM without giving up the safety of disk?

Step 2 of 13

Problem

Fast but fragile: memory now, disk eventually

The simplest engine changes the page in memory, answers “saved” right away and copies changed pages to disk every few seconds in the background. It writes very fast: in this example, 500,000 writes per second.

Until the power goes. Everything changed since the last copy is gone, including orders you already confirmed to the customer. With a copy every 4 s, that is 4 × 500,000 = 2 million lost writes. And the page being written at that very moment is left half done: a torn page that can no longer be trusted.

What changed

  • Answer “saved” as soon as memory changes
  • A power cut wipes the last 4 s of writes
  • One page is left half written

Step 3 of 13

Solution

Write it down first: the write-ahead log

Writing every changed page to disk before answering would be safe but painfully slow: rewriting 8 KB somewhere on the disk to change a 100-byte row.

Instead, the engine describes the change in a few bytes, appends it to a log file and forces it to disk with fsync before answering. This is the WAL (write-ahead log). Appending to the end of a file is about the cheapest thing a disk can do. Pages are changed in memory and copied to disk later, without hurry.

With a 0.2 ms fsync per transaction (an example value for an SSD), the ceiling is 1 s ÷ 0.2 ms = 5,000 writes per second. Your numbers will differ; the ratio between designs holds.

What changed

  • WAL log: append, then fsync
  • “Saved” only once the log entry is on disk
  • Pages are copied later, in the background

Step 4 of 13

Trade-off

Case: how safe is “saved”?

One fsync per transaction caps writes at 5,000 per second. With thousands of commits a second, that step becomes the bottleneck.

Group commit eases it without losing safety: transactions arriving at almost the same time share a single fsync. With 8 per group: 5,000 fsyncs/s × 8 = 40,000 writes per second.

Beyond that there is a dial: many databases let you fsync on a timer (every 100 ms, every second) instead of on every commit. Throughput multiplies, in exchange for losing the last moments of “saved” writes if the power goes.

What changed

  • Group commit: one fsync for 8 transactions
  • Writes: from 5,000 to 40,000 per second
  • Optional: fsync on a timer, faster but may lose data

Step 5 of 13

Technique

The log can't grow forever

If nobody trims it, the log grows without limit, and recovering from a crash would mean rereading days of changes. So every few minutes the engine takes a checkpoint: it copies every changed page to the data file, notes “up to here, everything is in the pages” and discards the older log.

After a crash, only the log written since the last checkpoint needs rereading: from a few seconds to a few minutes of work.

What changed

  • Checkpoint: copy changed pages out and trim the log
  • Recovery rereads only the log since the checkpoint

Step 6 of 13

Concept

The classic engine: B-tree pages, changed in place

What we just built is the design of most relational databases. Data lives in fixed-size pages organised as a B-tree; in some engines the table itself is that tree. To change a row, the engine finds its page and modifies it in place, with the log as a safety net.

It shines at reading. In a 4-level tree (example), any row is 4 page reads away, almost always already in memory, and neighbouring keys live on neighbouring pages, so scanning a range is cheap.

What changed

  • Reads: 4 pages, mostly from memory
  • Writes: find the page and change it in place

Step 7 of 13

Problem

Case: a flood of writes

Now the workload changes: sensor readings, chat messages, clicks. 200,000 small writes per second (example), each with a different key, so each lands on a different page. Memory fills with changed pages, and every one must eventually go back to its own spot on disk: a whole page for a few changed bytes.

The log copes easily, because it is sequential. The scattered page writes don't: checkpoints fall behind and throughput stalls at whatever the disk manages in random writes, about 40,000 per second in this example. The other 160,000 don't fit.

What changed

  • Workload: 200,000 small writes/s on scattered keys
  • Memory is full of changed pages; checkpoints fall behind
  • Throughput stalls at 40,000 writes/s

Step 8 of 13

Solution

Never in place: the LSM-tree

Another design drops the idea that each row has a fixed home. A write goes to the log and into a sorted in-memory structure, the memtable. That's it: there is no page to find.

When the memtable fills up, it is written to disk in one go as a sorted, immutable file, an SSTable, and a new memtable starts. Every disk write is sequential. This is the LSM-tree (log-structured merge tree), common in databases built for heavy writing.

The log still does 5,000 fsync calls per second; with more load, each group gathers more transactions: 200,000 ÷ 5,000 = 40 per fsync.

What changed

  • Pages in memory → sorted memtable
  • A full memtable is written out as one sorted file
  • Every disk write is sequential: 200,000/s

Step 9 of 13

Problem

Case: where is my key?

Now reading is the hard part. The latest value of a key may be in the memtable or in any SSTable. You check from newest to oldest, and a key written long ago (or one that doesn't exist) would mean checking every file.

Two tricks fix it. Each SSTable carries a Bloom filter, which answers “definitely not in here” without touching the disk, and a small index of where each key range starts. So a typical lookup reads a single file.

What changed

  • A lookup might check every SSTable
  • A Bloom filter and a small index per file
  • Most lookups read a single file

Step 10 of 13

Technique

Compaction: tidying up in the background

Files pile up, and older ones are full of values that have since been overwritten or deleted. A background process keeps merging them: it reads several sorted files, writes a new one that keeps only the latest value of each key, and deletes the originals.

That is compaction. It limits how many files a read has to look at and frees space. It is also the price of the design: every byte is rewritten several times over its life, and compaction competes with real traffic for the disk.

What changed

  • Compaction merges three files into one
  • Overwritten values and tombstones that hide nothing are dropped
  • Fewer files to check on every read

Step 11 of 13

Trade-off

B-tree or LSM?

Lots of reads, range queries and transactions: a B-tree. Huge numbers of writes and enormous data that mostly grows: an LSM-tree.

It isn't black and white: some modern SQL databases run on an LSM engine, and B-tree engines handle writes very well on a good disk.

Step 12 of 13

Concept

Case: rows or columns?

One axis left. Both engines so far keep each row together: perfect for reading or changing whole records. But an analyst runs SELECT SUM(price) FROM orders over 2 billion rows, and a row store has to read all 40 columns of every row to add up just one.

A column store keeps each column in its own file. The query reads only price, one fortieth of the data: if the table takes 4 TB (example), it reads about 100 GB instead of 4 TB. And since similar values sit together, they compress much better. That is how analytics warehouses scan billions of rows in seconds.

What changed

  • Analytics query: SUM(price) over 2 billion rows
  • Row store: every column of every row is read
  • Column store: 1 column of 40

Step 13 of 13

Summary

Recap

Memory is fast and forgetful; disk is durable and slow. The storage engine bridges them.

The WAL makes “saved” true: append, fsync, then answer.

How often you fsync is a durability dial: know where yours is set.

B-trees change pages in place: predictable reads, scattered writes.

LSM-trees only append: fast writes, paid for with compaction and harder reads.

Column stores serve analysis by reading only the columns a query asks for.

You will learn

  • What it takes for “saved” to survive a power cut
  • fsync, group commit and checkpoints
  • How a B-tree engine reads and writes
  • Memtable, SSTables, Bloom filters and compaction in an LSM-tree
  • When to pick a B-tree or an LSM, rows or columns