Consistency Trade offs · CRDTs

Key Question

Where are CRDTs used in real systems today?

Deep Dive

CRDTs aren’t theoretical. They power production systems handling millions of users, often without engineers even knowing they’re using CRDTs.

1. Riak KV — Distributed Database

Riak was one of the first production systems to ship CRDTs. It provides CRDT data types as first-class citizens:

Counters (PN-Counter) — distributed metrics, page views
Sets (OR-Set) — tags, categories, group memberships
Maps — a nested structure where each field is itself a CRDT

Shopping cart example with Riak Map CRDT:

Cart (Map):
  ├── items: OR-Set
  │     ├── ("shirt-L", tag_x1)
  │     └── ("jeans-32", tag_y1)
  ├── quantity: PN-Counter
  │     └── P=[2,0,0], N=[0,0,0]  → value = 2
  └── coupon: LWW-Register
        └── (t=100, "SAVE20")

Two users add items offline. When they sync, the OR-Set merges both sets of items automatically. No conflict resolution needed. The Map CRDT guarantees the entire structure converges.

2. Redis Enterprise — CRDT-Based Replication

Redis Enterprise uses CRDTs for active-active geo-distribution. Two Redis instances in different regions can accept writes independently and merge.

  ┌──────────────┐          ┌──────────────┐
  │ Redis US-East │◄────────►│ Redis EU-West │
  │              │          │              │
  │ INCR likes   │          │ INCR likes   │
  │ SADD tags    │          │ SADD tags    │
  └──────────────┘          └──────────────┘
         │                        │
         └───── SYNC/CRDT ───────┘
                   │
                   ▼
          Both converge to same state

Without CRDTs, geo-distributed Redis would need a master-master setup with conflict resolution. With CRDTs, each Redis instance can accept writes from local users with lower latency and merge transparently.

3. Automerge & Yjs — Collaborative Editing

Automerge and Yjs are JavaScript CRDT libraries that power real-time collaborative editing:

Google Docs offline mode uses a CRDT-like model
Figma uses CRDTs for collaborative design
VS Code Live Share uses CRDTs

User A (offline):    "Hel" ──[type "lo"]──► "Hello" ──[sync]──┐
User B (offline):    "Hel" ──[type "y "]──► "Help"  ──[sync]──┤
                                                                │
                                                ┌───────────────┘
                                                ▼
                                        Both see: "Hello Help"
                                        (both inserts preserved)

The key advantage over OT (Operational Transformation): CRDTs don’t require a central server to order operations. Every replica independently converges. This is why CRDTs dominate in offline-first collaborative editing.

4. SoundCloud — Play Counts

SoundCloud uses CRDT counters for play counts across their distributed infrastructure. Each region maintains its own counter, and counts merge periodically. No lost increments even when network partitions occur.

5. Phoenix LiveView — State Sync

Elixir’s Phoenix LiveView uses CRDTs to synchronize UI state between server and browser. The server maintains a CRDT of the page state. When the network reconnects after a disconnect, the CRDT merges and the UI updates without flickering or losing user input.

Why Not Consensus?

Why use CRDTs instead of Paxos/Raft for replication?

Aspect	CRDT	Consensus (Raft)
Coordination	None	Leader election, quorum
Latency	Local writes	Requires majority ack
Network partition	Both sides continue	Minority partitions stop
Data loss	None (mergeable)	Depends on configuration
Complexity	Moderate	High

The trade-off: CRDTs sacrifice strong consistency (you might read a stale value) for availability (writes always succeed). This is the CAP theorem in action — CRDTs are AP systems.

Check Your Understanding

Why are CRDTs a natural fit for “active-active” geo-distributed databases?
A shopping cart uses an OR-Set CRDT. User A adds “shirt” to cart, goes offline. User B (same account, different device) removes “shirt” and adds “shoes”. They both come online and sync. What is in the cart?
CRDTs don’t need consensus. What property do they give up compared to a system that uses Raft?

