CRDTs (Conflict-free Replicated Data Types)

Imagine you're building a collaborative document editor like Google Docs. Two users are editing the same document simultaneously—one in New York, another in Tokyo. Each types a word at the exact same position at the exact same moment. Network latency means neither sees the other's change immediately.

The question that defines distributed systems: When these edits finally propagate to each replica, what should the document contain? Whose edit wins? Can both edits be preserved? How do we ensure that every replica eventually agrees on the same final state—without expensive coordination?

This is the conflict resolution problem, and it has haunted distributed systems engineers since the first networked databases. For decades, the answers were unsatisfying: use locks (kills performance), use a single leader (creates bottlenecks), use timestamps (risks data loss), or accept inconsistency (confuses users).

To understand why CRDTs are revolutionary, we must first understand the problem they solve at a fundamental level. In distributed systems, data is replicated across multiple nodes for fault tolerance, availability, and low-latency access. But replication creates a fundamental tension:

The Replication Dilemma:

• If we require all replicas to agree before accepting a write, we get strong consistency but sacrifice availability during network partitions (per the CAP theorem)
• If we allow replicas to accept writes independently, we get high availability but risk conflicting updates

For decades, system designers chose one of these extremes. But there's a third path—one that embraces concurrent updates and resolves conflicts mathematically rather than operationally.

Example: The Lost Update Problem

Consider a distributed shopping cart replicated across three data centers:

1. User adds "iPhone" to cart in DC-East
2. Simultaneously, user adds "AirPods" to cart in DC-West (via a different CDN route)
3. Network partition prevents immediate synchronization
4. When partition heals, DC-East has {iPhone}, DC-West has {AirPods}

With Last-Write-Wins, one item disappears forever. With application-level merge, you need custom code that might have bugs. With consensus, the partition would have blocked one of the writes entirely.

What if there were a data structure that could merge {iPhone} and {AirPods} into {iPhone, AirPods} automatically, deterministically, and correctly—every time?

CRDT stands for Conflict-free Replicated Data Type. The term was formally introduced by Marc Shapiro et al. in their landmark 2011 paper "Conflict-free Replicated Data Types." But the concept draws on decades of research in distributed computing, particularly around lattice theory and eventual consistency.

Formal Definition:

A CRDT is a data type that satisfies the following property:

Strong Eventual Consistency (SEC): Replicas that have received the same set of updates will have equivalent state—regardless of the order in which those updates were received or applied.

This is stronger than ordinary "eventual consistency," which only guarantees convergence "eventually" without specifying when. SEC guarantees that once messages are delivered (even out of order), replicas converge immediately.

Why These Properties Matter:

Commutativity ensures order doesn't matter. If Replica A receives updates from B then C, and Replica D receives updates from C then B, they still converge. This is crucial because network delays can reorder messages arbitrarily.

Associativity ensures that it doesn't matter how we group merges. Whether we merge A with B first, then merge the result with C, or merge B with C first then A—the final state is identical.

Idempotency ensures that redelivery is safe. If a network hiccup causes an update to be received twice, the result is the same as receiving it once. This eliminates the need for exactly-once delivery guarantees.

CRDTs come in two fundamental variants, each with its own approach to achieving convergence:

1. State-based CRDTs (CvRDTs - Convergent Replicated Data Types)

• Replicas periodically send their entire state to other replicas
• Receiving replica merges incoming state with its own using a merge function
• The merge function must be commutative, associative, and idempotent

2. Operation-based CRDTs (CmRDTs - Commutative Replicated Data Types)

• Replicas broadcast discrete operations (not full state) to other replicas
• Operations must be designed to commute—applying them in any order yields the same result
• Requires reliable broadcast (all operations eventually delivered to all replicas)

Equivalence and Conversion:

Shapiro et al. proved that state-based and operation-based CRDTs are equivalent in terms of expressiveness—any CvRDT can be expressed as a CmRDT and vice versa. In practice:

• Delta-state CRDTs bridge the gap: they send only the changes (like op-based) but use state-based merge semantics
• The choice between them is largely practical: network guarantees, state size, and implementation complexity

Hybrid Approaches:

Modern CRDT implementations often use delta-state approaches:

