crdt

package
v5.1.0 Latest Latest
Warning

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

 Go to latest Published: Mar 25, 2026 License: Apache-2.0 Imports: 9 Imported by: 0

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

  1. Create nodes: nodeA := crdt.NewCRDT(initial, "node-a")
  2. Edit locally: delta := nodeA.Edit(func(v *T) { v.Field = newVal })
  3. Distribute: send delta (JSON-serializable) to peers
  4. 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.

Index

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 

func NewCRDT[T any](initial T, nodeID string) *CRDT[T]

NewCRDT creates a new CRDT wrapper.

func (*CRDT[T]) ApplyDelta 

func (c *CRDT[T]) ApplyDelta(delta Delta[T]) bool

ApplyDelta applies a delta from a remote peer using Last-Write-Wins resolution. Returns true if any operations were accepted.

func (*CRDT[T]) Clock 

func (c *CRDT[T]) Clock() *hlc.Clock

Clock returns the internal hybrid logical clock.

func (*CRDT[T]) Edit 

func (c *CRDT[T]) Edit(fn func(*T)) Delta[T]

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 (c *CRDT[T]) MarshalJSON() ([]byte, error)

func (*CRDT[T]) Merge 

func (c *CRDT[T]) Merge(other *CRDT[T]) bool

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]) NodeID 

func (c *CRDT[T]) NodeID() string

NodeID returns the unique identifier for this CRDT instance.

func (*CRDT[T]) UnmarshalJSON 

func (c *CRDT[T]) UnmarshalJSON(data []byte) error

func (*CRDT[T]) View 

func (c *CRDT[T]) View() T

View returns a deep copy of the current value.

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 

func NewCounter(nodeID string) *Counter

NewCounter creates a new Counter for the given nodeID.

func (*Counter) Decrement added in v5.1.0 

func (c *Counter) Decrement(delta int64)

Decrement adds delta to this node's decrement total. Ignored if delta <= 0.

func (*Counter) Increment added in v5.1.0 

func (c *Counter) Increment(delta int64)

Increment adds delta to this node's increment total. Ignored if delta <= 0.

func (*Counter) Merge added in v5.1.0 

func (c *Counter) Merge(other *Counter) bool

Merge merges the state of other into this Counter. Returns true if any changes were applied.

func (*Counter) NodeID added in v5.1.0 

func (c *Counter) NodeID() string

NodeID returns the node identifier for this Counter.

func (*Counter) Value added in v5.1.0 

func (c *Counter) Value() int64

Value returns the current counter value: sum(Inc) - sum(Dec).

type Delta 

type Delta[T any] struct {
	Timestamp hlc.HLC `json:"t"`
	// contains filtered or unexported fields
}

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 (d Delta[T]) MarshalJSON() ([]byte, error)

func (*Delta[T]) UnmarshalJSON 

func (d *Delta[T]) UnmarshalJSON(data []byte) error

type LWW 

type LWW[T any] struct {
	Value     T       `json:"v"`
	Timestamp hlc.HLC `json:"t"`
}

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.

func (*LWW[T]) Set 

func (l *LWW[T]) Set(v T, ts hlc.HLC) bool

Set updates the register's value and timestamp if ts is after the current timestamp. Returns true if the update was accepted.

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]) Contains added in v5.1.0 

func (m *Map[K, V]) Contains(key K) bool

Contains reports whether key exists in the map.

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 

func (m *Map[K, V]) Get(key K) (V, bool)

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]) Len added in v5.1.0 

func (m *Map[K, V]) Len() int

Len returns the number of entries in the map.

func (*Map[K, V]) Merge added in v5.1.0 

func (m *Map[K, V]) Merge(other *Map[K, V]) bool

Merge performs a full state-based LWW merge with another Map node. Returns true if the local state changed.

func (*Map[K, V]) NodeID added in v5.1.0 

func (m *Map[K, V]) NodeID() string

NodeID returns the unique identifier for this Map instance.

func (*Map[K, V]) Set added in v5.1.0 

func (m *Map[K, V]) Set(key K, value V)

Set sets key to value.

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.

func (*Set[T]) Contains added in v5.1.0 

func (s *Set[T]) Contains(elem T) bool

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 

func (s *Set[T]) Len() int

Len returns the number of distinct live elements.

func (*Set[T]) Merge added in v5.1.0 

func (s *Set[T]) Merge(other *Set[T]) bool

Merge performs a full state-based OR-Set merge with another Set node. Returns true if the local state changed.

func (*Set[T]) NodeID added in v5.1.0 

func (s *Set[T]) NodeID() string

NodeID returns the unique identifier for this Set instance.

func (*Set[T]) Remove added in v5.1.0 

func (s *Set[T]) Remove(elem T)

Remove marks all non-deleted entries whose Elem equals elem as deleted. Only entries visible at call time are tombstoned; concurrent adds on other nodes create entries with different tags that this Remove never sees.

type Text 

type Text []TextRun

Text represents a CRDT-friendly text structure using runs.

func MergeTextRuns 

func MergeTextRuns(a, b Text) Text

MergeTextRuns merges two Text states into a single convergent state.

func (Text) Delete 

func (t Text) Delete(pos, length int) Text

Delete removes length characters starting at pos.

func (Text) Diff 

func (t Text) Diff(other Text) deep.Patch[Text]

Diff compares t with other and returns a Patch.

func (Text) Insert 

func (t Text) Insert(pos int, value string, clock *hlc.Clock) Text

Insert inserts a string at the given character position.

func (*Text) Patch 

func (t *Text) Patch(p deep.Patch[Text], logger *slog.Logger) error

Patch applies p to t.

func (Text) String 

func (t Text) String() string

String returns the full text content, skipping deleted runs.

type TextRun 

type TextRun struct {
	ID      hlc.HLC `deep:"key" json:"id"`
	Value   string  `json:"v"`
	Prev    hlc.HLC `json:"p,omitempty"`
	Deleted bool    `json:"d,omitempty"`
}

TextRun represents a contiguous run of characters with a unique starting ID.

Source Files

View all Source files

Directories

Path Synopsis
Package hlc implements a Hybrid Logical Clock (HLC) for distributed causality tracking.
 Package hlc implements a Hybrid Logical Clock (HLC) for distributed causality tracking.

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.