OT 与 CRDT 的区别

有人能简单地解释一下操作变换和 CRDT 之间的主要区别吗？

据我所知，这两种算法都允许数据在分布式系统的不同节点上不冲突地收敛。

在哪种情况下您会使用哪种算法？据我所知，OT 主要用于文本，CRDT 更一般，可以处理更高级的结构，对吗？

CRDT 比 OT 更有效吗？

我问这个问题是因为我想知道如何实现 HTML 文档的协作编辑器，而不确定首先应该朝哪个方向看。我看到了 ShareJS 项目，以及他们试图在浏览器上支持 contenteditables元素上的富文本协作。在 ShareJS 中，我没有看到任何使用 CRDT 的尝试。

我们也知道 Google Docs 正在使用 OT 技术，而且对于实时版本的富文档来说效果非常好。谷歌之所以选择使用 OT，是因为 CRDT 在当时并不为人所知吗？或者今天也是个不错的选择？

我也对其他用例感兴趣，比如在数据库中使用这些算法。Riak 似乎用了 CRDT。OT 可以用来同步数据库的节点吗? 它可以替代 Paxos/Zab/Raft 吗？

17473

小开

最佳答案

Both approaches are similar in that they provide eventual consistency. The difference is in how they do it. One way of looking at it is:

OT does it by changing operations. Operations are sent over the wire and concurrent operations are transformed once they are received.
CRDTs do it by changing state. Operations are made on the local CRDT. Its state is sent over the wire and is merged with the state of a copy. It doesn't matter how many times or in what order merges are made - all copies converge.

You're right, OT is mostly used for text and does predate CRDTs but research shows that:

many OT algorithms in the literature do not satisfy convergence properties unlike what was stated by their authors

In other words CRDT merging is commutative while OT transformation functions sometimes are not.

OTs are generally complex and non-scalable

There are different kinds of CRDTs (sets, counters, ...) suited for different kinds of problems. There are some that are designed for text editing. For example, Treedoc - A commutative replicated data type for cooperative editing.