Системный дизайн совместного редактирования: OT против CRDT на примере Google Docs

Как спроектировать совместный редактор вроде Google Docs: операционные преобразования и CRDT с кодом на Python, сервер сессии документа, WebSocket, журнал операций, снимки, курсоры и офлайн.

12 мин чтениясистемный дизайн · распределённые системы · python · собеседования

Коротко

ВопросРешение в этом разборе
Главная проблемадвое правят один текст одновременно, и у всех должен получиться одинаковый результат
Подход 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 с сервером.

Как это работает:

  1. Сервер хранит документ и номер ревизии. Каждая принятая операция увеличивает ревизию.
  2. Клиент отправляет операцию вместе с номером ревизии, на которой она сделана, и держит не более одной неподтверждённой пачки в полёте.
  3. Сервер прогоняет операцию через transform по всем операциям, принятым после этой ревизии, применяет, рассылает остальным.
  4. Клиент, получая чужие операции, трансформирует их относительно своих неподтверждённых.

Сервер становится единственным арбитром порядка. Это и есть главная цена 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 DocsYjs, 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, и сервер не нужен». Сервер всё равно нужен: хранение, права, история, рассылка.
  • Хранить только последний текст. Тогда нет ни истории, ни восстановления после падения сервера сессии.
  • Писать курсоры в базу. Это эфемерные данные, им место в памяти.
  • Распределять правки одного документа по многим серверам. Нагрузка на один документ мала — проще и надёжнее один владелец.

Что запомнить

  1. Ядро задачи — сходимость при одновременных правках; пересылаем операции, а не текст.
  2. OT переписывает позиции чужих операций; на практике работает с центральным сервером, задающим порядок. Так устроен Google Docs.
  3. CRDT даёт символам уникальные id и вставляет «после соседа»; операции коммутируют, но стоят памяти.
  4. Все правки документа — через один процесс-владелец; журнал операций + снимки — источник правды.
  5. Курсоры и присутствие — отдельный эфемерный канал.

Похожие разборы с постоянными соединениями: чат и система уведомлений.

Потренироваться в спокойной обстановке

Все задачи