aweft state format, v0

Status: draft. Normative, and not yet frozen.

This document defines how a change to observable state is described, grouped, and encoded so that an implementation in any language can produce and consume it. It is a specification with conformance fixtures, not a description of one library's behavior.

Keywords MUST, MUST NOT, SHOULD, and MAY are used in the usual sense.

1. Model

State is a graph of observables. Three kinds exist:

Every observable carries an id, unique within a document. Ids are how two replicas agree on which observable a change refers to without agreeing on where it sits in the tree.

A delta describes one change to one slot in one observable. A commit is a set of deltas that took effect together.

1.1 Attach edges and aliases

A slot may hold a reference to another observable, and every reference states which kind of edge it is:

• an attach edge means the observable lives there

• an alias names it without giving it a home

Every observable reachable from the root has exactly one attach edge. The attach edges form a tree, and the aliases are what make the whole thing a graph.

An implementation MUST refuse a commit that would give an observable a second attach edge. That includes a commit adding two attach edges to one observable, because deltas within a commit are unordered and there is no defensible way to choose between them.

An implementation MUST refuse a delta whose target has no path of attach edges from the root. Reachability is computed against the document before the commit, extended by the attach edges the commit adds. Attach edges the commit removes are not counted, so a commit may write into a subtree in the same breath as it detaches it.

Moving an observable is one commit that removes its old attach edge and adds the new one. Both happen together, so it is never in two places and never in none.

Rationale: one attach edge means "where does this live" has a single answer, computed by walking up rather than by searching. Without it the question is answered by enumerating an observable's paths, and with aliases in the graph that count grows past any budget: a document of 142 observables produced 36,507 paths, and one of about 2,000 exhausted a 4 GB heap. The consequence for the layer above is that a reference can neither widen nor narrow who may write what, which makes two classes of privilege bug unrepresentable. See docs/design/010.

1.2 An observable's kind is fixed

An observable is an object, an array or a map, and it is that one kind for as long as it exists. Nothing changes an observable's kind.

Every mention of an id therefore has to agree about its kind: the kind on a reference that names it, the kind implied by a ref addressing it, and the kind it already has in the document. An implementation MUST refuse a commit in which two mentions of one id disagree, including two deltas in the same commit that each introduce the id with a different kind.

Rationale: section 6.4 carries the kind on the reference so a receiver can read a delta about an observable it has not materialized yet. That only works if the kind is a fact about the observable rather than an opinion of whoever wrote the delta. Without this rule a commit can describe an id as an array in one delta and a map in another, and both readings are defensible, so two implementations diverge without either being wrong.

1.3 A detached observable leaves the document

When a commit removes an observable's last attach edge, and no delta in that same commit gives it another one, that observable and everything attached below it are no longer part of the document. An implementation MUST NOT answer for it afterwards: it is not in the document's contents, a delta naming it is refused as unreachable by the rule in 1.1, and it is not carried in any description of the document's state.

A later commit MAY attach it again, by id. That commit describes the observable exactly as it would describe one the document has never held: the attach edge, and a delta for every slot it is to hold. A receiver that has no observable by that id materializes a new one and applies those deltas to it.

Rationale: both ends of a link apply the same commits and hold no other channel, so a rule that lets one end remember what the other has forgotten is a rule they cannot both follow. Forgetting at the moment the edge goes, and describing the contents again on the way back in, is one rule with one reading. The alternative, remembering every observable a document ever held, makes a list that is filled and cleared grow without bound. See docs/design/084.

2. Deltas

A delta has a type, a target, and a value.

delta = {
	type : "add" | "replace" | "remove"
	id   : observable id        the observable the change happened in
	ref  : reference            which slot within it
	value: any                  absent for remove
}

2.1 Types

• add: the slot did not exist and now holds value.

• replace: the slot existed and now holds value.

• remove: the slot existed and now does not. value MUST be absent.

2.2 The target is id plus ref, never a path

An implementation MUST address a delta by the id of the observable and a reference within it. It MUST NOT address a delta by a path from the document root.

Rationale, measured: a delta produced by coalescing a remove and a re-add within one window can have no position in the tree at the moment it is described, because the observable it refers to was detached and reattached during the window. Path resolution on such a delta has no defined answer. Addressing by id has one, always.

2.3 ref is polymorphic and MUST be discriminated by the encoding

An encoding MUST make the three distinguishable without consulting the observable being addressed, because a receiver may process a delta for an observable it has not yet materialized.

2.4 Prior values are not carried

A delta MUST NOT carry the value the slot held before the change.

