Hacker News Reader

Comment by jff | Hacker News Reader

The real question is why the hell Time Machine backs up at a file level instead of at a block level.

Plan 9's Venti archival storage (http://en.wikipedia.org/wiki/Venti and http://plan9.bell-labs.com/sys/doc/venti/venti.html) stores data as blocks, which are referenced by SHA1 hashes. Since these blocks range between 512 bytes and 56 KB, a large file (like a mail file) gets split into many blocks. The brilliant thing is that a given block will only ever be stored once; your top-level filesystem then only has to keep track of which SHA1 hashes make up a file.

With this system, people have been keeping daily snapshots of their filesystems over the course of years, and the space consumption rate actually tends to decrease over time--see the graphs at http://plan9.bell-labs.com/sys/doc/venti/venti.html

View on HN

Backup systems make tradeoffs to be space efficient (block level backups) or computationally efficient (using full file backups that have mostly IO cost.)

Apple made the choice to have time machine operate with little CPU burden. While this would be a tremendously poor choice for an online storage system like SpiderOak, Dropbox, SugarSync, etc. it probably makes sense for them since it's usually working with a local external drive.

I admire much of Venti's design, but last I checked, Venti didn't support recovering the space from deleted items, except by way of making a new copy of the file system.

Apple made the choice to have Time Machine operate with little CPU burden.

I don't know why, given that my CPU is a sunk cost. (Also, I suspect that Apple chose hard links instead of deltas for ease of implementation, not to save CPU cycles.)

last I checked, Venti didn't support recovering the space from deleted items, except by way of making a new copy of the file system.

I think the state of the art has moved on since Venti; Cumulus (and probably tarsnap) implements garbage collection to recover space. http://cseweb.ucsd.edu/~mvrable/cumulus/

It was definitely not chosen for ease of implementation, as Apple had to modify core file system functionality, adding support for hard links to directories as well as files in HFS+ which is fraught with peril if not implemented just right. Users just don't want a backup utility to use any significant amount of CPU and slow down their machine.

As a side note, it has always been possible (on UFS at least) to link directories. It just gets a bit messy at fsck time, and older shells get a bit confused with 'cd ..'

Apple's implementation could have avoided linking directories - by creating new directories each time but always linking the files inside them - though I suspect that they decided it would be far quicker to replicate entire trees if you knew nothing in them had changed.

If I recall correctly, Venti doesn't support "recovering space from deleted items" by design - it was designed to store data on WORM drives.

Time Machine can be made to be "aware" of files that are effectively filesystems themselves - you can watch it as it backs up VirtualPC for example. It doesn't take the entire 10G virtual disk image every time.

i've never heard this before. how is it done?

I can't find any documentation on it on Apple's website, but it's easy to see it working. Annoyingly it doesn't do with with VirtualBox which is what I use now. Well it kinda does - it recognizes the VDI files as virtual disks, but can't open them with the VirtualPC plugin (in /Library/Plug-ins/DiskImages/).

I'm not sure this is Time Machine. I know that in VMware Fusion, at least, there's an option to turn your monolithic disk image into a set of smaller individual files. If you turn this on, then Time Machine only has to backup the smaller part-image file that's changed.

I know I've definitely seen Time Machine re-copying entire 10 GB virtual machine disk images before, with Parallels and VMware Fusion images, before I discovered this feature.

Reply on news.ycombinator.com