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.