12 октября 2026Команда Сарнас

Как Notion обеспечивает одновременное редактирование документов с помощью CRDT

Статья разбирает, как Notion удаётся поддерживать совместное редактирование документов без потери правок при конфликтах. На примере CRDT-подхода на основе RGA и Peritext показывается, как устроены идентификаторы символов, порядок вставок и работа с форматированием в условиях распределённой сети.

Notion хранит документы как блоки и позволяет нескольким людям править один документ одновременно. Вопрос в том, что происходит, когда двое меняют один и тот же текст, пока не видят правок друг друга. Разобрать это нетривиально, потому что итоговый порядок символов и форматирования должен совпасть у всех участников, а сеть может задерживать операции и разрывать соединение.

Зачем понадобились CRDT

CRDT дают клиентам держать локальные копии одних и тех же данных и сливать одновременные изменения так, чтобы «concurrent edits can be merged without losing anyone’s changes». Главная причина их использовать — гарантировать, что одновременные правки объединяются без потери чьих-либо изменений.

Альтернатива — OT. OT пытается преобразовывать позиции индексов для сходимости, а CRDT используют математические модели, обычно без преобразования индексов, например связные списки. OT без центрального сервера требует слишком много служебных данных, чтобы быть практически пригодным; CRDT лучше подходят для распределённых систем и не требуют центрального источника истины.

Другой прежний подход — last write wins (LWW): сервер обрабатывал каждое обновление по мере поступления, и результат определяло последнее пришедшее. Поскольку каждое новое обновление перезаписывало предыдущее, правки одного человека полностью терялись.

Гарантия детерминированного объединения не означает, что сохраняется намерение каждого автора: одновременные правки сливаются без потери чьих-либо изменений, но «Even if changes are not lost, each collaborator’s intent is not always preserved perfectly».

Идентификаторы и порядок вставок

В реализации Notion на основе RGA каждый вставленный символ представлен узлом с уникальным стабильным ID, а операции вставки или удаления текста могут ссылаться на эти ID.

ID операции состоит из буквенной части — упрощённого session ID — и числовой части — Lamport clock. Вместе они делают ID уникальным: два клиента могут совпасть по Lamport clock, но не по session ID, а один клиент всегда увеличивает Lamport clock на основе знания наибольшего значения.

Порядок вставок задаётся сортировкой элементов, которые ссылаются на один и тот же origin: элемент с самой свежей логической меткой идёт первым, а session ID используется как тай-брейкер. Поэтому вставки после A@12 с ID E@18 и C@13 всегда разрешаются в одном порядке: 18 больше 13, значит E@18 встаёт раньше. Тот же принцип работает для цепочек вставок от одного якоря: каждая новая вставка получает свой Lamport clock, и при общем origin сортировка идёт по убыванию логической метки, а при равенстве — по session ID.

Для экономии памяти символы группируются в непрерывные последовательности от одной сессии и одного Lamport clock, а дополнительно хранится длина последовательности.

Rich text поверх базового порядка

Чтобы поддержать форматирование, введены операции на основе алгоритма Peritext: CRDT-деревья хранят операции добавления и удаления аннотации на текстовых элементах. В отличие от базового порядка, который расставляет сами текстовые элементы, Peritext работает поверх него и описывает форматирование как отдельные операции-аннотации, привязанные к этим элементам. Каждый текстовый элемент может хранить массив операций-аннотаций, что позволяет поддерживать перекрывающиеся аннотации.

Диапазон аннотации задаётся якорями start и end, которые указывают позицию непосредственно до или после границы элемента. Якоря определяют, расширяется ли аннотация: жирный шрифт расширяемый, поэтому текст, введённый в конце жирного фрагмента, тоже становится жирным, а гиперссылка — нет, поэтому её конечный якорь ставится иначе. Аннотация может охватывать несколько элементов, но её операция хранится только на первом, а остальные определяются по диапазону ID.

При конкурентных изменениях одного диапазона обе аннотации сохраняются: если Charlie применяет bold, а Emma одновременно italics, итоговый текст включает обе аннотации. Накопленные операции-аннотации применяются к тексту при разборе дерева.

Разбиение блока по Enter

