CRDTs: Conflict-Free Replicated Data Types

A conflict-free replicated data type (CRDT) is a data structure designed so that replicas can be updated independently and concurrently, without coordination, and are guaranteed to converge to the same state once they have exchanged their updates. CRDTs provide strong eventual consistency: any two replicas that have received the same set of updates are in the same state, regardless of the order in which the updates arrived.

The problem

In a replicated store that accepts writes at several nodes (multi-leader or leaderless replication), two replicas can update the same value concurrently during a network partition or before replication catches up. When the replicas later exchange updates, the system must merge them. Options are:

• Pick one write and discard the other (last-write-wins). This loses data.
• Keep both versions and ask the application to merge them (siblings). This pushes complexity to every client.
• Use a data type whose merge is defined by construction and always yields the same result. This is the CRDT approach.

CRDTs avoid consensus and locking, so a replica can always accept a write, even while partitioned. This is an availability-oriented choice in the sense of the CAP theorem.

State-based CRDTs (CvRDT)

Each replica holds a full state. Replicas periodically send their state to others, and the receiver applies a merge function. Convergence is guaranteed if the states form a join semilattice and merge is the least upper bound. In practice, merge must be:

• Commutative: merge(a, b) == merge(b, a)
• Associative: merge(merge(a, b), c) == merge(a, merge(b, c))
• Idempotent: merge(a, a) == a

Local updates must also only move the state upward in the semilattice order. Because merge is idempotent, duplicate and reordered state messages are harmless. The transport can be unreliable and needs no ordering. The cost is that shipping full state can be large. Delta-state CRDTs mitigate this by sending only the recent change.

Operation-based CRDTs (CmRDT)

Replicas broadcast operations (for example, "add element x with tag t") instead of state. Each replica applies every operation it receives. For convergence, concurrent operations must commute. The delivery layer must also deliver every operation to every replica exactly once, and in causal order when operations are not otherwise commutative. Messages are small, but the delivery requirements are stricter than for state-based types.

flowchart LR
    subgraph R1["Replica 1"]
        s1["state S1"]
    end
    subgraph R2["Replica 2"]
        s2["state S2"]
    end
    s1 -- "send S1" --> m2["merge(S2, S1)"]
    s2 -- "send S2" --> m1["merge(S1, S2)"]
    m1 --> c["same converged state"]
    m2 --> c

Common CRDTs

G-Counter (grow-only counter)

Each replica i keeps a vector of counts, one slot per replica. Replica i increments only its own slot i.

• Value: sum of all slots.
• Merge: element-wise maximum.

Taking the maximum is safe because each slot is written by exactly one replica and only grows.

Example with replicas A and B: A increments twice, B increments once, concurrently. A holds {A:2, B:0}, B holds {A:0, B:1}. After merge both hold {A:2, B:1}, value 3.

import java.util.Map;
import java.util.TreeMap;

public class Main {
    static class GCounter {
        private final Map<String, Long> slots = new TreeMap<>();

        GCounter copy() {
            var c = new GCounter();
            c.slots.putAll(slots);
            return c;
        }

        void increment(String replica) {
            slots.merge(replica, 1L, Long::sum);
        }

        long value() {
            return slots.values().stream().mapToLong(Long::longValue).sum();
        }

        void merge(GCounter other) {
            other.slots.forEach((replica, count) -> slots.merge(replica, count, Math::max));
        }

        boolean sameState(GCounter other) {
            return slots.equals(other.slots);
        }
    }

    public static void main(String[] args) {
        var a = new GCounter();
        var b = new GCounter();
        a.increment("A");
        a.increment("A");
        b.increment("B");

        var ab = a.copy();
        ab.merge(b);
        var ba = b.copy();
        ba.merge(a);
        System.out.println("commutative: " + ab.sameState(ba));
        System.out.println("value after merge: " + ab.value());

        ab.merge(b);
        System.out.println("value after repeated merge: " + ab.value());
    }
}

commutative: true
value after merge: 3
value after repeated merge: 3

PN-Counter (increment and decrement)

