Difference between revisions of "Regolith"

Summary

Regolith is the layer of soil and large boulders between the solid Bedrock and the Topsoil. In terms of the architecture of the next generation of AboutUs software, Regolith is the low level distributed object persistence and user action framework that allows for the cool features of Topsoil.

Brandon CS Sanders is currently using this page as a scratchpad to think about Regolith as he develops the framework.

Collapsed

A collapsed object is the hash of an object that has been decomposed and serialized to a string.

Decomposition

Decomposition of objects allows you to have many compositional objects that share pieces. This is both a storage savings and it allows for the computation of back references. An essential feature of this is that the same expanded object always maps to the same collapsed object (hash).

Folded

Some objects such as Arrays and Hashes are themselves containers for other objects. During decomposition, the objects they contain must be collapsed and stored. Then a "folded" version of the original object is stored. The folded version replaces all top level objects in the container with the collapsed version of those objects.

One-to-one

It is essential that a particular set of object contents always collapses to the same hash. This makes it possible to determine when an object is part of several different compositional objects. This is the one-to-one property. A particular object always collapses to the same hash. Likewise, no other object with different contents collapses to that same hash.

Loops

When a data-structure has loops, there is a decompositional solution that maintains the one-to-one property, but that solution is effectively uncomputable. Other objects that want to point to one of the objects in the loopy data-structure need.

N-squared decomposition

For any loopy datastructure having N nodes, the storage complexity is N-squared. Basically you pick up the entire structure by each node in turn and write that node out while watching for revisits of a node that you already have written. Whenever you revisit a node that you've already written, you break the cycle with a self reference.

The collapse of the graph depends upon the order of traversal, so selecting a deterministic order is important.