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

Question

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

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

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

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

---

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

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

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

Answer 1

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

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

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

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

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

От Wikipedia article on CRDT:

ОЦ, как правило, сложны и не масштабируемый

Существуют различные виды CRDTs (наборы, счетчики, ...) подходят для различных видов проблем. Есть некоторые, которые предназначены для редактирования текста. Например, Treedoc - A commutative replicated data type for cooperative editing.