crdt

README

crdt

中文

A bounded Go CRDT library for convergent state, delta replication, recovery, and explicit protocol boundaries.

crdt provides deterministic CRDT primitives and framed binary codecs for replicas that must converge despite duplicate, reordered, or delayed delivery. It is a library, not a complete collaboration service: the host owns identity, authorization, storage, transport, membership, retention, and product invariants.

Start in three minutes

Requires Go 1.21 or later.

go get github.com/DarkInno/crdt@latest

package main

import (
	"fmt"
	"log"

	"github.com/DarkInno/crdt/counter"
)

func main() {
	left, err := counter.NewGCounter("left")
	if err != nil {
		log.Fatal(err)
	}
	right, err := counter.NewGCounter("right")
	if err != nil {
		log.Fatal(err)
	}
	if _, err := left.Increment(3); err != nil {
		log.Fatal(err)
	}
	if err := right.Merge(left); err != nil {
		log.Fatal(err)
	}
	value, err := right.Value()
	if err != nil {
		log.Fatal(err)
	}
	fmt.Println(value) // 3
}

For a checkout:

git clone https://github.com/DarkInno/crdt.git
cd crdt
go test ./...

What is included

• G-Counter, PN-Counter, G-Set, add-wins OR-Set, and causal MV-Register.
• Bounded canonical state/delta frames, deterministic snapshots, recovery plans, and persisted HLC state for reusable replica identities.
• RGA collaborative text with stable run-v2 frames by default; stable bounded rich-text and observed-remove tree protocols; plus list and XML-fragment layers.
• Delta batching, Merkle anti-entropy, exact-acknowledgement tombstone-GC coordination, and manifest-bound replica/inbox recovery helpers.
• A bounded live WebSocket provider, a separate bbolt-backed durable relay, and a local bbolt checkpoint reference.
• Optional, manifest-negotiated compression-aware outer frame v2 with explicit v1 conversion; it does not change CRDT TypeIDs or semantics.
• RGA diagnostic obfuscation that replaces text content while retaining an isolated debug timeline structure.

Experimental protocols—LWW-Set, LWW-Map, legacy scalar RGA v1, and list RGA—need explicit ProtocolPolicy{AllowExperimental: true} at every participating boundary. Stable run-v2 RGA, rich-text v1, and observed-remove tree v1 use the zero policy, but a frame type alone is never a negotiated protocol, authenticated peer, or permission to compact tombstones.

Choose a path

Goal	Read or run
Learn the basic APIs	Getting started and runnable examples
Build a complete client flow	End-to-end integration
Survive local restarts safely	Local bbolt checkpoint reference and go run ./examples/persistent-replica
Add replay and reconnect	Durable relay reference
Use a bounded live relay	WebSocket provider reference
Attach media without CRDT byte replication	Attachment integration
Implement run-v2 outside Go/Wasm	RGA run-v2 protocol and vectors
Implement stable formatting or trees	Rich-text v1 and observed-remove tree v1

The documentation index separates getting-started, integration, protocol/design, and operational material. Detailed performance evidence and deployment runbooks live there instead of making this entry page a manual.

Persistence and recovery

State bytes alone are not a recoverable replica for HLC-backed CRDTs. Persist the state frame, HLC state, and application delivery frontier/outbox atomically before reusing a replica ID. The persistence package is a local bbolt reference for one typed CRDT schema and one active process; it validates the concrete state before saving and on every load.

go run ./examples/persistent-replica
# recovered=true cursor=41 outbox_bytes=24

It is not a clustered database, authenticated transport, or generic business transaction manager. The host still owns encryption at rest, backup/restore, remote authorization, tenant isolation, membership, and tombstone lifecycle.

The durable package intentionally persists a relay operation log and replay cursor. Clients must persist their concrete CRDT checkpoint before advancing that cursor; read the local checkpoint and durable relay references together.

Package map

Package	Purpose
counter, set, register	Counter, set, and register CRDTs.
lww, tree, text, list, xml, richtext	HLC-backed and ordered collaborative structures.
encoding, delta, snapshot, clock	Framing, bounded batches, snapshots, and HLC state.
replica, membership, tombstonegc, merkle	Delivery continuity, membership, safe GC coordination, and anti-entropy.
persistence	Local bounded bbolt CRDT checkpoint reference.
durable, extensions, observe	Durable relay, bounded live relay, and process-local observation.
attachment	Immutable media-reference metadata; never raw media bytes.

