Аннотация
ПЕРЕЧЕНЬ СОКРАЩЕНИЙ И ТЕРМИНОВ 6
ВВЕДЕНИЕ 7
1 ПРЕДМЕТНАЯ ОБЛАСТЬ 9
1.1 Общая архитектура систем совместного редактирования текста 12
1.1.1 Централизованная (Client-Server) 12
1.1.2 Децентрализованная (P2P) 13
1.1.3 Гибридная 14
1.1.4 Архитектуры на основе Блокчейн (Blockchain) 15
1.1.5 Вывод 16
1.2 Дифференциальная синхронизация (Differential synchronization) 16
1.3 Операционная трансформация (Operational Transformation) 22
1.4 Бесконфликтный реплицируемый тип данных (conflict-free replicated
data type (CRDT)) 29
1.4.1 Last-Write-Wins-Element-Set СRDT (LWW-ES CRDT) 31
1.4.2 CRDTs предметной области 32
2 ИДЕЯ ПРЕДЛОЖЕННОГО АЛГОРИТМА 37
3 ПОСТАНОВКА ЗАДАЧИ 41
3.1 Цель 41
3.2 Задачи 41
4 РЕШЕНИЕ 42
4.1 Общая архитектура реализации 42
4.2 Архитектура ПО (модели данных) 44
4.3 Конфликты 46
4.4 Возникают проблемы 48
4.4.1 Размер буфера сообщений 48
4.4.2 Синхронность выполнения операций 48
4.4.3 Определение авторства операции 49
4.5 Предлагаемые решения проблем 49
4.5.1 Размер буфера сообщений 49
4.5.2 Синхронность выполнения операций 50
4.5.3 Определение авторства операции 50
4.6 Сравнение полученной реализации и известных аналогов 50
ЗАКЛЮЧЕНИЕ 53
ЛИТЕРАТУРА 54
В современном и быстро меняющимся мире, где удалённая работа и коллаборация становятся нормой, приложения с внедренными системами совместного редактирования текста играют очень важную роль. Они позволяют нескольким пользователям одновременно работать над одним проектом увеличивая плодотворность и скорость работы многократно.
Такие приложения обеспечивают:
• Прозрачность изменений: в таких приложениях легко можно
идентифицировать автора некоторых изменений и оставить комментарии на счет этих изменений.
• Минимизацию конфликтов: эти приложения давно научились решать конфликты, возникающие между пользователями. Когда некоторое количество пользователей имеют различные желания по изменению одного и того же фрагмента текста приложения так или иначе гарантированно решает возникший конфликт.
• Высокая скорость взаимодействия: в наше время сеть интернета уже способна обеспечивать хорошую скорость взаимодействия, однако она может быть нестабильна или вовсе отсутствовать. Разработчики приложений нашли способы бороться и с этими проблемами путем применения желаемых изменений сначала к локальной версии текста. При возвращении к нормальной работоспособности сети локальные изменения будут отправлены остальным пользователям.
Такие технологии применяются в различных сферах — от разработки программного обеспечения до научных исследований и бизнес- документооборота. Существует множество решений для совместного редактирования, включая Google Docs, Etherpad, Microsoft 365 и каждая из этих систем имеет свои ограничения, связанные с производительностью, конфликтами правок или сложностью реализации.
Может показаться, что в этой предметной области решены все проблемы и научных вопросов не осталось. И действительно технология широко распространена и прекрасно используется при соблюдении минимальных требований для работоспособности. Однако такое мнение формируется при взгляде с точки зрения пользователя, имеющего современную ЭВМ.
При взгляде со стороны разработчика ПО видны проблемы алгоритмической и архитектурой сложности итоговой системы.
• Проблемы архитектурной сложности в основном зависят от подхода, лежащего в основе конкретной системы. Последствия этих проблем можно ослабить, однако глобально изменить ситуацию невозможно, не меняя сам подход, лежащий в основе системы.
• Проблемы алгоритмической сложности по времени слабо интересны, если находятся в приемлемых рамках. Приемлемость рамок определяется ожидаемой задержкой сети. Учитывая, что интернет считается сетью с высокой задержкой, можно утверждать, что проблемы данного характера придется решать не зависимо от того, что является их первопричиной.
• Проблемы алгоритмической сложности по памяти слабо интересны только в том случае, если отсутствуют ограничения на размер RAM. Однако существуют кране важные отрасли, в которых размеры RAM строго ограничены. К таким можно отнести отрасли, результат деятельности которых попадает в крайне враждебную среду (космический вакуум, среды с высоким давлением).
Если оставаться в рамках известных подходов к проектированию систем совместного редактирования текста, то интерес вызывают только проблемы алгоритмической сложности по времени и памяти.
Был реализован предложенный алгоритм. При его реализации была решена проблема согласованности, присущая всем алгоритма совместного редактирования текста. Так же были решены сопутствующие проблемы технического характера.
По временной сложности алгоритм превосходит большинство устаревших аналогов, однако в данной реализации не может соперничать с передовыми алгоритмами семейства SOCT.
По пространственной сложности алгоритм превосходит аналоги, но жертвует ради этого практически всеми метаданными операций.
В итоге алгоритм хорошо подходит для использования в условия ограниченного размера RAM.
