CRDTs (Conflict-Free Replicated Data Types) are data structures that can be updated independently and concurrently on multiple nodes without coordination, and can always be merged to a consistent state without conflicts. CRDTs enable collaborative editing, offline-capable apps, active-active multi-region replication, and distributed counters without the latency of consensus protocols. They achieve convergence through mathematical guarantees rather than locking or consensus.
G-Counter (Grow-Only Counter)
The simplest CRDT: a counter that only increases. Each node maintains its own count; the global counter is the sum of all node counts. Increment: node N increments its own slot (counter[N]++). Merge: take the element-wise maximum of two counter arrays. Query: sum all slots. Why max instead of sum for merge? If node A has [5, 3] and node B has [4, 3] (node B hasn’t seen A’s latest increment), merge = [max(5,4), max(3,3)] = [5, 3]. This prevents double-counting. G-Counters are used for: unordered event counting (page views, likes, impressions) where exact ordering doesn’t matter and absolute precision is required over performance.
PN-Counter (Positive-Negative Counter)
PN-Counter extends G-Counter to support decrement. Maintain two G-Counters: P (increments) and N (decrements). Value = sum(P) – sum(N). Increment: P[node]++. Decrement: N[node]++. Merge: merge P and N independently using G-Counter merge (element-wise max). Query: sum(P) – sum(N). Used for: inventory counters (can go down), vote counts, follower counts. The value can temporarily appear negative during a network partition if more decrements than increments are applied to one partition — this resolves correctly after merge. PN-Counters are the foundation for shopping cart item counts, upvote/downvote tallies, and any counter that goes both up and down.
LWW-Element-Set (Last-Write-Wins Set)
LWW-Element-Set stores (element, timestamp) pairs for adds and removes. To add: add (element, current_timestamp) to the add-set. To remove: add (element, current_timestamp) to the remove-set. Membership: element is in the set if its highest add-timestamp > its highest remove-timestamp. Merge: union the add-sets and remove-sets across replicas. Conflict resolution: the most recent operation wins (by timestamp). Limitation: requires synchronized clocks (or logical clocks) to determine which timestamp is “most recent”. Used for user presence status, shopping cart (last write to an item slot wins), and configuration values.
CRDT Sets: OR-Set (Observed-Remove Set)
OR-Set (Observed-Remove Set, also called 2P2P-Set) solves the tombstone problem: in an LWW-Set, removing an element that was concurrently re-added can produce incorrect results. OR-Set tags each add operation with a unique ID (UUID). To add element X: add (X, UUID). To remove element X: remove all (X, *) pairs that the node currently observes. Membership: X is in the set if there exists any (X, uuid) in the add-set that is not in the remove-set. Merge: union add-sets and remove-sets. An element added after a remove is never affected by that remove (it has a new UUID). Riak, Basho’s distributed database, uses OR-Set for its set data type.
Collaborative Text Editing: RGA and LSEQ
CRDTs power collaborative document editing (like Google Docs) by allowing concurrent edits without operational transformation (OT). RGA (Replicated Growable Array): each character has a globally unique position identifier. Insert inserts a character at a position relative to an existing character (to the right of character with ID X). Delete marks a character with a tombstone. Merge: merge inserts by their position identifiers; tombstones are replicated. The document is the ordered sequence of non-tombstoned characters. LSEQ assigns fractional positions between existing characters using a tree-based addressing scheme. Yjs and Automerge are popular CRDT-based libraries for collaborative applications.
CRDTs in Distributed Databases
Riak (Amazon Dynamo lineage) uses CRDTs natively for counters, sets, maps, registers, and flags — providing conflict-free convergence without application-level conflict resolution. Redis Cluster, Aerospike, and Fauna use CRDT-like approaches for geo-replication. CRDT-based replication enables active-active multi-region setups: every region accepts writes and replicates asynchronously; CRDTs ensure convergence when partitions heal. The trade-off: CRDTs can only represent operations that are commutative, associative, and idempotent — not all business logic maps to CRDTs. A bank balance (you cannot withdraw more than you have) cannot be correctly modeled as a PN-Counter alone — coordinated consensus is still needed for invariant-maintaining operations.
When to Use CRDTs
CRDTs are appropriate for: eventually consistent counters and sets where the last-write-wins or merge semantics are acceptable, collaborative editing where concurrent changes to different parts of a document should both be preserved, offline-capable mobile apps where the device can make changes without connectivity and sync later, and active-active multi-region replication where each region must accept writes without round-trip coordination. CRDTs are not appropriate for: financial transactions requiring exact balance checks, inventory where exact stock count matters for order placement, and any operation where invariants must be maintained across concurrent writes. In these cases, use consensus (Paxos, Raft) or centralized coordination.