Backup system progress update (by alaric)

I forgot to mention before... I chose a name for it. Ugarit, after the site of the oldest human archive yet found.

Anyway, I had another few hours at it last night (I think my total's up to about a working day now; one more working day to go before I know if my two day estimate was correct!).

I've implemented two fundamental abstractions. In a limited-block-size reference-counted content-addressed store, a large file has to be stored as lots of chunks, with the keys of the chunks stored in one or more indirect chunks full of keys. If there's too many keys to fit in one indirect chunk, then you need lots of indirect chunks, and in turn, one or more doubly-indirect chunks to store the keys of THEM in, until you finally have a single chunk at the top of a big tree, whose key you can use to refer to the file.

Reference counting complicates this. As you're writing the file's chunks, some may already exist in the archive, and some might not. Those that already exist, you need to up their reference count, so we know they're being used. Those that don't, you upload the actual content to create them.

But if you reuse all of the blocks of a file - because it's not changed - then you'll find you can reuse the indirect blocks, too, since they won't have changed. In which case you mustn't increment the refcounts of the data blocks, since they're still only referenced from the one indirect block, even though that indirect block now has two references.

So, what I've done is to implement a "key stream writer" API. You create a key stream writer and feed keys into it, but along with every key, you feed a 'reused?' flag which is true if the key is a reused one rather than a new one.

At the end, you finish the key stream writer, and it returns you a key for the entire tree, plus a reused? flag.

And it does all the magic internally, incrementing the refcounts on reused keys passed to it if and only if it creates a brand new indirect block referring to that key, and correctly handling refcounts on any indirect blocks it uses. It does this with a lovely recursion; the key stream writer accepts keys into a buffer and flushes the buffer out to a key stream indirect block when it gets full, at which point it creates a parent key stream writer to manage the next "level" up in the tree, writing the key of the newly created indirect block to that writer. I'm quite taken aback by how simple and elegant the code is, for what it does 🙂

Then, on top of that, I implemented an sexpr-stream writer, which accepts sexprs (Lisp data records, in effect) and buffers them, writing them to the archive when there's too much for a single block, and using a key stream writer to track the blocks written. This is to be used to implement directories, which will be a list of records giving details of all the files in the directory. The sexpr stream writer needs to know about keys mentioned in the sexprs, so it can do the same refcount-tracking magic to handle sharing correctly. Luckily, in spite of those requirements, it also works beautifully and is also elegant code!

Then I just need to implement storing files (which should be quite easy; split the file into chunks, check to see if each chunk is already in the archive and upload if not, write keys to key stream), then I can implement storing directories (recursively store files and directories, use an sexpr stream writer to log each file created). Directory storage will need a few cases handled, since I plan to store funny filesystem objects like FIFOs, device specials, symlinks, and so on.

Then I'll need the main driver that does a snapshot of a directory tree, then creates a snapshot object with metadata in and links it into the snapshot chain for a chosen tag.

I reckon that lot will take me half of the next day - then I'll implement deletion (I've been implementing primitive deletion operators for key streams and sexpr streams as I go along, so this won't take long) and extraction (again, I've written fold operators for key and sexpr streams, so this won't take long), then I'll have the core done!

What will remain then? A command-line wrapper with decent option parsing and command line ops to do a snapshot to a tag, retrieve all or part of a snapshot, list snapshots on a tag, delete a snapshot, and delete a tag, which should just be a matter of plumbing. Then I'll be done!

I still think I'm on for two days... but mainly because I'm punting on writing an actual S3 backend for now. That'll take a while, dealing with fiddly Web Services authentication stuff!

Other things I ought to get around to doing at some point are:

1. LZMA compression. For now, I'm using a deflate implementation for Chicken Scheme that I found, but I would like to wrap liblzma as a Chicken egg, since it's thought to have tighter compression.
2. Encryption. Right now I have a stub in the code for encrypt/decrypt operations, applied to the compressed blocks, but for now it just returns the block unchanged. I need to either use Chicken's libcrypt egg (which looks complicated) or find a lightweight implementation of a good cipher that I can wrap as an egg.
3. More storage backends.
   1. A replication backend that wraps a list of backends, doing writes and deletes to all of them, and servicing reads from the first backend that succeeds to provide a block. That way I could back up to a local disk and to S3, and restores would come from the local disk if possible or from S3 if not. Even if I lost part of the local disk in a filesystem corruption incident, anything I lost would still be available from S3.
   2. A generational backend, that wraps a list of backends. Writes are only done to the first, but reads (and deletes) are serviced from the first one that responds. That way, I can fill up one hard disk with archives, then start filling another, and so on, building up a chain of archive partitions.

Care must be taken when doing complex things with backends, though, in order to preserve the correctness of reference counts. A group of archives that are used together by replication or generations will have refcounts that are correct across the whole group, not necessarily individually within each component archive.

More forbodingly, my existing cache backend wrapper won't mix well with deletion of snapshots when the same backend is shared between multiple machines, as it basically caches the existence of blocks; but if a block is deleted by another system, the local cache won't know, and will incorrectly report that the block is already known. Which means it won't get uploaded to the archive, which means data could be lost.

For now I'll recommend that people who want to delete from shared repositories don't use the cache, or flush the caches after a deletion, but in the long run I'd like to think about how to improve the cache. Perhaps by logging deleted keys to a special area in the backend, and when a cache starts up, it can fetch the log and look for any deletions it doesn't already have. Or just compress the entire cache file and upload it when closing the connection, and download it when starting a connection, as long as no two cache-using machines are snapshotting at the same time...

Backup system progress (by alaric)

I mentioned an intent to build a backup system this Christmas. Well, I've not had two days to work on it yet; I've just had an hour and a half one evening, in which I've written the local-filesystem backend...

But last night I had a dream about it. In particular, I dreampt of visiting an old friend I've neglected to keep in touch with lately; and at her house she had a rather snazzy little mini-laptop, like an EeePC or something, which had an eSATA connector into which she plugged some humungous (in terms of gibibytes; it was the size of a double CD case, physically) external hard disk upon which she had a filesystem that seemed to work very much like Fossil/Venti, the original inspiration for my backup system - or perhaps like a giant personal Git repository.

In particular, one feature that cropped up in the dream was that the filesystem had a magic file on it which was an RSS feed of recent changes to files.

Which got me thinking about features for version 2 of my backup system (if I get to finish version 1, that is!). My focus is on offline use, for batched backups, but the filesystem in my dream was being used online.

For a start, we could have a log of changes to tags, as in my system tags are the "roots" of the archive system. The creation of new tags, the deletion of tags, or the updating of a tag to point to a new snapshot would all be logged. This could then be used to create the RSS feed.

Secondly, it shouldn't be too hard to write a FUSE interface to the thing for read-only access, presenting a root directory containing an RSS file generated from the log, along with a directory for each tag, which in turn contains a current subdirectory containing the current value of the tag as well as dated subdirectories containing all the past contents of the tag, in ISO date format so they sort correctly. And perhaps an RSS file just listing the history of that tag.

But then the next cool thing would be to allow write access, by using a local disk directory as a staging area, so the current subdirectory can be written to (with the changes being spooled to the local disk). Then when a commit command is given, those changes are merged into current. Which would require a new underlying operation to merge changes in, rather than taking a new snapshot; the difference being that any files or directories missing in the directory tree being snapshotted are 'inherited' from a previous snapshot already in the system, with some mechanism to reflect deletions.

Anyway, unrelated to the dream, it also occurred to me that it'll be neat to support replicated archives; my implementation of the backend architecture will make it easy to take a set of backend instances and merge them into one, with every write going to all of them and reads serviced from the first one that succeeds. It'll also be easy to support staged archives, where a number of read-only backends are checked for existing blocks, but all new blocks go to a nominated writable backend, with another backend adapter. That will allow for generational backup systems, where a local disk is filled up with backups until it reaches a size limit, whereupon its contents are shipped off to a DVD writer (keeping a local cache of what blocks where on there, so the DVD need not be put in unless the contents of blocks are actually needed).

But, all idle speculation for now. I still need another day and three quarters to implement the core of the thing...

Design patterns (by alaric)

I'd thought I'd had this little rant before, but as I went to find the post I'd had it in to link to it from a big ranty post I'm working on, I couldn't find it.

So here it is.

My opinion of design patterns.

Design patterns are common structures that appear in computer programs, but that can't themselves be abstracted into a reusable component.

That's fair enough. I have the "gang of four" book of design patterns, that started the craze, and I think they're all good design patterns in mainstream OO languages; things that can't be actually encapsulated as a class or whatever, but that keep cropping up.

However, the problem is that the patterns community has somehow ended up with some dogmatic folks in it. Who take phrases such as "Design patterns are common structures that appear in computer programs, but that can't themselves be abstracted into a reusable component" - and then attack anybody who claims to have encapsulated a design pattern into a reusable component.

Because design patterns are really only valid in relation to a set of languages. For example, in assembly language (or even traditional BASIC with GOSUB), procedure calls are a design pattern. There is no language construct for a procedure; instead, you have a GOSUB or CALL to a given address, that explicitly saves the calling location somewhere and then jumps, and a RETURN to go back to that saved location. The GOSUB...RETURN pairing is put in there by the programmer; it's a design pattern.

But then higher-level languages have explicit procedure abstractions, and all the fun they entail.

Even object orientation is a design pattern in languages like C. "Put function pointers in a struct, and call them with the struct pointer passed as the first argument". Or including a pointer to a struct of function pointers in every data struct (and call it a virtual method table). But go to Java and that's an explicit language abstraction facility.

The gang-of-four book is taken as the authoritative book of common design patterns (although it is, in my opinion, a book of design patterns for mainstream OO languages). And design patterns are things that cannot be expressed as native abstractions in code. THEREFORE, fools think, it's impossible to write a design pattern in code. And anybody who claims to have done so needs shouting at.

Sadly, as demonstrated in Peter Norvig's presentation on design patterns in dynamic languages, more advanced languages can express abstractions that others can't, and there are plenty of more advanced languages than C++ and Java.

In fact, I think that the appearance of design patterns in a language is probably a hint that the language needs to be more powerful - and suggests how to make it so. What sort of abstraction would make it possible to encode your design patterns?

And so, as I read "Modern C++ Design" by Andrei Alexandrescu (a book on doing good things with C++ templates), I come across the following phrase:

Eventually, Andrei turned his attention to the development of template-based implementations of popular language idioms and design patterns, especially the GoF [gang of four] patterns. This led to a brief skirmish within the Patterns community, because one of their fundamental tenets is that patterns cannot be represented in code. Once it became clear that Andrei was automating the generation of pattern implementations rather than trying to encode patterns themselves, the objection was removed...

Bleargh. It sucks when people get all religious about the interpretation of a given piece of "scripture". Even when people manage to work around it by using illogical arguments ("No, no, it's not a representation of the pattern in code, it's a bit of code that automates the creation of implementations of the pattern..."). Sadly, in other realms, this kind of thing can lead to people being burnt at the stake.

Sump plug woes (by alaric)

It's time I changed the oil (and the oil filter) in the van, since it's been over a year now.

So I bought myself some new oil, and a new oil filter, and prepared to do the deed according to the instructions in my Haynes manual.

The first step is removing the plug in the bottom of the oil sump, that lets the oil out. It looks like this:

Naturally, when you remove it, lots of hot oil comes running out (you do this with the engine warm so the oil flows well). So you do it with a bucket underneath!

However, I've not gotten as far as that step yet, because the head of the sump plug (which is hexagonal, like a bolt) is rounded. You can see in the pictures how the corners of the hexagon have all come off. They're shiny where I've been trying to grab them with a spanner, which just rotates when I apply enough force... and it doesn't take very much force.

So I went out and bought a special thing for undoing damaged nuts and bolts. It'll make a mess of the sump plug, so I bought a new sump plug, too. The magical nut remover looks like this:

The spiral grooves inside are rifled so that when you put it onto a nut and turn it (such as with the big adjustable spanner in the background), the points grip into the metal of the nut, and the spiral pulls the socket onto the nut as it twists it out, so that it can't push the socket off. Most stripped nuts and bolt heads are rounded towards the top, so tend to push spanners and sockets off as they are twisted; this thing pulls itself onto the nut with the spiral shape, thus counteracting this.

However, my sump plug bolt head is already far enough gone that the special socket rotates on it (shaving off little curls of shiny metal as it goes) when I turn it, again with surprisingly little force - but the next size of socket down doesn't fit onto it...

Perhaps the sump plug was made out of lead or aluminium or something?!?

I guess the next thing to try would be getting under there with a file and shrinking the head down to the next size by putting new flats on it.

But, since it's freezing outside and I've nowhere inside to work on the van, and we need the van ready to do a long drive in a couple of days (which I'd rather not do with the current black oil in, in this punishing weather), I think I'm going to take it to a garage and ask them to sort it out for me... I can give them the oil, the oil filter and the replacement sump plug I've already bought and just ask them to do the hard part!

How to use a Maplin USB microscope on a Mac (by alaric)

We received a USB microscope from Maplin for Christmas, from my father and stepmother. It's basically a webcam engine coupled to a different optical system; so there's a small hand-held device on a cable that plugs straight into a USB port. It has inbuilt LED lights, so you push the end right up against a surface, and the casing of the unit holds the surface at the correct focussing distance while illuminating it. There's a manual control to focus, but once it's set, you don't need to fiddle with it.

It's Maplin code N87FX.

Anyway, it claims to work under various flavours of Windows, and certainly doesn't work out of the box on a Mac - but a bit of research (see the USB vendor/device codes in System Profiler, looking them up at http://www.linux-usb.org/usb.ids to find the generic name of the device, googling from there) led me to http://www.pc210.com.cn/downloadhtml/sonix201_PC_Camera_driver_for_MAC_405.html where a suitable driver can be downloaded. The RAR file wouldn't expand under Stuffit, but unrar from pkgsrc on my NetBSD system opened it fine, to reveal two zip files (duh) each containing a .dmg file (duh) which had a different driver in each... I just installed both.

Skype then immediately picked up on it as a webcam. But Photo Booth refuses to talk to anything other than the inbuilt iSight on my laptop, but then I found that the driver installs had also installed an app called Webcam Monitor, which is a simple wrapper around the underlying Quicktime video capture APIs, adapted from Apple's reference source code. It can record video, or a simple ⌘-C will copy a picture to the clipboard for Preview.app to save. It'd be nice to find something where I could just press a capture button and have a snapshot appear in a list which I can then choose a name for and save as a .PNG to automate this, though. Perhaps I ought to do my own quick adaption of Apple's reference source code...

Observe, my stubble!