协同编辑算法和 DIFF 算法实现思路¶

统计信息：字数 2168 阅读5分钟

对协同编辑和 diff 的一点想法记录

sockct 同步¶

socket 主要应用在多人聊天室，在线动态评论，文件协同编辑等场合，使用 socket 协议。

服务端和多个客户端如何同步？类似网络中广播报文的思路：客户端发送一个消息，服务端收到消息后，放入消息堆栈中，同时广播给全部客户端。其他客户端收到广播消息后，通过评论时间，更新本地的评论列表。

因为不同客户端的评论不会互相感染，所以这里不涉及 diff，直接把新获取的评论，push 到已有评论最后即可（时间复杂度O1）。如果同时收到多条评论，或者由于网络原因，服务端发送评论的顺序和客户端接收的评论顺序不一样，那么本地需要查找到合适的位置并插入评论（时间复杂度 OLogN）

协同：多个客户端对同一个数据更改，发送到服务端，或者在客户端之间同步，如何实现合并 diff 操作？

1、数据类型是简单格式（数字，字符串）：根据时间顺序，直接覆盖

例如 1 -> 2, 1-> 3 这两个行为，根据时间顺序，diff 后直接变成 3，覆盖原来的 2

2、数据类型是数组：遍历数组，如果不同内容，判断增删情况，实例是 git 操作

例如，一个文件是

const a = 10;
const b = 20;
const c = 30;
const d = 40;

另一个文件

const a = 10;
const b = 10;
const c = 30;
const e = 50;

那么 e 就是数组新增的一项，b 内容发生变化，需要手动比较，判断保留 master 还是使用新的 code

* const a = 10;

- const b = 20;
+ const b = 20;

* const c = 30;
* const d = 40;

+ const e = 50;

3 数据类型是复杂对象，例如 DOM 树或者 React 中虚拟 DOM

首先比较树节点的类型，如果类型不一致，直接删除旧节点，使用新节点渲染；

如果节点类型一致（都是 div）那么继续比较节点的下层节点 div.children，一直到比较完整树节点；

基于Dom Diff算法分析React刷新机制

Last update: November 9, 2024