Architecture

August 21, 2026 · View on GitHub

ygo is a pure-Go implementation of the Yjs CRDT algorithm. It is binary-compatible with the JavaScript reference implementation: updates produced by ygo can be consumed by Yjs clients, and vice versa.

Package dependency graph

provider/webhook                                        mobile/
       │                                                    │
       ▼                                                    ▼
provider/websocket ────────────────────────────────── provider/client        provider/http
       │                                                    │                       │
       ├──────────────────┬───────────────┬─────────────────┤                       │
       ▼                  ▼               ▼                                         │
     sync/            cluster/       persistence/                                   │
       │                  │               │                                         │
       │                  ▼               │                                         │
       │             awareness/           │                                         │
  ┌────┼──────────────────┘               │                                         │
  │    │                                  │                                         │
  │    └─────────────────────────┬────────┘                                         │
  │                              ▼                                                  │
  │                            crdt/ ◄──────────────────────────────────────────────┘
  │                              │
  │                              ▼
  └─────────────────────────►encoding/

The bus (├──┬──┬──┤) is fed from both provider entry points — provider/websocket's trunk on the left, provider/client's on the right — and forks into exactly three arrows, one per label (sync/, cluster/, persistence/); the bus's own width just spans from one trunk to the other, it is not a fourth branch. The ┼ below sync/ is a crossing, not a junction: the line running left through it is awareness/'s edge to encoding/, passing over sync/'s column on its way to the left rail. awareness/ does not depend on crdt/.

Rule: no upward imports. encoding/ has zero runtime dependencies. crdt/ depends only on encoding/. sync/ depends on crdt/ and encoding/; persistence/ depends only on crdt/; cluster/ depends on awareness/ and crdt/. awareness/ is the one exception to the otherwise-neat layering: it depends only on encoding/, not crdt/, despite sitting next to packages that do. provider/websocket and provider/client both import sync/, awareness/, cluster/, and persistence/ directly; provider/http skips that whole tier and depends on crdt/ directly. provider/webhook and mobile/ sit one layer up, wrapping provider/websocket and provider/client respectively — but each also imports lower tiers directly for its own use: provider/webhook imports crdt/, and mobile/ imports both awareness/ and crdt/.

Note: Since v1.0, the library has added several mechanisms not detailed here — the pending-structs queue for out-of-order delivery, structured logging via slog, per-peer broadcast queues, and context-aware methods. See CHANGELOG.md for the per-release picture.

`encoding/` — lib0 binary codec

Implements the lib0 variable-length binary encoding used by Yjs on the wire.

Primitive	Description
`VarUint`	7-bit chunks, LSB-first, continuation bit in MSB. 1–8 bytes.
`VarInt`	ZigZag-encoded signed integer stored as VarUint.
`VarString`	`VarUint(byteLen)` + raw UTF-8 bytes.
`VarBytes`	`VarUint(len)` + raw bytes.
`Float32/64`	4/8-byte little-endian IEEE 754.
`Any`	Tagged union covering nil, bool, int, float, string, []byte, []any, map[string]any.

`crdt/` — core CRDT engine

ID and StateVector

ID = { Client ClientID, Clock uint64 }
StateVector = map[ClientID]uint64   // highest integrated clock per client

Only insertions increment the clock. Deletions do not.

Item

The fundamental unit of the CRDT. Each insertion creates one Item.

Field	Purpose
`ID`	Unique logical timestamp
`Origin`	ID of left neighbour at insertion time
`OriginRight`	ID of right neighbour at insertion time
`Left / Right`	Current neighbours in the doubly-linked list
`Parent`	Owning shared type
`ParentSub`	Map key (for YMap entries)
`Content`	The actual data (see content types below)
`Deleted`	Tombstone flag — item stays in list when deleted

YATA integration algorithm

When integrating a new item:

