CRDT Types

Deep dive into LWW-Register, PN-Counter, OR-Set, RGA List, and Nested Document merge semantics, algorithms, and use cases.

Grove supports five field-level CRDT types. Each has different merge semantics optimized for specific use cases. This page covers the algorithms, concurrent update behavior, and practical guidance for each type.

LWW-Register (Last-Writer-Wins)

Tag: crdt:lww

The simplest CRDT: when two nodes write to the same field concurrently, the write with the higher HLC timestamp wins.

Merge Algorithm

MergeLWW(local, remote):
  if remote.HLC > local.HLC:
    return remote   // Remote wins
  if local.HLC > remote.HLC:
    return local    // Local wins
  // Tie: compare NodeIDs lexicographically
  if remote.NodeID > local.NodeID:
    return remote
  return local

The HLC comparison is: timestamp first, then counter, then node ID. This guarantees total ordering with no ambiguity.

Concurrent Update Example

Node A (ts=100): Title = "Draft"
Node B (ts=105): Title = "Final"

After sync: Title = "Final" (Node B wins, higher timestamp)

Node A (ts=100, c=1): Title = "Draft"
Node B (ts=100, c=1): Title = "Final"

After sync: Title depends on NodeID comparison (deterministic tiebreak)

Usage

type Document struct {
    grove.BaseModel `grove:"table:documents,alias:d"`
    ID      string `grove:"id,pk"`
    Title   string `grove:"title,crdt:lww"`
    Body    string `grove:"body,crdt:lww"`
    Status  string `grove:"status,crdt:lww"`
}

Best For

Scalar values: strings, booleans, numbers, JSON objects
Fields where "last write" is the desired resolution
Configuration values, status fields, free-text content

Go API

Function	Signature	Description
`MergeLWW`	`(local, remote LWWRegister) LWWRegister`	Returns the register with the higher HLC

PN-Counter (Positive-Negative Counter)

Tag: crdt:counter

A counter that supports both increment and decrement operations across multiple nodes without conflicts. Each node tracks its own increments and decrements independently.

Merge Algorithm

MergeCounter(local, remote):
  for each nodeID in union(local.nodes, remote.nodes):
    merged.Increments[nodeID] = max(local.Increments[nodeID], remote.Increments[nodeID])
    merged.Decrements[nodeID] = max(local.Decrements[nodeID], remote.Decrements[nodeID])
  return merged

Value(state):
  return sum(Increments) - sum(Decrements)

Taking the per-node max ensures that updates are idempotent and order-independent.

Concurrent Update Example

Node A: Increment(+5)  -> Increments{"A": 5}
Node B: Increment(+3)  -> Increments{"B": 3}

After sync both nodes:
  Increments{"A": 5, "B": 3}
  Value = 5 + 3 = 8

Node A: Decrement(-2)  -> Decrements{"A": 2}
After sync:
  Increments{"A": 5, "B": 3}, Decrements{"A": 2}
  Value = (5 + 3) - 2 = 6

State Structure

type PNCounterState struct {
    Increments map[string]int64 `json:"inc"` // nodeID -> cumulative increment
    Decrements map[string]int64 `json:"dec"` // nodeID -> cumulative decrement
}

Usage

type Article struct {
    grove.BaseModel `grove:"table:articles,alias:a"`
    ID        string `grove:"id,pk"`
    Title     string `grove:"title,crdt:lww"`
    ViewCount int64  `grove:"view_count,crdt:counter"`
    Likes     int64  `grove:"likes,crdt:counter"`
}

Best For

View counts, like counts, vote tallies
Inventory quantities across warehouses
Any numeric value that multiple nodes increment/decrement concurrently

Go API

Function	Signature	Description
`NewPNCounterState`	`() *PNCounterState`	Creates an empty counter state
`MergeCounter`	`(local, remote PNCounterState) PNCounterState`	Per-node max merge
`Value`	`(s *PNCounterState) int64`	Returns sum(increments) - sum(decrements)
`CounterFromFieldState`	`(fs FieldState) PNCounterState`	Extracts counter state from a field

OR-Set (Observed-Remove Set)

Tag: crdt:set

An add-wins observed-remove set. When one node adds an element and another concurrently removes it, the add wins. Removals only affect elements that were observed at the time of removal.

Merge Algorithm

MergeSet(local, remote):
  // Union all entries (element -> tags)
  for each element in union(local.Entries, remote.Entries):
    merged.Entries[element] = union(local.tags, remote.tags)

  // Union removed tags
  merged.Removed = union(local.Removed, remote.Removed)

  return merged

Elements(state):
  result = []
  for each element in state.Entries:
    if any tag for this element is NOT in state.Removed:
      result.add(element)
  return result

