CSE Roadmap

Common tier · about 3 hours · 8 parts

Part 8 of 8 · 3 min read

Exercises

Easy

Easy 1: Levels of a tree (20 minutes)

Pages hold 200 references. How many data pages can 2, 3 and 4 levels of index pages address? With 4 KB per page, how many bytes is that?

Done when: three counts and three sizes in a sensible unit.

Hint

References per page, raised to the number of levels.

Easy 2: Merge two files (20 minutes)

Older: b=2, d=4, f=6. Newer: a=1, b=20, d=DELETED, g=7. Merge them by hand and write the result.

Done when: the merged file and the rule used for each key.

Hint

The newer file wins, a tombstone removes the key.

Easy 3: Which engine (20 minutes)

Pick B-tree or LSM-tree and say why: a banking ledger with strict rules, a stream of sensor readings, a user table with many lookups, a chat message log.

Done when: four picks, each with a reason from the table in section 6.

Hint

Think about writes against reads and about strict rules.

Medium

Medium 1: Split a page (30 minutes)

A leaf holds at most 5 keys: 3, 7, 11, 15, 19. Insert 9, then 13, then 17. Show the pages after each insert and count the page writes.

Done when: the pages after each step and a total write count.

Hint

A split writes the two leaves and the parent.

Medium 2: Write amplification (30 minutes)

An app writes 12 MB per second. A B-tree engine writes 4 KB pages for 150-byte changes, plus the log. An LSM engine has a write amplification of 12. Compute the disk write rate for each. Which one exceeds a disk limit of 300 MB per second?

Done when: two rates in MB per second with the working, and a verdict.

Hint

Page bytes per change ÷ change size gives the page factor.

Medium 3: Bloom filter savings (30 minutes)

An LSM-tree has 10 files. 40 percent of lookups ask for keys that do not exist. Filters give false alarms 2 percent of the time. For 5,000 lookups per second, count the file reads with and without filters, assuming that an existing key is found on average after 3 file reads.

Done when: two totals in reads per second, and the saving.

Hint

Absent keys cost 10 reads without filters. Present keys cost 3.

Hard

Hard 1: Will compaction keep up (45 minutes)

An LSM database receives 25 MB per second of writes. Disk bandwidth is 500 MB per second, of which 20 percent is reserved for reads. Leveled compaction has write amplification of 18, size-tiered 7. Check each. At what write rate does each stop keeping up? What would you do if writes grow by 50 percent?

Done when: two verdicts, two break-even rates and a plan.

Hint

Available bandwidth = 500 × 0.8. Required = write rate × amplification.

Hard 2: Predict the lookup cost (45 minutes)

A B-tree index for 2 billion rows has 120 rows per leaf and a branching factor of 400. Work out the number of levels. Assume the root and level 2 are in memory, each disk read is 0.1 ms. Find the lookup time. Then compare with an LSM-tree with 6 files, Bloom filters with 1 percent false alarms, and an existing key found in the third file.

Done when: a level count, two lookup times and a comment on what drives the difference.

Hint

Levels = enough powers of 400 to cover 2 billion ÷ 120 leaf pages.

Hard 3: Pick an engine for three systems (50 minutes)

Choose an engine and justify it for: (a) a payment ledger at 1,500 writes per second with range locks, (b) a metrics store at 400,000 points per second, (c) a product catalogue of 20 million items read 30,000 times a second. For each, state the main risk of your choice and how you would measure it.

Done when: three choices, three risks and a measurement for each.

Hint

Match write volume and locks to the engine strengths.