技术

协同编辑技术：OT 与 CRDT 学习

两种方式的学习和简要理解

在多人实时协作系统中（如 Google Docs, Figma），解决并发冲突、保证数据一致性主要有两条技术路线：OT 和 CRDT。

公司的主要画布产品没有使用这两个技术，而是部分画布锁+后写win的方案，严格意义上并不能算是协同编辑画布... 按你胃，这里学习一下两种常用协同编辑的处理方式.

1. OT (Operational Transformation - 操作变换)

OT 的核心思想是对操作进行转换。通常依赖一个中心服务器来规定操作的全局顺序。

核心逻辑

当两个用户同时对同一份文档进行操作时，服务端通过变换函数来调整操作的偏移量：

  • 变换函数：transform(op1, op2) -> (op1', op2')

  • 一致性目标：S∘op1∘op2′=S∘op2∘op1′S \circ op1 \circ op2' = S \circ op2 \circ op1'

    • op1' 是在应用了 op2 的基础上，对 op1 进行修正后的操作。
    • op2' 同理。

  • 可以发现变换函数抽象程度很高，所以实现难度必然复杂，需要考虑所有边界条件. 需要判断op1 op2到达服务端的顺序，所以无法离线使用

2. CRDT (Conflict-free Replicated Data Types)

CRDT 的思路是设计一种特殊的数学数据结构。 因为是一个数据结构，所以不像OT需要服务端进行转换，它可以离线使用

数学特性

CRDT 必须满足半格（Semilattice）性质，即操作需要符合：

  • 结合律 (Associativity)
  • 交换律 (Commutativity)
  • 幂等性 (Idempotency)

由于具备这些特性，无论操作以什么顺序到达、到达多少次，最终所有副本都能达成一致状态。

最简单的示例：G-Counter

  1. 每个副本（或每个参与者）维护一个局部的计数器。
  2. 当一个副本增加计数时，它只增加自己局部的计数。
  3. 当副本之间同步时，它们交换彼此的局部计数器集合（一个向量或映射）。
  4. 合并时，对每个参与者的局部计数器取最大值。
  5. 总计数是所有局部计数器之和。

e.g.

  • 客户端A的内部状态：{A: 5, B: 0} (A增加了5次)
  • 客户端B的内部状态：{A: 0, B: 3} (B增加了3次)
  • 客户端A同步到B后，A收到B的状态，合并：{A: max(5,0), B: max(0,3)} = {A: 5, B: 3}。总计数 = 8。
  • 客户端B同步到A后，B收到A的状态，合并：{A: max(5,0), B: max(0,3)} = {A: 5, B: 3}。总计数 = 8。

gcounter只能处理单向增加的计数问题，无法表达这种空间或时间上的关系，也不能表达顺序关系

还有很多其他的方式，比如RGA（加唯一id和时间戳）

加上id可以解决空间问题，加上时间戳可以解决时间问题...etc

3. 延申和一些灵感