Verify and measure

Run focused checks while changing one package:

go test ./persistence ./examples/persistent-replica
go test -race ./persistence
go test -run='^$' -fuzz=FuzzUnmarshalCheckpoint -fuzztime=20s -parallel=1 ./persistence
go test -run='^$' -bench='BenchmarkStore(Save|Load|SaveParallel)$' -benchmem -benchtime=2s ./persistence

Repository gates:

go test ./...
go test -race ./...
go vet ./...
make coverage
make verify

make verify also runs bounded fuzzing, static analysis, linting, integration, and extreme scenarios. make benchmark is a controlled development measure, not a production capacity promise—repeat focused benchmarks on the target disk, CPU, Go version, network, and workload before selecting limits.

Boundaries that matter

• CRC-32C, SHA-256, and a frame type detect format damage; they do not authenticate a peer. Bind exact manifests and protocol policies during an authenticated handshake.
• A greatest observed tag is not proof of contiguous delivery or permission to retire tombstones. Use the relevant frontier, inbox, and membership contracts.
• bbolt uses one writer and an exclusive local file lock. Do not share its file between active pods or treat a local checkpoint as HA storage.
• The library does not enforce business invariants. Validate identity, tenant, value permissions, rate limits, retention, and backup access in the host.

Contributing and releases

Contributions should include focused tests, preserve canonical encoding, bound untrusted input before allocation or mutation, and update the closest relevant documentation. Review CONTRIBUTING.md; keep beta changes on the reviewed beta-to-main release path and do not manually move published tags.

License

SPDX-License-Identifier: MIT. See LICENSE.

Documentation

Overview

Package crdt provides the shared contracts and protocol capability discovery used by this module's state-based CRDT implementations.

Applications normally use a concrete data type from a subpackage, such as counter for G-Counters and PN-Counters, set for add-wins OR-Sets, or clock for hybrid logical clocks. This root package contains the common CRDT, delta, snapshot, and mutation-tag contracts those implementations share.

The framed protocol table is intentionally closed. Use ProtocolPolicy during authenticated connection setup to advertise only the state and delta frame types a replication group has agreed to exchange. Experimental protocols require explicit opt-in and may change before stable promotion.

For installation, examples, and package-level guidance, see the module README at https://github.com/darkinno/crdt.

Example (LwwRegister)

package main

import (
	"fmt"

	"github.com/DarkInno/crdt/register"
)

func main() {
	writer, err := register.NewLWW("writer")
	if err != nil {
		panic(err)
	}
	reader, err := register.NewLWW("reader")
	if err != nil {
		panic(err)
	}
	if err := writer.Set([]byte("healthy")); err != nil {
		panic(err)
	}
	if err := reader.Merge(writer); err != nil {
		panic(err)
	}

	value, ok := reader.Get()
	fmt.Println(ok, string(value))
}

Output:
true healthy

Example (LwwSet)

package main

import (
	"fmt"

	"github.com/DarkInno/crdt/lww"
)

func main() {
	writer, err := lww.NewSet[string]("writer")
	if err != nil {
		panic(err)
	}
	reader, err := lww.NewSet[string]("reader")
	if err != nil {
		panic(err)
	}
	if err := writer.Add("on-call"); err != nil {
		panic(err)
	}
	if err := reader.Merge(writer); err != nil {
		panic(err)
	}

	fmt.Println(reader.Contains("on-call"))
}

Output:
true

Example (MaxRegister)

package main

import (
	"fmt"

	"github.com/DarkInno/crdt/register"
)

func main() {
	local := register.NewMax()
	remote := register.NewMax()
	if err := local.Set(8); err != nil {
		panic(err)
	}
	if err := remote.Set(13); err != nil {
		panic(err)
	}
	if err := local.Merge(remote); err != nil {
		panic(err)
	}

	value, ok := local.Get()
	fmt.Println(ok, value)
}

Output:
true 13