A G-counter cannot decrease, because element-wise max would resurrect a decremented value. A PN-counter uses two G-counters: P for increments and N for decrements.

• Value: sum(P) - sum(N).
• Merge: merge P and N separately.

A PN-counter can go negative. It cannot enforce a lower bound such as "stock never below zero", because that invariant needs coordination.

LWW-Register (last-writer-wins)

Stores a value with a timestamp. Merge keeps the value with the higher timestamp; ties are broken deterministically, for example by replica ID. For example, replica A writes "x" at timestamp 100 and replica B concurrently writes "y" at timestamp 105. Every replica ends with "y", and "x" is discarded. It converges, but concurrent writes are resolved by timestamp, so one is lost. The timestamps must be comparable across replicas, which brings back the clock issues in time, clocks, and ordering. Cassandra uses per-cell last-write-wins timestamps on this basis.

OR-Set (observed-remove set)

A plain set with add and remove has a conflict: if one replica adds x while another removes x concurrently, the result is ambiguous. The OR-Set resolves this with unique tags.

• add(x): create a fresh unique tag t and store the pair (x, t).
• remove(x): delete all pairs for x that this replica has observed.
• lookup(x): x is present if at least one pair (x, _) exists.
• merge: union of the added pairs, minus pairs known to be removed (tombstones, or a causal context that records which tags were seen).

A concurrent add and remove of x therefore ends with x present: the remove only deletes the tags it observed, and the concurrent add created a new tag. This is called add-wins semantics. A remove-wins variant is also possible.

sequenceDiagram
    participant A as Replica A
    participant B as Replica B
    Note over A,B: both hold {(x, t1)}
    A->>A: remove(x) deletes (x, t1)
    B->>B: add(x) creates (x, t2)
    A-->>B: state {} with removed tag t1
    B-->>A: state {(x, t1), (x, t2)}
    Note over A,B: after merge both hold {(x, t2)}, x is present
    Note over A,B: without the removed-tag record, B could not tell that t1 was removed

Other types

• Flags and multi-value registers: a multi-value register keeps all concurrent values instead of picking one, similar to Dynamo siblings.
• Sequences and text (RGA, Logoot, Yjs, Automerge): each character gets a unique, ordered identifier so concurrent inserts commute. Used for collaborative editing.
• Maps and nested documents: compose the types above per key.

Trade-offs and limits

• Metadata growth. Tombstones, per-replica vectors, and unique tags accumulate. Garbage collection usually requires knowing that all replicas have seen an update, which is a form of coordination.
• Limited invariants. CRDTs guarantee convergence, not application invariants. Uniqueness, non-negative balances, and "at most N" constraints need coordination or escrow schemes.
• Semantic surprises. Merge results can be correct by the type's rules but unexpected to users (for example, add-wins resurrecting an item).
• Weak reads. A replica may serve stale state until it merges. There is no linearizability (see consistency models).

Where CRDTs are used

• Riak data types (counters, sets, maps, flags, registers).
• Redis Enterprise Active-Active databases, which use CRDT-based conflict resolution across regions.
• Collaborative editors and local-first applications using libraries such as Automerge and Yjs.
• Distributed counters and presence or membership sets where merge semantics are simple.

They are less suitable for financial balances or inventory with hard constraints, where a coordinated protocol such as a consensus or transaction system is required.

Interview questions

• Why must state-based CRDT merge be idempotent, commutative, and associative? Replicas can receive states duplicated, reordered, and in any grouping. These three properties make the result independent of delivery order and repetition, so all replicas converge.
• Why does a G-counter merge use max instead of sum? A state message may be delivered more than once, and it includes counts already merged. Summing would double-count. Max is idempotent, and it is correct because each slot has a single writer and only grows.
• How does an OR-Set handle a concurrent add and remove of the same element? Removes delete only the unique tags they observed. The concurrent add carries a new tag, so it survives the merge and the element remains (add-wins).
• Can a CRDT enforce a uniqueness or non-negative constraint? Not without coordination. Concurrent operations that are each valid locally can together violate the invariant, and the CRDT merge only guarantees convergence.