The rescue operation

Chapter 39 ended with all our carefully counted page views living in the memory of a process, where they vanish as soon as the power goes off. The memory of flip-flops we built in Chapter 31 remembers only while current flows. To outlast a shutdown, data is put where it stays without electricity: on a magnetic disk or in flash memory. But putting it there is not enough. The power fails in the middle of a write, disks break, bits go bad on their own, and people make mistakes more often than hardware does. This chapter is a drill: five disasters, and after each one we look at what survived and what should have been done for everything to survive.

Pixar, 1998. The film disappears

The film, as it happens, was later largely remade anyway, but by the studio’s own decision. In the fourth drill we’ll need two lessons from this story. A backup that nobody checks may have stopped working long ago. And what saves you is the copy that lies far from the scene of the accident. But first, where and how does data lie on a disk at all?

Where the data lives

To a program, a disk looks like a huge array of numbered blocks, like the memory of Chapter 14, except that it has to be read and written in whole blocks, usually 4,096 bytes each. How the disk works inside doesn’t matter to the program. In a hard disk the blocks are magnetized patches on spinning platters: to read one, the head has to travel to the right track and wait for the right spot to float underneath. That takes milliseconds, an eternity by the processor’s standards, as we worked out in Chapter 34. In a solid-state drive the blocks live in flash memory, nothing moves, and a block is read about a hundred times faster. Flash memory has a temper of its own, though: it can be erased only in large chunks, and each cell survives a limited number of rewrites. So the SSD’s controller keeps its own table, “block number as the program sees it → place on the chip,” and spreads the writes evenly over all the cells. It is the same idea as the page table of Chapter 38.

A file always occupies a whole number of blocks, even if it holds a single byte.

One byte takes up 4,096 bytes, and 4,097 bytes take up 8,192: a second block has been started, and all of it is ours. The last line is a confession. When this chapter was written, the sandbox’s /tmp directory was a tmpfs, a file system that lives in RAM. Everything your cells write there disappears along with the sandbox. For this chapter’s experiments that is even convenient: our disasters will be make-believe, and the laws that blocks and files live by stay the same.

The table of contents: the file system

An array of blocks is not yet a collection of files. Something has to record which blocks belong to which file, what the file is called, who owns it and when it was last changed. That is the job of the file system. In Unix every file has an inode, an index node: a record with the file’s size, owner, permissions, modification time and the list of blocks that hold its contents. The inodes are numbered. Dennis Ritchie later admitted that he didn’t know for certain where the i came from either: “‘Index’ is my best guess,” since the number of an inode served as an index into the array of inodes on the disk.

The inode holds no name. Names live in directories, and a directory is a special file whose contents are a table, “name → inode number.” Directories sit inside directories, and the result is a tree from Chapter 17: the path /tmp/film/woody.txt is a descent from the root along branches named tmp, film and woody.txt. And since a name is only a line in a table, one inode can have several names.

Both names lead to the same inode, and its count of names is 2. The rm command erases a line in a directory, not a file, and decreases the count. As long as the inode has names left, its contents live on; when the count reaches zero, the file system marks the inode and its blocks as free. The bytes themselves usually aren’t wiped: they stay where they are until something new is written in their place. That is why deleted files can sometimes be recovered with special programs, and why the first thing Pixar did was shut down the servers: any new write could land on top of the erased scenes. You can use this too: if you notice you’ve deleted something you need from a flash drive, don’t write anything to it.

Drill 1. The power goes out

Scenario one: a program is saving a document, and halfway through the write the power fails. What ends up on the disk?

Writing a file takes several actions. open(path, "w") truncates the file to zero at once: the old version is gone, and the new one doesn’t exist yet. Then the new contents go out piece by piece. And even what has been “written” isn’t necessarily on the disk: write returns as soon as the kernel has put the bytes into its cache in memory, and they go to the disk later, whenever it suits the kernel. This is the cache of Chapter 34 again, this time between memory and the disk. We can’t switch off the power in the sandbox, but we can do nearly the same thing: kill a process in the middle of a write. A child process saves a new version of a scene, and after 0.05 seconds its parent kills it with a signal that can’t be caught.

The naive save left a stump on the disk: no old lines at all, and as many new ones as had been written (when this chapter was written, 500 out of a thousand, and sometimes 400, one piece fewer). Both versions are lost. The safe save left the old version untouched: the crash hit the temporary file, and that one is no loss.

The recipe for a safe save is worth remembering; text editors, databases and installers all use it. Write the new version into a temporary file in the same directory. Call os.fsync, which doesn’t return until the kernel has sent the file’s bytes to the disk. Only then does os.replace rename the temporary file so that it takes the old one’s place. What makes the recipe work is an atomic rename: within one file system, renaming is a single change to one line of a directory, and anyone who opens the file sees either the whole old version or the whole new one. After a crash the disk holds the old file and perhaps an unfinished temporary one, but never a stump. To be completely sure, careful programs also call fsync on the directory itself, so that the rename reaches the disk as well.

