vault

CRDTs Basics

22 min read

CRDTs Basics

Conflict-free Replicated Data Types (CRDTs) are abstract data types — counters, sets, maps, sequences, even nested JSON documents — designed so that concurrent updates on different replicas can be merged automatically with mathematically guaranteed eventual consistency and no coordination between replicas. The core trick is to push all the conflict-resolution work into the algebra of the data type itself: design the operations so that every possible merge is correct, regardless of order or repetition. Two formalizations exist. State-based CRDTs (CvRDTs, Convergent RDTs) ship the full state between replicas; the merge function ⊔ must form a join-semilattice — commutative, associative, idempotent — and updates must be monotone with respect to that lattice’s partial order. Operation-based CRDTs (CmRDTs, Commutative RDTs) broadcast individual operations; operations must commute pairwise (when concurrent), and the delivery layer must guarantee causal broadcast and exactly-once delivery. Both are anti-CAP: they explicitly choose Availability and Partition tolerance and recover from concurrency through algebraic structure, not through locking, voting, or coordination. CRDTs power Riak’s data types, Redis Enterprise’s geo-distributed CRDBs, Automerge (offline-first JS/Rust apps), Yjs (the de-facto CRDT engine behind TipTap, ProseMirror, Slate, Monaco, and many collaborative-editor products — though notably not Notion, which uses a server-arbitrated LWW scheme), the CRDT-inspired (not pure-CRDT, not OT) hybrid behind Figma’s multiplayer, and large parts of Apple’s iCloud sync infrastructure. The 2011 Shapiro et al. paper is the canonical reference; a comprehensive zoo of CRDT designs (G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Element-Set, RGA, JSON-CRDT, …) has been catalogued since.

1. Intuition — Two Editors Editing the Same Document Offline

Two editors, Alice and Bob, both have a copy of a shopping list. They board separate flights with no internet. Alice adds “milk.” Bob adds “eggs” and removes “bread.” When the planes land, their phones reconnect and need to merge.

A naïve approach uses last-writer-wins: each operation has a wall-clock timestamp; the merge picks the operation with the larger timestamp. This loses Alice’s add if Bob’s clock was ahead. A quorum-based approach (like Raft or Two-Phase Commit) requires a network round-trip per operation — impossible offline.

CRDTs give a third answer: structure the data so that merging is always correct. For a shopping list, we represent it as a “set of additions” minus a “set of removals,” each operation tagged with a unique identifier. Adding “milk” means inserting (milk, alice-tag) into the additions set. Removing “bread” means inserting the tag of the original “bread” addition into the removals set. To compute the visible set: take the additions set, subtract any whose tag is in the removals set.

Now merging two replicas is just union the additions sets, union the removals sets. Union is commutative (order doesn’t matter), associative (groupings don’t matter), idempotent (merging the same thing twice is harmless). Whatever order Alice and Bob’s phones reconnect in, whatever subset of updates each side has seen, the result converges. This is the OR-Set (Observed-Remove Set), one of the foundational CRDTs.

The depth of the trick: there’s no central authority, no clock synchronization, no rollback, no operator intervention. The algebra of the data type guarantees correctness. That’s what “conflict-free” means — the system never has a conflict to resolve, because the merge operation handles every possible combination by construction.

The cost: data types must be carefully designed; “natural” ones (a counter, a set, a register) admit straightforward CRDTs, but more complex ones (a JSON tree, a rich-text document with formatting and cursor positions) require considerable engineering. Some operations cannot be expressed CRDT-style without coordination — the canonical example is reserving a unique seat at a concert (Shapiro et al. point out this requires a quorum no matter what).

2. The Two Flavors

2.1 State-Based (CvRDTs — Convergent Replicated Data Types)

Each replica holds a state s. Updates apply locally: s' = update(s, op). To synchronize, replicas exchange full states; the receiver merges with s_new = s_local ⊔ s_received. Eventual consistency requires three algebraic properties of the merge:

Commutative:  a ⊔ b = b ⊔ a
Associative:  (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c)
Idempotent:   a ⊔ a = a

