crdt

package module
v0.10.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

CI Go Reference coverage license

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), a replicated sequence of values (List) and a replicated map (Map) — 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

A list, for what sits beside the text

The things built around a document are sequences too — the comments on it, the record of who changed what, the messages beside it — and they need the same guarantees. List is the same algorithm over values the caller encodes:

comments := crdt.NewList(site)
ops, _ := comments.Insert(0, encoded)   // values are opaque []byte
comments.Apply(fromPeers...)
anchor, _ := comments.Anchor(pos)       // a handle that survives other edits

It is a separate type rather than a generic one, deliberately: a document holds hundreds of thousands of characters and earns run-length storage and an index over runs, while a list holds tens or hundreds of values, where a slice is both faster and obviously correct.

A map, for the cells beside it

Not everything beside a document is a sequence. A spreadsheet is a map of cells, a table of settings is a map of settings: written and cleared, never woven in between their neighbours. Map merges those by last writer wins per key, under the same (clock, site) order the text uses, over values the caller encodes:

sheet := crdt.NewMap(site)
op, _ := sheet.Set("B7", []byte("42"))  // send op to every peer
value, ok := sheet.Get("B7")            // a copy; writing to it changes nothing
op, _ = sheet.Delete("B7")
sheet.Keys()                            // sorted, so every replica agrees

A deleted key keeps its clock. Dropping it would let an older write arriving afterwards bring the key back on the replica that heard it late and not on the one that heard it early, permanently — the classic mistake in a last-writer-wins map, and the thing here most worth reading docs/design.md for.

Keeping a view in step

A view of the text — an editor, a preview — has to be told what changed, not what the text now is. Handed only the new text it would have to replace everything, and replacing everything throws away the selection, the scroll position, the folded regions and the decorations, on every keystroke anybody else makes.

ApplyChanges is Apply and also reports the edits, in the order they have to be made, coalesced: a peer typing a word is one change, not one per letter. Apply does not pay for that.

Anchoring, and who wrote what

An offset names a place; an anchor names a character, and keeps naming it however the document moves around it. That is what a comment, a mark or a stored selection should be:

changes, _ := doc.ApplyChanges(ops...) // what a view has to do to catch up
anchor, _ := doc.Anchor(pos)     // the identity of the character there
pos, ok := doc.Position(anchor)  // where it is now — or where it was, if deleted
doc.Visible(anchor)              // whether it is still in the text
doc.AuthorRuns()                 // the visible text split by who wrote each stretch

Every character already carried the identity of the operation that created it, and the site is part of that identity, so none of this costs the document anything to store.

Counting the way a browser counts

The document counts characters. CodeMirror, the DOM, the Language Server Protocol and every index into a JavaScript string count UTF-16 code units, in which an emoji, an extended CJK ideograph or a 𝔸 is two units and one character. An editor handing its cursor offset to Insert therefore edits in the wrong place as soon as the document holds one of them — silently, and with nothing left behind that a later read could notice.

So the same operations are addressed both ways, and a caller who counts in UTF-16 never converts by hand:

doc.LenUTF16()                 // what JavaScript's String.length would report
doc.InsertUTF16(pos, "text")   // pos in code units
doc.DeleteUTF16(pos, n)        // pos and n in code units
doc.UTF16Offset(runePos)       // and the conversion, both ways
doc.RuneOffset(utf16Pos)

An offset landing between the two units of one character is refused rather than rounded; docs/design.md says why, and how to round it in one step if that is what you want. A document holding no such character converts in constant time, so nothing pays for this until it has an emoji in it. The answers are checked against node's, not against ours.

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; and operations arranged to make integration walk the whole document cost a descent of an index instead.

Status

Version 0.10: the text, list and map CRDTs, the wire and snapshot formats, awareness, and the surface an editor needs — reported changes, anchors, authorship, and UTF-16 addressing. Pure Go, CGO=0, 100% statement coverage on both packages, race-clean, six-arch CI, and the full suite green under js/wasm.

