1
Price an access pattern
The crossover between sequential and random I/O for a stated seek time and bandwidth, a B-tree’s height and the I/Os a lookup and a range scan cost, and the I/O count of a workload mix on a hash index against a tree.
Course · System Design
Storage Engines and Indexes
Every storage engine is a bargain between reads, writes and space, and the bargain is countable: seeks against bytes, tree levels against fanout, bytes rewritten per byte ingested, bits per key for a Bloom filter, fsyncs per second. The course prices each structure so that “use an LSM” or “add an index” becomes a number a designer can defend.
time = seeks × t_seek + bytes/bandwidth
the pattern, not the size
height = ⌈log_B N⌉
a billion keys at B = 500 is four
k indexes ⟹ k + 1 random writes an insert
WA ≈ L·F/2 RA ≈ L before filters
bits/key ≈ log₂(1/p) / ln 2, independent of n
durable writes/s ≤ 1/t_fsync, or B/t_fsync grouped
What this course is about
- Subject
- System Design
- Lessons
- 11
- Format
- Interactive
Overview
What you will be able to do
By the end you can price a read and a write against the structure that serves them, compute the amplification an LSM pays for its sequential writes, size the filter that cancels most of it, and say what your backup schedule means in bytes and in hours.
2
Price a write
The k + 1 random writes an insert costs with k indexes, the write amplification of a levelled LSM at a given fanout, and the compaction bandwidth that amplification implies.
3
Size a Bloom filter for an engine
Bits per key at a target false-positive rate, the memory that costs for n keys, and the read amplification a filter on every level turns L into.
4
State the recovery and durability bargain
The RUM triple for three engine shapes, the durable write rate a single fsync allows and what grouping buys, and the RPO and RTO a backup schedule and a restore bandwidth imply.
Lessons
11 lessons
The physics first — what a seek costs and what a tree height is — then the write side, then the filter and the trade-off the course is named after, and last what a running engine owes its hardware: the fsync, the layout, the page cache and the recovery window.
Sequential vs Random I/OPrice the same read both ways from time = seeks × t_seek + bytes/bandwidth, and find the chunk size where its two terms balance.Not marked
The Height of a B-treeFind a tree's height by exact integer search, and turn it into the I/Os a lookup costs once the page cache is counted.Not marked
Hash vs Tree for RangesCount the I/Os a mixed workload costs on a hash index and on a B-tree, and solve for the range rate at which the ordering reverses.Not marked
The Write Cost of an IndexCompute the random writes an insert costs with k indexes, the insert rate that leaves, and the most indexes a throughput target allows.Not marked
Write Amplification in LSM TreesCompute the write and read amplification of a levelled LSM from its fanout and level count, and the compaction bandwidth they imply.Not marked
Bloom Filters: Bits per KeySize a filter from a target false-positive rate, compute the memory it costs for n keys, and the read amplification a filter per level leaves.Not marked
The RUM Trade-offCompute the read, update and memory amplification of three engine shapes from the same parameters, and the disk bandwidth each one implies.Not marked
fsync and Group CommitCompute the durable write ceiling from the fsync time, what grouping B commits buys, and the batch wait it costs.Not marked
Row vs Column StorageCompute the bytes a scan reads in each layout and the time each takes, then find the query on which the ordering reverses.Not marked
Working Set and the Page CacheCompute the page cache's hit rate from memory, dataset and skew, and the disk IOPS the misses leave behind.Not marked
RPO and RTOCompute the bytes a backup schedule puts at risk and the hours a restore takes, and invert the second to get the schedule a target allows.Not marked
Recommended background
Capacity estimation and caching and hit rates on this path; discrete mathematics: trees, independence, recursion-trees-and-amortised-analysis, big-o-notation; algebra: what-a-logarithm-is, change-of-base, the-number-e.
Practice suggestions
Convert everything into I/Os before comparing structures. Bytes and seconds make two engines look similar; I/O counts make the bargain visible, and every lab on this course reports in them.
Compute the amplification before the latency. Write amplification decides how much disk bandwidth you need and therefore whether the latency question is even interesting — an engine whose compaction cannot keep up has no steady latency to quote.
Take “Working Set and the Page Cache” as a callback rather than as new material. It is the cache of Caching and Hit Rates under different names, and the point of it is that you already know how to size one.
What it does not cover
Isolation levels, query planning, and any particular product’s internals. The structures here are shapes, and every figure is a ratio rather than a benchmark.
The derivation of the Bloom filter’s false-positive rate and its optimal k. Both are stated in “Bloom Filters: Bits per Key” and derived in “Bloom Filters” on the Algorithms path, which owns them along with the rule that a filter supports no deletion.
Compression algorithms. The ratio is an input on this course; the break-even it feeds — whether the processor time a codec costs is worth the bytes it saves — is “Compress or Not” in Scaling Laws and Cost.