CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 2 of 7 · 4 min read

The crash problem

Think of moving house with a list. If you carry the boxes and then cross them off the list, a stop in between leaves a list that disagrees with the boxes. The analogy stops in one place: you can look at both and fix the list, while a disk after a crash has only its own structures to compare.

In plain words: Adding a block to a file changes three structures: the data block itself (D), the inode that now points to it (I), and the bitmap bit that marks it as used (B). These are three separate writes to three places. A power cut can stop the system after any subset of them, and the disk may also complete them in any order. Some of the resulting states are harmless. Others leave a block that no file owns (a leak), or a file that points to a block that the bitmap calls free, which may then be given to a second file.

A worked example. The program below goes through all eight subsets of the three writes and classifies the disk.

#include <stdio.h>

/* Appending one block to a file needs three writes: D (the data block), I (the inode, which now
   points to the block) and B (the bitmap bit that marks the block as used). A crash can stop the
   system after any subset of them. This table classifies the disk after each possible subset. */
static const char *outcome(int d, int i, int b) {
    if (!d && !i && !b) return "old state, consistent";
    if (d && !i && !b)  return "data written but unreferenced, consistent";
    if (!d && !i && b)  return "block marked used, no file owns it: LEAK";
    if (d && !i && b)   return "block marked used, no file owns it: LEAK";
    if (!d && i && !b)  return "inode points to a block marked free, with old contents: CORRUPT";
    if (d && i && !b)   return "inode points to a block marked free: the block may be given away again";
    if (!d && i && b)   return "metadata consistent but the file shows garbage";
    return "new state, consistent";
}

int main(void) {
    for (int s = 0; s < 8; s++) {
        int d = s & 1, i = (s >> 1) & 1, b = (s >> 2) & 1;
        printf("%c%c%c  %s\n", d ? 'D' : '-', i ? 'I' : '-', b ? 'B' : '-', outcome(d, i, b));
    }
    return 0;
}

Output:

---  old state, consistent
D--  data written but unreferenced, consistent
-I-  inode points to a block marked free, with old contents: CORRUPT
DI-  inode points to a block marked free: the block may be given away again
--B  block marked used, no file owns it: LEAK
D-B  block marked used, no file owns it: LEAK
-IB  metadata consistent but the file shows garbage
DIB  new state, consistent

Only two of the eight states are fully correct: none of the writes, and all of them. One more is harmless: the data is written and nothing points to it. Three are consistent but wrong or wasteful: a leak (two cases), and a file that shows garbage. Two are structurally corrupt: the inode points to a block that the bitmap says is free.

The key lines. Crash consistency is the problem of keeping the file system usable after such a stop. There are two ways to solve it. One is to repair after the crash (fsck, section 2). The other is to make the updates atomic with a log (sections 3 and 4).

Crash consistency

Crash consistency is the property of a file system that its on-disk structures are in a valid state after an unexpected stop, such as a power failure, whatever set of its writes had reached the disk. A file system without it needs a repair tool before it can be used again.

Example: after appending a block, a crash that left the inode written but the bitmap not written is an inconsistent state: two structures disagree.

Check yourself: 1. How many separate writes does a block append need in the model? 2. Which two subsets of the three writes are fully correct? 3. Why is "inode written, bitmap not written" dangerous?