Why pressing Enter makes Notion's CRDT harder

// the short version

Two people edit the same sentence. One presses Enter. Where should the other's new word go?

// what to take away

• Stable character IDs and tombstones let concurrent edits retain their anchors, even when characters are deleted.
• Movable slices preserve their original text-instance identity when a sentence is split across blocks.
• Search labels record split history so prefix queries can find moved text without loading every candidate block.

// transcript

Your teammate's typing could erase your work in Notion. Until twenty twenty-five, concurrent edits to the same block could overwrite each other. Under last-write-wins, the latest arrival replaced the block, even if yours contained different changes. Working offline would make that collision possible long after you finished typing. Notion replaced that with a CRDT, a data structure that merges concurrent edits. Each character has a stable ID, so insertions reference the character they follow. A Lamport clock orders competing insertions, with session IDs breaking ties. Even deleted characters leave markers called tombstones, because an edit arriving later might still point to one of them. But those pointers face another problem when someone presses Enter. Emma splits a sentence into two blocks while Charlie adds a word at the end. His word belongs with the text that moved, although he edited the original block. So Notion divides text into slices that can move between blocks, while keeping their original text instance, an identity shared by slices from the same source. An instance-to-block mapping tracks their locations, letting Charlie's edit find its destination. That mapping can become expensive. Split the original block ninety-nine times, and adding one character could require fetching a hundred blocks. Knowing where the text started isn't enough to find it cheaply. Each split therefore extends its slices' search labels with left or right. Splitting the right slice again creates right-left and right-right. An edit includes the label its author knew, narrowing the blocks to search. A prefix search includes descendants of that label, so an edit aimed at the right piece can still find text that's since been split again. Notion now processes millions of these operations every minute. The result won't always capture exactly what each writer intended, but in our split sentence, Charlie's word follows the text. Emma can press Enter without leaving his contribution behind.