Daemon fix: store what changed, not what was asked
Seed PR #1375. Written 2026-11-17. Part of the work on the task Some document updates are expensive.
The problem in one paragraph
When a client edits a document through the daemon (PrepareChange, used by the web app, and CreateDocumentChange, used by the desktop app), the daemon applies the requested block moves in memory and then writes a Change that other peers replay. It wrote that Change by walking the moves it was asked to make. That walk had three faults: it dropped moves it judged redundant without re-anchoring the move that came next, it visited some levels of the tree more than once, and on certain histories it never stopped. So a correct request could be stored as a wrong, bloated, or never-finished Change.
What a user sees
Blocks land in the wrong place. Re-send a level and insert a block after the first one: the new block is stored in front of the first one. Reorder [a, b, c, d] to [a, c, d, b]: it reads back [a, c, b, d].
Changes grow without reason. On nested documents with reorder history, one move is stored many times. On a real document, inserting one child was stored as 1,206,055 moves in a 61.5 MB Change, which cannot be published.
The request never returns. If a document's history ever had block A under B and later B under A (outdent, then indent the other way), the daemon's walk goes round forever and holds a CPU until restart.
A cleared and re-set metadata map disappears. The unchanged entries are skipped and only the clear is stored.
These are in the daemon that is deployed today. Any client of PrepareChange can hit them.
Why it happened
A stored move says "put block X after block Y". Y is named by the position Y was given when Y was last placed.
A dropped move left a dangling anchor. Inside one request, the daemon treated "move the first block to the start" as a real move, then dropped it when writing the Change because the block ended where it began. The next move in the request was anchored on the dropped move's position, which nobody else ever sees. Peers place that block at the start instead.
"Same left neighbour" was taken to mean "did not move". A block that still follows the same block as before was dropped, even when that neighbour itself had moved.
Stale entries were walked. Every past position of a block stays in the list as a tombstone. The walk queued the children of every entry, tombstones included, with no record of what it had already visited. A level under a block with many past positions was written once per past position, and a parent/child inversion in history became a loop.
Attribute writes were compared with the stored document only. A write equal to the stored value was skipped even when an earlier write in the same request had just cleared its parent.
The fix
The daemon no longer writes down the moves it was asked to make. It compares each level before and after the request and writes the difference.
Keep the longest run. For each level, find the largest set of blocks that are already in the right relative order. Those blocks are not mentioned in the Change.
Move the rest, once each. Every other block gets exactly one move, anchored on the block that precedes it in the final order, at that block's settled position: its original position if it stays, or the move just written if it moved too.
Visit each level once, parents before children. Tombstones and superseded positions are not walked, so nothing is written twice and the walk always ends. A move under a block is always stored after the move that puts that block in place.
Attributes account for the rest of the request. A write removes pending writes below it, and is kept when a pending write above it would otherwise wipe it out.
Two smaller fixes ride along: a block written after the first move of a request can be used as a parent, and "move the first block to the start" is recognised as no move at all.
Nothing changes in how Changes are encoded or read. Peers running an older daemon read the new Changes the same way.
flowchart LR
A[Request: list of moves] --> B[Apply in memory]
B --> C{Old: replay the request}
C --> D[Drop some moves, repeat others]
D --> E[Stored Change may differ from the result]
B --> F{New: compare before and after}
F --> G[Keep longest in-order run]
G --> H[One move per remaining block, anchored on its settled predecessor]
H --> I[Stored Change equals the result]Behaviour to know about
The stored move may name a different block than the one the user dragged. Moving a from the front of [a, b, c, d] to the end and moving b, c, d in front of a are the same result; the daemon stores the single move of a.
Deletes are no longer always the last operations in a Change: a move under a deleted block is stored after its delete.
Evidence
Shapes. 37 named move shapes and 20 attribute cases, each checked by reloading the stored Change from its encoded bytes. 20 of the 37 fail on the old code.
Random histories. 20,000 seeds each for tree and attribute tests, with concurrent branches merged and then edited, up to 40 operations per Change.
Real documents. 10,332 documents from two local daemon databases (about 41,900 changes and 420,000 blocks), plus 16,153 earlier states of their histories:
Check | New code | Old code |
|---|---|---|
Re-send a whole document unchanged | 0 operations stored, all 10,114 | 4 documents time out |
Single edits | 49,767 moves stored where 49,767 expected; largest Change 832 bytes | 7,404 documents store duplicated moves |
Re-send a level and insert after the first block | correct on every document | wrong tree on every document that has blocks |
Clear a metadata map and set the same entries | nothing stored | map lost on 112 of 112 |
Slowest commit | 89 ms | 3 documents never finish |
What was not tested
The gRPC handler itself: the replay applied requests to the document model directly.
Readers other than the Go one.
Request shapes beyond the ones listed in the PR.
Do you like what you are reading? Subscribe to receive updates.
Unsubscribe anytime