Rationale, measured: the receiver reconstructs the prior value from its own state while applying, so on the wire it is derivable data, and derivable data carried alongside its source is a way for two things to disagree. Carrying it measured at +40.2% gzip on a representative editing stream, against +12.7% for the per-commit integrity tag in section 3.3, which provides the divergence detection that was the actual motivation. A per-delta hash of the prior value was also measured and is worse than both at +45.0%, because hashes do not compress and the values they replace do.

Implementations that need an inverse MUST compute it locally, where the prior value is available for free.

3. Commits

A commit is an unordered set of deltas that took effect together.

3.1 A commit is the unit that crosses every boundary

An implementation MUST transmit, persist, and validate whole commits. It MUST NOT split a commit across messages, and MUST NOT apply a commit partially.

Rationale, measured: a consumer that rebuilds state by applying deltas one at a time observes intermediate states in which invariants spanning two slots are false. Applying the same deltas as one commit does not, because every delta is validated, then every delta is applied, then observers are notified once. Splitting a two-delta commit into two applications was measured to expose a broken invariant; applying it whole did not.

3.2 Deltas within a commit are order-independent

A receiver MUST produce the same state regardless of the order in which it applies the deltas of one commit.

A commit MUST NOT contain two deltas addressing the same (id, ref).

Rationale, measured: 2,700 commits containing 16,515 deltas were applied in generated, shuffled, and reversed order across objects, arrays, maps, nested observables and shared references, with no divergence in any order and no duplicate (id, ref) pair observed in any commit.

3.3 Integrity tag

A commit MAY carry an integrity tag: a short digest over the prior values of the slots it addresses, computed by the sender against its own pre-commit state.

A receiver that supports tags and computes a different tag MUST treat the replicas as diverged. It MUST NOT attempt to repair by inference; divergence is resolved by resynchronizing.

The tag detects that a commit landed on state the sender did not expect. It does not identify which delta diverged, and is not required to.

3.4 Commit scope is one document

A commit MUST NOT span two documents.

Rationale: atomicity across documents is available on some storage backends and not on others. A commit whose atomicity depends on where it is stored has semantics that change with deployment, which is worse than a narrower guarantee that holds everywhere. Invariants spanning two documents belong to the layer above this one.

4. Ordering between commits

Commits MUST be applied in the order the sender emitted them.

Coalescing is safe only within one emission window. An implementation MAY merge changes into a single commit before emitting it, subject to section 5.

5. Coalescing

An implementation MAY merge multiple changes to state into one commit before emitting it. If it does:

1. It MUST NOT drop a change to a slot that no other merged change addresses.

2. It MUST merge changes to the same slot into the net effect over the window.

3. It MUST omit a slot whose net effect over the window is no change.

Rationale, measured: rule 1 is the one that gets violated in practice. A coalescing strategy that keeps the first and last change of a burst and discards what falls between was measured silently dropping a change to a slot nothing else in the burst touched. A strategy keyed by slot, merging only within a slot, was measured lossless across 2,700 commits and 16,515 deltas.

A conforming implementation SHOULD key its merge structure by slot rather than by time, because the two rules above then hold by construction rather than by care.

6. Encoding

A commit is encoded as a byte string that describes itself. The type set is small on purpose: null, booleans, integers, one float width, byte strings, text strings, and arrays. There are no maps and no tagged values.

Conformance is stated as byte equality, so the encoding has exactly one spelling for every value. A decoder MUST refuse any input an encoder would not have produced, and the rest of this section is that one rule applied case by case.

Rationale, measured: a text encoding cannot meet byte equality across languages. The same double prints as 1e-7 from one runtime's JSON and 1e-07 from another's, so two conforming implementations would write different bytes for one value. A byte encoding also measured smaller on a representative editing stream of 2,000 commits and 10,431 deltas: 24.9% smaller raw, 11.0% smaller with each frame compressed alone, and 6.0% smaller with one compression context across the stream. Size was the tiebreaker. The spelling problem was the decision.

6.1 Heads

Every item begins with an initial byte: three bits of major type, five bits of additional information. Additional information below 24 is the argument itself. The values 24, 25, 26 and 27 introduce a further 1, 2, 4 or 8 bytes, most significant first. The values 28 to 31 are not part of the format.

Majors 5 and 6 are not part of the format.

An encoder MUST write every head in the shortest form that holds its argument. A decoder MUST refuse a wider one, MUST refuse an indefinite length, MUST refuse bytes following the end of the commit, and MUST refuse an array whose stated length exceeds the bytes remaining.

Nothing this format writes nests past four levels (a commit, its list of deltas, a delta, a ref inside it). A decoder MUST refuse nesting past eight levels (nesting-too-deep), so a hostile length cannot recurse a reader to death, while the format keeps room to grow without re-freezing this rule.

