The highest tagged major version is
Documentation
¶
Overview ¶
Package crdt provides Conflict-free Replicated Data Types (CRDTs) built on top of the deep patch engine.
The central type is CRDT, a concurrency-safe wrapper around any value of type T. It tracks causal history using a per-field Hybrid Logical Clock (HLC) and resolves concurrent edits with Last-Write-Wins (LWW) semantics.
Basic workflow ¶
- Create nodes: nodeA := crdt.NewCRDT(initial, "node-a")
- Edit locally: delta := nodeA.Edit(func(v *T) { v.Field = newVal })
- Distribute: send delta (JSON-serializable) to peers
- Apply remotely: nodeB.ApplyDelta(delta)
For full-state synchronization between two nodes use CRDT.Merge.
Text CRDT ¶
Text is a convergent, ordered sequence of TextRun segments. It supports concurrent insertions and deletions across nodes and is integrated with CRDT directly — no separate registration required.
Collections ¶
How a collection merges depends on how its elements are addressed:
- Map entries are addressed by key, so concurrent writes to different keys both survive and a write to one key never disturbs another.
- A slice whose element type carries a deep:"key" tag is addressed by that key, so concurrent edits to different elements both survive, and an element's fields merge independently. Element order is not part of the synchronized state — Diff emits nothing when a keyed slice is merely reordered — so replicas keep these slices in key order. Sort on read, or carry an explicit ordering field, when a particular order matters.
- A slice with no key tag is synchronized as one value: concurrent edits resolve by last-write-wins, so one writer's version of the whole slice wins. Prefer a map or a keyed slice for anything edited concurrently.
- List is a sequence that merges: concurrent insertions and deletions from different replicas all survive and every replica agrees on the order. Reach for it when position matters and several writers can edit at once — the case an ordinary slice cannot express.
Every case converges — replicas that have seen the same operations agree — but only the first, second and last merge concurrent edits rather than choosing between them.
Text and List resolve concurrency themselves by implementing Convergent; a type of your own can do the same.
Index ¶
- type CRDT
- func (c *CRDT[T]) ApplyDelta(delta Delta[T]) bool
- func (c *CRDT[T]) Clock() *hlc.Clock
- func (c *CRDT[T]) Edit(fn func(*T)) Delta[T]
- func (c *CRDT[T]) MarshalJSON() ([]byte, error)
- func (c *CRDT[T]) Merge(other *CRDT[T]) bool
- func (c *CRDT[T]) NodeID() string
- func (c *CRDT[T]) OnChange(fn func(Change[T])) (cancel func())
- func (c *CRDT[T]) Reverse(delta Delta[T]) Delta[T]
- func (c *CRDT[T]) UnmarshalJSON(data []byte) error
- func (c *CRDT[T]) View() T
- type Change
- type ChangeSource
- type Convergent
- type Counter
- type Delta
- type LWW
- type List
- func (l List[T]) At(pos int) (T, bool)
- func (l List[T]) Delete(pos, count int) List[T]
- func (l List[T]) Diff(other List[T]) deep.Patch[List[T]]
- func (l List[T]) Insert(pos int, value T, clock *hlc.Clock) List[T]
- func (l List[T]) Items() []T
- func (l List[T]) Len() int
- func (l List[T]) MergeFrom(other any) any
- func (l *List[T]) Patch(p deep.Patch[List[T]], logger *slog.Logger) error
- type ListEntry
- type Map
- func (m *Map[K, V]) Contains(key K) bool
- func (m *Map[K, V]) Delete(key K)
- func (m *Map[K, V]) Get(key K) (V, bool)
- func (m *Map[K, V]) Keys() []K
- func (m *Map[K, V]) Len() int
- func (m *Map[K, V]) Merge(other *Map[K, V]) bool
- func (m *Map[K, V]) NodeID() string
- func (m *Map[K, V]) Set(key K, value V)
- type Set
- type Text
- func (t Text) Delete(pos, length int) Text
- func (t Text) Diff(other Text) deep.Patch[Text]
- func (t Text) Insert(pos int, value string, clock *hlc.Clock) Text
- func (t Text) Len() int
- func (t Text) MergeFrom(other any) any
- func (t *Text) Patch(p deep.Patch[Text], logger *slog.Logger) error
- func (t Text) String() string
- type TextRun
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CRDT ¶
type CRDT[T any] struct { // contains filtered or unexported fields }
CRDT represents a Conflict-free Replicated Data Type wrapper around type T.
func NewCRDT ¶
NewCRDT creates a new CRDT wrapper around a deep copy of initial, so later changes to the caller's value cannot reach inside the replica (and two replicas seeded from one value do not share state).
func (*CRDT[T]) ApplyDelta ¶
ApplyDelta applies a delta from a remote peer using Last-Write-Wins resolution. Returns true if any operations were accepted.
func (*CRDT[T]) Edit ¶
Edit applies fn to a copy of the current value, computes a delta, advances the local clock, and returns the delta for distribution to peers. Returns an empty Delta if the edit produces no changes.
func (*CRDT[T]) MarshalJSON ¶
func (*CRDT[T]) Merge ¶
Merge performs a full state-based merge with another CRDT node. For each changed field the node with the strictly newer effective timestamp (max of write clock and tombstone) wins. Text fields are always merged convergently via MergeTextRuns, bypassing LWW.
func (*CRDT[T]) OnChange ¶ added in v5.7.0
OnChange registers fn to be called after every change to this replica, and returns a function that unregisters it.
Callbacks run synchronously on the goroutine that made the change, after the replica's lock has been released. A callback may therefore read the replica, and may edit it — an edit from inside a callback announces itself in turn, so guard against recursing forever. A slow callback holds up whoever made the change.
Nothing is serialized on your behalf: changes made from several goroutines deliver on those goroutines, so a callback can run concurrently with itself. Take a lock inside the callback, or hand changes to a single goroutine, if that matters. The Patch in each Change describes that change on its own, so they can be processed independently.
func (*CRDT[T]) Reverse ¶ added in v5.2.0
Reverse applies the inverse of delta to this node and returns a new Delta representing the undo operation. The returned Delta carries a fresh HLC timestamp so it is causally after the original edit and will be accepted by ApplyDelta on any peer that has already seen the original.
Calling Reverse on the returned Delta produces a redo Delta.
func (*CRDT[T]) UnmarshalJSON ¶
type Change ¶ added in v5.7.0
type Change[T any] struct { Patch deep.Patch[T] Source ChangeSource }
Change describes what actually happened to a replica's value.
Patch holds the operations that were applied, which for a remote delta is only the part that survived conflict resolution — an operation another replica made but this one rejected as stale does not appear. Reading it is how a consumer learns what changed without diffing snapshots: a user interface can redraw just the affected paths.
type ChangeSource ¶ added in v5.7.0
type ChangeSource int
ChangeSource says where a change came from.
const ( // ChangeLocal is an edit made on this replica through [CRDT.Edit]. ChangeLocal ChangeSource = iota // ChangeRemote is a delta from a peer, applied through [CRDT.ApplyDelta]. ChangeRemote // ChangeMerge is the result of [CRDT.Merge] with another replica. ChangeMerge )
func (ChangeSource) String ¶ added in v5.7.0
func (s ChangeSource) String() string
type Convergent ¶ added in v5.7.0
Convergent is implemented by types that resolve concurrent edits themselves rather than being replaced wholesale under last-write-wins. Text and List implement it.
A CRDT applies operations on a Convergent value unconditionally, skipping the clock filter that would discard one side of a concurrent edit, and combines two copies by calling MergeFrom rather than choosing a winner. Implement it to plug a data type of your own into that machinery:
func (s MySet) MergeFrom(other any) any {
o, ok := other.(MySet)
if !ok {
return s
}
return union(s, o)
}
MergeFrom must be commutative, associative and idempotent — merging in any order, any number of times, has to reach the same value — and must return a value of the receiver's own type.
type Counter ¶ added in v5.1.0
type Counter struct {
// contains filtered or unexported fields
}
Counter is a Positive-Negative Counter CRDT. Each node maintains independent increment and decrement totals; the observed value is sum(Inc) - sum(Dec).
func NewCounter ¶ added in v5.1.0
NewCounter creates a new Counter for the given nodeID.
func (*Counter) Decrement ¶ added in v5.1.0
Decrement adds delta to this node's decrement total. Ignored if delta <= 0.
func (*Counter) Increment ¶ added in v5.1.0
Increment adds delta to this node's increment total. Ignored if delta <= 0.
func (*Counter) Merge ¶ added in v5.1.0
Merge merges the state of other into this Counter. Returns true if any changes were applied.
type Delta ¶
Delta represents a set of changes with a causal timestamp. Obtain a Delta via CRDT.Edit; apply it on remote nodes via CRDT.ApplyDelta.
func (Delta[T]) MarshalJSON ¶
func (*Delta[T]) UnmarshalJSON ¶
type LWW ¶
LWW represents a Last-Write-Wins register for type T. Embed LWW fields in a struct to track per-field causality. Use Set to update the value; it accepts the write only if ts is strictly newer.
type List ¶ added in v5.7.0
List is a convergent sequence of T.
An ordinary slice inside a CRDT is synchronized as a single value, so concurrent edits resolve by last-write-wins and one writer's version of the whole slice wins. A List merges instead: concurrent insertions and deletions from different replicas all survive, and every replica converges on the same order.
Elements are placed relative to their neighbours rather than by index, and concurrent insertions at the same position are ordered by ID, so replicas agree regardless of the order updates arrive in. Use it for collaborative ordered data — a task list being reordered by several people, a document outline, a playlist.
The zero List is empty and ready to use. Like Text, a List is a value: Insert and Delete return a new List rather than mutating the receiver.
func MergeLists ¶ added in v5.7.0
MergeLists combines two Lists into one containing every element either side has seen, in the order both sides agree on. A deletion on either side wins, since a tombstone records an element that was removed rather than never seen.
func NewList ¶ added in v5.7.0
NewList returns a List holding values, in order, with IDs drawn from clock.
func (List[T]) At ¶ added in v5.7.0
At returns the live element at pos, and whether pos is in range.
func (List[T]) Delete ¶ added in v5.7.0
Delete removes count elements starting at pos, counted over live elements. Removed entries are kept as tombstones so concurrent insertions that named them still have an anchor.
func (List[T]) Diff ¶ added in v5.7.0
Diff reports the change from l to other as a single whole-value operation: the receiving side merges rather than overwrites, so the operation carries the sequence and lets MergeLists work out the result.
func (List[T]) Insert ¶ added in v5.7.0
Insert places value at pos, counted over live elements. A pos of 0 inserts at the head; a pos at or past the end appends.
func (List[T]) Items ¶ added in v5.7.0
func (l List[T]) Items() []T
Items returns the live elements in order.
func (List[T]) MergeFrom ¶ added in v5.7.0
MergeFrom implements Convergent, so a List merges with a peer's copy instead of one replacing the other under last-write-wins.
type ListEntry ¶ added in v5.7.0
type ListEntry[T any] struct { // ID identifies this element for all time. It is assigned once, by the // replica that inserted the element, and never reused. The deep:"key" tag // makes a List nested inside a struct diff and merge entry by entry rather // than as one opaque value. ID hlc.HLC `deep:"key" json:"id"` // Prev is the ID of the element this one was inserted after — the zero // value for an insertion at the head. Position is expressed relative to a // neighbour rather than as an index, so it survives concurrent edits that // shift indices around. Prev hlc.HLC `json:"p,omitempty"` // Deleted marks a removed element. The entry stays as a tombstone so that a // concurrent insertion that named it as Prev still has somewhere to attach. Deleted bool `json:"d,omitempty"` Value T `json:"v"` }
ListEntry is one element of a List together with the metadata that places it in the sequence.
type Map ¶ added in v5.1.0
type Map[K comparable, V any] struct { // contains filtered or unexported fields }
Map is a distributed LWW key-value map CRDT built on top of CRDT.
Concurrent writes to the same key are resolved by Last-Write-Wins: the write with the strictly higher HLC timestamp wins. Deletions remove the key from the map and record a tombstone timestamp, so a delete with a newer timestamp wins over an older set, and a set with a newer timestamp wins over an older delete.
func NewMap ¶ added in v5.1.0
func NewMap[K comparable, V any](nodeID string) *Map[K, V]
NewMap returns an empty Map CRDT bound to the given node ID.
func (*Map[K, V]) Delete ¶ added in v5.1.0
func (m *Map[K, V]) Delete(key K)
Delete removes key from the map. It is a no-op if the key does not exist.
func (*Map[K, V]) Get ¶ added in v5.1.0
Get returns the value for key and true if the key exists. It returns the zero value and false otherwise.
func (*Map[K, V]) Keys ¶ added in v5.1.0
func (m *Map[K, V]) Keys() []K
Keys returns a slice of all live keys. The order is non-deterministic.
func (*Map[K, V]) Merge ¶ added in v5.1.0
Merge performs a full state-based LWW merge with another Map node. Returns true if the local state changed.
type Set ¶ added in v5.1.0
type Set[T comparable] struct { // contains filtered or unexported fields }
Set is an Add-Wins Observed-Remove Set (OR-Set) CRDT built on top of CRDT.
Each Add creates a uniquely-tagged entry using the node's HLC. Remove only tombstones entries that exist at call time; a concurrent Add from another node produces a different tag, so after Merge the element is still present (add wins over remove).
func NewSet ¶ added in v5.1.0
func NewSet[T comparable](nodeID string) *Set[T]
NewSet returns an empty Set CRDT bound to the given node ID.
func (*Set[T]) Add ¶ added in v5.1.0
func (s *Set[T]) Add(elem T)
Add appends a new uniquely-tagged entry for elem. The tag is the current HLC timestamp serialised as a string map key.
Two clock ticks occur per Add: one to mint the entry's tag and a second inside the underlying Edit for the resulting Delta's Timestamp. Both values are monotonic per the HLC mutex, so the extra tick is harmless; keeping the tag-mint outside Edit means the tag is fixed before the inner closure runs, which keeps the data-flow easy to follow.
func (*Set[T]) Contains ¶ added in v5.1.0
Contains reports whether elem has at least one live (non-deleted) entry.
func (*Set[T]) Items ¶ added in v5.1.0
func (s *Set[T]) Items() []T
Items returns a deduplicated slice of all live elements.
func (*Set[T]) Len ¶ added in v5.1.0
Len returns the number of distinct live elements.
Cost is O(n) in the number of entries (live + tombstoned) because OR-Set duplicates require dedup; the prior implementation built a full slice via Items just to take its length, which this avoids.
func (*Set[T]) Merge ¶ added in v5.1.0
Merge performs a full state-based OR-Set merge with another Set node. Returns true if the local state changed.
type Text ¶
type Text []TextRun
Text represents a CRDT-friendly text structure using runs.
A Text held by this package is always stored in document order. Every operation here either preserves that order or restores it: Insert splices a run into the position the ordering would give it, Delete only flips flags, and MergeTextRuns — the one place runs arrive from elsewhere — derives the order from scratch. Operations can therefore read the runs directly instead of rebuilding the ordering tree, which is what keeps editing from costing more as a document grows.
func MergeTextRuns ¶
MergeTextRuns merges two Text states into a single convergent state.
func (Text) Len ¶ added in v5.7.0
Len returns the number of visible characters, counted in runes — the same unit Insert and Delete take positions in.
func (Text) MergeFrom ¶ added in v5.7.0
MergeFrom implements Convergent, so a Text merges with a peer's copy instead of one replacing the other under last-write-wins.
Source Files
Directories