A binary operation with these three properties is exactly a join-semilattice in lattice theory. The associated partial order is a ≤ b ⟺ a ⊔ b = b — read “a is less than or equal to b in the lattice.”

For CRDT correctness, updates must also be monotone: an update never makes the state “smaller” in the lattice sense. Formally, update(s, op) ≥ s. This guarantees that as updates accumulate, the state moves up the lattice; merge takes the least upper bound of two states, never going backward.

The proof of eventual consistency is by induction over the lattice: if every replica eventually exchanges with every other, and merge is the join, then all replicas converge to the same supremum of all updates ever performed. Section 3 of Shapiro et al. 2011 gives the full proof.

2.2 Operation-Based (CmRDTs — Commutative Replicated Data Types)

Each replica holds a state. An update is decomposed into a prepare (purely local — generates an operation message) and an effect (applied at every replica). Operations are broadcast over a causally-ordered, exactly-once delivery channel.

For correctness, concurrent operations must commute: if op_1 and op_2 are not in a causal relationship, then op_2(op_1(s)) = op_1(op_2(s)). Operations that are in a causal relationship are applied in causal order, so commuting them is unnecessary.

Operation-based CRDTs typically have smaller messages (just the operation, not the full state) but stronger delivery requirements (the network layer must guarantee causal broadcast and no duplication). State-based ones have larger messages but tolerate any out-of-order, duplicate, or lossy delivery.

In practice, modern CRDT systems often use delta-state CRDTs (Almeida, Shoker & Baquero 2018), which ship a delta — a small, monotone increment of the state — that has the algebraic properties of a state-based CRDT but the message-size economy of an op-based one.

2.3 The Equivalence

Shapiro et al. 2011 (Theorem 5.2) prove that under reasonable assumptions, the two flavors are equivalent in expressive power — anything achievable as a CvRDT has a CmRDT counterpart and vice versa. The choice is engineering: state vs op overhead, delivery requirements, sync frequency.

3. The Math — Join-Semilattices and Why CAI is Enough

Let’s walk through the lattice formalism for state-based CRDTs.

A partially ordered set (poset) (S, ≤) has elements with a relation ≤ that is reflexive, antisymmetric, and transitive but allows incomparable pairs. A join-semilattice is a poset where every pair of elements has a unique least upper bound (called the join, denoted ⊔).

Examples:

  • The natural numbers ordered by ≤ with ⊔ = max: a totally ordered chain. Join is just the maximum.
  • The power set 𝒫(U) of some universe U, ordered by ⊆, with ⊔ = ∪: every pair of subsets has a least upper bound (their union).
  • The Cartesian product of two semilattices, ordered componentwise: also a semilattice.

For a CRDT, the state space S is structured as such a semilattice; the merge operation is the join ⊔. The CAI properties are not arbitrary requirements — they fall out of the lattice axioms:

  • a ⊔ b = b ⊔ a because lub({a, b}) doesn’t depend on the order of the pair.
  • (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c) because both equal lub({a, b, c}).
  • a ⊔ a = a because a itself is the least upper bound of {a, a}.

The non-trivial requirement is monotonicity of update: update(s, op) ⊔ s = update(s, op), equivalently s ≤ update(s, op) in the lattice order. This is what lets the system progress: every operation moves us up the lattice, and merges aggregate progress across replicas.

The eventual-consistency proof (paraphrased from Shapiro et al.):

Suppose replica r_i has applied updates U_i ⊆ U (the set of all updates).
Its state is s_i = (the lattice supremum of U_i applied to the initial state).

If for every pair (i, j), eventually r_i merges with r_j (gossip),
then over time U_i grows, and eventually U_i = U for all i.

Therefore eventually s_i = supremum(U) for all i — all replicas converge.

The proof needs no clocks, no leader, no consensus. It needs only the algebraic structure and the assumption that eventually every update propagates everywhere.

4. The CRDT Zoo — Core Examples

4.1 G-Counter (Grow-Only Counter)

Use case: a click counter that only increases.

State: a vector c[1..N] indexed by replica id, where c[i] is the number of increments at replica i.

init:        c = [0, 0, ..., 0]
increment_at_i:  c[i] += 1                    # only the local counter
value:       sum(c)
merge(c1, c2): for i: c[i] = max(c1[i], c2[i])

