Yjs CRDT 算法
简介
用于协作编辑的无冲突复制数据类型(CRDT，Conflict-free Replicated Data Types)是操作转换(OT，Operational Transformation)的另一种方法。它们之间有一个非常简单的区别，OT 尝试通过转换索引位置以确保一致性(所有客户端最终使用相同的内容)，而 CRDT 使用的数学模型通常不涉及索引的转换。比如链表。OT 是当前共享文本编辑的事实标准。OT 方法支持共享编辑，但没有一个真正的来源中心(中央服务器)，需要保持数量众多的记录文档，虽然在实践中是可行的。CRDT 更适合于分布式系统，它为文档能够与远程客户机同步提供了额外的保证，同样也不需要一个真实的中心来源。
Yjs 实现了这篇文章算法的一个修改版本。我们将会发表一篇论文来论述为什么这个方法在实践中如此有效。注意：由于操作组成了文档结构，所以我们现在更喜欢用struct(结构)这个词。
适合于共享文本编辑的 CRDTs 的缺点是它们只会增加容量。虽然有一些 CRDTs 不会变大，但却没有利于共享文本编辑的特性(比如保存)。Yjs 对原始算法进行了诸多改进，减少了文档容量不断增加问题。我们不能在确保结构的唯一顺序的同时对已删除的结构(tombstone，墓碑)进行垃圾回收。但是我们可以这样做：
- 将之前的结构合并到一个结构中，可以减少元信息的数量。
- 如果内容被删除了，我们可以从结构中删除它。
- 如果我们不再关心结构体的顺序(例如父结构被删除)，我们可以对墓碑进行垃圾回收。
示例：
- 如果用户按顺序插入元素，多个结构将会合并为单个结构。举例来说：
array.insert(0, ['a']), array.insert(0, ['b']);首先表示为两个结构[{id: {client, clock: 0}, content: 'a'}和{id: {client, clock: 1}, content: 'b'}接下来合并为一个结构[{id: {client, clock: 0}, content: 'ab'}]。 - 当结构中包含的内容(如
ItemString)被删除了，那么它会被ItemDeleted所取代，这个结构中不包含任何内容。 - 在删除类型时，所有子元素将转换为
GC结构。GC结果仅表示结构的存在和删除。如果有的结构体和其他结构体的 ID 相邻，那么它们就会和其他结构体合并。
特别是在处理结构化内容(例如 ProseMirror 上的共享编辑)时，这些改进在基准测试随机文档编辑时产生了非常好的结果。在实践中，它们的性能更棒，因为用户通常会按顺序编辑文本，从而产生易于合并的结构体。基准测试表明，即使在用户从右到左编辑文本的最坏情况下，Yjs 也能在处理大型文档时获得良好的性能。
状态向量
当同步两个客户端时，Yjs 能够只交换差异。我们使用 lamport 时间戳来标识结构，并跟踪客户端创建它们的顺序。每个结构都拥有一个struct.id = { client: number, clock: number}，结构体的唯一标识。我们将每个客户端所期望的下一个clock定义为状态向量。这个数据结构类似于版本向量数据结构。但是我们只使用状态向量来描述本地文档的状态，因此我们可以计算远程客户端的缺失结构。我们不用它来追踪因果关系。