2 yjs

约 2492 字大约 8 分钟

2026-02-04

在分布式系统中，数据的复制和同步特别是当系统跨多个地理位置的节点时，数据一致性难以得到保障。传统的强一致性模型（如在数据库中使用的两阶段提交协议）通常会导致高延迟或低可用性，尤其是在网络断开或节点故障时。

协同编辑冲突解决：

直接覆盖，后面的修改覆盖前面的修改。一个大量的修改会被被后面的修改覆盖
锁机制：在编辑时锁定当前区域，其他用户无法编辑。会影响用户体验
差异对比：类似git的差异对比、合并，但多个用户同时修改同一区域时纯服务端无法处理，需要客户端手动处理冲突。需要额外的操作步骤和成本，实时性很差，不适合高频同时修改的场景。
OT：通过操作转换来实现数据的一致性。每个用户对数据的操作（如修改、删除等）都被记录下来，并在其他用户的客户端进行相应的转换，从而实现多个用户对同一份数据的协同编辑。它可以实时地反映用户的操作，并且可以很好地处理并发冲突。然而，OT 算法需要在中心化的服务器上进行协同调度，因此对于大规模的分布式系统来说可能不太适用。
CRDT：

OT

OT（Operational Transformation，操作转换），包含两个过程操作和转换。将文档的每一次修改看作是一个操作，即操作原子化处理，如在第 N 个位置插入一个字符时，客户端会将操作发送到服务端去处理。

采用中心化的思想，由服务端统一管理文档，客户端的修改操作发送到服务端，服务端修改后将操作分发给别的客户端客户端将原子化的操作发送到服务端时（必须有中央服务器进行调度），服务端对多个客户端的操作进行转换，对客户端操作中的并发冲突进行修正，确保当前操作同步到其他设备时得到一致的结果，因为对冲突的处理都是在服务端完成，所以客户端得到的结果一定是一致的，也就是说 OT 算法的结果保证强一致性。转换完成后，通过网络发送到对应客户端，客户端合并操作，从而得到一致结果。

示例： a和b同时修改一份文档，以下是初始文档

hello world

a在hello后面插入一个hi，消息结构如下所示

{
	op:'insert',//表示当前操作为插入操作
	index:4,//表示操作开始的索引是o
	value:'hi'//表示要插入的内容
}

b删除了world中的l，消息结构如下所示

{
	op:'delete',//表示当前操作为删除操作
	index:9,//表示操作开始的索引是l
}

服务端收到操作后会进行转换，比如a的操作先到达服务器就会先应用a的修改，文档变成以下内容：

hellohi world

这时对于服务端接收到的操作队列的后续操作就需要做出调整了，将b的操作消息更改成以下内容

{
	op:'delete',//表示当前操作为删除操作
	index:11,//表示操作开始的索引是l
}

OT 算法会通过一系列的变化来调整其中一个操作，而这个调整转化的核心就是transform方法，通过操作到达的时间顺序，对不同的操作进行修正，最终得到一致的结果。缺点：OT 算法对网络要求更高，如果某个用户出现网络异常，导致一些操作缺失或延迟，那么服务端的转换就会出现问题。

CRDT

CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型），是一种基于数据结构的无冲突复制数据类型算法，它通过数据结构的合并来实现数据的一致性。在 CRDT 算法中，每个用户对数据的修改都会被记录下来，并在其他用户的客户端进行合并，以实现数据的一致性。CRDT 算法的优点在于它可以适用于大规模的分布式系统，并且不需要中心化的服务器进行协同调度。但是，CRDT 算法在处理复杂操作时可能会存在合并冲突的问题，需要设计复杂的合并函数来解决。

CRDT有两种实现方式：

CmRDT：基于操作的 CRDT（OP-based-CRDT）：容易设计和实现，每个 CRDT 的整个状态最终都必须传输给其他每个副本，每个副本之间通过同步全量状态达到最终一致状态，开销很大；
CvRDT：基于状态的 CRDT，（State-based CRDT）：基于操作的 CRDT 只传输更新操作，各副本之间通过同步操作来达到最终一致状态，通常很小。

示例： 以计数器为例，计数器初始为0，a要加2，b要减1，CRDT算法可以容忍并发操作，每个节点都可以独立地改变计数器的值，而不需要协调。在这个例子中，CRDT算法可能采用向量时钟等技术，将每个节点的操作合并，得到一个合并后的计数器值1。最终所有节点都达到一个一致的值

向量时钟（Vector Clock）：一种在分布式系统中用于记录事件顺序的时间戳机制。它的主要目的是在分布式环境中实现事件的并发控制和一致性。向量时钟的基本思想是为系统中的每个节点维护一个向量，其中每个分量对应一个节点，用于记录该节点的事件发生次数。当一个节点发生事件时，它会增加自己分量的值。向量时钟的关键是在不同节点之间传递这些向量，并在合并时确保一致性。

步骤如下

事件发生：在分布式系统中，不同的节点（例如，多个客户端或服务器）都可以独立地发生事件。这些事件可以是用户的操作、消息的发送等。
向量时钟的基本思想：向量时钟是一种记录事件顺序的数据结构。每个节点都维护一个向量，向量的每个分量对应一个节点。分量的值表示对应节点的事件次数。当节点发生事件时，它会增加自己分量的值。
事件发生时的向量更新：当节点 A 发生事件时，它将自己的向量中对应分量的值增加 1。这样，每个节点的向量都会随着事件的发生而更新。
向量时钟的传递：当一个节点向另一个节点发送消息时，它会将自己的向量时钟传递给接收方。这样，接收方就能知道发送方的事件顺序。
合并向量时钟：当接收方收到消息并希望合并两个向量时钟时，它会比较两个向量的每个分量，选择较大的值作为合并后的值。这确保了在合并后的向量中，每个节点的事件次数都不会减少。
一致性和并发控制：向量时钟的设计旨在解决分布式系统中的并发控制问题。通过比较向量时钟，系统能够理解事件发生的顺序，从而确保在合并时保持一致性。

优点：

去中心化：减少对服务器的依赖，任意客户端可自行独立地解决冲突。
性能：CRDT 的性能已经超越传统 OT 的性能，并且由于 CRDT 的去中心化性质，可以容忍较高的延迟，并且可在离线模式下解决冲突。
灵活性和可用性：CRDT 支持更广泛的数据类型，像 Yjs 支持 Text、Array、Map 和 Xml 等数据结构，使其适用于更多业务场景。

OT vs CRDT

它们都提供了最终的数据一致性。不同之处在于他们做法不同：

OT 通过算法控制保证数据一致性：操作通过发送到服务端，一旦收到就会进行转换（ OT 控制算法）。
CRDT 通过数据结构保证数据一致性：操作是在本地 CRDT 上进行的，它的状态通过网络发送并与副本的状态合并。

不同点

OT 是基于中央服务器进行转换操作；而 CRDT 只需要与同伴交换新数据，不需要中央服务器，每个客户端都可以是独立完整的版本，因此稳定性很高。
OT 相较于 CRDT 发展更早，技术体系更为成熟，服务端压力大，客户端无需像 CRDT 那样存储大量额外元数据，因此压力较小。
OT 用复杂性换来了对用户预期的实现；而 CRDT 则更加关注数据结构，复杂性低，不过随着数据结构的复杂度上升，算法的时间和空间复杂度也会呈指数上升的，会带来性能上的挑战。
OT 处理不同数据模型需要实现不同的转换算法；CRDT 只需要转化数据结构。
CRDT 去中心化的特征，很容易实现离线编辑；