Soil: serializing a graph

In the last post we turned a single object into a self-describing stream of bytes and read it back. That was the easy half. Real objects don't live alone. They point at other objects, those point at more, and before long you have a graph. Sometimes that graph shares a node from two places, and sometimes it points back at itself in a cycle. This post is about writing such a graph to bytes without writing anything twice and without looping forever.

Why the naive way breaks

The obvious approach is to serialize an object by serializing each of its fields, and each field is an object, so you serialize its fields too, all the way down. This is just walking the graph, and it works right up until the graph stops being a tree.

Two things break it. If two objects both reference the same third object, walking naively writes that third object twice, and when you read it back you get two separate copies where there used to be one shared object. Worse, if the graph has a cycle, an object that eventually references itself, the walk never terminates. It follows the reference, comes back to where it started, follows it again, forever.

A graph with a shared node and a cycle, the object table that indexes it, and the resulting byte blob with references by index

*The same walk, done properly: each object gets an index the first time it's seen. A second reference to it is written as "reference number n" instead of the object again.*

Giving every object a number

The fix is to remember what you've already seen. As we serialize, we keep a table that maps each object to a small number, assigned in the order we first meet it. The whole table is this one method:

SoilObjectTable>>add: anObject
	^ table at: anObject ifAbsentPut: [ table size + 1 ]

The first object we see becomes 1, the next new one 2, and so on. Now serialization has a decision to make for every object it reaches: have I seen this one before? Every object answers the same way, by asking the serializer to register it:

Object>>soilSerialize: aSoilSerializer
	aSoilSerializer
		registerObject: self
		ifAbsent: [ self soilBasicSerialize: aSoilSerializer ]

If the serializer has seen the object, it writes a short internal reference, just the object's number, and stops. If it hasn't, it runs the `ifAbsent:` block, which does the real work of writing the object's contents, exactly the per-object serialization from the last post. A shared node is therefore written in full the first time and as a number every time after. The duplicate problem is gone.

Reading a cycle back

Cycles need one more idea, and it's on the reading side. When the materializer reads an object, it registers that object in its own table *before* it fills in the fields. That order is the whole trick.

Picture an object A whose field points to B, and B points back to A. Writing is fine: we write A, and while writing A's field we reach B, write B, and while writing B's field we reach A again, which is already number 1, so we write the reference "1". Reading has to mirror this. We create A, register it as 1, and only then start reading its field. Reading the field creates B, registers it as 2, and reads B's field, which is the reference "1". Because A was registered before we descended into its field, "1" resolves to the A we already have, half-built but present, and the cycle closes onto the same object instead of a copy.

This is why the materializer is strict about registering objects in exactly the same order, and before populating them, that the serializer used. Get the order wrong and cyclic graphs quietly fall apart.

Where the order comes from: class layouts

I've been saying "the order" as if it were obvious. It isn't ad hoc, it comes from the object's *class layout*, the same thing from the first post. A `FixedLayout` walks the named instance variables in their defined order, a `VariableLayout` walks the indexed elements in order. The layout defines the walk, and because the same layout drives both writing and reading, the two directions agree on the order automatically. That agreement is exactly what the register-before-populate trick relies on.

This layout-driven path is a single type code. Soil calls it type 1: reach any ordinary object with no special handling and it is written as type 1 followed by whatever its layout dictates. The generic serializer is just this delegation:

Object>>soilBasicSerialize: serializer
	"Delegate serialization to the class layout"
	self class classLayout soilBasicSerialize: self with: serializer

That one mechanism covers essentially every class you will ever store, including your own, without Soil knowing anything about them. Every other type code is a deliberate exception: a custom serializer that overrides this path because the generic form would be wrong or wasteful. They come in two flavours.

The first is immediate values. A `SmallInteger` is an *immediate value*, the term for an object that isn't a heap object with a layout to walk but whose value lives right in the reference itself. There is nothing to traverse, so its serializer just writes the value. Characters and small floats are immediate values too.

The second is efficiency. Take a `String` through the generic layout and it is a `VariableLayout` collection of character objects, each character potentially costing several bytes. That is correct but silly. So `String` overrides the layout path and writes one UTF-8 byte array instead, the type-21 encoding we saw last time:

String>>soilBasicSerialize: serializer
	serializer nextPutString: self

Because the generic path follows the layout, it handles ordered structures perfectly: arrays, ordered collections, your own objects. The one place it gets fuzzy is hash-based collections like `Set`, whose internal arrangement follows hashing rather than any meaningful order. Soil doesn't hand `Set` a custom serializer, and it doesn't need to worry much, because a set doesn't depend on element order in the first place. Structures where order or rehashing does matter, like `Dictionary`, do get their own handling.

Not everything should be one blob

We can now serialize any connected graph as one unit. Soil calls such a unit a *cluster*: a group of objects written together as a single blob of bytes. The word will keep coming back, because clusters are what transactions and versioning operate on later in the series.

But "any connected graph" is a trap if you take it literally. In a live system almost everything is reachable from almost everything else. If a cluster swallowed the entire reachable graph, loading one small object would drag half the database into memory with it. That defeats the point of a database, which is to read only what you need.

So a graph is deliberately cut into several clusters. Most references stay *inside* a cluster and are the internal, by-number references we just built. But some references cross from one cluster to another. Those are *external* references, and they are stored differently: not as the target's contents, and not as a local number, but as the target object's identity, an id that says "the object living over there". What that id actually is, and where the clusters physically sit on disk, is the next post. For now it's enough that a cross-cluster reference is stored as a stable pointer to another cluster, not as the cluster itself.

Two clusters: cluster A holds an external reference stored as an id; on read it becomes a proxy that loads cluster B only when touched

*An external reference is read back as a proxy. The second cluster stays on disk until something actually sends the proxy a message.*

Proxies: paying only when you touch

Here is the nice part. When we read a cluster back and hit an external reference, we do not load the target. We put a *proxy* in its place. A proxy is a small stand-in object that knows only one thing: the id of the real object it represents.

The proxy is built to be invisible. In Pharo you can make an object that has almost no methods of its own by subclassing `ProtoObject`, and then catch every message sent to it:

SoilObjectProxy>>doesNotUnderstand: aMessage
	^ aMessage sendTo: self soilRealObject

`soilRealObject` is where the actual loading happens, and it happens once. The first time anyone sends the proxy any message, the proxy fetches the real object from its cluster, caches it, and forwards the message to it. Every later message goes straight to the cached object. From the calling code's side nothing looks unusual: you send `customer name` and you get the name, whether `customer` is the real object or a proxy that quietly loaded it a moment ago.

This is lazy loading, and it is the mechanism that makes the clustering worthwhile. You read one cluster, you get its objects fully, and its links to the rest of the database are proxies that cost nothing until you follow them. Walk deeper and each step loads the next cluster on demand. Read a small object and touch nothing else, and nothing else is read.

Where this leaves us

We can serialize an arbitrary object graph, cycles and shared nodes included, into a cluster, split a large graph into several clusters connected by external references, and load those clusters lazily through proxies so a read only pulls in what it touches.

Two things are still hand-waved. External references are stored as an "id", but I haven't said what an id is or how it's laid out. And I've talked about clusters "on disk" without saying where on disk, or how you find a cluster from its id. That is the object heap, and it's the next post.

The code is on github if you want to read ahead.