When operating CRDTs at scale in production, what are the concrete costs (metadata growth, tombstone accumulation, causal stability tracking) and in what situations should you avoid choosing a CRDT for a piece of state at all?

## Why the metadata is never safely deletable at write time Every CRDT design — G-Counter's per-node vector, OR-Set's per-add tags and tombstones, PN-Counter's doubled vectors — shares a structural property: none of their internal metadata is ever safely deletable at write time, because deletion is itself a form of coordination the CRDT was built to avoid. A tombstone can only be discarded once every replica that might still hold a stale reference to the tagged add has demonstrably observed the tombstone — otherwise a late-arriving stale replica could resurrect a deleted element, since the OR-Set presence check depends on the tombstone still being there to cancel the corresponding tag. Determining "has every replica observed this" is a form of distributed agreement called **causal stability**, typically tracked via version vectors exchanged periodically among all replicas; it's real coordination work, just deferred from the write path (where CRDTs avoid it) to a background garbage-collection path (where it reappears). In practice this means running CRDTs at scale requires operating a second subsystem — the GC/compaction process — that most teams underestimate when they first adopt CRDTs specifically to escape coordination. ## No free lunch This cost exists precisely because it's the flip side of the coordination-free write guarantee: a system that lets every replica accept writes locally, instantly, without contacting any other replica, cannot simultaneously know in real time which of its own past writes are safe to forget, because "safe to forget" requires knowing what every other replica has (or hasn't) seen — information that, by construction, wasn't exchanged at write time. There is no free lunch here: either you pay coordination cost per write (traditional replicated systems, consensus-based systems), or you defer it to background reconciliation/GC (CRDTs), but a genuinely coordination-free, garbage-free system for arbitrary concurrent state does not exist. ## The operational trade-off The practical trade-off in production is between: - **unbounded metadata growth** (skip GC entirely, and merge time/storage/network bandwidth for the CRDT slowly degrades as tombstones and tags accumulate — fine for low-churn state, a real problem for high-churn state like presence indicators or frequently-retagged items); - **versus running a periodic causal-stability protocol** (bounded metadata, at the cost of building and operating that background subsystem correctly, including handling the case where a replica is permanently gone and its "pending acknowledgment" would otherwise block GC forever — most real implementations need an explicit replica-removal/eviction procedure for this). Systems that ship CRDTs as a first-class primitive (Riak, Akka Distributed Data) bake some form of this GC or pruning into the platform; teams that hand-roll a CRDT on top of a generic datastore often don't, and pay for it later as tombstone bloat degrades performance. ## The most consequential failure mode The most consequential failure mode, though, isn't operational overhead — it's choosing a CRDT for state that carries a **cross-replica invariant**. CRDTs guarantee that merges are well-defined and always succeed, but "always succeeds" is exactly the property that makes them unable to reject an update based on global state: a PN-Counter merge can't refuse to let the value go negative, an OR-Set add can't check "is this username already taken system-wide" before accepting, because checking either would require contacting other replicas at write time — the very coordination CRDTs are designed to avoid. Teams that reach for a PN-Counter for account balance, or an OR-Set for a "claimed usernames" set, discover the invariant violation in production: - two partitioned replicas both let a balance go to -50 because each only saw its own writes; - two users both successfully claim "admin" as their username in different regions during a partition. Reconciling that after the fact (deciding which claim "really" wins, refunding an overdraft) is exactly the manual, application-specific conflict resolution CRDTs were supposed to eliminate — just moved to a worse place, after the invariant has already been visibly violated to users. ## The rule of thumb The rule of thumb: **use a CRDT** when the operation's result is genuinely well-defined independent of what else concurrently happened elsewhere (accumulating a count, unioning a set of tags, converging on a "last write" for a display field) and availability-under-partition matters more than a real-time global constraint. **Don't use a CRDT** whenever the correctness of an update genuinely depends on the current state at every other replica, such as account balances that can't go negative, oversell-sensitive inventory counts, or global uniqueness constraints like usernames or email addresses. Use, instead: 1. **single-writer sharding** (route all writes for a given key to one owning replica/partition); 2. **a consensus protocol** (Raft/Paxos-backed strongly consistent store) for the invariant-bearing field; 3. **a saga/compensating-transaction pattern** (accept the invariant might be briefly violated, detect it, and issue a corrective action afterward). Amazon's original **Dynamo** paper, which inspired much of this line of work including Riak, is explicit about exactly this trade: shopping-cart "add item" is CRDT-friendly (an OR-Set of cart items merges fine, worst case a removed item reappears and gets silently re-removed on checkout), but payment capture is not, and is handled by a strongly consistent path instead.