OT和CRDT之间的区别

Question

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

据我所知，两者都是算法，允许分布式系统不发生冲突地在不同节点上汇聚数据。

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

CRDT比OT更强大吗？

---

我问这个问题是因为我正在尝试看如何为HTML文档实现协作编辑，并不确定应该先从哪方面入手。我看到了ShareJS项目，以及他们在浏览器上支持富文本协作的尝试，但在ShareJS中我并没有看到任何尝试使用CRDT的迹象。

我们也知道Google Docs使用OT，并且它在实时编辑富文档方面工作得非常好。 Google选择使用OT是因为当时CRDT并不是很出名吗？或者今天使用OT也是一个好选择吗？

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

- Sebastien Lorber

---

你应该阅读TreeDoc论文，它是为你的目的而设计的。https://hal.inria.fr/inria-00445975/document - simbo1905

建议：请查看 https://github.com/yjs/yjs-demos，特别是演示 https://demos.yjs.dev/atlaskit/atlaskit.html。 - Mikko Rantalainen

Answer 1

这两种方法都提供最终一致性，不同之处在于它们实现的方式。一种看待它的方法是：

• OT通过更改操作来实现。操作被发送到网络并在接收后对并发操作进行转换。
• CRDT通过更改状态来实现。在本地CRDT上进行操作，将其状态发送到网络并与副本的状态合并。无论进行多少次合并或以何种顺序进行合并-所有副本都会收敛。

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

文献中许多OT算法不能满足收敛属性，与其作者所述不同。

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

从CRDT Wikipedia文章中可以看到：

OT通常是复杂且不可扩展的

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

- Andrejs

---

CRDTs 不仅仅是基于状态的，它们分为两种类型。基于状态的 CvRDTs（收敛复制数据类型）和基于操作的 CmRDTs（交换律复制数据类型）。 - Magnus

这引出了一个问题，OT和CmRDT之间的区别是什么？ - hrdwdmrbl

@hrdwdmrbl 你好，CmRDT具有可交换操作，因此您无需转换它们即可正确应用它们。要么它们适合，要么您缺少某些内容，必须等待操作。OT处理冲突编辑问题时时间复杂度会增加，而CRDT则增加了空间复杂度。 - Marcel Klehr

Answer 2

另一个值得注意的区别是：

• OT需要一个集中式服务器来协调。
• CRDT可以采用任何网络拓扑结构，如基于WebRTC的P2P网络，并且具有抗网络分区的特性，这使得它分散化。

参考：Martin Kleppmann的“Designing Data-Intensive Applications”。

- Joe

---

我相信这实际上是两者之间的关键区别，或者至少是这种区别最显著的结果。对于操作转换，中央服务器会转换操作；对于CRDT，你只需要与同行交换新数据，每个人都会知道足够的信息来重建相同的最终状态。 - undefined

我相信这实际上是两者之间的关键区别，或者至少是这种差异最显著的结果。对于操作转换（Operational Transforms），中央服务器负责转换操作；而对于CRDT，你只需要与同行交换新数据，每个人都会知道足够的信息来重建相同的最终状态。 - Peeja

我本来也打算分享同一个视频，非常有用的参考资料。 - undefined