A real editing history — 259 778 edits from the trace text CRDTs are commonly measured on — replays in 18.4 ms and matches the recorded text exactly; the same history delivered back to front, nothing applicable until the last operation, settles in 0.25 s, and the document encodes to 620 KB. See docs/performance.md.

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.

A replicated map

Map is the same machinery applied to a key-value map, for what an editor keeps beside its text — a spreadsheet of cells, a table of settings. The last write to a key wins, under the same (clock, site) order, and a deleted key keeps its clock so that an older write arriving later cannot resurrect it. It shares ID, VersionVector, ErrMalformed and the wire conventions with Doc and nothing else, so neither structure can disturb the other.

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

View Source 
const MaxClock = 1 << 62

MaxClock is the highest Lamport timestamp an operation may carry, and so also the highest sequence number, since a clock is never below the sequence number beside it.

A clock counts operations: to reach this one, a session would have to issue four quintillion of them, one per nanosecond for a century and a half. The ceiling exists for what arrives from elsewhere, not for what is issued here. A replica raises its clock past every clock it is told about, so without a ceiling one operation from one peer — a corrupted varint is enough, no malice required — leaves the receiver's clock at the top of the range, and its next edit wraps to zero. That edit is then an operation every replica rejects as invalid, its own author included, and one that loses every tie it takes part in: the peer is silently and permanently unable to write. Refusing the clock on arrival is what keeps that from being reachable at all.

Variables

View Source 
var ErrEmptyValue = errors.New("crdt: a list value must not be empty")

ErrEmptyValue reports an attempt to insert a value of no bytes. A list of nothings is almost always a caller encoding badly, and allowing it would make "absent" and "empty" the same on the wire.

View Source 
var ErrExhausted = errors.New("crdt: the site has no clock left")

ErrExhausted reports a replica that can issue no further operations because its Lamport clock has reached MaxClock. Reaching it honestly is not something a running program does; see MaxClock.

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.

View Source 
var ErrSurrogateBoundary = errors.New("crdt: UTF-16 offset splits a surrogate pair")

ErrSurrogateBoundary reports a UTF-16 offset that falls between the two code units of one character.

Such an offset names a position that does not exist: half of an emoji is not a place a cursor can be, and no editor's user ever put it there. It is refused rather than rounded because rounding would move an edit somewhere the caller did not ask for and leave nothing behind to say so — the same reasoning that has Doc.Insert refuse invalid UTF-8 rather than substitute replacement characters.

It is not a hypothetical. JavaScript will happily do the operation, and `"a😀b".slice(0, 2) + "x"` is a string containing a lone high surrogate: not text, not valid UTF-8, and not anything this package can hold. An offset that splits a character has already lost the information needed to honour it.

A caller who must tolerate such an offset can round it down in one step, without a second API: an offset that splits a character is always exactly one past that character's first unit, so Doc.RuneOffset of pos-1 is the position of the character it landed inside.

Functions

func AppendMapOps added in v0.10.0 

func AppendMapOps(dst []byte, ops []MapOp) ([]byte, error)

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

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 AuthorRun added in v0.7.0 

type AuthorRun struct {
	// Pos is the visible offset the stretch starts at.
	Pos int
	// Len is how many characters it covers.
	Len int
	// Site is the replica that wrote them.
	Site SiteID
}

An AuthorRun is a stretch of the visible text one replica wrote.

type Change added in v0.7.0 

type Change struct {
	Pos     int
	Removed int
	Text    string
}

A Change is one contiguous edit to the visible text: remove Removed characters at Pos, then put Text there. Either part may be empty.

Offsets are in runes, and each change is expressed against the text as it stands after the changes before it. Applying them in order to a copy of the text is what brings the copy up to date.

func ChangesFrom added in v0.7.0 

func ChangesFrom(text, want string) []Change

ChangesFrom returns the edits that turn text into the document's current text, for a caller holding a copy it cannot otherwise reconcile — a view that has just been reconnected, say. It is a convenience over Doc.String, not a cheaper path: it compares the two.

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) Anchor added in v0.7.0 

