crdt

package module
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 16, 2026 License: BSD-3-Clause Imports: 6 Imported by: 10

README

crdt — collaborative text editing in pure Go

github.com/go-crdt/crdt is a pure-Go, CGO=0 conflict-free replicated data type for plain text: any number of replicas may edit the same document at once, offline, over an unreliable transport, and every replica ends up with the same text. No server arbitrates, and no operation is ever transformed.

It compiles to js/wasm, so the same merge logic runs on the server and in every browser tab — one implementation, one source of truth, no second codebase in JavaScript to keep in step. The whole test suite, convergence properties included, runs under js/wasm in CI.

Zero dependencies.

Packages

Package Purpose
crdt the replicated text document: Doc, operations, version vectors, snapshots
crdt/awareness ephemeral presence — who is here and where their cursor is

Using it

ada, grace := crdt.New(1), crdt.New(2)

opening, _ := ada.Insert(0, "the quick fox")
grace.Apply(opening...)

// Both edit at once, neither having seen the other.
fromAda, _ := ada.Insert(10, "brown ")
fromGrace, _ := grace.Insert(13, " jumps")

ada.Apply(fromGrace...)
grace.Apply(fromAda...)

fmt.Println(ada)   // the quick brown fox jumps
fmt.Println(grace) // the quick brown fox jumps

A replica joining late loads a snapshot instead of the whole history; one coming back from offline hands over its version vector and is sent only what it missed:

client, err := crdt.Load(siteID, snapshot)   // join
missed := server.OpsSince(client.Version())  // catch up

What it guarantees

  • Convergence. Replicas holding the same operations hold the same document, whatever order those operations arrived in. Proven by randomised sessions with late, reordered and duplicated delivery, and by enumerating every permutation of small histories.
  • Idempotence and reordering. Duplicates are ignored; an operation arriving before what it depends on is buffered until that lands. A transport needs to be eventually complete, not ordered.
  • Determinism. No wall clock, no randomness. Replica identity is injected by the caller, so a document behaves identically on a server and in a browser.
  • Intent. A run of characters typed one after another is never chopped up by someone else's concurrent insertion.
  • Nothing is trusted. Every decoder is fuzzed; a snapshot that no replica could have produced is rejected rather than loaded.

Status

Version 0.1: the sequence CRDT, the wire and snapshot formats, and awareness. Pure Go, CGO=0, 100% statement coverage on both packages, race-clean, six-arch CI, and the full suite green under js/wasm.

See docs/design.md for how it works and why, and docs/performance.md for what it costs and what changes next.

License

BSD-3-Clause — see LICENSE. Copyright the go-crdt authors.

Documentation

Overview

Package crdt implements a conflict-free replicated data type for plain text: a replicated character sequence that any number of replicas may edit concurrently, offline, and in any delivery order, and that is guaranteed to converge to the same text on every replica.

The sequence is an RGA (Replicated Growable Array). Every character carries a unique ID and the ID of the character it was inserted after, so insertions are placed relative to content rather than to an index that concurrent edits would invalidate. Deletions are tombstones, so an insertion may still refer to a character another replica has already removed.

Determinism

The package never reads the wall clock and never draws random numbers, so the same Doc compiled to js/wasm behaves exactly as it does on a server. Replica identity is injected by the caller as a SiteID; see DeriveSiteID for a deterministic way to obtain one from bytes the caller already has.

Two counters

Each operation carries two numbers, and they are not the same thing:

  • ID.Seq is a per-site counter that increases by exactly one per operation the site issues. It gives the operation its identity and lets a VersionVector describe, exactly, which operations a replica holds.
  • Op.Clock is a Lamport timestamp, bumped past every clock a replica has seen. It orders concurrent insertions at the same position, and it is what makes RGA integration convergent.

Folding the two into one counter would create gaps in a site's own sequence, and a version vector cannot describe a sequence with gaps.

Delivery

Doc.Apply tolerates duplicates, and it tolerates operations that arrive before the operations they depend on: an operation that is not yet ready is buffered and integrated as soon as its dependencies land. Callers therefore do not need an ordered transport, only an eventually-complete one.

Example

Two people edit the same document at the same time, neither having seen the other's change. Once the two operations have crossed, both replicas hold the same text — with no server deciding anything. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	ada, grace := crdt.New(1), crdt.New(2)

	opening, err := ada.Insert(0, "the quick fox")
	if err != nil {
		panic(err)
	}
	if err := grace.Apply(opening...); err != nil {
		panic(err)
	}

	// Both edit at once, neither seeing the other.
	fromAda, err := ada.Insert(10, "brown ")
	if err != nil {
		panic(err)
	}
	fromGrace, err := grace.Insert(13, " jumps")
	if err != nil {
		panic(err)
	}

	if err := ada.Apply(fromGrace...); err != nil {
		panic(err)
	}
	if err := grace.Apply(fromAda...); err != nil {
		panic(err)
	}

	fmt.Println(ada)
	fmt.Println(grace)
}

Output:
the quick brown fox jumps
the quick brown fox jumps

Index

Examples

Constants

This section is empty.

Variables

View Source 
var ErrInvalidOp = errors.New("crdt: invalid operation")

ErrInvalidOp reports an operation that cannot be applied because it is not well formed — an unknown kind, a missing identity, an unusable character, or a field set that does not belong to its kind.

View Source 
var ErrInvalidText = errors.New("crdt: invalid UTF-8")

ErrInvalidText reports text that is not valid UTF-8. The package refuses it rather than substituting replacement characters, which would silently corrupt a document that no later edit could repair.

View Source 
var ErrMalformed = errors.New("crdt: malformed encoding")

ErrMalformed reports bytes that are not a valid encoding.

View Source 
var ErrOutOfRange = errors.New("crdt: position out of range")

ErrOutOfRange reports a position or length outside the document.

Functions

func AppendOps 

func AppendOps(dst []byte, ops []Op) ([]byte, error)

AppendOps encodes a batch of operations onto dst — the form a transport sends. The batch is length-prefixed, so ParseOps can reject a truncated message instead of silently returning the operations that happened to survive.

Types

type Doc 

type Doc struct {
	// contains filtered or unexported fields
}

A Doc is one replica of a text document. It is not safe for concurrent use; serialize access from the outside, as an editor naturally does.

The zero Doc is unusable — construct one with New or Load.

func Load 

func Load(site SiteID, snapshot []byte) (*Doc, error)

Load rebuilds a document from a snapshot, to be edited as site. The site need not be one that appears in the snapshot — a client joining an existing document brings its own.

Example

A replica joining an existing session is given a snapshot rather than the whole history, and can take part immediately. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	server := crdt.New(1)
	if _, err := server.Insert(0, "shared draft"); err != nil {
		panic(err)
	}

	client, err := crdt.Load(2, server.Snapshot())
	if err != nil {
		panic(err)
	}
	edit, err := client.Insert(client.Len(), " — revised")
	if err != nil {
		panic(err)
	}
	if err := server.Apply(edit...); err != nil {
		panic(err)
	}

	fmt.Println(server)
}

Output:
shared draft — revised

func New 

func New(site SiteID) *Doc

New returns an empty document that issues operations as site. Every replica editing a document concurrently must pass a distinct site; see SiteID.

func (*Doc) Apply 

func (d *Doc) Apply(ops ...Op) error

Apply integrates operations from peers. Duplicates are ignored, and an operation that arrives before the operations it depends on is buffered until they do, so the caller needs no ordered delivery.

A malformed operation is rejected and nothing in the batch is applied.

func (*Doc) Delete 

func (d *Doc) Delete(pos, length int) ([]Op, error)

Delete removes length runes starting at rune offset pos and returns the operations that describe it. Deleting nothing is a no-op.

func (*Doc) Insert 

func (d *Doc) Insert(pos int, text string) ([]Op, error)

Insert adds text at rune offset pos and returns the operations that describe it. The operations are already applied here; send them to every peer.

