The Search Tree

Every key from the last chapter goes into one sorted sequence. Alice’s grocery list is small, but a real repository holds millions of keys. Dialog stores that sequence as a tree of nodes, so that finding one key reads a few nodes rather than all of them.

The tree has one property that everything else in Dialog leans on: the same entries always make the same tree. An entry is a key and the small payload stored with it. It does not matter in what order the entries were added, or who added them. Two replicas holding the same entries in canonical form hold byte-for-byte identical trees, with identical hashes at the top. The rest of this chapter explains how the tree gets that property, what it buys, and when Dialog chooses to give it up for a while.

Cutting the sequence into leaves

To keep the pictures small, pretend the keys are just grocery names. In a real tree each of these is a full EAV, AEV or VAE key.

The sorted sequence is cut into runs, and each run becomes a leaf node. The question is where to cut. A B-tree cuts when a node gets full, which depends on the order things were inserted. Dialog instead lets each key decide for itself, with a coin flip that always lands the same way for the same key:

The coin is the key’s BLAKE3 hash. Dialog reads the first 8 bytes of the hash as a number between 0 and 2⁶⁴, and cuts after the key when that number falls below a threshold. Since the hash of a key never changes, neither does its draw. Given the same entries around it, butter cuts after itself on every replica.

The threshold depends on how heavy the entry is. An entry weighs its key’s length in bytes, plus the size of its payload, plus a fixed overhead of 64. The chance of a cut after an entry is its weight divided by 65,536. A typical fact entry weighs a few hundred, so the coin fires after roughly one entry in a few hundred. Heavier entries are more likely to end a leaf, so leaves average about 64 KiB of weight no matter how big their entries are.

Separators and index nodes

Leaves need a parent that says which leaf holds which keys. For every cut, Dialog writes a separator: the shortest prefix of the first key after the cut that still sorts above the last key before it.

Real keys share long prefixes. The last key of one leaf might be the EAV key for item:1 and the first key of the next the one for item:2. Those differ only at the seventh byte, so their separator is the seven bytes 00 69 74 65 6d 3a 32, which reads as a zero byte followed by item:2. A separator is almost always much shorter than the key it stands for, which keeps parent nodes small.

An index node holds a list of links, one per child. Each link has the child’s separator, the child’s hash, and a one-byte estimate of how big the child’s subtree is, which the query planner uses. Here is Alice’s tree, with a root index node over four leaves:

To find oats, a reader starts at the root. oats sorts after m and before r, so it follows the third link, fetches the node with hash 07de…, and finds oats inside it.

Index nodes are cut into groups the same way leaves are. Each separator flips its own coin, from its own hash. A link weighs its separator’s length, plus the 32-byte child hash, plus 16 bytes of overhead, and its coin fires with probability weight / 65,536. A link whose coin fires starts a new index node, and its separator becomes that node’s separator one level up. The first four index levels each draw from a different 8 bytes of the separator’s hash, and a separator cuts a level only if it also fired at every level below, so one lucky separator does not cut every level at once. Short separators mean light links, so a single index node holds hundreds of them, and a tree three levels deep already covers a very large repository.

Why the order does not matter

Every cut depends only on the entries at that point: their hashes and their weights. Nothing depends on what was inserted first. So Alice and Bob can build the list in completely different orders and still end up in the same place:

A node’s hash covers its whole content, including the hashes of its children. So the root hash covers everything. If two roots are equal, the two trees hold exactly the same keys. If two roots differ, a reader can compare them link by link, skip every child whose hash matches, and descend only where they differ. That is how two replicas find what they disagree about without reading everything they agree on. Sync is built on this.

Changing the tree

A node is never changed in place. To add pasta, Dialog reads the path from the root down to the leaf where pasta belongs, writes a new copy of that leaf with pasta in it, and then a new copy of every node above it, since each parent must point at its child’s new hash:

Everything off the path is untouched and reused. An edit to a tree with millions of keys writes a handful of new nodes. The old root still names the old tree, whole and readable, which is what makes history cheap (see Commits and History).

After the edit, Dialog re-checks the coins along the new path. If pasta’s own coin had fired, leaf 3 would have split in two. The tree after an edit is exactly the tree a fresh build from the same keys would give.

A few safety valves

Coin flips are fair on average, but some key sets are not. Three rules keep the tree well shaped anyway:

• No huge separators. If two neighboring keys share their first 512 bytes, a separator between them would be over 512 bytes long. Such a spot is vetoed: its coin never cuts, at any level. Only the next rule may split there, at the leaf level, with a deliberately long separator that never cuts an index level.
• No endless leaves. A run where cuts were forbidden and that grows heavier than 65,536 is split anyway, at a spot chosen deterministically from the keys, so every replica picks the same spot.
• A hard ceiling. Any run between coin cuts that is heavier than three times 65,536 is split at allowed spots, where there are any, even if no coin fired.

The numbers used above, 65,536 and 512 and 3, the entry overhead 64 and the link overhead 16, and the fanout setting 8 behind the 256 below, are the tree’s format. They are the defaults, and every node records which values its tree uses. The Nodes chapter shows where.

Buffered writes

As Changing the tree showed, changing one fact rewrites every node on the path from its leaf up to the root: each node on that spine gets a new hash, so each is written again. When facts arrive a few per commit, every commit pays for a whole spine, and a commit that touches facts in several places pays for several. So by default, a commit does not push its changes all the way down. It parks them in a buffer in the root, on the link that leads toward where they belong:

Reads look at the buffers on the way down and merge what they find with what the leaves hold, so a buffered write is visible immediately. When the buffers on one node hold more than 256 operations, or more than 64 KiB of weight, the heaviest of them are pushed one level down until the node is back under half that limit. Over time, every operation reaches the leaves. Both limits come from the tree’s format: 256 is 2⁸, the format’s fanout setting, and 64 KiB is its node size target. A commit then rewrites the root, plus whatever nodes a flush reaches, instead of a whole spine for every change.

Why buffer by default

Giving up the canonical form sounds like a steep price, since it is what lets two replicas holding the same facts recognize each other at the root. But that is rarely how replicas meet. It is unlikely that two peers start from nothing, insert the same facts in different orders, and then sync. The usual case is the grocery list: Alice and Bob start from the same tree, each adds a few facts of their own, and then they reconcile.

In that case what matters is how many blocks differ between their trees, because every differing block has to be exchanged. With canonical edits, each new fact rewrites the spine from its leaf to the root, and facts that land in different parts of the tree rewrite different spines. With buffering, the new facts sit in the root, and everything below it is still the base both replicas started from. Here Bob adds two facts that belong in different leaves:

So replicas that have diverged a little sync by exchanging a root or two, rather than a path of nodes for every change. The rare case where replicas diverge a lot, such as importing a large dataset, is where the canonical form earns its keep: a bulk import pushes every buffer down once when it finishes, and an app can ask for the canonical form on any commit that needs it.