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

Free lesson

Tombstones, compaction and real CRDT libraries

After this lesson: I can decide which tombstones every replica has seen and can safely drop.

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

A document heavier than its words

A shared essay has 2,000 words on screen. Behind the scenes it may store every letter ever typed and deleted.

Deleted text is kept so that merges stay safe. This lesson asks when it can go, and how real local-first libraries handle it.

By the end of this lesson

Note

I can decide which tombstones every replica has seen and can safely drop.

Key words

WordWhat it means
Compactiondropping data nobody can need again
Stableseen by every replica
Garbage collectionfreeing memory that nothing uses
Automergea CRDT library for JSON-like documents
Yjsa CRDT library of shared types for editors

The cells students fill in are left blank in this preview.

Why a tombstone stays

In RGA, every character remembers the character it was typed after. If a replica has not yet heard about a delete, it may type after the deleted character.

When that insert arrives, the deleted character must still be there to hang it on. So a tombstone stays until every replica has seen the delete.

Try it: an hour of editing

Code: python
import random

rng = random.Random(3)
stored = 0       # characters ever typed, kept as entries
visible = 0      # characters still in the text

for minute in range(60):        # an hour of editing
    typed = rng.randint(20, 40)
    deleted = min(visible + typed, rng.randint(10, 35))
    stored += typed
    visible += typed - deleted

tombstones = stored - visible
print("visible characters:", visible)
print("stored entries:    ", stored)
print("tombstones:        ", tombstones)
print("share that is tombstones:", round(100 * tombstones / stored), "%")
# Change the deletes to rng.randint(25, 40). What happens to the share?

Two rules for dropping one

Stable: every replica has seen the delete. Take the smallest of each place across all the replicas' vector clocks. A tombstone is stable when its counter is at most that.

Nothing hangs off it: no character kept in the text was typed after it. Otherwise that character would lose its place.

Compact two documents

Command
docker exec jupyter python3 steps/tombstones.py

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

Worked example: what the lab printed

DocumentVisibleTombstonesDropped by compaction
200 typed, last 190 deleted10190190
200 typed, first 190 deleted101900

The cells students fill in are left blank in this preview.

List what the lab's text CRDT can do

Command
docker exec jupyter grep -n "def " rga.py

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

What real libraries add

Automerge treats a document like JSON: maps, lists, text and counters. It keeps the history of changes, so you can see who changed what. Replicas exchange changes with a sync protocol.

Yjs offers shared types, such as text, arrays and maps, built for editors. A replica sends a state vector, a per-replica count much like a vector clock, and receives only the missing updates.

Toy, Automerge and Yjs side by side

Like the lab's rga.py, both libraries give each inserted item an id and keep deleted items so merges stay safe. Yjs can drop the content of deleted text while keeping a small marker.

They differ from the toy in speed and size: compact binary formats, long runs of typing stored together, and tested code. The lab has neither library, because its pinned image carries none, so we compare them in words.

A common mistake

Warning

Many people think a delete frees space at once. In a CRDT a delete usually adds a marker, so the document grows. Space comes back only when compaction can prove every replica has seen the delete.

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.