协同操作设计
冲突处理
冲突处理的解决方案其实已经相对成熟，包括：
- 编辑锁：当有人在编辑某个文档时，系统会将这个文档锁定，避免其他人同时编辑。
- diff-patch：基于 Git 等版本管理类似的思想，对内容进行差异对比、合并等操作，包括 GNU diff-patch、Myer’s diff-patch 等方案。
- 最终一致性实现：包括 Operational Transformation（OT）、 Conflict-free replicated data type(CRDT，称为无冲突可复制数据类型)。
编辑锁的实现方式简单粗暴，但会直接影响用户体验。
diff-patch 可以对冲突进行自助合并，也可以在冲突出现时交给用户处理。
OT 算法是 Google Docs 中所采用的方案，Atom 编辑器使用的则是 CRDT。
冲突解决算法（OT 与 CRDT）
冲突解决算法
冲突解决算法分成了两个流派：
- 要么是以 operation 为抓手，打通对轻量 operation 数据的变换（Operational Transform，即
OT）。 - 要么是以 model 为抓手，实现出可以任意拥抱变化的 model 数据结构（Conflict-free replicated data type，即 CRDT）。
这两种玩法都有很多「形成闭环赋能业务」的成功案例。
既然已经提到了 OT 和 CRDT 的对比，这里就顺便多说一句：在 2021 年，这个领域的未来已经明显是属于 CRDT 的了。除了易于实现可横向扩展的服务端、易于实现端到端加密协作、性能问题已经基于 Yjs 算法得到大幅优化（参见这篇文章）之外，还有一条大家喜闻乐见的八卦：你知道前端最流行的开源 OT 库叫 ShareDB 吗？而它的作者 Joseph Gentle 在去年写了一篇 CRDTs are the future 的文章以后，现在正忙着把 Yjs 重写到 Rust 极致优化性能。
OT
什么是OT（Operational transformation）
Operational transformation 翻译过来就是操作转化，流程也是分为两个部分操作和转换。
操作 Operational
将设备的编辑转换成操作(Operational)，发送到服务端。
insert(index, char)
delete(index, char)转换 transformation
转换是为了确保不同设备的操作，同步到其他设备的时候，最后会得到一致的结果。服务端接受 Operational，转换Operational，发送到对应客户端，客户端合并操作，得到一致结果。
OT的行业运用
- Google Doc
CRDT
什么是CRDT
CRDT 翻译过来就是无冲突可复制数据类型。
CRDT的种类
CRDT有两种方法，都可以提供强最终一致性：基于操作的CRDT 和 基于状态的CRDT。
这两种方法在理论上是等同的，因为一个可以模仿另一个。然而，实际上还是有区别的。
基于状态的CRDT 通常更容易设计和实现；它们对通信底层的唯一要求是某种流言协议。它们的缺点是，每个CRDT的整个状态最终都必须传输给其他每个副本，这可能开销很大。
相比之下，基于操作的CRDT 只传输更新操作，通常很小。然而，基于操作的CRDT需要通信中间件的保证；在传输给其他副本时，操作不会被丢弃或重复，而且它们是按因果顺序传输的。
基于操作的CRDT
基于操作的CRDT也被称为交换性复制数据类型（commutative replicated data types，或CmRDT）。CmRDT副本只通过传输更新操作来传播状态。例如，单一整数的CmRDT可以广播操作（+10）或（-20）。副本接收更新并在本地应用这些更新。这些操作是可交换的。然而，它们不一定幂等。因此，通信基础设施必须确保一个副本上的所有操作都被传递给其他副本，没有重复，但以任何顺序传输都是可以的。
纯基于操作的CRDT是基于操作的CRDT的一个变种，它减少了元数据的大小。
基于状态的CRDT
基于状态的CRDT被称为收敛复制数据类型（convergent replicated data types，或CvRDT）。与CmRDT相反，CvRDT将其完整的本地状态发送给其他副本，在这些副本中，状态必须通过可交换的、可结合的并且是幂等的函数合并。合并函数为任何一对副本的状态提供连接，因此所有状态的集合形成一个半格。更新函数必须按照与半格相同的偏序规则，单调地增加内部状态。函数必须内部状态，根据与半网格相同的偏序规则。
Delta状态CRDT（或简称Delta CRDT）是基于状态的优化CRDT，其中只有最近应用到一个状态的更改才会被传播，而不是传播到整个状态。
CmRDT与CvRDT对比
虽然CmRDT对副本间传输操作的协议提出了更多的要求，但当事务数量与内部状态的大小相比较小时，它们使用的带宽比CvRDT要少。不过，由于CvRDT的合并函数是可结合的，与某个副本的状态合并会产生该副本之前的所有更新。流言协议在向其他副本传播CvRDT状态时效果很好，同时减少了网络使用并处理了拓扑变化。
基于状态的CRDT的存储复杂性的一些下界是已知的。
总结
基于操作的CRDT
- 优点：传输量小
- 缺点：需要网络实时同步
基于状态的CRDT
- 优点：可以离线操作再进行合并
- 缺点：传输量大
CRDT的行业运用
- Teletype for Atom采用了CRDT，使开发人员能够与团队成员分享他们的工作空间，并实时进行代码协作。
- Redis是一个分布式、高可用和可扩展的内存数据库，它使用CRDT来实现基于开源Redis的全球分布式数据库，并与之完全兼容。
- Facebook在他们的Apollo低延迟“规模一致性”数据库中实现了CRDT。
- Apple在Notes应用中实现了CRDT，用于在多个设备之间同步离线编辑。
OT与CRDT的对比
OT主要用于文本，通常常很复杂且不可扩展。CRDT 不仅仅应用在协同编辑，还有分布式系统的最终一致性上也有应用。
OT操作必须通过服务器的转换才可以合并，而 CRDT 由于其数据结构特性，不通过服务器也可以合并。
但 Google、Microsoft、CKSource 和许多其他公司依赖 OT 是有原因的，CRDT 研究的当前状态支持在两种主要类型的数据上进行协作：纯文本、任意 JSON 结构。
对于富文本编辑等更高级的结构，OT 用复杂性换来了对用户预期的实现，而 CRDT 则更加关注数据结构，随着数据结构的复杂度上升，算法的时间和空间复杂度也会呈指数上升的，会带来性能上的挑战。
版本管理
数据版本更新
数据版本能按照预期有序更新，需要几个前提：
- 协同数据版本正常更新
- 丢失数据版本成功补拉
- 提交数据版本有序递增
要怎么理解这几个前提呢？我们来举个例子。
小明打开了一个文档，该文档从服务器拉取到的数据版本是 100。这时候服务器下发了个消息，说是有人将该版本更新到了 101，于是小明需要将这个 101 版本的数据更新到界面中，这是协同数据版本正常更新。
小明基于最新的 101 版本进行了编辑，产生了个新的操作数据。当小明将这个数据提交到服务器的时候，服务器看到小明的数据基于 101 版本，就跟小明说现在最新的版本已经是 110 了。小明只能先去服务器将 102-110 的版本补拉回来，这是丢失数据版本成功补拉。
102-110 的数据版本补拉回来之后，小明之前的操作数据需要分别跟这些数据版本进行冲突处理，最后得到了一个基于 110 版本的操作数据。这时候小明重新将数据提交给服务器，服务器接受了并给小明分配了 111 版本，于是小明将自己本地的数据版本升级为 111 版本，这是提交数据版本有序递增。
维护数据任务队列
要管理好这些版本，我们需要维护一个用户操作的数据队列，用来有序提交数据。这个队列的职责包括：
- 用户操作数据正常进入队列
- 队列任务正常提交到接入层
- 队列任务提交异常后进行重试
- 队列任务确认提交成功后移除
这样一个队列可能还会面临用户突然关闭页面等可能，我们还需要维护一个缓存数据，当用户再次打开页面的时候，将用户编辑但未提交的数据再次提交到服务器。除了浏览器关闭的情况，还有用户在编辑过程中网络状况变化而导致的网络中断，这种时候我们也需要将用户的操作离线到本地，当网络恢复的时候继续上传。
房间管理
由于多人协同的需要，相比普通的 Web 页面，还多了房间和用户的管理。在同一个文档中的用户，可视作在同一个房间。除了能看到哪些人在同一个房间以外，我们能收到相互之间的消息，在文档的场景中，用户的每一个操作，都可以作为是一个消息。
但文档和一般的房间聊天不一样的地方在于，用户的操作不可丢失，同时还需要有严格的版本顺序的保证。用户的操作内容可能会很大，例如用户复制粘贴了一个10W、20W的表格内容，这样的消息显然无法一次性传输完。在这种情况下，除了考虑像 Websocket 这种需要自行进行数据压缩（HTTP 本身支持压缩）以外，我们还需要实现自己的分片逻辑。当涉及数据分片之后，紧接而来的还有如何分片、分片数据丢失的一些情况处理。
多种通信方式
前后端通信方式有很多种，常见的包括 HTTP 短轮询（polling）、Websocket、HTTP 长轮询（long-polling）、SSE（Server-Sent Events）等。
我们也能看到，不同的在线文档团队选用的通信方式并不一致。例如谷歌文档上行数据使用 Ajax、下行数据使用 HTTP 长轮询推送；石墨文档上行数据使用 Ajax、下行数据使用 SSE 推送；金山文档、飞书文档、腾讯文档则都使用了 Websocket 传输。
而每种通信方式都有各自的优缺点，包括兼容性、资源消耗、实时性等，也有可能跟业务团队自身的后台架构有关系。因此我们在设计连接层的时候，考虑接口拓展性，应该预留对各种方式的支持。
Undo/Redo 设计
对于大多数编辑器来说，Undo/Redo 是最基础的能力，文档编辑也不例外。前面我们提到实时协同有版本的概念，同时用户的每一个操作可能会被拆分成多个原子操作。
在这样的场景下，Undo/Redo 既涉及到落盘数据的恢复，还涉及到用户操作的还原时遇到冲突的一些处理。在多人协同的场景下，如果在编辑过程中接收到了其他人的一些操作数据，那么 Undo 的时候是否又会撤回别人的操作呢？
基于 OT 算法的 Undo 其实思路相对简单，通常是针对每个原子操作实现对应的invert()方法，进行该原子操作的逆运算，生成一个新的原子操作并应用。
前面我们介绍 transform 函数可以分为 IT 和 ET 两类，而 Undo 的实现有两种方式：
- Inv & IT: invert + inclusion transformation
- ET & IT: exclusion transformation + inclusion transformation
不管是哪种算法，OT 用于撤消的基本思想是根据操作之后执行的那些操作的效果，将操作的逆操作（待撤消的操作）转换为新形式，从而使转换后的逆操作可以实现正确的 Undo 影响。但如果用户在编辑的时候接收到了新的协同操作，当该用户在进行 Undo 的时候，通过逆运算生成的原子操作同样需要和这些新来的协同消息进行冲突处理，才能保证最终一致性。