协同算法之OT和CRDT


多人协同编辑

多人协同编辑,就是像腾讯文档等在线产品一样,可以两人及以上同时编辑一个文件,而双方的编辑操作互不干扰,能够自动解决冲突。
而目前,协同编辑的基本实现思路主要有两种

  • CRDT
  • OT

    CRDT

    CRDT即为无冲突可复制数据类型,是一些分布式系统中适应于不同场景且可以保持最终以执行的数据结构统称。CRDT本身只是一个概念,需要自行实现数据结构。
    CRDT的类型
  • 基于操作状态的CRDT
  • 基于状态的CRDT
    这两种CRDT在数学上是等价的,可以相互装换。基于操作的CRDT需要消息中间件提供额外的支持,对操作命名并保证通信过程中不会丢失或者交递信息时保证消息唯一。基于状态的消息中间件则需要通信时保证全部的状态完好的交递。
    基于操作的CRDT
    基于操作的CRDT又称CMCRDT,CMCRDT在传播时,只包含数据更新操作信息。比方说,一个整数在执行了(+10), (-20) 操作后,CmRDT 广播时则只包含关于这个整数进行了(+10), (-20) 操作。其他的 DC 收到这个 CmRDT 后会在本地对相应的数据执行 CmRDT 中包含的操作。CmRDT 所能携带的操作必须是可交换的,通信模块必须保证所有 CmRDT 包都能被正确交递,但是顺序无需保证。
    基于状态的CRDT
    基于状态的 CRDTs又称为CvRDTs。CvRDTs 会将本地全部的数据状态传播给其他 DC, 这些状态在接受到后会被一个函数做 merge 处理,所以这些状态必须是可交换的,关联的,幂等的。merge 函数会为在 CvRDT 之间提供一个 join 操作,将接收到 CvRDT 与本地数据合并。

    OT

    OT即为操作转换,是指对文档编辑以及同时编辑冲突解决的一类技术,且依赖服务器来保持最终一致性。

文章作者: Kevin Lee
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Kevin Lee !
评论
  目录