Join: element-wise maximum. The semilattice is (ℕ^N, ≤_componentwise). Each replica’s c[i] only increases (max is monotone), so the lattice progress invariant holds.

Why we need the vector and not a single integer: with a scalar counter, two replicas independently incrementing 5 → 6 and 5 → 6 would merge as max(6, 6) = 6 — losing one increment. The per-replica decomposition stores the increment-count locally and merges via max, so concurrent increments at different replicas accumulate.

4.2 PN-Counter (Positive-Negative Counter)

G-Counter only grows. PN-Counter supports decrements via two G-Counters: P for increments, N for decrements. Value = sum(P) - sum(N).

init:               P = [0]*N, N = [0]*N
increment_at_i:     P[i] += 1
decrement_at_i:     N[i] += 1
value:              sum(P) - sum(N)
merge:              P[i] = max(P[i], P'[i]); N[i] = max(N[i], N'[i])

Used in Riak as Riak Counter.

4.3 G-Set (Grow-Only Set)

State: a set; only adds allowed. Merge is union.

4.4 2P-Set (Two-Phase Set)

State: two G-Sets, A (added) and R (removed). Element is in the set if in A and not in R. Once removed, can never be re-added (the second phase is permanent removal). Merge is component-wise union.

This is “simple but limited” — re-adding a previously-removed element is forbidden.

4.5 OR-Set (Observed-Remove Set)

The most useful set CRDT. Each add tags the element with a unique identifier (e.g., {element, replica_id, monotonic_counter}). Each remove records the observed tag set for that element. An element is in the set if there exist tags in A for it that are not in R.

state:     A: dict[Element, set[Tag]]    R: dict[Element, set[Tag]]
add(x):    new_tag = (replica_id, fresh_counter())
           A[x].add(new_tag)
remove(x): R[x] |= A[x]                 # remove all observed tags
value:     {x : A[x] - R[x] != ∅}
merge(s1, s2): for x: A[x] = A1[x] ∪ A2[x]; R[x] = R1[x] ∪ R2[x]

Add-after-remove of the same element is fine: the new add gets a fresh tag not in R. Concurrent add and remove: the add’s tag is not in R (because R only contains observed tags), so the element survives. This is the “add wins” semantic. Riak uses OR-Set for Riak Set.

4.6 LWW-Element-Set (Last-Write-Wins)

Each element has a timestamp on add and remove. Element is in the set if its add-timestamp > remove-timestamp. Conflict-resolution is by timestamp comparison (with a tie-breaker by replica id). Simple but loses concurrent updates if clocks are skewed; not as semantically clean as OR-Set.

4.7 LWW-Register

A single value with a timestamp. Merge picks the value with the larger timestamp (replica id breaks ties). Used for atomic-feeling registers under EC. Simple but lossy — concurrent updates from different replicas resolve to one value, the other is silently dropped.

4.8 MV-Register (Multi-Value Register)

When concurrent writes happen, both values are kept; the application chooses on read. Reads return a set of values. This is what Dynamo uses (with Vector Clocks as the version tag) — the conflict is exposed to the application, which is honest about ambiguity.

4.9 RGA (Replicated Growable Array) and Sequences

Sequence CRDTs (text editors, ordered lists) are dramatically harder than sets. The operations are “insert at position p” and “delete at position p,” and positions must be stable under concurrent edits. Approaches:

  • WOOT (Without Operational Transform, Oster et al. 2006) — each character has a unique id and a (left-id, right-id) pair indicating its neighbors at insert time.
  • Treedoc (Preguiça et al. 2009) — tree-structured positions.
  • RGA (Replicated Growable Array, Roh et al. 2011) — total ordering of operation timestamps gives stable positions.
  • Logoot, LSEQ — assign rational-number-like positions between existing items.
  • YATA (“Yet Another Transformation Approach,” Nicolaescu, Jahns, Derntl & Klamma 2016) — the algorithm underneath Yjs. YATA uses a doubly-linked list of items, each tagged with a Lamport-timestamp-style unique ID, and a deterministic insertion rule combining ideas from RGA and WOOT while heavily optimizing the sequential-typing case (researchgate.net/publication/310212186).