Each add operation creates a unique tag (nodeID:HLC). Removes mark specific tags as removed. If a new add happens concurrently with a remove, the new add's tag is not in the removed set, so the element survives.

Concurrent Update Example

Initial state: Tags = {"go", "api"}

Node A: Remove("api")
  -> Removes the tag for "api" that existed at time of observation

Node B: Add("api")
  -> Creates a new tag for "api" with a new HLC

After sync:
  "api" has Node B's new tag, which is NOT in the removed set
  -> Tags = {"go", "api"}  (add wins!)

State Structure

type ORSetState struct {
    // Entries maps element (JSON string) -> list of tags (add operations).
    Entries map[string][]Tag `json:"entries"`

    // Removed maps tag keys to true for removed tags.
    Removed map[string]bool `json:"removed"`
}

type Tag struct {
    NodeID string `json:"node_id"`
    HLC    HLC    `json:"hlc"`
}

Tag Key Format

Tags are uniquely identified by the string nodeID:HLC{ts:<ts> c:<c> node:<node>}. This format must match across all language implementations for cross-platform sync.

Usage

type Project struct {
    grove.BaseModel `grove:"table:projects,alias:p"`
    ID       string   `grove:"id,pk"`
    Name     string   `grove:"name,crdt:lww"`
    Tags     []string `grove:"tags,type:jsonb,crdt:set"`
    Members  []string `grove:"members,type:jsonb,crdt:set"`
}

Best For

Tags, labels, categories
Member lists, collaborator lists
Any collection where concurrent add/remove must converge

Go API

Function	Signature	Description
`NewORSetState`	`() *ORSetState`	Creates an empty set state
`MergeSet`	`(local, remote ORSetState) ORSetState`	Union merge with add-wins
`Elements`	`(s *ORSetState) []json.RawMessage`	Returns elements with at least one non-removed tag
`SetFromFieldState`	`(fs FieldState) ORSetState`	Extracts set state from a field

RGA List (Replicated Growable Array)

Tag: crdt:list

An ordered list that supports concurrent insert, delete, and move operations. The list maintains a tree of nodes where each insertion creates a new child node under the insert position, and ordering is determined by DFS traversal sorted by HLC timestamps.

Merge Algorithm

MergeList(local, remote):
  merged.Nodes = union(local.Nodes, remote.Nodes)
  merged.Tombstones = union(local.Tombstones, remote.Tombstones)

  // DFS traversal: children sorted by HLC (descending)
  result = DFS(merged.Root, sortChildrenByHLC)
  return filter(result, not in merged.Tombstones)

Each node carries: ID (unique), ParentID (insert position), Value, HLC (creation timestamp), and an optional Tombstone flag. Concurrent inserts at the same position are ordered by HLC, giving a deterministic total order.

Concurrent Update Example

Initial list: ["A", "B", "C"]

Node 1 (ts=100): Insert "X" after "A"  -> ["A", "X", "B", "C"]
Node 2 (ts=105): Insert "Y" after "A"  -> ["A", "Y", "B", "C"]

