townx

rsync is a great utility. I bloody love it, and use it to do all my backups: over the network via SSH onto remote filesystems, and locally onto USB drives. I also use it to restore my home directory when I switch machine. Great.

However, the network part of my backup solution is expensive (in money). I use Strongspace at the moment, which works really well. But it is too expensive: $8 a month for 4Gb of storage, which means I have to keep a close eye on my files to make sure nothing massive goes over and maxes out my account. There are alternatives, of course, and the GDrive might solve all of my problems; but for now I'm stuck with not enough network storage.

S3 gives me the right price, but there is no mature client solution which does the job for me (JungleDisk looked promising, but it seems a bit buggy on my Linux machine - it sometimes just hangs - and Natilus doesn't properly mount WebDAV shares onto the filesystem, so I can't rsync to it). So I've been working on an S3 library for Ruby to allow me to sync a local filesystem to S3 automatically, only transferring the files which have changed.

I've been reading up on rsync a bit to work out what it does, and it's pretty clever: here's a technical report which explains the inner workings. It does a block by block copy from the source file to the target file, using a so-called "rolling checksum" on each block to decide whether: a) the source contains the block, but the target does not; or b) the block in the source file exists somewhere in the target file. In this way, only changed blocks are copied from the source file to the target file (plus some checksums and block indexes). This is what makes rsync so fast.

I'm not sure whether you could work things out the same way with S3. Each resource (accessible via a key into a bucket) on S3 has an MD5 checksum associated with it, so you could get a checksum for individual blocks or file fragments; but I'm not sure I'd want to split a file over multiple S3 keys to be able to do block-level copying. Although a bucket can contain as many keys as you like (even though you are limited to 100 buckets), so this might be possible. But to retrieve a file you would need to recompose it from the fragments on S3, which is a bit crap.

The obvious approach would be to associate one key with each object you put onto S3. This has the advantage of making each file addressable by URL, rather than requiring a reconstruction of the file from S3 fragments. Then when you sync your filesystem to S3, you do a comparison of the MD5 checksum of the local file to the MD5 checksum of the remote file. This could be pretty painful, though, and take forever: one call to S3 to get the target checksum, a checksum on the local file, then transfer of the whole file up to S3 if it has changed. This could perhaps be streamlined: instead of requesting the object using GET, you could use a HEAD request, which just gets the metadata; and perhaps the client could send a If-None-Match header with the request, passing the MD5 checksum as the value for the header - in this case, if the MD5 checksum in the request matches the checksum on S3, S3 will return a 304 response code (not modified), so we know the object hasn't changed and we don't need to parse the MD5 checksum out of the response. This could save a few cycles.

An alternative might be to put a piece of "file modified" metadata onto S3 (not the same as the date on the S3 resource, but a copy of the file modification time of the local file when it was transferred). Then just compare the local file modification time to the S3 metadata when the algorithm is deciding whether a file needs to be transferred. The file stat to get the modification time is likely to be far faster than an MD5 hash.

Yet another approach would be to just keep track locally of file paths and modification times (e.g. in a database) from the last time they were sent to S3. I think this is what JungleDisk does. Anything that has been added/removed/changed will be transferred without needing to reference S3 at all, so no expensive network operations. However, this will only work if S3 is only being sync'd from one location, and won't work if you are trying to sync from multiple locations. Is this enough, or should local files always be compared to S3 to determine whether they should be transferred? Maybe a local database of file modification times is enough?

One more idea: perhaps you could combine the database of local file modification times with a cache of MD5 checksums for those local files. You could then:

1. Find any new files and transfer them to S3, while their checksum is generated and stored in the local database in the background
2. Find any files which have changed, generate new checksums, cache them, and then compare those generated checksums to S3 checksums: the file gets transferred if its checksum differs from the one on S3
3. Determine which local files have disappeared and optionally remove them from S3; then delete their cached MD5 checksum from the database
4. Any files which haven't changed can have their checksum compared to the S3 resource

This has the advantage of some local caching, but isn't dependent on it; so you could use this approach to sync multiple machines to a single S3 bucket (unlike the database-only method). And the local cache could be optional, so you could use this approach from any machine, even if it was unable to do the caching (though with the ubiquity of file-based databases like SQLite it's unlikely you'll be working on a system with no database).

You could use this to do two-way synchronisation too, potentially. So if a file hasn't changed locally, you could get the client to compare to the S3 version, and fetch that to replace the local file if they are different. Though I think I will be concentrating on doing it in one direction first.