Recent Ugarit progress (by )

I had some time to work on Ugarit yesterday, which I made good use of.

I really should have worked on raw byte-stream-level performance issues - I did a large extract recently, and it took a whole week - but, having a restricted time window, I caved in and did something fun instead; I started work on archival mode. As a pre-requisite for this, I added the facility to give tags a "type" so we can distinguish archive tags from snapshot tags - thereby preventing embarrassing accidents that end up with a tag pointing to a mixture of snapshot and archive-import objects...

(Not that I didn't think about the performance issues. I have a plan in mind to rearrange the basic bulk-block-shovelling logic to avoid any allocation whatsoever by using a small number of reusable buffers, which should also avoid the copying required when talking to compression/encryption engines written in C.)

Archival mode

Archival mode in Ugarit works by building a tree of "archive import" objects (block type archive), rooted in an archive tag. Each import has some import-wide metadata of its own, such as the details of the host that did the import, a timestamp, links back to zero or more previous imports, which are the children in the tree (zero for the first import in an archive, and more than 1 if we "merge" two archives into one, which is a perfectly legal operation, but most imports will have just one parent). The import then points to a stream of archive entries, each of which links an object in the vault (identified by its hash) to a property list of object metadata.

The same object might appear more than once in an archive's chain of imports; in that case, the "most recent" archive entry's property list is considered current. That's the first one found in a depth-first search of the tree of imports (so the order in which previous imports are listed in an import with more than one "parent" is significant). So it's possible to update an object's entry in the archive by just re-importing it with different properties.

The Archive Cache

However, finding objects by traversing the tree would be a slow operation, so an archive mode client caches the archive blocks in a normalised sqlite database. There's an entry for each import and each object in a given archive tag, and object properties are keyed on import and object so the entire audit trail of a given tag (or object within a tag) is searchable using SQL queries. This cache is updated incrementally; when an operation on a given archive tag is requested, the caching engine is asked to ensure that the import pointed to by the tag is cached - if it isn't then it's read and all its entries added to the cache, after recursively ensuring that all previous imports referenced by the tag are cached. Each object in the cache carries a reference to the import that most recently updated it, so the "current" properties can be easily extracted with a suitable join constraint.

That's as far as I've implemented - I have a proof-of-concept bit of sample code that adds some files to an archive tag and then ensures the cache is up to date, which I test by manually examining the cache. I need to write an interface to query the cache (abstracting away the underlying SQL storage by implementing my own s-expression-based query language), then I can usefully integrate this lot into the unit test suite, then I need to work on the UI.

Low-Level User Interface to Archives

The low-level UI will be three extra commands to the ugarit command-line tool, plus an extension to the vault's virtual file system.

The first one will be to add an archive import to an archive tag. It'll accept a "manifest file" which contains a list of paths to files or directories to import, each with their list of properties. The second one will run a query against the archive (using the query language) and output the full property lists and vault key of the matching objects. The third one will be a tool to extract an object given just its vault key, so matching objects can be extracted.

The manifest file will let one provide a group of common properties for a number of entries within their "scope", to try and make it easier to (eg) attach the same album name to a bunch of MP3s. It'll be designed for easy human editing (s-expressions with a reasonable format), but there should be tools to auto-generate a manifest by taking a list of filenames and analyzing them with some logic to guess a file type and invoke type-specific plugins to extract metadata - ID3 tags, EXIF tags, and so on. However, the initial properties given to an object when it's imported aren't the whole story; manual "curation" of archive properties can be performed after import by assigning new properties to the existing object, and I'd like to one day provide a shiny user interface for that. I think it's important to get files imported into the archive, rather than having them languishing on disks "waiting until I get around to classifying them".

The virtual file system needs extending to allow for browsing of archive tags. Currently, snapshot tags contain a virtual subdirectory for each snapshot in the chain, plus one called "current" that reflects the most recent, and each snapshot object has a "contents" directory that's the actual snapshotted directory tree. Archive tags will have a history directory that contains a list of all the imports in the chain, each of which contains files exposing the import metadata and a list of imported objects (by key) with all their properties, and an all-objects directory that contains all the objects in the archive (also identified by their key), which will allow for very basic access to their contents.

High-Level User Interface

But I'd like to provide a way to configure "views" on the archive, based on object properties. I want to be able to make a virtual filesystem for all my music, perhaps, with a directory per artist, a directory per album, and then a file per track inside (with a made-up name consisting of the track number, title, and a suitable file extension), all made from properties.

My plan is to do that by providing a library of lazy tree constructor macros, so that snippets of Scheme code in the configuration file can explain how to build these hierarchies from the archive's cache.

The simplest would be list-objects, which queries the archive cache for all objects matching the current dynamic filter (fetched from a parameter which is empty by default), and then gives each of them a name constructed by a pattern from the object's properties. The next simplest would be filter, which adds extra filter constraints to the current dynamic filter parameter and then invokes its body, restoring the filter upon exit from the body (so it introduces a dynamic scope for the current dynamic filter). The "body" is a list of expressions which are evaluated to get lists of directory entries, which are concatenated together into one large list which is then returned. Another simple one is static-directory, which takes a name string as an argument and has a body; it evaluates the body (concatenating the results of multiple expressions) and returns a single directory entry, which is a subdirectory with the body as contents, and the given name.

The interesting one needs a good name, but let's call it narrow-by-property for now. It requires an ordered list of property names, and extracts all the distinct values of that list of properties from the archive cache, and returns a subdirectory for each. The name of the subdirectory is made by appending the value of each property in the list for that subdirectory, with hyphens inbetween, altbough an arbitrary user function can be supplied to override that. The body is then evaluated (as a list of expression, whose results are concatenated) for each subdirectory to populate its contents, but with the dynamic filter extended with the constraint that the named properties have the values associated with this subdirectory.

That way, one could construct hierarchies with code such as:

(static-directory "music"
   (filter (= ($ type) "music")
      (narrow-by-property 'media-creator
         (narrow-by-property 'media-collection
            (list-objects (sprintf "~A ~A.~A" ($1 media-collection-part) ($1 title) (guess-extension)))))))

That would create a top-level directory called "music", within which only objects with a property of "type" equal to "music" are shown; within that is a directory per "media-creator", containing a directory per "media-collection", containing files with names of the form "(track number) (track title).(guessed extension based on original filename or mime-type)".

I should explain the $ syntax, which is implemented twice (and both implementations used above). In the filter expression language demonstrated by filter, which isn't Scheme at all as it gets translated to SQL, (= ($ type) "music") actually means that the object being considered has at least one property called type which has the value music, for properties can be duplicated. Meanwhile, (= ($1 type) "music") would require that it has exactly one property called type, and that its value is music.

Within the filename-generation logic of list-objects (also used to override the name generation for narrow-by-property), however, that's actual Scheme code run in a dynamic environment that has a "current archive entry" bound to a parameter. In that context, ($ ...) is a macro that expands to a list of values for the named property in the current archive entry, while ($1 ...) expands to any one of the values of that property, or #f if there are none (perhaps an optional second argument could provide a default).

And I should clarify that all of these constructors are lazy; they are actually evaluated purely on demand, so producing each node of the tree should be relatively efficient.

Of course, extending the Ugarit vault virtual filesystem is of limited use when the only interface to that filesystem is via the ugarit explore command-line tool. It will really come into its own when HTTP / 9P / FUSE interfaces to the VFS are made available!

Use Cases

I've a few use cases I want to cover with archival mode. The first is just to move all of my "junk" - music, photos, academic papers, old software projects from my freelancing days (archive objects can be entire directory trees, as well as individual files - no need to tar things up), that sort of thing - off of read/writable disk and directly into the vault. Currently they live in manually-managed directory hierarchies, which are backed up into Ugarit snapshots, but that's not an idea data structure for read-only data. Being able to classify each object with a list of properties and throw them into an archive tag, then to have a mountable read-only virtual filesystem that's easily accessible from multiple machines, would eliminate a load of nasty duplication of state.

But I'd also like to put my email archive in there. Every email I send or receive could go into an archive, with all the headers fields extracted as properties and all the attachments as separate files. That'll de-duplicate nicely with the attached files where they appear in my home directory snapshots, either because I saved them from an incoming email or because they were sent by me.

And with all my photos in an archive, it would be possible to drive public-facing Web galleries from the photos, using properties that declare a photo to be publicly viewable in one or more galleries, through an HTTP interface. I'd be able to use that to replace the current infrastructure we use for putting images into blog posts, which uploads them to a server and creates three different sizes with an HTML page; all of that could be generated on-the-fly (with a bit of caching) from photos in the vault.

It might be nice to have cron jobs that archive audit trails from my various servers (eg, Web access logs); perhaps one file per day, with the hostname, name of the service, and the date as properties, so I can easily dig out old logs.

The possibilities of a self-organising distributed filesystem are many and varied. Dear readers, what fun do you think you would have with a filesystem that was also a database? How about adding support for objects that have no actual storage in the vault other than in the archive import metadata blocks, and purely consist of a set of properties, identified with a GUID rather than an object hash? These could contain structured data such as address book entries (sure, we could archive a vCard with all the contents of the vCard also extracted as properties, but then why bother with the vCard?), or to encode complex relationships between other items ("This photo shows this person at this position")?

No Comments

No comments yet.

RSS feed for comments on this post.

Leave a comment

WordPress Themes

Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales
Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales