讲协同编辑,先回顾下从BBS、邮件,到IM
信息的生产和消费异步发生。
典型的场景如论坛,博客,文档库,邮件。我在写这篇文档的时候,你们看不到。你们看的时候,我早已写完。异步场景下,信息的生产者会谨慎的推敲措辞,以确保自己的意思被准确的传达。表达方式的丰富性很重要,除了文本以外,段落结构,列表,示意图,表格都有利于信息的准确表达。
信息被生产的同时被消费。
话出我之口,入你之耳,过了此时此刻,想还原此情此景,麻烦得很,大多时候也不需要。
同步场景下,信息的生产往往不需要深思熟虑,而是通过你来我往的讨论,澄清,逐步勾
勒出话题的全貌。表达的时效性较之方式的丰富性更为重要。典型的场景如即时通讯,语音通话,视频会议等。简单明了,没有太多的格式。
传统文档的信息表达方式是典型的异步传播。上述的几类异步场景都可见文档的影子。
然而2016年3月,Google上线的Google Docs颠覆了这个结论,这个改变世界的功能就是“多人实时编辑”,或者称作“协同编辑”。引入了协同编辑的在线文档,就像一块儿在线的白板,使得身处世界两端的人可以在上面共同迭代一个内容,通过你来我往的信息反馈,实现信息的同步传播。而编辑的结果又将沉淀下来,成为信息异步传播的载体。
兼具信息同步与异步传播的能力,协同文档的诞生,无疑给基于互联网的沟通协作带来了一场革命。
这场革命爆发于2006年,而它的起源,早在17年前。
1984 年,MIT 的科学家提出了计算机支持的协同工作(Computer Supported Cooperative Work,缩写为 CSCW),使得人们可以借助计算机和互联网去完成协同工作。
比如利用用于文档编辑的 Wikis 和用于编程的版本控制系统,小组成员可以在世界任意角落去共同编写大型的百科全书或软件系统。
协同文档现在貌似有很多公司陆续实现了,例如最早的 Google、国内的石墨文档、腾讯的腾讯文档等等。
这所谓的实时协同编辑,是指多人同时编辑一个文档,最典型的例子是 Google Docs,你可以实时看到别人做出的修改,不用手动刷新页面。
要实现实时编辑,我们需要解决两个技术点:实时通信问题、编辑冲突问题,其中实时通信问题比较好解决,可以使用 long pull 或 WebSocket,所以这里就不过多讨论了,如何解决编辑冲突问题上,可以查看《实时协同编辑的实现》
协同分析的这方面最敬仰的还是Google Wave,《协同编辑:Google Wave架构分析》,其架构的核心是操作转换 (Operational Transformation,OT),这是一个支持并发控制的理论型框架。
核心算法被称为 OT 算法。这个算法本身并不复杂,但是协同文档本身涉及更复杂的系统设计,因为它本身就是分布式的,至少客户端和服务端是分布式的。在较高性能的要求下,服务端可能也是分布式的。所以,如何使这些都能很好的协同,是很值得考虑的。
1989年,代表着“文档”的Microsoft Office第一次在Macintosh系统上与世人见面,而代表着“协同”的操作变换算法也第一次见诸论文。
Microsoft Office 中所周知,而操作变换算法又是什么呢?
关于OT算法,copy:https://imweb.io/topic/5b3ec8dd4d378e703a4f4450 内容如下:
实时协同编辑,通俗来讲,是指多人同时在线编辑一个文档,且当一个参与者编辑文档的某处时,这个修改会立即同步到其他参与者的计算机上。归纳起来,需要下面几个步骤:
由于没有锁的机制,当多个参与者在编辑同一处内容时,便可能出现冲突,这个时候就需要通过一定的算法来自动地解决这些冲突。最后,当所有改变都同步后,每个参与者计算机上所看到的文档内容应该是完全一致的。
How does Operational Transformation work? Here’s the short overview:
insert(12, 'A')
and insert(0, 'B')
. If we would simply send B’s operation to client A and applied it there, there is no problem. But if we send A’s operation to B and apply it after B’s operation has been applied, the character ‘A’ would be inserted one character one position left from the correct position. Moreover, after these operations, A’s document state and B’s document state wouldn’t be the same. Therefore, A’s operation insert(12, 'A')
has to be transformed against B’s operation to take into account that B inserted a character before position 12 producing the operation insert(13, 'A')
. This new operation can be applied on client B after B’s operation.However, you don’t have to understand the details of Operational Transformation to use it with this library in your own project.
一个文档可以被抽象为一系列操作的集合,这个集合便是 changeset。
对于 changeset,通常可以使用 json 的形式表示。
interface Action { type: string; // ...}interface Changeset {
version: number;
actions: Action[];
}
例如,下面的 changeset 是在协同表格的第 15 行后面添加一行,并删掉第 5 行。
{
"version": 0,
"actions": [
{
"type": "insertRowAfter",
"index": 15 },
{
"type": "deleteRow",
"index": 5 }
]}
注意:
上面说到过,changeset 只有基于某个版本才是有意义的。
假设, 有一个 A 客户端和一个 B 客户端,他们在某时刻具有一样的文档 $X$, 这时,A 做了 $A$ 操作,B 做了 $B$ 操作,他们本地的文档看上去已经不再一样,这时,我们便需要进行 协同
我们可能会采用 merge 的思路。意思是,将 A 的操作和 B 的操作在服务端进行 merge,然后分别应用到 X 上,即
$X ← Xmerge(A, B)$
但是,这显然不可取,因为无论在 A 还是 B 端,都已经分别是 $XA$, $XB$ 了
我们采用 follow 算法
follow 具有如下特征
follow 的以上特性使其很适合作为协同编辑的运算单元。
定义 $V_n=C_1C_2...C_n$ 为第 $n$ 版本的服务端的文档。
假设服务端的数据库存储了形如 $V_0→V_1→V_2→V_3→...→V_m→ ...→V_H$ 版本信息的某文档,则若有某 changeset $C_m'(m<n)$ 的变更需要应用到该文档,显然,$C_m'$ 不能直接应用到 $V_H$(版本不兼容)。这时,我们根据 follow 的特性,容易想到使用 follow 来做变换。
由于
$$ V{m+1}=V_mC{m+1} $$
即
$$ V{m+1} follow(C{m+1},Cm') = V_m C{m+1} follow(C{m+1},C_m') = V_m C_m' follow(C_m',C{m+1}) $$
由此我们可以得到一个
$$ C{m+1}' = follow(C{m+1},C_m') $$
同理
$$ C{m+2}' = follow(C{m+2},follow(C_{m+1},C_m')) $$
重复以上过程,可以得到一个相对于 $C_H$ 的 $C_H'$。在实现的时候,可以使用数组的 reduce
来进行。
得到该 $V_H'$ 之后,这个 changeset 可以应用到最新的文档 $V_H$ 上,这样便可以完成此次编辑。
客户端负责收集新的变更,生成 changeset 并发送给服务端, 客户端因此需要 维护一些状态、存在一定的生命周期。
$A$: 本地最新的版本,类比服务端的 $V_H$
$X$: 发送给服务端的 changeset,但是还没有得到服务端的确认
$Y$: 用户做的变更生成的 changeset,但是还没有发送给服务端
容易知道,本地文档看上去的样子显然应该是 $V=AXY$
当收到服务端推送过来的 changeset $B$ 时,客户端应该
证明:
$$ A'X'Y'= ABfollow(B,X)follow(follow(X,B),Y) $$
$$ A'X'Y'= AXfollow(X,B)follow(follow(X,B),Y) $$
$$ A'X'Y'= AXYfollow(Y,follow(X,B)) $$
$$ A'X'Y'= AXYD $$
$$ A'X'Y'=VD $$
当发送出去一个 changeset 的后,等待服务端的 ACK。当收到 ACK 的时候
这里暂时只举例只有一台服务器的情况
服务端在数据库中维护一个形如 ${V_n} = V_0→V_1→V_2→V_3→...→V_m→ ...→V_H$ 版本信息列表
当有活跃用户进入这个文档时,读入内存中
当一个 changeset $C$ 从客户端发送过来的时候
interface Change { type: string;
[k: string]: any;
}type Changeset = {
baseVersion: number;
changes: Change[];
} | null;type FollowFunc = (cs1: Changeset, cs2: Changeset) => Changeset;
定义 client:
定义 client 协同文档:
/// <reference path="common.d.ts" />export = CoSyncClient;interface DocumentLifecycle {}declare class Document{ constructor(followFunc: FollowFunc, documentId: string);
connected?(): void;
reconnected?(ws: WebSocket): void;
connectionLost?(reason: string): void;
connectionClosed?(reason: string): void;
connectionRejected?(reason: string): void;
applyChanges?(changes: Change[]): void;
makeEmpty?(): void;
edit(change: Change): void;
leaveDocument(): Promise<void>;
enterDocument(): Promise<void>;
}
declare namespace CoSyncClient { function createClient(
websocket: WebSocket ): {
Document: new (followFunc: FollowFunc, documentId: string) => Document;
getAllDocuments: () => Document[];
websocket: WebSocket;
};
}
定义 server:
onEnterRequest
的回调注册函数,该回调函数定义 server 协同文档:
/// <reference path="common.d.ts" />import WebSocket from "ws";declare class Document{ constructor(followFunc: FollowFunc, docuemntId: string);
getInitialDocument(): Promise<Set<Changeset>>;
saveChangeset(cs: Changeset): Promise<void>;
changesetWillBeHandled(cs: Changeset): void;
changesetWillBeAccepted(cs: Changeset): boolean | void;
changesetWillBeBroadcast(cs: Changeset): boolean | void;
private broadcast(cs: Changeset): void;
private sendInitialDocument(document: Set<Changeset>): void;
acceptEnter(): void;
rejectEnter(reason: string): void;
closeDocument(reason: string): void;
}
export = CoSyncServer;
declare namespace CoSyncServer { function createServer(
websocket: WebSocket ): {
getAllDocuments: () => Document[];
websocket: WebSocket;
onEnterRequest: (
cb: (
websocket: WebSocket,
documentId: string,
Document: new (followFunc: FollowFunc) => Document) => void,
once: boolean
) => void;
};
}
解决文本文档的协同编辑有两种方案,一种是 Google Doc 使用的 Operational transformation (OT),还有一种就是 Atom teletype 使用的 Conflict-free replicated data type (CRDT)。
CRDT 有两种形式:
CRDT 必须符合可交换性,结合性,还有幂等性,所以 CRDT 数据类型合并最终会收敛到相同状态。
为什么要符合可交换性,结合性,还有幂等性三个特性呢?因为可以解决分布式达到最终一致会遇到的问题:
OT主要用於文本,CRDT更通用
CRDT 不仅仅应用在协同编辑,还有分布式系统的最终一致性上也有应用。
因为 OT 中的 transformation 流程太复杂,OT 概念不是很清楚,而 CRDT 很好理解,实现起来也不难。
在因果关系的事件需要知道事件的先后顺序,并且能够按照正确的顺序处理这些事件,所以需要 Lamport timeStamp 来确定事件发生的事件,Lamport timeStamp 只需要保证两个规则就好了。
newTimeStamp[local] = Max(timeStamp[local], timeStamp[receive])
newTimeStamp[local] = timeStamp[local] + 1
每个客户端都有一个唯一 UUUID,再加上 Lamport timeStamp 就可以为每个操作添加唯一可排序的 ID。
每个操作都有唯一的 ID,接下来就是定义操作的数据结构,并且符合 CRDT 的特性,ID的唯一性可以保证操作的幂等性,操作可以排序保证了交换性,接下来只要保证每个操作都可以被合并就可以了。
id U0@T1 insert 'a' at index 0
id U0@T2 insert 'b' at index 1
id U0@T3 insert 'c' at index 2
id U0@T4 delete 'c' at index 2
id U0@T5 delete 'd' at index 2
一般会这样定义操作,但是这样的操作是线性依赖的,每个操作都是依赖前一个操作的结果,并发的时候,必须确保执行的顺序是一致的,有些操作可能合并会得到不一致的结果。
id U0@T1 insert 'a' at id null
id U0@T2 insert 'b' at id U0@T1
id U0@T3 insert 'c' at id U0@T2
id U0@T4 delete 'c' at id U0@T3
id U0@T5 insert 'd' at id U0@T2
服务端实现就比较简单了,只要提供 UUUID 还有 Lamport timeStamp 生成,还有就是接受客户端的操作,并且广播给其他客户端,因为后端使用 node 写的,还可以和前端公用一部分代码,实现就更方便。
参考文章:
Google Wave的架构 https://www.infoq.cn/article/2009/06/wave/,查看英文原文: Google Wave’s Architecture
协同文档的技术实现 https://imweb.io/topic/5b3ec8dd4d378e703a4f4450
实时协同编辑的实现 https://fex.baidu.com/blog/2014/04/realtime-collaboration/
文献:
Context-based Operational Transformation in Distributed Collaborative Editing Systems——COT算法论文
Google Wave Operational Transformation——G-Suite协同引擎的协议白皮书
Achieving convergence,causality-preservation, and intention-preservation in real-time cooperative editing systems——GOT算法及一维数据操作变换算法论文
Operational Transformation Frequently Asked Questions and Answers——南洋理工大学教授Chengzheng Sun的Survey,覆盖了OT领域绝大多数研究成果
转载本站文章《协同文档:OT与CRDT实现协同编辑笔记》, 请注明出处:https://www.zhoulujun.cn/html/webfront/engineer/Architecture/8564.html
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。