Комментарии 29
Самое веселье в OT начинается с поддержкой операций отмены
Имеете ввиду false-tie? Про undo обязательно будет в продолжении.
Да, и FT тоже, ну и саму задачу отмены не последней операции + поддержку IP2-3 на уровне алгоритма.
Хотелось бы услышать в чем, с Вашей точки зрения, недостаток контекстной теории (context-based OT)?
Хотелось бы услышать в чем, с Вашей точки зрения, недостаток контекстной теории (context-based OT)?
1) Если не вводить дополнительные оптимизации, то с каждой операцией надо передавать ее контекст, то есть набор предыдущих операций от некоторого базового состояния. Чем дольше мы редактируем — тем больше «хвост». Оптимизации существуют, но они ведут к значительному усложнению алгоритма со всеми вытекающими.
2) Как я упоминал в статье, каждому пользователю необходима полная история операций, даже если он пришел позже.
3) Если есть возможность использовать центральный сервер, то лучше отказаться от peer-to-peer алгоритмов. Наличие одного «стандартного» порядка операций (естественно, это порядок операций на сервере) очень сильно упрощает алгоритм и положительно влияет на быстродействие, так как «нагрузка» к операции — это просто одно число (ревизия). В следующей статье это будет подробно разобрано и для тех, кто знаком с классическими «peer-to-peer» алгоритмами, разница будет видна невооруженным глазом.
4) Есть некоторые моменты, которые можно реализовать только если есть центральный сервер. А если нет общего «правильного» порядка, то невозможно. К сожалению, двумя словами их не объяснишь. Если получится, то это будет частью одной из следующих статей.
2) Как я упоминал в статье, каждому пользователю необходима полная история операций, даже если он пришел позже.
3) Если есть возможность использовать центральный сервер, то лучше отказаться от peer-to-peer алгоритмов. Наличие одного «стандартного» порядка операций (естественно, это порядок операций на сервере) очень сильно упрощает алгоритм и положительно влияет на быстродействие, так как «нагрузка» к операции — это просто одно число (ревизия). В следующей статье это будет подробно разобрано и для тех, кто знаком с классическими «peer-to-peer» алгоритмами, разница будет видна невооруженным глазом.
4) Есть некоторые моменты, которые можно реализовать только если есть центральный сервер. А если нет общего «правильного» порядка, то невозможно. К сожалению, двумя словами их не объяснишь. Если получится, то это будет частью одной из следующих статей.
По описанию сильно похоже на стандартный game server с возможностью reconnect'a :)
1 — передается вектор контекста, описывающий ее состояние. То есть если отказаться от отмены и упростить — данный вектор содержит количество операций на каждом сайте
2 — нет, зачем? у него есть состояние документа (вектор контекста) при его подключении, его интересует только то, что происходит после его подключения, а данные операции в любом случае рассылаются всем сайтам
3 — сontext-based может быть и не p2p, что сильно его упрощает. Не совсем понял, как поддерживается соответствие порядка операций на сервере и на клиенте. Получается операция выполняется и преобразуется только на сервере, а на клиенте затем виден результат? Но тогда как быть с оффлайном и низкой скоростью подключения?
4 — было бы интересно почитать
2 — нет, зачем? у него есть состояние документа (вектор контекста) при его подключении, его интересует только то, что происходит после его подключения, а данные операции в любом случае рассылаются всем сайтам
3 — сontext-based может быть и не p2p, что сильно его упрощает. Не совсем понял, как поддерживается соответствие порядка операций на сервере и на клиенте. Получается операция выполняется и преобразуется только на сервере, а на клиенте затем виден результат? Но тогда как быть с оффлайном и низкой скоростью подключения?
4 — было бы интересно почитать
1 — У нас вариант отказа от возможности отмены не рассматривался. Мало кто захочет пользоваться редактором, в котором нет undo-redo.
2 — А если вдруг придет операция, сгенерированная на состоянии более раннем, чем то, которое было при подключении?
3 — Мне сложно в одном комментарии рассказать весь алгоритм, потерпите немного, это обязательно будет в следующей статье. Могу намекнуть, что если взять алгоритм от google docs или wave, то с некоторыми изменениями этого можно добиться)
4 — Постараемся, это то, чего я в существующих статьях не встречал.
2 — А если вдруг придет операция, сгенерированная на состоянии более раннем, чем то, которое было при подключении?
3 — Мне сложно в одном комментарии рассказать весь алгоритм, потерпите немного, это обязательно будет в следующей статье. Могу намекнуть, что если взять алгоритм от google docs или wave, то с некоторыми изменениями этого можно добиться)
4 — Постараемся, это то, чего я в существующих статьях не встречал.
Я бегло посмотрел материал по ссылкам. Насколько я понял, там немного другая идея: документ представляется некоторой моделью, которая редактируется таким образом, чтобы не возникало коллизий. В частности элементам модели присваиваются уникальные идентификаторы, а удаление несуществующего элемента не считается ошибкой.
У ОТ подход другой — коллизии допускаются. К примеру, одновременная вставка в одну и ту же позицию в документе, или когда два пользователя меняют одно и то же свойство. Но при этом трансформация операций обеспечивает одинаковое итоговое состояние документа у всех.
У ОТ подход другой — коллизии допускаются. К примеру, одновременная вставка в одну и ту же позицию в документе, или когда два пользователя меняют одно и то же свойство. Но при этом трансформация операций обеспечивает одинаковое итоговое состояние документа у всех.
Основная идея семейства CRDT (WOOT, Logoot, Causal Trees и TreeDoc) — избежать трансформации операций, тем самым уменьшив сложность и повысив надёжность алгоритмов.
Это достигается за счёт уникальных идентификаторов, хранение которых и представляет интересную задачу.
При правильном подходе, идентификаторы занимают примерно столько же места, сколько и текст, а текст практически нисколько не занимает, по сравнению с различными медиа (картинки/видео).
CRDT также позволяет сложные сценарии (P2P, кэши, долгий оффлайн) и предлагает больший набор типов данных.
Кажется, мы общались с кем-то из вашей команды, примерно год назад. Вижу, за год вы многое успели. Впереди ещё много интересного.
Это достигается за счёт уникальных идентификаторов, хранение которых и представляет интересную задачу.
При правильном подходе, идентификаторы занимают примерно столько же места, сколько и текст, а текст практически нисколько не занимает, по сравнению с различными медиа (картинки/видео).
CRDT также позволяет сложные сценарии (P2P, кэши, долгий оффлайн) и предлагает больший набор типов данных.
Кажется, мы общались с кем-то из вашей команды, примерно год назад. Вижу, за год вы многое успели. Впереди ещё много интересного.
Неблокирующее одновременное редактирование — зло.
Одно дело когда у нас есть мерже-коммит, у которого есть автор. Другое дело когда у нас этот этап скрывается.
Ваш пример с «аптика» может быть фатальным.
Один человек удалил часть текста из одного места, и перенес его в другое место, параллельно другой человек удалили тот абзац куда фразу перенесли, и всё. На выходе уже текст который никто не читал, а если это договор, и пункт был важный…
Даже если мы целые фразы не теряем, а только буквы искажаем, ну или цифры… всё это может, и будет фатальным.
Либо у нас реально одновременная правка, как у гугла, где ты видишь чужой курсор, либо блокирующая работа.
Строго говоря здесь она тоже блокирующая, но строго на момент правки измеряющийся мс.
Одно дело когда у нас есть мерже-коммит, у которого есть автор. Другое дело когда у нас этот этап скрывается.
Ваш пример с «аптика» может быть фатальным.
Один человек удалил часть текста из одного места, и перенес его в другое место, параллельно другой человек удалили тот абзац куда фразу перенесли, и всё. На выходе уже текст который никто не читал, а если это договор, и пункт был важный…
Даже если мы целые фразы не теряем, а только буквы искажаем, ну или цифры… всё это может, и будет фатальным.
Либо у нас реально одновременная правка, как у гугла, где ты видишь чужой курсор, либо блокирующая работа.
Строго говоря здесь она тоже блокирующая, но строго на момент правки измеряющийся мс.
OT как раз дает реально одновременную правка как у гугла. Собственно у гугла и есть одна из реализаций OT, которую можно подсмотреть в apache wave например
1) Имея техническую возможность сделать одновременное неблокирующее редактирование всегда можно сделать режим с блокировкой любой части документа. В обратную сторону — очень сложно.
2)
3) Выше совершенно верно заметили, что в основе гугловского алгоритма тоже OT. Причем сам механизм ОТ позволяет поддерживать валидные позиции курсоров.
2)
Либо у нас реально одновременная правка, как у гугла, где ты видишь чужой курсорПосмотрите на верхнюю картинку в посте :)
3) Выше совершенно верно заметили, что в основе гугловского алгоритма тоже OT. Причем сам механизм ОТ позволяет поддерживать валидные позиции курсоров.
И как это сочетается с оффлайном?
Потерял коннект, имеешь блокировку. Иначе получаем мердж. Со всеми радостями…
Потерял коннект, имеешь блокировку. Иначе получаем мердж. Со всеми радостями…
Блокировка с офлайном, естественно, не сочетается никак. Я хотел отметить, что имея возможность совместного редактирования без блокировок, всегда можно дать возможность редактировать важные документы с блокировками его полностью или частично. А вот если сделать систему без оглядки на «фичу» одновременного редактирования, то впоследствии добавить ее будет очень сложно или даже практически невозможно.
Как же все знакомо) А в вашей реализации есть какие-то интересные отличия от sharejs.org (как самый простой пример) или от OT алгоритма, лежащего в основе Google Docs? Было интересно послушать. Кроме undo, животрепещущий вопрос работы в офлайне.
Отличия от гугловского алгоритма есть: tombstones, иерархическая модель документа, возможность изменения операции во время выполнения для поддержания ограничений бизнес-логики. Офлайн, в принципе, эквивалентен долгому обрыву связи.
OT с tombstones? Необычно…
У OT в оффлайне нарастает сложность задачи merge нетривиальным образом. Вы тестировали такие сценарии?
У OT в оффлайне нарастает сложность задачи merge нетривиальным образом. Вы тестировали такие сценарии?
OT с tombstones? Необычно…
Самое простое и эффективное решение FalseTie на мой взгляд.
У OT в оффлайне нарастает сложность задачи merge нетривиальным образом. Вы тестировали такие сценарии?
Из того, что проверяли в ручном режиме задержки именно OT-движка были незаметны. Специализированных тестов пока нет, у нас еще есть много моментов для оптимизаций и сжатия операций.
Разве совместное редактирование документа = collaboration? Последнее понятие намного шире.
А в чём проблема смёржить иерархические документы?
На одном из проектов имел дело с OT и вот какие ощущения:
1. Для каждого документа хранится вся история трансформаций (много весят, выборки тормозят и тп). Для решения этой проблемы пришлось писать таск на периодическое смёрживание трансформаций из одной сессии.
2. Малейший баг в алгоритме (а алгоритмы тут довольно нетривиальные) легко может запороть документ (у нас чудесно падал редактор), а исправлять битые трансформации — то ещё удовольствие.
3. Для получения актуальной версии нужно плясать с бубном — либо применяем все трансформации от начала времён, либо периодически расставляем «чекпоинты» и применяем трансформации от последнего чекпоинта.
В то же время, если использовать автомёрж, то:
1. Хранить нужно лишь последнюю актуальную версию и применять к ней патчи от клиентов.
2. Можно использовать любой редактор.
3. Неправильный автомёрж легко исправляется вручную.
На одном из проектов имел дело с OT и вот какие ощущения:
1. Для каждого документа хранится вся история трансформаций (много весят, выборки тормозят и тп). Для решения этой проблемы пришлось писать таск на периодическое смёрживание трансформаций из одной сессии.
2. Малейший баг в алгоритме (а алгоритмы тут довольно нетривиальные) легко может запороть документ (у нас чудесно падал редактор), а исправлять битые трансформации — то ещё удовольствие.
3. Для получения актуальной версии нужно плясать с бубном — либо применяем все трансформации от начала времён, либо периодически расставляем «чекпоинты» и применяем трансформации от последнего чекпоинта.
В то же время, если использовать автомёрж, то:
1. Хранить нужно лишь последнюю актуальную версию и применять к ней патчи от клиентов.
2. Можно использовать любой редактор.
3. Неправильный автомёрж легко исправляется вручную.
в чём проблема смёржить иерархические документы?
Проблема в том, что алгоритм автоматического мержа вынужден выбирать между надежностью и удобством для пользователя. То есть либо мы выбираем надежный алгоритм, который будет чаще просить пользователя смержить вручную. Либо более интеллектуальный, но который может дать неверный результат. По сравнению с простым текстом сложность мержа полноценного документа больше: представьте, что один пользователь добавил несколько строк в таблицу, а другой несколько столбцов. И при этом они отредактировали содержимое нескольких ячеек.
Кроме того, интерфейс ручного мержа офисных документов не может быть проще чем существующие утилиты для 3-way мержа. Вероятнее всего он будет значительно сложнее, а это значит, что пользователей нужно научить с ним работать.
1. Для каждого документа хранится вся история трансформаций (много весят, выборки тормозят и тп)
Скорее всего имелись ввиду операции, поскольку трансформации — это методы.
Правильно замечено, что наборы операций можно мержить. Плюс историю старше определенного времени можно удалять, если предположить, что клиенты достаточно регулярно синхронизируются с сервером. К тому же вся история нужна только на сервере, и при правильном выборе алгоритма большая ее часть практически не используется и может быть заархивирована. То есть проблемы с размером истории чисто технические и легко решаются с помощью стандартных подходов.
Малейший баг в алгоритме (а алгоритмы тут довольно нетривиальные) легко может запороть документ
Да, алгоритм должен быть качественно оттестирован. Кроме того, счет наличия истории всегда можно откатиться к последнему валидному состоянию.
Для получения актуальной версии нужно плясать с бубном
Обычно актуальная версия как раз и хранится, поэтому доступна без дополнительных издержек. Если нужно быстро получать старые версии, то можно использовать чекпоинты.
Хранить нужно лишь последнюю актуальную версию и применять к ней патчи от клиентов.
В этом как раз основная разница между ОТ и мержем. OT работает с операциями и имеет информацию о том, как менялся документ. Мерж имеет дело только с конечными состояниями и уже постфактум находит одинаковые и отличающиеся части, что дает намного меньше возможности «свести» различные изменения пользователей.
Элементарно — каждой ячейке назначаем гуид и по ним видно какие ячейки добавились, какие удалились и какие изменились. Со столбцами, строками, параграфами — та же песня.
И ручной мёрж можно сделать проще, так как у нас есть информация о структуре. В отличие от плоского текста, где единственная структура — это список строк текста.
Вот вам задачка: два пользователя находясь в оффлайне исправили опечатку поменяв «оптека» на «аптека» путём стирания буквы «о» (первая операция) и добавления буквы «а» (вторая операция), потом оба выходят в онлайн и что они получают в результате?
И ручной мёрж можно сделать проще, так как у нас есть информация о структуре. В отличие от плоского текста, где единственная структура — это список строк текста.
Вот вам задачка: два пользователя находясь в оффлайне исправили опечатку поменяв «оптека» на «аптека» путём стирания буквы «о» (первая операция) и добавления буквы «а» (вторая операция), потом оба выходят в онлайн и что они получают в результате?
Подход с гуидами близок к упоминавшемуся выше в комментариях CRDT. Если гуиды присваивать всему вплоть до букв, то это сильно просаживает производительность и увеличивает размер документа. Если внутри абзаца гуидов нет, то сама структура документа мержится однозначно, а вот текст внутри параграфов с теми же проблемами, что и плоский текст. Хотя в целом, если выбрать в качестве метода синхронизации мерж, то это решение выглядело бы оптимальным.
По поводу «аптеки» и «оптики» — для классического OT будет, естественно гибрид, хотя отслеживать такие конфликты возможность есть. Но и в зависимости от правил мержа это тоже может быть автоматически смержено, либо помечено как конфликт.
По поводу «аптеки» и «оптики» — для классического OT будет, естественно гибрид, хотя отслеживать такие конфликты возможность есть. Но и в зависимости от правил мержа это тоже может быть автоматически смержено, либо помечено как конфликт.
Спасибо за статью, познавательно. Действительно, задача не тривиальна и интересна.
Вышла вторая часть статьи. Там есть ответы на многие вопросы из комментариев :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Совместное редактирование. Часть 1