Skip to content

CRDTs — Detailed#

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