Loading...
Loading...
前段时间,我在刷微信公众号的时候,偶然间发现了一个有意思的推文:

当时我在脑海里简单构思了一下这个应用的大致解决方案——大概就是前端使用Canvas实时绘制画板操作,并同时向服务器传输本地的操作数据,然后服务器再向其它客户端同步状态。
因为实验室的师兄之前有做过类似的协同项目,所以就向他取了取经,不过因为他做的是协同文本编辑应用,所以可供我借鉴的思路并不多,更多的是需要我自己思考真正合适的实现方案。
因此,我在阅读完师兄当时的总结博客后,就去学了一下一些经典的协同算法,并开始了技术选型,准备亲手做一下上面那个画板项目。
分布式协同编辑领域是一个在业界比较老生常谈的话题了,其主要围绕协同环境中常见的矛盾问题展开研究,即如何保证所有客户端状态的一致性,换句话说就是,要怎么保证所有人看到的内容都严格一致,避免操作冲突导致内容混乱,多端之间无法统一协调的问题。这一系列问题,可以简化为以下几个比较常见的具体场景来讨论:
当两个客户端同时对同一个位置的内容产生修改时,例如一段文本:abc,用户A要在字符b的前面加一个X,用户B要删去字符b,当这两个操作同时进行时,受到网络传输和其它外部环境的影响,这两个操作最终在两个客户端上执行的顺序可能并不一致,从而导致最终两个人看到的内容并不一样。
当某个客户端处于弱网状态时,它的数据将会比同一批发出的数据包到达的更晚,从而导致原本有序的操作最终在网络空间中变成乱序到达的数据,破坏了客户端之间的一致性。
为了解决这些问题,业界诞生了两种比较常用的解决方案:OT和CRDT。
OT (Operational Transformation) ,即操作转换算法,于1989年在论文中被首次提出,它的核心思想就是对每个操作在实际应用前进行一次统一的操作转化(T),然后再推送给所有客户端,相当于是服务器在客户端渲染之前先对整体排一次序,对于有冲突的操作进行操作转换,再将处理后的操作交给客户端渲染,从而保证了所有客户端状态的一致性。
简单的说,OT就是在所有平级的客户端之上引入了一个裁判,它会裁定每个操作的执行顺序,并让每个客户端都严格按照它裁定的顺序进行渲染,从而达到了协同的目的,其核心概念“操作转换”的原理大致类似于这样:
还是上面那个文本abc的例子,我们给这三个字符分别赋予一个独立的位置,例如:
[1] a
[2] b
[3] c随后,用户A和用户B同时对位于位置2的字符b进行了不同的操作,对于用户A,如果没用OT的处理,它接收和执行的顺序应该类似于下面这样:
OpA('Insert', 'X', '2') -> OpB('Delete', '2')
OpA执行后:aXbc
OpB执行后:abc -> 实际删除的位置2上的内容并不是字符b,而是OpA刚刚插入的字符X对于用户B,它接收和执行的顺序则应该是这样:
OpB('Delete', '2') -> OpA('Insert', 'X', '2')
OpB执行后:ac -> 此时的位置2变成了字符c!
OpA执行后:acX很显然,在OT不插手的场景中,用户A和用户B最终看到的内容并不一致,它们后续的操作也会产生分歧,文档最后的状态就会混乱。
现在我们来看看OT是如何通过“操作转换”来解决这个问题的:
首先,服务端会对OpA和OpB进行一次排序,让所有客户端执行的顺序都相同,例如服务端强制要求每个客户端都要先执行OpA,再执行OpB,所有客户端都要确保自己收到服务端下发的顺序后再执行实际的渲染操作。
这里需要专门说明的是,对于后执行的OpB操作,由于它与前一个操作产生了冲突,导致OpB最终并不能正确的删除字符b,所以服务端会在执行前,对OpB进行一次操作转换:
原OpB:OpB('Delete', '2')
* 服务端在排序时发现,OpA执行后,原位置2上的字符b的位置会后移到位置3,触发操作转换:
T('OpA', 'OpB') -> 转换算法
转换后OpB:OpB('Delete', '3') -> 实际删除的位置变成了3,指向的还是字符b!OT在程序运行时动态的对每个操作进行冲突检测、操作转换,最终确保每个操作在实际执行时永远不会产生冲突。结果显而易见,最后所有客户端执行的操作顺序是一样的,那么最终的内容自然也会相同,这样就能确保所有客户端的状态严格一致了。
这就是OT的核心思想,也就是它名字的由来,这套算法的优缺点非常明显:
CRDT (Conflict-free Replicated Data Type),即无冲突复制数据类型,是一种与OT算法的思想截然不同的协同实现方案,旨在通过客观的数学定律,让客户端本身天然具有抵抗乱序数据、自动排序能力,甚至让整个协同系统去中心化。
CRDT主要分为两个流派,一种是基于状态的CRDT(State-based CRDT),另一种是基于操作的CRDT(Operation-based CRDT),顾名思义,一个着重于用状态同步多端数据,另一个则着重于用操作同步多段数据,但实际上它们是殊途同归的,互相之间也能很轻易的实现相互转化和兼容。
由于State-based CRDT在大多数场景中具有一些劣势,所以在工程实践中,一般很少用这种设计思想,所以下文主要介绍的CRDT默认是Operation-based CRDT。
CRDT 的核心思想其实可以用一句话概括:"让操作本身携带足够的信息,使得无论以什么顺序执行,结果都必然一致"。
与 OT 依赖服务端"裁判"进行动态转换不同,CRDT 把"排序逻辑"直接编码进了每个操作里。具体来说,每个操作都会携带两个关键信息:
interface SyncOperation {
id: string; // 全局唯一标识,如 `${clientID}-${seq}`
causality: { // 因果依赖信息
lamport: number; // 逻辑时钟,用于粗排序
deps?: string[]; // 显式依赖的操作ID
};
payload: { // 实际业务数据
type: 'add' | 'move' | 'delete';
targetId: string; // 操作目标的唯一ID
// ... 其它业务字段
};
}这样设计的好处是,客户端收到操作后,因为它所掌握的信息非常齐全,不需要问服务器"这个操作该插在哪",而是可以由客户端独立判断。
还是用上面那个 abc 文本的例子,我们来看看 CRDT 是怎么解决同样的问题的:
初始状态: "abc"
每个字符在底层其实都有一个唯一标识(用户不可见):
[uid-A] a [uid-B] b [uid-C] c当用户 A 想在字符 b 前面插入 X 时,它发出的操作不是简单的 Insert('X', 2),而是产生一个新的操作对象:
OpA: {
id: 'clientA-101', // 全局唯一ID
type: 'insert',
content: 'X',
after: 'uid-B', // 关键:指向"uid-B 这个节点之后",而不是"位置2"
timestamp: 1709000001 // Lamport逻辑时间戳,用于辅助排序
}同理,用户 B 想删除字符 b,发出的操作是:
OpB: {
id: 'clientB-205',
type: 'delete',
target: 'uid-B', // 关键:直接锁定"uid-B 这个节点",而不是"位置2"
timestamp: 1709000002
}注意到了吗?CRDT 的操作不依赖"位置索引",而是依赖节点的唯一 ID。这就从根本上避免了"位置漂移"的问题。
接下来,无论这两个操作以什么顺序到达客户端,执行逻辑都是:
after 或 target 找到对应的唯一 ID 节点(uid-B)。uid-B 后插入),就用 timestamp 或 id 的字典顺序决定先后。id 的操作重复到达时直接忽略。我们模拟两种乱序场景:
场景一:先收到 OpA,再收到 OpB
1. 执行 OpA: 在 uid-B 后插入 X → [a] [X] [b] [c]
2. 执行 OpB: 删除 uid-B → [a] [X] [c]
场景二:先收到 OpB,再收到 OpA
1. 执行 OpB: 删除 uid-B → [a] [c]
2. 执行 OpA: 在 uid-B 后插入 X → 虽然 b 被删了,但 uid-B 的"墓碑"还在,X 插在原来 b 的位置 → [a] [X] [c]显然,无论顺序如何,最终结果都是 aXc,而且 X 始终在原来 b 的位置附近,符合用户"在 b 前面加 X"的意图。
那么现在问题来了,为什么CRDT这样做就能保证一致?答案是因为依靠三条数学性质来让数据本身支持乱序操作:
exec(exec(state, op1), op2) = exec(exec(state, op2), op1)exec(exec(state, op), op) = exec(state, op)id来打破平局。只要操作设计满足这三条,网络怎么乱序、丢包、重传,最终都能收敛到同一状态。
总的来说,OT和CRDT的最终目的都是为了解决协同问题,但各自实现的思路不一样,甚至可以说是完全相反的。OT侧重于面向过程,在程序运行时动态对所有操作进行统一的管理和调配;而CRDT则更侧重于面向结果,利用客观的数学定律在客户端侧根据操作本身携带的信息进行静态的排序,但最终产出的结果都是一样的,区别在于OT 更像"中央调度",CRDT 更像"分布式共识"。
在深入了解完两套算法后,我最终选择了CRDT算法,因为我认为它更适合我理想中的设计模式,我做起来会更加顺手,同时它也能满足我“锻炼前端能力”的目标,因为OT的设计难度更多的是在服务端,而CRDT则更加考验客户端算法的设计水平,并且由于业界已经有诸如Yjs之类的较为成熟的CRDT库,也有Figma这种产品模式较为类似的商业化产品,因此在工程实践中,我能够获取的思路和方案也更多,能够催生出更多可行的方案,所以我选择了CRDT,并使用一个多月的事件构建了一个基于WebSocket的多人协同画板的最小可行方案:Aevia。
在设计这套系统时,我采用了前后端分离的设计模式,并分别使用了一些我熟悉的技术栈进行搭建:
在经过长时间的学习、搜索和思考后,我设计出了一套类似于CRDT的协同算法作为实际的画板协同方案——命令级空间包围盒(AABB 脏矩形)裁剪重绘算法。
首先来简单讲一下画板系统的一些正常工作流程和细节:
在架构设计上,客户端和服务端通过WebSocket通讯,客户端会将用户的每一次操作抽象为一个命令(Command):
interface Command {
id: string; // 命令唯一ID
type: 'path' | 'clear'; // 命令类型
tool?: 'pen' | 'eraser'; // 工具类型
color?: string; // 颜色值 (如:#ff0000)
size?: number; // 基础线宽
points?: Point[]; // 路径点数组 (如:[{x:0.5,y:0.5,p:0.5},...],x、y均为归一化坐标,p为压感)
timestamp: number; // 时间戳
userId:
其中,points属性是一个由Point对象组成的数组:
interface Point {
x: number; // 归一化坐标 (0-1)
y: number; // 归一化坐标 (0-1)
p: number; // 压力 (0-1)
lamport: number; // Lamport逻辑时间戳
}它们是一群组成整条线段的关键点,Canvas能在不同的设备上根据同一批关键点和其他有关信息画出完全相同的两条线。
客户端会维护一套命令队列,并使用Canvas上下文按序(Lamport时间戳)画出每一条线,服务端也会维护一套全局的命令队列,方便新用户进入时能快速同步所有历史记录。
假设用户在本地产生了一次新的path绘画操作,此时客户端会在队列中创建一个新的命令对象,记录命令的必要属性信息,接着向服务端发送一个start消息,触发对应的事件;在事件中,服务端首先会将命令注册到队列中,并广播给其它所有客户端,客户端在收到操作后,也会和发出消息的客户端执行同样的操作。
接着,用户的触点发生移动,线段开始不断延申和绘制,客户端就会持续采集用户的操作信息,当用户的移动范围大于一定范围时,便会记录一个新的关键点,加入命令队列对应的命令的points属性中,但不会立即发送,而是线暂存到一个临时的批处理缓存中,最后等待缓存中的点数量超过了限定的阈值后,客户端便会将缓存内的点一次性发给服务端,触发对应的update事件,服务端先是在队列中同步新点的信息,然后再广播给其它客户端,它们会在各自的队列和Canvas画板上实时更新数据,让其它用户看起来就像实时更新一样。
最后,用户的触点消失了,对应操作结束了,那么此时客户端就会最后记录一次点位信息,并将缓存中的所有点携带着一起发给客户端,触发stop事件,这个时候,命令就彻底完成了,服务端在接收到stop消息后的处理和update差不多,会先后进行点位同步和广播给客户端两个操作。
同时,为了在绘画中实现近似现实中的笔锋变化,画板在设计“绘画”功能时,对于线宽考虑了三个决定因素:基础线宽、速度和压力,基础线宽为用户在UI层面设置的画笔粗细,速度则是根据两个相邻关键点之间的距离计算出来的,而压力则是在具有压感能力的屏幕上使用PointEvent采集到的,它们彼此之间采用一个权重计算得出最终线宽:
const newWidth = clamp(lastWidth * 0.7 + targetWidth * 0.3, 1, baseSize + 2);这行代码实现了一个典型的指数平滑算法。根据当前速度和压感刚刚算出来的理想线宽(targetWidth)实际上只占了 30% 的决策权重,而上一个点遗留下来的历史线宽占据了 70% 的绝对权重。之所以要这么做,是因为用户书写时手部的力度和移动速度经常会发生大幅突变。通过这种加权混色式的平滑缓冲,能够强制弱化突变数据带来的影响,让线条在由粗变细时带有一种顺滑的阻尼过渡感,避免线宽突变。
最终绘制时,系统会采用 Canvas 的二次贝塞尔曲线画出一条平滑的曲线,而不是单纯用一段段直线连成一个锯齿状的线段。
读到这里时,相信你也发现了,这套流程好像并不是特别依赖CRDT,而是一套十分普通的协同设计。
这是对的,因为普通的协同场景并不太需要协同算法的特殊处理,但在某些极端场景中,它们的存在就显得尤为必要了:
在多人的实时网络下,经常会出现别人先画的线,最终因为网络卡顿导致最后才收到的情况。为了让这笔迟到的线段正确的回到它应该在的历史图层位置,我们就必须根据它诞生时携带的偏序逻辑时间戳(Lamport Timestamp)进行重新排队。
系统采用的是二分查找插入算法。每次有外来的 Command 到达,就会拿它和本地全局数组做折半比对。时间戳越小说明它落笔越早,就往数组更靠前的位置插队,以此来降低查找时的内存损耗。
同时为了打破两个异地用户在极低概率下刚好于同一时刻(Lamport时间戳相同)落笔导致的平局死锁,我们引入了硬性的保底规则:遇到时间戳相同时,直接对比它们各自携带的命令 ID 的 ASCII 码值大小,谁大谁排后面。这保证了无论在谁的电脑上,大家比对出来的排队纠错结果永远是数学上完全一致的,满足了CRDT核心的交换律思想。
当一个新用户进入房间时,会收到服务器推送的全量历史记录。按理来说按照这堆数据逐条绘制,理论上可以完全还原画板上的内容,使一个原本空空如也的白板同步成房间内其它人看到的样子。
但是,由于网络传输和多人同时操作的复杂性,服务器发来的这堆 Command 对象的物理先后顺序并不等于它们在画板上真实的上下层级关系,例如有两根线先后在不同的地方产生了交点,但第一个交点是第一条线最后经过,第二个交点是第二条线最后经过,而由于Canvas的状态遵循的是LWW(Last Writer Win)原则,所以最后逐条渲染出来的层级关系会错乱,如果第二根线对应的命令对象的时间戳更大的话,那这一整条线都会覆盖在第一条线的上面,包括那两个交点,这显然是不对的。
因此,为了完美还原画面,系统必须抛弃原有的逐条绘制逻辑,而是对每个关键点进行基于偏序逻辑的一套全量重绘。
首先,系统不看服务器下发时的数组索引,也不看每个Command中携带的 Lamport 时间戳,而是以附着在每个关键点上的 Lamport 时间戳为基准,将所有线段内的关键点彻底拆散、展开、打平成了一个包含成千上万个独立坐标点的一维时间数组,并按照 Lamport 时间戳和命令id进行一次严格的排序,并按顺序依次画到Canvas上。
例如打平后的数组长这样:
c1-p1 (0,0) -> 这是命令c1的点p1
c1-p2 (0,1) -> 命令c1往上方画了一条1像素长的线
c2-p1 (1,1) -> 这是一条新的命令c2的点p1
c3-p1 (2,4) -> 这是一条新的命令c3的点p1
c2-p2 (5,1) -> 命令c2往右边画了一条4像素长的线
c1-p3 (4,2) -> 命令c1往右上方画了一条线
...在实际渲染中,你可以想象画布上有很多个线头,每个线头都代表一条命令,Canvas从上往下依次读取每个点,并在不同的命令之间跳转,例如c1在画完p2后,下一个操作轮到c2了,那么c1的线头就会被暂时挂起,等到c2画完p2后,又轮到了c1继续画,那此时c1就会接着往它需要的地方画一笔。
这套机制一举解决了异步状态下的笔迹遮挡错误问题,它的核心优势在于:无论一个终端离线了多久、错过了多少次高并发的网络更新,只要它最终拿到这份数据并在本地展开重排打散,最后渲染出来的画面层级,与地球上任何一个正在协作的终端所看到的,在数学和视觉层面都必定是毫厘不差的,这也是CRDT交换律的体现。
这是整套协同算法的核心,前面提到了用来兜底纠错的“全量重绘”,但如果仅仅因为某人撤回了一条小弧线,或者因为一次网络延迟导致数据乱序,就要清空屏幕把几万条全部重新画一遍,这种消耗极不划算,将导致画板性能灾难性下滑。脏区域重绘就是为此诞生的终极优化方案。 脏区重绘主要会在三种情况下触发:
第一种是 网络延迟重绘,也就是发生了上面提到的,一条晚到的线通过二分插入,自己强行挤进历史老堆里导致曾经的层级错误时。
第二种是 交叉点撞车重绘,当两条时间戳相近甚至相同的线交汇时,由于两个设备可能因为网络原因,导致两条线在各自的画板上出现了不同的覆盖情况。
第三种是特殊操作引起的重绘,部分会对画板产生破坏性影响的操作会触发局部重绘,如撤回、重做、移动、变形、窗口尺寸变化等。
一旦系统发现这两种时空倒置操作,会立刻揪出引发异动的那条线段,读取它之前定稿时记录好的拓扑包围盒坐标。拿到这个正好能圈住它的矩形后,系统会在全量重绘前利用 Canvas 上下文激活 clip() 裁剪蒙版限制。
套上这个蒙版之后,系统再放心地去调用那套笨重的打平式全量重绘算法。此时由于底层硬件的重绘隔离,除了处在那个刚刚发生异动的狭小矩形范围内、和其他残影发生交叉的线段得到了重绘以外,矩形外的笔迹其实全被蒙版屏蔽了,连一帧多余的 CPU 计算资源都没有占用,重绘完全没有影响到其它的无关区域。这相当于把全屏刷新灾难极大地压缩成了微观级别。
在协同画板这类应用中,如果在绘制过程中因为两条线段发生了物理交叉而产生覆盖冲突,为了保证图层正确的遮挡关系,我们需要计算两者相交的最小脏矩形(AABB)并触发重绘。但如果每次光标移动画出一个点,都要粗暴地去和全屏几万点历史记录进行逐一比对,任何设备的 CPU 都会瞬间卡死。
为了解决这个碰撞检测的性能黑洞,系统在本地维护了一个被称作“全局哨兵”的滑动窗口队列。
之所以叫它“哨兵”,就是因为它真的就像一个哨兵一样,时刻盯着正在落笔的所有命令。它的核心机制是:
极简暂存:哨兵队列并不会将整个画布的历史点阵都存下来,它默认仅仅缓存最近 3 个连续的 Lamport 时间戳波次。
相交嗅探:当鼠标拖拽产生了一个新的坐标点时,这个点会被立即送进哨兵队列里。系统拿着这个新点周围算出的极小包围盒矩阵,去和哨兵队列里同时存在的、由其他人画出的有限邻近点做 AABB 相交重叠检测,判断它有没有与最近新画的其它点产生交叉。
动态触发:如果一旦算出来有交集,哨兵就会立即触发事件(point-collision):“这个位置发生了交叉,赶快把这部分包围盒拿去重绘!”而随着全网时钟的不断向前推进,当累计驻留超过 3 个时间波次后,那些安全通过的老网格点就会被这套滑动窗口无情清退并归档,不会再参与相交检测,而是自然的被比它更新的点覆盖。
延迟检测:当一个时间戳远小于当前队列中其它数据的时间戳的点进入队列,系统会立刻察觉到这个异常,并判断有可能是一个点因为网络延迟或其它原因,在传输过程中逗留了过长的时间才到达,而此时由于与它时间戳相近的点早已被渲染到画布上了,因此会直接触发事件(point-collision)进行局部重绘,将这个乱序的点插入到命令队列中正确的位置,并将其所处的区域进行一次局部重绘。 这套极致轻量的设计,将原本高达 O(N²) 的碰撞遍历运算强行压制在了常数级 O(1) 的微观视阀内,即完成了精准的区域时空碰撞检测,又绝不会产生内存膨胀。
它就像一个工厂的流水线一样,最大只能同时容纳三个产品,一旦有新的产品进来,旧的产品就会被自动弹出流水线,而如果有太久之前的产品因为上游卡死等原因迟到了,那么流水线入口处的负责人就会将它单独拎出来,丢到其它负责处理这种问题的产线上去,也就是前文提到的脏区域局部重绘机制。
同时,它也像一个哨兵,所有命令的举动都逃不过它的监视,一旦它发现两个命令产生矛盾了,就立刻拉响警报,让相关负责人介入和化解这场矛盾。
通过以上一系列的设计,我们最终实现了一套完整的协同算法,它能够抵抗弱网环境和传输损耗带来的乱序问题,也能在各种场景中保持所有用户最终看到的画面都是一致的,虽然它并不是完全参照的CRDT的设计模式,但在理念上,它属于是CRDT的一种变体,并且完全没有使用市面上的任何成套解决方案,而是自己从头设计了解决方案。
最关键的是,它的性能开销十分的可观,我在完成算法设计后,让 AI 使用 Playwright 写了一套压测脚本,观察了一下它的性能情况,结果也很意外:

在CPU四倍降速和完全禁用GPU的环境下,页面渲染十万个点仅需2秒,这已经是十分极端的场景了,现实中大部分的设备都至少能达到两倍降速以上的水平,并且GPU有一定的计算能力,实际的渲染耗时只会比这个数据更少,并且在十万点的环境下,实际内存占用仅百兆出头,部分场景在五万点出内存暴涨也是受限于测试环境压力过大、短时间内大量数据高强度的被创建、GC无法及时回收数据,导致内存在被清理前就被测试脚本记录了,在实际的使用中,一般不会发生这种情况,五万点的内存占用可能在30~50MB左右。
由此可见,这套算法的性能开销非常可观,在大部分设备上都能流畅渲染,高压环境也不会出现内存溢出、页面OOM的意外——它显然已经是一套比较成熟的协同算法了。
这个系统的复杂度在我做过的所有项目中能排到第一,不仅是因为实际工程实践中的实现比较难完成,同时也是因为整个协同领域对我来说也是一个全新的学科,我从最开始的完全不理解,到后来的一知半解,再到最后能够独立设计出一套协同编辑算法,这对于我的能力来说无疑是一个巨大的蜕变。
希望以后经常能接触到更多对我有很大帮助、且我热爱的项目。