Two people, one sentence
Two students write a group report in a shared document. One fixes a word at the start while the other adds a sentence at the end, both offline.
Text is the hardest data to merge, because every character has a place, and places move when somebody types.
By the end of this lesson
Note
I can merge two replicas of a text whose characters carry positions.
Key words
| Word | What it means | Example |
|---|---|---|
| Sequence CRDT | a CRDT for an ordered list, such as text | |
| Index | a character's place counted from the start | 0, 1, 2 |
| Character id | a name no other character shares | (6, 'ben') |
| Tombstone | a deleted character kept as a marker | |
| Interleaving | two words typed at once getting mixed up letter by letter |
The cells students fill in are left blank in this preview.
An index means different things
The easy way to send an edit is "insert a at index 0" or "delete index 2". But an index counts from the start of a text that has already changed on the other replica.
If Ana inserts at the start, every later character moves one place. Ben's "delete index 2" now points at a different character.
Try it: two edits by index
def apply(text, edit):
kind, index, char = edit
if kind == "insert":
return text[:index] + char + text[index:]
return text[:index] + text[index + 1:]
start = "cat"
ana = ("insert", 0, "a") # Ana types a at the start: "acat"
ben = ("delete", 2, "") # Ben deletes the t at index 2: "ca"
# Each replica applies its own edit first, then the other one.
on_ana = apply(apply(start, ana), ben)
on_ben = apply(apply(start, ben), ana)
print("Ana sees:", on_ana)
print("Ben sees:", on_ben)
# Which character did Ben mean to delete? Which did Ana's copy delete?
Idea 1: a position between neighbours
Give each character a position number, and sort by it. To type between positions 0.4 and 0.5, pick 0.45. Nothing else moves.
Real systems use a list of whole numbers, such as [4, 5], so there is always room for one more. The replica name breaks a tie. This is the idea behind Logoot.
Idea 2: an id and a parent
RGA gives each character an id, a counter and the replica name, and remembers which character it was typed after. Text is read by walking from the start, newer children first.
A delete only marks the character as a tombstone, because another replica may still type after it. The lab's rga.py works this way.
Merge two edits to one line
docker exec jupyter python3 steps/text.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
Worked example: what the lab printed
| Moment | Ana | Ben |
|---|---|---|
| Shared | Hello | Hello |
| Offline | Hello world | Oh, ello (H deleted) |
| After sync | Oh, ello world | Oh, ello world |
| Stored | one tombstone, the H | one tombstone, the H |
The cells students fill in are left blank in this preview.
When two words get mixed
Ana types "cat" and Ben types "dog" at the same place, at the same time. With positions between neighbours, both pick the same numbers, and the replica name sorts each pair.
The letters alternate. RGA chains each letter to the one before, so each word stays whole.
Watch two words interleave
docker exec jupyter python3 steps/interleave.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
A common mistake
Warning
Many people think that if every replica ends with the same text, the merge is right. "cdaotg" is the same on every replica and nobody typed it. Converging is required, but a good text CRDT also keeps what each person typed together.