Section 8: Never Overwrite Anything - Deep Dive: The Tablet Server Write & Read Path
Executive Summary: A tablet server never modifies a byte on disk. A write is appended to the server's single commit log on GFS (group commit within 1 ms), inserted into a sorted in-memory memtable, and acknowledged. A minor compaction writes a full memtable out as an immutable SSTable of 64 KB blocks, at the latest when its data is 4 GB (about 42 minutes) behind in the log. A read merges the memtable with every SSTable. Merging compactions keep that file count small, and only a major compaction physically removes deleted data. Because only the memtable is mutable, SSTable reads need no locks, splits share files, and deletion becomes garbage-collecting whole files. The price is about 5× write amplification, roughly 2.1 GB/s of cell disk writes.
The interviewer underlines a line from Section 6: "Memtables flush to new immutable SSTables later." "GFS is built for appends. Your API promises overwrites, deletes and versions. How do you get a mutable map out of files you won't modify?"
You: "By never modifying them. Every change is a new fact appended somewhere, and a row's current state is those facts merged newest first: a log-structured merge tree. I'll follow the crawler's 09:00:00 write to com.cnn.www through it."
Why an LSM, Not a B-tree
| Engine | Write cost | Read cost | Verdict |
|---|---|---|---|
| LSM: log + memtable + immutable SSTables (chosen) | One sequential log append; files written whole, once | Merge memtable + N SSTables | Matches GFS: large sequential writes, no in-place updates |
| In-place B-tree pages | Read-modify-write a page per update, over the network to 3 replicas | One path down the tree | Rejected: random small rewrites are what GFS does worst, and concurrent offset writes there are undefined |
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson