CRDTs for Collaborative Text Editing
Matthew Weidner
CMU PLunch 2/25/22
Goal: Collaborative (Plain) Text Editing
Google Docs minus formatting.
Challenge: Availability + Consistency
My typing should show up instantly (no network round trips).
But this creates concurrency.
Need to end up in consistent state (Strong Eventual Consistency).
The cat jumped on table.
The cat jumped on the table.
The gray cat jumped on table.
The gray cat jumped on the table.
The gray cat jumped on the table.
Strawman: Broadcast Indices
Problem???
When you change the text, broadcast your changes & their index.
Other users apply the same changes at same index.
The cat jumped on table.
The cat jumped on the table.
Broadcast “Insert ‘ the’ at index 17”.
The cat jumped on table.
The cat jumped on the table.
Strawman: Broadcast Indices
Indices move around during concurrent edits.
If you don’t correct for this, result would be inconsistent & not what users expect.
The cat jumped on table.
The cat jumped on the table.
The gray cat jumped on table.
The gray cat jumped on the table.
The gray cat jumped on the table.
Index 17
Index 22
One Solution: “Operational Transformation”
“Transform” indices in received ops, to account for concurrent ops you already performed.
Transform “Insert ‘ the’ at 17” by “Insert ‘ gray’ at 3”: Add 5 to index -> 22.
The cat jumped on table.
The cat jumped on the table.
The gray cat jumped on table.
The gray cat jumped on the table.
The gray cat jumped on the table.
Index 17
Index 22
One Solution: “Operational Transformation”
Define transformations for all pairs of ops (insert/insert, insert/delete, delete/delete, …).
Must satisfy algebraic properties.
Then use an OT algorithm to apply changes.
“An Integrating, Transformation-Oriented Approach to Concurrency Control and Undo in Group Editors” by Ressel, Nitsche-Ruhland, & Gunzenhäuser.
Operational Transformation: Problems
Checking algebraic properties: combinatorial explosion.
Alg is slow in face of many conflicts.
In practice: central server + no offline mode (e.g. Google Docs).
Conflict-free Replicated Data Types (CRDTs)
Conflict-free Replicated Data Types (CRDTs)
Forget about indices, transformation properties, …
Add extra metadata to data structure & network messages so you can process all ops “directly”, w/o explicitly considering past ops.
In other words: no conflicts between concurrent ops.
I’ll focus on one text/list CRDT (“Double RGA”); many others, plus CRDTs for other data types.
CRDT Basics
Instead of using indices, assign each char a unique immutable position.
Positions are totally ordered and dense:�If p < q, can create new r such that p < r < q.
Assign r to char inserted between p & q.
｢ T a b l e ｣
0
0.5
0.875
0.75
0.25
0.9375
1
CRDT Basics
In case of concurrent edits: sort positions as usual.
The cat jumped on table.
The cat jumped on the table.
The gray cat jumped on table.
The gray cat jumped on the table.
The gray cat jumped on the table.
.7
.8
“Insert ‘ the’ at 0.75”
.15
.25
“Insert ‘ gray’ at 0.2”
Issue 1: Real numbers aren’t real (for computers).
Floats only get 53 bits of precision.
T y p i n g f r o m l e f t t o r i g h t
0.1
0.11
0.111
0.1111
0.11111
0.111111
0.1111111
. . .
Issue 1: Real numbers aren’t real (for computers).
Arbitrary-precision floats
Represent as binary tree.
0.10001
1
1
0
0
0
CRDT Attempt 2
Order: Tree walk.
Insert: Assign char a path between its neighbors.�Broadcast char & path.
I
t
r
o
d
u
c
n
Introduc
Issue 2: Concurrent insertions at same position (path).
Sort arbitrarily (e.g. by sender).
But what if someone types in between?
Two
Three
people
typing
^
Four
CRDT Attempt 3 (Working)
Distinguish nodes w/ same parent and side by UID.
Order is still a tree walk: L children, node, R children.
Sort same-side children by UID.
(“alice”, 1)
(“bob”, 2)
(“bob”, 1)
(“bob”, 3)
a
b
c
d
CRDT Attempt 3 (Working)
Insert: Assign char a new node between its neighbors.
e
(“alice”, 1)
(“bob”, 2)
(“bob”, 1)
(“bob”, 3)
Broadcast (char, new UID, parent UID, side).
(“alice”, 2)
b
c
d
a
aebcd
CRDT Attempt 3 (Working)
Insert: Assign char a new node between its neighbors.
e
(“alice”, 1)
(“bob”, 2)
(“bob”, 1)
(“bob”, 3)
(“alice”, 2)
b
c
d
a
afebcd
(“dave”, 1)
f
Broadcast (char, new UID, parent UID, side).
CRDT Attempt 3 (Working)
Delete: Mark the node as deleted.
I.e., broadcast (“delete”, node’s UID).
(Need to keep the node around in case someone uses it as a parent concurrently.)
Text CRDT: Summary
Tree w/ left & right children.
Each node has UID (sender, counter).
Order: tree walk (UID as tiebreaker).
Insert: Assign char a new node between its neighbors. Broadcast (char, new UID, parent UID, side).
Delete: Mark the node as deleted. I.e., broadcast (“delete”, node’s UID).
afebcd
Further Topics
Text CRDTs, Plural
Numerous algs since 2008. See https://crdt.tech/papers.html.
All use “unique immutable positions”. Most use trees.
This alg: appears novel, but very similar to others.
Interleaving Anomalies
“Interleaving anomalies in collaborative text editors” by Kleppmann et al.
Interleaving Anomalies
Using hypothetical real-number CRDT (not the tree alg I described):
“Interleaving anomalies in collaborative text editors” by Kleppmann et al.
Interleaving Anomalies
Luckily, our text CRDT avoids interleaving:
In general, contiguous insertions by one user end up in a new subtree.
-> Not interleaved with other new subtrees.
In particular, concurrent LtR / RtL insertions not interleaved*.
l
o
A
l
i
C
h
a
*To the extent permitted by law.
Memory Usage
Easily 100 bytes per node, including deleted nodes.
Times 100,000 chars + 100,000 deletions (e.g. 14 page LaTeX doc): 20 MB. GC-intensive.
Vs 0.1 MB for non-CRDT.
Can get much worse…
Memory Usage
How to reduce memory usage?
Memory Usage: Common Case Opts
Most text comes in LtR chunks typed by a single user.
“Compress” these as pair�(first UID, chunk of text).
NB: Theory/alg is the same; just changing how code reps it.
Good enough in practice (x 10).
l
o
A
l
i
C
h
a
Memory Usage: Eliminate Deleted Nodes?
Important for docs with long edit history.
If you type 100k chars and delete them all, it’s surprising to see memory usage not decrease.
Tombstone: permanent record of deleted thing. Common criticism of CRDTs.
Node (“alice”, 7) with parent (“bob”, 3)
Memory Usage: Eliminate Deleted Nodes?
Why do we need to remember deleted nodes?
Need to remember “ the” and “ gray”’s paths in the tree, so that we can sort them. But these paths are made of deleted nodes.
The cat jumped on table.
The cat jumped on the table.
The gray cat jumped on table.
gray the
gray the
gray the
Memory Usage: Eliminate Deleted Nodes?
Need to remember “ the” and “ gray”’s paths in the tree, so that we can sort them. But these paths are made of deleted nodes.
Idea: On insert, instead of sending just the node’s parent, send its whole path to the root.
Issue: Now network message size is prop. to path length.
But long paths are the common case (LtR insertions)...
Trying to avoid this leads to interleaving anomalies.
Memory Usage: Eliminate Deleted Nodes?
Also:
Theorem (Attiya et al. 2016).�For any “reasonable” text CRDT, for any # of deleted chars D, there is an execution in which some user’s state is one char long (i.e., only one non-deleted element) but they use memory 𝛺(D).
“Specification and Complexity of Collaborative Text Editing” by Attiya et al.
Memory Usage: Takeaways
Compressing LtR chunks (common case) works well enough in practice.
Eliminating tombstones increases network usage and is theoretically challenging.
Note: Compressing LtR chunks also reduces the # of tombstones, by reducing # of nodes. Or, if you use your CRDT in “no tombstone” mode (sending whole paths each time), compression reduces effective path lengths. So it’s a good idea all around.
Conclusion
Text CRDTs enable collaborative plain text editing.
Not too complicated if you pick the right one: binary-ish tree where each node has a UID.
The text CRDT presented here avoids interleaving anomalies.
Memory usage is a concern, but compressing LtR chunks of text makes it acceptable in practice.
Avoiding tombstones is hard.
Thanks!