func (d *Doc) Anchor(pos int) (ID, error)

Anchor returns the identity of the character at visible offset pos.

The identity does not move. Insertions and deletions elsewhere change which offset the character sits at, and never change what it is, so an anchor is what a comment, a mark or a selection should be stored as — an offset stored instead would point somewhere else the moment anyone edits above it.

pos may equal Doc.Len, which anchors to the end of the document and returns the zero ID: the position after every character there is, and the one thing insertions at the end do not move.

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) ApplyChanges added in v0.7.0 

func (d *Doc) ApplyChanges(ops ...Op) ([]Change, error)

ApplyChanges is Doc.Apply, and also reports what the document did: the edits a view of the text has to make to catch up, in the order it has to make them.

Only what actually happened is reported. An operation already applied, or one still waiting for the operations it depends on, changes nothing and says nothing; when it does land, the change is reported then.

Finding where each edit landed costs a walk up the index per operation, which Doc.Apply does not pay. Use that one when nothing is watching.

func (*Doc) Author added in v0.7.0 

func (d *Doc) Author(pos int) (SiteID, error)

Author returns the replica that wrote the character at visible offset pos.

func (*Doc) AuthorRuns added in v0.7.0 

func (d *Doc) AuthorRuns() []AuthorRun

AuthorRuns splits the visible text into stretches by who wrote them, in order. It is what colouring a document by author needs, and it costs one pass rather than one lookup per character.

Adjacent stretches by the same replica are joined, so the result depends on the text rather than on how the document happens to be stored: two replicas holding the same document return the same runs.

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) DeleteUTF16 added in v0.8.0 

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

DeleteUTF16 is Doc.Delete with pos and length counted in UTF-16 code units rather than in runes.

Both ends of the range are converted, so length is a number of code units and the number of characters removed may be fewer — deleting the four units of two emoji removes two characters. A range whose either end splits a character is refused; see ErrSurrogateBoundary.

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) InsertUTF16 added in v0.8.0 

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

InsertUTF16 is Doc.Insert with pos counted in UTF-16 code units rather than in runes. The text itself is a Go string, and so is measured in neither.

Example

A browser's cursor offset counts UTF-16 code units, and an emoji is two of them. Handing that offset to Insert would put the text one place to the left of where the user asked for it, without an error and without a trace. 

package main

import (
	"fmt"

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

func main() {
	doc := crdt.New(1)
	if _, err := doc.Insert(0, "ship \U0001F680 it"); err != nil {
		panic(err)
	}

	// Nine characters, ten code units: the rocket is one and two.
	fmt.Println(doc.Len(), doc.LenUTF16())

	// The editor reports its caret just after the rocket, which is code unit
	// seven and character six.
	if _, err := doc.InsertUTF16(7, " now"); err != nil {
		panic(err)
	}
	fmt.Println(doc)

	// The offset between the rocket's two units names no position at all.
	_, err := doc.InsertUTF16(6, "x")
	fmt.Println(err)

}

Output:
9 10
ship 🚀 now it
crdt: UTF-16 offset splits a surrogate pair

func (*Doc) Len 

func (d *Doc) Len() int

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

func (*Doc) LenUTF16 added in v0.8.0 

func (d *Doc) LenUTF16() int

LenUTF16 returns the length of the document in UTF-16 code units — the number JavaScript's String.prototype.length reports for Doc.String.

It is a counter, not a walk: the count of visible supplementary characters is maintained beside the count of visible characters, so this reads the document no more than Doc.Len does.

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) Position added in v0.7.0 

func (d *Doc) Position(anchor ID) (pos int, ok bool)

Position returns where the character an anchor names sits now.

A deleted character still has a place — the offset it would occupy, which is where the text around it closed up — and that is returned too, because a comment on a deleted sentence belongs where the sentence was rather than nowhere. Use Doc.Visible to tell the two apart.

The zero ID anchors to the end of the document. ok is false only for an identity this document has never seen, which means the anchor came from somewhere else or the operations that would explain it have not arrived.

