引言
在分布式系统中，网络分区、节点故障和高延迟是不可避免的现实。工程师们始终面临一个核心矛盾：在允许副本独立写入的同时，如何保证数据不会出现不可调和的冲突？传统分布式事务（如 2PC、XA）虽然提供强一致性，但在网络分区时会导致系统完全不可用。CRDT（Conflict-Free Replicated Data Type，无冲突复制数据类型）为此提供了另一种思路：通过巧妙的数据结构设计，保证无论以何种顺序、在何种节点上执行操作，最终都能自动收敛到一致状态，无需协调、无需共识。
本文将从分布式系统一致性模型的谱论出发，深入剖析 CRDT 的数学基础（半格代数结构），然后逐一实现生产级 CRDT 数据类型：G-counter、PN-Counter、LWW-Element-Set、OR-Set、RGA 因果树。我们将引入向量时钟进行因果排序、处理 tombstone 垃圾回收问题，最终构建一个支持多端实时协作的分布式计数器与文档同步系统。
一、从 CAP 到一致性模型谱论
1.1 一致性强弱的光谱
分布式系统的一致性并非非黑即白，而是一个从强到弱的连续谱：
| 一致性级别 | 保证 | 典型系统 |
|---|---|---|
| Linearizability | 每个操作看起来是原子的、实时排序的 | Raft 提交读取、Redis 单实例 |
| Sequential Consistency | 所有节点看到相同操作顺序，但不保证实时性 | DynamoDB 默认模式 |
| Causal Consistency | 因果关系被保留，并发写入可能乱序 | MongoDB with causal session、AntidoteDB |
| Eventual Consistency | 若无新写入，最终会达成一致（无保证何时） | DNS、Amazon S3（旧版） |
CRDT 的最终一致性属于一个特殊子集：它不是简单的"最终会一致"，而是通过代数结构上的 merge 操作保证收敛，即达到一种强最终一致性（Strong Eventual Consistency, SEC）。SEC = EC 强收敛性 无需协调。
1.2 因果关系与向量时钟
分布式系统中每个事件的因果序可以用向量时钟（Vector Clock）精确表达：每个节点维护一个 N 维向量 V，当节点 i 发生本地事件时 V[i] ；发送消息时附带自身向量 V；接收消息时逐元素取 max 后 V[i] 。
对于任意两个事件 a 和 b：
- a → b（因果先于）：∀i, V_a[i] ≤ V_b[i] 且 ∃j, V_a[j]
发表评论 取消回复