Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Count the subsets (20 minutes)
How many subsets of three writes can be on disk after a crash, counting none and all?
Done when: 8, of which only 2 are fully correct.
Hint
each write is either done or not, so 2 x 2 x 2.
Easy 2: Journal writes (20 minutes)
A transaction changes 4 metadata blocks. It writes one descriptor block, the 4 blocks, one commit block, and then checkpoints. How many writes in all?
Done when: 6 journal writes + 4 checkpoint writes = 10.
Hint
add 1 + 4 + 1 and then 4.
Easy 3: Replay time (20 minutes)
A journal of 128 MiB is read at 100 MB/s. How long does recovery take at most?
Done when: 1.34 s (134,217,728 / 100,000,000).
Hint
bytes divided by bytes per second.
Medium
Medium 1: Classify a state (45 minutes)
A crash left the inode and the data block written, and the bitmap not written. Say what is wrong and what could happen later.
Done when: the inode points to a block that the bitmap calls free, and the allocator may give the block to another file, so two files would share it.
Hint
look at the state DI- in the table.
Medium 2: fsck time (45 minutes)
A file system has 200 GiB of inode tables and fsck reads them at 150 MB/s. Estimate the time of the inode pass, and compare it with a journal replay of 256 MiB at the same speed.
Done when: about 1,431 s (23.9 minutes), against 1.79 s for the journal.
Hint
200 GiB divided by 150 MB/s, and 256 MiB divided by the same.
Medium 3: Run the table (45 minutes)
Compile the program of section 1. Add a fourth write J, a journal commit that makes the three others atomic, and change the table so that every subset without J is treated as "discarded, old state" and every subset with J as "replayed, new state".
Done when: a 16-row table in which every row is consistent, and a sentence on why.
Hint
with J, all of D, I and B are replayed, so all states with J are the new state.
Hard
Hard 1: Atomic replace under failure (90 minutes)
Write a program that replaces a file with the method of section 5, and a second program that kills the first with kill -9 at random times. Run 1,000 trials and check that the file always holds a whole version.
Done when: 1,000 trials with 0 files that mix versions, and a note that kill -9 does not test a power cut.
Hint
use fork and kill(pid, SIGKILL) after a random sleep.
Hard 2: Break the order (90 minutes)
Change the program of section 5 to skip the first fsync. Explain what state could remain after a power cut, with the file system in ordered mode and with data=writeback.
Done when: a paragraph that says that the rename may reach the disk before the data, which can leave an empty or stale file of the new name, and that ordered mode reduces but the application should not rely on it.
Hint
write the new data, rename, and think about which of the two reaches the disk first.
Hard 3: Journal cost (90 minutes)
A workload makes 10,000 small file creations per second, and each changes 3 metadata blocks of 4 KiB. Compute the bytes per second written to the real places and to the journal, and the write amplification of metadata.
Done when: 3 x 4 KiB x 10,000 = 122.9 MB/s to the real places (assuming no batching), 5 x 4 KiB x 10,000 = 204.8 MB/s to the journal, and an amplification of (204.8 + 122.9) / 122.9 = 2.67, with a note that batching many creations in one transaction lowers it.
Hint
a journal transaction of 3 blocks has 5 writes.