pos may equal Doc.Len, which appends. Inserting the empty string is a no-op that returns no operations.

func (*Doc) Len 

func (d *Doc) Len() int

Len returns the number of visible characters, counted in runes.

func (*Doc) OpsSince 

func (d *Doc) OpsSince(vv VersionVector) []Op

OpsSince returns the operations this replica holds that vv does not, ready to be sent to the peer that produced vv. Pass a nil vector for the whole history.

The result is in document order, which for insertions is a causal order: a character always follows its origin. Deletions may arrive before the insertions they refer to, which the receiving Doc.Apply buffers.

A deletion's Lamport timestamp is not retained — it never affects ordering — so replayed deletions carry their sequence number as their clock.

Example

A replica that has been away asks for what it missed by handing over its version vector; it is sent those operations and nothing else. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	online, offline := crdt.New(1), crdt.New(2)
	start, err := online.Insert(0, "notes")
	if err != nil {
		panic(err)
	}
	if err := offline.Apply(start...); err != nil {
		panic(err)
	}

	// The offline replica misses everything that follows.
	if _, err := online.Insert(5, ": chapter one"); err != nil {
		panic(err)
	}
	if _, err := online.Delete(0, 1); err != nil {
		panic(err)
	}

	missed := online.OpsSince(offline.Version())
	fmt.Println(len(missed), "operations missed")
	if err := offline.Apply(missed...); err != nil {
		panic(err)
	}
	fmt.Println(offline)
}

Output:
14 operations missed
otes: chapter one

func (*Doc) Pending 

func (d *Doc) Pending() int

Pending returns the number of operations buffered awaiting their dependencies. A healthy replica returns to zero once delivery catches up; a number that only grows means a peer is withholding operations.

func (*Doc) Site 

func (d *Doc) Site() SiteID

Site returns the replica identity this document issues operations as.

func (*Doc) Snapshot 

func (d *Doc) Snapshot() []byte

Snapshot encodes the whole document — every character, alive or tombstoned, in document order, plus the version vector. It is what a server sends a client joining an existing session, and what it persists.

The encoding is deterministic: two replicas holding the same operations produce identical bytes, so a snapshot doubles as a convergence check.

The full history is recoverable from a snapshot: Doc.OpsSince on a loaded document returns the same operations it would have on the original.

func (*Doc) String 

func (d *Doc) String() string

String returns the document text.

func (*Doc) Tombstones 

func (d *Doc) Tombstones() int

Tombstones returns the number of deleted characters still held in memory. They cannot be dropped, because a concurrent insertion may name one as its origin; see docs/memory.md.

func (*Doc) Version 

func (d *Doc) Version() VersionVector

Version returns a copy of the version vector describing which operations this replica holds. Pass it to a peer's Doc.OpsSince to be sent exactly what is missing.

type ID 

type ID struct {
	Site SiteID
	Seq  uint64
}

ID names a single operation, and — for an insertion — the character that operation created. It is unique across replicas because Site is unique and Seq counts that site's own operations.

The zero ID is the document root: the virtual character that precedes all content. It is a valid insertion origin and is never the ID of a real operation, because Seq starts at one.

func (ID) IsRoot 

func (id ID) IsRoot() bool

IsRoot reports whether id names the virtual character at the start of every document rather than a real operation.

The test is on Seq alone, because Seq counts from one: no operation ever carries zero, whatever its site. A decoder that only compared against the zero ID would let a sequence number of zero paired with a non-zero site through as if it named something real.

func (ID) String 

func (id ID) String() string

String renders the ID as "seq@site", the notation used in the CRDT literature. The root prints as "root".

type Op 

type Op struct {
	// Kind selects insertion or deletion.
	Kind OpKind
	// ID names this operation. Its Seq is the issuing site's own counter and
	// increases by exactly one per operation.
	ID ID
	// Clock is the Lamport timestamp that orders this operation against
	// concurrent ones. See the package documentation.
	Clock uint64
	// Origin is the character the new one is inserted after; the zero ID means
	// the start of the document. OpInsert only.
	Origin ID
	// Char is the inserted character. OpInsert only.
	Char rune
	// Target is the character to tombstone. OpDelete only.
	Target ID
}