Resolve Right from OriginRight via getItemCleanStart (splitting the target item if it contains the right-origin clock mid-content). The conflict-scan loop in step 3 uses Right as its upper bound — without this resolution the scan has no termination and can place items past their declared right boundary (fixed in v1.8.1, see #65/#68).
Locate the position immediately after Origin in the current list.
Scan right past any concurrent items that have the same Origin and a lower ClientID (they win the tie-break). The scan terminates at Right (resolved in step 1).
Insert the new item at the resolved position.

This guarantees identical final state on all replicas regardless of message arrival order, because the tie-break on ClientID is deterministic and total.

Content types

Type	Holds
`ContentString`	UTF-8 text
`ContentBinary`	Raw bytes
`ContentAny`	Any JSON-compatible value
`ContentEmbed`	Embedded object (e.g. image metadata)
`ContentFormat`	Formatting attribute key/value (YText)
`ContentDeleted`	Tombstone placeholder (length only)
`ContentType`	Reference to a nested shared type
`ContentDoc`	Reference to a subdocument

StructStore

map[ClientID][]*Item — items are appended in clock order per client (append-only). Lookups by ID use binary search.

Pending-structs queue

When an update references an item whose dependency hasn't arrived yet — a same-client clock gap or a cross-update Origin reference — the item is parked in a per-doc pending queue rather than silently orphaned. The queue drains automatically on each subsequent ApplyUpdate when the missing predecessors arrive. This mirrors Yjs JS's pendingStructs and yrs's Store.pending. See the v1.2.0 CHANGELOG entry for the design.

The same machinery handles delete-set entries that target not-yet-integrated items (pendingDs). State-vector computation is unaffected — pending items don't appear in StateVector() until they're integrated, so peers correctly retry the missing dependencies.

The queue is bounded (default 100,000 parked items; configurable via crdt.WithMaxPendingItems or Server.MaxPendingItems). Updates that would push past the cap return ErrInvalidUpdate — see the v1.8.0 CHANGELOG and #46 for the security rationale.

DeleteSet

Tracks deleted ranges as map[ClientID][]DeleteRange{Clock, Len}. Items are tombstoned (marked Deleted = true) rather than removed, keeping linked-list positions stable.

Transaction

Batches multiple operations. Observers fire once per transaction, not per operation.

Lifecycle:

Collect all inserts and deletes.
Squash consecutive same-client items (run-length optimisation).
Fire beforeObserverCalls.
Fire observe() on each changed type.
Fire observeDeep() recursively.
Fire afterTransaction.
Emit the binary update event for the transport layer.

Doc

The root object. Holds the StructStore, named root types (Share map), Subdocs map, an internal GC flag (set at construction with crdt.WithGC, not a settable field), and observer subscriptions.

`crdt/types/` — shared types

All types embed abstractType which holds the linked-list head/tail and observer lists.

Type	Conflict resolution
`YArray`	Ordered by insertion position
`YMap`	Last-write-wins by ID (higher clock wins)
`YText`	YArray with run-length squashing + `ContentFormat` items
`YXmlFragment`	Ordered child nodes
`YXmlElement`	YXmlFragment + element name + attributes (YMap)
`YXmlText`	YText inside an XML tree

Update encoding (V1 and V2)

V1: each struct is serialised with full client/clock metadata. Simple but verbose.

V2: differential clock encoding + run-length encoding of same-client runs. Typically 30–40% smaller than V1.

Both formats append a DeleteSet section. Conversion between V1 and V2 is lossless. The public API provides EncodeStateAsUpdateV1/V2, ApplyUpdateV1/V2, UpdateV1ToV2, UpdateV2ToV1, and MergeUpdates.

`sync/` — y-protocols sync messages

Three message types (matching the y-protocols spec):

Type	Value	Purpose
`SyncStep1`	0	Send local `StateVector` to peer
`SyncStep2`	1	Respond with missing update (diff against received SV)
`Update`	2	Incremental update after initial sync

ReadSyncMessage(msg []byte) (msgType int, payload []byte, err error) parses any incoming message into its type and raw payload, making it easy to dispatch in custom transport handlers.

The protocol is transport-agnostic: messages are plain []byte and work over WebSocket, HTTP, WebRTC, or in-process pipes.

`awareness/` — ephemeral state

Separate from document updates. Stores map[ClientID]AwarenessState{Clock uint64, State any}.

Last-write-wins per client by Clock.
States expire after 30 s of inactivity. Call StartAutoExpiry(timeout) to run expiry automatically in a background goroutine; it returns a stop function.
Encoded as VarUint(numClients) + per-client (clientID, clock, jsonState).

`persistence/` — versioned storage layer

Depends only on crdt/. Layers an append-only, versioned store on top of the provider's LoadDoc/StoreUpdate primitive: every incremental update becomes a numbered Version, MaterializeAt(v) rebuilds the document at any past version via crdt.MergeUpdatesV1, and named snapshots plus crash-safe pruning/compaction round out the log.

Ships two reference implementations — NewMemoryPersistence() (in-process maps) and NewFilePersistence(dir) (atomic temp+rename writes to one directory per store) — plus persistence/sqlite, a pure-Go (CGo-free) SQLite backend. LegacyAdapter bridges a VersionedPersistence back to the provider's PersistenceAdapter shape without either package importing the other, avoiding a cycle. See PERSISTENCE.md for the full interface and a conformance suite external adapters can run against.

`cluster/` — cross-node relay

Depends on awareness/ and crdt/. Defines the Relay/Sink abstraction that fans document updates and awareness out across multiple provider/websocket (or provider/client) processes sharing rooms, superseding the older persistence-adapter-as-pub/sub pattern. MemRelay is the in-process reference implementation, used by tests and single-process multi-server simulations; production deployments plug in cluster/redis or an equivalent backend. See CLUSTERING.md.

`provider/` — transport handlers

`provider/websocket/`

net/http-compatible handler. One Doc per named room. On connect: exchanges SyncStep1/2 and awareness state. On message: applies update and broadcasts to all other peers in the room.

Persistence is pluggable via the PersistenceAdapter interface:

type PersistenceAdapter interface {
    LoadDoc(room string) ([]byte, error)
    StoreUpdate(room string, update []byte) error
}

Pass an implementation to NewServerWithPersistence(p). The built-in MemoryPersistence (returned by NewMemoryPersistence()) appends updates in memory and periodically folds a room's backlog (CompactEvery, default 500) rather than re-merging on every write; suitable for single-process deployments.

`provider/http/`

Method	Path	Semantics
`GET`	`/doc/{room}?sv=<base64>`	Return binary update diff
`POST`	`/doc/{room}`	Apply binary update from request body

`provider/webhook/`

Wraps a provider/websocket server with outbound HTTP callbacks — HMAC-SHA256-signed, debounced/coalesced, retried with backoff on transient failure — fired on room lifecycle and document-update events, so an external service can react to changes without holding a live connection.

`provider/client/`

The embeddable, offline-first counterpart to provider/websocket: a Go peer (not a server) that hydrates a *crdt.Doc from local storage, lets the caller edit it immediately regardless of connectivity, and runs a background dial loop that reconciles with a provider/websocket-served (or Hocuspocus-compatible) endpoint whenever one is reachable. Speaks the same wire protocol provider/websocket serves. See CLIENT.md.

`mobile/` — Go Mobile bindings

A gomobile bind-safe façade over crdt/, awareness/, and provider/client, for embedding ygo natively in iOS/Android apps with no JavaScript runtime and no CGo. Because gomobile bind only supports a restricted set of cross-language types, every exported method uses only string, int64, bool, []byte, error, and the bound pointer types *Doc/*Awareness/*SyncClient/*Subscription; the package translates ygo's internal uint64 IDs and maps at the boundary. SyncClient is the mobile-facing wrapper around provider/client's dial/sync loop.

Callbacks cross the boundary as interfaces (DocObserver, AwarenessObserver, SyncStatusObserver) rather than as Go func values, which gomobile cannot bind in that direction — the platform implements the interface in Swift or Kotlin and passes it in. Each is delivered on a dedicated drain goroutine, never a lock-holding one and never the platform's UI thread, so observers must marshal to the main thread themselves; SyncStatusObserver exists specifically so a platform observer can call SyncClient.Close from inside a status callback, which is not safe against the raw provider/client.Client.

Concurrency model

Doc is protected by sync.RWMutex. Transactions are serialised. Observer callbacks fire synchronously after the transaction completes. Providers fan out updates to peers under per-room locks.

Garbage collection

GC is on by default and is configured at construction — crdt.New(crdt.WithGC(false)) preserves full history for snapshots and undo/redo. There is no settable GC field on Doc.

Automatic. With GC enabled, each transaction frees the content of the items it deleted, at commit, after observer deltas have been computed and before the document lock is released — so no goroutine ever observes a partially collected state. Auto-GC is suspended while any UndoManager is registered: undoing a deletion re-inserts a copy of the deleted item's content, which requires that content still to be present. Yjs solves this with a per-item keep flag; ygo takes the conservative position of disabling automatic collection entirely for the lifetime of the undo manager.

Manual — tombstone reclamation. crdt.RunGC(doc) is the explicit entry point, and remains available when auto-GC is suspended. It does two passes: it replaces deleted item content with lightweight ContentDeleted tombstones, then merges adjacent tombstones from the same client into single nodes, compacting the linked list so future origin lookups traverse fewer items. Both the structural position information CRDT correctness depends on and the tombstone lengths survive; only the content is discarded. RunGC is a no-op when GC is disabled.

Reclamation is destructive with respect to history: after RunGC, RestoreDocument can no longer reconstruct states that predate the collected deletions. Take any snapshots you need first.

Compatibility testing

Two layers, answering different questions.

Fixtures — do we agree with Yjs on known cases? testutil/gen_fixtures.js generates canonical .bin files from the JS Yjs reference implementation. These are committed to testutil/fixtures/ and loaded by TestCompat_* tests, which assert exact document state and — for encoding tests — byte-for-byte output equality.

Fuzzing — do we agree on cases nobody wrote down? testutil/fuzz/ generates randomised multi-peer scenarios (insert/delete/push/map/xml, optionally moves, across 3–5 peers with random sync order) and replays them through several oracles in crdt/fuzz_test.go:

Test	Oracle	Needs node
`TestFuzzConvergence`	all peers converge to the same state (Go vs Go)	no
`TestFuzzConvergenceMoves`	same, with `YArray.Move` enabled	no
`TestFuzzCrossImpl`	each scenario replayed against real Yjs; ygo must match it logically and round-trip its encoded update	yes
`TestFuzzCorpus`	every frozen minimized reproducer under `testutil/fuzz/corpus` still converges	no

Moves are an ygo wire extension Yjs cannot decode, which is why they are validated by Go-internal convergence rather than against Yjs — and TestFuzzConvergenceMoves is what caught the YArray.Move divergence fixed in v1.40.0. TestFuzzCrossImpl skips when node/yjs is unavailable; set YGO_REQUIRE_NODE=1 to make that a hard failure instead. The two convergence sweeps default to 1000 seeds each and honour FUZZ_ITER for a soak run (TestFuzzCrossImpl is fixed at 200 seeds); any failure prints the FUZZ_SEED that replays it through TestFuzzSeed.