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
| Word | What it means |
|---|---|
| Compaction | dropping data nobody can need again |
| Stable | seen by every replica |
| Garbage collection | freeing memory that nothing uses |
| Automerge | a CRDT library for JSON-like documents |
| Yjs | a 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
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
docker exec jupyter python3 steps/tombstones.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
Worked example: what the lab printed
| Document | Visible | Tombstones | Dropped by compaction |
|---|---|---|---|
| 200 typed, last 190 deleted | 10 | 190 | 190 |
| 200 typed, first 190 deleted | 10 | 190 | 0 |
The cells students fill in are left blank in this preview.
List what the lab's text CRDT can do
docker exec jupyter grep -n "def " rga.pyShown 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.