Inventing the Future: Secure Persistent Objects, Take 0

From the day I first read about Croquet, I’ve been trying to wrap my head around the secure, persistent object model. Building applications — or even understanding what applications can be built — depends on this model, which is still under development by the Croquet architects. Four months later, I’m still pretty lost.

I’m most interested in how the pieces fit together, and the abilities afforded by that configuration. Alas, I’m not clever enough to understand and express this entirely in the abstract. The more specific I get in components and abilities, the more specific I need to be as to a plausible way of implementing it. Otherwise, I get lost. I hope (unrealistically?) that no one takes this as a proposal. In fact, I’d be perfectly happy if the same abilities were achieved for Croquet with different implementations. I’d even be ok with a different set of abilities, as long as I understood what and why they were. But I gotta start somewhere. This is public because I would like help in improving my understanding, and also because my blog is from me personally. It does not represent anything from U.Wisconsin or the Croquet architects. Maybe by putting even wrong stuff into print, we can clear up misconceptions.

—-

The first thing we need to achieve is to be able to get “interesting” objects when we need them. For example, when we visit a Croquet place, we want the system to transparently load all the objects in that place. (By “place”, I mean those spaces that are part of the same continuous collaboration. A Tea party.) If we leave and come back, we need to automatically and always get the changes, otherwise we’ll be out of step with whomever else is simultaneously working in that place. Same thing if we fall behind the others, or get some other kind of error in the collaboration. I’m not aware of any real difference in what is needed for joining, resynchronization, and recovery. These are all examples of some (any) host in the collaboration “giving” (a reference to) an interesting object to another host. As far as I can tell, any host might want to give an object to another, or to oneself. (The latter in a lookup or some other search, or any remembered interesting object reference, or when pulling something from one place, such as private pocket, to any other space.)

Each “interesting” object in Croquet could be persisted by serializing it and storing that serialization. I would expect the serialization mechanism (e.g., image segments?) to deal with objects such as numbers, strings, and references (pointers) to other objects in the same place, which are then included in the serialization. But there are two other interesting kinds of values. References to objects in other places need to be replaced in the serialization by some kind of stable handle for that object. When we read back in such an encoding, we automatically fetch the serialization of that object from wherever we keep these serializations. Each object will also have a class definition that specifies its behavior. That is, it has a class property that points to a class object. In general, we could treat this exactly like any other reference, but if we initially want to treat these as very slowly changing, we could treat these as specially recognized objects built in to the implementation. For now, let’s say that objects are saved “when needed”, but transparently, without the user doing anything special.

All these objects could be assigned a stable handle and stored under that key on a server database. (More on that handle, below.) Depending on the construction of that database, information such as author and date could be stored as additional metadata or simply as properties of the objects themselves. To distribute the world-wide load of Croquet access, we could partitions the database, and to avoid having a single point of failure, we could replicate the partitions. We might individually want to arrange for those partitions we use most often to be replicated on a handful of servers in our working group, and it might be cooler still if the migration of partitions happened automatically. One way to do this is to form a group for each interesting object. The serialization is broken into blocks that are distributed over the available servers in the group, with each block on multiple such servers for redundancy. A server need not be part of every such group, but only those groups that correspond to objects that are interesting to the constituents of that server (i.e., the folks paying for, subscribing to, or otherwise accounted on the server). In the case where the servers in a group are actually the exact same machines as those that are running a Croquet world using that object, the distribution, replication, and access are all taken care of by any well-known Distributed Hash-Table (DHT) algorithm. Some of these even optimize for local network distribution patterns, but that’s more experimental. For any chosen DHT algorithm, one can compute the number of machines necessary to produce a desired availability (e.g., a probability of getting the data greater than that for a big-iron server and network). Then we can provide such availability by dedicating that number of cheap machines and simply leaving them running in the given Croquet places with no users doing anything at the keyboard. None of the Croquet machines, including any headless “servers,” need any fancy networking or fixed IP address. (OK, I’m now waving my hands a bit.) By distributing the database over exactly the same set of machines that use it, we get the right economics for scalability. Anyone can play: they can create stuff that is only interesting to themselves, yet still transparently persist it. When someone opens an object up to others, then the others act as stores and servers for it. In fact the number of available servers grows as the number of interested parties grows. This is the same economics – and more or less the same mechanism – as BitTorrent. Interestingly, the more people you share your objects with and which they find interesting enough to use, the less resources it costs you personally. Also, a DHT-per-object gives us free distributed garbage collection: when no one is interested in an object any longer and they eventually clear their local machine cache, then the object ceases to exist. And there’s no need for users to be notified of changes to “the database.” Changes are made through an ordinary message in Croquet itself (and seen immediately by all members) and persisting to the database happens as a side-effect.