These are the heart of collaborative-editing systems. The Kleppmann & Beresford 2017 paper presents a JSON-tree CRDT that nests RGAs.

5. Pseudocode (G-Counter, OR-Set)

G-Counter

class GCounter:
    state: dict[ReplicaId, int]    # default 0

    def increment(self, replica: ReplicaId):
        self.state[replica] = self.state.get(replica, 0) + 1

    def value(self) -> int:
        return sum(self.state.values())

    def merge(self, other: GCounter) -> GCounter:
        merged = GCounter()
        for r in set(self.state) | set(other.state):
            merged.state[r] = max(self.state.get(r, 0), other.state.get(r, 0))
        return merged

    # Lattice partial order
    def __le__(self, other: GCounter) -> bool:
        return all(self.state.get(r, 0) <= other.state.get(r, 0)
                   for r in set(self.state) | set(other.state))

OR-Set

class ORSet:
    A: dict[Element, set[Tag]]     # adds
    R: dict[Element, set[Tag]]     # removes

    def add(self, x: Element, replica: ReplicaId):
        tag = (replica, fresh_counter(replica))
        self.A.setdefault(x, set()).add(tag)

    def remove(self, x: Element):
        if x in self.A:
            self.R.setdefault(x, set()).update(self.A[x])

    def contains(self, x: Element) -> bool:
        return x in self.A and bool(self.A[x] - self.R.get(x, set()))

    def merge(self, other: ORSet) -> ORSet:
        merged = ORSet()
        for x in set(self.A) | set(other.A):
            merged.A[x] = self.A.get(x, set()) | other.A.get(x, set())
        for x in set(self.R) | set(other.R):
            merged.R[x] = self.R.get(x, set()) | other.R.get(x, set())
        return merged

6. Python Implementation — Three-Replica Worked Example

from __future__ import annotations
from collections import defaultdict
from dataclasses import dataclass, field
from typing import Hashable
import itertools
 
 
@dataclass
class GCounter:
    state: dict[str, int] = field(default_factory=lambda: defaultdict(int))
 
    def increment(self, replica: str, by: int = 1):
        self.state[replica] += by
 
    def value(self) -> int:
        return sum(self.state.values())
 
    def merge(self, other: GCounter) -> GCounter:
        merged = GCounter()
        for r in set(self.state) | set(other.state):
            merged.state[r] = max(self.state.get(r, 0), other.state.get(r, 0))
        return merged
 
 
@dataclass
class ORSet:
    A: dict[Hashable, set] = field(default_factory=lambda: defaultdict(set))
    R: dict[Hashable, set] = field(default_factory=lambda: defaultdict(set))
    _counters: dict = field(default_factory=lambda: defaultdict(itertools.count))
 
    def add(self, x, replica: str):
        tag = (replica, next(self._counters[replica]))
        self.A[x].add(tag)
 
    def remove(self, x):
        if x in self.A:
            self.R[x] |= self.A[x]
 
    def value(self) -> set:
        return {x for x in self.A if self.A[x] - self.R.get(x, set())}
 
    def merge(self, other: ORSet) -> ORSet:
        merged = ORSet()
        for x in set(self.A) | set(other.A):
            merged.A[x] = self.A.get(x, set()) | other.A.get(x, set())
        for x in set(self.R) | set(other.R):
            merged.R[x] = self.R.get(x, set()) | other.R.get(x, set())
        return merged
 
 
if __name__ == "__main__":
    # Three-replica G-Counter
    a, b, c = GCounter(), GCounter(), GCounter()
    a.increment("A"); a.increment("A")           # A: a=2
    b.increment("B"); b.increment("B"); b.increment("B")  # B: b=3
    c.increment("C")                             # C: c=1
    # Network heals: A merges with B
    ab = a.merge(b)
    # Then ab merges with C, and so does b->c
    abc = ab.merge(c)
    bc = b.merge(c)
    final = abc.merge(bc)
    print("Final value:", final.value())         # 2 + 3 + 1 = 6 ✓
    # Re-merging is idempotent (CAI property)
    print("Re-merged:", final.merge(final).value())  # still 6 ✓
 
    # OR-Set demonstration
    s1, s2 = ORSet(), ORSet()
    s1.add("milk", "alice")
    s2.add("eggs", "bob"); s2.add("bread", "bob"); s2.remove("bread")
    print("s1:", s1.value(), "s2:", s2.value())
    merged = s1.merge(s2)
    print("merged:", merged.value())              # {'milk', 'eggs'}

