Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

Text that merges: sequence CRDTs

After this lesson: I can merge two replicas of a text whose characters carry positions.

70 min lesson2 commandsCRDT lab: local-first sync with counters, sets, vector clocks and text in Python

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

WordWhat it meansExample
Sequence CRDTa CRDT for an ordered list, such as text
Indexa character's place counted from the start0, 1, 2
Character ida name no other character shares(6, 'ben')
Tombstonea deleted character kept as a marker
Interleavingtwo 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

Code: python
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

Command
docker exec jupyter python3 steps/text.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Worked example: what the lab printed

MomentAnaBen
SharedHelloHello
OfflineHello worldOh, ello (H deleted)
After syncOh, ello worldOh, ello world
Storedone tombstone, the Hone 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

Command
docker exec jupyter python3 steps/interleave.py

Shown 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.

About this lab and its source: CRDT lab: local-first sync with counters, sets, vector clocks and text in Python

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.