Когда пользователь нажимает Enter в середине блока, создаётся новый блок после текущего, и текст делится между двумя блоками. Текстовые элементы блока принадлежат текстовому срезу, и каждый блок инициализируется пустым срезом. При разделении срез делится на два, и второй перемещается в новый блок.

Срезы одного блока организованы в дерево текстовых срезов. Срезы также принадлежат текстовому экземпляру: срез всегда сохраняет свой текстовый экземпляр, даже если разделён или перемещён.

Каждый срез имеет метку поиска, уникальную внутри текстового экземпляра. Изначально метка пустая, а при каждом разделении к ней добавляется L или R. После разделения блока метка правой части становится R; при дальнейшем разделении «things» на «thing» и «s» метки становятся RL и RR.

Таблица маппинга срезов

Таблица маппинга сопоставляет текстовые экземпляры с блоками, содержащими любой срез из этого экземпляра, и обновляется, когда блок получает срез из нового текстового экземпляра.

После split от Emma срезы из инстанса A оказываются одновременно в Block A и Block B: при разделении срез делится на два, второй перемещается в Block B, но оба сохраняют один и тот же текстовый экземпляр. Поэтому маппинг показывает, что срезы из инстанса A есть и в Block A, и в Block B. Чтобы найти нужный срез, сервер загружает все блоки, содержащие любой срез из соответствующего текстового экземпляра.

Почему поиск идёт по префиксу метки

Поиск по префиксу нужен потому, что целевой срез мог быть параллельно разделён. Если Emma разделила «things», пока Charlie дописывал в него, и её изменение применилось первым, операция Charlie всё ещё содержит метку R, хотя целевой срез теперь помечен RR. При запросе к маппингу ищутся блоки для экземпляра A, метка которых начинается с R, и тогда находится только один блок вместо двух.

То же покрывает повторные разделения одного среза: если продолжить делить «things» на «thing» и «s», метки станут RL и RR, и префиксный поиск по исходной метке всё равно находит нужный срез.

Синхронизация состояния: state vector и минимальный diff

Yjs хранит state vector. Каждый struct идентифицируется lamport-меткой из client и clock, а state vector задаёт следующий ожидаемый clock по каждому клиенту. Он используется только для описания состояния локального документа, чтобы вычислить недостающие structs удалённого клиента, и не применяется для отслеживания причинности.

Чтобы синхронизировать двух клиентов с минимальным объёмом данных, каждый клиент кодирует свой state vector, затем по state vector удалённой стороны вычисляет недостающие изменения, и полученный diff применяется у другой стороны. Кодирование state vector выполняет Y.encodeStateVector: оно превращает текущее состояние документа в компактное описание того, какие structs у клиента уже есть. Вычисление недостающих изменений делает Y.encodeStateAsUpdate, которому передают документ и state vector удалённой стороны, — на выходе получается diff только с теми изменениями, которых у удалённой стороны ещё нет. Применение полученного diff у другой стороны выполняет Y.applyUpdate. Обмен идёт в две стороны, потому что у каждого клиента свои недостающие изменения: один diff восполняет пробелы у первого клиента, другой — у второго.

Такой обмен требует дополнительного roundtrip, но может сэкономить много пропускной способности по сравнению с полной передачей структуры документа.

Синхронизация без загрузки Y.Doc в память

Синхронизировать клиентов и вычислять дельта-обновления можно без загрузки документа Yjs в память: Yjs предоставляет API для вычисления различий непосредственно на бинарных обновлениях. Текущее состояние каждого клиента кодируется в бинарный буфер, после чего сами документы уничтожаются. Далее векторы состояния вычисляются прямо из бинарных обновлений, а различия — функцией, которой передаётся бинарное обновление и вектор состояния удалённой стороны. Синхронизация завершается слиянием: к текущему состоянию одного клиента добавляется diff2, к состоянию другого — diff1.

Ограничение для серверной стороны в том, что вся работа ведётся только над бинарными обновлениями, без объекта Y.Doc, поэтому доступны лишь операции над буферами: получить вектор состояния из обновления, вычислить различие и слить обновления.

Shared-типы и их поведение

