2010年9月，Google Docs团队发布了一篇博客文章，宣布新版Google Docs采用了全新的协作架构。他们提到，旧版本需要约1秒钟来显示其他用户的编辑，而新版本将延迟降低到了毫秒级。这背后的技术——Operational Transformation（操作转换）——在之后的十几年里成为了实时协作的行业标准。
但OT有一个致命缺陷：它需要一个中心服务器来协调所有操作。如果你想做一个完全离线的协作应用呢？或者你想让用户在没有服务器的情况下也能同步数据呢？
这就是CRDT（Conflict-free Replicated Data Types，无冲突复制数据类型）要解决的问题。它不需要服务器协调，不需要锁定机制，甚至不需要网络连接——每个副本独立运行，最终却能达到一致状态。
数学上的保证
2011年，INRIA的研究员Marc Shapiro及其团队在分布式系统研讨会上发表了那篇开创性的论文《Conflict-free Replicated Data Types》。论文提出了一个惊人的结论：如果数据结构满足某些数学性质，那么无论用户如何并发操作，系统都能自动收敛到一致状态，且不需要任何同步机制。
这个结论的核心在于两个概念：单调半格（Monotonic Semilattice）和交换性（Commutativity）。
状态型CRDT（State-based CRDT，或称CvRDT）要求所有可能的状态构成一个半格结构。当两个副本合并时，计算它们的最小上界（Least Upper Bound）。由于半格的性质，这个合并操作满足交换律、结合律和幂等性——无论按什么顺序合并、合并多少次，最终结果都一样。
操作型CRDT（Operation-based CRDT，或称CmRDT）则走另一条路。它要求所有并发操作都满足交换律：如果操作A和B是并发的，那么先执行A再执行B，和先执行B再执行A，最终状态必须相同。
这两种方法在数学上是等价的。Shapiro的论文证明了任何CvRDT都可以被一个CmRDT模拟，反之亦然。
一个计数器的例子
想象一个分布式计数器。用户A在自己的副本上执行了3次增量操作，用户B在自己的副本上执行了5次增量操作。当他们同步时，最终结果应该是多少？
最简单的方案是G-Counter（增长计数器）。每个副本维护一个向量，记录每个节点执行的增量次数。当A执行increment时，它增加自己对应的向量分量。合并时，取两个向量的逐元素最大值。最终计数就是所有向量分量之和。
节点A的状态: [3, 0, 0] (A执行了3次increment)
节点B的状态: [0, 5, 0] (B执行了5次increment)
合并后: [3, 5, 0] (取逐元素最大值)
最终计数: 8
这个设计保证了一定正确，因为向量在每个维度上单调增长，而最大值操作满足半格的所有性质。
但G-Counter只能增量，不能减量。要支持减量，需要PN-Counter（正负计数器）。它由两个G-Counter组成：一个记录增量，一个记录减量。最终计数就是两者的差。
集合的挑战
计数器只是开始。真正的挑战在于集合（Set）——数据结构中最基础也最重要的类型之一。
普通的集合无法成为CRDT。假设用户A添加元素x，同时用户B删除元素x。当他们同步时，应该保留x还是删除x？这取决于操作顺序，但CRDT不允许依赖顺序。
解决方案是2P-Set（两阶段集合）。它维护两个集合：添加集A和删除集R（称为墓碑集）。查询时返回A - R。如果元素被删除，它会被加入R，之后即使再次添加也无效——因为元素同时在A和R中。
这导致了一个奇怪的行为：元素一旦被删除就不能再添加。这对于购物车这样的场景是不可接受的。
更好的方案是OR-Set（观测移除集合）。每个元素在添加时都获得一个唯一标识符。删除时只删除当前已知的那些标识符。这样，并发添加和删除可以和平共处：如果添加操作在删除之后到达，新添加的标识符不在删除集中，元素就会保留。
文本编辑：交织的噩梦
当CRDT用于文本编辑时，问题变得更加复杂。文本本质上是一个字符列表，而列表的插入和删除操作天然存在冲突。
早期的研究者提出了WOOT、Treedoc、Logoot、LSEQ等算法。它们都基于一个共同思路：给每个字符分配一个唯一标识符，标识符之间有全序关系。字符在文档中的位置由标识符的排序决定。
当用户在两个字符之间插入新字符时，算法生成一个新的标识符，这个标识符在排序上恰好位于两个相邻字符的标识符之间。听起来很优雅，但存在一个致命问题。
2019年，Martin Kleppmann等人在论文《Interleaving anomalies in collaborative text editors》中指出了这个问题：当两个用户同时在同一位置插入不同内容时，合并结果可能产生字符级别的交织。
假设文档最初只有一个换行符。用户A离线编辑，添加了"eggs"（每个字符依次插入）。用户B也离线编辑，添加了"bread"。当两人同步时，可能的结果是"ebgrgesad"——两个词的字符交织在一起，完全无法阅读。
这是因为Logoot和LSEQ等算法在生成标识符时，两个用户选择了相同的树路径，而tiebreaker（决胜机制）导致字符逐个交替排列。这个问题在之前的三十多年里几乎没有被正式讨论过。
2023年，Matthew Weidner和Martin Kleppmann在论文《The Art of the Fugue》中提出了Fugue算法。他们定义了一个新概念——最大非交织性（Maximal Non-Interleaving），并证明了FugueMax算法满足这个性质。在某些极端情况下，交织是不可避免的（数学上可以证明），但FugueMax能在所有可避免的情况下避免交织。
Fugue使用一棵双向树来表示文本序列。每个插入的字符成为树中的一个节点，可能是其左边字符的右孩子，也可能是其右边字符的左孩子。当并发插入发生在同一位置时，它们落在不同的子树中，深度优先遍历自然地保持了各自的连续性。
墓碑与内存代价
CRDT的一个经典批评是内存开销。删除的元素不能真正删除，必须保留为"墓碑"（tombstone），因为其他副本可能还持有针对该元素的并发操作。
对于一个活跃编辑的文本文档，墓碑的数量可能远远超过当前可见的字符数。早期的研究报告称每个字符需要数百字节的元数据。
但现代CRDT库已经大大优化了这个问题。Yjs的作者Kevin Jahns在2020年展示了，通过将连续插入的字符合并为单个"waypoint"对象，并使用Protocol Buffers编码，内存开销可以降低到每个字符约23字节——这已经足够实用。
另一个优化方向是垃圾回收。Yjs实现了墓碑回收机制：当所有副本都确认收到了某个删除操作后，对应的墓碑可以安全移除。但这需要一个额外的协调步骤。
OT还是CRDT？
既然OT在Google Docs等应用中工作良好，为什么还需要CRDT？
关键区别在于架构假设。OT假设存在一个中心服务器来序列化所有操作。当操作A和B并发到达服务器时，服务器决定一个顺序（比如A先于B），然后对B进行转换以考虑A的影响，最后将转换后的B广播给所有客户端。
这个设计有几个问题。首先，它需要服务器持续在线。如果服务器宕机，协作就会停止。其次，服务器的处理能力成为瓶颈——每个操作都需要服务器处理和转发。最后，对于复杂的操作类型，转换函数的正确性很难证明。历史上，多个OT算法被发现存在收敛性bug。
CRDT则完全不同。每个副本可以独立运行，不需要等待其他副本的确认。操作可以延迟到达、乱序到达，甚至永不到达——只要最终到达，系统就能收敛。这使得CRDT天然适合P2P架构和离线优先应用。
Figma的CTO Evan Wallace在讨论他们的协作架构时提到，Figma使用了一种混合方法：对于实时编辑，使用类似OT的技术来保证低延迟；对于离线场景，则依赖CRDT式的最终一致性。
Notion则选择了更简单的路径。据Notion工程师透露，他们的文本协作使用Last-Write-Wins策略，由服务器决定最终状态。这牺牲了某些一致性保证，但换来了实现的简单性。
性能之争：Yjs vs Automerge
当开发者选择CRDT库时，通常会面临Yjs和Automerge之间的抉择。这两个库代表了不同的设计哲学。
Yjs由Kevin Jahns开发，专注于文本编辑场景。它实现了YATA算法的一个变种，对内存和性能进行了极致优化。在基准测试中，Yjs处理一个包含260,000次编辑的真实文本编辑轨迹时，每秒可以处理约39,000次操作，内存使用约3.3MB。
Automerge最初由Martin Kleppmann用JavaScript实现，后来用Rust重写为Automerge 2.0。它提供了更丰富的数据类型（类似JSON的数据模型），但性能开销更大。在相同测试条件下，Automerge 2.0每秒处理约52,000次操作，但内存使用更高。
一个经常被引用的数据是：对于一份100页的文档，早期版本的Automerge需要约10秒和200MB内存来加载，而Yjs几乎可以瞬间完成。Automerge 2.0大幅改善了这个问题，但在纯文本编辑场景下，Yjs仍然有明显的性能优势。
选择哪个库取决于应用场景。如果核心需求是实时文本协作，Yjs是更好的选择。如果需要复杂的数据结构（嵌套对象、映射、列表组合）或者需要在不同语言之间共享状态，Automerge提供了更完整的解决方案。
本地优先软件的兴起
CRDT最重要的应用场景可能是"本地优先"（Local-First）软件。这个概念由Ink & Switch研究所在2019年的一篇论文中正式提出。
传统云应用假设网络始终可用。用户的数据存储在服务器上，客户端只是一个"瘦终端"。当网络断开时，应用变得无用。
本地优先软件则将数据主权还给用户。所有数据优先存储在本地设备上，云服务器只作为可选的同步媒介。用户可以在完全离线的状态下工作，当网络恢复时自动同步。
CRDT是实现本地优先软件的关键技术。它使得多个设备可以在没有协调服务器的情况下独立修改数据，最终自动合并。
典型的本地优先应用包括：
- 笔记应用：如Obsidian（使用Yjs进行实时协作）
- 任务管理：如Linear（使用自定义的同步协议）
- 设计工具：如Figma（使用混合OT/CRDT方法）
- 音乐制作：如某些DAW软件的协作功能
实现一个简单的CRDT
理解CRDT最好的方式是实现一个。下面是一个G-Counter的TypeScript实现：
class GCounter {
private counts: Map<string, number> = new Map();
private nodeId: string;
constructor(nodeId: string) {
this.nodeId = nodeId;
}
increment(): void {
const current = this.counts.get(this.nodeId) || 0;
this.counts.set(this.nodeId, current + 1);
}
value(): number {
let sum = 0;
for (const count of this.counts.values()) {
sum += count;
}
return sum;
}
merge(other: GCounter): void {
for (const [nodeId, count] of other.counts) {
const current = this.counts.get(nodeId) || 0;
this.counts.set(nodeId, Math.max(current, count));
}
}
getState(): Map<string, number> {
return new Map(this.counts);
}
}
// 使用示例
const counterA = new GCounter('node-a');
const counterB = new GCounter('node-b');
counterA.increment();
counterA.increment();
counterB.increment();
counterB.increment();
counterB.increment();
console.log(counterA.value()); // 2
console.log(counterB.value()); // 3
// 同步：A接收B的状态
counterA.merge(counterB);
console.log(counterA.value()); // 5
这个实现展示了CRDT的核心思想：状态可以独立演化，合并操作满足交换律和幂等性。无论合并多少次、按什么顺序合并，最终结果都相同。
现实世界的局限
CRDT不是万能药。它有几个重要的局限性需要注意。
首先是语义正确性。CRDT保证状态最终一致，但不保证这个状态有语义意义。例如，两个人同时修改同一个富文本段落的不同属性——一个加粗，一个改颜色——CRDT会保留两个修改，但结果可能不是用户期望的。解决这类问题需要更高级的冲突解决策略，或者放弃自动化，让用户手动解决。
其次是一致性约束。CRDT难以表达"如果A则B"这样的约束。一个经典例子是银行转账：账户A减少100元，账户B增加100元。这两个操作必须同时成功或同时失败。CRDT无法保证这种原子性——如果A的修改到达了而B的修改丢失，系统状态就会不一致。对于这类需求，需要使用分布式事务或其他一致性协议。
第三是历史依赖。某些CRDT（如操作型CRDT）需要保存操作历史来处理延迟到达的操作。这个历史可能无限增长。虽然可以定期压缩，但压缩需要协调——确定哪些操作已经传播到所有副本。
第四是调试困难。当CRDT应用出现问题时，追踪原因非常困难。操作可能以任意顺序到达，状态可能在任何时刻改变。传统的调试方法（断点、日志）在并发场景下效果有限。
未来的方向
CRDT研究仍在快速发展。几个值得关注的趋势：
形式化验证。研究者正在使用定理证明器（如Isabelle、Coq）来验证CRDT实现的正确性。Martin Kleppmann的团队开发了Automerge Model Checker（AMC），可以自动检查CRDT应用的行为是否符合规范。
性能优化。新的算法如Loro（2024年发布1.0版本）声称在某些场景下超越了Yjs。Loro使用了一种称为"delta-state CRDT"的技术，在状态传输和合并效率上做了优化。
语义扩展。传统的CRDT关注数据结构的收敛性，但忽略了用户意图。新的研究方向包括"意图保持"（Intention Preservation）——不仅保证最终状态一致，还保证最终状态符合用户的操作意图。
跨平台支持。随着Rust实现的成熟，CRDT正在被移植到更多平台。Yjs的Rust版本y-crdt、Automerge的多语言绑定，使得在iOS、Android、WebAssembly等平台上使用CRDT变得更加容易。
CRDT代表了分布式系统设计中的一个重要范式转变。它放弃了对强一致性的追求，转而保证最终一致性——不是通过协调，而是通过数学。
当你在协作文档中看到其他人的光标实时移动时，当你在飞机上编辑笔记、落地后自动同步时，当你的密码管理器在多个设备间无缝同步时——CRDT可能正在幕后工作。它是现代协作软件的隐形基础设施，一种将复杂的分布式系统问题转化为优雅的数学结构的艺术。
参考文献
-
Shapiro, M., Preguiça, N., Baquero, C., & Zawirski, M. (2011). Conflict-free Replicated Data Types. In Stabilization, Safety, and Security of Distributed Systems (SSS 2011). Grenoble, France.
-
Weidner, M., & Kleppmann, M. (2023). The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing. arXiv:2305.00583.
-
Kleppmann, M., Gomes, V. B. F., Mulligan, D. P., & Beresford, A. R. (2019). Interleaving anomalies in collaborative text editors. In 6th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC).
-
Kleppmann, M., Wiggins, A., van der Harden, P., & Macklin, M. (2019). Local-first software: You own your data, in spite of the cloud. In ACM SIGPLAN International Symposium on Software Langugage Engineering.
-
Attiya, H., Burckhardt, S., Gotsman, A., Morrison, A., Yang, H., & Zawirski, M. (2016). Specification and complexity of collaborative text editing. In ACM Symposium on Principles of Distributed Computing (PODC).
-
Nicolaescu, P., Jahns, K., Derntl, M., & Klamma, R. (2016). Near real-time peer-to-peer shared editing on extensible data types. In 19th ACM International Conference on Supporting Group Work.
-
Jahns, K. (2020). Are CRDTs suitable for shared editing? Blog post.
-
Automerge 2.0 announcement. https://automerge.org/blog/automerge-2/
-
Yjs Documentation. https://docs.yjs.dev/
-
Ink & Switch. Local-first software. https://www.inkandswitch.com/local-first/