The “So What?”

CRDTs have moved from academic papers to production infrastructure. Riak, Redis, and collaborative editing tools are just the tip of the iceberg. As more applications go offline-first and multi-region, CRDTs become the default choice for state synchronization. Every major collaboration tool (Google Docs, Figma, Notion, Miro) relies on CRDT-like convergence. If you’re building any system where multiple users modify shared state, CRDTs should be your first thought — before you reach for consensus.

✏️ Exercises

Exercises: CRDTs

Exercise 1: G-Counter Merge

A G-Counter has 3 replicas. Replica A’s state is [5, 0, 0]. Replica B’s state is [0, 3, 2].

What is the state of each replica after they merge (A with B, B with A)?
What is the final counter value?
Now replica C (state [1, 1, 1]) joins the merge. What is the final result?

Exercise 2: G-Counter Limitations

Explain in one sentence why a G-Counter cannot represent decrements.
Could you build a G-Counter where decrement is allowed by subtracting from the local slot? What goes wrong?
What mathematical property of the merge function would break if you allowed arbitrary subtraction?

Exercise 3: OR-Set Concurrent Operations

Three replicas (A, B, C) start with an empty OR-Set.

Replica A: adds “apple” (tag = a1), adds “banana” (tag = a2)
Replica B: adds “apple” (tag = b1), removes “banana” (removes a2 — B observed A’s add)
Replica C: removes “apple” (removes a1, b1 — C observed both)

After all replicas merge:

Is “apple” in the set? Why or why not?
Is “banana” in the set? Why or why not?
How many unique tags are in the final set?

Exercise 4: CRDT vs Consensus

An e-commerce platform uses an inventory CRDT (PN-Counter) to track stock across regions. The current count for item X is 5.

Two regions both sell one unit simultaneously (decrement by 1 each). What does the counter show after merge?
The actual physical inventory is 5 units. After the decrements above, you sell 3 more units in region A and 2 more in region B. A customer checks the count and sees 3. They buy 3 — but the warehouse only has 2 left. How could this over-selling happen?
Would Raft prevent this problem? What trade-off does it introduce?

👁️ View Solutions

Solutions: CRDTs

Exercise 1: G-Counter Merge

After A merges with B:
- A receives [0, 3, 2] from B → elementwise max of [5, 0, 0] and [0, 3, 2] = [5, 3, 2]
- B receives [5, 0, 0] from A → elementwise max of [0, 3, 2] and [5, 0, 0] = [5, 3, 2]
- Both converge to [5, 3, 2]
Final counter value: 5 + 3 + 2 = 10
C joins: max of [5, 3, 2] and [1, 1, 1]:
- max(5, 1) = 5
- max(3, 1) = 3
- max(2, 1) = 2
- Result: [5, 3, 2] — C’s values were all lower, so they don’t change the outcome.

Exercise 2: G-Counter Limitations

A G-Counter’s merge function is elementwise max — taking the maximum of two values can never produce a smaller number, so you can never reduce any slot.
If you subtract from your local slot, the elementwise max during merge would take the larger previous value from another replica. Your decrement would be silently lost. For example: A has [5, 0, 0], A decrements to [4, 0, 0], then merges with B’s [5, 0, 0] (which hadn’t seen the decrement). Result: [5, 0, 0] — the decrement disappeared.
Elementwise max is not invertible. If you allow subtraction, the merge function would need to decrease a value, which max cannot do. The lattice property (join = least upper bound) only works with monotonic increases.

Exercise 3: OR-Set Concurrent Operations

