Weft, a text that stays one text when nobody is online
Weft is a CRDT for text written from an empty file. Several copies of one text are edited on their own, offline if need be, and every copy ends up as the same text once it has seen every change, whatever order the changes arrive in. Below are three copies joined by a network you can cut. Type in all three, take one offline, keep typing, and bring it back.
Each copy keeps its own text, sends every change to the other two over the network, and applies theirs as they arrive. An offline copy keeps what it sends until it is back. The dots are changes on their way. The line under the copies is the laptop’s text, each character marked by the copy that wrote it.
Every character has a name
A position like “the fifth character” means different things on two copies that have both been edited. So Weft never sends positions. Every character gets an id when it is typed: a counter and the name of the copy that typed it. No two characters anywhere share one. Each change is one of two kinds, “put this character behind that id” or “remove that id”, and an id points to the same character on every copy.
The counter is a Lamport clock. A copy’s next counter is one more than the highest it has seen from anyone, so a character typed after another one was seen always has the higher counter.
The order comes from one rule
When two copies type behind the same character at the same time, both characters are typed into the same spot. Weft puts the one with the higher id first and skips over everything typed behind it. Every copy compares the same ids, so every copy picks the same order, and a word typed on one copy is never split by a word typed on another.
The rule is the whole difference between a CRDT and two texts that drift apart. Press “Leave out the rule” above and every copy inserts right behind the character it was typed behind, in the order the network happens to deliver. The copies stop agreeing within a few words.
Deleted characters stay, unseen
A copy that is offline may still type behind a character another copy has deleted. When that change arrives, the character it names has to be there. So a delete only marks a character as gone: it stays in the order as a tombstone, and the text you read skips it. “Show deleted” above draws them, struck through.
A change can also arrive before the change it depends on, when the network delivers out of order. Weft keeps it aside and tries again after each arrival. A change that arrives twice is recognized by its id and applied once.
Held against chance
A handful of hand-written cases cannot show that every order of arrival ends in the same text. The fuzzer can come closer. Each session starts two to four copies, types and deletes at random, delivers every change to every other copy in a shuffled order, some of them twice, and then checks that every copy reads the same. A seeded generator makes each session repeatable, so a failure can be replayed.
Each dot is a session: violet when every copy agrees, red when they do not.
The same fuzzer runs from the command line, with the rule and without it:
$ node web/notes/weft/fuzz.mjs 20,000 sessions, 2,276,527 operations, with the ordering rule, in 9.2 s every session ended with every copy the same text $ node web/notes/weft/fuzz.mjs --without-rule 20,000 sessions, 2,276,854 operations, without the ordering rule, in 9.1 s 19,871 sessions ended with copies that differ; the first is session 1
Without the rule nearly every session fails. A fuzzer that cannot catch a missing rule would prove nothing when it passes.
What it does not have
Weft is written to understand what a production CRDT does. Zibaldone keeps its documents in Yjs, which also handles rich text, stores a run of typing as one record, and drops the content of deleted text. Weft sends one operation per character, keeps every tombstone and knows only plain text. It does carry the property that matters, and the fuzzer above checks it.
The source is in the portfolio’s repository under web/notes/weft/: weft.js for the CRDT and the fuzzer, fuzz.mjs for the command, weft.test.mjs for the tests.