Alice.

Tuesday December 11, 2007

Apple, if I was an American, I'd probably sue you. I trusted this backup system because I had a deep knowledge of exactly how the underlying system works. I'll try to describe it for you, so as to help you understand what may have gone wrong here. I will apologize now for the length and technical nature of this entry.

Time Machine keeps, on disk, what appear to be complete snapshots of your files. Inside the Backups "folder" on the drive you designated to Time Machine, is one folder per computer. Inside that is one folder per time period. I.e. 24 hourly, daily backups for the month, and as many weekly backups as it can. This adds up to a lot of dated folders.

Each folder appears to contain every file in the backup set; not just the ones that have changed. This is, in fact, technically true. Each folder contains the backup files as of that date. This means that while the backup may only take up 40GB on disk, there will be 4TB of files present in the folders. Even simpler, if you are backing up 40,000 files, and you have all of the recommended backups (daily and hourly), then you will have 2.2 million files present on the backup drive. However, if none of the files have ever changed in the history of all of the backups, then only the original 40,000 files are taking up any room. This is done through the magic of linking.

On any UNIX-derived operating system there are two kinds of links. Called hard- and soft-links, they are fundamentally different. Soft links, a.k.a. symbolic links, the most common, are called "aliases" by Apple. They are implemented as a simple text file which contains the path to the target file, which is then flagged as "special". Any application that tries to read from the symlink will actually read the target file, not the symlink. This is useful. This, in fact, allows me to have my music, movies, and pictures stored on my external HDD without most applications on my computer realizing it. (They access /Users/amcgregor/Pictures/wallpaper.jpg which is actually /Volumes/Storage/Pictures/wallpaper.jpg.

Hard links are very special. There is only one way to tell if something is a hard link or not, and absolutely no programs try. Before I can explain how hard links work, it's important to know how files work in general. Your HDD is split into roughly 4KB sections. There are a lot of these sections. If you create a two-byte text file containing the word "hi", it takes up 4KB on disk. The sector size is the file size edge that every file is rounded up to. The name of the file, say, "foo.txt", is stored in a sector for the directory it is contained in, which references the 4KB sector which is the contents of the file. So reading the contents of "foo.txt" looks at the current directory's node to look up the sector for a file with the name "foo.txt", then it actually looks at the sector of the file to get its contents.

A hard link is when you have two (or more) directory entries referencing the same physical sector for their contents. File name A and file name B reference contents C on disk. The data sector keeps track of a few things, which help keep track of linking. First, it knows the numbers for all of the sectors which belong to itself, in the case where the file is larger than the sector size. It also keeps track of the number of directory entries pointing to it - the "reference count".

Here's the big difference between Windows FAT and NTFS, and UNIX file systems. Windows file systems don't have the reference count, so two directory entries pointing to the same data is called a "cross-linked" file and is a bad thing. Deleting files in Windows actually modifies the data sector to say "Hey, I'm gone!". On UNIX, deleting a directory entry deletes the directory entry, not the data sector. The file system then checks the data sector to see if the reference count is now zero. If it's zero, only then does it delete the data sector.

This, finally, brings me to the point of this diatribe. Time Machine, while its doing its backup, only copies files to the new snapshot folder that have changed since the last backup. This is smart, and good. Then, for every file that has not been deleted since the last backup and has not changed, it creates a hard link to the old data. This saves space and makes each snapshot folder appear (very convincingly) to be a complete copy of the backup files, changed and otherwise.

I did something silly, but not unexpected. My backup drive was full, I had never actually used Time Machine to restore anything yet, so I wanted to get rid of all of the old backups and just keep a few of the more recent ones. So I went in with the Finder and deleted all but the latest three snapshot folders. It took a long time to empty the trash. You may be wondering what this would accomplish. In the perfect world, it would only actually delete from disk the contents of the files which have been deleted (and thus aren't referenced in the last three backups). I download a lot, so my downloads folder constantly cycles as I add files, they are automatically backed up, and I then delete them. This should have reclaimed a fair amount of space. It did.

I then, to make sure the backup was A-OK after I did this, forced the backup to run again. It completed successfully, which made me happy, and I proceeded to re-install my computer. Once my system was back up and running I had a gander at the backup, and the files were gone. All of the files except the ones that had changed in the snapshot. All of the files but the ones that had been copied explicitly for that one snapshot. Wait a minute. What does this tell you?

That somehow the hard linking failed. All of the folders which should have contained files were empty. All I can guess is that the Finder, not understanding the concept of hard links, actually deleted the data sectors from disk and not just the directory references like it should have.

After a few minutes of stunned silence, and now nearly 24 hours of little productive work, I'm still trying to rebuild what I need to work. Secure keys for server access are gone. Projects I had been working on; gone. Everything is gone with two exceptions: my photos, which I copied by hand and verified, and everything saved to .Mac (saved passwords, address book, calendar, e-mail settings, browser bookmarks, and desktop preferences).

Holy shit. God damn it the fuck Jesus.

— Alice.