CSE Roadmap

Common tier · about 5 hours · 8 parts

Part 8 of 8 · 2 min read

Exercises

Easy

Easy 1: How many objects (20 minutes)

10 PB of capacity, disks 40 per cent full, the same size mix as this page. How many objects, and how much metadata at 1 KB each?

Done when: you write about 67 million objects and about 67 GB.

Hint

10 PB is 10^10 MB, and 40 per cent of that, divided by 59.3.

Easy 2: Extra space (20 minutes)

Store 100 TB of data. Give the total disk for three copies and for 8 + 4 erasure coding.

Done when: you write 300 TB and 150 TB.

Hint

8 + 4 gives 12 chunks for 8 chunks of data.

Easy 3: Parts (20 minutes)

A 3.2 GB file is cut into 200 MB parts. How many parts? If part 9 fails, how much is resent?

Done when: you write 16 parts and 200 MB.

Hint

3,200 / 200.

Medium

Medium 1: Durability sum (30 minutes)

A disk fails at 2 per cent a year. With three independent copies, what is the chance that all fail, and the durability?

Done when: you write 0.02³ = 0.000008 and 99.9992 per cent.

Hint

Cube 0.02.

Medium 2: Coding limits (30 minutes)

With 4 + 2 coding, how many chunks may be lost? What is the read cost in nodes? What if 3 are lost?

Done when: you write 2 lost is fine, any 4 nodes are read, and 3 lost cannot be rebuilt.

Hint

4 + 2 gives 6 chunks, and any 4 are enough.

Medium 3: List with prefixes (30 minutes)

A bucket holds a/x/1, a/y/2, b/3 and c.txt. List the top level, then prefix a/, using / as delimiter.

Done when: you write c.txt with prefixes a/ and b/ for the first, and prefixes a/x/ and a/y/ for the second.

Hint

Names after the prefix with a slash are rolled up.

Hard

Hard 1: Draw both flows (60 minutes)

Draw upload and download with every part named on this page, and number the steps. Mark where checksums are checked.

Done when: two diagrams with at least eight parts each and checksum points.

Hint

Checksums are checked on write and again on read.

Hard 2: Compaction plan (60 minutes)

A packed file of 4 GB has 60 per cent of its objects deleted. Describe when to compact, what is copied, how the lookup table is updated and how a crash mid-way is made safe.

Done when: a numbered plan with a threshold, a copied size of 1.6 GB, and a rule that old files are removed last.

Hint

Live data is 40 per cent of 4 GB.

Hard 3: Mock interview (60 minutes)

Answer "design S3-like object storage" aloud in 35 minutes and mark yourself on the four steps. List two missed topics.

Done when: a recording, a score on each step, and two named gaps.

Hint

Use the four-step framework as a checklist.