Skip to content
Search

Conflict-free replicated data type

lastmod 2025-12-02created 2023-02-028 edits

In distributed computing, a conflict-free replicated data type is a data structure that is replicated across multiple computers in a network and has the following feature: applications can update any replica independently and concurrently without coordinating with other replicas.

Libraries

Softwares

  • Warp - A fast terminal written in Rust

Field guide

A CRDT (Conflict-free Replicated Data Type) is a distributed data structure that enables consistent data merging without coordination, even under network partitions or concurrent modifications

  • If data merging satisfies commutativity, associativity, and idempotence, all replicas eventually converge to the same state
  • Representative forms include G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT, and Logoot, each handling different requirements for add, remove, re-add, and order preservation
  • Delta CRDTs improve efficiency by sending only changes instead of the full state, and Garbage Collection is a key challenge for solving metadata accumulation
  • CRDTs are not a perfect solution, but are regarded as a strong option in systems where availability matters more than immediate consistency

Basic concepts of CRDTs

  • A CRDT is a data structure that can be merged without coordination even when concurrent modifications occur in a distributed environment
    • If the merge operation is commutative, associative, and idempotent, all replicas converge to the same state
  • Based on the concept of a Lattice, designed so the state always moves only “upward”
    • e.g. G-Counter merges each replica's count with max, guaranteeing lossless summation
  • There are two approaches to CRDTs: State-based (CvRDT) and Operation-based (CmRDT)
    • CvRDT merges the full state, CmRDT propagates operations

Main CRDT types

  • G-Counter: An increment-only counter that sums the values of each replica
  • PN-Counter: Combines increment and decrement G-Counters to support counting in both directions
  • G-Set: An add-only set
  • 2P-Set: Supports add and remove, but not re-add
  • LWW-Element-Set: Timestamp-based; the most recent operation wins
  • OR-Set: Uses unique tags to merge concurrent adds without data loss, add-wins behavior
  • LWW-Register / MV-Register: For storing a single value; LWW has a single winner, MV keeps all concurrent values
  • OR-Map: A map structure combining OR-Sets per key
  • RGA / WOOT / Logoot / LSEQ: CRDTs for ordered sequence data
    • RGA is tree-based, WOOT is based on bidirectional references, Logoot/LSEQ are based on position identifiers

Advanced CRDT concepts

  • Causal CRDTs: Track causality using version vectors, enabling more accurate conflict detection
  • Delta CRDTs: Improve network efficiency by sending only changes (deltas) instead of the full state
  • Tree CRDTs: Support replicating hierarchical data (file systems, etc.); parent-child relationships must be maintained
  • Observed-Remove Shopping Cart: An e-commerce shopping cart example combining OR-Set and PN-Counter

The Garbage Collection problem

  • CRDTs keep accumulating metadata for convergence, causing unbounded growth
    • e.g. tags in OR-Set, tombstones in RGA
  • Various strategies exist: time-based expiration, consensus-based deletion, version-vector-based causal tracking, metadata caps, checkpoint/rebase, etc.
  • Each approach requires a trade-off between safety (preventing zombie resurrection) and space efficiency

Performance and selection guide

  • Space and time complexity per CRDT type depends on the number of replicas, elements, tags, etc.
    • G/PN-Counter is proportional to the number of replicas, OR-Set to the number of tags, RGA accumulates tombstones
  • Delta CRDTs greatly improve merge performance
  • Selection criteria:
    • Only adds needed → G-Counter, G-Set
    • Removal needed, re-add not needed → 2P-Set
    • LWW acceptable → LWW-Set/Register
    • Preserve concurrent modifications → OR-Set, MV-Register
    • Order preservation needed → RGA, Logoot
    • Nested structures → OR-Map

Conclusion

  • CRDTs guarantee convergence without coordination, but metadata growth and complexity are drawbacks
  • Useful in availability-first systems, and each CRDT is optimized for a specific type of problem
  • In practice they are used alongside traditional databases, and a garbage collection strategy is essential
  • There is no “perfect CRDT”; the key is choosing one that fits the application's requirements

See also

Favorite site

Articles

author Zer0 sitemap