Различия между OT и CRDT

Может ли кто-нибудь объяснить мне просто основные различия между Operational Transform и CRDT?

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

В каком случае вы бы использовали какой алгоритм? Насколько я понимаю, OT в основном используется для текста, а CRDT более общий и может обрабатывать более сложные структуры, верно?

Является ли CRDT более мощным, чем OT?


Я задаю этот вопрос, потому что пытаюсь понять, как реализовать совместный редактор для документов HTML, и не уверен, в каком направлении искать в первую очередь. Я видел проект ShareJS и их попытки поддерживать совместную работу с форматированным текстом в браузере на contenteditables элементах. Нигде в ShareJS я не вижу попыток использовать для этого CRDT.

Мы также знаем, что Google Docs использует OT и довольно хорошо работает для редактирования форматированных документов в режиме реального времени. Является ли решение Google использовать OT тем, что в то время CRDT не был широко известен? Или это будет хорошим выбором и сегодня?

Мне также интересно узнать о других вариантах использования, таких как использование этих алгоритмов в базах данных. Riak, кажется, использует CRDT. Может ли OT также использоваться для синхронизации узлов базы данных и быть альтернативой Paxos/Zab/Raft?


person Sebastien Lorber    schedule 01.11.2014    source источник
comment
Вам следует прочитать документ TreeDoc, который предназначен для ваших целей hal.inria.fr/inria-00445975/ документ   -  person simbo1905    schedule 19.03.2015
comment
Предложение: см. github.com/yjs/yjs-demos и особенно демо demos.yjs.dev/atlaskit/atlaskit.html   -  person Mikko Rantalainen    schedule 06.08.2020


Ответы (1)


Оба подхода схожи в том, что они обеспечивают конечную согласованность. Разница в том, как они это делают. Один из способов взглянуть на это:

  • OT делает это, изменяя операции. Операции отправляются по сети, а параллельные операции преобразуются после их получения.
  • CRDT делают это, изменяя состояние. Операции производятся на локальном CRDT. Его состояние передается по сети и объединяется с состоянием копии. Неважно, сколько раз и в каком порядке производится слияние — все копии сходятся.

Вы правы, OT в основном используется для текста и предшествует CRDT, но research показывает, что:

многие алгоритмы ОП в литературе не удовлетворяют свойствам сходимости, в отличие от того, что было заявлено их авторами.

Другими словами, слияние CRDT является коммутативным, в то время как функции преобразования OT иногда таковыми не являются.

Из статьи Википедии о CRDT:

OT, как правило, сложны и не масштабируемы.

Существуют различные типы CRDT (наборы, счетчики и т. д.), подходящие для решения различных задач. Некоторые из них предназначены для редактирования текста. Например, Treedoc — коммутативный реплицированный тип данных для совместного редактирования. .

person Andrejs    schedule 15.12.2014
comment
CRDT не только основаны на штате, они бывают двух видов. CvRDT на основе состояния (конвергентные реплицированные типы данных) и CmRDT на основе операций (коммутативные реплицированные типы данных). - person Magnus; 12.01.2016
comment
@Magnus Это приводит к вопросу, в чем разница между OT и CmRDT? - person hrdwdmrbl; 21.12.2016
comment
@hrdwdmrbl Что ж, в CmRDT есть коммутативные операции, поэтому вам не нужно преобразовывать их, чтобы применять их правильно. Либо они подходят, либо вы что-то упускаете и должны ждать операции. OT решает проблему конфликтующих правок с повышенной временной сложностью, в то время как CRDT имеет повышенную пространственную сложность. - person Marcel Klehr; 06.11.2017