Automerge Binary Document Format

• Spec Website
• The Automerge compressed binary document format spec
• Authors
  • Alex Good
  • Andrew Jeffery

Notes

Automerge is an operation-based CRDT that models concurrently editing a JSON document. This means that there are lot of little changes. In their uncompressed form, this often leads to a lot of change metadata overhead. The goals of this spec is to compress those changes to as small of a representation as possible by taking advantage of how people actually write JSON in practice (i.e. in a linear sequence of changes).

At its core, this is a columnar format with larger data lke hashes extracted into indices. I don’t think that anything prevents these from describing broken or circular documents, but this will be discovered during decompression.

Types

$$\begin{array}{rlrlr}\text{Typ}& \tau & ::=& scalar|object& \\ & scalar& ::=& \text{null}& \\ & & |& \text{bool}& \\ & & |& \text{u64}& \\ & & |& \text{i64}& \\ & & |& \text{f64}& \text{IEEE-754}\\ & & |& \text{string}& \text{UTF-8}\\ & & |& \text{bytes}& \\ & & |& \text{timestamp}& \text{Unix time in ms}\\ & object& ::=& \text{counter}& \\ & & |& \text{text}& \text{UTF-8}\\ & & |& \text{list}& \text{list of }\text{term}\text{s}\\ & & |& \text{map}& \end{array}$$

Action

Actions are a sum of op types supported by Automerge. These are rougly the AST leaves.

$$\begin{array}{rlrlrl}\text{Action}& \Delta & ::=& \text{makeMap}& \text{0x00}& \\ & & |& \text{set}& \text{0x01}& \text{Overwrite a collection element or edit rich text}\\ & & |& \text{makeList}& \text{0x02}& \\ & & |& \text{del}& \text{0x03}& \text{Opposite of }\text{set}\\ & & |& \text{makeText}& \text{0x04}& \\ & & |& \text{inc}& \text{0x05}& \end{array}$$

Layout

┌─────────────────────┬──────────────────┬──────────┬──────────┐
│      Magic Bytes    │     Checksum     │Chunk Type│  Length  │
├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ──│─ ─ ─ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─│─ ─ ─ ─ ─ ┤
│ 0x85 0x6f 0x4a 0x83 │ Truncated SHA256 │   Enum   │ ULEB-128 │
├─────────────────────┴──────────────────┴──────────┴──────────┤
│                                                              │
│                                                              │
│                           Content                            │
│                                                              │
│                                                              │
└──────────────────────────────────────────────────────────────┘

NOTE

I think that the spec uses the terms “chunk” and “block” interchangably. I’ve used “chunk” everywhere in these notes for consistency, but there may be some distinction that I’m just not picking up on.

Chunk Type

The chunk type field contains the following enum:

Tag	Meaning	Description
0x00	Document Chunk	Graph of related changes
0x01	Change Chunk	Single “change” (many ops)
0x02	Compressed Change Chunk	Same as 0x01, but DEFLATE compressed

Content

Based on the Chunk Type, the Content (payload) section is laid out differently.

Document Chunk

Documents represent the entire(?) causal history

Change Chunk

A “change” is perhaps better described as a “commit”. The distinction is that it may contain arbitrarily many ops, but they’re considered to be related. Also like a commit, a “change” does not include the entire document history.

Compressed Change Chunk

The same as Change Chunk, except compressed with DEFLATE.

Questions

Documenting both for my own understanding, and to provide (hopefully) helpful feedback to Alex for the next update of the spec.

• Why these three specific chunk types?
• Purely out of curiosity: how were the magic bytes derived?
• I assume that the Heads Index only contains the minimal set of hashes, not hashes for every change
  • Per the name, this would only need to be the latest (concurrent) heads
• Document Chunks: the name may be confusing
  • Do these always contain the entire document, or can they be the entire document broken into e.g. TCP packets?
• Was it called a “change” instead of a “commit” because there’s no required commit message?
  • FWIW, I find this terminology confusing (I’ll get over it, but it’s not immedietly clear)
    • $\because$ each op changes the document; I expected “op” and “change” to be synonyms
• Actions don’t include things like appending to text
  • Does Automerge not use something like RGA?
    • I can look this up myself, but I’d expect it to
    • Same w.r.t. the del action: are strings expressed as [Char], maybe?
  • ANSWER
    • Automerge uses rich text, which is likely Peritext
    • Based on the description in the Automerge docs, this is done with spans into existing strings, which means no need to track each keystroke