Chapter 07 · 12 minutes

The trade-offs, and real databases

Stash is fast, simple and crash-safe. It also keeps every key in memory and cannot answer "all keys between A and B". Meet the designs that make different trades.

Goal

Measure Stash's biggest limit, then place it on the map next to LSM trees and B-trees.

Every key lives in memory

uv run python -m stash memory

the index needs about 173 bytes of RAM per key
  1,000,000 keys: 173 MB
  100,000,000 keys: 17.3 GB

That is a Python dictionary of 13-character keys pointing at two numbers. A version in C would be leaner, but the shape stays: RAM grows with the number of keys, whatever the size of the values. Bitcask is happy with many large values and few keys, and unhappy with billions of small ones.

The second limit: the index is a hash map, so keys have no order. "Every key from acorn:100 to acorn:200" means looking at every key.

The map

Design	Writes	Reads	Used by
Log + hash index	append to the log	one seek; every key in memory	Bitcask, Stash
LSM tree	log, then a sorted table in memory, flushed to sorted files	check memory, then files, newest first	RocksDB, LevelDB, Cassandra
B-tree	change pages in place, after a log	walk a sorted tree of pages	SQLite, Postgres, MySQL

All three use the idea from chapter 02. An LSM tree keeps a log so the sorted table in memory survives a crash. A B-tree database writes every change to a write-ahead log first, then updates its pages later. If the plug comes out mid-update, the log replays the change on restart, just as Stash replays its log.

What the others buy with their extra complexity:

Sorted keys, so range queries are cheap.
Indexes that live on disk, so data can be far bigger than RAM.
Compaction or page reuse that runs in the background, without stopping writes.

What you built

In seven short chapters:

an append-only log with a record format you can read byte by byte
an in-memory index that makes reads one seek
crash recovery that keeps every finished write, tested at every byte
a clear line between a torn write and corruption
three durability levels, measured, and group commit
crash-safe compaction with an atomic rename

That is most of what "durable" means in any database. Next time a database's docs mention a WAL, fsync, checksums or compaction, you have built each one.

Check it works

memory prints the cost per key, and you can say why it matters more than value size.
You can name one database for each row of the map.

Exercise

Add keys(prefix) to Stash, returning every live key that starts with a prefix, in order. Time it with 1,000,000 keys. Then explain why an LSM tree or a B-tree can answer the same question without looking at every key.

More to try

Read the original Bitcask paper, "Bitcask: A Log-Structured Hash Table for Fast Key/Value Data". It is six pages long, and you have already built most of it.
Run SQLite with PRAGMA journal_mode=WAL and find its -wal file next to the database while it is open. What do you expect it to contain?