v5.8.0

Storage and speed work on crdt.Text, plus garbage collection for long-lived replicas.

Performance

A crdt.Text no longer stores one run per keystroke. That is what made a document cost about a hundred bytes per character and made every edit walk the whole thing.

Workload	v5.6.1	v5.7.0	v5.8.0
Type 2,000 characters	3.07 s	239 ms	2 ms
Type 100,000 characters	—	8.1 s	142 ms
Read a 1,000-character document	587 µs	25 µs	0.2 µs
Size of a 100,000-character document	~9.9 MB	~9.9 MB	103 KB

A document now costs about 1.03 bytes per character on the wire, and typing scales roughly linearly with its length.

Three causes, each only visible once the one before it was fixed:

• Identifiers were never adjacent. Clock.Reserve begins a new logical range whenever physical time has moved on — always, by the next keystroke — so two consecutively typed characters had nothing connecting them. Sequence elements now draw from the new Clock.ReserveSequence, which counts on from where it left off. It carries no causality, which a sequence does not need from an identifier: position comes from the element you follow, and the identifier only breaks ties between concurrent insertions.
• Counting runes meant walking the document. Positions are counted in runes, so nearly every operation needed a run's length, and with one long run that is the whole document. Runs now carry their count.
• Joining runs copied them. Appending one character to a long run copies it, so typing stayed quadratic even at one run. Runs are capped, which bounds the copy.

Added

CRDT[T].Compact discards the bookkeeping a replica accumulates. A replica remembers when every path was written and deleted so it can recognize a stale update, and a sequence keeps deleted elements as tombstones so a concurrent insertion still has an anchor — neither shrinks on its own:

After	Visible	Stored
500 map add+delete cycles	0 keys	55.9 KB
200 type+delete cycles	9 characters	201 runs / 21.6 KB

Compaction reclaimed 99% of a long-lived replica's stored state in the new example, with its value unchanged.

Dropping the record is only safe for changes every replica has already seen, so the caller supplies that watermark — only the application knows who its peers are or what they have acknowledged. A replica that has compacted still converges with one that has not. Compact reaches the Text and List values inside a replica and emits no delta, because discarding history does not change what the replica holds.

A tombstone that something is still anchored to is kept whatever its age: removing it would change how this replica orders the document without changing how any other replica orders it.

crdt.Text.Compact and crdt.List[T].Compact do the same for a sequence on its own, and crdt.Compactable lets a type of your own take part.

hlc.Clock.ReserveSequence allocates identifiers for sequence elements, and crdt.TextRun.N carries a run's rune count. Both are additive: Reserve is unchanged and still the right call for a timestamp, and a run without a count — an older document, or a literal built by hand — is counted on demand.

New examples

crdt_compaction, showing what accumulates and the watermark that makes reclaiming it safe.

Full Changelog: v5.7.0...v5.8.0