Killing a process and cutting the power are not the same thing. When a process dies, the kernel is still alive, and everything it has taken into its cache will reach the disk sooner or later. When the power goes, the kernel’s cache dies too. So when a process is killed, the naive save loses what it hadn’t finished writing, and when the power fails, it can lose even what was “written,” unless there was an fsync.

The journal

The same trouble lies in wait for the file system itself. To append one block to a file, it has to change several places on the disk: the data block itself, the bitmap of free blocks (that block is now taken) and the inode (the block is now on its list, and the size is different). The power can fail between any two of these writes. A block is marked as taken but belongs to no file: the space has leaked. An inode points to a block into which the data was never written: the file holds someone else’s garbage. In the old days, after every crash a checking program was run that went over the whole disk and reconciled everything; on large disks it ran for hours.

Modern file systems keep a journal. Before changing anything in place, they write all the intended changes as one record into a separate area and put a “done” mark at its end. Then they make the changes in place and erase the record. If the power fails before the mark, the record in the journal is incomplete: it is thrown away, and the disk stays in its “before” state. If the power fails after the mark, the records are replayed at the next start, and the disk reaches its “after” state. There is no middle. The same idea, “first write down what you are about to do,” will turn up in databases in Chapter 46.

Drill 2. The disk burns out

Scenario two: the disk dies for good. A hard disk’s mechanics wear out, an SSD’s cells wear out, and either kind can have its controller burn out. For a single disk this is rare, but in big storage systems with tens of thousands of disks, replacing dead ones is ordinary daily work. A disk will certainly break; the only question is what happens to the data when it does.

The first thing that comes to mind is a mirror: two disks with the same contents. When one dies, you carry on with the other, put in a new disk and copy everything onto it. That is reliable, but half the space goes to the copy. In 1988 David Patterson, Garth Gibson and Randy Katz of Berkeley published a paper called A Case for Redundant Arrays of Inexpensive Disks (RAID), and that is where the word RAID comes from. Their idea was to replace one big expensive disk with many small cheap ones. But the more disks there are, the more often one of them breaks, so the array needs redundancy, and not necessarily twofold. One extra disk for the whole array is enough, if it holds parity.

Parity is the exclusive or of Chapter 29 applied to whole blocks, bit by bit. Everything else rests on two properties of XOR: $a \oplus a = 0$ and $a \oplus 0 = a$. Suppose three disks hold blocks $d_1, d_2, d_3$, and a fourth holds $p = d_1 \oplus d_2 \oplus d_3$. If $d_2$ is lost, XOR together everything that is left: $d_1 \oplus d_3 \oplus p = d_1 \oplus d_3 \oplus d_1 \oplus d_2 \oplus d_3 = d_2$, because each surviving block appears twice and cancels itself out.

The parity bytes mean nothing on their own, but together with the two surviving disks they put BUZZ back together. This is how RAID-5 works. The data is cut into stripes: in each stripe every disk but one holds a data block, and the remaining disk holds their parity. The parity moves from disk to disk, stripe by stripe, so that no disk becomes a bottleneck: parity is recomputed on every write, and if it all lived on one disk, that disk would be doing the work of all the others.

RAID-5 has a weak spot: the rebuild time. To recompute a dead disk, you have to read all the others from beginning to end, and on large disks that takes hours, even days. If a second disk dies during that time, the data is gone: one equation with two unknowns can’t be solved. So large arrays keep two independent parities (RAID-6) and survive the death of any two disks.

Drill 3. Silent corruption

Scenario three is the most insidious one: the disk is alive and answers requests, but in one of its blocks a bit has flipped. The culprit may be a particle from a cosmic ray, an aging flash cell or a bug in the controller’s firmware. The disk hands the block over as if nothing had happened, and the damaged photo or spreadsheet lives on for years until somebody opens it. Meanwhile it is copied into the backups, and the damage spreads to all of them.

The defense is a checksum: a short number computed from a block when it is written and stored next to it, then computed again on reading and compared. The simplest checksum is an old acquaintance, the parity bit of Chapter 31, which guarded the core rope memory of Apollo. Here is what it catches and what it misses, next to two stronger checksums.

One flipped bit changes the parity, and two flip it back: a parity bit is blind to any even number of errors. CRC-32, a cyclic code computed in Ethernet, ZIP archives and PNG images, changes in both cases. It is built to be certain of catching every short burst of consecutive bad bits, and it lets random damage through about once in four billion cases. SHA-256 is a cryptographic hash function, a relative of the hashes of Chapter 16, but built so that nobody knows how to find two different blocks with the same hash, even on purpose. It is longer and slower, but it guards against forgery as well as against accidental damage.

The ZFS and Btrfs file systems store a checksum for every block and verify it on every read. If the disk returns a damaged block and the array has a mirror or parity, the file system takes the good copy and rewrites the bad one: the damage heals itself before anyone notices it. And the checksums of downloadable files, published next to the links, answer the same question for the network: did the file arrive the way it was sent? In the task “A sum with a memory” you’ll compute a checksum of your own, the one that works inside every zlib stream.

Drill 4. Human error

