CRDTs and collaborative editing

Two people edit the same document at the same time. Maybe both are online and their keystrokes cross in flight, or one of them is on a plane. Either way, their copies must end up identical, and the result should still make sense. This is one of the oldest problems in distributed systems with a user interface, and it has two families of answers: operational transformation, which powers Google Docs, and conflict-free replicated data types, which power local-first software and an increasing number of collaborative apps.

This article explains why the naive approach diverges, how OT repairs it and why OT is hard, what makes a data type “conflict-free”, how sequence CRDTs give every character a permanent identity, and the subtle problems (interleaving and tombstones) that took the field a decade to work through. The main figure runs a real RGA merge.

The problem

The obvious design sends edits as positions: “insert ‘B’ at index 3”. But an index means something only relative to the document it was computed on. If the other replica has inserted text before index 3 in the meantime, the same operation now lands somewhere else. Apply the same set of operations in a different order and you get a different document.

Operational transformation

OT (Ellis & Gibbs, 1989) keeps index-based operations but transforms each incoming operation against the concurrent operations already applied locally. If Alice inserted a character before Bob’s delete, Bob’s delete index shifts by one when it arrives at Alice. A transformation function T must close the “diamond”:

For two operations, the property is called TP1. For three or more concurrent operations exchanged peer to peer, transformations must also be independent of the path taken (TP2). TP2 turned out to be remarkably hard: several published OT algorithms were later shown by counterexample to violate it. Production systems avoid the problem with a central server that assigns every operation a place in a single total order (the Jupiter model), so each client only ever transforms against the server’s history. Google Docs works this way, and so did Google Wave. It works well, at the price of a server that must see every operation.

Strong eventual consistency

CRDTs (Shapiro et al., 2011) take the opposite approach: design the data type so that concurrent operations commute by construction, and no transformation is needed. The guarantee is strong eventual consistency: any two replicas that have received the same set of updates, in any order, are in the same state. No consensus, no coordination, no server required, and any replica can accept writes while offline.

State-based and op-based CRDTs

• State-based (CvRDT). Replicas periodically send their whole state, and the receiver merges it into its own. Convergence holds if states form a join semilattice and merge computes the join: it must be commutative, associative and idempotent. Delivery can then be unreliable: messages may be duplicated, reordered or lost and retried.
• Operation-based (CmRDT). Replicas broadcast operations, which are much smaller. Concurrent operations must commute, and the network must deliver every operation exactly once and in causal order. Delta-state CRDTs sit between the two, shipping small state fragments that merge like full states.

Registers, counters and sets

• Counters. The G-Counter in Fig. 3 only grows. A PN-Counter pairs two of them, one for increments and one for decrements, and reports the difference.
• Last-writer-wins register. Each write carries a timestamp, usually a Lamport or hybrid logical clock with the replica id as a tie-break, and merge keeps the larger. It is simple and widely used, but a concurrent write is silently discarded. A multi-value register keeps all concurrent values and lets the application or the user choose.
• Sets. Add and remove don’t commute naively: if one replica adds x while another removes it, which wins? The observed-remove set tags every add with a unique id, and a remove deletes only the tags it has observed. A concurrent add has a fresh tag the remove didn’t see, so it survives: “add wins”.
• JSON documents. Automerge (Kleppmann & Beresford, 2017) composes these into nested maps and lists, giving a whole application state that merges automatically.

Sequence CRDTs for text

Text is the hard case. The key move is to stop referring to positions and give every character a permanent unique identifier. An insert then says “put this character after the character with id X”, which means the same thing on every replica no matter what else has happened. The design question is how to order concurrent inserts at the same spot.

• RGA (Replicated Growable Array, Roh et al., 2011): each character’s id is a Lamport timestamp plus replica id. Among characters inserted after the same element, the one with the larger id comes first. That is the rule Fig. 1 runs, and why “Bob” (ids 3B–6B) precedes “Ann” (3A–6A) on both replicas.
• YATA (Nicolaescu et al., 2016), the algorithm behind Yjs, records both the left and the right neighbour at insertion time and orders conflicts using both.
• Logoot, LSEQ, Treedoc give each character a position identifier from a dense ordered space, like fractions between 0 and 1, so ordering is just comparing identifiers. Generating a new identifier between two existing ones never fails, but identifiers can grow long.

The interleaving problem

Convergence is not the whole story. Suppose Alice types “Ann” and Bob types “Bob” at the same place. “Hi Bob Ann” and “Hi Ann Bob” are both fine. “Hi BAonbn” converges just as well, but is useless. Kleppmann et al. (2019) showed that several published sequence CRDTs, notably Logoot and LSEQ, can interleave concurrently inserted runs character by character, and that RGA, while it avoids that worst case, still allows a milder form of the anomaly in some editing patterns. Fugue (Weidner & Kleppmann, 2023) gives a precise definition of “maximal non-interleaving” and an algorithm that achieves it. In Fig. 1, RGA keeps each word intact because each character is inserted after its own predecessor, so a run forms a chain that concurrent runs can’t split.

Tombstones and performance

A deleted character can’t simply vanish: another replica may concurrently insert after it, and that insert must still find its anchor. Sequence CRDTs therefore keep deleted elements as tombstones. A heavily edited document can contain many more tombstones than visible characters. Removing them safely requires knowing that every replica has seen the deletion (causal stability), which is hard to know in an open, offline-capable system.

