algorithm - OT 和 CRDT 的区别

Question

谁能简单解释一下 Operational Transform 和 CRDT 之间的主要区别？

据我了解，这两种算法都允许数据在分布式系统的不同节点上无冲突地聚合。

您会在哪个用例中使用哪种算法？据我了解，OT 主要用于文本，而 CRDT 更通用，可以处理更高级的结构，对吧？

CRDT 比 OT 更强大吗？

---

我问这个问题是因为我正在尝试了解如何为 HTML 文档实现协作编辑器，但不确定首先要看哪个方向。我看到了 ShareJS 项目，以及他们在 contenteditables 元素上支持浏览器富文本协作的尝试。在 ShareJS 的任何地方，我都没有看到任何为此使用 CRDT 的尝试。

我们还知道 Google 文档正在使用 OT，它在丰富文档的实时编辑方面效果很好。Google 选择使用 OT 是因为当时 CRDT 还不是很出名吗？还是今天也是一个不错的选择？

我也有兴趣了解其他用例，例如在数据库上使用这些算法。 Riak 似乎使用 CRDT。 OT 是否也可以用于同步数据库的节点并替代 Paxos/Zab/Raft？

Answer 1

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

• OT 通过改变操作 来做到这一点。操作通过线路发送，并发操作在收到后进行转换。
• CRDT 通过改变状态 来实现。操作在本地 CRDT 上进行。它的状态通过网络发送，并与副本的状态合并。无论合并多少次或合并的顺序如何 - 所有副本都会聚合。

你是对的，OT 主要用于文本并且确实早于 CRDT，但是 research表明:

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

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

来自Wikipedia article on CRDT :

OTs are generally complex and non-scalable

有不同类型的 CRDT(集合、计数器等)适用于不同类型的问题。有些是专为文本编辑而设计的。例如，Treedoc - A commutative replicated data type for cooperative editing .