Nodes

The last chapter drew nodes as boxes. This one opens a box and looks at its bytes.

A node has to answer two questions before anyone can use it. The first is how do I read you? A reader must know the node’s layout before it can make sense of anything inside it. The second is what tree are you part of? The tree’s format, its node size target and the other numbers from the last two chapters, decides where keys go. A reader that guessed those numbers wrong would look for keys in the wrong places.

Dialog answers both questions at the front of every node. A node starts with a short prelude, then its body:

It works like an HTTP message: a fixed opening line, a few headers, then a body of plain bytes.

The prelude

The prelude has four parts:

• version says how to read everything after it. The layout described here is version 02.
• kind says what the body is: 00 for a leaf, 01 for an index node.
• header length is the number of bytes of manifest fields that follow, so a reader can skip them without understanding them.
• manifest fields hold the tree’s format, as a list of settings.

After the fields come zero bytes, up to the next multiple of 16. The body starts right after, on a 16-byte boundary, because the body is read in place and needs that alignment.

Here is the whole prelude of a leaf in a tree created today:

There is one field, three bytes long. A setting equal to its default is never written, and a new tree differs from the defaults in one setting: value_encoding, which says how values are written in keys. Its value is 1, which names the encoding the Keys chapter described.

So every node of every new tree starts with the same 16 bytes, give or take the kind byte. A reader uses the kind byte to validate the body as a leaf or an index, then checks the 16 bytes with a single comparison.

Numbers in the prelude

Every number in the prelude is written as a bijou64 varint. Small numbers take one byte. Bigger numbers take a marker byte that says how many bytes follow:

The ranges are offset so they never overlap: f8 00 means 248, not 0. So every number has exactly one encoding. That matters more than it looks. A node is named by the hash of its bytes (see Blocks and Storage), so if the same number could be written two ways, the same node could have two names.

The manifest fields

Each field is three things in a row: a code saying which setting it is, the length of its value in bytes, and the value. The field above is 05 01 01: code 5 (value_encoding), one byte long, value 1. Here is a leaf from a new tree that also sets its fanout to 4:

The new field is 02 01 04: code 2 (fanout_n), one byte long, value 4. It comes first, because its code is smaller. The header length says 6, and seven zero bytes pad the prelude out to 16.

Codes come from a public table. These are the ones defined today:

A few rules keep the fields canonical, so the same format always gives the same bytes:

• Codes appear in ascending order, each at most once.
• A field equal to its default is left out.
• Every length is exact, and every number uses its one bijou64 encoding.

A reader refuses a node that breaks any of these rules. A node that spells out a default, for example, is not a valid node, even though a lenient reader could make sense of it.

The table only ever grows. A code is never reused and a default never changes. Changing a default would silently change the meaning of every node that left that field out. A new default is a new field with a new code.

Fields a reader does not know

Suppose Bob’s phone runs a newer build of Dialog than Alice’s laptop. Bob’s build knows a setting Alice’s build has never heard of, and Bob creates a tree that uses it. What should Alice’s build do with that tree?

Every setting is one of two kinds:

• Recommended settings only shape the tree: they move where the cuts fall. A build that does not recognize one does not follow it. Alice’s build still keeps the field and writes it back into every node it edits, so it does not strip Bob’s setting from his tree. Its edits may come out shaped a little differently from the canonical tree, which costs some extra work when replicas compare trees, but never loses a fact.
• Required settings change how bytes are read. inline_n, spill_prefix and value_encoding decide how a value is laid out inside its key, and a reader that ignored them would build different keys and miss facts. A build that does not recognize a required setting is not compatible with the tree: it refuses to read it and needs to be updated.

A build that has never seen a code cannot look up which kind it is, so the code itself says: even codes are recommended, odd codes are required. inline_n (01), spill_prefix (03) and value_encoding (05) are the required settings today. Here is a leaf from a new tree that also changes one setting of each kind:

The three fields take 13 bytes, so this prelude fills its 16 bytes exactly and has no padding.

Within this layout, the only setting that can lock out an older build is a required one the tree actually uses. Trees that use only recommended settings stay readable by every build that reads this layout. A new layout version or node kind would lock older builds out too, which is why those are reserved for changes that need it.

Reading a node

A reader is strict. The version must be known, every length must fit, the fields must be sorted and canonical, the padding must be exactly zero, and the body must validate as the kind of node the prelude names. A node that fails any of these checks is not a valid node.

A tree’s nodes all carry the same field bytes, so a reader decodes them once and remembers the result by those bytes. After the first node of a tree, reading its format is usually one lookup.

The body

The body is the node itself, stored with rkyv so that its structure can be read in place without copying. A leaf’s compressed keys are decoded as they are read. The body’s shape depends on the kind:

• A leaf stores its keys column by column. In an EAV, AEV or VAE leaf, each key is split into its parts, tag, entity, attribute, value type and value, in its index’s order, and each part gets its own column. A history leaf keeps whole keys in a single column. A column where the same few values repeat, like the attribute column, becomes a small dictionary plus an index per entry. A column of mostly distinct values, like entities, is front-coded: each entry stores only how much it shares with the previous one and the bytes that differ. The payloads come after the keys, one per entry.
• An index node stores the prefix its separators share once, then the rest of each separator and where each one ends, then the child hashes, then the one-byte size estimates, then any buffered writes, grouped by the link they ride on.

The empty tree

An empty tree still has a format, so it is still a node: a leaf with no entries, carrying the manifest like any other. For a new tree that is the 16-byte prelude above and an empty leaf body. It is only ever a root. The first insert replaces it.