Collaborative Text Editing

without CRDTs or OT

Matthew Weidner

Local-First Conf 2025

Berlin

This Talk: Simple Collaborative Text Editing

About Me

Common Curriculum dev (2024-)

• In-house sync engine (~2014): �event sourcing over MongoDB

CMU PhD student (2019-)

• Goal: FOSS collaborative software
• Blog about CRDTs etc. at mattweidner.com

What Now?

My experience: CRDTs are fun, but hard to use in practice!

• (Correct) algorithms are nontrivial
• Limits the ops that users can perform
• CRDT libraries are constraining

I now prefer “server reconciliation” (à la Replicache/Zero & FPS games) – a fully general, DIY-able alternative.

But I thought collaborative text editing still needed fancy algorithms…

Until I saw an intriguing comment from Wim Cools (@wcools) about how the Thymer IDE works.

The Approach

Typing in a doc: Tell the server, “I want to insert some text here”.

Here is not at index 9 any more!

The brown fox

{

op: “insert”,

text: “ fox”,

at: ???

}

{

op: “insert”,

text: “ fox”,

at: 9 // index

}

❌

Typing in a doc: Tell the server, “I want to insert some text here”.

Here is defined relative to a char, labeled w/ a UUID.

We “insert after” that char.

The brown fox

{

op: “insert”,

text: “fox”,

at: ???

}

{

op: “insert”,

text: “ fox”,

after: “207c35d3…”,

ids: [“b65bb6d2-…]

}

The quick brown fox

insert “ quick”

207c35d3-…

207c35d3-…

🧓️

😎

What we need

A local data structure that:

• Assigns a UUID to each char
• Can convert UUID <-> array index

• Remembers deleted chars’ UUIDs

{

char: “T”,

id: “8e82e5b3…”,

​

}

{

char: “h”,

id: “97f9a58b…”,

​

}

{

id: “591f0a08…”,

isDeleted: true,

}

,

,

, …

Optimized & persistent version:

Articulated on npm

Doable in ~250 LoC. Try it yourself!

, …

Updating clients?

UUIDs + “insert after” tell the server where to insert new chars.�But what about other clients, who might be ahead of the server’s state?

Now we need CRDTs/OT, right?�Nope! Server reconciliation works here, as usual.

Op R

Advantages

Can DIY instead of relying on someone else’s CRDT/OT lib.

Then add special features that your app needs:

1. Fancier ops (“change word …”)
2. Partial/lazy loading for large docs
3. Suggested changes

…

Server-Optional?

Decentralized Collaboration

Non-server reconciliation:�All clients (eventually) agree on a total order of operations, instead of using a server’s receipt order.

Non-server reconciliation + “insert after <id>” ops�→ decentralized collaborative text editing!

Decentralized Collaboration cont.

Q: Isn’t this a CRDT?�A: Yes, “non”-server reconciliation always is. See OpSets.

Q: So this particular choice of ops defines a text editing CRDT?�A: Yes! Order “insert after” ops by Lamport timestamps:

Q: What if we add formatting ops? E.g., “bold the text from here to there.”�A: With a server (+ server reconciliation), it’s nothing fancy.�In the decentralized case w/ Lamport timestamps:

≈ Causal Trees / RGA

≈ Peritext

Non-server reconciliation + “insert after <id>” ops�→ decentralized collaborative text editing!

Decentralized Collaboration cont.

Lamport timestamp order does weird things to offline work:

What if we instead stack the branches, like git rebase?

Used with our “insert after” strategy, this gives another text CRDT:

≈ Fugue!

🤔

😎

Non-server reconciliation + “insert after <id>” ops�→ decentralized collaborative text editing!

Recap

Recap

Collaborative text editing in three steps:

1. Assign a UUID to each char (and remember it after deleting).
2. Tell the server: “insert after here”, where here is a UUID.
3. Use server reconciliation to update other clients.

Articulated on npm

Bonus quests:

• Add detail to your ops to get fancy semantics, formatting, etc.
• Use “non-server reconciliation” to make it decentralized.

Backup Slides

Bibliography

• Overall approach: I have not found a definitive source, but I learned of the idea from Wim Cools (Thymer) on HNews. I would not be surprised if others have used it in practice. Ex: Jazz’s CoList
• Server reconciliation: How Replicache Works (Rocicorp); Wikipedia
• “Non-server reconciliation”: OpSets (Kleppmann, Gomes, Mulligan, & Beresford 2018); A Framework for Convergence (Wonlaw 2023)
• Text CRDTs referenced: Causal Trees / RGA (Grishchenko 2010); Peritext (Litt, Lim, Kleppmann, & van Hardenberg 2021); Fugue (Weidner & Kleppmann 2023)

General Lists

Besides text, the “insert after” (or “insert before”) approach is useful in many GUI lists where insert, delete, & move are the primary ops.

1. Ingredients list in a recipe
2. Powerpoint filmstrip
3. Spreadsheet rows, columns

E.g. spreadsheet formula refs (“3C”): if you store row & column UUIDs instead of “3” and “C”, the formula will adjust automatically when row 2 is deleted.

Why Articulated?

Articulated omits the chars (you store them in ProseMirror etc.) and is a persistent data structure (for easy server reconciliation) but is otherwise API-equivalent.

However, it adds nontrivial rope-like optimizations:

• B+Tree instead of array, for O(log^2(n)) ops & queries.
• Sequential LtR insertions (common case) are stored as single nodes.
• IDs have the form { UUID, counter } instead of just UUID.

Goal: Store a map from UUIDs to chars, w/ ops to insert & delete.

Simple impl is�Array<{ char, UUID, isDeleted }>.

Equivalence with Causal Trees / RGA

• Each tree node (char) has a unique ID
• Parent: left origin - preceding char at time of insertion
• So edges = “insert after” relations!
• Siblings in reverse Lamport timestamp order - for RtL insertions or concurrency
• Same result as applying “insert after” ops in Lamport timestamp order!

A

B

C

X

Y

Z

A -> AB -> ABC -> ABCZ -> ABCYZ -> ABCXYZ

Equivalence with Fugue

• Fugue: Same as RGA, but siblings are sorted by another tree - like RGA in reverse
• I.e. apply “insert after” ops in the backwards tree’s (forwards) order
• Sorting ops in tree traversal order ≈ stacking branches!

A

B

C

X

ABCzyZYX

Y

Z

y

z

All “inserted after” C