CSE Roadmap

Common tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Write cost (20 minutes)

Find the LFS write cost for u = 0.5 and u = 0.75.

Done when: 4 and 8.

Hint

2 divided by (1 - u).

Easy 2: Blocks in the tree (20 minutes)

A COW tree has fanout 4 and three levels of pointer blocks above the data. How many blocks does it hold if there are 64 data blocks?

Done when: 85 (1 + 4 + 16 + 64).

Hint

add the blocks of each level: 1 + 4 + 16 + 64.

Easy 3: One update (20 minutes)

How many blocks does one data-block update write in that tree, and how many blocks of the old version stay in use by the new one?

Done when: 4 written, and 81 shared.

Hint

the changed leaf plus the three pointer blocks on its path.

Medium

Medium 1: Small-file batch (45 minutes)

With the drive of Level 8 (13.2 ms per random block, 13.17 ms for one seek and rotation, 100 MB/s), compare creating 50 files at 3 random writes each with one batched segment of 150 blocks of 4 KiB.

Done when: 1.98 s against 13.17 ms + 6.14 ms = 19.3 ms, a ratio of about 103.

Hint

50 x 3 x 13.2 ms for in place. The segment is 150 x 4,096 bytes.

Medium 2: Bigger fanout (45 minutes)

A COW tree has fanout 512 and 3 levels of pointer blocks. How many data blocks can it address, and how many blocks does one update write?

Done when: 134,217,728 data blocks (512^3) and 4 writes.

Hint

512 x 512 x 512 data blocks.

Medium 3: Run the model (45 minutes)

Compile the program of section 4. Change the update to touch leaf 0, then leaf 63, and print the counts.

Done when: the same 4 new blocks each time, and a sentence on why the position of the leaf does not change the cost.

Hint

the path from root to any leaf has the same length.

Hard

Hard 1: Three versions (90 minutes)

Extend the program to make a second update of another leaf from version 1, so that three versions exist. Count the distinct blocks in all three, and the blocks that only version 0 uses.

Done when: 85 + 4 + 4 = 93 distinct blocks, and 4 blocks that only version 0 uses, which deleting version 0 would free.

Hint

the new root of version 2 copies the path of the second leaf from version 1.

Hard 2: A cleaner policy (90 minutes)

A log has 100 segments. Half are 90% live and half are 10% live. Compare the write cost of cleaning the 10% ones and the 90% ones. Say what policy a cleaner should use, and why a policy that looks only at u can still do badly.

Done when: 2 / 0.9 = 2.22 against 2 / 0.1 = 20, the policy "clean the emptiest first", and a note that cold, rarely changed data can make a segment look full while it never changes.

Hint

compute both formulas, then think about data that is full but cold.

Hard 3: Journal or COW (90 minutes)

A system updates 1,000 random blocks of a huge file each second. Estimate the metadata writes per second for an ext4-style journaled system (the data block, 5 journal writes and 3 checkpoint writes for each update, with no batching), and for a COW tree of height 3 (the data and 3 pointer blocks), and say which writes more and by how much.

Done when: 9,000 writes per second for the journal and 4,000 for COW, so the journal does about 2.25 times as many, with a note that batching changes both.

Hint

journal writes per update: 1 + 5 + 3 = 9.