CRDT 与最终一致性

• 用 CRDT 实现无冲突的最终一致副本
• 寄存器、计数器、集合等数据类型
• 多活写入的收敛性

Couchbase 与 Riak 等分布式数据库利用 CRDT 实现多活（multi-active）写入下的无冲突最终一致。它们内置多种 CRDT 数据类型（如计数器 G-Counter/PN-Counter、寄存器 LWW-Register、集合 G-Set/OR-Set、地图 Map），每个副本都可以独立更新，合并时通过 CRDT 的交换律/结合律/幂等律保证收敛到一致状态，无需锁定或协调。这样副本间发生网络分区时仍可各自写入，恢复后合并无冲突。Riak 的 conflict resolution 与 Couchbase 的 sync 功能都基于 CRDT 消除冲突。

CRDT 让数据库在"多活 + 分区"下仍能最终一致，代价是数据类型受限（需是可交换/结合/幂等的操作）。它把冲突解决从"运行时协调"转为"数据结构保证"，是 AP 数据库实现无冲突最终一致的关键。

• 文本 CRDT（RGA、YATA）实现无冲突文本合并
• 离线编辑与并发操作
• 无需服务器排序的收敛

Yjs 与 Automerge 等协同编辑库使用 CRDT 实现多人实时/离线编辑的文本合并。它们用文本 CRDT（如 RGA、YATA 算法）为每个字符分配唯一 ID 和顺序，多个用户并发插入/删除时，通过 CRDT 的合并语义（幂等、交换、结合）保证所有副本最终收敛到相同文本，无需中心服务器协调排序。用户离线编辑、联机后合并，操作不会冲突或丢失。这使协同编辑具备"离线优先 + 无冲突"的特性。

文本 CRDT 的核心是"每个字符唯一标识 + 稳定顺序"，使并发编辑可合并。Yjs（基于 YATA）与 Automerge（基于 RGA）是两大主流实现，解决了传统 OT 难实现与中心化的问题。

• join 半格的定义（偏序 + 最小上界）
• merge/lub 满足交换、结合、幂等
• 收敛性的数学基础

CRDT 的收敛性建立在 join 半格（join-semilattice）之上：CRDT 状态构成一个偏序集，任意两个状态都有最小上界（least upper bound，lub），即 join。merge 操作就是计算两个状态的 join（lub），它天然满足交换律、结合律、幂等律：merge(a,b)=merge(b,a)、merge(merge(a,b),c)=merge(a,merge(b,c))、merge(a,a)=a。正因为合并满足这三条性质，无论副本以何种顺序合并，最终结果都相同，从而保证收敛。状态 CRDT 的 merge 即求 join，操作 CRDT 则通过操作的正反抵消实现类似语义。

join 半格提供了"合并的数学保证"：可交换、可结合、幂等使任意合并顺序收敛到最小上界。这解释了为什么 CRDT 能无冲突收敛——它把分布式合并转化为数学上的 join 运算。

• LWW 用时间戳取最新写入者胜出
• vector clock 提供因果/新旧判断
• 处理并发写（concurrent）的取舍

LWW-Register 是一个寄存器 CRDT，每个写操作携带时间戳（或版本号），合并时取时间戳最大的值（最后写入者胜出）。它常配合 vector clock（或版本 vector）使用：vector clock 用于判断两个写入的因果先后关系，若一方更新（happens-before），则取更新者；若两者并发（无因果关系），LWW 用时间戳作为 tie-breaker 取较新者。配合使用时，LWW 提供确定性的冲突解决，vector clock 提供因果信息，二者结合实现"可预测胜出规则"的收敛。代价是 LWW 可能覆盖较旧但语义上更重要的并发更新。

LWW 的关键是"确定性胜出规则"，vector clock 帮助识别并发与因果。LWW 简单高效但可能丢失并发更新，故常与"冲突检测"配合，由上层决定是否保留。Riak 等系统用 vector clock 检测并发、用 LWW 或客户端解决冲突。

• 2P-Set 由 add-set 与 remove-set 组成
• remove-wins：元素无论在哪个集合都算被删
• 墓碑（tombstone）只增不减导致膨胀

2P-Set 由两个 grow-only 集合组成：add-set（只增）与 remove-set（只删，也即墓碑集合）。元素存在于 add-set 且不存在于 remove-set 时才算"在集合中"。remove-wins 语义：一旦元素被加入 remove-set，即使之后又被 add，也仍视为被删除（因为原子性操作要么全在要么全不在）。remove-set 只增不减是因为删除操作也需要可合并（幂等），若删除可被撤销则难以保证收敛。墓碑（remove-set 中的元素）只增不减导致集合无限膨胀，需通过"版本/时间戳 + GC"清理：当确认所有副本都已合并某墓碑后，可安全删除该墓碑并重写 add-set。

2P-Set 的 remove-wins 来自"删除集合只增不减"的单调性，保证并发删除与添加的收敛。墓碑膨胀是代价，需在确认全局合并后 GC，这是所有带删除语义 CRDT 的共性难题。

• 标准 CRDT 假设节点诚实
• Byzantine-CRDT 容忍恶意节点乱序/伪造
• 用签名、验证与容错机制增强

标准 CRDT 假设所有节点诚实地执行合并操作，若节点可能被攻击或作恶（拜占庭故障），其合并可能被破坏。Byzantine-CRDT 是 CRDT 的拜占庭容错扩展，通过引入消息签名、身份验证、状态校验与多数确认等机制，使 CRDT 在存在恶意节点时仍能收敛到一致状态。它通常需要额外的信任与验证开销，限制恶意节点伪造或篡改更新。这使 CRDT 可用于对抗性更强的环境（如不可信网络、联盟链）。

Byzantine-CRDT 在"无冲突合并"之上叠加"防恶意"层，用签名与验证保证更新可信。它牺牲部分性能换取拜占庭容错，是 CRDT 在对抗性场景的扩展，实际部署较复杂。

• δ-CRDT 只同步状态变化（delta）而非全量状态
• 减少带宽与合并开销
• 通过 delta 合并重建全量

δ-state CRDT 是状态 CRDT 的优化：标准状态 CRDT 合并时需交换整个状态，δ-CRDT 只交换"自上次同步以来的状态变化"（delta），从而显著降低带宽与合并开销。delta 是状态的一个子集，节点通过 apply delta 更新本地状态，多个 delta 通过 join 合并即可重建完整状态。δ-CRDT 保留了状态 CRDT 的收敛性（一致性与幂等/交换/结合），同时以差分方式同步，提升效率。它特别适合跨数据中心、网络资源受限的场景。

δ-CRDT 把"全量同步"优化为"差分同步"，在保持收敛性的前提下减少冗余传输。它把"状态"与"变化"解耦，是状态 CRDT 在工程上降低带宽的实用扩展。

• 用 CRDT 同步玩家状态、物品、成就
• 多区/多活副本最终一致
• 合并不冲突、离线恢复

在游戏服务器中，CRDT 用于同步玩家属性、背包物品、成就、社交数据等。多个游戏区服或副本可独立更新玩家状态，通过 CRDT 合并保证最终一致，避免复杂的冲突解决与锁。玩家离线期间的状态变化，联机后通过 CRDT 合并而不错乱。CRDT 的计数器、集合、寄存器等数据类型适合表达游戏数值与物品。它让游戏实现"多活 + 离线优先 + 无冲突"的状态同步，简化了跨区服一致性。

游戏状态的"多活 + 离线"特性与 CRDT 契合。CRDT 把冲突解决内化到数据结构，避免服务器协调，降低实现复杂度，代价是需把游戏状态建模为可合并的 CRDT 类型。

• CRDT 保证最终一致与因果一致
• 强一致性（线性一致）要求实时全序
• 两者的取舍与适用场景

CRDT 提供的是因果一致性与最终一致性：它保证有因果关系的操作按因果关系被观察到，且所有副本最终收敛到相同状态，但不保证"实时/线性一致"（操作不保证在返回时就对其他副本瞬时可见、全局顺序一致）。强一致性（如线性一致）要求任何读都返回最新且全局一致的顺序，通常需要共识协调。CRDT 以"无协调 + 最终一致"换取高可用与低延迟，适用于对实时强一致要求不高的场景（如协同编辑、缓存、社交数据）；强一致性适用于需要强事务语义的场景（如银行转账）。二者是"可用性/延迟"与"实时强一致"的权衡。

CRDT 的因果一致性保证"因果序列正确、最终收敛"，但不保证"实时全局一致"。强一致性则牺牲协调成本换取实时一致。理解二者差异有助于在系统设计中按需选择，避免过度强一致或过度弱一致。

• 每个节点维护一个只增计数
• 总值 = 所有节点计数之和
• 合并取各节点计数最大值