After sync: ["A", "Y", "X", "B", "C"]
  (Node 2's "Y" has higher HLC, sorts before "X" among children of "A")

Node 1 (ts=110): Delete "B"  -> tombstone node "B"
Node 2 (ts=108): Move "C" before "B"  -> re-parent "C" under "A"

After sync: ["A", "Y", "X", "C"]
  ("B" is tombstoned, "C" re-parented)

State Structure

type RGAListState struct {
    Nodes      map[string]*RGANode `json:"nodes"`
    Tombstones map[string]bool     `json:"tombstones"`
    RootID     string              `json:"root_id"`
}

type RGANode struct {
    ID       string          `json:"id"`
    ParentID string          `json:"parent_id"`
    Value    json.RawMessage `json:"value"`
    HLC      HLC             `json:"hlc"`
}

Usage

type TaskBoard struct {
    grove.BaseModel `grove:"table:boards,alias:b"`
    ID    string   `grove:"id,pk"`
    Name  string   `grove:"name,crdt:lww"`
    Tasks []string `grove:"tasks,type:jsonb,crdt:list"`
}

Best For

Ordered collections (task lists, kanban columns)
Drag-and-drop reordering across multiple clients
Sequential data where position matters (playlist items, paragraph ordering)
Any list where concurrent insert/delete/move must converge

Go API

Function	Signature	Description
`NewRGAListState`	`() *RGAListState`	Creates an empty list state
`MergeList`	`(local, remote RGAListState) RGAListState`	Union nodes, DFS traversal merge
`ListElements`	`(s *RGAListState) []json.RawMessage`	Returns ordered elements (excludes tombstoned)
`ListFromFieldState`	`(fs FieldState) RGAListState`	Extracts list state from a field

Nested Document

Tag: crdt:document

A hierarchical document CRDT that supports per-path field merging with heterogeneous child types. Each path in the document can independently use a different CRDT type (LWW, counter, set, or list), enabling complex nested structures like forms, user profiles, and JSON-like documents.

Merge Algorithm

MergeDocument(local, remote):
  allPaths = union(keys(local.Fields), keys(remote.Fields))
  for each path in allPaths:
    localField  = local.Fields[path]
    remoteField = remote.Fields[path]

    // Delegate to MergeEngine based on each field's CRDT type
    merged.Fields[path] = MergeEngine.MergeField(localField, remoteField)

  return merged

Each path (e.g., "address.city", "tags", "stats.viewCount") stores its own FieldState with an independent CRDT type. This allows mixing LWW fields, counters, sets, and lists at different paths within the same document.

Path-Based Addressing

Paths use dot notation to address nested fields:

"name"              -> top-level LWW field
"address.city"      -> nested LWW field
"address.zip"       -> nested LWW field
"tags"              -> top-level OR-Set
"stats.viewCount"   -> nested PN-Counter
"items"             -> top-level RGA List

Concurrent Update Example

Node A: SetPath("address.city", "New York")   // LWW at path "address.city"
Node B: SetPath("address.zip", "10001")        // LWW at path "address.zip"

After sync: both paths merge independently
  address.city = "New York", address.zip = "10001"

Node A: IncrementPath("stats.viewCount", 5)    // Counter at path "stats.viewCount"
Node B: IncrementPath("stats.viewCount", 3)    // Counter at path "stats.viewCount"

After sync: stats.viewCount = 8 (counter merge)

State Structure

type DocumentCRDTState struct {
    Fields map[string]*FieldState `json:"fields"`
}

Each entry in Fields is keyed by the dot-notation path and holds a standard FieldState with its own CRDT type (TypeLWW, TypeCounter, TypeSet, or TypeList).

Usage

type UserProfile struct {
    grove.BaseModel `grove:"table:profiles,alias:p"`
    ID      string         `grove:"id,pk"`
    Data    map[string]any `grove:"data,type:jsonb,crdt:document"`
}

Best For

JSON-like nested structures with independent field-level merge
Forms with nested sections (address, preferences, settings)
User profiles with mixed data types per field
Any document where different paths need different merge strategies

Go API

Function	Signature	Description
`NewDocumentCRDTState`	`() *DocumentCRDTState`	Creates an empty document state
`MergeDocument`	`(local, remote DocumentCRDTState) DocumentCRDTState`	Per-path field merge
`DocumentPaths`	`(s *DocumentCRDTState) []string`	Returns all paths in the document
`DocumentFromFieldState`	`(fs FieldState) DocumentCRDTState`	Extracts document state from a field

MergeEngine

The MergeEngine dispatches to the correct merge function based on the CRDT type of each field. It handles full-state merging for records with multiple fields.

Field-Level Merge

engine := crdt.NewMergeEngine()

// Merge a single field.
merged, err := engine.MergeField(localFieldState, remoteFieldState)

MergeField dispatches based on FieldState.Type:

TypeLWW calls MergeLWW
TypeCounter calls MergeCounter
TypeSet calls MergeSet
TypeList calls MergeList
TypeDocument calls MergeDocument

If the local state is nil, the remote state is accepted directly.

Record-Level Merge

// Merge all fields of a record at once.
merged, err := engine.MergeState(localState, remoteState)

MergeState iterates over all fields in both states and merges each one. It also handles tombstone propagation: if either state is tombstoned with a higher HLC, the merged result is tombstoned.

Choosing the Right Type

Scenario	Recommended Type	Why
User edits a title	`crdt:lww`	Last edit should win
Page view counter	`crdt:counter`	Multiple nodes increment independently
Adding tags to a post	`crdt:set`	Concurrent add/remove should converge
JSON config object	`crdt:lww`	Treat the whole object as one value
Shopping cart items	`crdt:set`	Add-wins prevents lost items
Score in a game	`crdt:counter`	Multiple score sources merge correctly
Status field (draft/published)	`crdt:lww`	Last status change wins
Task list ordering	`crdt:list`	Concurrent insert/reorder must converge
Kanban board columns	`crdt:list`	Drag-and-drop across multiple users
Playlist items	`crdt:list`	Ordered sequence with concurrent edits
User profile with nested fields	`crdt:document`	Independent merge per nested path
Form with mixed field types	`crdt:document`	Different merge strategies per section
Settings with counters and flags	`crdt:document`	Heterogeneous child types at each path

CRDT Types

On this page