Architecture
Typing together without CRDTs
In this post
Everything in Milieu is live. Move a to-do to another project, and it moves in your other tabs too. Tick something off on your phone, and it’s ticked on your laptop. In a shared project, everyone else sees your changes moments later. You never need to refresh.
Most changes are easy to share like this, because they replace one value with another. A to-do is either done or not done. It belongs to one project or another. When two people change the same thing, the server applies their changes in the order they arrive, and the sync engine brings every device into agreement. Our previous post, From the server to SQLite to reactive Svelte state, explains how that engine works.
Text is harder. A contact’s phone number can be one value, saved when you leave the field. But if a note worked like that, whoever saved last would win, and everyone else’s words would vanish. Typing is a stream of small changes, and two people can be in the middle of the same sentence at once.
So in notes, to-dos and project descriptions, several people can type at once. You see each other’s carets and typing as it happens, and nothing anyone types is lost, even offline. There’s no CRDT behind it, and no operational transformation. Instead, Milieu follows Matthew Weidner’s approach from Collaborative Text Editing without CRDTs or OT:
- Give every character an id.
- Say where an edit goes using a character’s id, not a position.
- Let a server apply everyone’s edits in the order they arrive.
Weidner’s point is that once a server decides the order, you can skip the hardest part of a text CRDT. Milieu already had that server, so live text works much like the rest of its sync engine.
This post explains how it works and what it costs. The demos run Milieu’s real editor code in this page. Press play to watch them. Halfway down, there are two editors to try for yourself.
Positions don’t survive
Imagine a to-do that says “Buy milk”. Ben selects “milk” and types “bread”. At the same moment, Alice adds “ and eggs” to the end. Both editors send their changes, and Ben’s reaches the server first.
Here’s what happens if each edit says where it goes by position:
Her edits get to the server at position 8 too. Everyone agrees on “Buy brea and eggsd”, which nobody typed.
All 6 steps
- Alice and Ben both have “Buy milk”, its characters known only by where they are.
- Ben replaces “milk” with “bread” while Alice types “and eggs” at the end, position 8.
- Both editors send their edits. Ben’s gets to the server first.
- The server applies Ben’s edits. “milk” is gone, and the text is a letter longer.
- Alice’s editor takes version 1 and applies her edits again on top, at position 8: inside “bread”.
- Her edits get to the server at position 8 too. Everyone agrees on “Buy brea and eggsd”, which nobody typed.
Alice meant to type after the “k” in “milk”. Her editor sent “insert at position 8”, but by the time that edit arrived, position 8 was inside “bread”.
Every collaborative text editor has to solve this problem. Operational transformation keeps positions, but adjusts each incoming edit to account for the edits it raced. Here, Alice’s insert at 8 would become an insert at 9, because Ben’s edit made the text one character longer. That needs rules for every pair of edit types, and those rules are notoriously hard to get right.
CRDTs give each character an identity instead. They also need an ordering rule, so that every copy puts simultaneous insertions in the same order, even when edits arrive in different orders and there’s no server. That ordering rule is the intricate part. With a server, the server’s order is enough, so you can leave the rule out. Weidner’s article makes this argument in detail.
Every character has a name
In Milieu, each character’s id has two parts. The bunch is a random name for one person’s typing in one text, and the counter goes up as they type. So letters typed in a row get ids like k3x9:0, k3x9:1 and k3x9:2. Milieu stores runs of ids rather than one id per character. The idea, and the name “bunch”, come from Weidner’s Articulated library.
Text that existed before anyone edited it live gets ids from its position in the original text: bunch 0, counting from the start. Every browser and server process works these ids out the same way, so they don’t need to be stored. A to-do’s title stays as plain text until someone edits it live.
Here’s Alice typing, deleting and undoing, and the ids and edits each step makes:
- delete alice:2
- delete alice:1
- delete alice:0
- restore alice:0–3
Undo brings back those same characters, with their ids, rather than typing new ones.
All 4 steps
- “Buy milk” was written before anyone edited it live, so its ids are bunch 0, counted from the start.
- Alice types “oat ”. Each letter gets the next id in her bunch, and goes after the one before.
- She deletes it. Its characters stay, marked deleted.
- Undo brings back those same characters, with their ids, rather than typing new ones.
Edits only refer to characters by id. There are five kinds. Here’s the type from src/lib/editor/text.ts, without mentions:
type Edit =
| {
kind: 'insert';
after: Id | null; // the character it goes after, or null for the start
id: Id; // the first new character's id; the rest count on from it
text: string;
marks?: Mark[];
style?: Style;
}
| { kind: 'delete'; ids: Ids[] }
| { kind: 'restore'; ids: Ids[] }
| { kind: 'format'; ids: Ids[]; mark: Mark; on: boolean }
| { kind: 'style'; at: Id | null; style: Style };
- Insert adds text after a character, or at the start.
- Delete marks characters as deleted.
- Restore brings deleted characters back. Undo uses this.
- Format turns bold or italic on or off.
- Style turns a paragraph into a heading, a list item or a checklist item.
Here’s Alice’s edit from the race:
{
"kind": "insert",
"after": { "bunch": "0", "counter": 7 },
"id": { "bunch": "alice", "counter": 0 },
"text": " and eggs"
}
“After 0:7” means after the “k” in “milk”, wherever that character has moved. (Real bunches are random, like k3x9. We’ve called hers alice.)
The server’s order is the truth
The server applies each batch of edits as it arrives, in its own database transaction. Each batch creates a new version of the text. SQLite lets only one transaction write at a time, so however many requests arrive at once, the batches go in one order, and that order decides what the text says.
Applying an insert is simple. Here’s a simplified version of the code in Text.apply:
if (this.has(edit.id)) return; // already applied
const at = edit.after ? this.#find(edit.after) + 1 : 0;
this.#chars.splice(at, 0, ...chars(edit.id, edit.text));
An insert goes straight after the character it names. So if two people insert after the same character, the second insert to arrive ends up closer to that character, before the first:
Ben’s arrives second and also goes straight after 0:3, so before Alice’s.
All 4 steps
- Alice and Ben both have their caret after the space, 0:3.
- At the same moment, Alice types “oat” and Ben types “fresh”.
- Both send. Alice’s gets there first, and goes straight after 0:3.
- Ben’s arrives second and also goes straight after 0:3, so before Alice’s.
The order is arbitrary, but it’s the same everywhere. Every copy applies the edits in the server’s order, so every copy ends up the same.
Words don’t get mixed together. When Alice types “oat”, the “a” goes after her “o”, and the “t” goes after her “a”. Even if her keystrokes and Ben’s arrive mixed up, her letters stay together and so do his. That holds for typing forwards; someone typing backwards, putting each letter before the last, could still end up interleaved with someone else doing the same. A property test checks this with random typing from several people.
Applying the same edit twice does nothing. If the text already has an inserted character’s id, the insert is skipped. Deleting a deleted character or restoring a visible one also does nothing. So if a connection drops and a batch is sent again, the second copy doesn’t change the text or its version.
Deleted characters stay
Back in the race, Ben deleted “milk”, but Alice’s edit still points to 0:7, the “k”. If Milieu removed deleted characters, the server wouldn’t know where to put her words.
So Milieu keeps deleted characters and marks them as deleted. They aren’t shown, but edits can still refer to them.
Keeping them makes texts grow. Every hour, the server looks for texts that nobody has open and nobody has edited for 30 days. It removes their deleted characters, and saves the result only if the text still reads the same, with the same ids, formatting and paragraph styles.
It waits that long because any text, a to-do’s title as much as a note, may be edited on a device that’s offline for days. If an edit refers to a character that has been removed, the server can’t place it, so it refuses the edit. A text also can’t store more than four times the longest it may be, counting deleted characters, and edits that would go past that are refused until it’s tidied.
Rebasing in the browser
If the editor waited for the server before showing each keystroke, typing would feel slow. Instead, your editor shows your edits immediately and keeps them on top of the server’s text until the server confirms them.
Each editor remembers the last version it received from the server and the edits it has made since. It sends one batch at a time. While a batch is on its way, new edits queue behind it, though you see them straight away. When the server answers, the queued edits go as the next batch.
When the server sends a new version with someone else’s changes, the editor starts from that version and applies its own unconfirmed edits again, in order. This is the method from src/lib/editor/live.svelte.ts:
#rebuild() {
const text = this.#confirmed.clone();
const answered = this.#answered.flatMap((batch) => batch.edits);
for (const edit of [...answered, ...(this.#sent ?? []), ...this.#waiting]) {
try {
text.apply(edit);
} catch {
// Refers to text the server doesn't have yet, as when an edit
// arrives out of order, and comes right with the next copy.
}
}
this.text = text;
// …and a caret after a character someone has deleted moves back.
}
answered holds batches the server has accepted but hasn’t yet included in a version, because the answer and the new version travel separately. The empty catch loses nothing: an edit that can’t be placed yet stays in the editor’s lists and is applied again with the next version. Each edit is applied by id, so it lands in the same place in the new version. If the new version already includes an edit, applying it does nothing.
Here’s the same race, by id. Deleted characters are struck through. Watch Alice’s editor get version 1 while her own edits are still on their way:
Her edits get to the server and land after 0:7 there too: “Buy bread and eggs”.
All 6 steps
- Every character has an id. “Buy milk” is 0:0 to 0:7.
- Ben replaces “milk” with “bread” while Alice types “and eggs” after 0:7, the “k”.
- Both editors send their edits. Ben’s gets to the server first.
- The server marks “milk” deleted but keeps it, so 0:7 is still there. That’s version 1.
- Alice’s editor takes version 1 and applies her edits again on top, after 0:7.
- Her edits get to the server and land after 0:7 there too: “Buy bread and eggs”.
Milieu’s sync engine works the same way for rows, as the previous post describes in Replaying your pending changes: it keeps the server’s state, puts your pending changes on top, and recalculates when the server’s state changes. For text, recalculating just means applying a few edits by id. None of them needs adjusting, because each names the character it goes after.
Now try two real editors. Each field below runs Milieu’s editor code and talks to a stand-in server. You can make the connection as slow as you like:
Set the delay to a couple of seconds and type in both. Each person sees their own typing immediately and the other person’s typing later. Both always end up matching the server.
Carets are ids too
Milieu keeps a caret’s position as the id of the character before it, or as the start of the text. If Ben types before Alice’s caret, her caret stays after the same character, even though that character has moved. If her caret were stored as a number, Ben’s typing would shift the text, and Alice would end up typing in the middle of his word.
Two cases need special handling. If someone deletes the character a caret follows, the caret moves back to the nearest visible character. Otherwise, the next thing typed could appear in the wrong place.
If someone types exactly where your caret is, their text goes straight after the character your caret follows, so it appears to the right of your caret. Yours stays where you left it, and theirs moves along with their typing.
Other people’s carets are sent separately from their typing. While a caret moves, Milieu sends its position at most ten times a second, and once every ten seconds while it’s still. This means someone’s typing can arrive before their new caret position. So each caret position includes its owner’s bunch and how far their counter had got when it was sent, and Milieu draws the caret after any typing that has arrived since. Their caret never trails behind their own words.
Here’s Ben editing around Alice’s caret. The dashed mark is where a caret kept as a number would be:
Ben deletes “Sam”. Alice’s caret moves back to the nearest visible character before it.
All 4 steps
- Alice’s caret is after “Sam”, the id of the “m”.
- Ben types “Today: ” at the start.
- When it reaches Alice, her caret stays after “Sam”. Kept as the number 7, it would now sit before “Ask”.
- Ben deletes “Sam”. Alice’s caret moves back to the nearest visible character before it.
Offline, and on the device
The editor doesn’t talk to the server directly. Milieu keeps your account in a database on your device, and each batch goes there first, as an editText operation. The device applies its edits to its own copy of the text, exactly as the server will, and queues the operation in a change to send.
While a change is waiting to be sent, Milieu adds new operations to it, up to a hundred. So a minute of typing is one change rather than hundreds. Each batch stays its own operation inside that change, so the device counts versions exactly as the server does.
Without a connection, you can keep typing. The device keeps applying your edits, and the change waits.
When the connection returns, the device sends the change and fetches what changed on the server. Then it does what it does for every other change: it removes its predictions, applies the server’s rows, and runs the pending operations again. For text, that means applying your edits by id to the server’s newer text. Other people’s changes are already there, and yours land where you typed them. Try this in the two editors above: disconnect Alice, type in both, then connect her again.
If the server refuses a change, your typing isn’t thrown away. That can happen if you were offline for so long that a character your edit refers to was tidied away. The device keeps the refused change in Settings → Unsaved, where you can send it again or discard it.
Undo is your own
Text needs its own undo, because the app’s usual undo puts rows back as they were. That works for moving a to-do, but putting a text’s row back would undo everyone’s typing in it. So typing is never part of the app’s undo history, and the editor undoes it with edits instead.
Each editor keeps an undo history of its own edits. Undo never removes someone else’s typing, even if their words are between yours.
Ids make this possible. Undoing typing deletes the characters you typed. Undoing a deletion restores the characters you deleted, but only the ones that were visible when you deleted them, so it can’t bring back something someone else deleted first. Undoing formatting only changes the characters you formatted.
Redo restores the same characters, with the same ids, instead of typing them again. That way, anything someone typed after them while they were deleted still has the right place to go.
Typing undoes in groups. Keystrokes within a second of each other, and within five seconds of the first, undo together. A new line undoes separately.
Formatting, mentions and Markdown
Formatting is stored per character, by id. Bold and italic are marks on characters. A paragraph’s style belongs to the line break before it. When you type, the new text takes the formatting of the character before it, and the insert includes that formatting. So formatting stays with the text it was applied to, even as others type around it.
Weidner suggests storing formatting as spans between two ids, and points to Peritext for how those spans should behave. Per-character marks are simpler to apply and undo by id. Neighbouring characters with the same marks are stored together, so they don’t cost much. The trade-off is that a simultaneous insert keeps the formatting its author saw, even if it lands inside a different span. If Ben makes a sentence bold while Alice types into the middle of it, her words stay plain.
A mention of a person or a project is one character, U+FFFC, with its link and the name it had when it was mentioned. You insert, delete and undo it like any other character.
The server also keeps a plain copy of each text, so lists, search and assistants can read it without understanding ids. Titles are plain text, and notes are Markdown. When an assistant changes a note, it sends Markdown, and the server turns the difference into edits. Only the paragraphs that changed are edited. Anyone with the note open sees the change arrive like someone else’s typing, and their own typing elsewhere in the note is left alone.
What it costs
A server has to decide. Two offline devices can’t merge their edits with each other. Each keeps its own predictions until the server puts the edits in order. That suits Milieu, because the server already decides every change, and devices keep working on their own in the meantime. A peer-to-peer app would need a CRDT.
Deleted characters accumulate. They stay until the text is tidied, and that only happens when nobody has the text open. Every text keeps them for 30 days after its last edit. A text that’s always open somewhere isn’t tidied at all.
Devices receive whole texts, not edits. Edits go up to the server, but other devices receive the whole text with their next sync, because Milieu syncs rows. For a long note, that sends more data than the edits alone.
Finding positions means walking the text. To find where a caret is, or which character is at a position, the editor walks through the characters. On a note of about 50,000 characters, the longest Milieu allows, with a thousand deleted ones kept beside them, making and applying one keystroke’s edit takes about 6 milliseconds on a recent Mac. That’s fine for to-dos and titles, but worth improving for long notes on slower phones.
Edits merge; intentions don’t. Suppose Alice changes “Sam” to “Samuel” at the same time as Ben changes it to “Sammy”. Both deletions succeed, and both insertions land after the space, so if Ben’s arrives second, the text reads “Ask SammySamuel about the venue”. A CRDT would keep both words too. Nothing at this level knows what either person meant, but both can see the result and fix it.
Three small ideas
Give every character a name, let the server decide the order, and keep what’s deleted. Rebasing, carets, undo and working offline all follow from those three choices, and they run on the same engine as the rest of Milieu. There’s no CRDT, and no transformation: just edits that say exactly where they mean.