Index

• Constants
• func IsExperimentalFrame(typeID uint64) bool
• func MarshalDiagnosticJSON(summary StateSnapshot) ([]byte, error)
• func MarshalStateJSON(value StateReporter) ([]byte, error)
• type CRDT
• type DeltaCapable
• type FrameType
  • func DefaultRGAFrameType() FrameType
  • func FrameTypeForDelta(deltaID uint64) (FrameType, bool)
  • func FrameTypeForState(stateID uint64) (FrameType, bool)
• type ProtocolPolicy
  • func (p ProtocolPolicy) FrameTypes() []FrameType
  • func (p ProtocolPolicy) SupportsFrame(typeID uint64) bool
• type StateReporter
• type StateSnapshot
• type Tag
  • func (t Tag) Compare(other Tag) int
  • func (t Tag) Valid() bool

Examples

• Package (LwwRegister)
• Package (LwwSet)
• Package (MaxRegister)
• ProtocolPolicy

Constants

const (
	TypeIDGCounterState   uint64 = 1
	TypeIDORSetState      uint64 = 2
	TypeIDGCounterDelta   uint64 = 3
	TypeIDORSetDelta      uint64 = 4
	TypeIDPNCounterState  uint64 = 5
	TypeIDPNCounterDelta  uint64 = 6
	TypeIDLWWSetState     uint64 = 7
	TypeIDLWWSetDelta     uint64 = 8
	TypeIDLWWMapState     uint64 = 9
	TypeIDLWWMapDelta     uint64 = 10
	TypeIDRGAState        uint64 = 11
	TypeIDRGADelta        uint64 = 12
	TypeIDGSetState       uint64 = 13
	TypeIDGSetDelta       uint64 = 14
	TypeIDMVRegisterState uint64 = 15
	TypeIDMVRegisterDelta uint64 = 16
	// Observed-remove tree v1 carries immutable parent links with add/remove
	// semantics. A move-capable tree requires a new independently negotiated
	// frame pair; TypeIDs 17/18 must never be repurposed for it.
	TypeIDORTreeState uint64 = 17
	TypeIDORTreeDelta uint64 = 18
	// RGA run frames retain scalar Position semantics while compacting linear
	// same-replica insertion chains. They are the default protocol for new RGA
	// replication groups; TypeIDRGAState and TypeIDRGADelta remain immutable v1
	// contracts for explicitly negotiated legacy groups.
	TypeIDRGARunState uint64 = 19
	TypeIDRGARunDelta uint64 = 20
	// List RGA frames carry one canonical caller-coded value per position.
	// They are intentionally distinct from text RGA frames: a text position is
	// one Unicode scalar while a list position is one opaque application value.
	TypeIDListRGAState uint64 = 21
	TypeIDListRGADelta uint64 = 22
	// Rich text nests a run-v2 RGA frame with bounded inline formatting
	// registers. Its renderer schema is bound by replica.Manifest.SchemaID;
	// TypeIDs 23/24 and semantics version 1 are immutable.
	TypeIDRichTextState uint64 = 23
	TypeIDRichTextDelta uint64 = 24
)

Stable frame type assignments. Values are part of the v1 wire contract and must never be reused for a different payload shape.

Functions

func IsExperimentalFrame

func IsExperimentalFrame(typeID uint64) bool

IsExperimentalFrame reports whether typeID belongs to an implemented experimental protocol. Reserved or unknown type IDs return false.

func MarshalDiagnosticJSON

func MarshalDiagnosticJSON(summary StateSnapshot) ([]byte, error)

MarshalDiagnosticJSON encodes a caller-provided diagnostic summary. It is useful for CRDT delta log views that use the same schema as StateSnapshot. The summary must not contain application values or replication state.

func MarshalStateJSON

func MarshalStateJSON(value StateReporter) ([]byte, error)

MarshalStateJSON returns a compact JSON diagnostic summary for value.

This helper is intended for structured logs and human inspection. It does not encode CRDT state, deltas, or opaque application values, so its output cannot reconstruct a replica and must not be used as a wire format.

Types

type CRDT

type CRDT[T any] interface {
	Merge(other T) error
	State() StateSnapshot
}

