The CRDT That Throws Itself Away: Inside Eg-walker

Here's a number from a recent systems paper that stopped me cold.

Take the real editing history of Git's own Makefile, reconstructed from the Git repository, with its many authors and branches. Merge it with a classic Operational Transformation algorithm, and it takes one hour. Merge it with an algorithm called Eg-walker, and it takes 24 milliseconds.

Eg-walker comes from Joseph Gentle and Martin Kleppmann, in the paper Collaborative Text Editing with Eg-walker: Better, Faster, Smaller, presented at EuroSys 2025. What makes it interesting isn't just the speed. It's the trick behind it: a CRDT that only exists for the duration of a merge and is then thrown away.

If you've worked with collaborative editing, you know the trade-off this breaks. Let's look at how.

The trade-off everyone has lived with

There are two families of algorithms for collaborative text.

Operational Transformation (OT) stores the document as plain text and transforms concurrent operations against each other. It's memory-light and loads instantly, which is why Google Docs, Microsoft Office, and Overleaf use it. The problem is merging. If two users each made n edits while apart, every edit from one side has to be transformed against every edit from the other. That's at least O(n²), and some OT algorithms are cubic or worse. Fine for real-time typing with small n. Painful for offline work or long-running branches.

CRDTs give every character a unique ID and store positions relative to other IDs. Merging long branches is fine, and they work peer-to-peer. But that metadata has to be loaded from disk and held in memory the entire time a document is open, even when nobody else is editing. The paper measured that even the best CRDTs today use more than ten times the memory of OT just to view and edit a document.

So you pick: slow merges, or heavy documents.

Insight 1: store the history, not the state

Eg-walker starts by changing what gets stored and replicated.

Instead of CRDT metadata, every replica keeps an event graph: a DAG of every edit, where each event holds three things. An ID, the IDs of its parent events, and the operation exactly as the user performed it. That means plain index-based operations like Insert(3, "l") or Delete(1), never transformed, never rewritten.

If that sounds like Git, it should. The parents of an event record what its author had seen when they made it. Two events are concurrent if neither is an ancestor of the other, just like two commits on different branches.

This gives a clean definition of the problem. The document is simply:

document = replay(eventGraph)

where replay is a deterministic function. Any two replicas with the same set of events must produce the same document. Everything else is about making replay fast.

Insight 2: you only need a CRDT when there's concurrency

Here's the observation the whole algorithm rests on.

When you type locally, your edit's parent is the current state of the document. When a remote edit arrives that was made after everything you already have, its parent is also the current state. In both cases, there's nothing to transform. The edit's index is already correct, and you can apply it directly to a plain string.

Transformation is only needed when concurrent events meet. And in most real editing histories, concurrency is rare. Authors take turns, or there's only one author.

So Eg-walker keeps three things per replica:

1. The event graph, on disk.
2. The document, as plain text, in memory. No metadata at all.
3. An internal CRDT state, which is temporary. It's built only to merge concurrent edits and then discarded. It's never saved to disk and never sent over the network.

Most of the time, the third item doesn't exist.

How replay works

When concurrent events do need merging, Eg-walker walks the event graph in topological order and builds its temporary CRDT as it goes. The clever part is that the CRDT tracks the document at two versions at once:

• The effect version: the document with every event processed so far applied. This only moves forward.
• The prepare version: the document exactly as the author of the current event saw it. This moves backward and forward.

Why two versions? Because an event like Delete(1) means "delete whatever was at index 1 in the author's view." To find the right character, you need the author's view (prepare). To know where that character sits in the real merged document, you need the full view (effect).

Each character gets one record in a list, including deleted ones. Each record holds two small states:

• Prepare state: NotInsertedYet, Ins, or Del n (deleted by n concurrent deletions in the prepare view).
• Effect state: Ins or Del.

And three operations move things around:

• apply(e): interpret e in the prepare version, update both versions, and output the transformed operation for the real document.
• retreat(e): make the prepare version behave as if e never happened.
• advance(e): make e take effect in the prepare version again.

A walkthrough

Let's use the paper's own example. The document starts as hi. One user changes it to hey. At the same time, another user capitalizes it to Hi. After syncing, someone adds !.

Event	Operation	Branch
e1, e2	Insert h, Insert i	shared start: hi
e3, e4	Insert(0, H), Delete(1)	user B: Hi
e5, e6, e7	Delete(1), Insert(1, e), Insert(2, y)	user A: hey
e8	Insert(3, !), parents: e4 and e7	after merging

Replaying in order:

1. Apply e1 to e4. Each event's parent is the previous one, so nothing to adjust. The internal records are H, h (deleted), i, and the real document is Hi.
2. Before e5, retreat e4 and e3. User A never saw B's edits, so the prepare version must forget them. H becomes NotInsertedYet, and h becomes Ins again. The effect state doesn't change: the real document is still Hi.
3. Apply e5, e6, e7. A's Delete(1) is interpreted against A's view, hi, so it deletes i. A's inserts land after h in the record list. But when converted to the effect version, they're counted relative to the real document, which contains H. The real document becomes Hey.
4. Before e8, advance e3 and e4. e8's author had seen both branches, so B's edits are brought back into the prepare view.
5. Apply e8. Insert(3, "!") is interpreted against Hey, and the result is Hey!.

