The problem: two replicas, two writes, no coordinator to pick a winner#
TL;DRthe 30-second version
- The same value lives on several replicas, and each can take writes even while it's cut off from the others. When they reconnect, each has updates the others never saw.
- The naive fix is last-writer-wins: stamp each write with a timestamp and, on merge, keep the one with the later stamp. But that throws away the other write completely — a lost update — and it leans on clocks that drift.
- A CRDT avoids the loss by changing the data type, not the timestamp. Each replica keeps a little extra bookkeeping so that concurrent updates combine instead of overwrite.
- A grow-only counter gives every replica its own slot that it alone increments. The value is the sum of the slots. Merging keeps the larger count in each slot, so an increment can never be clobbered.
- The merge is commutative, associative, and idempotent — reorder the merges, repeat them, it doesn't matter. That's what makes every replica converge to the same state with no coordination. This guarantee is called strong eventual consistency.
Picture a page-view counter for one article, served from three data centers so it stays fast worldwide. Each data center keeps its own copy of the count and bumps it as readers arrive. Most of the time the copies gossip their updates to each other and stay close. Then a network link drops, and for thirty seconds the data centers can't reach one another. During those thirty seconds, one copy counts three new views and another counts five. Now the link comes back. One copy says 3, another says 5, and you need the real answer, which is 8.
Here's the naive approach, and it's the one most people reach for first: store the count as a single number, and when two copies disagree, keep the one with the later timestamp. Play it out. The copy that reached 5 has a later write than the copy that reached 3, so last-writer-wins keeps 5 and discards 3. The count is now 5. But the true total was 8. You didn't merge the two updates — you kept one and silently deleted the other. Three page views vanished, and nothing in the system will ever tell you they're gone.
The forced first step: give every replica its own slot#
The loss happened because both replicas wrote to the same single number, so on merge one write had to win and the other had to lose. So stop sharing the number. Instead of one count, keep one count per replica, and make the rule that a replica only ever increments its own slot. Replica one writes only to slot one, replica two writes only to slot two, and so on. No two replicas ever write the same slot, so no write can overwrite another.
The value you report is the sum of all the slots. During the partition, replica one bumps its own slot to 3 and replica two bumps its own slot to 5. Their slot arrays are now different, but nothing has been lost, because the two increments landed in different places. The only question left is how to combine the two arrays when the replicas reconnect.
Here is the key choice. To merge two arrays, go slot by slot and keep the larger of the two counts. Why the larger, and not the sum? Because a replica might send you its state more than once — gossip repeats, messages get redelivered — and if merging added the counts, receiving the same state twice would double it. Keeping the larger count is safe to repeat: merging the same thing again changes nothing. A slot only ever holds the highest count that slot has reached, so an increment is remembered the moment it lands and can never be undone by a merge.
| Slot | Replica 1 has | Replica 2 has | Keep the larger | Running sum |
|---|---|---|---|---|
| slot 1 | 3 | 0 | 3 | 3 |
| slot 2 | 0 | 5 | 5 | 8 |
After the merge, both replicas hold the same array, and the sum of that array is 8 — the true total, with no view lost. This is a grow-only counter, usually written G-counter. Each replica owns a slot it alone raises, the value is the sum of the slots, and merge keeps the larger count in each slot. That last rule is doing all the work, so it's worth naming what makes it safe.
Why the merge order never matters#
Keeping the larger count in each slot has three properties, and together they are exactly what let replicas converge without a coordinator. Take them one at a time.
- It is commutative: merging replica one into replica two gives the same result as merging replica two into replica one. The larger of two numbers doesn't care which one you name first.
- It is associative: with three replicas, it doesn't matter whether you merge one and two first and then bring in three, or merge two and three first and then bring in one. You reach the same array either way.
- It is idempotent: merging the same state in twice is the same as merging it in once. The larger of a number and itself is just the number.
Put those together and the consequence is strong. No matter what order the replicas exchange state in, no matter how many times a given state gets redelivered, and no matter which replica starts the merge, they all end up holding the identical array. You don't need the replicas to agree on an order first. You don't need a leader to serialize the writes. You just let them swap states whenever they can, and the math guarantees they land in the same place. That guarantee has a name: strong eventual consistency. Once two replicas have seen the same set of updates, they hold the same state, full stop.
Counting down, and sets you can add to and remove from#
A grow-only counter only goes up. What if you need to count down too — likes and unlikes, items added to and taken out of a cart? You can't just let a replica lower its own slot, because merge keeps the larger count, so a decrement would be ignored the next time any higher value merged in. The fix is to keep two grow-only counters instead of one: a plus counter for increments and a minus counter for decrements. To go down, a replica bumps its own slot in the minus counter. The value you report is the sum of the plus counter minus the sum of the minus counter. This is a PN-counter, and it inherits the grow-only counter's convergence for free, because it is just two of them merged side by side.
Sets are harder, because you can add an item and later remove it. Start with the easy half. A grow-only set only ever gains items, so merging two of them is just the union — throw all the items into one bag. That converges for the same reason the counter did: union is commutative, associative, and idempotent. The trouble starts when you allow removal. If you simply delete an item on remove, a concurrent add on another replica will bring it back after the merge, and now add and remove fight every time they meet.
The naive patch is a tombstone: instead of deleting the item, mark it as removed and remember that mark. But a single tombstone per item is too blunt. Once an item is tombstoned you can never cleanly add it again, because the tombstone keeps shooting it down. The real fix is to make every single add distinct. When a replica adds an item, it attaches a globally unique tag to that add — the replica's name plus a counter, so no two adds ever share a tag. An item is present as long as it holds at least one tag that hasn't been tombstoned. A remove tombstones only the tags it can currently see. Merge unions the tags and unions the tombstones.
Now walk the conflict that broke the naive set. Replica one removes an item, tombstoning the one tag it can see. At the same time, replica two adds that item back, creating a brand-new tag that replica one's remove never saw. When the two states merge, the item has one dead tag and one live tag, so it stays present. The concurrent add wins over the concurrent remove, because the add's fresh tag was never in the remove's sights. This is an observed-remove set, or OR-set, and add-wins is its defining behavior. A naive set would have lost that re-add; the OR-set keeps it.
There's one more member of the family worth naming, because it's the simplest and the most misused. A last-writer-wins register just stores a value and a timestamp, and on merge keeps the value with the later timestamp. It is a perfectly valid CRDT — its merge is commutative, associative, and idempotent — but it converges by design to keep exactly one of two concurrent writes and drop the other. That's fine when losing one is acceptable, like a user's display name, and wrong when it isn't, like a shopping cart. The counter and the OR-set exist precisely so you don't have to accept that loss.
Now name it: state-based and op-based CRDTs#
What you've built is a conflict-free replicated data type, a CRDT. The definition is simple: a data type designed so that replicas can be updated independently and then merged back together with no coordination, always converging to the same state. Everything hangs on the merge being commutative, associative, and idempotent. Mathematically, the states form a structure called a join-semilattice, and the merge is its join — the least upper bound of the two states. You don't need that vocabulary to use one, but it's the reason the guarantees hold.
There are two ways to ship the same idea, and they're equivalent in power. The first is what we've built: each replica holds a full state, and to sync, a replica sends its whole state to another, which merges it in. This is a state-based CRDT, sometimes called a convergent replicated data type. The second sends operations instead of states. When a replica does an update, it broadcasts the operation itself — increment, or add this tag — and every replica applies it. This is an op-based CRDT, or commutative replicated data type. It moves less data, but it demands more of the network: every operation must be delivered to every replica exactly once, in causal order, or the replicas diverge. State-based CRDTs are more forgiving, which is why gossip-style systems favor them — a lost or repeated message just heals on the next merge.
What it costs: metadata that grows with replicas and with history#
CRDTs don't get their guarantees for free — they pay in metadata. A grow-only counter carries one slot per replica, so its size grows with the number of replicas. A PN-counter carries two of those. An OR-set is worse in a subtler way: it carries a tag for every add, and a tombstone for every remove, so its bookkeeping grows with the history of operations, not just with the number of replicas. A set that has seen a million adds and removes drags a million-ish tags and tombstones behind it, even if it currently holds three items.
PredictA page-view counter runs as a G-counter across 100 data centers, and each slot takes 8 bytes. How big is one counter's state? And if you switched to a naive single 8-byte integer with last-writer-wins, what would you save — and what would it cost you?
Hint: One slot per replica for the CRDT; one integer total for the naive version.
The G-counter holds 100 slots at 8 bytes each, so about 800 bytes per counter, versus 8 bytes for a single integer — roughly 100 times larger. What the naive integer buys you in size, it loses in correctness: under last-writer-wins, every concurrent increment except one is silently dropped, so a busy counter under partitions would steadily undercount. The 800 bytes is the price of never losing a view. This is the core trade — CRDTs spend space and metadata to buy coordination-free correctness, which is why real systems cap replica counts, prune slots for retired replicas, and garbage-collect tombstones once every replica has seen the remove.
- A grow-only counter and a PN-counter cost on the order of the number of replicas — a fixed per-counter overhead once the cluster size is set.
- An OR-set costs on the order of its operation history, because each add leaves a tag and each remove leaves a tombstone. Tombstone garbage collection — dropping tombstones once every replica has definitely seen the remove — is the standard defense, and it needs the replicas to agree on what everyone has seen.
- Merging two states is one pass over their entries, so a single merge is cheap; the cost that bites is storing and shipping the metadata, everywhere, all the time.
- Delta-state CRDTs are the common optimization: instead of shipping the whole state on every sync, a replica ships only the small piece that changed since last time, which keeps convergence but cuts the bandwidth sharply.
Common misconceptions & gotchas
Do CRDTs give me strong consistency?
No. They give strong eventual consistency: replicas converge to the same state once they've seen the same updates, but at any moment before that they can hold different, stale values. If you need every reader to see the single latest value immediately, or you need a global invariant like a balance that must never go negative, you want consensus (Raft or Paxos), not a CRDT.
Isn't a CRDT just picking a winner, like last-writer-wins?
A last-writer-wins register is one CRDT, and it does pick a winner — that's its whole design, and it loses the other write. The counters and sets are different: they merge concurrent updates so nothing is lost. The point of the family is that you choose the type whose merge matches what 'correct' means for your data, instead of being stuck with lossy overwrite.
Why tag every add in a set instead of just remembering the item?
Because without unique tags, a concurrent add and remove of the same item can't be told apart from a repeated one, so add-wins semantics become impossible and re-adding a removed item breaks. The tag is what lets a fresh add survive a concurrent remove: the remove can only tombstone tags it has already seen, never the new one.
Can a CRDT enforce a rule like 'this username is unique' or 'stock can't go below zero'?
No, and this is the sharpest limit. CRDTs guarantee convergence, not global invariants. Two replicas can each independently reserve the last unit of stock, and both merges will happily keep both reservations — the state converges, but the invariant is violated. Anything that needs a global 'only one of these can happen' still needs coordination.
QuizTwo replicas start from an empty OR-set. Replica 1 adds "milk" and removes it. Concurrently, replica 2 adds "milk" with its own fresh tag. After they merge, is "milk" in the set?
- No — the remove wins because it came from replica 1
- Yes — replica 2's add carries a tag the remove never tombstoned
- It depends on which replica has the later timestamp
- No — one add and one remove cancel out
Show answer
Yes — replica 2's add carries a tag the remove never tombstoned — Replica 1's remove only tombstones the tag replica 1 could see — its own add's tag. Replica 2's concurrent add created a different, unique tag that the remove never touched. After the merge the item holds one dead tag and one live tag, and an item is present as long as it has any live tag. So "milk" is in the set: the OR-set is add-wins.
When to reach for a CRDT, and when not to
A CRDT is the right tool when you want every replica to accept writes locally and stay available during a partition, and you can express 'correct' as a merge that never needs a coordinator. It is the wrong tool when correctness depends on a global rule that all replicas must respect at once. Choose the weakest mechanism that actually meets your consistency need.
- Reach for a CRDT when availability and low latency matter more than reading the very latest value, and concurrent updates should merge rather than block — counters, carts, presence, collaborative documents.
- Reach for last-writer-wins specifically when losing one of two concurrent writes is genuinely acceptable and you want the smallest possible metadata — a display name, a last-seen timestamp.
- Reach for consensus (Raft or Paxos) when you need a single agreed order, a linearizable latest value, or a global invariant like uniqueness or a non-negative balance. That costs a round trip and blocks during partitions, which is exactly what a CRDT refuses to do.
- Between the two CRDT flavors: state-based over lossy or gossip networks where messages repeat and reorder; op-based when you can guarantee exactly-once causal delivery and want to ship less data.
CRDT vs last-writer-wins vs consensus
| CRDT (counter / OR-set) | Last-writer-wins register | Consensus (Raft / Paxos) | |
|---|---|---|---|
| Coordination on write | None — write locally | None — write locally | Round trip to a quorum |
| Available during a partition | Yes | Yes | No (minority side blocks) |
| Concurrent writes | Merged, none lost | One kept, one dropped | Serialized into one order |
| Consistency | Strong eventual | Strong eventual (lossy) | Linearizable |
| Enforces global invariants | No | No | Yes |
| Metadata cost | Grows with replicas / history | Tiny (value + timestamp) | Log + quorum state |
Where CRDTs run in the wild
- Riak KV exposes CRDTs as first-class database types — counters, sets, maps, registers, and flags — built directly on the Shapiro and Baquero work, and uses delta-state internally to keep the shipped metadata small. It was one of the first production systems to adopt CRDTs.
- Redis Enterprise runs Active-Active (multi-master) geo-replication on CRDTs, so every region takes local writes on counters, sets, and hashes and they converge across regions without a coordinator.
- Automerge and Yjs are CRDT libraries for local-first and collaborative apps: two people edit the same document offline, and their changes merge without a central server picking a winner. Yjs's text CRDT backs many collaborative editors.
- SoundCloud's Roshi is a large-scale LWW-element-set built on top of Redis for its activity timelines, and multi-region databases such as Azure Cosmos DB offer last-writer-wins conflict resolution for the same reason — it's the cheapest CRDT when losing a concurrent write is acceptable.
PredictAn OR-set backs a collaborative to-do list that's been edited for a year. It currently holds 20 items, but its stored state is megabytes. What is all that weight, and what has to be true before you can shed it?
Hint: Think about what a remove leaves behind, and who has to have seen it.
The weight is tombstones — a marker left by every one of the thousands of removes over the year, each one kept so a concurrent add can't accidentally resurrect a deleted item. You can only safely garbage-collect a tombstone once you're sure every replica has already seen the corresponding remove, because dropping it earlier could let a straggler's old add bring the item back. That's why tombstone garbage collection needs a notion of what all replicas have observed — often exactly the causal bookkeeping from vector clocks — and why long-lived OR-sets are the classic place CRDT metadata gets painful.
In an interview
Lead with the problem, not the definition. Say: two replicas take writes during a partition, and when they reconnect you have concurrent updates and no coordinator to order them. Last-writer-wins resolves it by keeping one write and dropping the other, which is a lost update. Then introduce the fix as a change of data type: give each replica its own counter slot it alone increments, report the sum, and merge by keeping the larger count in each slot. Point out why the larger and not the sum — idempotency, so redelivered gossip doesn't double-count — because that detail signals you actually understand the mechanism.
From there, name the property that generalizes it: the merge is commutative, associative, and idempotent, so replicas converge in any order with no coordination — strong eventual consistency. Extend to a PN-counter (two grow-only counters) and an OR-set (tag every add, tombstone observed tags, add-wins), and mention the two flavors, state-based versus op-based, with the trade that op-based needs exactly-once causal delivery. Close on the honest limit, which is the question interviewers actually probe: CRDTs guarantee convergence but not global invariants, so they can't enforce uniqueness or a non-negative balance — for that you still need consensus. Land it in a real system: Riak's data types, Redis Active-Active, or Automerge and Yjs for collaborative editing.
References & further reading
- Shapiro, Preguiça, Baquero, Zawirski — A Comprehensive Study of Convergent and Commutative Replicated Data Types (INRIA RR-7506, 2011) — the foundational technical report: state-based vs op-based, the semilattice conditions, and the full catalog of types
- Shapiro, Preguiça, Baquero, Zawirski — Conflict-free Replicated Data Types (SSS 2011) — the shorter conference paper that coined the CRDT name and strong eventual consistency
- crdt.tech — CRDT resources, maintained by the original authors — a curated hub of papers, talks, and implementations for every type in the family
- Riak KV — Data Types (documentation) — how counters, sets, maps, registers, and flags are exposed as first-class database types
- Kleppmann — Designing Data-Intensive Applications, Ch. 5 (Handling Write Conflicts) — conflict resolution, last-writer-wins, and convergence in replicated stores
- Almeida, Shoker, Baquero — Delta State Replicated Data Types (2016) — shipping only the changed delta instead of full state — the standard bandwidth optimization
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.