crdt#

A small CRDT engine that encodes a JSON document as an append-only operation log and reads it back into plain JSON. Every replica that holds the same set of operations converges on the same document — not through a merge lattice, but through a deterministic sort followed by a plain linear fold.

The wire shape of operations, the reduced document body, and the atproto record types are described as atproto lexicons under lexicons/local/crdt/.

The pipeline#

Reading the log back into a document is three layers, each its own module:

1. Sort (src/sorter.ts) — order the op log deterministically by causal bucket, then lexically by opId. Ops whose dependencies can never be satisfied are dropped here.
2. Reduce, keyed by target (src/reducer.ts) — each op names a value-object target. Group the sorted ops by target and fold each group with the matching semantics — register (set / incr / assign) or collection (add / remove / insert / delete). The output is a document body: a ROOT register followed by one value object per target in first-appearance order.
3. Materialize (src/materialize.ts) — starting from ROOT, walk the document body, resolving references and positional indexes into plain JSON.

References live entirely in layer 3. The reducer treats a reference as an opaque value and never interprets it, so the register and collection folds are unchanged by them.

import { reduceOperations } from "./src/reducer.js";
import { materializeDocument } from "./src/materialize.js";

const body = reduceOperations(ops); // DocBodyItem[] — ROOT first
const doc = materializeDocument(body); // plain JSON, or undefined if empty

See example/ for a worked op log, reduced body, and materialized document.

Operations#

Every operation carries three common fields:

The $type field selects the op (atproto NSID form):

The previousOpIds edges are what give the sort its causal order: an op sorts into a bucket one past the deepest predecessor it observed. A well-formed remove or delete observes the adds it cancels, so those adds sort earlier and are live when it runs — the observed-remove property throughout: you can only remove what you have already seen.

Operation identity#

The sort boundary deduplicates by opId: two ops sharing an opId are folded as one. So opId is the unit of identity, and how it is assigned decides which ops merge. Mint it from a per-replica nonce (replica:counter) and only a literal re-delivery dedups. Mint it as a hash of the op's content and two replicas that independently produce the same edit produce the same opId — so two editors who both fix "a typa" → "a typo" converge on a single insert instead of "typoo".

src/identity.ts mints content-addressed ids via cidForLex (the same canonical DAG-CBOR + CID the repo already uses for record CIDs, so clients agree on the encoding for free). Which fields are identity is per family, governed by one rule: include previousOpIds exactly when the op's effect depends on its causal position (what sorts before it). Position-independent ops exclude deps so the same act always collapses; occurrence-bearing ops are not content-addressed at all.

Inline OR-Set add (no valueId) is the one per-collection choice — multiset (the default, each add distinct by opId) or set (identical data collapses, opt-in via mintOpId(op, { inlineAdd: "set" })). Nonce ops are not minted here: they must carry a client-assigned unique opId, and mintOpId throws for them rather than return a colliding hash.

Content ids only collide when clients produce byte-identical identity fields, which takes agreement on three layers — the canonical encoding (handled by cidForLex), the identity fields (the table above), and canonical op construction in the editor: a fixed anchor choice for inserts (anchor the left neighbour, side after), a canonical range for deletes (omit bounds for open ranges), and a minimal, canonical dependency set where deps are identity. mintOpId sorts previousOpIds so their order never matters, but it cannot choose which deps a client lists — that is the editor's contract. The conformance suite in test/identity.test.ts pins the "same edit → same id, distinct edit → distinct id" boundary and should run in every client.

Value objects#

Reducing the log yields a document body — a list of value objects, always led by ROOT:

type DocBodyItem = DocValue | DocSet | DocSequence;

interface DocValue {
  $type: "local.crdt.document#value";
  id: string;       // the op `target` — register identity, stable across writes
  value: unknown;   // the folded value, possibly containing references
  lastOpId: string; // opId of the last op folded into this value object
}

interface DocSet {
  $type: "local.crdt.document#set";
  id: string;
  set: Record<string, unknown>; // OR-Set members, keyed by element identity
  lastOpId: string;
}

interface DocSequence {
  $type: "local.crdt.document#sequence";
  id: string;
  seq: SeqItem[];   // run-length encoded RGA sequence (live values + tombstones)
  lastOpId: string;
}

id and opId are distinct namespaces. id (the target) names a value object — the unit of sharing; opId names a single op. lastOpId is the last op that wrote the object — useful for attribution and change detection.

