协同算法导论

在日常生活中, 我们有很多需要依赖协同的地方, 因此在此详细研究一下. 我们接下来从底层到顶来讲解一下. 正好, 我最近做了份协同画板, 可以作为一个例子, 我也会放在末尾作为一个小test.

我的输入法使用的英文标点, 但是我这里很多地方是copy的各处资料, 他们都是中文标点, 所以标点混用就忍受一下了(

网络通信技术

REST API

最基础的写法.

说白了，REST是一种风格！

REST的作用是将我们上面提到的查看（view），创建（create），编辑（edit）和删除（delete）直接映射到HTTP 中已实现的GET, POST, PUT和DELETE方法。

本质上可以理解为每次操作都需要向服务器发送一次HTTP请求, 然后服务器返回后即中断本次链接. REST API可能看着比较ez, 但是在项目起步的时候是非常利于API变得统一，因为我们只需要改变请求方式就可以完成相关的操作，这样大大简化了我们接口的理解难度，变得易于调用。

在这种REST API下, 我们做协同算法有比较简单的两种的方法: ajax轮询和long poll.

ajax轮询很简单, 就是每隔n秒去给服务器去发一个请求, 问服务器是否有更新.

ajax轮询的优点是简单, 但是缺点也很清晰: 当不需要更新数据的时候, 你能发现我们绝大部分带宽都用在了一些重复不需要的地方: TLS握手, header, cookie等(因为绝大部分都是空数据)... 同时我们的服务器压力也比较大, 再加上轮询本质上无法做到绝对的实时, 所以不适合用在需要及时反馈的服务(如cockpit等web终端).

long pull就是发送一个request, 但是服务器在需要更新的时候才返回值, 也就是你能够在web开发人员工具看到"挂起". 虽然相比ajax减少了一定的带宽压力, 但是对服务器的并发性能有较大要求.

WebSocket

作为最主流的Web实现方法, WebSocket 协议在2008年诞生，2011年成为国际标准。现在所有浏览器都已经支持了。它是一种全双工的通信协议, client和server是平等的.

它还有以下特点:

建立在 TCP 协议之上，服务器端的实现比较容易。
与 HTTP 协议有着良好的兼容性。默认端口也是80和443，并且握手阶段采用 HTTP 协议，因此握手时不容易屏蔽，能通过各种 HTTP 代理服务器。
数据格式比较轻量，性能开销小，通信高效。
可以发送文本，也可以发送二进制数据。
没有同源限制，客户端可以与任意服务器通信。
协议标识符是ws（如果加密，则为wss），服务器网址就是 URL

WebRTC

WebSocket是一种中心化技术, 那有没有去中心化的p2p实现呢? 有的, 就是WebRTC(Web Real-Time Communications) 它只需要一个信令服务器建立初始链接即可. STUN：STUN 是一种网络协议，其目的是进行 NAT 穿越。

当然, 信令服务器也可以使用WebSocket, 这就是多种技术的结合了. 但是WebRTC也是有缺点的, 因为大部分的client都是处于NAT环境下需要做穿透, 这一点的实现比较复杂.

还有一些不那么常见的协议这里就略去了.

同步策略

State Based

保存每次操作后的state并同步. 例如, 字符串Hello World, 我第一步删除了World, 第二步在Hello后加上了JavaScript, 那么传输到服务器的只有Hello JavaScript. 我们不难看出State Based同步策略不会记录操作流程而是直接将末状态同步至服务器并广播.

这种策略是最容易实现的, 也是最占带宽的, 而且基本不存在冲突处理的可能性.

Operational-based

保存至服务器的只有操作，客户端需要重新执行操作以还原状态。可以看作是State Based的优化版本，它的占用带款较小，实时性比较强，但是不能处理冲突的缺点仍然存在。

冲突解决方案

前面的同步方案只做到了基本的同步，针对冲突我们还需要专门的冲突解决方案。

lock

最简单的解决方案：加锁。只同时允许一个用户进行更改，避免冲突的可能。但是这样的话，我们也丧失了同时更改文件的可能性。

CRDT

CRDT全称为Conflict-free Replicated Data Type，分为State-based和Operation-based。我们在这以及以后的算法都只关注Operation-based。CRDT本质上是限制或者序号化了可用的操作。对于能够满足“可交换”的操作，允许直接执行。例如Add(), Swap()等。

举个例子：假设存在方法Add(x)，可以向服务器增加x，现在有用户A，B，分别发送了Add(1)，Add(2)，服务器初始值为0。

假设二者的操作是乱序到达服务器的。若A先到达，服务器：

0.Add(1).Add(2) // = 3

若B先到达：

0.Add(2).Add(1) // = 3

二者结果相同。于是这种方法就被CRDT所接受。

对于没有可交换性的，CRDT的方法很简单，对于每一个最小单元增加一个独立id，后期所有的操作均附上id，这样就不会出现冲突了。这个id不止针对于服务器id，还针对于客户端发送的数据。即CRDT通过id创建了一种不确定排序法则（例如当冲突时client的id小的排前面）来避免冲突。

CRDT看似很完美，但是还是有缺点的。小的缺点暂且按下不表，最大的缺点就是数据量大，对存储空间以及内存的要求比较高。

OT

OT（Operation Transfrom）是很多文档类同步（例如Google Docs）使用的冲突处理办法，核心就是当并发请求产生时，服务器根据接收的时间前后，将后接受的操作做一次第一次操作后的变换，并将新的操作重新传回客户端以实现双端同步。

举个例子，服务器有四个字符1111，现在两个客户端（几乎同时，A比B先通信到服务器）发送请求：

A->Server: insert(2,'2') // insert number '2' after second number.
B->Server: insert(2,'3') // insert number '3' after second number.
Server: 112311
Server->A: Transfrom:Flase, Action:"insert(3,'3')", TransfromAction:Null
Server->B: Transfrom:True, Action:"insert(2,'2')", TransfromAction: "insert(3,'3')"

其他板块

有了以上所提到的三大板块，你已经可以实现一个最基本的协同系统。

接下来就是围绕着这三个板块的。例如：从网络版块有心跳，重连，分布式等，编辑方面有权限管理等。

我们有以下的架构图：

协同系统
├── 通信层（WebSocket / RTC / PubSub）
├── 状态建模（Document Model）
├── 冲突处理（OT / CRDT）
├── Presence 系统
├── 权限与鉴权
├── Undo / 历史
├── 评论 / 审阅
├── 搜索与索引
├── 离线与缓存
├── 扩展性与分片
├── 安全与合规
└── 监控与运维