OT和CRDT之间的差异

Question

有人可以简单解释一下Operational Transform和CRDT之间的主要区别吗？

据我所知,这两种算法都允许数据在分布式系统的不同节点上收敛而不会发生冲突.

在哪个用例中你会使用哪种算法？据我所知,OT主要用于文本,CRDT更通用,可以处理更高级的结构吗？

CRDT比OT更强大吗？

---

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

我们也知道Google Docs正在使用OT,它在富文档的实时版本中运行良好.谷歌是否选择使用OT,因为CRDT当时并不为人所知？或者它今天也是一个不错的选择？

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

Answer 1

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

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

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

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

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

来自Wikipedia关于CRDT的文章:

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

有不同种类的CRDT(套,计数器......)适合不同类型的问题.有些是专为文本编辑而设计的.例如,Treedoc - 用于协作编辑的可交换复制数据类型.

Answer 2

另一个显着的区别是：

• OT 需要一个中央服务器进行协调。
• CRDT 可以采用任何网络拓扑，例如 WebRTC 上的 P2P，并且它对网络分区具有弹性，这使得它去中心化。

参考：https://youtu.be/B5NULPSiOGw? t=643，作者：Martin Kleppmann，《设计数据密集型应用程序》一书的作者。