Skip to content

CRDTs#

Problem statement (interviewer prompt)

Design a data structure that two replicas can update concurrently - without coordination - and still converge to the same state after they sync. Cover counters, sets, and text editing. Explain garbage collection, op-based vs state-based variants, and where you'd use them.

flowchart LR
  A[Replica A<br/>local op]
  B[Replica B<br/>local op]
  A -. async sync .-> B
  B -. async sync .-> A
  A --> CV[Converged state]
  B --> CV

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class A,B,CV service;

Conflict-free Replicated Data Types: any order of merges yields the same state. No coordination needed for writes.

flowchart TB
  subgraph Families[Two families]
    SB[State-based CvRDT<br/>merge S1, S2 = join lattice]
    OP[Op-based CmRDT<br/>commutative ops + causal delivery]
    DELTA[Delta-state<br/>send only diffs]
  end

  subgraph Counters
    GC[G-Counter<br/>per-replica increments]
    PNC[PN-Counter<br/>two G-Counters: + and -]
  end

  subgraph Sets
    GS[G-Set<br/>add-only]
    TPS[2P-Set<br/>add + remove tombstones]
    ORS[OR-Set / OR-Set-AWW<br/>add-wins via unique tags]
    LWWS[LWW-Element-Set]
    RWS[Remove-Wins-Set]
  end

  subgraph Maps_Regs[Maps and Registers]
    MV[Multi-Value Register]
    LWW[LWW Register]
    ORM[OR-Map / AW-Map]
  end

  subgraph Sequences[Sequences - for text]
    RGA[RGA<br/>Replicated Growable Array]
    LSEQ[LSEQ]
    LOGO[Logoot]
    YJS[Yjs / Automerge<br/>Yata, modern CRDTs]
    TR[Treedoc]
  end

  subgraph Graph[Graphs]
    SG[Add-only graph]
    G2[2P-graph / OR-graph]
  end

  subgraph Sync[Sync mechanisms]
    GOSS[Gossip / anti-entropy]
    DV[Dotted version vectors]
    CC[Causal context]
    DELTA2[Delta-CRDTs reduce bandwidth]
  end

  subgraph Apps[Where used]
    DOC[Google Docs / Yjs editors]
    FIG[Figma multiplayer]
    NOT[Notion blocks]
    REDIS[Redis CRDT - Enterprise]
    RIAK[Riak DT, Roshi]
    AKKA[Akka Distributed Data]
  end

  Families --> Counters
  Families --> Sets
  Families --> Maps_Regs
  Families --> Sequences
  Sync --- Sequences
  Apps --- Sequences
  Apps --- Counters

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class SB,OP,DELTA,GC,PNC,GS,TPS,ORS,LWWS,RWS,MV,LWW,ORM,RGA,LSEQ,LOGO,YJS,TR,SG,G2,GOSS,DV,CC,DELTA2,DOC,FIG,NOT,RIAK,AKKA service;
    class REDIS cache;

Properties#

  • Commutative: a ⊕ b = b ⊕ a
  • Associative: a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
  • Idempotent: a ⊕ a = a (state-based)

Together → state is a join-semilattice; merges always converge.

Example: G-Counter#

state: { replicaId -> count }
inc():  state[me]++
value(): sum(state.values())
merge(s1, s2): { id -> max(s1[id], s2[id]) }  # pointwise max

Example: OR-Set (add-wins)#

  • Add(x): generate unique tag t, store (x, t).
  • Remove(x): remove all currently-known (x, t) for that x.
  • Merge: union of tags; concurrent add+remove → add wins.

Text CRDTs (RGA, Yjs)#

  • Each character has a globally unique id + parent.
  • Insertions go between siblings; deletions are tombstones (later GC'd).
  • Yjs / Automerge are state-of-the-art for size + speed.

Pitfalls#

  • Tombstones grow forever - need GC with causal stability.
  • State-based merges blow up bandwidth → use delta-CRDTs.
  • Op-based requires causal delivery (vector clocks / dotted contexts).

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag Concept What it is Page
HLD Leader/follower replication sync/semi-sync/async replication, failover replication-leader-follower
HLD Logical clocks Lamport, vector clocks, HLC, TrueTime logical-clocks
HLD CRDTs commutative replicated data types crdts

Quick reference#

When you actually need them#

  • Offline-first apps that sync later.
  • Multi-leader / multi-region writes without a coordinator.
  • Collaborative editors (Docs, Figma, Notion, whiteboards).
  • Mobile sync (CouchDB / Couchbase Lite).
  • Edge clouds (Cloudflare Durable Objects, Cloudflare D1 alt).

CRDT vs OT (Operational Transformation)#

  • OT transforms incoming ops against local concurrent ops; requires server with global order (Google Docs original).
  • CRDTs decentralize but at higher memory / metadata cost.
  • Modern collab tools (Yjs, Automerge) use CRDTs; Google Docs / Quill moved partially.

Practical concerns#

  • Garbage collection: tombstones and old version metadata must be GC'd once all replicas have observed them - needs causal stability tracking.
  • Bandwidth: state-based diffing is hard; delta-CRDTs ship only deltas.
  • Permissions / ACL: CRDTs don't model authorization; layer on top.

Where they show up in this repo#

  • Google Docs, Figma, Notion, Online Whiteboard, Collab editor.
  • Distributed cache (counters), shopping cart (Dynamo).
  • Multi-region key-value stores (Riak, Redis Enterprise).

Refs#

  • Shapiro, Preguiça et al.: "Conflict-free Replicated Data Types" (SSS '11).
  • Almeida et al.: "Delta-CRDTs."
  • Yjs / Automerge papers and docs.
  • Riak DT docs; Akka Distributed Data; Cassandra LWW limits.

FAQ#

What is a CRDT?#

A Conflict-free Replicated Data Type is a data structure that multiple replicas can update concurrently without coordination, and still converge to the same value once they exchange updates.

What is the difference between state-based and op-based CRDTs?#

State-based CRDTs ship the full merged state and require an idempotent commutative merge. Op-based CRDTs ship operations and need exactly-once causally ordered delivery.

CRDTs vs operational transformation, which is better?#

CRDTs are easier to reason about and run without a central server, ideal for peer-to-peer. OT is more compact and predates CRDTs, used by Google Docs. Modern systems like Figma and Linear use CRDTs.

Where are CRDTs used in production?#

Redis CRDTs in Enterprise, Riak, Automerge, Yjs in collaborative editors like Notion and Linear, Soundcloud counters, and Apple's iCloud sync for notes and reminders all rely on CRDTs.

What are the downsides of CRDTs?#

Metadata overhead grows with replicas and updates, garbage collection is hard, and not every data type has a known CRDT. Causal ordering and tombstones often make storage and bandwidth bigger.

Further reading#

Curated, high-credibility sources for going deeper on this topic.