Scenario four is the one that happened at Pixar. The hardware is fine, the bits are intact, the journal is kept. A person gave a command, and the system carried it out. Neither the journal nor RAID nor checksums will save you from that: they all keep the data in whatever form they were told to keep it. The only thing that saves you is a copy the command couldn’t reach. Ransomware that encrypts your files, a stolen laptop and a fire belong here too: the trouble comes from outside and hits everything nearby.

This is where both lessons from Pixar come in. The studio had a backup, but it hadn’t worked for a month, and nobody knew, because nobody had ever tried to restore anything from it. A backup you have never restored from is not a backup but a hope. The check is simple and dull: every so often, take a few files out of the backup and open them. The second lesson: what saved the film was a copy that lay far from the server, on another computer in another house, where the rm command couldn’t reach.

Both ideas are gathered in the rule known as “3-2-1,” usually credited to the photographer Peter Krogh: keep at least three copies of your data, on two different kinds of media, with one of them off-site. Three copies, because two can die at once, like two disks of a RAID-5 during a rebuild. Different kinds of media, because identical disks from one batch suffer from identical ailments. And the off-site copy saves you from fire and thieves, who don’t choose which of the disks in the room to take. The drill below lets you test which copies survive what.

The drill soon reveals two traps. Sync, a folder that repeats itself on another computer or in the cloud, is not a backup: it diligently repeats deletion and encryption too. A mirror and a disk that is always plugged in also repeat whatever happens to the original, or perish along with it. What saves you are copies with a history of versions, from which you can get back yesterday’s state even when today’s is ruined, and copies that stay unplugged most of the time. Many systems take such snapshots by themselves: the ZFS and Btrfs file systems can save the state of a whole disk in a fraction of a second, and backup programs keep versions from hours, days and months ago.

Drill 5. Bring back yesterday

Scenario five: nothing burned and nobody erased anything. Yesterday the program worked, after today’s edits it doesn’t, and it’s unclear which of the forty edits is to blame. Or two people edited the same file, and their work has to be brought together. This calls for history: every version, signed with who changed what and why. Today almost every programmer in the world keeps that history in git, and git itself was born as a rescue operation.

Git could be written in a few days because it rests on one simple idea. A file is stored under an address computed from its contents: the SHA-1 of a short header and of the bytes themselves. This is called content addressing. Git itself isn’t installed in the sandbox, but its addresses can be computed by hand, and they will match what git hash-object prints on any computer in the world.

The string hello world with a newline lives at the address 3b18e51… in every repository, and an empty file always lives at e69de29…. Three properties follow from this idea at once. Identical files are stored once, however many versions and copies mention them: their address is the same. A changed file gets a new address, and the old version stays where it was, so nothing is ever overwritten. And if a byte in the store goes bad, the hash stops matching the address and the damage gives itself away: the checksum of the third drill is built into the store itself.

Git builds everything else out of the same bricks. A directory is a tree object: a list of lines, each with a file’s address and its name, and a tree has a hash for an address too. A commit is an object with the address of a tree, the address of the parent commit, an author and a message. Here is a toy version, in which the store is a dictionary and a commit is a piece of text.

Two commits, and only seven objects: Woody’s and Buzz’s files didn’t change in the second version, and the second tree points to the same addresses. The commit shows the whole construction: the address of the tree, the address of the parent and the message. The last lines show what happens if one byte goes bad in an old file: the check finds the object whose contents no longer match its address.

A commit’s address vouches for far more than one snapshot. It includes the address of the tree, and so the addresses of all the files, and the address of the parent, which in turn includes the address of its own parent, and so on back to the very first commit. Change a single byte in any past version of any file, and the addresses of all the commits after it change. Forty hexadecimal digits vouch for the whole history of a project. Commits with links to their parents form the directed acyclic graph of Chapter 19: an ordinary commit has one parent and a merge commit has two, while a branch is only a name that points to some commit and moves on to the new one with every commit made on it.

Git stores full snapshots rather than the differences between versions; it computes a difference when you ask for one, by the same search for the longest common subsequence of lines as the diff program of Chapter 22, only with a faster variant of it. The snapshots don’t bloat the store, because unchanged files are shared, everything is compressed, and when git packs objects, it does store similar ones as differences from each other. One more thing: every clone of a repository is a complete copy of the whole history. The server across the world that holds your project is the off-site copy of the 3-2-1 rule. In the task “A git of your own” you’ll build one that can save versions, bring them back and read the history.

Tasks

Four tasks, four tools of the rescue team: parity, rebuilding an array, a checksum and a version store.

What next

All five drills are done, and every disaster has met its remedy, from fsync and the journal to git, where every version is vouched for by a hash.

Think back to the rescue of Toy Story 2. The copy on Galyn Susman’s home computer didn’t get there by itself: the studio kept sending her the changes over a phone line. The off-site copy of the 3-2-1 rule also has to get there somehow, and git push sends commits to a server on the other side of the world. The common thread is that there is more than one computer. Two machines share no memory and no disk; between them there is only a wire or a radio wave carrying signals, and often a dozen intermediaries along the way. How two machines exchange data, who finds the route across half the world, and why bytes reach their destination at all is the story of the next chapter.