1. Track changes since last sync as a delta
2. Transmit only the delta (bandwidth efficient like CmRDT)
3. Merge using lattice join (robust like CvRDT)
4. Fall back to full state sync if deltas are lost

Understanding why CRDTs work requires grasping the concept of monotonic semi-lattices. This sounds intimidating but is surprisingly intuitive once visualized.

The Key Insight: State Can Only Go "Up"

In a CRDT, the state space forms a partial order where every update moves the state "upward" in the lattice. The merge function computes the least upper bound of two states—the smallest state that is greater than or equal to both.

Because state only moves up, and there's always a unique least upper bound, concurrent updates from different replicas can only converge to the same point—they're both climbing the same lattice toward the same peaks.

Concrete Example: Set Union

The simplest CRDT is a grow-only set (G-Set). Each replica maintains a set. The merge function is set union:

Replica A: {apple, banana}
Replica B: {banana, cherry}

merge(A, B) = {apple, banana, cherry}

Set union is:

• Commutative: A ∪ B = B ∪ A
• Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C)
• Idempotent: A ∪ A = A

No matter how many replicas, in what order they sync, or how many times messages are duplicated—everyone eventually has the same set containing all elements anyone ever added.

To fully appreciate CRDTs, let's compare them systematically against the traditional approaches we reviewed earlier. This comparison illuminates when CRDTs shine and where they have trade-offs.

Key Trade-offs:

Semantic Constraints: Not every operation can be made conflict-free. CRDTs work by restricting operations to those that can mathematically commute. You can't have a CRDT that supports arbitrary "set to value X" operations from multiple replicas—one would have to win. CRDTs embrace operations like "add to set," "increment counter," "insert at position" that can be meaningfully merged.

Space Overhead: Some CRDTs carry metadata proportional to the number of replicas or operations. A vector clock-based set might store a counter per replica. This overhead is the price of tracking enough information to merge correctly.

Permanent Tombstones: In CRDTs that support deletion (like OR-Sets), deleted elements often leave behind "tombstones" that must be retained to prevent resurrection. Garbage collection of tombstones is an active research area.

CRDTs have moved from academic research to production systems powering some of the world's largest applications. Understanding where they're deployed illuminates their practical value.

Case Study: Collaborative Text Editing

Text CRDTs power real-time collaboration in tools like Google Docs, Notion, and Figma. The challenge: how do you merge concurrent edits to the same document?

Traditional approaches (Operational Transformation, used by early Google Docs) required a central server to transform operations. Text CRDTs (like WOOT, RGA, or Yjs's YATA) embed enough metadata in each character that any replica can merge any sequence of operations.

For example, instead of storing:

"Hello World"

A text CRDT might store:

{id: (A,1), char: 'H', after: null}
{id: (A,2), char: 'e', after: (A,1)}
{id: (A,3), char: 'l', after: (A,2)}
...

Each character has a unique ID and knows which character it follows. When concurrent insertions happen at the same position, the IDs provide a deterministic tiebreaker.

CRDTs represent a specific position in the design space defined by the CAP theorem. Understanding this position clarifies their guarantees and limitations.

The CALM Theorem Connection:

The CALM theorem (Consistency As Logical Monotonicity) by Hellerstein and Alvaro provides the theoretical foundation for why CRDTs work:

Programs that are logically monotonic can be implemented in a consistent, coordination-free way.

Programs requiring non-monotonic operations (like negation or universal quantification) require coordination.

CRDTs are the practical realization of this theorem. By restricting to monotonic operations (only adding information, never removing or contradicting), CRDTs achieve coordination-free consistency.

Practical Implication:

If you can express your data model and operations in monotonic terms, you can use CRDTs and get availability + eventual consistency without coordination. If your semantics require "check if X doesn't exist, then do Y," you need coordination—no CRDT can help.

We've established the foundational understanding of CRDTs that will guide our deeper exploration in subsequent pages. Let's consolidate the key concepts:

What's Next:

Now that we understand what CRDTs are and why they work, the next page dives into the two families in detail. We'll examine State-based vs Operation-based CRDTs, exploring their implementation differences, trade-offs, and when to choose each approach. We'll see concrete code examples and understand the engineering decisions involved in building each type.