Conflict-Free Replicated Data Types (CRDTs): Ensuring Eventual Consistency Across Replicas

|

In the ever-expanding world of distributed systems, data replication plays a vital role in ensuring availability, fault tolerance, and resilience. However, replication introduces the challenge of data consistency when updates are made concurrently across nodes. Traditional consistency models like strong consistency can be too restrictive or inefficient for high-availability systems. This is where Conflict-Free Replicated Data Types (CRDTs) come in.

CRDTs are specially designed data structures that allow safe, concurrent, and asynchronous updates across replicas, with the guarantee that all replicas will eventually converge to the same state, even in the face of network partitions or delays.

What Are CRDTs?

CRDTs (Conflict-Free Replicated Data Types) are a family of data structures that enable concurrent updates without the need for distributed coordination or conflict resolution mechanisms like locks or consensus protocols (e.g., Paxos or Raft).

There are two main types of CRDTs:

  • State-based (Convergent) CRDTs (CvRDTs): Replicas exchange and merge full states.

  • Operation-based (Commutative) CRDTs (CmRDTs): Replicas propagate operations that are guaranteed to commute.

Key Properties of CRDTs

To ensure convergence, CRDTs follow these mathematical properties:

  1. Commutativity: Operations can be applied in any order and still result in the same final state.

  2. Associativity: Grouping of operations doesn’t affect the result.

  3. Idempotency: Applying the same operation multiple times doesn’t change the result after the first application.

These properties make CRDTs resilient to eventual delivery, retries, and reordering—common issues in distributed environments.

Use Cases of CRDTs

CRDTs are especially useful in:

  • Collaborative applications (e.g., Google Docs, Figma)

  • Distributed databases (e.g., Riak, Redis CRDTs)

  • Edge computing and offline-first mobile apps (e.g., local-first software)

  • Messaging systems and social media (likes, counters, feeds)

Common CRDT Examples and Their Implementations

Let’s dive into some popular CRDTs and implement them in Python for demonstration purposes.

Grow-Only Counter (G-Counter)

A G-Counter is a monotonically increasing counter where each node maintains its own count. Merging takes the maximum of each node’s count.

python
class GCounter:
def __init__(self, node_id):
self.node_id = node_id
self.counters = {node_id: 0}def increment(self, value=1):
self.counters[self.node_id] += valuedef merge(self, other):
for node, count in other.counters.items():
self.counters[node] = max(self.counters.get(node, 0), count)def value(self):
return sum(self.counters.values())# Example
nodeA = GCounter(“A”)
nodeB = GCounter(“B”)nodeA.increment()
nodeB.increment()
nodeB.increment()nodeA.merge(nodeB)
nodeB.merge(nodeA)print(nodeA.value()) # Output: 3
print(nodeB.value()) # Output: 3

Grow-Only Set (G-Set)

A G-Set only supports additions, not deletions. Merging is done via union.

python
class GSet:
def __init__(self):
self.set = set()def add(self, element):
self.set.add(element)def merge(self, other):
self.set |= other.setdef elements(self):
return self.set# Example
set1 = GSet()
set2 = GSet()set1.add(“apple”)
set2.add(“banana”)set1.merge(set2)print(set1.elements()) # Output: {‘apple’, ‘banana’}

Last-Write-Wins Register (LWW Register)

This CRDT resolves conflicting values by using timestamps.

python

import time

class LWWRegister:
def __init__(self):
self.value = None
self.timestamp = 0

def write(self, value, timestamp=None):
timestamp = timestamp or time.time()
if timestamp >= self.timestamp:
self.value = value
self.timestamp = timestamp

def merge(self, other):
if other.timestamp >= self.timestamp:
self.value = other.value
self.timestamp = other.timestamp

# Example
reg1 = LWWRegister()
reg2 = LWWRegister()

reg1.write(“A”, 100)
reg2.write(“B”, 200)

reg1.merge(reg2)
print(reg1.value) # Output: B

Observed-Remove Set (OR-Set)

Supports adds and removes while avoiding accidental data resurrection.

python

import uuid

class ORSet:
def __init__(self):
self.adds = {}
self.removes = set()

def add(self, element):
tag = uuid.uuid4()
self.adds.setdefault(element, set()).add(tag)

def remove(self, element):
if element in self.adds:
self.removes |= self.adds[element]

def elements(self):
return {e for e, tags in self.adds.items() if tags – self.removes}

def merge(self, other):
for e, tags in other.adds.items():
self.adds.setdefault(e, set()).update(tags)
self.removes |= other.removes

# Example
setA = ORSet()
setB = ORSet()

setA.add(“apple”)
setB.add(“apple”)

setA.remove(“apple”)

setA.merge(setB)

print(setA.elements()) # Output: {‘apple’}

PN-Counter (Positive-Negative Counter)

Supports both increments and decrements, internally using two G-Counters.

python
class PNCounter:
def __init__(self, node_id):
self.inc = GCounter(node_id)
self.dec = GCounter(node_id)def increment(self, value=1):
self.inc.increment(value)def decrement(self, value=1):
self.dec.increment(value)def merge(self, other):
self.inc.merge(other.inc)
self.dec.merge(other.dec)def value(self):
return self.inc.value() – self.dec.value()# Example
pnA = PNCounter(“A”)
pnB = PNCounter(“B”)pnA.increment(3)
pnB.decrement(1)pnA.merge(pnB)

print(pnA.value()) # Output: 2

Benefits of Using CRDTs

  • High Availability: No need to block writes due to coordination.

  • Offline Support: Local updates can happen without network.

  • Eventually Consistent: Strong convergence guarantees.

  • Fault Tolerance: Handles network partitions gracefully.

  • Conflict-Free by Design: No application-specific resolution required.

Limitations and Trade-offs

While powerful, CRDTs come with some limitations:

  • Memory Overhead: OR-Sets and PN-Counters can grow large due to metadata (tags, per-node counts).

  • No Global Invariants: Constraints like “total must not exceed X” are hard to enforce.

  • Limited Expressiveness: Not every data structure can be easily modeled as a CRDT.

  • Merge Complexity: Operation-based CRDTs require reliable causal delivery.

CRDTs in Real-World Systems

  • Riak: One of the earliest production-grade distributed databases to integrate CRDTs.

  • Redis CRDTs: Supported in Redis Enterprise for globally distributed applications.

  • Automerge/Yjs: CRDTs used for real-time collaboration in web apps.

  • Databricks Delta: Uses CRDT-like techniques for scalable conflict resolution.

Conclusion

Conflict-Free Replicated Data Types (CRDTs) represent a significant leap in the design of distributed, fault-tolerant systems. By avoiding the need for centralized coordination or complex consensus algorithms, CRDTs provide a mathematically sound and elegant way to ensure that replicas eventually converge to a consistent state—even in the presence of concurrent updates, network partitions, or node failures.

Through our examples—G-Counter, G-Set, LWW Register, OR-Set, and PN-Counter—we’ve explored how CRDTs handle different data types and operations. Each is tailored to a specific problem in distributed computing, demonstrating that with the right data structures, we can build systems that are both highly available and strongly convergent.

CRDTs empower developers to build collaborative tools, offline-first applications, and geo-distributed databases that “just work” without requiring intricate conflict resolution logic. As the need for scalable and robust distributed applications grows, understanding and using CRDTs will become an essential skill for software engineers, architects, and data platform designers.