多人协作算法

源页面：

• https://www.notion.so/57a48baf7123443b8dd0c32f9bf38216

标签：

• 题目
• Collaboration

页面摘要：

• 直接覆盖
• 锁机制
• diff-patch
• Operational Transformation（OT）
• Conflict-free Replicated Data Type（CRDT）

#OT

#简介

OT 通过算法控制保证数据一致性：操作通过发送到服务端，一旦收到就会进行转换。

首先用户的操作会被分解成一个个的原子操作。当用户操作之后，发送当前用户操作给服务器，由服务器根据其他人的操作记录进行转换，再分别转换为每个用户的原子操作进行分发，每个客户端执行分发下来的操作来保证同一份数据的一致性。

#优点

• 客户端压力小
• 满足用户的预期

#缺点

• 中央服务器依赖，压力较大
• 对网络要求更高，如果用户网络出现异常，则服务端转换就会出现问题
• 根据原子操作拆分的方式不同，算法实现也不同，复杂性高

#适用场景

• 可以拆分的原子操作较少的场景，例如在线文档、富文本编辑器
• 需要有人对协作算法十分熟悉

#CRDT

#简介

CRDT 通过数据结构保证数据一致性：操作是在本地 CRDT 上进行的，它的状态通过网络发送并与副本的状态合并。

CRDT 全称为 Conflict-free Replicated Data Type，即无冲突复制数据类型，是一种基于数据结构的无冲突复制数据类型算法，它通过数据结构的合并来实现数据的一致性。

在 CRDT 算法中，每个用户对数据的修改都会被记录下来，并在其他用户的客户端进行合并，以实现数据的一致性。CRDT 的优点在于它可以适用于大规模分布式系统，并且不需要中心化服务器进行协同调度；但在处理复杂操作时可能会存在合并冲突，需要设计复杂的合并函数来解决。

#优点

• 去中心化，减少对服务器的依赖，任意客户端可以自行独立解决问题
• 性能较好，在复杂网络中表现更加稳健，可以容忍较高延迟
• 支持更广泛的数据类型

#缺点

• 资源消耗更高，需要更多内存和存储来跟踪状态变更历史
• 某些实现为了合并状态和解决冲突，需要复杂算法
• 垃圾收集更难，历史数据不容易有效清理
• 为了保证副本同步，可能需要发送大量更新消息

#适用场景

• 不依赖编辑器实现，支持对接任意编辑器实现
• 适用于不了解多人协作算法的团队

#References

• 原页面末尾为书签引用，Notion 导出未提供可读标题，未继续展开。