Concern

The source code for my master’s project is now available via a read-only git repository at http://git.metastatic.org/readonly/arrow.git. If you’re interested in it, you can run:

git clone http://git.metastatic.org/readonly/arrow.git

and start playing with it. If you just want to browse the code, you can try out the gitweb interface via http://git.metastatic.org/. That lets you download a tarball of the current code, if you don’t want to clone the project.

Note that I’ve removed parts of the code that compute the Reed-Solomon erasure codes, since the licensing terms for that library aren’t clear right now.

It’s somewhat unstable right now, in that you really need to know what you’re doing to produce results, instead of breaking things. The source is available under the MIT/X11 license, though parts of it does use code licensed under the LGPL.

My Master’s project report, aka Technical Report UCSC-SSRC-08-02.

I’ve completed enough code with Arrow to get some results for local backups. Eventually, I want to be able to do remote backups over an SSH tunnel, similar to how rsync works, but this is a good start on trying out the idea. To run this test I wrote a simple program that backs up single files, specified by commands read from stdin, and a Python harness that drives the backup.

This first test used all Linux kernel versions in the 2.6.23 series; that is, every kernel version from 2.6.23 to 2.6.23.17. This table shows the results:

I’m fairly happy with the way it performs, and with the savings between versions. Of course, the savings aren’t optimal, and there is a significant amount of overhead with all the hashes and error-correction codes stored along with the data, but I’m satisfied that it doesn’t inflate the space used significantly more than the plain text-based diff. Also, the actual disk space used by the chunks is significantly larger than the space above, since each block is pre-allocated, and many of the slots are empty (this could be optimized, by allocating the keys and headers ahead of time, but allocating the space for the chunks on an as-needed basis).

Next I’m going to try implementing the SSH tunneling, at least, a prototype of it. Counting the network bandwidth used in a network backup is the next test.

Arrow stores most everything as files. Blocks, which can store multiple chunks, identified by the chunk’s hash code, are stored in sequentially-numbered files, starting from zero and going to whatever (internally, this is a 64-bit unsigned integer, so it can’t be more than 2⁶⁴, but I don’t think that will be an issue ;-). Version files, lists of chunks that comprise the underlying file, are identified by a random GUID.

I initially made all these file names base-64, with a minor modification: instead of ‘/’, I used ‘*’. This gave me something I can store on sensible file systems, it doesn’t waste too much space with the encoding, and it’s really simple to encode and decode. The trouble happened when I tried running arrow on Mac OS X, which by default has a case-insensitive file system [1]. Arrow failed pretty spectacularly when it tried writing more than 26 blocks into the store.

I could have rewritten the storage parts to use something like hexadecimal, but instead I just replaced the lower-case letters with other letters from the ASCII alphabet. It just so happens that if you avoid control and space characters, and characters that can’t be a part of file paths (/ and .), you have just enough characters to cover the 26 you can’t use! I know I could have used space characters, or characters between 128 and 255, but I opted to stay in ASCII, and came across an alphabet that works:

ABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&'(),-:;<>?@[~]^_`{|}0123456789+*

I thought it was pretty neat that ASCII had just enough to cover what I needed.

I’ve put some of the code up on-line. I don’t have permission to publish all of it, but I’ll see if I can get it.

I’ve been struggling a little with Arrow recently, trying to make progress. Since the chunk storage layer is nearly complete, the next part is the file metadata layer, which we will use to store the actual information about files backed up.

Continue Reading »