Различия между OT и CRDT
Может кто-нибудь объяснить мне просто основные различия между операционным преобразованием и CRDT?
Насколько я понимаю, оба являются алгоритмами, которые позволяют данным сходиться без конфликта на разных узлах распределенной системы.
В каком случае вы будете использовать какой алгоритм? Насколько я понимаю, OT в основном используется для текста, а CRDT является более общим и может обрабатывать более сложные структуры, верно?
CRDT более мощный, чем OT?
Я задаю этот вопрос, потому что я пытаюсь понять, как реализовать совместный редактор для документов HTML, и не уверен, в каком направлении смотреть в первую очередь. Я видел проект ShareJS и их попытки поддержать совместную работу с расширенным текстом в браузере на contenteditables элементы. Нигде в ShareJS я не вижу никакой попытки использовать CRDT для этого.
Мы также знаем, что Google Docs использует OT, и он работает довольно хорошо для редактирования документов в режиме реального времени. Является ли Google выбором использования OT, потому что CRDT был не очень известен в то время? Или это был бы хороший выбор и сегодня?
Мне также интересно услышать о других случаях использования, таких как использование этих алгоритмов в базах данных. Риак, кажется, использует CRDT. Можно ли использовать OT для синхронизации узлов базы данных и быть альтернативой Paxos/Zab/Raft?
2 ответа
Оба подхода похожи в том, что они обеспечивают возможную согласованность. Разница в том, как они это делают. Один из способов взглянуть на это:
- ОТ делает это, изменяя операции. Операции отправляются по проводам, а параллельные операции преобразуются после получения.
- CRDT делают это путем изменения состояния. Операции производятся на местном CRDT. Его состояние отправляется по проводам и объединяется с состоянием копии. Неважно, сколько раз или в каком порядке производится слияние - все копии сходятся.
Вы правы, OT в основном используется для текста и предшествует CRDT, но исследования показывают, что:
многие алгоритмы ОТ в литературе не удовлетворяют свойствам сходимости в отличие от того, что было заявлено их авторами
Другими словами, слияние CRDT является коммутативным, в то время как функции преобразования OT иногда нет.
Из статьи в Википедии о CRDT:
ОТ, как правило, сложные и не масштабируемые
Существуют различные типы CRDT (наборы, счетчики, ...), подходящие для различных задач. Есть некоторые, которые предназначены для редактирования текста. Например, Treedoc - коммутативный тип реплицируемых данных для совместного редактирования.
Еще одно заметное отличие заключается в том, что:
- OT требует центрального сервера для координации.
- CRDT может принять любую сетевую топологию, такую как P2P через WebRTC, и он устойчив к сетевым разделам, что делает его децентрализованным.
Ссылка: https://youtu.be/B5NULPSiOGw?t=643 Мартина Клеппманна, автора книги «Проектирование приложений, интенсивно использующих данные».