CSE Roadmap

Common tier · about 3 hours · 7 parts

Part 6 of 7 · 3 min read

In practice

In practice

Think of choosing between a filing cabinet and a diary. The cabinet is quick for small changes in known places, and a mess after a crash. The diary is safe and tidy to write, and slow to look through when old entries pile up. The analogy stops in one place: file systems blend the two, taking the safe write path of the diary and keeping an index like the cabinet's.

In plain words: Pure log-structured disk file systems are rare, since the cleaning cost hurts under random overwrites. The ideas live on in other places. Btrfs and ZFS are copy-on-write trees with checksums, snapshots and built-in volume management. F2FS is a log-structured file system designed for flash, which matches the garbage collection of the drive. Inside every SSD, the flash translation layer (Level 8, page 3) is itself a log with a cleaner. The costs are space for old versions, a fragmented layout after many random overwrites of a large file, and a more complex free-space accounting.

A worked example (made up to show the idea). A database file of 1 GiB is overwritten at random, 4 KiB at a time, in a COW file system. Each overwrite lands in a new place. After 100,000 overwrites (390 MiB), about a third of the file's blocks have moved, and a sequential read of the file now jumps between the new and the old places. That is the fragmentation cost. On a flash disk the jump costs little, and on a spinning disk it can cost a seek for each jump.

The key lines. Some systems allow a file to opt out of copy-on-write, or use cp --reflink to make a copy of a file that shares its blocks until one of them changes. Those features are the same technique as the snapshot of section 4, at the level of one file. The test machine here has only ext4, so none of them was run.

Interview angle

A common question is "What is the difference between a journaling and a copy-on-write file system?" A good answer says that journaling writes a change twice (log, then place) and overwrites in place, while copy-on-write writes once to a new place and switches a root pointer, which gives atomic updates and cheap snapshots at the cost of fragmentation and space.

Check yourself: 1. Why is a database a hard case for copy-on-write? 2. Which flash component is itself a log with a cleaner? 3. What does cp --reflink share between the original and the copy?

Words you will meet

Word Meaning
Segment A large piece of the log that is written at once.
Inode map Table of the current disk address of each inode.
Checkpoint region Fixed place with the addresses of the latest map pieces.
Cleaner Reclaims segments by copying their live blocks.
Snapshot An old version of the tree that is kept.

Quick notes

  • Update in place costs several random writes for one change. Writing to new space batches them into one sequential write.
  • An LFS writes data and metadata together in segments, and finds inodes through an inode map.
  • Cleaning copies live blocks out of a segment. Write cost = 2 / (1 - u).
  • A copy-on-write tree copies the path to the root. One changed data block costs height + 1 writes.
  • A snapshot is an old root. It shares all unchanged blocks.
  • COW gains atomic updates and snapshots, and pays in fragmentation and space.