Soil: turning an object into bytes

A few years ago I wrote two posts about building an object database from scratch, BYOB - build your own (data)base and BYOB - object serialization, and then went quiet and just built the thing. Soil is real now: a file-based, transactional object database for Pharo, running in production. I want to go through its architecture properly this time, from the beginning, and this is the beginning.

Before a database can do anything interesting, it has to do one boring thing well: take an object that lives in memory and put it on disk as a sequence of bytes, then read those bytes back into the same object. Disks only store bytes. So everything else, transactions, indexes, recovery, all of it sits on top of this one operation. Let's get it right.

*The job in one picture: turn a live object graph into a flat, self-describing byte stream, and read it back into objects. We start with the simplest possible case, a single object, and build up from there.*

I'll assume you've used a database before but know nothing about Soil or much about Pharo. Where Pharo matters, I'll explain it.

What an object actually is

To turn an object into bytes we first need to know what we're dealing with. In Pharo, when you hold an object you hold a *reference* to it. The interesting part is that not every reference points somewhere.

Pharo has no primitive types. "Everything is an object" is meant literally: integers, floats and characters are objects too. That sounds wasteful. The integer `1` carries one bit of information, and putting it somewhere in memory with a full object header pointing to its class would be absurd. So Pharo doesn't. A reference has a few tag bits, and for small integers, floats and characters the value is encoded directly in the reference itself. The class comes from the tag, the content comes from the reference. These are called *immediate* objects. The virtual machine hides the trick, so `1 class` still answers `SmallInteger` as if it were a normal object.

Everything else is a *heap* object: the reference holds an address, and at that address you find first a reference to the object's class, then its contents. How the contents are laid out is decided by the class's *layout*. The two you'll meet most are `FixedLayout`, for objects with a fixed set of named instance variables, like a C struct, and `VariableLayout`, for collections whose size can change. There are others (weak, ephemeron), but those two carry the idea.

This split matters for serialization. An immediate object we can write by just writing its value. A heap object we have to walk: write which class it is, then write each of its parts.

Why not just copy the memory

The obvious idea is to copy an object's bytes straight out of memory onto disk. It doesn't work. The bytes in memory are full of references, and a reference is a memory address that will be meaningless the next time the image starts. The layout is a Pharo implementation detail. And the format wouldn't survive the object changing shape later.

What we want instead is a format that is self-describing: bytes that carry enough information to rebuild the object without knowing anything in advance about what was written. That means, for each thing we store, encoding *what* it is alongside *the value*.

Type, length, value

Structured data can be encoded as text or as binary. Text is human-readable, but it needs delimiters, and then you have to escape the delimiters when they appear in the content, and that is fiddly and slow. Nobody is going to hand-edit a database file, so we use binary. The format Soil uses is the one I keep coming back to as the simplest that works: *type - length - value*.

Type is a single byte, a tag that says what the value is: a string, an array, a date, and so on. One byte is plenty; we are never going to have hundreds of these.

Value is just the raw bytes of the content. Because we never interpret them as anything but bytes, anything can go there.

Length is the number of bytes in the value, and it is the interesting one. If you spend a fixed small number of bytes on it, you cap how large a value can be. Spend a fixed large number, and you waste space on the many small values. Soil avoids the choice with variable-length encoding: it uses the most significant bit of each length byte as a "there's more" flag. As long as the high bit is set, another byte belongs to the length. So small lengths take one byte, large lengths take as many as they need, and there is no ceiling.

Reading it looks like this:

nextLengthEncodedInteger
	| value |
	value := self nextByte.
	(value < 128) ifTrue: [ ^ value ].
	^ (self nextLengthEncodedInteger bitShift: 7) bitOr: (value bitAnd: 127)

and writing is the mirror image:

nextPutLengthEncodedInteger: anInteger
	anInteger < 128 ifTrue: [ ^ self nextPutByte: anInteger ].
	self
		nextPutByte: ((anInteger bitAnd: 127) bitOr: 128);
		nextPutLengthEncodedInteger: (anInteger bitShift: -7)

The type codes

The type byte needs to mean something on both ends. Soil keeps the mapping in one place, in a shared pool called `SoilTypeCodes`, so the numbers aren't scattered as magic constants through the code. One direction maps a symbol to its byte, the other maps a byte back to the class (or a small block) that knows how to read it. So on writing we look up the code for what we have, and on reading we look up the reader for the code we find. The string type, for instance, is code 21.

There are codes for the types you'd expect, arrays, ordered collections, byte arrays, strings and symbols, associations and dictionaries, dates and times, floats, fractions, characters, large integers, and a few more. Deliberate gaps are left in the numbering for future types.

Storing a string, concretely

Let's serialize the string `'soil is ramping up'` and see the bytes.

A string in Pharo is a collection of characters, and characters are immediate objects, so the fully generic path would store the collection's class, then its size, then each character one by one. That is correct but wasteful and, for wide characters, awkward. A string has a much better representation: encode it as UTF-8 and store the resulting bytes. So Soil handles strings specially, writing the string type code and then the bytes:

SoilSerializer new
	stream: stream;
	serialize: 'soil is ramping up'

gives

#[21 18 115 111 105 108 32 105 115 32 114 97 109 112 105 110 103 32 117 112]

You can read it straight off. `21` is the type code for a string. `18` is the length, the string has eighteen characters. The rest is the UTF-8 bytes: `115` is `s`, `111` is `o`, and so on. Type, length, value.

Reading it back reverses the path. The materializer reads the first byte, looks up `21` in the mapping to learn it's a string, and hands off to the string reader, which reads the length and then that many bytes:

SoilMaterializer new
	stream: bytes readStream;
	materialize

and we get our string back:

soil is ramping up

Wide strings, the ones that contain characters outside the Latin-1 range, get their own type code and their own path, but the shape is the same: a type byte, a length, and the encoded bytes.

Where this stops

We can now turn a single object into a self-describing sequence of bytes and read it back. That is genuinely most of a minimal database: open a file, write the bytes, and with a known filename you can write and read one object. In the old series I called this "almost a database", and it is, in the same way a single brick is almost a house.

The thing it can't do yet is the thing that makes an *object* database interesting. Real objects don't live alone. They reference other objects, which reference others, until you have a graph, and that graph can have cycles. Writing one object is easy. Writing a graph without writing the same object twice, or looping forever, or dragging half the image onto disk when you only wanted one model, is the actual problem. That's the next post.

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

Part 1 of 2 in the Soil series.  · next part -->