The G-Counter example demonstrates anti-entropy convergence: regardless of which pairwise merges happen first, the final value is 6. The OR-Set demonstrates that “remove bread, but only the one Bob added” leaves a clean post-merge state with just milk and eggs.

7. Complexity

TypePer-replica stateUpdate costMerge costMessage size
G-CounterO(N) where N = replicasO(1)O(N)O(N) state-based
PN-CounterO(N)O(1)O(N)O(N) state-based
G-SetO(|S|)O(1)O(|S₁ ∪ S₂|)O(|S|) state-based
OR-SetO(|S| · avg_tags)O(1)O(|merged|)O(|delta|) for delta-CRDT
RGA / SequenceO(L · log L) typicalO(log L)dependsO(op-size) for op-based

The growth of OR-Set state with deletes is a real engineering problem: tags accumulate. Tombstone garbage collection (removing tags from R once all replicas have observed them) is necessary for long-running OR-Sets. This requires causal stability knowledge — a tombstone is collectible once every replica has seen the corresponding remove. This is itself a coordination concern; Riak handles it via sweeps.

8. Variants and Production Examples

8.1 Riak

Basho’s Riak KV (now maintained as Riak in the open-source community) was the first major production datastore to expose CRDTs as first-class types. Riak data types: Counter, Set, Map, Register, Flag. Map allows nested CRDTs (a map of sets of counters). See Riak data types.

8.2 Redis Enterprise (CRDB)

Redis Labs’ geo-distributed “Active-Active” deployment uses CRDTs for the underlying replication. They support Counter, Set, Hash, Sorted Set, Stream as CRDTs. The merge happens at the Redis cluster level; users see eventually-consistent semantics across regions.

8.3 Automerge

JavaScript / Rust library by Martin Kleppmann’s group implementing the JSON-CRDT design from his 2017 paper. Used for offline-first apps where two clients edit the same document offline and merge on reconnect. See Automerge docs.

8.4 Yjs

Highly-optimized JS/Rust CRDT framework by Kevin Jahns, implementing the YATA algorithm from his 2016 paper with RWTH Aachen co-authors (researchgate.net/publication/310212186). It exposes shared types (Y.Map, Y.Array, Y.Text, Y.XmlElement) that merge concurrently without conflicts. Yjs is unusually fast — the implementation includes ID compression, run-length encoding of adjacent items, and a tightly-packed binary protocol — and is the de-facto CRDT for browser-based editors. Its ecosystem covers a wide range of editor and storage bindings (ProseMirror, TipTap, Slate, Quill, Monaco, CodeMirror, IndexedDB, WebRTC) and is sold as a service by Liveblocks, Y-Sweet, and Tiptap Cloud. Despite frequent secondary-source claims to the contrary, Notion does not use Yjs — Notion’s collaborative text uses a server-arbitrated last-writer-wins scheme on per-block text, as confirmed by Notion engineers on public forums (see Hacker News discussion). Documented at docs.yjs.dev; source at github.com/yjs/yjs.

8.5 Figma

Figma’s October 2019 engineering blog (“How Figma’s multiplayer technology works,” Evan Wallace) is unusually candid about the architecture and is worth reading directly. The salient points, verified from the post itself:

  • Figma explicitly rejected Operational Transform (OT) — “the standard multiplayer algorithm popularized by apps like Google Docs” — calling it “overkill for what we wanted to achieve.”
  • Figma’s system is inspired by CRDTs but is not a pure CRDT: “Figma isn’t using true CRDTs though. CRDTs are designed for decentralized systems… Since Figma is centralized (our server is the central authority), we can simplify our system.”
  • Because the server is the arbiter, Figma can use last-writer-wins registers for many properties (with server-assigned timestamps that sidestep the clock-skew failure mode of LWW in a fully decentralized setting), tree-structured object IDs for the document hierarchy, and CRDT-inspired conflict-free merge rules for property-level edits.