Из shared-типов описан Y.Array — разделяемый тип, похожий на массив, поддерживающий эффективные вставку и удаление элементов в любой позиции; внутренне он использует связный список массивов, разбиваемый при необходимости.

Для Y.Text приведены операции: вставка строки по индексу с назначением атрибутов форматирования, удаление диапазона, назначение атрибутов форматирования диапазону текста и применение delta. Общий алгоритм Yjs — модифицированная версия YATA CRDT.

Удаление структуры с содержимым заменяет её на структуру без содержимого, а при удалении типа все дочерние элементы превращаются в GC-структуры, которые можно сливать при смежных id. Последовательные вставки сливаются в одну структуру: две вставки сначала дают две структуры, затем одну с содержимым 'ab'.

applyDelta и модель срезов

applyDelta принимает delta из lib0/delta и применяет её к общему типу; позиции в delta интерпретируются относительно содержимого с атрибуциями, если передан opts.renderer. Опциональный origin сохраняется в транзакции и дословно передаётся в событие 'delta', чтобы слушатели могли распознать и пропустить собственные изменения. Пример строит delta через retain(5) и insert('!'): сначала пропускаются 5 позиций, затем вставляется символ.

Модель срезов и идентификаторов из Notion описывает группировку символов в непрерывные прогоны с одним ID и длиной, а также операции-аннотации с якорями start и end для расширяемых и нерасширяемых аннотаций.

Относительные позиции и курсоры

Относительная позиция фиксируется к элементу в общем документе и не затрагивается удалёнными изменениями. Обычные индекс-позиции неудобны: индекс становится недействительным, как только удалённое изменение манипулирует документом. Относительные позиции могут представлять расположение курсора, диапазоны выделения или привязку комментария к диапазону текста.

Создаётся она функцией, которая фиксирует позицию к i-му элементу последовательного типа; по умолчанию позиция ассоциируется с символом после указанного индекса, а при отрицательном assoc — с символом перед ним. Обратное преобразование возвращает тип, индекс и assoc либо null, если позицию нельзя сослаться или тип удалён.

Поведение при удалённых правках: для документа "a|c" позиция привязана к c, и когда удалённый пользователь вставляет символ перед курсором, курсор остаётся привязан к c: insert(1, 'x')("a|c") = "ax|c". Если позиция установлена в конец документа, она останется привязана к концу документа. Для передачи позицию можно закодировать в Uint8Array или через JSON, а на удалённой стороне декодировать и восстановить абсолютную позицию.

Форматы обновлений V1 и V2

Yjs реализует два формата обновлений. По умолчанию используется V1, а V2 можно включить опционально, и он даёт лучшее сжатие. V2 пока используется не всеми провайдерами, но его можно применять при создании собственного провайдера.

Для V2 все функции доступны с суффиксом «V2», а события обновлений нужно слушать отдельно. Между форматами есть функции конвертации в обе стороны.

Undo/Redo и origins

StackItem. Y.UndoManager объединяет изменения в один StackItem, если они происходят с временным зазором меньше options.captureTimeout — промежутка времени, в течение которого изменения считаются одной операцией. Явный вызов stopCapturing() разрывает эту группировку, так что следующий StackItem не будет объединён с предыдущим. Без stopCapturing две последовательные вставки попадают в один интервал захвата и сливаются в один StackItem, поэтому undo откатывает их обе; с stopCapturing между вставками undo откатывает только вторую. Событие 'stack-item-updated' возникает, когда два изменения происходят внутри captureInterval.

origin. trackedOrigins — набор значений-origin, которые UndoManager считает своими и записывает в undo-стек. У каждого изменения в общем документе есть origin; если origin не задан, он равен null. Указав trackedOrigins, можно выборочно определить, какие изменения отслеживать; сам экземпляр UndoManager всегда добавляется в набор. Изменения с origin, не входящим в набор, в undo-стек не попадают и не откатываются через undo(). Так чужие правки, приходящие с другим origin, не откатываются: вставка с origin null не отслеживается, а вставка внутри транзакции с origin 42 отслеживается, потому что 42 входит в набор.

Сборка мусора и удаление

