Проектирование аналога Google Docs

Google docs – это сервис для совместного редактирования документов. В целом подобные сервисы можно спроектировать двумя способами:

• В качестве централизованного ресурса, использующего клиент-серверную архитектуру для предоставления возможности редактирования документа всем пользователям.
• На базе одноранговой архитектуры, позволяющей разным людям совместно работать над одним документом.

Большинство коммерческих решений ориентированы на клиент-серверный подход ввиду предоставляемого им более детального контроля. Так что и мы в этой статье разберём проектирование сервиса с использованием именно клиент-серверной архитектуры.

Требования

▍ Функциональные

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

▍ Нефункциональные

• Задержка: во время работы над одним документом к системе может быть подключено множество пользователей. И если они будут географически распределены по удалённым локациям, то обеспечение устойчиво низкой задержки окажется непростой задачей.
• Согласованность: система должна разрешать конфликты, возникающие при одновременном редактировании одних и тех же частей документа разными пользователями, обеспечивая его согласованное представление. В то же время пользователи из разных регионов должны наблюдать обновлённую версию документа. Поддержание согласованности является важным аспектом для всех пользователей, независимо от того, находятся они в одном регионе или в разных.
• Доступность: сервис должен быть доступен всегда и являться устойчивым к сбоям.
• Масштабируемость: на случай роста числа одновременных пользователей в архитектуру сервиса должна быть заложена возможность увеличения мощности.

Компоненты

▍ Хранилища данных

• Реляционная база данных – для хранения информации о пользователях и документах. На основе этих данных будут предоставляться различные права доступа.
• NoSQL — для хранения комментариев пользователей и организации быстрого доступа к ним.
• Временной ряд — для сохранения истории изменения документов.
• Хранилище BLOB-объектов — для хранения видео и изображений внутри документа.
• Кэш — распределённый кэш вроде Redis и CDN для обеспечения высокой производительности на стороне конечных пользователей. Redis мы используем для хранения разных структур данных, включая пользовательские сессии, признаки для функции автозаполнения, а также часто используемые документы. При этом с помощью CDN мы сохраняем наиболее часто открываемые документы и тяжёлые объекты, такие как изображения и видео.

▍ Очередь на обработку

Использовать HTTP-вызов для отправки каждого символа неэффективно. Поэтому мы задействуем технологию WebSockets, позволяющую снизить накладные издержки и наблюдать вносимые пользователями изменения в реальном времени.

▍ Прочие компоненты

К прочим компонентам относятся серверы сессий, хранящие информацию о сессиях пользователей. С помощью этих серверов мы реализуем управление правами доступа. По сути, у нас также будут присутствовать службы конфигурации, мониторинга, логирования и система «издатель-подписчик». С помощью этих служб мы будем обрабатывать такие процессы, как отслеживание и выбор лидеров в случае сбоев серверов, постановка в очередь задач вроде уведомления пользователей, а также логировать отладочную информацию.

Рис. 1 Подробная схема сервиса для совместного редактирования документов

Рабочий поток

• Совместное редактирование и разрешение конфликтов: каждый запрос передаётся в очередь операций. Именно здесь разрешаются конфликты между правками одной и той же части документа. Если конфликтов нет, данные собираются в пакет и сохраняются в базе данных временных рядов через серверы сессий. Для повышения эффективности использования хранилища видео и изображения подвергаются сжатию. Символы обрабатываются сразу.
• История: база данных временных рядов позволяет восстанавливать различные версии документа. При этом можно использовать операции DIFF, позволяющие сравнивать разные версии документа и определять отличия между ними для восстановления более старых ревизий.
• Асинхронные операции: уведомления, электронные письма, количество просмотров и комментарии – всё это относится к асинхронным операциям, которые можно добавлять в очередь с помощью системы «издатель-подписчик» вроде Kafka. Шлюз API генерирует эти запросы и перенаправляет в модуль «издатель-подписчик».
• Предложения: предложения реализуются через службу автозавершения, предлагающую автоматическое дополнение ввода часто используемых слов и фраз. Эта служба также может извлекать из документа атрибуты и ключевые слова, предлагая пользователю те или иные варианты. Поскольку слов может быть много, мы для этой задачи используем базу данных NoSQL. Кроме того, часто используемые слова и фразы будут сохраняться в кэше Redis.
• Импорт и экспорт документов: серверы приложения выполняют ряд важных задач, включая импорт и экспорт документов. Помимо этого, они конвертируют документы из одного формата в другой. К примеру, документ .doc или .docx можно конвертировать в .pdf и наоборот. Серверы приложения также отвечают за извлечение признаков для службы автозавершения.

Подробный дизайн

▍ Текстовый редактор

Документ представляет собой набор символов, расположенных в определённом порядке. Каждый символ имеет значение и индекс размещения. В качестве символа может выступать буква, число, возврат каретки (
) или пробел. Индекс представляет позицию символа в упорядоченном списке всех символов.