G-Counter 是只增计数器：每个节点维护向量中自己索引处的计数（只增不减），总值为所有节点计数之和。合并时对每个节点取最大值（因为各节点计数单调递增，取 max 保持可合并）。G-Counter 的合并满足交换、结合、幂等，因此并发递增后合并收敛到正确总和。它只能递增不能递减，递减需用 PN-Counter（增加负计数）。G-Counter 是 CRDT 中最简单、最基础的类型。

G-Counter 用"向量 + 逐节点取 max"实现无冲突的只增计数。它体现了 CRDT 的核心思想：把状态分解为可独立演进、可合并的部分，用单调合并保证收敛。常用作点赞数、访问量等只增指标。

• CvRDT 同步整个状态、合并需满足半格
• CmRDT 同步操作、需可靠因果有序信道
• 两者的收敛前提与适用场景

CmRDT（operation-based，操作型 CRDT）通过传播单个操作来传播更新，操作需满足可交换性，且依赖可靠、因果有序的信道（消息不丢失、按因果序到达），否则收敛性被破坏，但带宽低。CvRDT（state-based，状态型 CRDT）通过同步整个状态来传播更新，合并时用 join 半格语义（交换、结合、幂等），即使消息乱序、重复、延迟也能收敛，但对带宽要求高。注意：按论文定义，CvRDT 常指 state-based、CmRDT 常指 operation-based，两者对应不同传播模型。选择取决于信道可靠性：不可靠信道用 state-based，可靠有序信道用 operation-based。

两类 CRDT 的收敛前提不同：state-based 靠"合并幂等"容忍不可靠信道，operation-based 靠"可靠因果信道 + 操作可交换"保证收敛。工程上操作型更高效但依赖信道，状态型更健壮但带宽大。

• 每个元素带唯一 ID（tag）
• observe 机制：remove 只删自己观察到的 add
• 解决并发 add/remove 的歧义

OR-Set（Observed-Remove Set）是支持添加与删除的 CRDT 集合。每个元素在 add 时赋予唯一 ID（tag），add 操作把 (element, tag) 加入集合，remove 操作给元素附加一个 tombstone（删除标记），并记录"该 remove 观察到的 add 的 tag 集合"（observe 机制）。并发语义：remove 只删除"自己观察到的那些 add 的 tag"，若某 add 在 remove 之后并发到来（remove 未观察到该 add），则不会被删除，元素保留。这样并发 add 与 remove 不会产生歧义：remove 只针对已观察到的 add，未观察到的并发 add 得到保留，从而保证收敛（最终所有节点看到相同集合）。observe 机制正是 OR-Set 解决"并发 add/remove 顺序歧义"的关键：它把"删除"绑定到"被观察到的特定 add（tag）"，而非笼统删元素。

OR-Set 用"每个元素带 tag + remove 只删观察到的 tag"来消除并发 add/remove 的歧义：删除是有具体对象的（绑定到 tag），并发未观察到的 add 不会被误删，从而在所有副本上收敛到一致结果。

• 状态 CRDT 的 join（半格）合并
• 操作 CRDT 的操作应用与交换性
• 两者收敛前提的差异

状态 CRDT 的合并语义是"求状态的最小上界（join/lub）"：合并两个状态得到能包含两者信息的更"大"状态，合并满足交换、结合、幂等，因此任意顺序合并都收敛。操作 CRDT 的合并语义是"应用操作"：每个操作作用于状态，操作需满足可交换性（以及配套的因果传递），使任意顺序应用相同操作集得到相同状态，但前提是操作以可靠、因果有序的方式到达。区别在于：状态 CRDT 把"合并"内置为幂等运算、容忍乱序/重复；操作 CRDT 把"合并"分解为"应用可交换操作"，依赖信道有序。

状态 CRDT 的合并是"join 半格"，操作 CRDT 的合并是"可交换操作应用"。前者对信道健壮，后者需可靠因果信道但更高效。二者是同一思想在"状态 vs 操作"传播上的两种表达。

• 操作 CRDT 需操作以因果序到达
• 乱序/丢失导致操作应用顺序不一致
• 破坏交换性/收敛性

操作型 CRDT（CmRDT）通过传播操作更新副本，其收敛性依赖操作以"可靠、因果有序"的方式到达：所有操作必须按因果顺序被每个副本应用，且不丢失。若消息乱序，某副本可能先应用"因果后"的操作、再应用"因果前"的操作；若消息丢失，某副本可能缺少某些操作。虽然操作本身可交换（无因果关系的操作顺序无关），但一旦依赖关系（因果）被破坏，或操作缺失，副本应用的操作序列就不同，导致状态无法收敛到一致。因此 operation-based CRDT 必须架设在可靠因果信道上（如稳定 ordered broadcast），否则收敛性无从保证。

