CRDTs — Conflict-Free Replicated Data Types

Also Known As

TL;DR

Explanation

Traditional distributed databases use consensus protocols (Raft, Paxos) to serialize writes — one node coordinates, others follow. CRDTs take a different approach: they define data structures where any two states can be merged with a mathematically defined merge function that is commutative (A merge B = B merge A), associative ((A merge B) merge C = A merge (B merge C)), and idempotent (A merge A = A). These properties guarantee that any order of merges converges to the same result. Common CRDTs include G-Counter (increment-only counter), PN-Counter (inc/dec counter), LWW-Register (last-write-wins), OR-Set (add/remove set), and RGA (replicated growing array for text collaboration). Collaborative text editors (like Google Docs), shopping carts, and offline-capable mobile apps use CRDTs.

Watch Out

Common Misconception

Why It Matters

Common Mistakes

• Conflating CRDTs with eventual consistency — eventual consistency is a consistency model; CRDTs are a data structure technique. You can have eventual consistency without CRDTs.
• Using LWW-Register (last-write-wins) without understanding its semantics — LWW discards concurrent writes based on timestamps; clock skew between nodes can cause data loss.
• Trying to model everything as a CRDT — financial transactions, inventory counts, and any 'exactly-once' operation cannot be correctly modelled as CRDTs.
• Ignoring tombstone accumulation in OR-Set CRDTs — deleted items leave tombstones that must periodically be garbage-collected, complicating implementation.

Avoid When

• When strong consistency is non-negotiable — financial transactions, inventory decrement, or permission checks require immediate, coordinated agreement across all replicas before acknowledging writes.
• For data with complex, non-commutative business logic — arbitrating conflicting orders, enforcing cardinality constraints, or applying rules that depend on total ordering of events cannot be safely merged without coordination.
• In low-latency, single-datacenter deployments where network partition risk is negligible — the overhead of tracking vector clocks, tombstones, and merge state adds complexity without the availability benefit of geo-replication.
• When tombstone/garbage collection overhead becomes operationally prohibitive — deleted items in OR-Sets and other CRDTs retain metadata indefinitely, causing memory bloat in high-churn datasets without careful pruning strategies.

When To Use

• You need high availability and partition tolerance across geographically distributed nodes where coordination latency is unacceptable — CRDTs eliminate the need for a central coordinator.
• Your application must support offline-first workflows (mobile, PWA) where clients merge changes automatically when reconnecting without manual conflict resolution.
• You're building real-time collaborative features (document editing, shared whiteboards, multiplayer state) where multiple users edit simultaneously and every change must propagate without blocking.
• Eventual consistency is acceptable for your use case and you want to avoid the operational complexity and performance overhead of consensus protocols like Raft or Paxos.

Code Examples

// ❌ Naive counter replication — concurrent increments cause lost updates
// Node A: counter = 5, increments to 6
// Node B: counter = 5, increments to 6 (read old value)
// Merge: last-write-wins → counter = 6 (one increment lost)

// This is not a CRDT — the merge function loses information

<?php
// ✅ G-Counter CRDT — each node tracks its own increments
// Merge = take max of each node's count
class GCounter
{
    private array $counts = []; // nodeId => count

    public function increment(string $nodeId): void
    {
        $this->counts[$nodeId] = ($this->counts[$nodeId] ?? 0) + 1;
    }

    public function value(): int
    {
        return array_sum($this->counts);
    }

    public function merge(GCounter $other): GCounter
    {
        $merged = clone $this;
        foreach ($other->counts as $nodeId => $count) {
            $merged->counts[$nodeId] = max(
                $merged->counts[$nodeId] ?? 0,
                $count
            );
        }
        return $merged;
    }
}
// Node A increments 3 times, Node B increments 2 times
// Merge always yields 5 regardless of order

Tags

Related Terms

References

• https://crdt.tech
• https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type