File Systems as Data Structures
A file system is a data structure on a block device. It maps names to bytes, and it must stay consistent when the power fails in the middle of an update. One append touches several structures: the data block, the record that describes the file, the map of free space, and sometimes the directory. A crash can land between any two of those writes.
How a file system orders those writes, and what it promises when a write returns versus when a sync returns, decides whether a crash loses a second of data or corrupts a database. This topic treats the file system the way the rest of the book treats a hash table: as a structure with a shape, a cost and a set of guarantees, some of them weaker than engineers assume.
Names, Metadata, Blocks
A Unix-style file system has three layers. A directory maps a name to a file's metadata record, called an inode: the file's size, owner, times, permissions and a map of where its data lives. That map turns offsets in the file into blocks on the device. The blocks hold the bytes.
The name is not part of the file. It is an entry in a directory that points at the inode. That is why one file can have two names, why deleting a name does not delete a file that another name still points to, and why renaming a file inside one file system moves no data at all: it rewrites two directory entries and leaves every block where it was.
Directories and Free Space as Structures
A small directory can be a plain list of names, searched from the start. A directory with a million entries cannot, or every lookup scans a million names, the O(n) of Chapter 1 paid on every file open. Modern file systems index large directories with a hash table, from Chapter 5, or a B-tree, from Chapter 6, so a lookup costs a few block reads whatever the size.
Free space is a structure too: a bitmap with one bit per block, or a tree of free runs. Good file systems hand out long contiguous runs of blocks, called extents, instead of single blocks. A large file stored as a few long runs is read sequentially, which every rung of the storage ladder in Chapter 4 does far faster than scattered reads, and its block map stays a few entries long instead of millions.
The Crash Between Two Writes
Appending one block to a file takes three separate writes: the data into a free block, a mark in the free-space map saying the block is used, and an update to the inode's size and block map. The device completes them one at a time, in whatever order the file system issued them. A crash after marking the block but before the inode update leaks a block that nothing will ever free. A crash after the inode update but before the data leaves the file ending in whatever the block held before, which may be somebody else's old data.
The old remedy was a full consistency check at boot: walk every inode and every directory, rebuild the free-space map, and repair what does not agree. On a large volume that check could take hours, with the machine unavailable the whole time.
Journaling and Copy-on-Write
A journaling file system writes a description of its intended changes to a log first, and applies them to their real places afterwards. On recovery it replays the complete log entries and discards the incomplete one, so the metadata is never half-updated, and recovery takes seconds. This is the write-ahead idea that databases use for the same reason. In their common defaults, journaling file systems log metadata, not your file's contents: the structure survives a crash, and the last writes to the data may not.
A copy-on-write file system never overwrites a live block. It writes the new version of everything that changed somewhere free, then switches one root pointer, atomically, from the old tree to the new one. A crash leaves either the old tree or the new, never a mixture, and keeping an old root around makes a snapshot nearly free. ZFS, Btrfs and Apple's APFS work this way.
What a Write Promises
When a write returns, the bytes are in the page cache from the previous topic. Every other process sees them at once, and nothing is on the device yet. When a sync of the file returns, its data and metadata have been sent to the device and the device has been told to make them durable. A newly created file needs one more step: the directory that holds its name must be synced too, or after a crash the data can be on disk with no name pointing at it.
So the safe way to replace a file takes four steps. Write the new content to a temporary file in the same directory. Sync that file, so its bytes are durable. Rename it over the old name, which the file system does atomically. Sync the directory, so the rename itself is durable. Skip the first sync and a crash can leave the name pointing at an empty file; skip the last and the old file can come back.
The Cost of a Sync
A sync waits for the device. On a data-centre solid-state drive with power-loss protection it takes well under a millisecond. On consumer solid-state drives it takes from under a millisecond to a few milliseconds, and on a spinning disk close to ten, about one turn of the platter. A database commit can be no faster than one sync, so databases group many commits behind one: at 5 milliseconds per sync, syncing each commit caps a system at 200 commits a second, while fifty commits per sync reach 10,000.
An application that syncs every small write is capped at a few hundred writes a second. One that never syncs can lose seconds of work it has already reported as saved. The skill is placing the sync exactly where the program makes a promise. Disks, partitions and file-system types in practice are covered in Linux Deep Dive, chapters Files and the Filesystem and Storage and Disks.
A flush, in Python and most languages, moves bytes from the program's buffer into the kernel. Afterwards other processes can read them and a crash of the program loses nothing, but a crash of the machine can. Closing a file flushes it.
A sync, the system call fsync, moves the bytes from the kernel to the device and waits. Afterwards a power loss loses nothing, provided the device honours the request. Closing a file does not sync it.
- "A write that returned means the data is on disk." It means the data is in the page cache. The kernel writes it back seconds later, and a power loss in between loses it after the program has already told its user "saved".
- "A journaling file system keeps my file's contents safe in a crash." In the common default, only metadata is journaled. The file system comes back consistent, and the file can come back shorter than expected, empty, or with old contents where the last writes were.
- "Renaming a new file over the old one is atomic, so the replace is safe." The rename is atomic in the directory, but without syncing the new file first, a crash can leave the name pointing at a file whose data never reached the device, often an empty one.
- "If a sync fails, retrying it until it succeeds is safe." After a failed writeback, common kernels may mark the dirty pages clean, so the retry succeeds with the data already gone. PostgreSQL discovered this in 2018 and now stops and recovers from its own log instead of retrying.
- "A sync makes data durable on any storage." It makes the request. A drive with a volatile write cache that ignores flush commands, or a virtual disk that acknowledges early, can still lose data after the sync returned.
- Replace files with write-temp, sync, rename, sync-directory. Every shorter sequence has a crash window that leaves a truncated or empty file.
- Sync where the program makes a promise: before telling a user or a peer "saved", and nowhere else. Every sync costs a device round trip.
- Group many small durable writes behind one sync. Batching turns a few hundred syncs a second into thousands of commits.
- Treat a failed sync as lost data, not a transient error. Recover from your own log or copy, and never retry and carry on.
Knowledge Check
A program writes a record, flushes it and closes the file. The machine loses power a second later. What is guaranteed?
- The record is on the disk, because closing a file syncs it to the device
- The record is lost for certain, because it was never flushed from Python
- Nothing, since only a sync waits for the device to make that data durable
- The record is safe, because the journal holds a copy of all file contents
One sync takes 5 ms. How many durable commits per second can a database reach with one sync per commit, and with 50 commits grouped per sync?
- 5,000 and 5,000, because grouping changes latency, not throughput
- 200 and 250, because grouping saves only the extra metadata writes
- 1,000 and 50,000, because a sync overlaps with the next commit
- 200 and 10,000, because each sync now carries fifty commits
Why can a journaling file system, after a crash, return a file whose last writes are missing or wrong?
- The journal protects the structure, not the file's contents
- The journal is kept only in memory until the file is closed
- Journaling turns off the page cache, so writes land in random order
- The journal replays every entry twice, duplicating the last writes
In the safe file replace, which crash window does syncing the temporary file before the rename close?
- The window in which a reader could see half of the old and half of the new file
- The window in which the rename itself could be undone and the old file return
- The window in which the new name could point at a file whose data is not on disk
- The window in which another process could delete the temporary file first
Why does a directory holding a million files need an indexed structure rather than a list?
- A list of names cannot hold more than 65,536 entries on any disk
- The inode of a large directory cannot fit in one block without an index
- The rename of a file needs a tree, since a list cannot be changed atomically
- Every open would otherwise scan up to a million names, an O(n) search
You got correct