How databases write data: logs, indexes, and storage engines
I used to think of a database as a place where data simply lives. This part of the book made the machinery clearer: a database has to accept writes, find values later, survive a crash, and avoid making every read painfully expensive. The storage engine is the component that does that work.
A database has two jobs
At its simplest, a database stores information when the application writes it and returns the right information when the application asks for it. The hard part is making both operations fast enough as data grows. This is why storage engines matter when choosing or tuning a database, even though application code usually works through a higher-level query API.
APPLICATION
write(key, value)
read(key)
STORAGE ENGINE
-> persist the write
-> locate the value later
-> recover after failure
The simplest storage engine is an append-only log
Imagine a small key-value store. Every write appends one record to the end of a file: first the key, then the value. Updating a key does not overwrite the old record. The newer record becomes the current answer. In this context, a log means an append-only sequence of records. It does not mean an application log file.
Appending is attractive because it turns each write into a sequential disk operation. Sequential writes are generally simpler and faster than repeatedly changing data in the middle of a file. The downside is obvious: without extra help, reading a key means scanning the whole log and keeping the last value seen for that key.
SET cat = black
SET dog = brown
SET cat = white
GET cat
-> scan records
-> newest cat record wins
Indexes trade write work for fast reads
An index is extra metadata that helps the database find data without reading every record. For the append-only log, the useful index is an in-memory hash map from each key to the byte offset of its newest record in the file. A read becomes: look up the key in memory, seek to that offset on disk, and read the value.
The index is derived from the primary data. That makes it expendable in principle because the database can rebuild it, but it also makes every write more expensive because the index must stay current. This is the central index trade-off: indexes speed up reads while consuming memory, disk space, and write work. There is no reason to index every possible field. The right indexes follow the queries the application actually needs.
WITHOUT AN INDEX
GET key -> scan many records
WITH A HASH INDEX
key -> byte offset -> value
fast lookup, index kept in RAM
This approach is close to Bitcask, a storage engine designed for workloads with a modest number of distinct keys that are updated often. Values can remain on disk, but all keys and offsets must fit in memory. That makes it a poor fit when the keyspace is larger than available RAM.
Old values need compaction
An append-only log accumulates stale records. If a key changes ten times, nine old values are no longer useful for normal reads. Storage engines deal with this by splitting the log into segment files. When a segment reaches a chosen size, the database closes it and begins a fresh segment.
In the background, compaction rewrites a segment so it contains only the newest value for each key. Compaction can merge several segments at once. During a merge, the database keeps the newest copy of each key and discards older copies. Once the replacement file is ready, reads switch to it and the old segments can be removed.
OLD SEGMENTS
cat -> black
cat -> white
dog -> brown
COMPACTED SEGMENT
cat -> white
dog -> brown
Deleted keys also need a record. A tombstone marks the deletion so that compaction knows not to resurrect an older value from another segment.
Making the idea survive real failures
The toy design becomes a usable storage engine only after a few practical details are added.
Each record should use a binary encoding with length information, so the database can find record boundaries without relying on a delimiter that might appear inside the value. A checksum lets recovery detect a partly written or corrupted record after a crash. The database can rebuild indexes by scanning segment files at startup, but it can also write index snapshots to make recovery faster.
A common concurrency design allows many readers but only one writer. The writer appends to the current segment while readers use immutable older segments. That avoids coordination around files that are changing. The database can create a merged replacement file first, then atomically switch readers to it before deleting the old files.
ONE WRITER
-> append to active segment
MANY READERS
-> read immutable segments
BACKGROUND WORK
-> compact and merge
-> switch files when replacement is ready
Why append-only designs are useful
Append-only files are easier to reason about than in-place updates. They turn writes into sequential I/O, avoid overwriting the only copy of a value, and work well with immutable files. Compaction eventually reclaims the space consumed by obsolete records, but it also means the system must manage temporary duplication and background work.
APPEND-ONLY WRITES
+ sequential I/O
+ simple crash story
+ immutable old files
THE COST
- stale data until compaction
- hash index must fit in RAM
- no efficient range scans
The last limitation matters. A hash index is excellent for finding one exact key, but it cannot efficiently answer a question such as "show every key between A and Z." The next storage design solves that by keeping keys sorted in files called SSTables. That leads into LSM-trees.
What I will carry forward
Database performance is not one number. Every useful data structure moves work somewhere else. An index makes reads cheaper but makes writes and storage more expensive. Append-only logs simplify writes but require compaction. A hash index is great for exact lookups but not ranges. The useful question is always: which operations does this application perform most often, and where should the database pay the cost?
These are my personal learning notes from Designing Data-Intensive Applications by Martin Kleppmann.