What a CRDT actually costs you in production

Conflict-free Replicated Data Types are one of those ideas that sound almost too good. Distributed state that merges automatically, without coordination, without locks, without a single point of failure to orchestrate convergence. The papers are elegant. The talks are compelling. The production experience is more complicated.

I want to write about the costs — not to argue against CRDTs, which genuinely solve problems that are hard to solve otherwise, but because the papers don't talk about operations, and the blog posts tend to stop at "here's how a G-Counter works." What happens two years later, when your data volume has grown and your team has turned over and you need to debug something at 2am?

A brief taxonomy

CRDTs come in two broad families. Operation-based CRDTs (CmRDTs) propagate operations between replicas; they require reliable causal delivery but keep per-replica state small. State-based CRDTs (CvRDTs) propagate full state and merge using a join operation on a semilattice; they don't need causal delivery but pay for it in state size.

Most production deployments I've seen use state-based CRDTs — they're simpler to reason about and don't require you to build a causal delivery layer. The cost shows up in memory and in merge computation.

The memory growth problem

Take a basic OR-Set (Observed-Remove Set) — the canonical CRDT for sets that support both add and remove. Each element carries a set of unique tags added when it was inserted, and a tombstone set of tags for removed elements. To resolve an add/remove conflict, you check whether the element's tags are a subset of the tombstones.

In a low-churn dataset this is fine. In a dataset where elements are frequently added and removed — a session store, a shopping cart, a presence list — the tombstone set grows without bound. Tombstones represent every deletion that has ever happened, and you can't safely discard them without coordinating a global garbage collection round.

The tombstone GC problem: You can GC a tombstone only when you're certain every replica has seen the corresponding removal. In an eventually consistent system with no guaranteed delivery time and potentially offline clients, "certain" is hard. In practice, most teams either accept unbounded growth or implement a periodic GC with a coordinator — which reintroduces exactly the coordination they were trying to avoid.

I've seen OR-Sets in production systems reach 40–60× the size of the logical data they represent, entirely due to accumulated tombstones. The fix — periodic compaction with a global consensus round — is not hard to implement, but it requires you to understand the invariants of your specific CRDT deeply enough to know when compaction is safe.

Merge is not free

State-based CRDT merges are typically linear in the size of the state. For small states, this is irrelevant. For large states, it compounds. If you have a G-Map (a map of CRDTs) with thousands of entries, and you're merging state from ten replicas on every write, your merge cost is O(entries × replicas) per write. At scale, this shows up in CPU and in the latency tail.

Delta-state CRDTs address this by propagating only the "delta" — the portion of state that changed since the last sync — rather than full state. This gets you near-operation-based efficiency while keeping the simpler mental model. But it adds implementation complexity: you need to track which deltas have been acknowledged by which replicas, which is essentially implementing a vector clock.

The delta tracking footprint

Vector clocks — or their variants, version vectors and dotted version vectors — solve the "which replica has seen what" problem. They work well. They also add per-entry metadata that grows with the number of replicas, and they require you to periodically compact the clock state as replicas are added, removed, or replaced.

In a static deployment with a known, fixed number of replicas, this is manageable. In a cloud environment where instances come and go, it requires active management. I've seen systems where the vector clock metadata exceeded the size of the actual application state.

Debugging convergence failures

CRDTs are supposed to always converge. In theory, any two replicas that have received the same set of updates will reach the same state. In practice, convergence failures happen — and they're among the hardest bugs to debug because they're not errors. Everything returns 200. The system appears healthy. Two replicas just quietly disagree.

The usual causes:

A merge implementation that doesn't correctly implement the semilattice join (often found in custom CRDTs, rarely in library implementations)
Serialisation/deserialisation round-trips that lose precision or reorder map keys, breaking the merge's assumptions
Clock skew introducing causal inversions in operation-based CRDTs with weak delivery guarantees
Partial state propagation — a replica received a subset of updates and merged them, then propagated before receiving the rest

The diagnostic tooling for this class of bug is poor. You need a way to inspect the raw CRDT state of two diverged replicas, compute the expected merge result, and compare it to what's actually stored. Most applications don't expose this. Building it retroactively, after you've discovered a problem, is not fun.

When CRDTs are the right answer

None of this means CRDTs are the wrong choice. They are genuinely the right choice for a specific class of problems:

Collaborative editing where multiple users may modify the same document simultaneously
Distributed counters and accumulators where only monotonic growth is needed
Presence and availability systems where last-write-wins is acceptable
Offline-first applications where sync must work without a coordination server

If your problem fits these shapes, the CRDT operational cost is worth paying. If you're considering a CRDT because you want to avoid thinking carefully about consistency, you're trading one hard problem for several harder ones.

What I'd do differently

The most useful thing I've learned: instrument the CRDT state aggressively from day one. Track tombstone set sizes, delta accumulation, merge latency at the 95th and 99th percentile, and replica divergence time. These metrics will tell you when you're approaching a compaction threshold before it becomes a crisis.

The second most useful thing: pick a CRDT library rather than rolling your own, and read its source. The subtle invariants in a correct CRDT implementation are non-obvious, and a library that has been used in production by others will have fixed bugs you haven't thought of yet.

The papers describe CRDTs as a free lunch. Production teaches you that the lunch is not free — the bill just arrives later, and it's itemised in ways you didn't expect.

Know the costs before you order.