Wikilon Filesystem

Wikilon isn’t just an online dictionary for AO code. It will offer a simple filesystem-like abstraction, allowing use as a software platform for creating interesting applications and services. Simple isn’t easy. I’ve spent a great many hours designing, refining, and backtracking on the subject over the last ten days.

A few of the design points I find interesting:

• Stateful files are replaced by purely functional objects, i.e. closures with fixpoint behavior. An unsophisticated purely functional object is `µO.[arg→(O*result)]`. I plan to use the same model as for embedded literal objects, which cleanly separates queries from updates. For example
• Basic authorities aren’t just “read” and “write”, but also “update” and “query”. Read and write are still available, but operate at source level (reflection, direct manipulation), whereas update and query authorities use message passing and thus allow the object in question to protect its own invariants. This should simplify collaboration between software agents.
• Usefully, state resources for RDP can essentially use the same model as state resources for imperative code, albeit with a small tweak: the update method takes a set of demands rather than a singular update message, and I must compute to a fixpoint.
• Scripts can also be transparently used as resources, allowing ad-hoc adaptability and attenuation of the resource model. By ‘script’, I mean bytecode that is run when a query or update hits that resource, with the possibility of querying or updating other objects.
• Updates are typically transactional (for imperative) or logically timed (for RDP) so this filesystem is a great deal easier to reason about than conventional filesystems, even with high levels of concurrency.
• I’m making extensive use of logarithmic history. Users will be able to step back in time and briefly interact with historical snapshots. Even better, this will support retroactive testing, i.e. applying new tests on all available past states, and rather flexible debug modes where you can operate on past states.
• Directory structure, relative to convention, is inverted. Every user has their own ‘root’, at least so far as they can tell. Public or shared directories might be mounted as subdirectories into each user’s workspace.
• Directories have both internal ‘pet’ names, e.g. a file or directory named “bob”, and stable, opaque, external names based on, e.g. `HMAC(serverSecret,parent++"bob")`.
• Capability secure. Capability strings provide authority to directories or objects, and may be attenuated and shared. In addition to an opaque GUID, each capability includes an authority code and an HMAC to guard the capability against forgery.
• Simple tactic to mitigate supercalifragilisticexpialidociousID problem. See below.

The capabilities aspect has received much of my attention recently. I’ve determined that I can’t use ABC’s `[{tokens}]` because it creates aliasing problems for imperative code (resulting in race-conditions), and because it also muddles up cross-model queries between imperative transactions and RDP behaviors. Instead of tokens, I’m using strings together with a few annotations and sealers.

The capability strings look like `Mbdfghjkmnpqstxyz…` where `M` is an authority code, and the mess that follows is a bunch of base16 including GUID, HMAC, and potentially some path information. My goal is that this string should look exactly the same in your browser URL as within Wikilon.

Instead of permission flags, which allow invalid combinations, I’ll just use a short enumeration of valid codes: M: query+update, P: update, Q: query, R: read, S: read+update, T: read+write. (I’ve rejected write-only option as unwise, though it could be modeled indirectly via script. In most cases, what you’d really want is update-only.)

Unfortunately, a conventional representation of GUID+HMAC gets to be pretty bulky.

I’ve found a simple tactic to mitigate this: GUID and HMAC can overlap a fair amount so long as I expose enough of the GUID (e.g. 32 bits) to filter down candidates. I can then XOR the candidate GUID with the string to recover the HMAC, then test the HMAC. Thus, a 192 bit GUID plus a 160 bit HMAC could share a space. (I wouldn’t be surprised if other people have been using this idea since before I was born. But it’s the first time I’ve thought of it.)

A simple annotation like {&rsc} could greatly improve performance and ability to locate dead links in scripts or objects.

I’m still hammering out many details.

In addition to GUID and HMAC, I’m thinking I might want to keep some path information in some manner so as to support transitive revocations. One candidate mechanism is to list the first sixteen bits in each GUID in a path from root to the target GUID. If any of the elements on the path (most likely symbolic links) are disabled or now point elsewhere, we could disable the capability. Again, path information could partially overlap the GUID, and perhaps even a little with itself, while still supporting an efficient search. But it couldn’t overlap with the HMAC.

I’m also starting to think that acid-state isn’t going to scale (not with long logarithmic histories and goals like game development), and its interface doesn’t fit right for my use case. I’m now checking out TX, TCache, and Perdure. I’m hoping I won’t need to write my own.

Addendum: I speak more about the resource model on the captalk mailing list.