6.2 Numbers

A number that is whole and within plus or minus 2^53 MUST be encoded as an integer, in the shortest head that holds it. Every other finite number MUST be encoded as a float64.

A decoder MUST refuse an integer outside that range, which cannot be held exactly, and MUST refuse a float64 holding a whole number inside it, because the integer form is the one an encoder would have written.

NaN and the infinities have no encoding. Negative zero is written as zero: nothing in the model tells the two apart, and a second spelling for one value is exactly what section 6 exists to prevent.

6.3 Text

Text is UTF-8. A string holding an unpaired surrogate has no encoding, and an encoder MUST refuse it rather than substitute a replacement character. Substituting changes the value on its way out, and the result still decodes cleanly, so nothing downstream can notice.

6.4 Values

A value is a primitive or a reference to an observable. There is nothing else. An implementation MUST NOT inline a structure into a slot.

reference = [ edge, kind, id ]
edge      = 0 attach | 1 alias
kind      = 0 object | 1 array | 2 map

Rationale: a structure inlined into a slot would be state that changes without a delta addressing it, and every change to state is a delta. Carrying the kind on the reference, rather than inferring it from the other deltas that mention the id, is what lets an observable with no slots be fully described, and lets a receiver read a delta about an observable it has not seen yet. The edge is section 1.1, and it costs one byte per reference, measured at 0.26% of a representative raw stream and nothing measurable once compressed.

6.5 Refs

ref = [ kind, key ]

The kind is written rather than inferred. This is section 2.3 made concrete.

6.6 Positions

A position is a byte string, ordered as a byte string: bytes are unsigned, and a string that is a prefix of another sorts before it.

A position MUST be non-empty and MUST NOT end in a zero byte. Both rules exist so a position can always be produced between any two others. With a trailing zero allowed, nothing fits between a key and that key followed by a zero, and the array acquires a place it can never grow into.

How a position between two others is chosen is not specified. Any choice meeting the two rules interoperates, because a receiver orders by comparing positions and never by regenerating them.

6.7 Deltas

delta = [ type, id, ref ]           when the type is remove
delta = [ type, id, ref, value ]    otherwise
type  = 0 add | 1 replace | 2 remove

6.8 Commits

commit = [ deltas ]
commit = [ deltas, tag ]

deltas holds at least one delta. tag is a byte string of 4 to 32 bytes, section 3.3.

A commit with no deltas MUST be refused. Coalescing whose net effect is nothing emits nothing at all, not an empty commit.

6.9 Canonical order

Within a commit, deltas MUST be written in ascending order of the encoding of the delta's id followed by the encoding of its ref, compared as byte strings.

A decoder MUST refuse a commit whose deltas are in any other order, rather than sorting them. Sorting would mean two byte strings decode to one commit, and re-encoding could then not reproduce its input.

Because the order is strict, one comparison also enforces section 3.2's other rule: two deltas addressing the same (id, ref) compare equal, and equal is not ascending.

6.10 Ids

An id is 12 bytes. See spec/identity.md.

6.11 What a commit does not carry

Left out deliberately:

• Which document it belongs to. Section 3.4 confines a commit to one document. Which one is the routing layer's business, and carrying it here would invite a commit to be read without its route.

• Where it sits in a causal order. Section 4 requires commits to be applied in the order the sender emitted them, which is a property of the channel, not of the commit.

• A format version. Versioning is negotiated once, not repeated on every commit. See spec/CHANGELOG.md.

7. Conformance

An implementation conforms when:

1. It decodes every fixture in spec/fixtures/ to the deltas that fixture states.

2. It encodes those deltas to bytes equal to the fixture, whatever order they are handed to it in.

3. It applies each fixture's commits in generated, shuffled and reversed order, and reaches the document the fixture states.

4. It refuses each fixture in spec/fixtures/invalid/, for the reason that fixture names.

Point 4 is stricter than refusing somehow. A format whose implementations disagree about why an input is invalid has not been specified, only implemented.

Every fixture in spec/fixtures/invalid/ names its reason, and that directory is the complete vocabulary. Most reasons belong to decoding, and each one is a MUST in section 6 read back as a refusal:

Five belong to applying, where the bytes are a well formed commit and the document is what refuses it:

An implementation that refuses at the wrong stage has also failed point 4. A commit whose bytes are well formed MUST decode, and be refused when it is applied.

8. Open

Not yet specified, and deliberately not guessed:

• The integrity tag algorithm, and whether this specification fixes it or a connection negotiates it. The encoding does not depend on the answer, because a tag is opaque bytes.

• Large and exact numbers. There is no big integer and no decimal type. An application needing one carries it as text or as a byte string, and knows it is doing so.