CRDT is the common contract for state-based CRDTs.

For every concrete state type T, Merge must be commutative, associative, and idempotent. If Merge returns an error, it must leave the receiver unchanged.

type DeltaCapable

type DeltaCapable[T any, D any] interface {
	CRDT[T]
	ApplyDelta(delta D) error
}

DeltaCapable is implemented by a state-based CRDT that accepts a concrete, type-safe delta D. Delta mutators return D directly; the library does not maintain an implicitly acknowledged delta buffer.

type FrameType

type FrameType struct {
	StateID uint64
	DeltaID uint64
	UsesHLC bool
}

FrameType describes one fully implemented framed CRDT protocol. The type table is deliberately closed: reserving an ID alone must not make a payload eligible for batching or recovery before its concrete codec is available.

func DefaultRGAFrameType

func DefaultRGAFrameType() FrameType

DefaultRGAFrameType returns the compact run-v2 protocol for new RGA replication groups. Legacy scalar RGA v1 frames remain available only when a group explicitly enables experimental protocols for migration.

func FrameTypeForDelta

func FrameTypeForDelta(deltaID uint64) (FrameType, bool)

FrameTypeForDelta returns the supported protocol associated with deltaID.

func FrameTypeForState

func FrameTypeForState(stateID uint64) (FrameType, bool)

FrameTypeForState returns the supported protocol associated with stateID.

type ProtocolPolicy

type ProtocolPolicy struct {
	// AllowExperimental includes framed LWW-Set, LWW-Map, legacy scalar RGA v1,
	// and generic list RGA protocols. Keep it false until the
	// replication group has accepted their experimental API and
	// tombstone-retention lifecycle.
	AllowExperimental bool
}

ProtocolPolicy controls which implemented frame types one replication group advertises. It is a local, immutable-by-convention value for connection setup; it does not install a process-wide switch or permit runtime protocol registration.

Peers must compare FrameTypes before sending state or deltas. A matching TypeID remains necessary but is not sufficient: applications still own authentication, authorization, limits, and decoder selection.

Example

package main

import (
	"fmt"

	"github.com/DarkInno/crdt"
)

func main() {
	stable := crdt.ProtocolPolicy{}
	experimental := crdt.ProtocolPolicy{AllowExperimental: true}

	fmt.Println(stable.SupportsFrame(crdt.TypeIDRGAState))
	fmt.Println(experimental.SupportsFrame(crdt.TypeIDRGAState))
}

Output:
false
true

func (ProtocolPolicy) FrameTypes

func (p ProtocolPolicy) FrameTypes() []FrameType

FrameTypes returns a copy of every protocol enabled by p. The returned slice is stable in type-ID order and safe for callers to advertise or modify.

func (ProtocolPolicy) SupportsFrame

func (p ProtocolPolicy) SupportsFrame(typeID uint64) bool

SupportsFrame reports whether typeID is both implemented by this module and enabled by p. It applies to either a state or delta frame type ID.

type StateReporter

type StateReporter interface {
	State() StateSnapshot
}

StateReporter exposes an immutable CRDT diagnostic summary.

It intentionally excludes application values, mutation tags, clock state, and framed bytes. Use it for observability only, never to persist or replicate a CRDT.

type StateSnapshot

type StateSnapshot struct {
	Type           string `json:"type"`
	ReplicaID      string `json:"replica_id"`
	ElementCount   int    `json:"element_count"`
	TombstoneCount int    `json:"tombstone_count"`
}

StateSnapshot is an immutable summary of a CRDT state for diagnostics and observability. It never exposes mutable internal data.

type Tag

type Tag struct {
	ReplicaID string
	WallTime  uint64
	Logical   uint64
}

Tag uniquely identifies a CRDT mutation. WallTime, Logical, and ReplicaID are compared in that order. ReplicaID must be globally unique among live logical replicas; callers that reuse an ID across restarts must persist the last emitted clock state.

func (Tag) Compare

func (t Tag) Compare(other Tag) int

Compare returns -1, 0, or 1 according to the canonical ordering of tags.

func (Tag) Valid

func (t Tag) Valid() bool

Valid reports whether t is safe to use as a CRDT mutation identifier.