Commits and History

A tree root names one state of the facts. To go from one state to the next, an app makes a commit. This chapter follows Bob as he checks the eggs off the list, and looks at everything his commit leaves behind.

Two questions drive the design. When Bob’s change reaches Alice, how does her replica know whether it has already seen it? And when Bob asserts that the eggs are done, superseding done false, how does Alice know that her own copy of done false is the one his change removes, and not a newer one she wrote since? Both answers come from giving every change a version.

Who is writing

Every commit is written by someone, on some branch, of some replica. Dialog names each of these with a hash of the level above:

• A replica is one peer’s copy of a repository: the hash of the repository’s DID and the peer’s DID.
• A branch is a named line of work in a replica, like main: the hash of the replica and the name.
• An origin is one writer on one branch: the hash of the branch and the key that signs the commits. That is the peer’s own key when the peer writes as itself, and a session’s key when it writes through a session (see Identity and Capabilities).

An origin writes one commit at a time, in order, never two at once. Everything below depends on that.

Versions

A version is a pair: an origin, and an edition.

The edition counts depth, not writes. A commit’s edition is its parent’s edition plus one. A merge’s edition is the larger of its parents’ editions, plus one. So when Bob pulls Alice’s two commits and then makes his first, his first commit is already edition 2:

Editions give a rough sense of order that every replica agrees on without a clock. Versions compare by edition first, then by origin, so any two versions have a definite order.

What a commit writes

Bob’s commit asserts done true on item:2. The done flag is read under last, so the assertion supersedes the fact such a read returns, done false. Every entry the commit writes carries its version, (oB, 2). Here is all of it:

The fact keys. The new fact goes into EAV, AEV and VAE, as in the Keys chapter. Its payload records the version that wrote it. The old fact, done false, is removed from all three. Had the item held a second done flag that a read did not return, that one would have stayed (see Facts).

A history record. Under tag 03, the commit writes one record for each fact it changed. The record’s key starts with the origin and then the edition, so each writer’s records sit together, in edition order. Its payload lists the versions this change supersedes. Bob’s record says “at (oB, 2), item 2’s done became true, superseding what (oA, 1) wrote.” A retraction writes a record too, marked as a retraction.

A coverage record. A record that removed something, a retraction, or an assertion that superseded at least one earlier version, is copied under tag 05, keyed by version and by the hash of the value rather than the value itself. The coverage region holds nothing but removals, so a replica can list every removal since it last synced without reading the much larger history of assertions. A graft merge (see Sync) relies on exactly that.

A revision record. Last, the commit writes one fact about itself: attribute dialog.db/revision, on an entity derived from the version. Its value is a signed record naming the commit’s parent versions, its issuer, and links further back for fast ancestry walks. So the tree also holds the commit graph.

The fact indexes answer what is true now. The history region answers what happened. Both live in the same tree, under the same root.

The head

The commit then seals the tree and writes the new blocks (see Blocks and Storage). At that point the commit is staged: it exists, but no reader of the branch sees it yet. Publishing it moves the branch’s head. The head is a small signed record in a cell named branch/main/revision. It holds:

• the branch,
• the issuer, the key that signed it,
• the tree root,
• the edition,
• a marker saying its watermark, described below, is in its tree,
• the signature over all of the above.

These are the bytes the signature covers:

The head is updated with compare-and-swap. Bob’s replica says “move the head from the revision I built on to this new one.” If another commit moved it first, the swap fails with a version mismatch and nothing is lost: Bob’s blocks are stored, and the app runs its change again on the new head.

The watermark

The watermark says, for every origin, how far into that origin’s commits this head has seen. It is a map from origin to two numbers: the highest edition seen, and how many of the origin’s commits that covers.

Because an origin writes one commit at a time, “everything up to edition 3” is an exact description of what the head has seen from oA. So the question “has this head seen version v?” is one lookup: v is seen when its edition is at most the watermark’s edition for its origin.

A watermark has one row per origin that ever wrote into the history, and rows are never removed: a device that commits once and is never seen again keeps its row. So the watermark is not carried on the head at all. It is written into the tree itself, in a small region of its own with one entry per origin, and the head only says that it is there.

The region skips one row: the head’s own. That row says where the current writer’s run of commits began, and a reader brings it up to date from the head, because each commit in a run adds exactly one edition and one commit. So a writer committing on top of its own head writes nothing to the region. A commit on another writer’s head writes two rows, the other writer’s (its run has ended) and its own, and a merge writes the rows its two sides disagree on.

That one question answers both questions from the start of the chapter. When a change arrives that the receiver has already seen, it can be skipped. And when a fact arrives from another replica that the receiver has seen and no longer holds, the receiver knows it was removed on purpose, not missing, and does not bring it back. Deleted facts need no tombstone in the fact indexes. The Sync chapter shows this in action.