A document is the graph you get by picking a root id and following references.

For callers that already hold plain { id, value, lastOpId } registers, materialize(rootId, objects) is a thin adapter over materializeDocument.

References#

A reference is a pointer to another value object, by its id:

interface Ref { $ref: string }   // e.g. { "$ref": "user:bob" }

Two structural rules make references unambiguous:

Single-key rule#

A reference is exactly a one-key object whose only key is $ref and whose value is a string id. An object that carries a $ref key alongside anything else is not a reference — it is data. References are pure pointers; they cannot carry sidecar fields. (See isRef in src/ref.ts.)

Depth-1 rule (one layer)#

Within a single value object, a reference may appear only as a direct member of the root container — a top-level field value, or a top-level array element. Anything that is itself a container (a nested object or array) is inline, frozen data and may not contain references.

{ "a": { "$ref": "test" } }              // OK   — ref is a top-level field value
{ "a": { "b": { "$ref": "test" } } }     // not OK — ref nested one container deeper

You go deeper in the document by chaining value objects through references, not by nesting inline. Depth resets across a reference boundary, so a list is its own value object whose value is an array of references:

// "doc"
{ "id": "doc",   "value": { "title": "Notes", "children": { "$ref": "list1" } } }
// "list1" — a list is a value object; its elements are refs
{ "id": "list1", "value": [ { "$ref": "n1" }, { "$ref": "n2" } ] }
// "n1" — inline nested *data* (no refs) is fine at any depth
{ "id": "n1",    "value": { "text": "first", "addr": { "city": "NYC" } } }

Why depth-1: a value object's outgoing edges are then visible in its top-level members, so reference-graph operations (garbage collection, "who points here", cycle checks, copy/move analysis) are shallow scans rather than deep walks. It also pushes the things you'd want addressable for concurrent edit — list elements, sub-records — to become their own value objects. The restriction is reversible at zero cost: every depth-1 document is already valid under a looser rule and materializes identically, so it can be relaxed later if needed; the reverse would orphan references.

Positional references ($idx)#

A positional reference points at a position inside a materialized RGA sequence rather than at a value object:

interface IdxRef {
  $idx: { target: string; id: string; idx: number; after?: boolean };
}

