Skip to content

CONCEPT Cited by 1 source

Conflict-free Replicated Data Type (CRDT)

A Conflict-free Replicated Data Type (CRDT) is a data structure replicated across multiple machines such that: (1) any replica may be updated independently and concurrently without coordination, (2) the type itself encodes an algorithm that auto-resolves inconsistencies, (3) replicas eventually converge if all updates stop — replicas may disagree at any instant, but never forever. The convergence property is a mathematical invariant of the type, not an invariant maintained externally by a coordinator.

Canonical examples (Figma quotes these two):

  • Grow-only set (G-Set) — the only update is "add X." Adding X twice is a no-op. State is recoverable from any replay of updates in any order. Commutativity + idempotency = convergence.
  • Last-writer-wins register (LWW-Register) — container for a single value. Update = (value, timestamp, peerID). Read returns the update with the greatest (timestamp, peerID) tuple, using peerID as a deterministic tiebreaker when timestamps collide.

See Preiss's CRDT notes for a broader portfolio (counters, OR-sets, sequences, trees, etc.).

The centralization simplification

CRDTs are designed for decentralized systems — peer-to-peer networks, edge replicas, mobile clients with intermittent server contact, where no single authority decides the canonical state. The mathematical convergence-without-coordination guarantee has unavoidable overhead: metadata per update, tombstones on delete-support variants, vector clocks or per-peer counters.

If a system does have a central authority, that overhead is pure waste — the authority can just tie-break. Figma's Multiplayer is inspired by CRDTs but not a CRDT: the server owns a per-document process that is the single authority, so Figma "simplifies our system by removing this extra overhead and benefits from a faster and leaner implementation." (Source: sources/2019-figma-how-figmas-multiplayer-technology-works)

The insight: the CRDT literature is still worth studying even when building a centralized system. It's the well-studied foundation for reasoning about what should converge and what shape of operation composes safely. Starting there and relaxing the decentralization constraint is cheaper than starting from scratch.

Why not OT?

OT is the alternative lineage for real-time collaborative editing (Google Docs, Etherpad). It's a runtime-transformation approach rather than a data-structure convergence approach. OT's combinatorial-state-explosion critique (Wikipedia) pushed Figma toward the CRDT foundation despite being centralized.

Composition, not monolith

Figma's document data structure "isn't a single CRDT" — it's a composition of multiple CRDTs layered into an overall structure (the object tree). A property value might be LWW-register flavor; an object-children list might be a different type. Composition + central-authority tie-break = a bespoke centralized reconciler inspired by the CRDT tradition.

Seen in

Last updated · 200 distilled / 1,178 read