1
How databases store data
Every database is a way of answering two questions: where do I put this, and how do I find it again? Start with the simplest answer that works, then watch it break.
Core concepts
The world's simplest database
Imagine a database that is just a file. To write, you append key,value to the end. To read, you scan the file and keep the last value you saw for that key. Writes are about as fast as disks allow, because appending is sequential I/O. Reads are terrible: every lookup is a full scan, so cost grows linearly with the data.
That append-only file is a log, and it shows up everywhere in this course: in databases, in replication, in Kafka, in Raft. It's worth getting comfortable with now.
Indexes are a trade
An index is an extra structure derived from the primary data, kept around to make reads fast. It never comes free: every write now has to update the index too. That is the first trade-off in storage design, and databases usually make you choose indexes explicitly because only you know your read patterns.
The hash index
Keep an in-memory hash map from each key to the byte offset of its latest record in the log. A read becomes one hash lookup plus one disk seek. This is essentially how Bitcask, the storage engine behind Riak, works. It's excellent when you have many writes to a modest set of keys, such as a counter per URL.
Segments and compaction
An append-only log grows forever, so you break it into segments. When the active segment reaches a size limit, close it and start a new one. In the background, compaction rewrites old segments keeping only the latest value for each key, and merges small segments together. Reads keep using the old segments until the merged one is ready, then switch over atomically.
Details that make it real
- Deletes append a special tombstone record. Compaction sees it and discards all earlier values for that key.
- Crash recovery means rebuilding the hash map. You can re-read every segment, or save a snapshot of each segment's map to disk (Bitcask calls these hint files) so startup is fast.
- Torn writes happen when the process dies mid-append. A checksum on each record lets you detect and skip the partial one.
- Concurrency is kept simple: one writer thread appends, many readers read. Segments are immutable once closed, so readers need no locks on them.
Where the hash index breaks
Two limits. All keys must fit in memory, since a hash map on disk performs badly with random I/O. And range queries are hopeless: finding every key between user:1000 and user:1999 means looking up each one individually, because a hash spreads neighbours apart.
Sorted String Tables
Change one rule: require each segment to be sorted by key. That's an SSTable, and it fixes both limits.
- Merging sorted segments works like the merge step of mergesort: read them side by side and always emit the smallest key. It's efficient even when segments are bigger than memory.
- You no longer need every key in memory. A sparse index of, say, one key every few kilobytes is enough; to find a key, jump to the nearest indexed key before it and scan forward.
- Ranges become cheap, because neighbouring keys sit next to each other. Blocks between index entries can also be compressed.
But how do you write sorted data when writes arrive in random order? Buffer them in an in-memory sorted structure (a memtable, often a red-black tree or skip list). When it grows past a threshold, write it out as a new SSTable. To survive crashes, every write also goes to a small append-only log first, which is discarded after the flush. You'll dig into this design properly in week 2.
The idea to keep: append-only writes are fast and simplify crash recovery; the cost shows up later as compaction work and as extra structures you need for reads. Almost every storage engine is a different answer to how to pay that cost.
Try it: a log with a hash index
Write some keys, overwrite a few, delete one, then compare how a read works with and without the index. Hit compact to see stale records disappear.
Log on disk (offset, record)
Hash index in memory (key → offset)
Trade-offs
| Design | Writes | Point reads | Range reads | Memory | Main cost |
|---|---|---|---|---|---|
| Plain log, no index | Fastest | Full scan | Full scan | None | Reads grow with data size |
| Log + hash index | Fast | One seek | Not practical | Every key | Key set must fit in RAM |
| Memtable + SSTables | Fast | A few seeks | Efficient | Sparse index | Compaction I/O, more moving parts |
Reading map
- DDIA, chapter 3, from the start through "SSTables and LSM-Trees".The source for this week. Stop before B-trees; that's week 2.
- Sheehy & Smith, "Bitcask: A Log-Structured Hash Table for Fast Key/Value Data" (2010).Six pages. A real engine built on exactly the hash-index design above, including hint files.
Check yourself
Why are appends faster than updating records in place?
Appending is sequential I/O, which both spinning disks and SSDs handle much better than scattered random writes. It also avoids the problem of an update being bigger than the space it's replacing, and makes crash recovery simpler: a record is either fully written or detectably torn at the end of the file.
How does a log-structured store delete a key?
It appends a tombstone record for the key. Reads that find a tombstone treat the key as absent. During compaction, the tombstone causes all older values for that key to be dropped, and eventually the tombstone itself can go once no older segment could still hold the key.
After a crash, how does a Bitcask-style store get its index back?
By rebuilding the in-memory hash map. The slow way is to read every segment from start to finish. The fast way is to load a snapshot of each segment's map (a hint file) written when the segment was closed. Checksums let it discard a partially written final record.
Why can SSTables get away with a sparse index?
Because keys are sorted. If you know the offsets of apple and banana, any key between them must sit between those offsets, so you jump to apple and scan a small block forward.
A service stores a view count per video, with huge write volume and a few million distinct keys. Which design fits, and why?
Log plus hash index. Writes are append-only and fast, a few million keys fit comfortably in memory, and reads are single lookups. You don't need range queries over video IDs, which is the main thing the hash index can't do.
Mini-build: bitkv in Go
Goal
Build a persistent key-value store with an append-only log and an in-memory hash index.
Record format
| crc32 (4B) | key_len (4B) | val_len (4B) | flags (1B) | key | value | flags: 0 = normal, 1 = tombstone
Requirements
Set(key, value),Get(key), andDelete(key), where delete writes a tombstone.- An index of
map[string]locationholding the segment ID and offset for each key. - On startup, rebuild the index by reading all segments in order, skipping a final record whose checksum fails.
- Rotate to a new segment file when the active one passes a size limit (use 1 MB so you can watch it happen).
- A
Compact()that rewrites closed segments into one containing only live keys, then swaps it in and deletes the old files.
Prove it works
- Write 100k keys, kill the process with
kill -9mid-write, restart, and confirm every acknowledged write is readable. - Measure file size before and after compaction on a workload that overwrites the same 1k keys many times.
Stretch
- Write a hint file when each segment closes and load it on startup. Time startup with and without it.
- Run compaction in a background goroutine while writes continue.