Real-Time Backend
Operational Transform
В 2009 году Google запустил Wave - амбициозную платформу совместного редактирования. Под капотом был алгоритм Operational Transformation, который Google разрабатывал 3 года. Сегодня тот же алгоритм работает в Google Docs, который обслуживает более 1 млрд документов и миллиарды операций в день.
- **Google Docs** использует OT с централизованным сервером-арбитром: каждое нажатие клавиши - это операция с revision-номером. При 50 одновременных пользователях в документе сервер сериализует до 500 операций/сек, трансформируя каждую относительно пропущенных изменений. Latency редактирования - <100ms даже при геораспределённых пользователях.
- **ShareDB** (open-source, бывший DerbyJS) - production OT-фреймворк для Node.js с поддержкой MongoDB и PostgreSQL как backend. Quill.js интегрируется с ShareDB через quill-delta: каждый символ rich-text описывается операцией `{insert: 'text', attributes: {bold: true}}`. Сотни стартапов используют этот стек для collaborative editing без написания OT с нуля.
- **Figma** применяет собственную OT-подобную систему для синхронизации состояния дизайн-файлов. При 100+ дизайнерах в одном файле операции перемещения, изменения размера и стиля трансформируются на сервере. Их инженеры публично описали, что выбрали OT над CRDT из-за меньшего overhead по памяти на крупных файлах.
- **Atom Teletype** (GitHub, 2017) использовал CRDT вместо OT для peer-to-peer code sharing без центрального сервера - это иллюстрирует, что OT не единственный подход и выбор зависит от архитектуры: OT требует сервера, CRDT - нет.
Что такое Operational Transformation
Сценарий: два пользователя редактируют один документ одновременно. Первый вставляет 'X' в позицию 5, второй удаляет символ в позиции 3. Оба действия идут на сервер независимо. Если просто применить их по очереди - документ у разных клиентов окажется разным. Именно эту проблему решает **Operational Transformation (OT)** - алгоритм, который корректирует операции с учётом уже применённых изменений.
Операция в OT - это не просто «изменить текст», а структурированный объект с типом (`insert`/`delete`/`retain`), позицией и данными. Сервер хранит историю операций и при получении новой операции от клиента трансформирует её относительно всех операций, которые клиент ещё не видел. После трансформации - применяет результат и рассылает всем остальным.
Два клиента создают операции на одной версии документа (revision 3). Клиент A отправляет операцию первым, сервер её применяет. Что сервер делает с операцией клиента B, когда она приходит?
Transform Functions - математика под капотом
Transform-функция принимает две операции `(opA, opB)` и возвращает пару `(opA', opB')` - трансформированные версии, где `opA'` применяется поверх `opB`, а `opB'` - поверх `opA`. Ключевое свойство: `apply(apply(doc, opA), opB') == apply(apply(doc, opB), opA')`. Это называется **convergence property** - конечный документ одинаков независимо от порядка применения.
Реальная сложность возникает с парами `insert/insert`, `insert/delete`, `delete/insert`, `delete/delete`. Каждая комбинация требует своей логики. Google использовал проприетарный алгоритм, Etherpad открыл свой (easysync), ShareDB реализовал json0 - библиотека для JSON-документов с 7 типами операций.
ShareDB (Node.js OT-сервер с 6k+ GitHub stars, используется в Quill и ряде стартапов) реализует json0 - формат операций для JSON-деревьев. Там transform покрывает не просто позиции строки, а вложенные объекты: `{p: ['content', 3], li: 'new item'}` - вставка в список по пути.
Документ 'ABC'. Клиент A делает insert(1, 'X') - вставить 'X' после позиции 1. Клиент B делает delete(2, 1) - удалить 1 символ с позиции 2 (символ 'B'). Оба на revision 0. После трансформации insert(1,'X') применяется первым. Какой должна быть трансформированная операция B (delete_prime)?
Convergence и доказательство корректности
Convergence - свойство, что все клиенты приходят к одному и тому же состоянию документа, применив все операции в правильном порядке. Формально: для любых двух операций `a` и `b`, применённых на одном состоянии `s`, должно выполняться `apply(apply(s, a), transform(b, a)) == apply(apply(s, b), transform(a, b))`. Это **CP1** - первое свойство convergence.
Существует и **CP2** - intention preservation: каждая операция должна достигать своего первоначального намерения. Вставить слово в абзац - слово должно оказаться в том абзаце, а не съехать в другое место из-за трансформации. CP2 гораздо сложнее формализовать и реализовать - именно поэтому ряд ранних OT-алгоритмов (Jupiter, dOPT) имели баги при 3+ пользователях.
В 2006 году Sun и Ellis формально доказали, что алгоритм Jupiter (основа Google Wave OT) нарушает CP2 при 3+ клиентах. Google Docs использует модифицированный алгоритм с централизованным сервером-арбитром, который сериализует все операции - это избавляет от peer-to-peer проблем, но требует постоянного соединения с сервером.
Три клиента (A, B, C) одновременно редактируют документ. Все делают операции на revision 5. Алгоритм Jupiter (peer-to-peer OT) показывает разные документы у A и B после применения всех операций. Какова наиболее вероятная причина?
OT в Google Docs и production-реализации
Google Docs обрабатывает более 1 млрд документов. Архитектура совместного редактирования строится на централизованном OT-сервере: каждый клиент поддерживает очередь неподтверждённых операций (`pending`) и состояние (`revision`). При отправке операции клиент переходит в режим ожидания - новые локальные изменения буферизируются. Сервер подтверждает операцию (ACK) с текущим revision, и клиент трансформирует буфер относительно всех операций, которые он пропустил.
ShareDB - open-source OT-фреймворк (бывший DerbyJS), поддерживает json0 и rich-text. Используется в Figma (для совместного редактирования свойств), ряде no-code платформ. Quill.js (редактор с 43k звёзд на GitHub) нативно интегрируется с ShareDB через quill-delta - формат операций поверх json0, оптимизированный для rich-text.
OT и CRDT решают одну задачу, поэтому современные системы переходят с OT на CRDT как на 'лучший' алгоритм
OT и CRDT - разные trade-off: OT требует центрального сервера и истории операций, но компактен по памяти; CRDT работает peer-to-peer без сервера, но хранит метаданные о каждом символе (tombstones, vector clocks). Figma использует OT, Notion - CRDT (их Y.js форк), Atom Teletype - CRDT. Выбор зависит от архитектуры, не от 'лучшести'.
CRDT на практике занимает в 10-100x больше памяти на документ из-за tombstones. Для Google Docs с миллиардами документов OT + централизованный сервер экономически выгоднее. CRDT выигрывает в offline-first и P2P-сценариях, где нет постоянного серверного соединения.
OT-клиент находится в состоянии 'awaiting' (ожидает ACK от сервера). Пользователь вводит ещё текст. Как клиент должен обработать новую локальную операцию?
Итоги
- **OT - это transform(opA, opB) -> (opA', opB')**: трансформированные операции дают одинаковый результат в любом порядке применения (convergence property CP1).
- **Централизованный сервер решает проблему CP2**: Google Docs линеаризует все операции через сервер-арбитр, избегая peer-to-peer проблем при N>2 клиентах, доказанных для алгоритма Jupiter.
- **Клиентский state machine: synchronized -> awaiting -> buffered**: локальные операции применяются мгновенно (optimistic UI), накапливаются в buffer, отправляются по одной после ACK.
- **OT vs CRDT - trade-off, не замена**: OT компактнее по памяти, требует сервер; CRDT работает P2P, но хранит tombstones. Google Docs выбирает OT, Notion - Y.js (CRDT).
Связанные темы
OT - это конкретная реализация более широких принципов распределённых систем:
- CRDT (Conflict-free Replicated Data Types) — Альтернативный подход к eventual consistency без центрального сервера - CRDT кодирует порядок операций в структуре данных, а не в алгоритме трансформации
- Vector Clocks и Lamport Timestamps — OT использует revision-номера как упрощённые логические часы; vector clocks позволяют отслеживать причинность между операциями в распределённой системе
- Eventual Consistency — OT реализует одну из моделей eventual consistency: все узлы в итоге приходят к одному состоянию, convergence property гарантирует это математически
Вопросы для размышления
- Google Docs требует постоянного соединения с сервером, а Figma позволяет некоторое время работать офлайн. Какие архитектурные изменения нужны для offline-first OT, и почему CRDT лучше подходит для этого сценария?
- Transform-функция для текстовых операций (insert/delete) относительно проста. Как усложняется реализация при переходе к rich-text (жирный, курсив, ссылки) или к структурированным данным (JSON-деревья таблиц)?
- При 1000 одновременных пользователей в документе сервер должен хранить историю операций для трансформации. Как ограничить рост этой истории, не нарушая корректность для клиентов с плохим соединением?