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

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

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

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

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

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

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

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

Ответы

Ответ 1

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

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

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

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

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

Из Статья в Википедии о CRDT:

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

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