The take-home is that Figma demonstrates a pragmatic third design point between OT and full CRDTs: borrow CRDT-style ID-tagged structures and commutative merge rules where they simplify the code, but keep a centralized server to avoid the metadata cost (tombstones, vector clocks, causal-broadcast machinery) that decentralized CRDTs pay for partition tolerance. This is increasingly common in production collaborative systems where strict decentralization is not a requirement.

8.6 Apple iCloud

iCloud’s CloudKit replication and many app-level conflict-resolution paths use CRDT-style or CRDT-inspired techniques. Public details are scarce; presentations from WWDC have referenced “vector-timestamp-based conflict resolution” which is at minimum CRDT-flavored.

8.7 Microsoft Fluid Framework

Microsoft’s collaborative-editing framework underlying Microsoft Teams (Loop / Fluid components) is CRDT-based. Open-source SDK at fluidframework.com.

8.8 SoundCloud, eBay, Bet365

SoundCloud has spoken at conferences about using Riak data types for activity feeds. eBay uses CRDTs internally for product-catalog merging across data centers. Bet365’s distributed-betting platform uses CRDTs for liability tracking across data centers.

9. Pitfalls

9.1 LWW Loses Updates Silently

Last-Write-Wins registers and sets resolve by timestamp. If clocks are skewed (and they always are — see Vector Clocks), one replica’s writes can be silently dropped. LWW is “conflict-free” only in the sense that the merge function is total; it’s not “concurrent-update-preserving.” Use OR-Set or MV-Register when this matters.

9.2 Tombstone Accumulation

OR-Set’s R grows monotonically with every removal. Without garbage collection, long-lived sets bloat. GC requires causal-stability tracking — knowing every replica has seen the remove — which is non-trivial.

9.3 Some Operations Genuinely Need Coordination

Reserving a unique seat, atomically transferring funds, ensuring a unique username — these have invariants that no CRDT can preserve under partition. Section 4 of Shapiro et al. acknowledges this; the solution is to use Two-Phase Commit or Raft for those operations and CRDTs for everything else.

9.4 Causal Delivery for Op-Based CRDTs

Op-based CRDTs assume the network delivers operations in causal order (and exactly once). If the network reorders or duplicates, op-based CRDTs break. Implementations either build a causal-broadcast layer (vector-clock-based) or fall back to state-based.

9.5 Replica Identifier Collision

G-Counter assumes replica IDs are unique. If two replicas share an ID, increments collide via max instead of accumulating, losing increments. Use UUIDs or a coordination service.

9.6 Concurrent Add/Remove Semantics Vary

  • Add-wins (OR-Set): concurrent add + remove → element present.
  • Remove-wins: concurrent add + remove → element absent.
  • 2P-Set: remove-wins absolutely (re-add forever forbidden).

These are different application-level semantics with different bug profiles. Users must pick the right one for their use case.

9.7 State-Based Message Bloat

A G-Counter’s state is N integers (N = replica count). For a 1000-region deployment, every gossip message is ~8 KB just for one counter. Delta-CRDTs (Almeida et al. 2018) ship only changes, addressing this.

9.8 Equality vs Equivalence

Two CRDT states can encode the same observable value with different internal state (e.g., two OR-Sets with different tag sets but the same visible elements). Naive equality checks compare internals; users want semantic equality (compare the value() results). Bug source.

9.9 Snapshotting and Compaction

Like LSM trees, CRDTs benefit from periodic compaction. But compaction must preserve the lattice properties — naive compaction can lose updates from replicas behind on sync. Designs like delta-state CRDTs handle this carefully.

9.10 Anti-Entropy Cost

CRDTs need eventual propagation, typically via gossip (Gossip Protocol). Network partition healing produces a flood of merges. Tail latencies during reconnect can spike.

10. Mermaid Diagram — State Lattice and Merge