func (*Doc) RuneOffset added in v0.8.0 

func (d *Doc) RuneOffset(pos int) (int, error)

RuneOffset converts a UTF-16 offset into the rune offset naming the same position. pos may equal Doc.LenUTF16, which converts to Doc.Len.

An offset falling between the two code units of one character is refused with ErrSurrogateBoundary; see there for why, and for the one-line way to round it down instead.

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.

Characters are written in runs: one header for a stretch one site typed consecutively, then its text, then the stretches of it that have been deleted. Writing one record per character instead, as version 1 did, cost twenty-five bytes for every character of a real document — measured against other implementations, between eight and twenty-four times what they need.

The runs written are maximal, whatever boundaries the document happens to hold in memory. That is what keeps the encoding canonical: two replicas that have applied the same operations produce identical bytes even if the operations arrived in different orders, so a snapshot doubles as a convergence check. It also keeps the format independent of the layout a replica stores, which is what let that layout change twice without a flag day.

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/performance.md.

func (*Doc) UTF16Offset added in v0.8.0 

func (d *Doc) UTF16Offset(pos int) (int, error)

UTF16Offset converts a rune offset into the UTF-16 offset naming the same position. pos may equal Doc.Len, which converts to Doc.LenUTF16.

This is the direction an editor needs to place someone else's cursor, or to report where an edit of its own landed.

Example

Awareness offsets are rune positions, because both peers have to agree what an offset means and an update has nowhere to say. A peer whose editor counts UTF-16 converts at its own edge — where it has to clamp in any case, since a cursor may describe a document longer than the one it now has. 

package main