Notice what happened in step 3. A's Delete(1) was index-based, written against a document that never existed on B's machine. Retreating and advancing let the algorithm reconstruct exactly the view A had, at the cost of a few state flips.

A toy implementation

Here's a deliberately simple version in JavaScript, about 80 lines for the core. It skips all the performance work (more on that below), but it follows the algorithm's structure: topological sort, prepare/effect states, retreat/advance, and transformed output.

const NOT_INSERTED = -1, INS = 0; // sp: -1 not yet inserted, 0 inserted, n>0 deleted n times

export class EventGraph {
  constructor() { this.events = new Map(); }
  add(e) { this.events.set(e.id, e); return e; }

  // Lamport timestamp: one more than the max of the parents
  lamport(id) {
    const e = this.events.get(id);
    if (e._lt === undefined) e._lt = 1 + Math.max(0, ...e.parents.map(p => this.lamport(p)));
    return e._lt;
  }

  ancestors(ids) { // a version plus everything that happened before it
    const out = new Set(), stack = [...ids];
    while (stack.length) {
      const id = stack.pop();
      if (out.has(id)) continue;
      out.add(id);
      stack.push(...this.events.get(id).parents);
    }
    return out;
  }

  topoSort(shuffle = false) {
    const children = new Map(), order = [], seen = new Set();
    for (const e of this.events.values()) {
      for (const p of e.parents) {
        if (!children.has(p)) children.set(p, []);
        children.get(p).push(e.id);
      }
    }
    const visit = (id) => {
      if (seen.has(id)) return;
      if (!this.events.get(id).parents.every(p => seen.has(p))) return;
      seen.add(id); order.push(id);
      const kids = [...(children.get(id) || [])];
      if (shuffle) kids.sort(() => Math.random() - 0.5);
      for (const k of kids) visit(k);
    };
    const roots = [...this.events.values()].filter(e => e.parents.length === 0).map(e => e.id);
    if (shuffle) roots.sort(() => Math.random() - 0.5);
    for (const r of roots) visit(r);
    return order;
  }
}

export function replay(graph, { shuffle = false } = {}) {
  const order = graph.topoSort(shuffle);
  const pos = new Map(order.map((id, i) => [id, i]));
  const records = [];       // temporary CRDT: one record per character, incl. tombstones
  const target = new Map(); // event id -> record it touched
  let prepare = [];         // current prepare version
  let doc = '';             // the real document (effect version)

  const cmp = (a, b) =>     // total order on events: Lamport timestamp, then agent
    graph.lamport(a) - graph.lamport(b) ||
    (graph.events.get(a).agent < graph.events.get(b).agent ? -1 : 1);

  const nthVisibleInPrepare = (n) => {
    let seen = -1;
    for (let i = 0; i < records.length; i++)
      if (records[i].sp === INS && ++seen === n) return i;
    return -1;
  };
  const effectIndex = (recIdx) =>
    records.slice(0, recIdx).filter(r => r.se === INS).length;

  for (const id of order) {
    const e = graph.events.get(id);

    // 1. Move the prepare version to e.parents
    const oldSet = graph.ancestors(prepare), newSet = graph.ancestors(e.parents);
    const toRetreat = [...oldSet].filter(x => !newSet.has(x)).sort((a, b) => pos.get(b) - pos.get(a));
    const toAdvance = [...newSet].filter(x => !oldSet.has(x)).sort((a, b) => pos.get(a) - pos.get(b));
    for (const x of toRetreat) {
      const r = target.get(x);
      r.sp = graph.events.get(x).type === 'ins' ? NOT_INSERTED : r.sp - 1;
    }
    for (const x of toAdvance) {
      const r = target.get(x);
      r.sp = graph.events.get(x).type === 'ins' ? INS : r.sp + 1;
    }

    // 2. Apply e, interpreting its index in the prepare version
    if (e.type === 'ins') {
      let i = e.index === 0 ? 0 : nthVisibleInPrepare(e.index - 1) + 1;
      // Tie-break among concurrent inserts at the same spot (RGA-style rule)
      while (i < records.length && records[i].sp === NOT_INSERTED && cmp(records[i].id, id) > 0) i++;
      const rec = { id, ch: e.ch, sp: INS, se: INS };
      records.splice(i, 0, rec);
      target.set(id, rec);
      const at = effectIndex(i);
      doc = doc.slice(0, at) + e.ch + doc.slice(at);   // transformed op: insert at `at`
    } else {
      const i = nthVisibleInPrepare(e.index);
      const rec = records[i];
      target.set(id, rec);
      rec.sp += 1;
      if (rec.se === INS) {
        const at = effectIndex(i);
        rec.se = 'del';
        doc = doc.slice(0, at) + doc.slice(at + 1);    // transformed op: delete at `at`
      }                                                // already deleted elsewhere: no-op
    }
    prepare = [id];
  }
  return doc;
}