flowchart BT
    subgraph "G-Counter Lattice (3 replicas A, B, C)"
        bot["⊥ = (0,0,0)"]
        s1["(2,0,0) <br/>A=2"] --> bot
        s2["(0,3,0) <br/>B=3"] --> bot
        s3["(0,0,1) <br/>C=1"] --> bot
        s12["(2,3,0) <br/>= s1 ⊔ s2"]
        s13["(2,0,1) <br/>= s1 ⊔ s3"]
        s23["(0,3,1) <br/>= s2 ⊔ s3"]
        s12 --> s1
        s12 --> s2
        s13 --> s1
        s13 --> s3
        s23 --> s2
        s23 --> s3
        top["(2,3,1) <br/>= s1 ⊔ s2 ⊔ s3 = supremum"]
        top --> s12
        top --> s13
        top --> s23
    end

What this diagram shows. The Hasse diagram of the partial order on G-Counter states for three replicas A, B, C, with the bottom element ⊥ = (0,0,0) (initial state, no increments anywhere) and the top of the visible portion (2, 3, 1) representing the merged state after A has incremented 2, B has incremented 3, and C has incremented 1 in some order. Edges go upward toward larger states (in the lattice partial order: componentwise ≤). Each node (a, b, c) represents the state where replica A has applied a increments, B has b, C has c. The crucial visual pattern is that every pair of states has a unique least upper bound — for instance, (2,0,0) and (0,3,0) both lie below (2,3,0), and (2,3,0) is the smallest such state. The merge operation ⊔ computes exactly this least upper bound. Eventual consistency is the statement that, if all replicas eventually exchange and merge, every replica’s state climbs the lattice and converges to the supremum (2,3,1) — the correct final value summing every replica’s contributions. The diagram makes monotonicity visible: an update on replica A (incrementing the first coordinate) can only move the state upward through one of the leftward edges; it never decreases any coordinate.

11. Common Interview Problems / System-Design Round Questions

QuestionWhat to hit
“What’s a CRDT?”Data type with mathematically-conflict-free merge; eventual consistency without coordination
“Why CRDTs over Last-Write-Wins?”LWW silently drops concurrent updates; CRDTs preserve them by structure
“Design a counter that works across data centers without coordination”G-Counter — vector indexed by replica, merge via element-wise max
“Why a vector instead of a single integer?”A scalar would lose concurrent increments through max(6,6)=6; vector preserves per-replica contributions
“Implement a set that supports add and remove with concurrent operations”OR-Set — tag adds with unique IDs, remove records observed tags, merge unions both
“What’s a join-semilattice?”Poset where every pair has a least upper bound; CRDT state forms one
“Why must merge be commutative, associative, idempotent?”These three are exactly the lattice axioms — they make merge order-independent
“When can you NOT use a CRDT?”Operations with global invariants (uniqueness, capacity limits) need coordination
“Compare CRDTs to Operational Transform”OT requires order-preserving transforms; CRDTs use ID-tagged operations that commute by construction
“Compare state-based and op-based”State: large messages, weak network; Op: small messages, needs causal delivery
“What is delta-state CRDT?”Hybrid: ship a small delta with state-based safety; reduces bandwidth
“Walk through a 3-replica concurrent counter trace”Per-replica vectors evolve independently; merges via max recover the total
“Why do real-time editors (Yjs, Automerge) use CRDTs?”Offline-first, P2P sync, no central coordinator needed
“What’s tombstone GC?”Removing dead entries from R once all replicas have seen the remove; needs causal stability

12. Open Questions

  • How do you efficiently GC tombstones in a heterogeneous deployment where replica liveness is unknown?
  • What’s the practical limit on N (replica count) for vector-based CRDTs before metadata dominates?
  • Is there a CRDT for ordered sequences that doesn’t need O(L log L) auxiliary metadata? (Recent work on RGAs and L-WOOT suggests yes for some operation patterns.)
  • How does CRDT formalism extend to operations with side effects (e.g., “send notification on add”)?
  • Can we design CRDTs with stronger-than-eventual-consistency guarantees (e.g., causal+, monotonic reads) without paying for coordination?
  • The 2017 Kleppmann JSON-CRDT works but is complex; can simpler nested CRDTs achieve the same expressiveness?

13. See Also

Graph View

Backlinks