https://s3-us-west-2.amazonaws.com/secure.notion-static.com/49b038ad-e12a-4bbf-955f-7224ba79949b/416c991bb47c4a0e940158f212c600a4tplv-k3u1fbpfcp-zoom-crop-mark151215121512851.awebp
作为近年来分布式系统领域算法研究的新成果，CRDT 基础库为前端应用带来了奇妙的可能性：只需要一个 API 与 backbone 几乎一样简单的 model 层，你的应用就能自然地获得对多人协作场景下并发更新的支持。这背后隐藏着怎样的黑魔法呢？本文希望以当下代表前端 CRDT 库性能巅峰的 Yjs 为例，向大家直观地展示 how CRDT works。
https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d9fe96b2-cf7c-4df2-8bf3-1fac6befc247/c9ae97dcc7654d108a55fab04ece6c45tplv-k3u1fbpfcp-zoom-in-crop-mark4536000.awebp
（图为 Yjs 和其他前端主流 CRDT 库的性能对比，Yjs 对应底部的蓝线）
本文会从 Yjs 的工程实现出发，介绍一个典型的工业级 CRDT 库是如何实现以下能力的：
作为一份科普性的介绍，本文不会动辄甩出大段晦涩的源码，也不会涉及多少抽象的数学知识。阅读时只需了解数据结构方面的计算机基础即可。
在实际介绍 Yjs 内部概念前，我们该如何直观地了解 CRDT 库的使用方式呢？Yjs 对使用者提供了如 YText、YArray 和 YMap 等常用数据类型（即所谓的 Shared Types，这里把它们统称为 YModel），可以直接作为应用的 model 层使用：
import * as Y from 'yjs'
// 应用中的全部协作状态均可在单个 YDoc 容器中承载
// 将该实例传入 WebSocket 等协议的 provider 后即可支持网络同步
const doc = new Y.Doc()
// 在 YDoc 上可以创建不同类型的顶层 YModel 实例
// 这里创建了一个顶层名为 root 的 YMap
const yRoot = doc.getMap('root')
// 也可以用 class 构造器来实例化独立的 YMap 等 YModel
// 可直接用 get set delete 等常见 API 对 YModel 增删改查
const yPoint = new Y.Map()
yPoint.set('x', 0)
yPoint.set('y', 0)
// YMap 的值也可以是 YMap，从而构造出嵌套的数据类型
yRoot.set('point', yPoint)
// YMap 中还可以存入 YText 等其他 YModel，形成复合的数据类型
const yName = new Y.Text()
yName.insert(0, 'Wilson Edwards')
yRoot.set('name', yName)
复制代码
这套 API 表面看起来平淡无奇，但它真正的强大之处在于 Conflict-free，亦即对上层而言，并发更新时潜在的状态冲突已经被 Yjs 自动解决了：
// 可以用 2 份独立的 YDoc 实例来模拟 2 个客户端
const doc1 = new Y.Doc()
const doc2 = new Y.Doc()
const yText1 = doc1.getText()
const yText2 = doc2.getText()
// 在某份 YDoc 更新时，应用二进制的 update 数据到另一份 YDoc 上
doc1.on('update', (update) => Y.applyUpdate(doc2, update))
doc2.on('update', (update) => Y.applyUpdate(doc1, update))
// 制造两次存在潜在冲突的更新
yText1.insert(0, 'Edwards')
yText2.insert(0, 'Wilson')
// CRDT 算法可保证两份客户端中的状态始终一致
yText1.toJSON() // WilsonEdwards
yText2.toJSON() // WilsonEdwards
复制代码
透过这些 Yjs 表层 API 的例子，我们应该已经可以认识到 CRDT 的威力所在了。下面真正有趣的问题来了：Yjs 内部是如何实现这一能力的呢？
提到「底层原理」，很多同学可能会立刻会开始想象某种精妙的冲突解决算法。但在介绍这一算法前，我们最好先熟悉一下 Yjs 在工程上建模 CRDT 时所用的基础数据结构：双向链表。
在 Yjs 中，不论是 YText、YArray 还是 YMap，这些 YModel 实例中的数据都存储在一条双向链表里。粗略地说，这条链表中的每一项（或者说每个 item）都唯一地记录了某次用户操作所修改的数据，某种程度上和区块链有些异曲同工。可以认为上面例子中对 YModel 的操作，最后都会转为对这条链表的 append、insert、split、merge 等结构变换。链表中每个 item 会被序列化编码后分发，而基于 CRDT 算法的保证，只要每个客户端最终都能接收到全部的 item，那么不论客户端以何种顺序接收到这些 item，它们都能重建出完全一致的文档状态。