Совместное редактирование несколькими людьми всегда было функцией, которую мы не осмеливаемся затрагивать в PingCode Wiki из-за технических проблем. Тем не менее, сама технология совместного редактирования разрабатывалась в течение многих лет, и решение является относительно зрелым.Наша команда также завершила внедрение решения для совместного редактирования на основе редактора PingCode Wiki в только что завершившемся Q3.Поэтому мы хотели бы совместить наш технический отбор и практический опыт.Расскажите о моем понимании этой технологии.
Основное содержание основано на технологии совместного редактирования, а понимание развития и эволюции технологий также будет обсуждаться в середине.
сцена
Обычный сценарий, конфликт публикации страницы, такое взаимодействие действительно существовало в наших продуктах.
Два пользователя внесли изменения на основе одного и того же содержания статьи.Один пользователь публикует первым, а второй пользователь будет иметь такое напоминание при публикации.Хотя напоминания есть, это на самом деле недружелюбно к пользователям.
Решения для продукта обычно следующие три:
1. Пессимистическая блокировка - документ может иметь только пользователь в редактировании
2. Автоматически объединяйте контент и разрешайте конфликты
3. Совместное редактирование
Второе решение также сделано иностранными продуктами, это Gitbook.
Гитбуки также являются способом решения проблем.
Ниже приведен окончательный интерактивный скриншот нашего совместного редактирования продукта:
Основное взаимодействие при совместном редактировании выглядит следующим образом: вы можете видеть список соавторов и то, что каждый соавтор печатает, видеть, что они ввели в режиме реального времени, и мы даже можем напрямую общаться друг с другом, что может эффективно избежать конфликтов.
Хотя совместное редактирование, наконец, предоставляет пользователю этот интерфейс, оно поддерживается сложными технологиями, лежащими в его основе.Давайте посмотрим, как работает совместное редактирование.
Познакомьтесь с совместным редактированием
руководящая идеология: Система не обязательно должна быть правильной, она просто должна быть последовательной, и вам нужно приложить усилия, чтобы сохранить свое намерение.
Я думаю, что это предложение можно использовать в качестве руководящей идеологии для разрешения конфликтов при совместном редактировании.В нем кратко и ясно говорится об одном: обработка конфликтов при совместном редактировании не обязательно полностью верна, потому что изначально конфликт означает, что операции являются взаимоисключающими. ., оперативные намерения взаимоисключающих сторон не могут быть полностью сохранены. Самое главное в урегулировании конфликтов — обеспечить согласованность конечных данных обеих сторон, а затем стремиться поддерживать на этой основе свои соответствующие оперативные намерения.
Поговорим о модели данных Rich Text.
Совместное редактирование — это технология, основанная на редакторе форматированного текста. Ее реализация в определенной степени зависит от структуры модели данных форматированного текста. Вот две репрезентативные модели данных:
2012 Перо -> Дельта
Шифер 2016 -> JSON
Дельта-модель данных
Редактор Quill, показывающий фрагмент текста
Его представление данных выглядит так
Он определяет три операции (вставка, сохранение, удаление).Каждая запись операции, сгенерированная редактором, сохраняет соответствующие данные операции, а затем выражает форматированное текстовое содержимое с помощью серии операций, а список операций является конечным результатом.
Модель данных Slate (JSON)
Определение модели:
В редакторе есть узел типа изображения, соответствующая структура данных
операция модификации свойства
Мы видим, что, хотя выражения данных Delta и Slate различны, все они имеют одну общую черту, то есть модификации данных могут быть выражены объектами операций, которые могут передаваться в сети для достижения обновлений контента на основе операций. Это основа для совместного редактирования.
В следующей части я хочу рассказать об основных проблемах, возникающих при реализации совместного редактирования.
Проблемы, с которыми сталкиваются совместное редактирование
Здесь мы сначала поднимем вопрос и покажем вам конкретные сценарии проблем, с которыми сталкивается совместное редактирование, начиная с проблемы, а затем обсуждая решение.
Проблема 1: Проблема грязного пути
Если в редакторе три абзаца, как показано на следующем рисунке
Здесь три приведенных выше абзаца просто моделируются с помощью массива.На следующем рисунке показана последовательность операций, сгенерированных двумя пользователями, изменяющими данные одновременно.
Вы можете видеть, что позиция вставки абзаца «Testhub», вставленного слева, неверна.
Вверху находится исходная структура данных, левая и правая части представляют собой последовательность операций двух пользователей, и их состояния в начале одинаковы. Пользователь слева вставляет новый абзац «Доступ» в позицию Index = 2, а пользователь справа вставляет новый абзац «Testhub» в позицию Index = 4. После того, как они применили свои собственные операции, они соответственно передать операцию через службу сообщений.Для другой стороны, когда пользователь слева получает синхронизированное сообщение от пользователя справа «Вставить Texthub в индекс = 4», результат слева появится, когда прямое приложение Этот результат несовместим с первоначальным намерением пользователя и согласуется с окончательными данными справа.
Причина в том, что операция вставки, выполняемая пользователем слева, вызывает изменение индекса данных, стоящих за ней, а прямое приложение, основанное на синхронизированной операции, вызовет исключение на приведенном выше рисунке, которое я называю проблемой грязного пути. .
Проблема 2: Проблема конфликта параллелизма
Здесь представленная выше структура данных изображения используется в качестве примера для иллюстрации проблемы конфликтов параллелизма.На следующем рисунке показан процесс решения проблемы.Для удобства выражения узел изображения сохраняет только два поля: тип и выравнивание.
Верхняя структура данных показывает двух пользователей, начинающих с одного и того же состояния, выравнивание изображения = 'центр'.
Пользователь слева изменяет атрибут выравнивания на левый, а пользователь справа изменяет атрибут выравнивания на правый.Согласно обработке по умолчанию, они передают свои соответствующие операции друг другу через службу сообщений, что приведет к окончательному отображению слева, чтобы быть справа, и окончательное отображение справа слева, и данные несовместимы.Эта ситуация называется конфликтом параллелизма, они изменяют одно и то же свойство на основе одной и той же позиции.
Вопрос 3: проблема отмены/возврата
Суть проблемы undos/redos по-прежнему заключается в упомянутой выше «проблеме грязного пути» + «проблеме конфликта параллелизма», но сценарии, в которых возникает проблема, несколько отличаются и относительно сложны, поэтому здесь они представлены отдельно.
Это все еще операция с данными из предыдущей «проблемы грязного пути». Здесь мы смотрим только на правую часть и анализируем ее стек отзывов:
Список действий пользователя справа:
Стек отмены правого пользователя (последовательность обратная из списка действий):
① Удалить узел в позиции Index=2
② Удалить узел в позиции Index=4
На самом деле существует проблема с реализацией этой логики вывода. Причина в том, что триггер (Происхождение) операции, соответствующей операции вывода ①, является пользователем слева. Если пользователь слева выполняется в соответствии с этой логикой вывода, пользователь слева может быть сбит с толку: «Что случилось с контентом, который я только что ввел? Хватит!», хотя это можно объяснить логически, это не соответствует привычкам использования пользователя, поэтому для сценариев совместного редактирования:Снятие должно отозвать только свою собственную операцию, операция соавтора должна быть проигнорирована.
Пользователь справа отзывает версию восстановления стека:
① Удалить узел в позиции Index=4
Видно, что стек отзыва включает только операцию справа, но это приводит к другой проблеме. Если вы внимательно посмотрите, вы обнаружите, что узел, соответствующий индексу = 4, — это «План». В это время «План " будет удален при отзыве. Фактическим узлом, вставленным пользователем справа при вставке, является "Testhub", и снова появляется грязный путь.
В дополнение к этой проблеме «грязного пути» аналогичным образом возникнет проблема «конфликта параллелизма», и конкретная логика не будет подробно анализироваться.
После того, как стек отвода проигнорирует операцию координатора, путь операции в стеке отвода будет иметь проблему «грязного пути» + проблему «конфликта параллелизма».
Вопрос 4: Проблема лендинга проекта
Эту проблему легко понять, то есть конкретную проблему приземления совместного редактирования:
- Синхронизация операций
- синхронизация курсора
- Сетевой агностик (дрожание сети, задержка в сети, переподключение сообщений и обработка различных ситуаций после переподключения)
- История версий документа
- Изменить офлайн
- ...
Кратко суммируя проблемы, упомянутые выше, по сути, их можно разделить на две категории:
Первая категория: в основном включает грязные пути, конфликты параллелизма, отмены/возвраты и т. д., которые в совокупности можно назватьПроблемы согласованности данных, это относится к категории академических задач, потому что результаты разрешения параллельных конфликтов должны быть гарантированы.конечная согласованность данных, это требует большого количества академических исследований и демонстраций.
Вторая категория: инженерные проблемы, основное внимание уделяется реализации конкретного плана реализации на основе решения «консистентность данных».В дополнение к функциональным точкам разработки конкретных реализаций, упомянутых выше, необходимо решить вопросы производительности, вопросы эффективности передачи данных и т. д. , который на самом деле содержит большую рабочую нагрузку и является ключом к тому, действительно ли теоретические исследования могут быть реализованы в производственной практике.
Решение первого типа академической задачи состоит в следующем.Алгоритм согласованности данных, в академических кругах есть две основные области исследований: алгоритм OT и CRDT.
Ниже мы кратко представим эти два алгоритма.
Алгоритм согласованности данных
Я не буду слишком подробно рассказывать о деталях реализации алгоритма, а просто предложу его идеи по устранению конфликтов и способ взглянуть на него с точки зрения самой проблемы.Что касается конкретной реализации алгоритма, если вам интересно, вы можете пойти на Github, чтобы найти соответствующую информацию.Попрактикуйтесь сами.
OT
Полное название ОТ — Operational Transformation, его основной идеей является операционная трансформация, которая решает различные задачи в совместном редактировании посредством трансформационных операций модификации данных.
История развития
OT - это самый ранний (1989 г.) предложенный алгоритм совместного разрешения конфликтов.
2006 был применен к документам Google
применяется в 2011 году
Office 365
Пока что OT по-прежнему является наиболее важным техническим выбором для совместного редактирования.Решения OT по-прежнему используются в документах Google и Office 365. Некоторые продукты для работы с документами, появившиеся в Китае в последние годы, включают Graphite, DingTalk, Tencent Docs и т. д. Их технология совместного редактирования также основан на ОТ.
Главная мысль
Как и его название, его основная идея состоит в том, чтобы преобразовать параллельные операции, созданные при совместном редактировании пользователя, и преобразоватьКонфликт параллелизмаа такжегрязный путьВнесите исправления, а затем повторно примените исправленные операции к документу, чтобы обеспечить правильность операций и возможную согласованность данных.
Схема
Основной принцип ОТ можно представить в виде ромбовидной диаграммы.
Левый рисунок поясняет:
- a идентифицирует операцию пользователя слева
- b представляет операцию пользователя справа
- Точка, в которой они пересекаются, указывает на то, что документ основан на одном и том же начальном состоянии.
левое государство:
После того, как пользователи с обеих сторон применяют операции a и b соответственно, содержимое документов на обеих сторонах изменяется и становится несогласованным;
Преобразование операции:
Чтобы добиться согласованного состояния для левого и правого документов, нам нужно выполнить операционное преобразование transfrom(a, b) => (a', b') над a и b, чтобы получить две производные операции как a' и b ' .
Результат применения операции трансформации на изображении справа:
Производная операция a' от операции a' слева применяется справа, а b' применяется слева, и окончательное содержимое документа является согласованным.
Это только самая базовая модель ОТ, случай, когда у каждого клиента есть только одна операция (1:1), случай, когда каждому клиенту соответствует несколько операций (M:N), и алгоритм управления ОТ и т.д. А в реальной реализации ОТ возможно, что каждое преобразование операции получит только одну производную операцию (преобразование операции, определяемое ottypes, таково), которая несколько отличается от предыдущих преобразований, но это не особо важно. реализуя его, вам нужно тщательно его понять.Здесь описание - это только самая основная идея алгоритма ОТ.
Решение проблемы «грязного пути» с помощью OT
Как показано на рисунке выше, OT добавляет уровень логики преобразования операций в процессе синхронизации операций для исправления грязных путей, созданных параллельными операциями.
Индекс преобразуется из 4 в 5, когда левая синхронизируется с правой операцией..
Анализ логики преобразования операции:
Для левых пользователей:
Поскольку до поступления совместной операции «Вставить Testhub в индекс = 4» была выполнена локальная операция «Вставить доступ в индекс = 2», а индекс локальной операции «Индекс = 2» меньше, чем индекс совместной операции «Индекс». =4, поэтому совместная операция Индексный путь должен быть дополнен длиной вновь добавленного узла, которая равна 1, а индекс изменится с 4 на 5.
Для пользователей справа:
Поскольку индексный путь совместной операции меньше, чем индексный путь локальной операции, локальная операция не влияет на совместную операцию, поэтому преобразование не требуется, и можно напрямую применить исходную операцию.
Решить проблему «конфликта параллелизма» с помощью OT
Видно, что решение «конфликтов параллелизма» на основе OT также использует логику преобразования операций, но на этот раз преобразование операций преобразует не грязные пути, аСогласование конфликтующих модификаций атрибутов, предполагается, что результат обработки приведенного выше рисунка достигает сервера после операции справа,Окончательный результат свернут для отображения справа.
Из анализа двух приведенных выше сценариев видно, что процесс преобразования операции не слишком сложен, хотя в реальных сценариях необходимо учитывать больше ситуаций, но это уровень логического преобразования. Существует также реальная сцена, в которой необходимо выполнить преобразование между операциями для каждого типа операции.Например, Delta поддерживает три операции, поэтому он может поддерживать преобразования операций 3 * 3, а Slate поддерживает 9 атомарных операций, и может потребоваться реализовать 9 *9 Этот вид преобразования операции, сложность, вероятно, такова.
OT для решения проблемы отмены/возврата
Как упоминалось ранее, проблема отмены/возврата — это, по сути, проблема «грязного пути» + «конфликта параллелизма», поэтому решение ОТ состоит в том, что когда редактор получает совместную операцию, ему необходимо выполнить операции над всеми операциями в стеке отмены и Повторите стек в цикле.Логика преобразования, когда отмена или повтор наконец выполняются, является преобразованной операцией, и конкретная логика здесь не будет повторяться.
Алгоритм Описание
Можно видеть, что OT заключается в преобразовании данных операции редактора, поэтому реализация алгоритма OT зависит от дизайна модели данных редактора, и разные модели данных должны реализовывать разные алгоритмы преобразования операций.
Алгоритм OT, вероятно, здесь, давайте посмотрим, как CRDT справляется с проблемой согласованности данных.
CRDT
CRDT (Conflict-free Replicated Data Type) означает "Бесконфликтно-реплицированный тип данных". Он в основном используется в распределенных системах для обеспечения согласованности данных распределенных приложений. Совместное редактирование документов можно понимать как тип распределенного приложения. Его суть является структурой данных, и окончательная согласованность данных параллельных операций гарантируется за счет конструкции структуры данных.
CRDT был официально предложен в 2011 году. Фреймворк для совместного редактирования Yjs на основе CRDT был открыт примерно в 2015 году. Yjs специально разработан для создания приложений для совместной работы в Интернете.
Главная мысль
Большинство CRDT присваивают уникальный идентификатор каждому символу, созданному в документе.
Чтобы гарантировать, что документ всегда сходится, модель CRDT сохраняет метаданные даже при удалении символов.
Первоначально CRDT был предложен для решения окончательной согласованности данных распределенных систем.Он поддерживает прямую синхронизацию модификации данных между каждой репликой хоста, а порядок синхронизации модификации данных и количество синхронизаций не влияют на окончательный результат. операции модификации непротиворечивы, данные. Конечное состояние CRDT непротиворечиво, то есть обычно говорят, что коммутативные и идемпотентные свойства данных CRDT выполнены.
Краткое введение в то, как CRDT обрабатывает конфликты
На следующем рисунке показана модель алгоритма обработки конфликтов в Yjs, которая представляет собой модель обработки конфликтов, поддерживающую двухточечную передачу.
Основное описание картинки выше
- Нижняя буква «AB» обозначает начальное состояние.
- Каждая строка выше представляет операцию вставки
- Каждая операция имеет уникальный идентификатор
Например, 0,0 в операции C0,0 является идентификатором
Первый 0 указывает номер пользователя
Второй 0 указывает последовательность операций
Например, следующий идентификатор означает, что пользователь 0 вставляет «C» между «A» и «B».
C0,0
Тот же пользователь пользователя 0 вставляет «D» между «B» и «C», можно использовать следующую операцию.
D0,1
В это время другой пользователь ожидает вставки «E» между «A» и «B», но эта операция является параллельной операцией с предыдущей операцией (C0, 0) вставки «C».
В этот момент уникальный идентификатор пользователя должен отличаться от предыдущего, но часы должны быть похожи на предыдущую операцию вставки:
E1,0
Из-за конфликтов параллелизма Yjs выполняет то же разрешение конфликтов, что и OT, и сравнивает соответствующие вставленные идентификаторы пользователей.
Поскольку идентификатор пользователя 1 больше 0, результирующий документ будет следующим:
ACDEB
Вышеприведенное представляет собой введение алгоритма Yjs для решения конфликтов параллелизма. На самом деле это нетрудно понять. Прежде всего, его операция вставки основана на относительном положении существующих символов, что эквивалентно абсолютному положению, основанному на на индекс, используемый в OT, а затем обработка конфликтов, в основном это сравнение идентификаторов пользователей, сначала применяются идентификаторы с меньшими, а затем применяются те, у которых больше.
Вышеприведенное использует Yjs в качестве примера для представления модели обработки конфликтов CRDT.Давайте посмотрим, как CRDT решает проблемы, поднятые выше.
Решите проблему грязного пути с помощью идеи CRDT
Сначала мы опишем только что полученный массив аналогично CRDT:
Видно, что список справа заменяет индекс исходного массива на уникальный Id, а затем соответствующим образом корректируется операция описания модификации контента.
Операция слева:
Вставить доступ по индексу = 2 -> Вставить доступ после 111
Правильная операция:
Вставить Testhub в индекс = 4 -> Вставить Testhub после 333
Окончательная структура данных слева и справа должна быть одинаковой после операции синхронизации:
Поскольку это просто для имитации CRDT и объяснения идеи CRDT, настоящий CRDT обычно использует двусвязный список.Для лучшего понимания мы по-прежнему используем здесь массив, но добавляем уникальный идентификатор к данным узла каждого абзаца в массиве. .
CRDT разрешает конфликты параллелизма
Вот пример установки свойства align изображения.Во-первых, давайте посмотрим, как CRDT описывает свойства объекта и модификации свойств:
Слева — модель данных изображения, а справа — структура данных, соответствующая смоделированному CRDT. Каждое поле в объекте изображения использует объект структуры для описания содержимого и модификации содержимого. Здесь представление поля выравнивания привык видеть его выражение.
Операция ①:
Верхняя синяя часть указывает на то, что начальное значение align равно center, а (140, 20) — это идентификатор этой исходной структуры данных, который также генерируется на основе операции пользователя.
В это время пользователь выполнил операцию ①, изменил свойство выравнивания на левое и сгенерировал новый объект структуры, который представляет собой оранжевую часть на рисунке. После завершения операции поле выравнивания на карте указывает на вновь сгенерированный объект структуры с идентификатором (141,0), поскольку объект структуры (141,0) изменяется на основе (140,20), поэтому его левый указатель указывает на (140,20) этот объект структуры.
В этом примере будет некоторая двусмысленность, то есть сама структура данных связанного списка будет иметь два указателя слева и справа (слева и справа от объекта структуры), и тогда средняя часть будет собственно содержимым, но мой контент хранит свойство align изображения, его значение может быть левым, центральным, правым, что может вызвать путаницу с левым и правым указателями связанного списка.Под отметкой здесь второй блок в структуре описывает объект содержание свойства.
Операция ②:
В это время другой пользователь выполнил операцию на основе только что сгенерированного объекта структуры (141,0) ②, изменил атрибут выравнивания вправо и сгенерировал новый объект структуры, который представляет собой оранжево-красную часть на рисунке. .
Нижняя часть картинки - итоговая структура данных после этих двух операций, это выражение двусвязного списка (это выражение очень близко к реальной структуре данных Yjs), оно может не только описывать конечное состояние данных ( справа), но и порядок изменения данных может быть выражен: по центру -> слева -> справа.
Этот пример фактически описывает последовательные операции.Состояние, основанное на каждой операции, является последним состоянием, а операции, выполняемые двумя пользователями, находятся в определенном порядке.
Давайте посмотрим на структуру данных, сгенерированную, когда два пользователя одновременно выполняют изменение атрибута:
Самое большое отличие от предыдущего заключается в том, что состояние, основанное на операции выполнения ②, и операция выполнения ① одинаковы, и все они изменяются на основе align = 'center', что выражает модификацию параллельных данных. Далее следует логика параллельной обработки, которая согласуется с предыдущим введением.В настоящее время соответствующий идентификатор пользователя 141 операции ① меньше, чем соответствующий идентификатор пользователя 142 операции ②, поэтому сначала применяется операция ①, а затем операция ② применяется, поэтому атрибут выравнивания конечного изображения имеет статус «Правильно».
CRDT решает проблему отмены/возврата
CRDT можно понимать как отсутствие проблемы «грязного пути» вообще, и тогда проблема конфликтов параллелизма также может быть решена на основе идентификатора CRDT (временной метки), тогда в решении на основе CRDT должно быть относительно просто реализовать отмену/возврат, только нужно. Проблема может быть эффективно решена путем реализации стека отмен/возврата в соответствии с добавлением или удалением структуры данных CRDT. Если выполняется операция по созданию объекта структуры, он может быть помечен для удаления при выводе.
Если выполняется операция удаления объекта структуры, операция отзыва может соответствовать повторному выполнению операции вставки объекта структуры.
Описание алгоритма CRDT
В отличие от OT, CRDT — совершенно новое решение. Оно не зависит от реализации редактора. Для любой модели данных редактора для обработки конфликтов можно использовать набор структур данных CRDT. также может Он не зависит от централизованных серверов и обладает высокой стабильностью. Это отличается от OT. OT можно понимать как обеспечение согласованности данных посредством управления алгоритмом. CRDT обеспечивает согласованность данных посредством проектирования структуры данных. Его обработка в сложных сетевых средах. Надежный. Стоимость CRDT заключается в сохранении большего количества метаданных, что приведет к определенному потреблению памяти, но это можно оптимизировать. Оказывается, что в сценариях совместного редактирования эта стоимость совершенно незначительна.
Yjs-оптимизация
На самом деле, схема совместного редактирования, основанная на CRDT, всегда подвергалась сомнению, и до сих пор раздаются голоса вопрошания, и это также влияет на Yjs. Хотя Yjs, основанный на CRDT, уже настолько мощен, все все еще говорят о накладных расходах памяти и производительности CRDT.Согласно моему нынешнему пониманию: накладные расходы памяти и проблемы с производительностью больше не являются проблемой для Yjs, поэтому вот краткое введение. оптимизация Yjs, окончание этой части основано на официальном введении в оптимизацию Yjs.Есть много бенчмарк тестов для проверки каждой точки производительности и использования памяти.Здесь только краткое введение в методы оптимизации.
1. Оптимизация структурного представления
Когда пользователь вводит содержимое «ABC» слева направо, он делает следующее: вставка (0, «A») • вставка (1, «B») • вставка (2, «C»). Связанный список YATA CRDT, которые моделируют текстовое содержимое, будет выглядеть следующим образом:
Модель CRDT для вставки содержимого «ABC» (при условии, что у пользователя есть уникальный идентификатор клиента «1»). Все CRDT присваивают каждому символу какой-то уникальный идентификатор и дополнительные метаданные, что очень дорого для больших документов в ОЗУ. Мы не можем удалить метаданные, так как это необходимо для разрешения конфликтов.
Yjs также однозначно идентифицирует каждый символ и присваивает метаданные, эффективно представляя эту информацию. Вставки документов большего размера представляются как один объект Item с использованием смещения символов для уникальной идентификации каждого символа в отдельности.
Тогда есть место для оптимизации.Следующий элемент также может однозначно идентифицировать символ «A» как {client:1,clock:0}, символ «B» как {client:1,clock:1} и т. д. .....
Item {
id: { client: 1, clock: 0 },
content: 'ABC',
length: 3,
...
}
Если пользователь копирует/вставляет большое количество содержимого в документ, вставленное содержимое представляется одним элементом. Кроме того, односимвольные вставки, написанные слева направо, могут быть объединены в один элемент. Важно отметить, что мы могли разделять и объединять элементы без потери метаданных.
Это представлено оптимизацией данных Yjs, таким образом, она может эффективно уменьшить количество структур Yjs структуры данных объекта, тем самым эффективно уменьшая объем памяти.
Однако наиболее важным недостатком этого подхода является то, что становится сложнее обрабатывать отдельные символы (это нормально, поскольку это то, что делает инфраструктура Yjs).
Когда другой пользователь хочет вставить символ между «B» и «C», часть действия «BC» необходимо разделить на два отдельных действия. Мы не можем перегруппировать эти операции, потому что в CRDT мы никогда не можем удалять символы или удалять их из дерева документа.
Во-вторых, удалите оптимизацию
Единственный способ, которым мы можем указать, что персонаж должен быть удален, — это пометить его как удаленный. Тем не менее, все еще есть место для оптимизации.В качестве примера возьмем структуру абзаца Slate.Когда вы помечаете абзац для удаления, вы также можете пометить все текстовые структуры под абзацем для удаления.
Например, абзац, содержащий текст «ABC», при пометке абзаца на удаление:
(Абзац) Д
Эквивалентно пометке всех следующих текстовых узлов (символов) для удаления:
AD BD CD
Это структура, для которой мы можем полностью удалить все узлы символов из памяти, потому что узлы символов являются дочерними элементами удаленного абзаца.
Основываясь на этом методе, объем памяти Yjs также может быть эффективно уменьшен.
3. Определение операции
Эта часть на самом деле предназначена для оптимизации создания структурных объектов Yjs с точки зрения V8.Общая идея состоит в том, чтобы позволить браузеру оптимизировать процесс создания объектов в Yjs, будь то использование памяти или скорость создания объекта.
В-четвертых, оптимизация запросов
Каждый должен знать, что самым большим недостатком двунаправленного списка является производительность запроса, потому что для каждой операции вам нужно пройти весь связанный список, чтобы запросить структурный объект, когда данные объекта структуры YJS очень велики, каждая операция выполнения может быть потеряна. В течение определенного времени YJS также оптимизирован.В настоящее время я вижу из исходного кода.YJS будет кэшировать структурные объекты, которыми часто пользуются пользователи (фактически, расположение кеша), приоритет в процессе поиска.Сопоставление, вызывая удар, вы можете эффективно улучшить скорость запроса данных.
5. Оптимизация кодирования
Yjs будет выполнять унифицированное двоичное кодирование объектов структуры, передаваемых в сети и хранящихся в базе данных.Конечно, он также будет обеспечивать соответствующие операции декодирования.Благодаря двоичному кодированию эффективность передачи данных может быть эффективно повышена.
OT vs CRDT
Часть алгоритма OT и CRDT находится здесь, а ниже описан план реализации проекта на основе алгоритма OT и CRDT в реальной разработке.
решения с открытым исходным кодом
Здесь в основном представлены два решения: одно — решение ShareDB на основе OT, а другое — решение Yjs на основе CRDT.
SharedB-решение
На самом деле в сообществе всегда было соответствующее решение для ОТ — sharedb, но, к сожалению, нет четкого решения, как совместить slate и sharedb, я поискал на Github и обнаружил, что некоторые люди его изучали, но оно нацелено на более старый шифер.Версия почти не поддерживается, но ее реализация дала мне некоторые идеи, и с первоначальным пониманием у меня есть текущее решение: slate + ottype-slate + sharedb.
ShareDBShareDB — это набор решений для совместного редактирования на основе OT, обеспечивающих совместную пересылку сообщений, синхронизацию курсора, сохранение данных, алгоритмы управления OT и многое другое.
Схема архитектуры ShareDB выглядит следующим образом.
Светло-голубая часть ниже — это основные модули, включенные в ShareDB.ShareDB предоставит реализацию службы сообщений на основе WebScoket и соответствующий пакет SDK для службы сообщений внешних ссылок, который может синхронизировать операции и курсоры.ShareDB также включает реализацию сохраняемости данных часть.
Самый левый OTType является основной частью преобразования операции.Поскольку модели данных разных редакторов должны реализовывать отдельные алгоритмы OT, сама ShareDB не содержит реализаций OT, но предоставляет стандартный интерфейс доступа.Любой тип данных, основанный на этом интерфейсе, реализует соответствующую операцию алгоритм преобразования, то его можно подключить к ShareDB через регистрацию.Определение этого стандартного интерфейса может ссылаться на реализацию в ottypes.
Фиолетовая часть выше — это редактор, который в настоящее время может поддерживать ShareDB.Последняя задача для доступа к редактору — реализовать OTType на основе модели данных редактора, а затем модель данных Delta самого редактора Quill реализует преобразование операции. , так что доступ к Quill проще всего.
ottypes
Упомянутые выше ottypes на самом деле являются стандартным интерфейсом OT.Преобразование типов, реализованное в соответствии с этим стандартом, может быть прекрасно использовано в сочетании с ShareDB для завершения совместного редактирования данных.Как упоминалось в предыдущей схеме, ottype-slate на самом деле является реализацией ottypes .
ottype-slate
Лично я чувствую, что модель данных и преобразование данных, определенные в slate, очень удобочитаемы, его выражения и функции инструментов очень ясны и полны, а каждая атомарная операция обратима.Я, вероятно, видел поддержку по умолчанию sharedb.Преобразование операций на основе JSON реализации (ot-json0), выражение ot-json для модификации данных по-прежнему очень удобочитаемо, поэтому я чувствую, что могу написать реализацию OTType для модели данных планшета, поэтому яottype-slate.
В настоящее время ottype-slate только первоначально реализовал некоторые функции преобразования операций, а затем объединил slate-angular и sharedb для создания совместно редактируемой тестовой демонстрации, а оставшаяся часть функций преобразования операций будет добавлена позже.
Блок-схема сценария ShareDB
Исходя из вышеизложенного, если пользователь осуществляет совместное редактирование на основе редактора Slate, можно увидеть, что операции, сгенерированные модификацией пользовательского контента, могут подвергаться преобразованию операции перед передачей на сервер ShareDB, в зависимости от версии документа и сервера. документ, на котором основана операция.Независимо от того, согласуются ли версии или нет, необходимо вычислить некоторые операции различия между двумя версиями, преобразовать операцию различия с вновь сгенерированной операцией и синхронизировать модификацию контента на основе результат преобразования операции.После этого процесса окончательная операция передается через службу сообщений, которая перенаправляется другим клиентам, и другие клиенты применяют эту операцию для реализации совместного редактирования.
Из этого процесса видно, что преобразование операции может в конечном итоге выполняться на стороне сервера или на стороне клиента. Поскольку процесс преобразования операции должен реализовать координацию преобразования операции с несколькими клиентами с помощью алгоритма управления OT, этот процесс должен проходить через централизованный сервер, в противном случае процесс трудно контролировать, поэтому это решение, основанное на алгоритме OT, не может реализовать точечный точечная связь.
Yjs решение
Yjs — это решение с открытым исходным кодом, основанное на CRDT, которое обеспечивает относительно полную экосистему.В 2020 году сообщество также появилось в среднем слое привязки на основе редактора Slate.
Схема архитектуры Yjs
y-websocket — обеспечивает обмен сообщениями во время совместного редактирования, включая SDK для реализации на стороне сервера и интерфейсной интеграции.
y-протоколы — определение протоколов передачи сообщений, включая инициализацию службы сообщений, обновление контента, аутентификацию, систему восприятия и т. д.
y-redis — сохранять данные в Redis
y-indexeddb — сохранить данные в IndexedDB
На верхнем уровне Yjs поддерживает доступ большинства основных редакторов, потому что Yjs также можно понимать как набор независимых моделей данных, которые отличаются от моделей данных каждого редактора, поэтому каждый редактор, желающий получить доступ к Yjs, должен реализовать промежуточный уровень привязки для преобразования модели данных редактора и модели данных Yjs. Это преобразование является двунаправленным. В настоящее время официальный предоставляет промежуточные уровни привязки для таких редакторов, как Prosemirror, Quill и Ace, на основе редактора Slate. Предоставляется промежуточный уровень привязки от разработчиков сообщества.
Блок-схема схемы Yjs
Описать процесс синхронизации пользовательских операций сверху вниз.Если вышеуказанный пользователь изменяет какие-то данные на основе редактора Slate, сгенерированные операции необходимо преобразовать в модификацию данных Yjs через Yjs Bindings (используя applySlate), обновить локальную структуру данных Yjs , когда структура данных Yjs изменена, она может синхронизировать изменения структуры данных с соавтором через протокол сетевой передачи, и соавтор напрямую применяет удаленные данные для синхронизации с локальной структурой данных Yjs, а затем происходит подписка операция в Yjs Bindings, которая заключается в том, чтобы подписаться на удаленную модификацию данных Yjs, а затем преобразовать выражение модификации данных Yjs в операции Slate с помощью метода applyYjs. Наконец, Slate использует эту операцию для достижения синхронизации контента и проблемы промежуточных конфликтов параллелизма Он полностью передается в структуру данных Yjs для обработки, и операция преобразования в Slate всегда согласуется с результатом обработки Yjs.
Из блок-схемы видно, что каждый клиент поддерживает копию структуры данных Yjs.Содержимое, выраженное этой копией структуры данных, точно такое же, как содержимое, выраженное данными редактора Slate, но у них разные обязанности. Данные Slate предназначены для редактирования. Структура данных Yjs используется для обработки конфликтов и обеспечения согласованности данных. Наконец, изменение данных синхронизируется через структуру данных Yjs.
Стоит отметить, что сама структура данных Yjs поддерживает прямую синхронизацию сквозных данных без необходимости использования централизованного сервера.
PingCode Wiki Совместный выбор решения
В 2021 году технологии должны были измениться, и решение для совместного редактирования должно быть не только OT.Давайте кратко поговорим о наших соображениях при выборе технологии.
В третьем квартале этого года наша команда официально приступила к совместному редактированию. Наш редактор основан на платформе Slate. Хотя до этого у меня были некоторые исследования по совместному редактированию, они не носили систематического характера, поэтому мы повторили это в начале третьего квартала. В исследовании основной вопрос заключается в том, что выбрать: OT или CRDT.
ОТ решение
- Редактор TinyMCE реализует совместное редактирование на основе модели Slate + OT, но их исходный код не является открытым.
- Все решения для совместного редактирования крупномасштабных продуктов реализованы на основе OT.
- Для ОТ я тогда просто понял идею, но не знал, как ее реализовать, точнее, не знал, какие базовые модули должны быть включены в совместное редактирование.
Схема CRDT
- У сообщества всегда были некоторые сомнения по поводу CRDT.
- В CRDT отсутствуют варианты использования (классы документов) для коммерческих продуктов.
- Экология Yjs относительно полная, на основе редактора Slate со зрелой демонстрацией.
- Перевел некоторые технические материалы Yjs и получил хорошее впечатление от Yjs
- На основе нашего редактора мы создали демо-версию Yjs для совместного редактирования, которая может выполняться через
Демонстрационные скриншоты, предоставленные slate-yjs, которые были исследованы в то время, следующие:
Можно сказать, что эта демонстрация очень функциональна, и стек технологий в основном соответствует нашему. Хотя есть некоторые сомнения в сообществе CRDT, факты всегда нуждаются в проверке.Из-за идеальной демонстрации Yjs и ее первоначального впечатления мы решили попробовать в соответствии с планом Yjs.
Это в основном процесс нашего выбора, потому что процесс очень плавный, во-первых, наша экологическая среда на основе YJS быстро создала первоначальную версию совместного редактора в тестовой среде и постепенно обеспечила основу новостной службы, предоставляемой официальным Повторная реализация нашей собственной службы сообщений, а также аутентификация, а затем на основе некоторых деталей постепенного расследования и исправления совместного редактирования, включая контроль подключения службы сообщений, проблему отмены / возврата, блокировку бомбы обработка и т. д. Это не слишком большая проблема, и производительность в основном без потерь, загрузка большого документа (около 5-6 миллионов слов) YJS может в основном перейти на миллисекундный уровень.
Глядя на выбор плана Yjs еще раз, я думаю, что наш выбор этого плана очень правильный.В этом процессе мы не тратили время команды, и в процессе совместного редактирования в Q3 все были очень расслаблены, и на Yjs Мы все еще можем многому научиться, вот некоторые из преимуществ Yjs с точки зрения функциональности и дизайна, которые я суммировал:
Функционально:
- Разработана идеальная система восприятия, и пользователи могут синхронизировать онлайн-статус пользователя, положение курсора и т. д.
- Поддержка автономного редактирования
- Не зависит от сети, может очень надежно справляться с дрожанием сети, задержкой сети и другими проблемами
- Обеспечивает управление отменами/повторами
- История версий
По дизайну:
- Обязанности модулей четко разделены, особенно извлечение независимой библиотеки протоколов y-протоколов делает синхронизацию сложных сообщений очень понятной и управляемой.
- Сетевой протокол/постоянство данных Реализовать слабую связь, сетевые протоколы поддерживают доступ к y-websocket, y-webrtc, постоянный y-redis и y-mongodb, предоставляемый сообществом
- Может быть быстро интегрирован с любым редактором
Можно сказать, что значение Yjs для нас сейчас такое же, как значение Slate для нас два года назад.На данном этапе важно понять и изучить совместное редактирование.Что включает в себя совместное редактирование и что каковы проблемы?Yjs, как это решить, каковы недостатки Yjs, как он оптимизирован и т. д., как учитель, чтобы помочь вам с вашей работой, а затем сделать вас прогрессировать в этом процессе.
Расскажите об эволюции технологий
Алгоритм OT 1989 года официально предложен от имени технологии совместного редактирования, но в то время редактор архитектурного дизайна сильно отстает от текущего уровня, его философия должна быть очень продвинутой в то время, и теперь совместное редактирование эволюции данных модель, я думаю, что алгоритм OT также в определенной степени влияет.
В 2006 Google внедрил OT в коммерческие продукты.Этот процесс занял около десяти лет.Затем в 2011 Microsoft реализовала совместное редактирование на основе OT.На это ушло около 5 лет в середине.Я думаю этот промежуток времени Это должно быть как-то связано с Технический опыт редактора в то время Фактически, технология совместного редактирования была разработана и применена только в этих ведущих технологических компаниях в этот период.
Алгоритм CRDT, предложенный в 2011 году, представляет собой появление новой схемы совместного редактирования.
В 2012 году исходный код редактора Quill был открыт, а его модель данных Delta была разработана на основе алгоритма OT. Лично я считаю, что открытый исходный код редактора Quill является важной вехой для совместного редактирования и разработки OT. , совместное редактирование могло быть исследовано несколькими крупными компаниями. После редактирования Quill совместное редактирование постепенно применяется к продуктам малых и средних компаний. Например, вся основная технология домашних графитовых документов, включая совместное редактирование, может быть на основе Quill и Delta.
ShareDB была открыта в 2013 году, представляя полное решение, основанное на OT.
В 2015 году открытый исходный код Yjs представлял собой официальную разработку решения для совместной работы на базе CRDT. В 2019 году фреймворк Slate был полностью переработан на основе TypeScript, а его модель данных была дополнительно оптимизирована. Теперь она предельно лаконична и элегантна. Я думаю, что это также является изменением.
В 2020 году slate-yjs будет с открытым исходным кодом.Это комбинация Yjs и Slate. Благодаря этой комбинации на самом деле существует полное решение для совместной работы на основе Slate.
2021 Я думаю, что мы выбрали YJS также очень разумно в это время, выберите другой период технологии, должны быть разными.
Здесь я хочу добавить, что алгоритм OT на самом деле является совместным редактированием, основанным на существующей модели данных редактора. Его идея также хорошо понятна. На самом деле, наоборот, проблема непротиворечивости данных, с которой сталкивается совместное редактирование, теперь является частью причина вызвана выражением «операции модификации данных» в модели данных, например, проблемой грязного пути, вызванной основанным на индексе способом поиска данных, подлежащих изменению в операции модификации данных. Короче говоря, OT может понять существующие технические идеи.с решением. Тогда CRDT на самом деле является решением, независимым от существующей архитектуры редактора.Это техническое нововведение.Он предлагает новую идею для совместного редактирования и имеет множество отличных функций, таких как поддержка синхронизации данных точка-точка и структура данных. Обработка конфликтов на основе на самом деле более надежна.Хотя структуру данных на основе CRDT сложнее реализовать, эта сложность может быть полностью устранена на уровне структуры.Может быть нечувствительным.
окончание
Эта статья на самом деле представляет собой тематическое содержание, подготовленное для «Конференции разработчиков PingCode 2021», проводимой нашей компанией в этом году, и затем я действительно хочу организовать содержание совместного редактирования и воспользоваться этой возможностью, чтобы сделать это вместе, в основном это излагает мое понимание этой технологии, включая то, что такое совместное редактирование, некоторые проблемы или проблемы, возникающие при совместном редактировании, и то, как работают основные алгоритмы обработки конфликтов при совместном редактировании, а затем более поздние алгоритмы обработки на основе конфликтов.Большинство технологий, упомянутых здесь, на самом деле открыты На самом деле, я очень восхищаюсь участниками этих работ с открытым исходным кодом, и я также призываю себя усердно работать, чтобы делать больше продукции с открытым исходным кодом.
Адрес открытого проекта:
GitHub.com/quill — это просто /qui…
github.com/ottypes
GitHub.com/Выполнение водопада…
GitHub.com/QQ — это ee/slate…
GitHub.com/share/share…
github.com/yjs/yjs
Справочная статья
OT
Оперативное преобразование SharedPen
This Is How to Build a Collaborative Text Editor Using Rails
Принципы и практика совместного редактирования — Sandbar
Yjs
Yjs — платформа для совместной работы с данными на основе CRDT.
Yjs deep dive: How Yjs makes real-time collaboration easier and more efficient
blog.Kevin JA трудно сказать. /are- куй железо, пока горячо- это…
Этот склад записал некоторую информацию, которую мы закончим, когда мы выполняем редактирование.