import (
	"fmt"

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

func main() {
	doc := crdt.New(1)
	if _, err := doc.Insert(0, "\U0001F600 hello"); err != nil {
		panic(err)
	}

	peers := awareness.New()
	peers.Apply(awareness.Update{Site: 2, Clock: 1, Cursor: awareness.Cursor{Anchor: 2, Head: 99}})

	for _, peer := range peers.Peers() {
		head := min(max(peer.Cursor.Head, 0), doc.Len())
		at, err := doc.UTF16Offset(head)
		if err != nil {
			panic(err)
		}
		fmt.Println("caret at code unit", at)
	}
}

Output:
caret at code unit 8

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.

func (*Doc) Visible added in v0.7.0 

func (d *Doc) Visible(anchor ID) bool

Visible reports whether the character an anchor names is still in the text.

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 List added in v0.9.0 

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

A List is one replica of a sequence of values. It is not safe for concurrent use; serialize access from the outside.

The zero List is unusable — construct one with NewList or LoadList.

func LoadList added in v0.9.0 

func LoadList(site SiteID, snapshot []byte) (*List, error)

LoadList rebuilds a list from a snapshot, to be edited as site.

func NewList added in v0.9.0 

func NewList(site SiteID) *List

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

func (*List) Anchor added in v0.9.0 

func (l *List) Anchor(pos int) (ID, error)

Anchor returns the identity of the value at index pos, which keeps naming that value however the list moves around it — what a reference to a comment should hold. pos may equal List.Len, which anchors to the end and returns the zero ID.

func (*List) Apply added in v0.9.0 

func (l *List) Apply(ops ...ListOp) error

Apply integrates operations from peers. Duplicates are ignored, and an operation arriving before what it depends on waits until that lands.

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

func (*List) Delete added in v0.9.0 

func (l *List) Delete(pos, count int) ([]ListOp, error)

Delete removes count values from index pos and returns the operations describing it. Removing nothing is a no-op.

func (*List) Get added in v0.9.0 

func (l *List) Get(pos int) ([]byte, error)

Get returns a copy of the value at index pos.

func (*List) Insert added in v0.9.0 

func (l *List) Insert(pos int, values ...[]byte) ([]ListOp, error)

Insert adds values at index pos and returns the operations describing it. The operations are already applied here; send them to every peer.

pos may equal List.Len, which appends. Inserting nothing is a no-op.

func (*List) Len added in v0.9.0 

func (l *List) Len() int

Len returns the number of values present.

func (*List) OpsSince added in v0.9.0 

func (l *List) OpsSince(vv VersionVector) []ListOp

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

The result is in list order, which for insertions is a causal order: an element always follows its origin.

func (*List) Pending added in v0.9.0 

func (l *List) Pending() int

Pending returns the number of operations waiting for the operations they depend on.

func (*List) Position added in v0.9.0 

func (l *List) Position(anchor ID) (pos int, ok bool)

Position returns where the value an anchor names sits now, or where it was if it has been removed. ok is false for an identity this list has never seen.

func (*List) Site added in v0.9.0 

func (l *List) Site() SiteID

Site returns the replica identity this list issues operations as.

func (*List) Snapshot added in v0.9.0 

func (l *List) Snapshot() []byte

Snapshot encodes the whole list — every value, present or removed, in order, plus the version vector. It is what a server sends a client joining, 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: List.OpsSince on a loaded list returns what it would have on the original.

func (*List) Tombstones added in v0.9.0 

func (l *List) Tombstones() int

Tombstones returns the number of removed values still held. They cannot be dropped: a concurrent insertion may still name one as its origin.

func (*List) Values added in v0.9.0 

func (l *List) Values() [][]byte

Values returns copies of every value present, in order.

func (*List) Version added in v0.9.0 

func (l *List) Version() VersionVector

Version returns a copy of the version vector describing which operations this replica holds.

func (*List) Visible added in v0.9.0 

func (l *List) Visible(anchor ID) bool

Visible reports whether the value an anchor names is still in the list.

type ListOp added in v0.9.0 

type ListOp struct {
	// Kind selects insertion or deletion.
	Kind OpKind
	// ID names this operation, its Seq counting the issuing site's operations.
	ID ID
	// Clock is the Lamport timestamp ordering this against concurrent
	// operations; see the package documentation on the two counters.
	Clock uint64
	// Origin is the element the new one is inserted after; the zero ID means
	// the start of the list. OpInsert only.
	Origin ID
	// Value is the inserted element. OpInsert only.
	Value []byte
	// Target is the element to remove. OpDelete only.
	Target ID
}

A ListOp is one indivisible change to a list. Like Op it is self-describing and applying it is idempotent, so a transport may duplicate or reorder freely.

type Map added in v0.10.0 

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

A Map is a replicated key-value map: any number of replicas may write to it at once, offline, in any delivery order, and every replica ends up holding the same keys and the same values. Values are opaque bytes — the caller encodes whatever it likes — and they are copied in and out, so no slice is ever shared between a caller and the map.

Writes to one key are ordered by the same (clock, site) total order the text uses: a Lamport clock raised past everything the replica has seen, ties broken by site. The highest write wins, and it wins everywhere whatever order the writes arrived in, because a maximum does not depend on the order it is taken in. Writes to different keys never interact at all.

A deleted key keeps its clock

A deletion leaves a record behind rather than dropping the key. Dropping it would leave nothing for an older write arriving later to lose against, so that write would take effect — resurrecting the key on the replica that heard it late and not on the one that heard it early, permanently. Keeping the clock is also what makes a delete and a concurrent set to the same key resolve identically everywhere. Map.Len and Map.Keys do not count a deleted key; Map.Snapshot writes it.

What a replica may forget, and what it may not

A map keeps one record per key, so the value a write put there is gone the moment a later write replaces it. The operation is not gone. Sequence numbers are contiguous per site — that is what lets a VersionVector describe a replica exactly — and Map.Apply never skips one: an operation that arrives before its predecessor waits for it rather than being dropped. A peer catching up therefore has to be told that the number was used, and Map.OpsSince tells it with a MapSuperseded operation, which names no key, carries no value, and covers a whole run of numbers at once. Catching up a peer from nothing therefore costs one operation per key it does not hold plus one per stretch it does not need, never one per write ever made.

That is sound only because the operation which superseded it travels in the same batch: it is either the record now held for that key, which OpsSince sends whenever the peer lacks it, or something the peer already has. A caller that filters what OpsSince returns breaks the map.

A Map is not safe for concurrent use. The zero Map is unusable — construct one with NewMap or LoadMap.

Example

Two replicas write to the same cell at the same time, and one of them then deletes it. The later write wins wherever the operations arrive, and the deleted cell keeps the clock that beat them: an older write turning up afterwards cannot bring it back. 

package main

import (
	"fmt"

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

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

	fromAda, err := ada.Set("B7", []byte("41"))
	if err != nil {
		panic(err)
	}
	fromGrace, err := grace.Set("B7", []byte("42"))
	if err != nil {
		panic(err)
	}
	if err := ada.Apply(fromGrace); err != nil {
		panic(err)
	}
	if err := grace.Apply(fromAda); err != nil {
		panic(err)
	}

	value, _ := ada.Get("B7")
	fmt.Printf("%s %s\n", value, ada.Keys())

	// Grace clears the cell, having seen both writes.
	cleared, err := grace.Delete("B7")
	if err != nil {
		panic(err)
	}
	if err := ada.Apply(cleared); err != nil {
		panic(err)
	}
	_, present := ada.Get("B7")
	fmt.Println(present, ada.Len())

}

Output:
42 [B7]
false 0

func LoadMap added in v0.10.0 

func LoadMap(site SiteID, snapshot []byte) (*Map, error)

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

A snapshot arrives over a network, so most of what follows is refusing states no replica could have reached. The version vector is what the rest is measured against: a record written by an operation the vector does not promise, or by an operation another record already claims, describes a map that could not reproduce its own history.

func NewMap added in v0.10.0 

func NewMap(site SiteID) *Map

NewMap returns an empty map that issues operations as site. Every replica writing to a map concurrently must pass a distinct site; see SiteID.

func (*Map) Apply added in v0.10.0 

func (m *Map) Apply(ops ...MapOp) error

Apply integrates operations from peers. Duplicates are ignored, and an operation that arrives before the operation its site issued before it is buffered until that one lands, so the caller needs no ordered delivery.

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

func (*Map) Delete added in v0.10.0 

func (m *Map) Delete(key string) (MapOp, error)

Delete removes key and returns the operation that describes it.

It writes a tombstone whether or not this replica holds the key. What a deletion means cannot depend on what the deleting replica happens to have heard: a peer's write still in flight has to lose to a later deletion on every replica, including one that has not yet seen the write it is beating.

func (*Map) Get added in v0.10.0 

func (m *Map) Get(key string) ([]byte, bool)

Get returns the value stored at key, and whether the key is present. The value is a copy: writing to it does not change what the map holds.

A value stored as empty reads back as nil — the two are one value here, and the encoding cannot tell them apart either.

func (*Map) Keys added in v0.10.0 

func (m *Map) Keys() []string

Keys returns the keys present, in ascending order, so that anything a caller derives from them is the same on every replica. Deleted keys are not among them.

func (*Map) Len added in v0.10.0 

func (m *Map) Len() int

Len returns how many keys are present, not counting deleted ones.

func (*Map) OpsSince added in v0.10.0 

func (m *Map) OpsSince(vv VersionVector) []MapOp

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 everything.

The result is ordered by site and then by sequence number, so the peer can apply it as it arrives without ever having to buffer. Operations whose values have since been overwritten come back as MapSuperseded runs, carrying nothing but the sequence numbers they stand for; the writes that overwrote them are in the same result, which is what makes that safe. See Map.

func (*Map) Pending added in v0.10.0 

func (m *Map) Pending() int

Pending reports how many received operations are still waiting for the operation their own site issued before them.

func (*Map) Set added in v0.10.0 

func (m *Map) Set(key string, value []byte) (MapOp, error)

Set stores value at key and returns the operation that describes it. The operation is already applied here; send it to every peer.

The map copies value, so the caller may reuse the slice, and the returned operation carries a copy of its own, so writing to it cannot reach the map. A key that is not valid UTF-8 is refused; see MapOp.

func (*Map) Snapshot added in v0.10.0 

func (m *Map) Snapshot() []byte

Snapshot encodes the whole map — every key ever written, deleted ones included, each with the identity and Lamport timestamp of the write it holds — plus the version vector. It is what a server sends a client joining an existing session, and what it persists.

Keys are written in ascending order, so two replicas that have applied the same operations produce identical bytes whatever order those operations arrived in. That makes a snapshot a convergence check: agreeing on the keys and values is weaker than agreeing on the state, because two replicas can agree on every value while disagreeing about which write produced it, and would then resolve the next concurrent write differently.

What a snapshot does not keep is the values of writes that have already lost; see Map for what Map.OpsSince sends in their place.

func (*Map) Tombstones added in v0.10.0 

func (m *Map) Tombstones() int

Tombstones returns how many keys are held only to keep their clock. They are the one thing here that grows without bound, so a caller measuring what a long session costs measures this.

func (*Map) Version added in v0.10.0 

func (m *Map) Version() VersionVector

Version returns what this replica holds, to be handed to a peer that will send back what it is missing; see Map.OpsSince.

type MapOp added in v0.10.0 

type MapOp struct {
	// Kind selects writing, removal, or values the sender has forgotten.
	Kind MapOpKind
	// ID names this operation. Its Seq is the issuing site's own counter and
	// increases by exactly one per operation. For MapSuperseded it is the last
	// of the sequence numbers the operation accounts for.
	ID ID
	// Clock is the Lamport timestamp that orders this operation against
	// concurrent writes to the same key. See the package documentation.
	Clock uint64
	// Key is the key written or removed. MapSet and MapDelete only.
	Key string
	// Value is the bytes written. MapSet only; it may be empty.
	Value []byte
	// Span is how many consecutive sequence numbers this operation accounts for,
	// ending at ID.Seq. MapSuperseded only, where it is at least one.
	Span uint64
}

A MapOp is one indivisible change to a Map. 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: Key belongs to MapSet and MapDelete, Value to MapSet alone, Span to MapSuperseded alone. The unused fields must be zero, and are checked, so a garbled operation is rejected rather than silently reinterpreted.

func ParseMapOps added in v0.10.0 

func ParseMapOps(data []byte) ([]MapOp, error)

ParseMapOps decodes a batch written by AppendMapOps.

func (MapOp) MarshalBinary added in v0.10.0 

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

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

func (*MapOp) UnmarshalBinary added in v0.10.0 

func (o *MapOp) 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 MapOpKind added in v0.10.0 

type MapOpKind uint8

MapOpKind distinguishes the operations a replicated map exchanges. 

const (
	// MapSet writes a value at a key.
	MapSet MapOpKind = 1
	// MapDelete removes a key, and leaves its clock behind. See [Map].
	MapDelete MapOpKind = 2
	// MapSuperseded stands in for operations whose values the sending replica no
	// longer holds, because later writes to the same keys replaced them. It names
	// no key and carries no value: it exists so that a peer catching up can
	// account for the sequence numbers and move on. Only [Map.OpsSince] produces
	// one.
	//
	// It covers a run of consecutive sequence numbers rather than one, because
	// the numbers a replica has forgotten are exactly the gaps between the ones
	// it still holds: a key written a million times leaves one record and one
	// run, not a million operations to send.
	MapSuperseded MapOpKind = 3
)

func (MapOpKind) String added in v0.10.0 

func (k MapOpKind) String() string

String renders the kind for diagnostics.

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.

func (VersionVector) MarshalBinary added in v0.1.1 

func (v VersionVector) MarshalBinary() ([]byte, error)

MarshalBinary encodes the vector. Entries are written in ascending site order, so the same state always produces the same bytes and a caller may compare or cache them.

A replica sends this to be told what it has missed; see Doc.OpsSince.

func (*VersionVector) UnmarshalBinary added in v0.1.1 

func (v *VersionVector) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes a vector written by MarshalBinary. A site listed twice, a sequence number of zero, and trailing bytes are all rejected: each would leave what the vector means dependent on decoding order.

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.