Системный дизайн совместного редактирования: OT против CRDT на примере Google Docs
Как спроектировать совместный редактор вроде Google Docs: операционные преобразования и CRDT с кодом на Python, сервер сессии документа, WebSocket, журнал операций, снимки, курсоры и офлайн.
Коротко
| Вопрос | Решение в этом разборе |
|---|---|
| Главная проблема | двое правят один текст одновременно, и у всех должен получиться одинаковый результат |
| Подход 1: OT | операции по позиции, сервер переписывает их относительно уже принятых |
| Подход 2: CRDT | у каждого символа уникальный id, вставки «после соседа» коммутируют без сервера |
| Что выбрать | центральный сервер есть всегда → OT проще и экономнее; офлайн и P2P → CRDT |
| Транспорт | WebSocket к серверу сессии; все правки документа идут через один процесс |
| Хранение | журнал операций + периодические снимки; история версий — бесплатно |
| Курсоры и присутствие | эфемерные данные, отдельно от документа, без записи на диск |
Совместный редактор — задача, где «нарисовать сервисы и базу» недостаточно. Интервьюер ждёт, что вы покажете сам конфликт: Алиса вставляет букву в начало, Боб в тот же момент удаляет третью — что увидит каждый? Без ответа на этот вопрос остальная архитектура не имеет смысла.
Ниже — алгоритмическое ядро с работающим кодом и система вокруг него. Общий план секции — в статье про подходы к проектированию систем.
Шаг 1. Требования
| Вопрос | Ответ интервьюера | Что это меняет |
|---|---|---|
| Что редактируем? | текст с форматированием | модель — последовательность символов и атрибутов |
| Сколько человек в одном документе? | обычно 1–5, до 100 одновременно | одна сессия помещается в один процесс |
| Насколько быстро видны чужие правки? | меньше секунды | постоянное соединение, не опрос |
| Нужен офлайн? | короткий — пропала сеть в поезде | клиент копит операции и досылает их |
| История версий? | да, с откатом | храним журнал операций, а не только текст |
| Видеть курсоры других? | да | отдельный канал присутствия |
Нефункциональные: ни одна принятая правка не теряется; все участники в итоге видят одинаковый документ (сходимость); своя правка применяется мгновенно, без ожидания сервера.
Последнее требование — источник всей сложности. Если бы клиент ждал подтверждения перед каждой буквой, хватило бы блокировки. Но печатать с задержкой в 100 мс на символ никто не станет, поэтому каждый клиент применяет правку локально сразу, а значит, реплики документа временно расходятся.
Шаг 2. Оценка нагрузки
- 10 млн активных документов в день, в пике открыто 1 млн сессий, в среднем по 2 человека.
- Печатающий человек генерирует 3–5 операций в секунду; клиенты обычно склеивают их в пачки раз в 50–100 мс. Получается порядка нескольких сотен тысяч операций в секунду на весь сервис.
- Одна операция — десятки байт. Журнал растёт на гигабайты в день, но снимки позволяют держать горячим только хвост.
Вывод: нагрузка на весь сервис большая, а на один документ — крошечная. Это подсказывает архитектуру: все правки документа обрабатывает один процесс, а масштабируемся числом процессов. Подробнее про такие прикидки — в статье про оценку на салфетке.
Шаг 3. Почему не «последний записавший побеждает»
Самое простое — пересылать весь текст и брать последнюю версию. Алиса и Боб одновременно печатают в разных абзацах, и правка одного из них пропадает целиком. Блокировка документа или абзаца тоже не годится: «кто-то сейчас редактирует, подождите» — это не Google Docs.
Пересылать нужно операции: «вставь с в позицию 0», «удали символ в позиции 2». Но позиции у всех разные, как только реплики разошлись. Документ кот:
- Алиса вставляет
св позицию 0 →скот. - Боб одновременно удаляет позицию 2 (
т) →ко. - Алиса получает операцию Боба «удали позицию 2» и удаляет
о:сот. Боб получает «вставьсв 0»:ско. Документы разошлись.
Есть два семейства решений.
Шаг 4. Operational Transformation
Идея OT: перед применением чужой операции переписать её с учётом своих, которые она «не видела». Если Алиса вставила символ левее позиции удаления, позиция Боба сдвигается на 1.
from dataclasses import dataclass, replace @dataclass(frozen=True) class Op: kind: str # 'ins' или 'del' pos: int char: str = '' site: int = 0 # id клиента, разбивает ничьи def apply(doc, op): if op.kind == 'ins': return doc[:op.pos] + op.char + doc[op.pos:] if op.kind == 'del': return doc[:op.pos] + doc[op.pos + 1:] return doc # 'noop' def transform(a, b): """Переписать a так, будто b уже применена к документу.""" if a.kind == 'noop' or b.kind == 'noop': return a if b.kind == 'ins': if b.pos < a.pos or (b.pos == a.pos and a.kind == 'ins' and b.site < a.site): return replace(a, pos=a.pos + 1) if b.pos == a.pos and a.kind == 'del': return replace(a, pos=a.pos + 1) return a # b — удаление if b.pos < a.pos: return replace(a, pos=a.pos - 1) if b.pos == a.pos and a.kind == 'del': return replace(a, kind='noop') # этот символ уже удалён return a doc = 'кот' a = Op('ins', 0, 'с', site=1) # Алиса: «скот» b = Op('del', 2, site=2) # Боб: «ко» left = apply(apply(doc, a), transform(b, a)) right = apply(apply(doc, b), transform(a, b)) print(left, right) # ско ско
Два момента, которые стоит назвать на интервью:
- Ничьи. Две вставки в одну позицию нужно упорядочить одинаково у всех. Для этого нужен детерминированный признак — здесь
site, id клиента. - Свойство сходимости. Для пары операций должно выполняться
apply(apply(d, a), T(b, a)) == apply(apply(d, b), T(a, b)). Код выше я проверил на 100 000 случайных пар — расходится ноль. Но это свойство только для двух операций. Чтобы OT работал без центрального сервера при произвольном порядке доставки, нужно ещё одно, куда более капризное свойство, и многие опубликованные алгоритмы его нарушали.
Поэтому на практике OT почти всегда используют с центральным сервером, который задаёт единый порядок операций. Эта схема восходит к системе Jupiter из Xerox PARC середины 90-х, а Google Docs — самый известный продукт на OT с сервером.
Как это работает:
- Сервер хранит документ и номер ревизии. Каждая принятая операция увеличивает ревизию.
- Клиент отправляет операцию вместе с номером ревизии, на которой она сделана, и держит не более одной неподтверждённой пачки в полёте.
- Сервер прогоняет операцию через
transformпо всем операциям, принятым после этой ревизии, применяет, рассылает остальным. - Клиент, получая чужие операции, трансформирует их относительно своих неподтверждённых.
Сервер становится единственным арбитром порядка. Это и есть главная цена OT: без него ничего не работает. Для онлайн-редактора это нормально — сервер всё равно нужен для хранения и прав доступа.
Шаг 5. CRDT
CRDT (Conflict-free Replicated Data Type) решает задачу иначе: делает операции такими, что их можно применять в любом порядке и получать одно и то же. Для текста главный трюк — не использовать индексы. Каждый символ получает уникальный id (счётчик, site), а вставка звучит как «поставь с сразу после символа с id X». Удаление не стирает символ, а помечает его «надгробием» (tombstone), потому что на него могут ссылаться чужие вставки.
Ниже — упрощённая последовательность в духе RGA. Символы образуют дерево «вставлен после», среди вставленных после одного соседа первым идёт символ с большим id; текст — обход дерева в глубину.
ROOT = (0, 0) class Replica: """Последовательность-CRDT в духе RGA: символ вставляется «после» соседа.""" def __init__(self, site): self.site = site self.clock = 0 self.chars = {ROOT: ''} self.children = {ROOT: []} self.deleted = set() def apply(self, op): if op[0] == 'ins': _, id_, parent, ch = op if id_ in self.chars: return # повторная доставка ничего не ломает self.clock = max(self.clock, id_[0]) self.chars[id_] = ch self.children[id_] = [] self.children[parent].append(id_) self.children[parent].sort(reverse=True) # новее — ближе к родителю else: self.deleted.add(op[1]) def visible(self): out, stack = [], list(reversed(self.children[ROOT])) while stack: id_ = stack.pop() if id_ not in self.deleted: out.append(id_) stack.extend(reversed(self.children[id_])) return out def text(self): return ''.join(self.chars[i] for i in self.visible()) def insert(self, index, ch): # вставить ch перед видимым символом index ids = self.visible() parent = ids[index - 1] if index > 0 else ROOT self.clock += 1 op = ('ins', (self.clock, self.site), parent, ch) self.apply(op) return op def delete(self, index): op = ('del', self.visible()[index]) self.apply(op) return op a, b = Replica(1), Replica(2) for op in [a.insert(0, 'к'), a.insert(1, 'о'), a.insert(2, 'т')]: b.apply(op) x = a.insert(0, 'с') # Алиса: «скот» y = b.delete(2) # Боб: «ко» b.apply(x) a.apply(y) print(a.text(), b.text()) # ско ско
Никакой transform не нужен: Боб удаляет символ с конкретным id, а не «позицию 2», и где бы этот символ ни оказался у Алисы, удалится именно он. Я прогнал модель на тысячах случайных сценариев с тремя репликами и случайным порядком доставки (вставка приходит только после символа, к которому привязана) — реплики всегда сходятся. Повторная доставка тоже безопасна: операция идемпотентна.
Цена CRDT:
- Метаданные. У каждого символа id и ссылка на соседа, удалённые символы остаются надгробиями. Наивная реализация тратит десятки байт на символ текста. Современные библиотеки (Yjs, Automerge) сжимают подряд набранные символы в блоки, и накладные расходы падают в разы, но не до нуля.
- Сборка мусора надгробий требует знать, что все реплики их увидели, — а это снова координация.
- Чередование. При одновременной вставке двух слов в одно место некоторые CRDT перемешивают их буквы. Хорошие алгоритмы это учитывают, но это ещё один пункт, который нужно проверять.
Шаг 6. OT или CRDT: что сказать на интервью
| Критерий | OT с сервером | CRDT |
|---|---|---|
| Нужен центральный сервер | да, он задаёт порядок | нет, но обычно есть для хранения и прав |
| Офлайн надолго, P2P | тяжело: длинные цепочки трансформаций | естественно |
| Память на документ | только текст + журнал | id на символ, надгробия |
| Сложность корректности | функции transform на каждую пару типов | структура данных, но доказуемо сходится |
| Примеры | Google Docs | Yjs, Automerge; Figma — серверная схема, вдохновлённая CRDT |
Разумный ответ: «Пользователи всегда онлайн, сервер у нас всё равно есть — беру OT с центральным сервером, это дешевле по памяти и проще в эксплуатации. Если появится требование долгого офлайна или локального приложения, переходим на CRDT». Важно не выбрать «правильный» вариант, а показать, что вы понимаете, чем платите.
Шаг 7. Архитектура вокруг алгоритма
Клиенты ──WebSocket──► Gateway ──► Document Session Server (владелец документа)
│ │
│ └──► Presence (курсоры, в памяти)
▼
Журнал операций ──► Snapshot Worker ──► Хранилище снимков
- Транспорт. Двусторонний поток с малой задержкой — WebSocket; сравнение вариантов есть в статье про WebSocket и long polling. Gateway держит соединения и ничего не знает о тексте.
- Один владелец на документ. Все операции документа обрабатывает один процесс Session Server — так у OT появляется единый порядок без распределённых блокировок. Документ привязывается к серверу через консистентное хеширование или через реестр «документ → сервер» с арендой. При падении сервера документ переезжает: новый владелец поднимает последний снимок и доигрывает хвост журнала. Чтобы старый владелец после паузы не продолжил писать, используют номер эпохи — как в статье про выбор лидера.
- Журнал операций — источник правды:
(doc_id, revision, op, author, ts)с уникальностью по(doc_id, revision). Операция подтверждается клиенту только после записи в журнал. Это, по сути, event sourcing: история версий и откат получаются бесплатно. - Снимки. Раз в N операций или минут фоновый воркер сохраняет текст целиком. Открытие документа = последний снимок + хвост журнала, а не миллион операций с начала.
- Присутствие. Курсоры и выделения меняются десятки раз в секунду и не нужны после закрытия вкладки. Их рассылают через тот же Session Server, но не пишут в журнал и не трансформируют строго — достаточно сдвигать позицию курсора при чужой вставке левее.
- Офлайн. Клиент копит операции локально с номером последней известной ревизии и после переподключения отправляет пачкой. Сервер трансформирует их по всему, что накопилось. Если офлайн был долгим, пачка большая — здесь CRDT выигрывает.
- Права доступа проверяются при открытии сессии и на каждой операции записи: читатель не должен иметь возможности прислать
ins.
Узкие места и вопросы вглубь
| Вопрос интервьюера | Ответ |
|---|---|
| 1000 человек открыли один документ | писать могут единицы; читателей обслуживают реплики рассылки за сервером |
| Session Server упал | новый владелец: снимок + журнал; клиенты переподключаются и досылают неподтверждённое |
| Клиент прислал операцию дважды | (client_id, seq) в операции, сервер отбрасывает повтор (идемпотентность) |
| Форматирование (жирный, ссылки) | отдельные типы операций над диапазонами, со своими правилами transform |
| Копипаст на 10 МБ | одна операция с большим payload, ограничение размера, загрузка через хранилище |
| Поиск по документам | асинхронная индексация снимков, не по каждой букве |
Типичные ошибки на интервью
- Не показать конфликт. Без примера «вставка + удаление одновременно» непонятно, что вы вообще решаете.
- Блокировки вместо слияния. Pessimistic locking абзацев ломает главный сценарий продукта.
- «Возьмём CRDT, и сервер не нужен». Сервер всё равно нужен: хранение, права, история, рассылка.
- Хранить только последний текст. Тогда нет ни истории, ни восстановления после падения сервера сессии.
- Писать курсоры в базу. Это эфемерные данные, им место в памяти.
- Распределять правки одного документа по многим серверам. Нагрузка на один документ мала — проще и надёжнее один владелец.
Что запомнить
- Ядро задачи — сходимость при одновременных правках; пересылаем операции, а не текст.
- OT переписывает позиции чужих операций; на практике работает с центральным сервером, задающим порядок. Так устроен Google Docs.
- CRDT даёт символам уникальные id и вставляет «после соседа»; операции коммутируют, но стоят памяти.
- Все правки документа — через один процесс-владелец; журнал операций + снимки — источник правды.
- Курсоры и присутствие — отдельный эфемерный канал.
Похожие разборы с постоянными соединениями: чат и система уведомлений.