Early implementations stored one object per character with all its metadata and were slow and memory-hungry, which gave CRDTs a reputation they no longer deserve. Modern libraries store runs of consecutively typed characters as a single item, compress ids and metadata, and keep only the structure of deleted text, not its content. Eg-walker (Gentle & Kleppmann, 2024) goes further: it stores a plain operation log and builds CRDT state only temporarily, for the stretch of history where concurrent edits need merging. It is faster to load and smaller to store than both classic CRDTs and OT.

How real products sync

Many products that look peer-to-peer actually use a server, and borrow CRDT ideas selectively. Figma’s engineering team has described their multiplayer system as inspired by CRDTs but simpler: the server is the authority, each object property is a last-writer-wins register, the order of children is kept with fractional indices between neighbours, and the server rejects edits that would, for example, create a cycle in the layer tree. Text inside a document remains the case where full sequence CRDTs (Yjs, Automerge, Loro, Diamond Types) earn their complexity.

The choice comes down to topology. With a reliable central server and no offline editing, OT or a simpler server-ordered log is enough. With offline editing, peer-to-peer sync or end-to-end encryption, where the server can’t read operations to transform them, CRDTs are the only practical option. That is the core of the local-first software movement (Kleppmann et al., 2019).

RGA in code

A complete replicated sequence: unique ids from a Lamport clock, inserts anchored to their left neighbour, deletes as tombstones, and the one ordering rule that makes concurrent inserts converge.

// RGA: a replicated sequence. Every element has a unique id and remembers what it was inserted after.
type Id = { counter: number; replica: string };
type Elem = { id: Id; value: string; deleted: boolean };
type Op =
  | { kind: "insert"; id: Id; after: Id | null; value: string }
  | { kind: "delete"; id: Id };

const cmp = (a: Id, b: Id) =>
  a.counter !== b.counter ? a.counter - b.counter : a.replica < b.replica ? -1 : a.replica > b.replica ? 1 : 0;
const same = (a: Id | null, b: Id) => a !== null && cmp(a, b) === 0;

export class RGA {
  private elems: Elem[] = [];
  private clock = 0;
  constructor(private replica: string) {}

  // Local edits produce operations to broadcast. Positions are visible indices.
  insertAt(index: number, value: string): Op {
    const visible = this.elems.filter((e) => !e.deleted);
    const after = index === 0 ? null : visible[index - 1].id;
    const op: Op = { kind: "insert", id: { counter: ++this.clock, replica: this.replica }, after, value };
    this.apply(op);
    return op;
  }
  deleteAt(index: number): Op {
    const op: Op = { kind: "delete", id: this.elems.filter((e) => !e.deleted)[index].id };
    this.apply(op);
    return op;
  }

  // Remote and local operations go through the same path. Requires causal delivery:
  // an insert arrives after the element it references.
  apply(op: Op) {
    if (op.kind === "delete") {
      const e = this.elems.find((x) => cmp(x.id, op.id) === 0);
      if (e) e.deleted = true; // a tombstone: the element stays as an anchor
      return;
    }
    this.clock = Math.max(this.clock, op.id.counter); // Lamport clock
    let i = op.after === null ? 0 : this.elems.findIndex((e) => same(op.after, e.id)) + 1;
    // Concurrent inserts after the same element: the larger id goes first.
    while (i < this.elems.length && cmp(this.elems[i].id, op.id) > 0) i++;
    this.elems.splice(i, 0, { id: op.id, value: op.value, deleted: false });
  }

  toString() {
    return this.elems.filter((e) => !e.deleted).map((e) => e.value).join("");
  }
}

References

1. Shapiro, M., Preguiça, N., Baquero, C. & Zawirski, M. (2011). Conflict-free Replicated Data Types. SSS. doi:10.1007/978-3-642-24550-3_29
2. Ellis, C. A. & Gibbs, S. J. (1989). Concurrency Control in Groupware Systems. SIGMOD. doi:10.1145/67544.66963
3. Nichols, D. A. et al. (1995). High-Latency, Low-Bandwidth Windowing in the Jupiter Collaboration System. UIST. doi:10.1145/215585.215706
4. Roh, H.-G., Jeon, M., Kim, J.-S. & Lee, J. (2011). Replicated abstract data types: Building blocks for collaborative applications. JPDC. doi:10.1016/j.jpdc.2010.12.006
5. Nicolaescu, P. et al. (2016). Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types. GROUP. doi:10.1145/2957276.2957310
6. Kleppmann, M. & Beresford, A. R. (2017). A Conflict-Free Replicated JSON Datatype. IEEE TPDS. arXiv:1608.03960
7. Kleppmann, M., Gomes, V. B. F., Mulligan, D. P. & Beresford, A. R. (2019). Interleaving anomalies in collaborative text editors. PaPoC. doi:10.1145/3301419.3323972
8. Weidner, M. & Kleppmann, M. (2023). The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing. arXiv:2305.00583
9. Gentle, J. & Kleppmann, M. (2024). Collaborative Text Editing with Eg-walker: Better, Faster, Smaller. arXiv:2409.14252
10. Kleppmann, M., Wiggins, A., van Hardenberg, P. & McGranaghan, M. (2019). Local-first software: You own your data, in spite of the cloud. Onward! inkandswitch.com/local-first
11. Wallace, E. (2019). How Figma’s multiplayer technology works. Figma blog. figma.com/blog