And a tiny helper to record edits the way a real editor would, with each event's parents set to whatever its author had seen:

export function makeAgent(graph, name) {
  let seq = 0, frontier = [];
  return {
    get frontier() { return frontier; },
    set frontier(f) { frontier = f; },
    ins(index, ch) {
      const e = graph.add({ id: `${name}${++seq}`, agent: name, type: 'ins', index, ch, parents: frontier });
      frontier = [e.id];
    },
    del(index) {
      const e = graph.add({ id: `${name}${++seq}`, agent: name, type: 'del', index, parents: frontier });
      frontier = [e.id];
    },
  };
}

Now replay the walkthrough:

const g = new EventGraph();
const a = makeAgent(g, 'a'), b = makeAgent(g, 'b');

a.ins(0, 'h'); a.ins(1, 'i');           // shared start: "hi"
b.frontier = a.frontier;

b.ins(0, 'H'); b.del(1);                // B: "Hi"
a.del(1); a.ins(1, 'e'); a.ins(2, 'y'); // A: "hey"

a.frontier = [...b.frontier, ...a.frontier]; // A syncs with B
a.ins(3, '!');

console.log(replay(g)); // "Hey!"

Every operation in the graph is stored exactly as typed. replay produces Hey!. Run it with { shuffle: true } and you get a different traversal order but the same result.

Two honest caveats about this toy. It uses a simple RGA-style rule to order concurrent insertions at the same position, while the authors use a variant of the Yjs algorithm designed to avoid interleaving concurrent runs of text. And it replays everything from scratch with linear scans, which brings us to the part that makes the real thing fast.

Insight 3: critical versions let you forget

A critical version is a point in the history where everything before it happened before everything after it. No branch crosses it. In a linear editing session, every single version is critical.

The paper's key observation is that critical versions split the history into independent sections. Events before one can't affect how events after it are transformed. That enables two optimizations:

• Whenever replay reaches a critical version, the entire internal state can be thrown away. It's replaced with a single placeholder record meaning "some unknown text is here."
• If an event and its parent are both critical, it's emitted unchanged. No CRDT work at all.

So when a concurrent edit arrives later, Eg-walker doesn't replay from the beginning of time. It finds the most recent critical version before the concurrency, starts from a placeholder, replays only the events since then, and applies the new ones.

For a document that's mostly edited by one person at a time, that means almost the entire history is skipped.

What the benchmarks show

The authors tested on real editing traces: sequential writing, real-time collaboration, and histories reconstructed from Git repositories. They compared their Rust implementation against Automerge, Yjs, their own optimized reference CRDT, and an OT implementation.

• Merging long branches: On the Git Makefile trace, OT took an hour while Eg-walker took 24 ms, about 160,000 times faster.
• Sequential editing: Eg-walker was 7 to 10 times faster than their reference CRDT, which itself outperformed both Yjs and Automerge.
• Memory: In the steady state, while a document is open for editing, Eg-walker used 1 to 2 orders of magnitude less memory than the best CRDT.
• Loading: Like OT, a document loads as plain text, orders of magnitude faster than the CRDTs tested.

The trade-offs

It isn't free, and the paper is upfront about where it costs.

Peak memory during a merge is CRDT-sized. While merging, Eg-walker's peak memory is roughly comparable to a CRDT's steady state. It's only cheap between merges.

Heavily concurrent histories gain little. On traces with constant concurrency, merge time was similar to their reference CRDT, because there are few critical versions to exploit. One trace had none at all.

Traversal order matters. On highly concurrent histories, a poorly chosen topological order made merging up to 8 times slower. The real implementation uses a heuristic to avoid that.

The worst case is O(n² log n). The authors note it's unlikely in real editing histories, but it exists.

You still store history. The event graph must be kept as long as concurrent edits might still arrive. It compresses well, but it's a cost.

It's plain text, for now. The paper covers plain text only, and the authors believe the approach can extend to rich text and other formats. That's not trivial: the team behind the Loro library, which draws on Eg-walker's ideas, has written that the original Peritext rich-text algorithm couldn't be used on top of it directly.

Why it matters

For years, the practical advice was: if you want lightweight, fast-loading documents, use OT and a central server. If you want offline editing and peer-to-peer sync, use a CRDT and pay for it in memory.

Eg-walker suggests that was a false choice. Keep the immutable history, keep the document as plain text, and build the CRDT only for the moment you actually need it.

If you want to dig deeper, the authors' production Rust implementation lives in Diamond Types, and there's a TypeScript reference implementation written for readability. The paper itself is very readable too.

I'm curious whether anyone here has run into the OT vs. CRDT trade-off in production. Which side did you pick, and would something like this have changed your decision?