85

Can someone explain me simply the main differences between Operational Transform and CRDT?

As far as I understand, both are algorithms that permits data to converge without conflict on different nodes of a distributed system.

In which usecase would you use which algorithm? As far as I understand, OT is mostly used for text and CRDT is more general and can handle more advanced structures right?

Is CRDT more powerful than OT?

I ask this question because I am trying to see how to implement a collaborative editor for HTML documents, and not sure in which direction to look first. I saw the ShareJS project, and their attempts to support rich text collaboration on the browser on contenteditables elements. Nowhere in ShareJS I see any attempt to use CRDT for that.

We also know that Google Docs is using OT and it's working pretty well for real-time edition of rich documents. Is Google's choice of using OT because CRDT was not very known at that time? Or would it be a good choice today too?

I'm also interested to hear about other use cases too, like using these algorithms on databases. Riak seems to use CRDT. Can OT be used to sync nodes of a database too and be an alternative to Paxos/Zab/Raft?

4

1 回答 1

56

这两种方法的相似之处在于它们提供了最终的一致性。不同之处在于他们如何做到这一点。一种看待它的方法是：

  • OT 通过改变操作来做到这一点。操作通过线路发送，并发操作在收到后进行转换。
  • CRDT 通过改变state来做到这一点。在本地 CRDT 上进行操作。它的状态通过网络发送并与副本的状态合并。合并的次数或顺序无关紧要 - 所有副本都会收敛。

你是对的，OT 主要用于文本，并且早于 CRDT，但研究表明：

与作者所说的不同，文献中的许多 OT 算法不满足收敛特性

换句话说，CRDT 合并是可交换的，而 OT 转换函数有时不是。

来自关于 CRDT 的维基百科文章：

OT 通常很复杂且不可扩展

有不同种类的 CRDT（集合、计数器……）适用于不同种类的问题。有些是为文本编辑而设计的。例如，Treedoc -用于协作编辑的可交换复制数据类型。

于 2014-12-15T22:33:22.150 回答