Когда тип удаляется, все его дочерние элементы преобразуются в GC-структуры. GC-структура обозначает только факт существования структуры и то, что она удалена, и может быть объединена с другими GC-структурами при смежных идентификаторах. То есть GC-структуры сохраняют лишь идентификацию и признак удаления, но теряют содержимое.

Восстановление удалённого контента возможно только если отключить сборку мусора. При включённой сборке удалённые структуры заменяются на GC-структуры, и восстановить исходное содержимое нельзя.

Провайдеры и транспорт

Любые провайдеры Yjs можно комбинировать между собой для синхронизации данных по разным сетевым технологиям. Обычно сетевой провайдер (например, y-websocket или y-webrtc) комбинируют с провайдером персистентности (y-indexeddb в браузере), чтобы быстрее загружать документ и сохранять данные, созданные офлайн. В примере на одном Y.Doc одновременно используются IndexeddbPersistence, WebrtcProvider и WebsocketProvider с одинаковым именем комнаты, и все они синхронизируют один и тот же документ.

pluv.io описан как полнофункциональный бэкенд для Yjs, который можно использовать на управляемой WebSocket-инфраструктуре или развернуть самостоятельно на Cloudflare Workers и Node.js, с typesafe API, аутентификацией, вебхуками и комнатами.

Отладка: обфускация апдейтов

Обфускация апдейтов нужна, чтобы пользователь мог отправить разработчику документ для разбора странного бага, не передавая исходное содержимое: вместо запроса полного документа пользователь может заменить содержимое на бессмысленное сгенерированное и отправить его. Приватность не абсолютна: по общей структуре документа всё ещё можно предположить тип содержимого, но это лучше, чем запрашивать оригинальный документ.

Для воспроизведения багов обфусцированный апдейт остаётся полноценным CRDT-апдейтом: он содержит все CRDT-данные, необходимые для слияния, поэтому его безопасно сливать. Функция Y.obfuscateUpdate(update) берёт апдейт, полученный, например, через Y.encodeStateAsUpdate(ydoc), и возвращает апдейт с перемешанными данными. Такой апдейт можно применить на другом документе, и содержимое текста станет бессмысленным.

Практические компромиссы

CRDT позволяют клиентам хранить локальные копии и детерминированно сливать одновременные изменения, но структура только растёт, а удалённые элементы остаются как tombstones. В RGA хранятся все когда-либо вставленные символы, а удаление лишь помечает элемент удалённым, потому что на его ID могут ссылаться отложенные или офлайн-операции. Yjs также отмечает, что подходящие для текста CRDT растут в размере; нельзя собирать tombstones, сохраняя уникальный порядок структур, но можно объединять соседние структуры, удалять содержимое удалённой структуры и собирать tombstones, когда порядок больше не важен.

Выгода — распределённость и отсутствие центрального источника истины. Неоптимальность возможна, когда нужно точно сохранить намерение одного пользователя: если Emma хотела текст ровно «Build cool things», объединённый результат не достигнет этой цели.

Что из этого следует на практике

Итоговый порядок символов детерминирован, но не обязан совпадать с намерением автора: одновременные правки не теряются, а вот точное намерение сохраняется не всегда. Планируя поведение редактора, стоит рассчитывать на слияние без потерь, а не на «правильный» результат с точки зрения одного человека.
Порядок вставок от одного якоря определяется логической меткой: чем свежее Lamport clock, тем раньше элемент. Это значит, что поздние вставки в общий якорь оказываются перед более ранними, и на это нельзя влиять порядком доставки операций.
Поиск среза по префиксу метки — прямое следствие параллельных разделений: операция, отправленная до чужого split, продолжает находить свой срез, потому что метка целевого среза лишь дополняется символами L/R.
Синхронизацию можно вести без загрузки полного документа в память, работая только с бинарными обновлениями. Это ограничивает серверную сторону набором операций над буферами, но снимает необходимость держать Y.Doc целиком.
Включённая сборка мусора необратима для содержимого: после замены структур на GC-структуры восстановить удалённый текст нельзя. Если нужна возможность отката старого контента, сборку мусора отключают заранее.
Undo по умолчанию группирует быстрые правки в одну операцию, а trackedOrigins отделяет свои изменения от чужих: без явного разрыва захвата и без учёта origin откат может затронуть не то, что ожидал пользователь.