An Op is one indivisible change to a document. It is the only thing replicas exchange, it is self-describing, and applying it is idempotent, so a transport may duplicate or reorder operations freely.

Which fields carry meaning depends on Kind: Origin and Char belong to OpInsert, Target to OpDelete. The unused fields must be zero, and are checked, so a garbled operation is rejected rather than silently reinterpreted.

func ParseOps 

func ParseOps(data []byte) ([]Op, error)

ParseOps decodes a batch written by AppendOps.

func (Op) MarshalBinary 

func (o Op) MarshalBinary() ([]byte, error)

MarshalBinary encodes the operation. It reports ErrInvalidOp rather than producing bytes that would be rejected on arrival.

func (*Op) UnmarshalBinary 

func (o *Op) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes an operation written by MarshalBinary. Trailing bytes are an error: an operation is decoded from exactly its own encoding.

type OpKind 

type OpKind uint8

OpKind distinguishes the two operations a text CRDT needs. 

const (
	// OpInsert adds one character after an existing one.
	OpInsert OpKind = 1
	// OpDelete tombstones an existing character.
	OpDelete OpKind = 2
)

func (OpKind) String 

func (k OpKind) String() string

String renders the kind for diagnostics.

type SiteID 

type SiteID uint64

SiteID identifies a replica. It is chosen by the caller and must be distinct for every replica that concurrently edits a document; two replicas sharing a SiteID can mint the same ID for different characters, which breaks convergence.

The package never generates one itself: a random or clock-derived identifier is unavailable, or not reproducible, under js/wasm. See DeriveSiteID.

func DeriveSiteID 

func DeriveSiteID(b []byte) SiteID

DeriveSiteID hashes b into a SiteID with FNV-1a. It gives callers a deterministic way to turn an identifier they already hold — a session token, a user ID, a tab identifier — into a replica identity, on any platform, including js/wasm where the usual sources of randomness are absent.

Distinctness is the caller's responsibility: distinct b almost always yields distinct SiteIDs, but a hash cannot promise it.

Example

Site identities have to be distinct and cannot be drawn at random under js/wasm, so they are derived from something the caller already holds. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	first := crdt.DeriveSiteID([]byte("session-8f2c"))
	second := crdt.DeriveSiteID([]byte("session-8f2c"))
	fmt.Println(first == second, first == crdt.DeriveSiteID([]byte("session-91ab")))
}

Output:
true false

type VersionVector 

type VersionVector map[SiteID]uint64

A VersionVector records, per site, the highest sequence number a replica has applied. Because a site's sequence numbers have no gaps and Doc refuses to apply an operation until its predecessor has landed, the vector describes a replica's state exactly: it holds operation Seq from Site if and only if Seq <= v[Site].

The nil vector is valid and reads as "nothing applied".

func (VersionVector) Clone 

func (v VersionVector) Clone() VersionVector

Clone returns an independent copy. The clone of a nil vector is empty but non-nil, so it can be written to.

func (VersionVector) Equal 

func (v VersionVector) Equal(other VersionVector) bool

Equal reports whether v and other describe the same set of operations. Sites recorded with a zero sequence number count as absent, so a nil vector equals an empty one.

func (VersionVector) Get 

func (v VersionVector) Get(site SiteID) uint64

Get returns the highest sequence number applied for site, or zero.

func (VersionVector) Includes 

func (v VersionVector) Includes(id ID) bool

Includes reports whether the operation named by id has been applied.

Source Files

View all Source files

Directories

Path Synopsis
Package awareness tracks who else has a document open and where their cursor is — the coloured carets and name labels a collaborative editor shows.
 Package awareness tracks who else has a document open and where their cursor is — the coloured carets and name labels a collaborative editor shows.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.