12 — Storage engines
A database’s storage engine decides how bytes are laid out on disk. It determines what’s fast, what’s slow, and how the system behaves as it grows.
Starting simple: an append-only log
The simplest database is a file. Writing appends a line, and reading scans for the last match.
Writes are excellent, because appending is sequential. Reads are terrible, because they scan the whole file. A hash map in memory, from each key to its position in the file, makes reads fast, and this is a real design, used by Bitcask. Its limit is that all keys have to fit in memory, and range queries don’t work.
The two main engines both solve this, in different ways.
B-trees
A B-tree keeps data in fixed-size pages, usually 4 to 16 KB, arranged as a shallow, balanced tree. Inner pages hold keys and pointers to children, and leaf pages hold the data. Each page can have hundreds of children, so even billions of rows need only about four levels.
Reading walks from the root to a leaf, and the top levels are usually cached.
Writing updates a page in place. If a page is full, it splits into two, and its parent is updated.
In-place updates are risky: a crash partway through could leave a page half-written. So B-trees depend on a write-ahead log. Every change goes to the log first. PostgreSQL and MySQL’s InnoDB both work this way.
LSM trees
A log-structured merge tree takes the opposite approach: never update in place.
- Writes go to the write-ahead log, and an in-memory sorted table, called a memtable.
- When the memtable is full, it’s written to disk as an immutable sorted file, an SSTable.
- Over time, background compaction merges files, dropping overwritten and deleted data.
A read checks the memtable, then SSTables from newest to oldest. A deleted key is marked with a tombstone, which is removed later by compaction.
RocksDB, Cassandra and ScyllaDB use LSM trees.
Bloom filters
Checking every file for a missing key would be slow. A Bloom filter is a compact structure that can say “definitely not here” or “probably here”. It’s a bit array with several hash functions. Adding a key sets several bits, and a lookup checks them. If any bit is clear, the key is absent.
A simulation at 10 bits per key with 7 hash functions measured a false positive rate of 0.81%, against a theoretical 0.82%. So about 1.25 bytes per key avoids 99% of needless disk reads.
Amplification
Engines trade off three costs (TiKV):
| Cost | Meaning |
|---|---|
| Write amplification | Bytes written to disk per byte of user data |
| Read amplification | Disk reads per query |
| Space amplification | Disk used per byte of data |
Improving one tends to cost another.
| B-tree | LSM tree | |
|---|---|---|
| Writes | Rewrites pages | Cheap and sequential, then compaction |
| Reads | Predictable | May touch several files |
| Range scans | Good | Good, but has to merge files |
| Space | Pages have free space | Depends on compaction |
| Hidden risk | Page bloat | Compaction falling behind |
The usual summary is that B-trees suit read-heavy workloads, and LSM trees suit write-heavy ones. Real results depend on hardware and configuration, so a benchmark on real data is better than a rule of thumb.
Compaction strategies
Levelled compaction keeps files sorted into levels with little overlap, which gives better reads and space use, and writes more. Size-tiered compaction merges files of similar size, which writes less, and uses more space and reads more. Compaction that falls behind is a classic production failure: reads slow down, and disk use climbs.
Durability details
A write isn’t durable until fsync returns (chapter 2). Some configurations acknowledge writes before that, which is faster, and risks losing recent data on a power failure. Replication changes the picture too: if data is on three machines, some systems accept weaker local durability, on the assumption that all three won’t fail together.
Row and column storage
The engines above store rows. Column stores keep each column separately, which suits analytics.
| Row store | Column store | |
|---|---|---|
| Good for | Fetching whole records | Aggregating a few columns |
| Writes | Efficient one at a time | Best in batches |
| Compression | Moderate | Excellent |
| Examples | PostgreSQL | ClickHouse, BigQuery |
A query that averages one column across a billion rows only needs that one column, and similar values next to each other compress very well. This split is the basis of the divide between OLTP, for transactions, and OLAP, for analytics.
Block, file and object storage
| Type | Interface | Good for | Example |
|---|---|---|---|
| Block | Raw disk blocks | Databases | EBS |
| File | Paths and directories | Shared files | NFS |
| Object | Whole objects by key | Images, backups, data lakes | S3 |
Object storage is very durable and cheap, with a simple interface. It’s the standard home for large files. Applications store a key in the database, and the bytes in object storage. Many modern databases also tier older data onto it.
Search and specialized indexes
An inverted index, as used by Elasticsearch, maps each word to the documents that contain it, which makes full-text search fast. Vector indexes find similar items, using approximate nearest-neighbour methods. Data for these is usually copied from the main database, through a change stream (chapter 13), so they lag slightly behind it.
Backups
Replication isn’t a backup. A mistaken DELETE replicates immediately. Real backups need point-in-time recovery, usually a snapshot plus the write-ahead log. An untested backup can’t be relied on, so restores need regular testing.
The takeaway
B-trees update in place and read predictably. LSM trees append and merge, which helps writes, and needs Bloom filters and compaction to keep reads fast. Every engine trades write, read and space cost against each other, and picking the right one starts with knowing the workload.