I’d like to never have to tell Croquet to “save”. That’s a computer thing, like memory management, that has nothing to do with whatever I’m using Croquet for. I imagine (in my dreams?) that slowly changing objects can be persisted (asynchronously) as soon as a change is committed. You work on something, you walk away (or crash), and the object is just the way you left it. (This might make more sense for a DHT than for storage on a central bottleneck server.) Where performance doesn’t allow this, we might have to checkpoint large, frequently changing objects periodically, with a separate object for the message history since the last checkpoint. One way to decrease the need for this (if any), might be to make the saved segments be finer-grained. For example, an application object need not be directly within a Croquet place. It can be wrapped in an object that takes care of its position and orientation within the local space (like TSpinner), and which also serves as an “impostor” or “proxy” for the real object (which can be a separate “interesting” object on its own (with its own handle, segment, DHT, etc.). Changes to the object need not then cause the whole place to need saving, and there’s less to save directly in the place itself. This also allows the same identical object to appear (in a wrapper) in multiple places, such that changes to the object made in one context are immediately visible to changes made in other contexts. Finally, these wrappers allow for the security regime to be different for the various underlying real, “interesting” objects within a single place. The down side is that this would mean more communication between (the imposter in) one interesting object (the place) vs the real object. I think this is equivalent to “far” references and communication between Tea Parties, and I don’t know what the performance implications are. I think textures and other big dumb commonly used objects are likely to be separate (“interesting”) objects, so that they can be shared. I also think the indirect wrapping of objects is important for applications. It seems to me that symbolic links are not often used by ordinary file system users because the benefit just isn’t worth the cognitive overhead of the new concept. How much context do you really get from a directory listing? Not much. On the Web, context is more important, and we have links, not copies, to other pages. We are also increasingly using portals to aggregate content, which allows a symbolic link to be created to another site such that we can see the content of the other page directly within the aggregated context instead of within its original context. I think it’s going to be that much more important in Croquet for you to be able to see and work with an object in one context (a place) while I work simultaneously with that same object in another context.

If the performance tolerates it, we could even split up every object: make every object “interesting”, with its own stable handle and its own separately accessible storage. But this would mean that all object references are “far” references, which doesn’t feel like a good idea to me. Another trick when using DHTs might be to not treat each interesting object as a single serialization to be split into uniform sized blocks, but to instead treat each persistable property as the key in the DHT, and the serialization of the value as the data to be stored. This would allow us to store only a value that has changed instead of storing the whole object. Also, it lets us take advantage of whatever distributed First-Order Predicate Logic engines are developed for semantic Web activities, and lets them take advantage of Croquet-developed data. The unification is object=DHT=RDF:thing, handle=key=RDF:property, value=value=value. Searches/computations over RDF stores become DHT searches of the Croquet data.

We need unshared objects (e.g., a private place) to be useable without being connected to the Internet. This happens automatically (for unshared objects) with the DHT model, but can be achieved in any case with a local cache. This is also desirable for performance in retrieving shared objects over a network. If we cache everything (shared or not), then we need a way to resolve discrepancies. Same thing for replicated blocks in a DHT, or replicated partitions in a distributed database. I think the normal Croquet commit mechanism can do this for us. Maybe for uncommitted histories, the objects messages of different objects can simply be entered into the normal queue, and the normal Croquet commit process merges them. I’m not sure whether Tea messages are defined in terms of acting on a particular last committed state. If they’re not, maybe we can use this to remerge even committed states (e.g, you work on something while disconnected, and then rejoin the party).

Another thing about the local cache is that whatever means is used to search it ought to be functional when disconnected from the network. If the local cache really keeps a copy of everything we are now using (or used last session, or since the cache was cleared,…) then the search mechanism (whether SQL or DHT based, or whatever) could be run locally first (with local answers presented immediately), and then augmented through an asynchronous network search if connected. If the persistent store is distributed among the peers anyway, then this doesn’t require any additions as to what software is required on each peer. Regardless, I’m not sure what to do to allow searching of places that I have not joined. Your group may have content that I would be interested in if I knew about it, and after I find out about it I might ask you if I can join. In a centralized database world, the server is a trusted third party that might get to search the data of all those subscribed to it, but I wouldn’t find out about things on servers in other places unless your institution and mine had worked something out, which isn’t likely to happen at the individual group level. Messy. It might be easier to create a limited use wrapper for our objects and publish them in a public place shared by everyone. This wrapper would provide searching capabilities but view and copy and other operations might not be present.

This should be the point where I explain how nothing actually refers directly to the stable handle, but is instead indirected through a secure nickname that is defined relative to the place in which the reference occurs. Versioning (“newest”) can be done through this indirection. If code (class objects and their methods) is like all other interesting objects, then we can have different (wrapped) application objects use different versions of a class, even when (their wrapper/imposter is) in the same place. I should explain how verification of credentials and auditing can be done on object retrieval or during resolution of local names, the latter because they can be unique to each user in the place (unlike the stable names). Per user nick names can be revoked. The stable names handed back during resolution can be cryptographically signed, as can the objects retrieved from server or DHT. But I haven’t figured out how any of that works yet.

I should also say that visiting a place (and joining the DHT corresponding to that place) involves a rendezvous in which your Croquet host needs to present a name and have it resolve to something that gives it enough information to find a host in that place/DHT. But this is already long, I’m tired, and the details might depend on the name resolution/security that I don’t yet have a handle on, so to speak. But I do want to note that the combination of rendezvous and name resolution gives us a nice hook to introduce different mechanisms for secure persistence. We can implement something simple now, and folks can define their own rendezvous and resolution mechanisms with different choices for some of the things I’ve described, yet it should all work together. Croquet will define an extensible rendezvous protocol, which bootstraps an extensible persistence protocol (with recovery of code and data), which bootstraps the applications. Croquet™ will define this initial core (but extensible) protocols for each of these three. This is somewhat analogous to having a generic URI mechanism that can be extended with different schemes.