Conflict-free Replicated Data Types (CRDTs)

Source: Dev.to

Background

Modern distributed systems frequently replicate data across multiple machines, regions, or user devices. Replication is a fundamental design choice that improves system behavior and user experience.

Why replication matters

• High availability – the system continues working even if some nodes fail
• Low latency – users interact with nearby replicas
• Offline support – devices can operate while disconnected
• Fault tolerance – redundancy prevents data loss

The core problem

What happens when multiple replicas modify the same data concurrently?

In distributed environments, concurrent updates are not an edge case — they are the norm.

Real‑world conditions

• Nodes maintain independent copies of data
• Network partitions and disconnections occur
• Updates may happen at the same time
• Messages can be delayed or reordered

Without careful design, these realities can cause:

• Conflicts between updates
• Lost updates
• Diverging replicas
• Inconsistent system state

Classic coordination‑based solutions

• Locks
• Leader‑based systems
• Consensus protocols (e.g., Paxos, Raft)

While effective, coordination introduces trade‑offs:

• Increased latency
• Reduced availability during failures
• Higher system complexity

Correctness is preserved, but performance and resilience may suffer.

---

Conflict‑free Replicated Data Types (CRDTs)

CRDTs take a fundamentally different approach. Instead of preventing conflicts through coordination, they are designed so that:

• Concurrent updates are expected
• Conflicts are mathematically impossible or automatically resolved
• Replicas always converge to the same state

This enables systems that remain:

• Highly available
• Low latency
• Partition tolerant

CRDTs shift the burden from runtime coordination to data‑structure design.

What is a CRDT?

A Conflict‑free Replicated Data Type (CRDT) is a data structure specifically designed for distributed systems where multiple replicas may update data independently.

A CRDT guarantees that:

1. Replicas can update data independently.
2. Replicas can merge safely without coordination.
3. Conflicts do not occur (by design).
4. All replicas eventually converge to the same state.
5. No central coordinator or locking mechanism is required.

CRDTs provide strong eventual consistency through deterministic merge rules.

Core merge properties

CRDT merge operations satisfy three critical algebraic properties:

Because of these properties, replicas always converge regardless of:

• Message delays
• Network partitions
• Duplicate updates
• Out‑of‑order delivery

---

Two Broad CRDT Families

1. State‑based (a.k.a. Convergent) CRDTs

• How they work

  1. Each replica updates its local state independently.
  2. Replicas periodically share their full state with peers.
  3. A deterministic merge function combines the received state with the local one.

• Key characteristics

  • Simple to reason about
  • Naturally resilient to message duplication
  • Robust under unreliable networks
  • Drawback: larger messages due to full‑state transfer

2. Operation‑based (a.k.a. Commutative) CRDTs

• How they work

  1. Replicas generate operations (add, remove, insert, …).
  2. Operations are broadcast to other replicas.
  3. Operations are designed to commute safely, so order does not matter.

• Key characteristics

  • More bandwidth‑efficient (smaller messages)
  • Lower per‑message size
  • Requires reliable delivery assumptions (or causal broadcast)
  • More complex to design correctly

---

Simple Counter Example (State‑based)

Assume two replicas start with the same value:

Value = 0

Both go offline and update independently:

Merge rule: take the maximum for each replica slot.

Merged result = { A: 1, B: 1 } → Value = 2

No updates are lost, even without coordination.

PN‑Counter (supports decrements)

A PN‑Counter maintains two internal G‑Counters:

• P – counts increments (positive)
• N – counts decrements (negative)

value = P − N

This preserves convergence while allowing both operations.

---

Text‑editing Example (Operation‑based)

Initial text

Hello World

Two users edit concurrently at the same logical position:

If edits rely purely on numeric indexes (6), the order of arrival determines the final string, potentially overwriting one another and causing divergence.

CRDT‑based approach

• Every character receives a unique identifier (e.g., a tuple of replica ID + counter).
• Insertions are expressed relative to identifiers, not absolute indexes.
• Concurrent inserts are preserved by design.

Possible merged results (deterministic tie‑breakers decide order):

• Hello vikasnannu World
• Hello nannuvikas World

All replicas agree on the same final text.

---

CRDT Catalog

---

Takeaways

• CRDTs eliminate the need for runtime coordination by embedding conflict‑resolution logic in the data type itself.
• They provide strong eventual consistency: all replicas converge to the same state once they have seen the same set of updates.
• Choosing between state‑based and operation‑based CRDTs depends on bandwidth, reliability, and design‑complexity considerations.
• A rich ecosystem of CRDTs (registers, counters, sets, maps, etc.) enables safe replication for a wide variety of application domains.

Models

• Sequences maintain ordered collections, essential for collaborative editing.

Use Cases

• Text editors
• Real‑time collaboration tools
• Ordered shared logs

Deletion vs. Insertion

• Deletion is fundamentally harder than insertion in distributed systems.
• A common CRDT technique is the use of tombstones:
  • Elements are marked as deleted instead of being removed.
  • Metadata is preserved for correct merging.

Trade‑off

• Increased storage / metadata overhead
• Guaranteed convergence and correctness

Safety Properties of CRDT‑Based Systems

• No lost updates
• No manual conflict resolution
• Eventual convergence across replicas
• High availability under failures
• Partition tolerance by design
• No locks, leaders, or coordination required

Why CRDTs Are Powerful

• Align naturally with distributed environments:
  • Allow independent replica updates
  • Operate correctly under offline conditions
  • Eliminate complex conflict‑resolution logic
  • Scale efficiently across regions
  • Reduce coordination overhead

Practical Challenges (Limitations)

• Metadata growth over time → memory and storage overhead
• Non‑intuitive ordering behavior
• Difficulty enforcing strict invariants

Poor Fit For Systems Requiring

• Strong consistency guarantees
• Global ordering constraints
• Complex transactional invariants (e.g., banking systems, financial ledgers, strictly serialized workflows)

Contrasting Design Philosophies

Strong Consistency Systems

• Use consensus protocols
• Enforce global ordering
• Provide immediate consistency
• Typically incur higher latency

CRDT‑Based Systems

• Avoid coordination
• Accept eventual consistency
• Prioritize availability and latency

The correct choice depends entirely on application requirements.

When CRDTs Work Best

• Concurrent updates are common
• Offline operation is expected
• Low latency is critical
• Eventual consistency is acceptable

Example Domains

• Collaborative editors
• Offline‑first applications
• Distributed counters
• Edge / multi‑device systems
• Shared‑state applications

Reasoning About CRDTs

• Replicas never fight over updates.
• CRDTs prevent conflicts by design; every update is structured so that merging is always deterministic and safe.

Conclusion

CRDTs represent an elegant shift in distributed‑system design:

Instead of coordinating every update, replicas evolve independently while still guaranteeing convergence.

They are especially valuable in modern systems where:

• Offline usage is normal
• Latency directly impacts user experience
• Global coordination is expensive

When used appropriately, CRDTs dramatically simplify distributed data management while improving system resilience.