操作型 CRDT 把"收敛"的责任部分外包给信道：可交换性保证无因果操作顺序无关，但因果序与不丢失必须由信道保证。乱序/丢失会破坏因果序或操作集合的完整性，直接破坏收敛，这是它与 state-based CRDT"幂等合并容忍乱序"的本质区别。

• 三种律与任意合并顺序收敛的对应
• join 半格保证最小上界
• 不满足则合并结果依赖顺序、无法收敛

状态型 CRDT 的 merge 被设计为"求状态的最小上界（join）"，它必须满足幂等（merge(a,a)=a）、交换（merge(a,b)=merge(b,a)）、结合（merge(merge(a,b),c)=merge(a,merge(b,c))）。这三条性质保证了"无论副本以何种顺序、何种次数合并，最终结果都相同（收敛到最小上界）"，这正是分布式同步中消息乱序、重复、延迟下的收敛保证。若 merge 不满足这三条（例如交换律或结合律不成立），则合并结果依赖合并顺序，不同副本按不同顺序合并会得到不同状态，无法收敛到一致，最终一致性被破坏。

join 半格的三条律是状态 CRDT 收敛的充要条件。交换律消除顺序依赖、结合律消除分组依赖、幂等律消除重复影响，三者共同保证任意合并路径收敛到同一结果。任何一条失效都会导致收敛失败。

• 由两个 G-Counter 组成（增计数与减计数）
• 总值为增计数减减计数
• 支持递增与递减

PN-Counter 由两个 G-Counter 组成：一个记录所有递增（P 分量），一个记录所有递减（N 分量），总值为 P 分量之和减去 N 分量之和。每个节点对 P 和 N 各自维护只增的向量分量，合并时对各分量取 max。由于 P、N 都是 G-Counter（只增、可合并），PN-Counter 继承了可交换、结合、幂等性质，支持并发递增与递减并收敛到正确值。它解决了 G-Counter 只能递增的限制，可用于库存增减、用户余额等需要正负变化但最终一致的场景。

PN-Counter 用"两个只增计数器"把递减表达为"负方向的只增"，从而保持单调合并不变。这种"增/减分量的同构"是 CRDT 处理"有增有减"的通用技巧，也是原子计数器的典型实现。

• RGA 是基于顺序的文本 CRDT
• 每个字符带唯一 ID 与引用
• 并发插入/删除的收敛

RGA（Replicated Growable Array）是用于文本/列表协作的 CRDT 算法。每个字符（或列表项）由"唯一 ID + 引用前驱的 ID"标识，形成有序链表。并发插入时，新字符引用本地看到的前驱，通过比较顺序解决同一位置插入的冲突；删除时用墓碑标记。RGA 的合并满足 CRDT 的收敛性质，因此多个用户并发编辑同一文本（插入、删除、编辑）后，通过合并副本能收敛到同一结果。RGA 是 Automerge 等协同编辑库的基础，比 OT 更易实现离线与并发。

RGA 的核心是"每个字符唯一 ID + 前驱引用 + 墓碑删除"，通过稳定的顺序基线解决并发编辑。它把文本编辑建模为 CRDT，实现无冲突、离线优先的协同，是文本 CRDT 的经典算法。

• LWW 用时间戳解决最终一致冲突
• G-Counter 用单调计数解决计数并发
• 墓碑处理删除语义

在最终一致性系统中，冲突解决常借助特定机制：LWW（Last-Writer-Wins）用时间戳/版本号作为胜出规则，解决并发写冲突（取最新者）；G-Counter 用"每节点只增计数 + 合并取 max"解决并发递增的计数，无需时间戳；墓碑（tombstone）用于表达删除语义，记录"被删除的标记"使删除操作可合并、可收敛，避免删除与其他并发操作冲突。三者分别处理"寄存器冲突、计数冲突、删除冲突"，是最终一致性系统（如 Riak、Cassandra）中常见的冲突解决手段。代价是 LWW 可能丢失并发更新、墓碑导致存储膨胀。

最终一致性需要"确定性的冲突解决规则"：LWW 用时间、G-Counter 用单调性、墓碑用标记。它们把冲突解决从运行时协调变为数据结构/规则保证，使各副本无协调地收敛，代价是对语义灵活的取舍。