Задача текстового редактора заключается в выполнении с содержащимися в нём символами таких операций, как insert(), delete(), edit() и многих других. Ниже показан пример документа и выполнения в нём этих операций.

Рис. 2 Схема выполнения текстовым редактором различных операций

▍ Конкурентность

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

Добавление символа в один и тот же позиционный индекс:

Рис. 3 Как изменение двумя пользователями одного и того же символа может привести к конфликту

Удаление одного и того же символа:

Рис. 4 Как удаление одного и того же символа может привести к неожиданным изменениям

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

В этом механизме должно быть учтено два аспекта:

• Коммутативность: порядок применяемых операций не должен влиять на результат.
• Идемпотентность: одинаковые операции в случае повторения должны применяться только раз.

Техники разрешения конфликтов

▍ Операционная трансформация (OT)

Эта техника широко используется для разрешения конфликтов при совместном редактировании текстов без применения блокировки. Если выполняемые разными людьми операции конфликтуют, OT разрешает этот конфликт и передаёт корректное итоговое состояние конечным пользователям, обеспечивая тем самым согласованное представление.

В этом случае разрешение конфликтов происходит за счёт использования в операциях позиционного индекса символов. Описанные выше проблемы эта техника решает за счёт сохранения коммутативности и идемпотентности.

Рис. 5 Пример операционной трансформации

Текстовые редакторы, использующие ОТ, дают согласованные результаты, если соблюдают два свойства:

• Сохранение последовательности: если операция a произошла до операции b, она выполняется до неё.
• Конвергентность: все копии документа, находящиеся на разных клиентах, в конечном итоге оказываются одинаковыми.

Описанные выше свойства являются частью модели СС (Causal Сonsistency, причинная согласованность), используемой при совместном редактировании.

При этом у техники операционной трансформации есть два недостатка:

• Любая операция с символами может привести к изменению позиционного индекса, а значит порядок их выполнения имеет значение.
• Её сложно разрабатывать и реализовывать.

Операционная трансформация представляет собой набор алгоритмов, и её реализация в реальных проектах требует немалых усилий. Например, команде Google Wave для написания алгоритма ОТ потребовалось два года.

▍ Бесконфликтный реплицируемый тип данных (CRDT)

Этот принцип был разработал в качестве улучшенной альтернативы ОТ. CRDT (Conflict-free Replicated Data Type) имеет сложную структуру, но при этом является более простым алгоритмом.

Он выполняет условия коммутативности и идемпотентности за счёт применения к каждому символу двух ключевых свойств:

• Глобально уникального идентификатора.
• Глобального упорядочивания.

Теперь каждая операция имеет обновлённую структуру данных:

Рис. 6 Упрощённая структура данных CRDT

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

• PositionalIndex других символов не изменялся вследствие каких-либо операций.
• Исключить зависимость от порядка выполнения операций разными пользователями.

Пример ниже показывает, что пользователь с идентификатором области 123e4567-e89b-12d3 вставляет символ со значением A в PositionalIndex со значением 1.5. И хотя эта операция добавляет новый символ, позиционный индекс существующих символов сохраняется за счёт использования дробных значений. Таким образом исключается зависимость от последовательности выполнения операций. Как видно из примера, операция insert(), выполненная между O и T, не изменила позицию T.

Рис. 7 Устранение зависимости от порядка выполнения операций

CRDT позволяет обеспечить стабильную согласованность текста у разных пользователей. Даже если некоторые из них в момент внесения правок окажутся офлайн, когда они вернуться в сеть, хранящиеся на их устройствах локальные копии документа будут приведены к единому представлению.

И хотя популярные платформы для онлайн-редактирования документов вроде Google Docs, Etherpad и Firepad используют технику OT, CRDT значительно упростил одновременную работу над общими документами, в том числе повысив её согласованность. В действительности с помощью CRDT можно реализовать бессерверный одноранговый сервис для совместного редактирования текстов.

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

Итоги

▍ Согласованность

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

Нам также нужно сохранять согласованность документа между разными серверами датацентра. Для одновременного копирования и обновления его состояния в одном датацентре можно использовать одноранговые протоколы вроде Gossip. И такая стратегия повысит не только согласованность, но и доступность.

▍ Доступность

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

В добавок ко всему, наши WebSocket-серверы могут подключать пользователей к серверам, обслуживающим сессии, которые, в свою очередь, будут определять, работает ли пользователь с документом. Наконец, мы задействуем службы кэширования и CDN (Content Delivery Network, сеть доставки содержимого) для повышения доступности в случае сбоев.

▍ Масштабируемость

За счёт использования архитектуры микросервисов мы с лёгкостью сможем масштабировать отдельные компоненты, если вдруг число запросов в очереди операций начнёт превышать ёмкость какого-либо из них. В этом случае каждая очередь операций будет связана с одним документом. Мы можем перенаправлять операции, запрошенные разными пользователями, связанными с одним документом, в отдельную очередь. В итоге число созданных очередей будет равно количеству активных документов. Таким образом мы реализуем горизонтальное масштабирование.