Is “apple” in the set? Yes. C removed tags a1 and b1. But A had already added “apple” with a1, and B had added with b1. Both are removed by C’s operation. However… wait, let’s trace carefully:
- A adds “apple” with tag a1. A adds “banana” with tag a2.
- B adds “apple” with tag b1. B removes “banana” — removes tag a2.
- C removes “apple” — removes tags a1 and b1 (that C observed).
After merge: A has {(“apple”, a1), (“banana”, a2)} ∪ {(“apple”, b1)} — but a1 and b1 were removed by C. However, the merge is a union of internal sets. C’s state has { } (it removed everything it knew about). A has {(“apple”, a1), (“banana”, a2), (“apple”, b1)} only if B’s adds propagated. But B also sent its adds.

Actually, OR-Set merge is set union of (element, tag) pairs. C’s remove of tags a1 and b1 means those tags are excluded from C’s internal set. But when A merges with C, A still has a1 and b1 (A received b1 from B). So the union brings them back. Wait — that breaks the semantics.

Correction: In an OR-Set, when you remove, you add the removed tags to a “tombstone” set (or equivalently, the internal set is {(elem, tag)} and remove means “remove all observed (elem, tag) pairs”). But the merge is union — if another replica still has those tags, they come back.

This is why real OR-Sets use “observed-remove” with version vectors or tombstones. The answer depends on implementation. For the standard OR-Set:

After all merges (union of all (e,t) pairs minus removed pairs):
- Banana’s a2 tag is removed by B, and only A had it. Gone.
- Apple’s a1 is removed by C, but B has b1 (different tag) — wait, a1 is explicitly removed, but a1 was from A. B had b1, not a1.
Let me retrace properly: after full sync:
- All tags: a1 (“apple”), a2 (“banana”), b1 (“apple”)
- Removed tags: a2 (by B), a1 and b1 (by C)
- Surviving tags: none — all three tags are in the remove set.
Final set: empty {}.

This is actually a problem with basic OR-Sets — concurrent adds and removes can delete everything. This is why production OR-Sets often use version vectors or “add wins” semantics more carefully.
Is “banana” in the set? No — tag a2 was removed by B, and no other replica added “banana”. a2 is in the tombstone set.
Unique tags surviving: 0 (everything was removed).

Key insight: This exercise shows a weakness of basic OR-Sets — if a remove operation observes all tags and removes them, the element disappears. Production OR-Sets add version vectors to track causality so that concurrent adds survive.

Exercise 4: CRDT vs Consensus

After both regions decrement: Both decrements are recorded. Region A’s N-counter has [1, 0], Region B’s has [0, 1]. After merge: P = [0, 0], N = [1, 1]. Value = 0 - (1 + 1) = -2. Wait — the initial value was 5, so P should track the initial value. Let me reconsider.

Initial state (both regions): P = [5, 5], N = [0, 0] (each region’s P-counter has “5” for the initial stock). If each sells 1: region A decrements → N_A = [1, 0], region B → N_B = [0, 1].

After merge: P = [5, 5], N = [1, 1]. Value = (5+5) - (1+1) = 10 - 2 = 8. That’s wrong — we only had 5 units initially. This reveals a problem: each region independently initialized P to 5. The initialization is not coordinated.

The real answer: A PN-Counter for inventory must be initialized on one replica and propagated. If both regions independently set P to 5, the merge results in P = max(5,5) = 5 per slot, sum(P) = 10 — double counting. This is why initial state needs coordination.

But ignoring the initialization issue: after both decrements, the counter shows 3 (5 - 1 - 1 = 3).
Over-selling: The counter shows 3 (a stale or concurrent read), but in reality, by the time that customer checks, 5 more units have been sold across both regions (3 + 2). The counter eventually converges to show -2, but during the sync delay, the customer saw 3 and bought 3. The system sold 10 units of a 5-unit inventory.
Would Raft prevent this? Yes — Raft provides strong consistency. All writes go through a leader, so inventory is always accurate. Trade-off: Writes are slower (require majority ack), and if the leader is in a different region, every write incurs cross-region latency. During a network partition, the minority partition cannot sell anything. CRDTs sacrifice accuracy (stale reads) for availability (local writes always succeed).