Unlike $ref, $idx may appear at any depth of inline data (for example a facet's byteStart / byteEnd). It resolves to the offset of element <id>.<idx> within the fully-materialized target sequence — a byte offset for a string sequence, an item index for an array one. after: true resolves to the exclusive end boundary instead of the start.

Escaping#

The $ prefix is system-owned in value space. A writer escapes any data key that begins with $ by doubling the leading $; the reader reverses it. (See escapeKey / unescapeKey in src/ref.ts.)

The invariant this buys: a raw single-key { "$ref": ... } in stored data is always a real pointer, never accidental user data, because any genuine $ref key was escaped to $$ref. Behavior on malformed input (a raw reference deeper than depth-1, or an unescaped $ data key) is unspecified — writers must follow the contract.

Materialization#

materializeDocument(body, rootId?) resolves the document body into plain JSON, starting from rootId (default "ROOT").

Walking a #value object's root container, each direct member is either:

• a reference → resolve it (recurse into the target value object), or
• inline data → copy it through, unescaping keys and resolving $idx at every depth.

#set materializes to an array of its members' values (identity keys dropped). #sequence materializes to a re-joined string (string-origin runs) or an array (array-origin elements).

Absence#

A reference that resolves to nothing is absent, and absence collapses:

• object field → the key is dropped
• array element → the element is dropped and the array compacts
• document root → the document is empty (undefined)

A reference resolves to nothing in two cases:

• Dangling — the target id has no value object.
• Cycle — the target id is already being expanded on the current path.

Cycles are path-based, not global#

The "already being expanded" check is against the chain of ancestors on the current resolution path, not a global "first occurrence wins" set. So a → b → a becomes a → b → nothing (the back-edge collapses), while a diamond — two places referencing the same id without a cycle — legitimately expands in both places. Global de-duplication would blank out the second appearance, which would break copy (copy is two slots referencing one id, and both must expand).

Collections: the OR-Set#

An OR-Set (observed-remove set, src/orset.ts) is a value object whose target is written by add / remove ops instead of register ops. It folds to a #set keyed by element identity, which materializes as an array. An element is added one of two ways, and each way is removed by naming the identity it carries:

• By ref, the element's identity is valueId (the value-object id it points at). Adding the same valueId twice is one element (refs dedup by target); remove cancels every live ref with that identity.
• Inline data has no stable id, so its identity is the add op's own opId. Two inline adds of identical data are two distinct, independently removable elements; remove names the opId of the add to cancel.

Like the registers, the fold is a plain linear pass over the causally-sorted op stream — convergence comes from the deterministic sort, not a merge lattice. A well-formed remove causally follows (via previousOpIds) the adds it cancels, so those adds sort earlier and are live when it runs; a later re-add sorts after the remove and re-appears. This is the observed-remove property: you can only remove what you have already seen.

Collections: the RGA list#

An RGA (replicated growable array, src/rga.ts) is a value object whose target is written by insert / delete ops. Like the OR-Set it folds to a #sequence that materializes as a string or array; what it adds is order — elements live at stable positions and new elements are inserted relative to an existing position.

Elements#

A single insert inserts several elements at once. Its value is:

• a string — one element per Unicode code point ("hi" → two elements),
• an array — one element per entry, each a reference ({ $ref }, recognized structurally as everywhere else) or inline data, or
• any other JSON value — a single inline element.

Each element's identity is "<opId>.<index>": insert c1 of "hi" yields the elements c1.0 and c1.1. That per-element id is what later inserts anchor on and what deletes name.

Insert: anchor + side#

The block is spliced immediately before/after the anchor's current position. BEGIN and END are the virtual ends of the list — after BEGIN is the front, before END is the back (either side of a sentinel resolves the same). As with the other types the fold is a linear pass over the causally-sorted stream, so "the anchor's current position" is identical on every replica; concurrent inserts at the same anchor each splice nearest it and so land in a stable, deterministic order. Causality keeps an anchor present when an op referencing it runs; an insert whose anchor is genuinely missing is dropped.

Delete: observed-remove of known elements#

delete names a source id (the opId of the insert that created the block) and an optional startIdx / endIdx sub-range (inclusive); with no range it tombstones the whole block. The fold tombstones each named element: it stays in the list, so inserts anchored on it (even a deleted one) still resolve, but it drops out of the projected value. Because a delete names ids rather than a positional span, an element inserted into that span concurrently has a different id, is not named, and survives — the observed-remove property again: you can only delete what you have already seen.

Collections transform across families#

The OR-Set and the RGA fold to the same substrate — an ordered list of element nodes (a ref by target, or inline data, live or tombstoned), defined in src/collection.ts. They differ only in how their ops touch it: an OR-Set add appends (refs dedup by target) and remove filters out by identity, while an RGA insert splices a block at an anchor and delete tombstones by element id.

Because the substrate is shared, a single target may be written by both families, and its type transforms across the op stream — there is no conversion step, the one node list flows through whichever handler each op needs:

• an insert can anchor on an element an OR-Set add contributed (the element id is that add's opId);
• an add appends onto an RGA list; a remove imposes set dedup on refs the RGA inserted (cancelling every node pointing at the target);
• a delete can tombstone an OR-Set-added element, and a tombstone does not count as live, so it never blocks a later add re-add.

As everywhere else, the handler is chosen per op and the fold is a linear pass over the causally-sorted stream, so order in that stream is all that decides the outcome. (Mixing a register and a collection on one target remains undefined — the transform is between the two collection families only.)

Copy / move / copy-on-write#

The machinery only knows aliasing; everything else is ordinary ops on top.

• move — write the destination to { "$ref": "A" } and drop the source in the same op set.
• copy (alias, the default) — write the destination to { "$ref": "A" }. Both slots resolve to the same value object; edits to A show through both.
• copy-on-write — start as the alias above; the fork is just the next write to the destination replacing the $ref with fresh content. COW is not a primitive — it falls out of "alias, then a normal write replaces it."

Lexicon#

Three lexicons under lexicons/local/crdt/ describe the wire shapes:

lexicons/com/atproto/repo/strongRef.json is included for oplog signature strong refs.

Validate and regenerate TypeScript with the @atproto/lex-cli tooling:

npm run lex:check   # validate all lexicons
npm run lex:gen     # regenerate src/lexicon/ from lexicons/local/crdt/

The local.crdt NSID prefix is a placeholder — swap it for a real namespace before publishing.

Development#

npm test          # vitest suite (test/fixtures.test.ts, driven by test/fixtures/**)
npm run test:watch
npm run typecheck # tsc --noEmit