架构设计

两类数据最重要：第一就是metadata，也就是文档的元数据，诸如文档名称、文档作者、创建时间、存放目录、最近修改时间、文档大小、文档类型等；第二就是文档本身了！文档的metadata都是结构化的数据，用mysql存就行了！文档本身了？当然是File system啦，诸如HDFS之类的是最合适不过的了

存储上，

• 每个段落可以是一条数据, 一个kv这样。
• 段落有前后指针，组成一个链表。
• 协同编辑可以段落上挂靠评论数据。每个段落一个id。这个id可以客户端产生，每次最大id + 1即可，也代表了时间先后。
• 每个段落可以做行锁解决冲突也可以OT来直接合并，可能最后结果不正常。
• 在编辑文档是，还想要知道另一个也在编辑文档的人，这个功能简单，直接把同一个文档在线用户存放在redis，用户放在list或set就行了！
• 显实正在编辑某行的人: 同样存在redis中，由server通过websocket同步给其他client

接入层和业务逻辑层之前的请求分成了两类，

• 一类是普通的HTTP请求，一类是内容编辑操作。对于普通的HTTP请求接入层直接转发给对应的业务模块就可以了，两层服务之前是内网调度，可以采用RPC协议。
• 内容编辑操作我们采用MQ传输，通过文档的类型区分不同的Topic，根据文档的ID选择Partition有序传输消息。为什么内容编辑操作采用MQ传输呢？一是通过MQ解耦长链接的转发和业务处理逻辑；二是内容编辑操作很容易产生大量的并发请求，通过MQ消峰填谷；三是通过MQ完成消息广播的功能，当用户的编辑操作处理完成之后，广播给其他打开文档的用户；四是通过MQ产生有序消息，方便各OP模块顺序处理用户操作。为什么没有把全部请求都通过MQ转发呢？所有请求通过MQ转发，理论上是行得通的，但是会增加开发人员的工作量，当前系统的并发量不大，调用链路也不是很长，所以没有必要。

因为OP操作逻辑比较独立，占用CPU、内存往往比较高，所以拆分成单独的服务部署，方便合理分配资源，也可以避免一种文档出问题影响其它业务。

在线文档协同编辑

OT 的英文全称是 Operational transformation，是一种处理协同编辑的算法。

它常用于实现协同文档的底层算法，支持多个用户同时编辑文档，不会因为并发修改导致冲突，而使结果不一致或数据丢失。

冲突的处理方式

假设 A 和 B 在同时编辑同一个内容，我们处理冲突的方式有：

1. 加锁。用户 A 在编辑时，就锁住文档，只能 A 进行更新。用户 B 就不能编辑，或编辑后提交修改被服务器丢弃；
2. 覆盖。谁最后修改，就全量使用他的修改，更早一些的其他人的修改会被丢弃。
3. 用户自行处理冲突。就像 git merge 导致的冲突一样，会提示哪个地方被同时修改了，让合并者手动选择使用哪一个修改；
4. 使用一致性算法。比如我们要介绍的 OT 算法，可以让用户编辑进行算法处理进行调整，在多个客户端生成一致的修改结果。

对于在线协同文档，

加锁体验太差，一个人在编辑时其他人就要干等着。

覆盖则是导致用户的修改来回彼此覆盖，辛苦编辑的内容突然被别人覆盖掉了心情低落。

自行处理冲突则需要额外的操作步骤和成本，实时性很差，不适合高频同时修改的场景。

一致性算法是最好的选择，对用户最友好，不过带来了实现的复杂。

使用 OT

OT 算法可以解决一致性问题，我们来看看 OT 到底做了什么。

同样，原始内容是 “12”。

1. 用户 A 在末尾添加 “A”，本地变成 “12A”，并发送 insert(2, A)，这个操作计作 OA；
2. 用户 B 在末尾添加 “B”，本地变成 “12B”，并发送 insert(2, B)，这个操作计作 OB；
3. 用户 A 收到 OB，执行 transform(OA, OB)，得到修正后的操作 insert(3, B)，记为 OB’，相比 OB，它将插入位置从 2 修正为 3，于是 “12A” 变成了 “12AB”；
4. 用户 B 则收到 OA，同样执行 transform(OA, OB)，得到修正操作 insert(2, A)，记为 O1’，让内容从 “12A” 变成 “12AB”。transform 方法会同时产生 OA’ 和 OB’。

最后，用户 A 和用户 B 看到的是 一致 的 “12AB”。

这里的核心在于这个 transfrom 方法，它能够对操作进行修正。transform 没有固定实现，要根据实际需求自行实现。

假如我们把 A 提交的行为叫做 A，B 提交的行为叫做 B，现在后台就是一个简单的转发功能，告诉 A 的是 B，告诉 B 的是 A，然后就出现问题了。所以后台应该更聪明一点，它应该学会一个招术，那就是把每个人提交的行为转变一下再告诉别人，其实这个技术就是 OT 算法。

OT 算法全名叫 Operation Transformation，你看从名字就对应了上面我说的转变算法。 假设我们的 OT 算法的转换功能叫 transform，那 transform（A，B）= A’,B’。 也就是说你输入两个先后执行的行为，它会告诉你两个转换过后的行为，然后把 A’行为告诉 B，把 B’行为告诉 A，这样大家再应用就相安无事了。

这里实际抽象一下，用户永远就只有两个人，一个是自己，一个是服务端，只是服务端的操作可能来自很多人，如果不这样抽象，那一个个进行冲突处理可能会让你觉得无法理解。

OT 算法的实现

所有对文本的操作都可以抽象成三个原子行为：

R = Retain，保持操作 I = Insert，插入操作 D = Delete，删除操作

那之前的行为

第 3 个字符行后面插入了一个 ‘d’

就会变成

R(3), I(‘d’)

核心

你输入两个先后执行的行为，它会告诉你两个转换过后的行为，然后把 A’行为告诉 B，把 B’行为告诉 A，这样大家再应用就相安无事了。

  // produces two operations A' and B' (in an array) such that
  // `apply(apply(S, A), B') = apply(apply(S, B), A')`. This function is the
  // heart of OT.

A和B原子操作只有三种，根据排列组合，最多只会有 9 种情况。 分别处理即可。

比如A是插入，则遍历位置对应字符，判断A是Insert，则B对这个字符进行Retain，相当于延后B的字符串处理，索引S对应需要加一。

时序

不是基于时间先后。

而是要基于版本。

服务器设计

服务器中维护了一系列历史的修改版本，例如 r1,r2,r3,…r100,…r110

假如某个客户端提交的变化 C,是基于 R100 的，这时候，我们需要不停的产生变化 newC = follow(R101,C) , 然后 newC = follow(R102,newC)，不断执行，最后要得到针对 r110 这个版本的 newC 变化，推送到各个客户端

参考

• 协同编辑中使用的 OT 算法是什么？

在线表格存储如何设计

可以20行作为一个KV这样。